From 928c40ff4808b6eebc3e52b9b1087ee948b09043 Mon Sep 17 00:00:00 2001 From: Sylvain Th?nault Date: Fri, 16 Apr 2010 17:44:42 +0200 Subject: graph: new ordered_nodes method to return an ordered list of nodes from a graph --- graph.py | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) (limited to 'graph.py') diff --git a/graph.py b/graph.py index 638e96a..d4f55cd 100644 --- a/graph.py +++ b/graph.py @@ -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 -- cgit v1.2.1