diff options
author | Sylvain Th?nault <sylvain.thenault@logilab.fr> | 2010-04-16 17:44:42 +0200 |
---|---|---|
committer | Sylvain Th?nault <sylvain.thenault@logilab.fr> | 2010-04-16 17:44:42 +0200 |
commit | 928c40ff4808b6eebc3e52b9b1087ee948b09043 (patch) | |
tree | 0523241e0995d12576d41653293ff2675e79014f | |
parent | 2675e321d1d4e6b70fa79e9c7d003284f03dc844 (diff) | |
download | logilab-common-928c40ff4808b6eebc3e52b9b1087ee948b09043.tar.gz |
graph: new ordered_nodes method to return an ordered list of nodes from a graph
-rw-r--r-- | graph.py | 27 |
1 files changed, 27 insertions, 0 deletions
@@ -149,6 +149,33 @@ class GraphGenerator: return self.backend.generate(outputfile=outputfile, mapfile=mapfile) +class UnorderableGraph(Exception): + def __init__(self, cycles): + self.cycles = cycles + + def __str__(self): + return 'cycles in graph: %s' % self.cycles + +def ordered_nodes(graph): + cycles = get_cycles(graph) + if cycles: + cycles = '\n'.join(' -> '.join(cycle) for cycle in cycles) + raise UnorderableGraph(cycles) + ordered = [] + while graph: + # sorted to get predictable results + for node, deps in sorted(graph.items()): + if not deps: + ordered.append(node) + del graph[node] + for deps in graph.itervalues(): + try: + deps.remove(node) + except KeyError: + continue + return tuple(reversed(ordered)) + + def get_cycles(graph_dict, vertices=None): '''given a dictionary representing an ordered graph (i.e. key are vertices |