3 '''a collection of tools for working with directed acyclic graphs
5 A graph is represented as a dict which maps a node to a list
6 nodes connected via the outgoing edges of that node.
14 is a DAG represented by the edges (1,2) (1,3) (2,3)
15 where the edge 2tuple is in the form of (from,to)
17 Note: If a DAG represents dependencies, e.g. the edge (1,2) is taken
18 to mean "1 depends on 2", this is backwards from a binary relation.
19 (1,2) would be the relation 2P1
21 from collections import defaultdict,deque
23 def graph_from_edges(edges):
24 '''return a graph from a set of edges
25 edges are a 2tuple in the form of (from_node, to_node)
27 graph = defaultdict(set)
31 return dict((a,list(b)) for a,b in graph.items())
33 def copy_graph(graph):
34 '''return a copy of a graph'''
35 return dict((a,list(b)) for a,b in graph.items())
37 def iter_edges(graph):
38 '''return an iterator over every edge in a graph in the form (from,to)'''
39 return ((a,b) for a in graph.iterkeys() for b in graph[a])
41 def iter_partial_order(graph):
42 return ((a,b) for b,a in iter_edges(graph))
44 def from_partial_order(edges): return [(a,b) for (b,a) in edges]
45 to_partial_order = from_partial_order
47 class OrderViolationException(Exception): pass
49 def verify_partial_order(partial_order, items):
50 '''verify that the order of items supplied satisfies the dependency graph
51 raises OrderViolationException unless a<b for every aPb in the partial order
52 (i.e. if a task is inserted before any of it's dependencies)
54 itempos = dict((item,pos) for pos,item in enumerate(items))
55 for a,b in partial_order:
56 if itempos[a] >= itempos[b]:
57 raise OrderViolationException("item '%s' is in the order before it's dependency '%s'" %( repr(b),repr(a)),items)
59 def postorder_traversal(graph, root):
60 '''traverse a graph post-order and yield a list of nodes'''
62 for traversed in postorder_traversal(graph,n):
66 def dfs_topsort_traversal(graph, root):
67 '''traverse a graph postorder while not traversing already seen nodes'''
69 for n in postorder_traversal(graph, root):
74 def dfs_traverse_iter_path(graph, root, path=None):
75 '''depth first traversal of graph generating every path seen'''
76 if path == None: path = []
77 if root in path: return
81 for traversed in dfs_traverse_iter_path(graph, n, path):
85 def dfs_iter_edges(graph, root):
86 '''traverse a graph depth-first and yield edges as they are traversed'''
89 for edge in dfs_iter_edges(graph,n):
92 def get_connected_subgraph(graph, root):
93 '''return the connected subgraph visible from supplied root node'''
94 return graph_from_edges( dfs_iter_edges(graph,root) )