Given an acyclic directed graph, return a collection of collections of nodes "at the same level"?
<p>Firstly I am not sure what such an algorithm is called, which is the primary problem - so first part of the question is what is this algorithm called?</p>

<p>Basically I have a <code>DiGraph()</code> into which I insert the nodes <code>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</code> and the edges <code>([1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10])</code></p>

<p>From this I'm wondering if it's possible to get a collection as follows: <code>[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]</code></p>

<p>EDIT: Let me add some constraints if it helps.
- There are no cycles, this is guaranteed
- There is no one start point for the graph</p>

<p>What I'm trying to do is to collect the nodes at the same level such that their processing can be parallelized, but within the outer collection, the processing is serial.</p>

<p>EDIT2: So clearly I hadn't thought about this enough, so the easiest way to describe "level" is interms of <em>deepest predecessor</em>, all nodes that have the same depth of predecessors. So the first entry in the above list are all nodes that have 0 as the deepest predecessor, the second has one, third has two and so on. Within each list, the order of the <em>siblings</em> is irrelevant as they will be parallelly processed.</p>

<p>Your question states that you would like the output, for this graph, to be <code>[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]</code>. IIUC, the pattern is as follows:</p>

<ul>
<li><p><code>[1, 2, 4, 6]</code> are the nodes that have no in edges.</p></li>
<li><p><code>[3]</code> are the nodes that have no in edges, assuming all previous nodes were erased.</p></li>
<li><p><code>[4]</code> are the nodes that have no in edges, assuming all previous nodes were erased.</p></li>
<li><p>Etc. (until all nodes have been erased)</p></li>
</ul>

<p>Say we start with</p>

<pre><code>g = networkx.DiGraph()
g.add_edges_from([[1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10]])
</code></pre>

<p>Then we can just code this as</p>

<pre><code>def find_levels(g):
    levels = []
    while g.nodes():
        no_in_nodes = [n for (n, d) in g.in_degree(g.nodes()).items() if d == 0]
        levels.append(no_in_nodes)
        for n in no_in_nodes:
            g.remove_node(n)
    return levels
</code></pre>

<p>If we run this, we get the result:</p>

<pre><code>&gt;&gt;&gt; find_levels(g)
[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]
</code></pre>

<p>The complexity here is <em>&Theta;(|V|<sup>2</sup> + |E|)</em>. A somewhat more complicated version can be built using a <a href="https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times" rel="nofollow">Fibonnacci Heap</a>. Basically, all vertices need to be placed into a heap, with each level consisting of the vertices with 0 in degree. Each time one is popped, and the edges to other vertices are removed, we can translate this to a heap decrease-key operation (the in-degrees of remaining vertices are reduced). This would reduce the running time to <em>&Theta;(|V| log(|V|) + |E|)</em>.</p>

python algorithm graph graph-theory networkx