1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#!/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():
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)
|
