Index: pylib/gyp/common.py |
=================================================================== |
--- pylib/gyp/common.py (revision 1374) |
+++ pylib/gyp/common.py (working copy) |
@@ -401,3 +401,52 @@ |
seen[marker] = 1 |
result.append(item) |
return result |
+ |
+ |
+class CycleError(Exception): |
+ """An exception raised when an unexpected cycle is detected.""" |
+ def __init__(self, nodes): |
+ self.nodes = nodes |
+ def __str__(self): |
+ return 'CycleError: cycle involving: ' + str(self.nodes) |
+ |
+ |
+def TopologicallySorted(graph, get_edges): |
+ """Topologically sort based on a user provided edge definition. |
+ |
+ Args: |
+ graph: A list of node names. |
+ get_edges: A function mapping from node name to a hashable collection |
+ of node names which this node has outgoing edges to. |
+ Returns: |
+ A list containing all of the node in graph in topological order. |
+ It is assumed that calling get_edges once for each node and caching is |
+ cheaper than repeatedly calling get_edges. |
+ Raises: |
+ CycleError in the event of a cycle. |
+ Example: |
+ graph = {'a': '$(b) $(c)', 'b': 'hi', 'c': '$(b)'} |
+ def GetEdges(node): |
+ return re.findall(r'\$\(([^))]\)', graph[node]) |
+ print TopologicallySorted(graph.keys(), GetEdges) |
+ ==> |
+ ['a', 'c', b'] |
+ """ |
+ get_edges = memoize(get_edges) |
+ visited = set() |
+ visiting = set() |
+ ordered_nodes = [] |
+ def Visit(node): |
+ if node in visiting: |
+ raise CycleError(visiting) |
+ if node in visited: |
+ return |
+ visited.add(node) |
+ visiting.add(node) |
+ for neighbor in get_edges(node): |
+ Visit(neighbor) |
+ visiting.remove(node) |
+ ordered_nodes.insert(0, node) |
+ for node in sorted(graph): |
+ Visit(node) |
+ return ordered_nodes |