toposort

gistfile1.py

# http://en.wikipedia.org/wiki/Topological_sorting
# sort build targets thanks to dependency information.
# 

def toposort(buildgraph):
   '''
   For topological sort:
   An edge from x to y means x needs to be done before y.
   This is the opposite of our graph where target A depends on a list of
   components.
   http://en.wikipedia.org/wiki/Topological_sorting
   '''
   output = []
   ready = set()
   # track incoming edges
   incoming = {}
   # track edges from component to corresponding build
   successors = {}
   # track total number of edges
   edges = 0
   for build, dependencies in buildgraph.items():
      incoming[build] = len(dependencies)
      edges += incoming[build]
      if incoming[build] == 0:
         ready.add(build)
      successors.setdefault(build, set())
      for component in dependencies:
         successors.setdefault(component, set()).add(build)
   while ready:
      component = ready.pop()
      output.append(component)
      edges -= len(successors[component])
      for build in successors[component]:
         incoming[build] -= 1
         if incoming[build] == 0:
            ready.add(build)
   assert edges == 0, 'graph has at least one cycle'
   return output


def test():
   '''
   graph structure

    5:            A
                  |
                  |
    4:            B
                 /|\
                / | \ 
    3:         /  |  D
              |   |   \
              |   |    \
    2:        C   |     I
              |   |    /|\
              |   |   / | \
    1:        E   |  K  |  \
            / | \ | /   |   \
           /  |  \|/    |    \
    0:    F   G*  H     G*    J

   '''
   graph = {
      'A.5': ['B.4'],
      'B.4': ['C.2', 'H.0', 'D.3'],
      'C.2': ['E.1'],
      'D.3': ['I.2'],
      'E.1': ['F.0', 'G.0', 'H.0'],
      'F.0': [],
      'G.0': [],
      'H.0': [],
      'I.2': ['G.0', 'K.1', 'J.0'],
      'J.0': [],
      'K.1': ['H.0'],
   }
   result = toposort(graph)
   for build, dependencies in graph.items():
      bindex = result.index(build)
      for component in dependencies:
         cindex = result.index(component)
         assert cindex < bindex, 'Dependency not respected'