| Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 1 | #!/usr/bin/env python |
| 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 | |
| 24 | import sys |
| 25 | |
| 26 | def 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.read_dot(dotfile)) |
| 34 | |
| 35 | def node_missing(node): |
| 36 | import difflib |
| 37 | close_matches = difflib.get_close_matches(node, graph.nodes(), cutoff=0.7) |
| 38 | if close_matches: |
| 39 | print('ERROR: no node "%s" in graph. Close matches:\n %s' % (node, '\n '.join(close_matches))) |
| 40 | sys.exit(1) |
| 41 | |
| 42 | if not fromnode in graph: |
| 43 | node_missing(fromnode) |
| 44 | if not tonode in graph: |
| 45 | node_missing(tonode) |
| 46 | return networkx.all_simple_paths(graph, source=fromnode, target=tonode) |
| 47 | |
| 48 | |
| 49 | def find_paths(args, usage): |
| 50 | if len(args) < 3: |
| 51 | usage() |
| 52 | sys.exit(1) |
| 53 | |
| 54 | fromnode = args[1] |
| 55 | tonode = args[2] |
| 56 | paths = list(get_path_networkx(args[0], fromnode, tonode)) |
| 57 | if paths: |
| 58 | for path in paths: |
| 59 | print ' -> '.join(path) |
| 60 | else: |
| 61 | print("ERROR: no path from %s to %s in graph" % (fromnode, tonode)) |
| 62 | sys.exit(1) |
| 63 | |
| 64 | def main(): |
| 65 | import optparse |
| 66 | parser = optparse.OptionParser( |
| 67 | usage = '''%prog [options] <command> <arguments> |
| 68 | |
| 69 | Available commands: |
| 70 | find-paths <dotfile> <from> <to> |
| 71 | Find all of the paths between two nodes in a dot graph''') |
| 72 | |
| 73 | #parser.add_option("-d", "--debug", |
| 74 | # help = "Report all SRCREV values, not just ones where AUTOREV has been used", |
| 75 | # action="store_true", dest="debug", default=False) |
| 76 | |
| 77 | options, args = parser.parse_args(sys.argv) |
| 78 | args = args[1:] |
| 79 | |
| 80 | if len(args) < 1: |
| 81 | parser.print_help() |
| 82 | sys.exit(1) |
| 83 | |
| 84 | if args[0] == "find-paths": |
| 85 | find_paths(args[1:], parser.print_help) |
| 86 | else: |
| 87 | parser.print_help() |
| 88 | sys.exit(1) |
| 89 | |
| 90 | |
| 91 | if __name__ == "__main__": |
| 92 | main() |