diff options
author | Nicolas Chauvat <nicolas.chauvat@logilab.fr> | 2011-01-31 18:37:27 +0100 |
---|---|---|
committer | Nicolas Chauvat <nicolas.chauvat@logilab.fr> | 2011-01-31 18:37:27 +0100 |
commit | 9e33dcf029feb83c86aabf5b278e80e876fb2d3c (patch) | |
tree | 673ed2ff2ff473188badd60fc7be18abf6e10f1e /graph.py | |
parent | 59e46b0d804514c026479abe7b1562cfd70d16ca (diff) | |
download | logilab-common-9e33dcf029feb83c86aabf5b278e80e876fb2d3c.tar.gz |
graph: fix and test ordered_nodes() [closes #60288]
Diffstat (limited to 'graph.py')
-rw-r--r-- | graph.py | 48 |
1 files changed, 29 insertions, 19 deletions
@@ -165,11 +165,7 @@ class GraphGenerator: class UnorderableGraph(Exception): - def __init__(self, cycles): - self.cycles = cycles - - def __str__(self): - return 'cycles in graph: %s' % self.cycles + pass def ordered_nodes(graph): """takes a dependency graph dict as arguments and return an ordered tuple of @@ -179,24 +175,38 @@ def ordered_nodes(graph): Also the given graph dict will be emptied. """ + # check graph consistency cycles = get_cycles(graph) if cycles: cycles = '\n'.join([' -> '.join(cycle) for cycle in cycles]) - raise UnorderableGraph(cycles) - ordered = [] + raise UnorderableGraph('cycles in graph: %s' % cycles) + vertices = set(graph) + to_vertices = set() + for edges in graph.values(): + to_vertices |= set(edges) + missing_vertices = to_vertices - vertices + if missing_vertices: + raise UnorderableGraph('missing vertices: %s' % ', '.join(missing_vertices)) + # order vertices + order = [] + order_set = set() + old_len = None while graph: - # sorted to get predictable results - for node, deps in sorted(graph.items(), key=id): - 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)) - + if old_len == len(graph): + raise UnorderableGraph('unknown problem with %s' % graph) + old_len = len(graph) + deps_ok = [] + for node, node_deps in graph.items(): + for dep in node_deps: + if dep not in order_set: + break + else: + deps_ok.append(node) + order.extend(sorted(deps_ok)) + order_set |= set(deps_ok) + for node in deps_ok: + del graph[node] + return tuple(order) def get_cycles(graph_dict, vertices=None): |