Given an acyclic directed graph, return a collection of node-level collections of nodes?

Question

Firstly, I'm not sure what is called such an algorithm, which is the main problem. So the first part of the question is what is called this algorithm?

I basically have DiGraph()one in which I insert the nodes [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]and the edges([1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10])

From this, I wonder if the collection can be obtained as follows: [[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]

EDIT: Let me add some limitations if this helps. - No cycles, this is guaranteed - There is no starting point for the schedule

What I'm trying to do is collect nodes at the same level so that their processing can be parallelized, but the processing inside the external collection is consistent.

EDIT2: So it is clear that I have not thought about it enough, so the easiest way to describe the “level” is through the gaps of the deepest predecessor, all nodes that have the same predecessor depth. Thus, the first entry in the above list is all nodes that have 0 as the deepest predecessor, the second one, the third two, and so on. In each list, the order of siblings does not matter, since they will be processed in parallel.

Answer 1

Your question indicates what you want for this graph to be [[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]. IIUC, the template is as follows:

• [1, 2, 4, 6] are nodes that have no edges.

• [3] - , , .

• [4] - , , .

• Etc. ( )

,

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]])

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

, :

>>> find_levels(g)
[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]

& Theta; (| V | ² + | E |). Fibonnacci Heap. , , 0 . , , , ( ). & Theta; (| V | log (| V |) + | E |).

Answer 2

, . Boost Graph Library , . toporder . .

template<typename F>
void 
scheduler<F>::set_run_levels()
{

  run_levels = std::vector<int>(tasks.size(), 0);
  Vertexcont toporder;

  try
    {
      topological_sort(g, std::front_inserter(toporder));
    }
  catch(std::exception &e)
    {
      std::cerr << e.what() << "\n";
      std::cerr << "You most likely have a cycle...\n";
      exit(1);
    }

  vContIt i = toporder.begin();

  for(;
      i != toporder.end();
      ++i)
    {
      if (in_degree(*i,g) > 0)
        {
          inIt j, j_end;
          int maxdist = 0;
          for(boost::tie(j,j_end) = in_edges(*i,g);
              j != j_end;
              ++j)
            {
              maxdist = (std::max)(run_levels[source(*j,g)], maxdist);
              run_levels[*i] = maxdist+1;
            }
        }
    }
}

, , , . , , ( _, ). , , . run_level ?

Answer 3

Why doesn't bfs solve? The bfs algorithm is a width traversal algorithm, i.e. Crosses a tree level. It also means that all nodes on the same level are traversed at once, which is your desired exit. As stated in the comment, this, however, will be the starting point on the chart.