diff options
author | Sylvain Thenault <sylvain.thenault@logilab.fr> | 2008-10-03 14:23:29 +0200 |
---|---|---|
committer | Sylvain Thenault <sylvain.thenault@logilab.fr> | 2008-10-03 14:23:29 +0200 |
commit | cdb9fabfa44b235c47b38b0cf86e8020f1fe9ba3 (patch) | |
tree | 3d782b09a8aa86dd66e05668d6f63fab735f8361 /graph.py | |
parent | 89670478d8402324475f0ea8ff3d51146f453f70 (diff) | |
download | logilab-common-cdb9fabfa44b235c47b38b0cf86e8020f1fe9ba3.tar.gz |
new has_path method
Diffstat (limited to 'graph.py')
-rw-r--r-- | graph.py | 19 |
1 files changed, 19 insertions, 0 deletions
@@ -175,3 +175,22 @@ def _get_cycles(graph_dict, vertice=None, path=None, result=None): except KeyError: pass path.pop() + +def has_path(graph_dict, fromnode, tonode, path=None): + """generic function taking a simple graph definition as a dictionary, with + node has key associated to a list of nodes directly reachable from it. + + Return None if no path exists to go from `fromnode` to `tonode`, else the + first path found + """ + if path is None: + path = [] + elif fromnode in path: + return False + path.append(fromnode) + for destnode in graph_dict[fromnode]: + if destnode == tonode or has_path(graph_dict, destnode, tonode, path): + return path[1:] + path.pop() + return None + |