File: graph-tred.py

package info (click to toggle)
botch 0.21-8
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 1,298,428 kB
  • sloc: xml: 11,924,948; ml: 4,497; python: 3,620; sh: 1,269; makefile: 319
file content (37 lines) | stat: -rwxr-xr-x 1,232 bytes parent folder | download
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
#!/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)