1#!/usr/bin/env python3
2
3# Simple graph query utility
4# useful for getting answers from .dot files produced by bitbake -g
5#
6# Written by: Paul Eggleton <paul.eggleton@linux.intel.com>
7#
8# Copyright 2013 Intel Corporation
9#
10# This program is free software; you can redistribute it and/or modify
11# it under the terms of the GNU General Public License version 2 as
12# published by the Free Software Foundation.
13#
14# This program is distributed in the hope that it will be useful,
15# but WITHOUT ANY WARRANTY; without even the implied warranty of
16# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17# GNU General Public License for more details.
18#
19# You should have received a copy of the GNU General Public License along
20# with this program; if not, write to the Free Software Foundation, Inc.,
21# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22#
23
24import sys
25
26def get_path_networkx(dotfile, fromnode, tonode):
27    try:
28        import networkx
29    except ImportError:
30        print('ERROR: Please install the networkx python module')
31        sys.exit(1)
32
33    graph = networkx.DiGraph(networkx.nx_pydot.read_dot(dotfile))
34    def node_missing(node):
35        import difflib
36        close_matches = difflib.get_close_matches(node, graph.nodes(), cutoff=0.7)
37        if close_matches:
38            print('ERROR: no node "%s" in graph. Close matches:\n  %s' % (node, '\n  '.join(close_matches)))
39        sys.exit(1)
40
41    if not fromnode in graph:
42        node_missing(fromnode)
43    if not tonode in graph:
44        node_missing(tonode)
45    return networkx.all_simple_paths(graph, source=fromnode, target=tonode)
46
47
48def find_paths(args, usage):
49    if len(args) < 3:
50        usage()
51        sys.exit(1)
52
53    fromnode = args[1]
54    tonode = args[2]
55
56    path = None
57    for path in get_path_networkx(args[0], fromnode, tonode):
58        print(" -> ".join(map(str, path)))
59    if not path:
60        print("ERROR: no path from %s to %s in graph" % (fromnode, tonode))
61        sys.exit(1)
62
63def main():
64    import optparse
65    parser = optparse.OptionParser(
66        usage = '''%prog [options] <command> <arguments>
67
68Available commands:
69    find-paths <dotfile> <from> <to>
70        Find all of the paths between two nodes in a dot graph''')
71
72    #parser.add_option("-d", "--debug",
73    #        help = "Report all SRCREV values, not just ones where AUTOREV has been used",
74    #        action="store_true", dest="debug", default=False)
75
76    options, args = parser.parse_args(sys.argv)
77    args = args[1:]
78
79    if len(args) < 1:
80        parser.print_help()
81        sys.exit(1)
82
83    if args[0] == "find-paths":
84        find_paths(args[1:], parser.print_help)
85    else:
86        parser.print_help()
87        sys.exit(1)
88
89
90if __name__ == "__main__":
91    main()
92