What's the most efficient algorithm for topologically sorting a (special case of a) directed acyclic graph?
<p>I have a data set that is a special case of a directed acyclic graph (DAG). The nodes in my DAG have either 0 or 1 arcs. All arcs are equally weighted (that is, the only information contained in an arc is the node it points at, no "distance" or "cost" or "weight").</p>

<p>My users will input nodes in a semi-random order, with the expectation that the order of arcless nodes be preserved, but all arcs get sorted before the nodes that point at them (so child-first ordering).</p>

<p>Here is a simplified class representing my data:</p>

<pre><code>class Node:
    def __init__(self, name, arc=None):
        self.name = str(name)
        self.arc = str(arc)
</code></pre>

<p>(note that <code>self.arc</code> is a string representation of the pointed-at node and not the object itself)</p>

<p>So, given an input like this:</p>

<pre><code>input = [Node('A'),
         Node('B'),
         Node('C'),
         Node('Z', 'Y'),
         Node('X', 'W'),
         Node('Y', 'X'),
         Node('W')]
</code></pre>

<p>You would get output like this, preferably using the fewest loops and intermediate data structures:</p>

<pre><code>output = [Node('A'),
          Node('B'),
          Node('C'),
          Node('W'),
          Node('X', 'W'),
          Node('Y', 'X'),
          Node('Z', 'Y')]
</code></pre>

<p>So far this is the best algorithm I've been able to come up with:</p>

<pre><code>def topo_sort(nodes):
    objects = {}           # maps node names back to node objects
    graph = OrderedDict()  # maps node names to arc names
    output = []
    for node in nodes:
        objects[node.name] = node
        graph[node.name] = node.arc
    arcs = graph.values()

    # optional
    missing = set(arcs) - set(graph) - {None}
    if missing:
        print('Invalid arcs: {}'.format(', '.join(missing)))

    def walk(arc):
        """Recurse down the tree from root to leaf nodes."""
        obj = objects.get(arc)
        if obj and obj not in output:
            follow_the_arcs(graph.get(arc))
            output.append(obj)

    # Find all root nodes
    for node in graph:
        if node not in arcs:
            walk(node)
    return ordered
</code></pre>

<p>What I like about this is that there are only 2 loops (one to build the graph and one to find the roots), and the output is built exclusively with <code>list.append()</code>, no slow <code>list.insert()</code>s. Can anybody think of any improvements to this? Any obvious inefficiencies I've overlooked?</p>

<p>Thanks!</p>

python algorithm python-3.x directed-acyclic-graphs topological-sort