digraphtools/digraphtools.py

   1 #! /usr/bin/env python
   2
   3 '''a collection of tools for working with directed acyclic graphs
   4
   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.
   7
   8 e.g.
   9
  10         graph = { 1: [2,3],
  11                   2: [3],
  12                   3: [] }
  13
  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)
  16
  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
  20 '''
  21 from collections import defaultdict,deque
  22
  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)
  26         '''
  27         graph = defaultdict(set)
  28         for a,b in edges:
  29                 graph[a].add(b)
  30                 graph[b]
  31         return dict((a,list(b)) for a,b in graph.items())
  32
  33 def copy_graph(graph):
  34         '''return a copy of a graph'''
  35         return dict((a,list(b)) for a,b in graph.items())
  36
  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])
  40
  41 def iter_partial_order(graph):
  42         return ((a,b) for b,a in iter_edges(graph))
  43
  44 def from_partial_order(edges): return [(a,b) for (b,a) in edges]
  45 to_partial_order = from_partial_order
  46
  47 class OrderViolationException(Exception): pass
  48
  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)
  53         '''
  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)
  58
  59 def postorder_traversal(graph, root):
  60         '''traverse a graph post-order and yield a list of nodes'''
  61         for n in graph[root]:
  62                 for traversed in postorder_traversal(graph,n):
  63                         yield traversed
  64         yield root
  65
  66 def dfs_topsort_traversal(graph, root):
  67         '''traverse a graph postorder while not traversing already seen nodes'''
  68         seen = set()
  69         for n in postorder_traversal(graph, root):
  70                 if n not in seen:
  71                         yield n
  72                         seen.add(n)
  73
  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
  78         path.append(root)
  79         yield path
  80         for n in graph[root]:
  81                 for traversed in dfs_traverse_iter_path(graph, n, path):
  82                         yield traversed
  83         path.pop()
  84
  85 def dfs_iter_edges(graph, root):
  86         '''traverse a graph depth-first and yield edges as they are traversed'''
  87         for n in graph[root]:
  88                 yield root,n
  89                 for edge in dfs_iter_edges(graph,n):
  90                         yield edge
  91
  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) )