#!/usr/bin/python3

import networkx as nx
import sys
sys.path.append('/usr/share/botch')
from util import read_graph, write_graph


def transitive_reduction(g):
    for n1 in g.nodes_iter():
        if g.has_edge(n1, n1):
            g.remove_edge(n1, n1)
        for n2 in g.successors(n1):
            for n3 in g.successors(n2):
                for n4 in nx.dfs_preorder_nodes(g, n3):
                    if g.has_edge(n1, n4):
                        g.remove_edge(n1, n4)
    return g

if __name__ == '__main__':
    import argparse
    parser = argparse.ArgumentParser(
        description="find the transitive reduction of a graph in GraphML "
                    "or dot format"
    )
    parser.add_argument("g", type=read_graph, nargs='?', default='-',
                        help="Input graph in GraphML or dot format (default: "
                        "stdin)")
    parser.add_argument("h", type=write_graph, nargs='?', default='-',
                        help="Output graph in GraphML or dot format "
                        "(default: stdout)")
    parser.add_argument(
        '-v', '--verbose', action='store_true', help='be verbose')
    args = parser.parse_args()
    h = transitive_reduction(args.g)
    args.h(h)
