# pyobjc / build-support / topsort.py

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76``` ```""" Module defining a topological sort function, see for more information. Original topological sort code written by Ofer Faigon (www.bitformation.com) and used with permission """ def topological_sort(items, partial_order): """ Perform topological sort. items is a list of items to be sorted. partial_order is a list of pairs. If pair (a,b) is in it, it means that item a should appear before item b. Returns a list of the items in one of the possible orders, or None if partial_order contains a loop. """ def add_node(graph, node): """Add a node to the graph if not already exists.""" if node not in graph: graph[node] = [0] # 0 = number of arcs coming into this node. def add_arc(graph, fromnode, tonode): """Add an arc to a graph. Can create multiple arcs. The end nodes must already exist.""" graph[fromnode].append(tonode) # Update the count of incoming arcs in tonode. graph[tonode][0] += 1 # step 1 - create a directed graph with an arc a->b for each input # pair (a,b). # The graph is represented by a dictionary. The dictionary contains # a pair item:list for each node in the graph. /item/ is the value # of the node. /list/'s 1st item is the count of incoming arcs, and # the rest are the destinations of the outgoing arcs. For example: # {'a':[0,'b','c'], 'b':[1], 'c':[1]} # represents the graph: c <-- a --> b # The graph may contain loops and multiple arcs. # Note that our representation does not contain reference loops to # cause GC problems even when the represented graph contains loops, # because we keep the node names rather than references to the nodes. graph = {} for v in items: add_node(graph, v) for a,b in partial_order: add_arc(graph, a, b) # Step 2 - find all roots (nodes with zero incoming arcs). roots = [node for (node,nodeinfo) in graph.items() if nodeinfo[0] == 0] # step 3 - repeatedly emit a root and remove it from the graph. Removing # a node may convert some of the node's direct children into roots. # Whenever that happens, we append the new roots to the list of # current roots. sorted = [] while len(roots) != 0: # If len(roots) is always 1 when we get here, it means that # the input describes a complete ordering and there is only # one possible output. # When len(roots) > 1, we can choose any root to send to the # output; this freedom represents the multiple complete orderings # that satisfy the input restrictions. We arbitrarily take one of # the roots using pop(). Note that for the algorithm to be efficient, # this operation must be done in O(1) time. root = roots.pop() sorted.append(root) for child in graph[root][1:]: graph[child][0] = graph[child][0] - 1 if graph[child][0] == 0: roots.append(child) del graph[root] if len(graph.items()) != 0: # There is a loop in the input. return None return sorted ```