How to find all descendant vertices of all vertices in a big DAG (Directed acyclic graph)?

Question

A simple algorithm may be traverse all vertices, and perform DFS for every vertex.

However, the computational complexity is $O(n(n+m))$, where $n$ and $m$ are the number of vertices and edges in the DAG, respectively. (Since $m \in O(n^2)$, the complexity is actually $O(n^3)$. Hope I'm right about the complexity).

For very big graphs, the complexity is unacceptable.

Is there any algorithm or idea that can solve the problem (reduce the algorithm complexity)?

Answer 1

The general strategy is as follows:

1. For each node, determine its in-degree.
2. Locate those nodes for which the in-degree is zero have no incoming edges (there will always be some since this is a DAG).
3. Add those nodes to a queue.
4. Pop nodes from the queue and process them.
5. For each node popped from the queue, decrement the in-degree count of its "downstream" neighbours. If a neighbour's count becomes zero, add it to the queue.
6. Repeat.

This algorithm can be parallelized across the "wavefront" of 0-in-degree cells either directly, or by using a parallelized matrix library.

Depending on the type of processing you want to do and whether or not your graph is already partitioned, it may be possible to achieve greater parallelism.

For instance, in this paper I wish to calculate the number of "upstream" nodes each node has in a 2 trillion node graph. Since my DAG is conveniently partitioned I can calculate this quantity with fixed per-cell and per-partition communication events achieving considerably more parallelism than the wavefront approach alone would allow.

For other resources you could consider the following papers:

• Distributed-Memory Breadth-First Search on Massive Graphs
• Parallel Breadth-First Search on Distributed Memory Systems

Both of these papers follow the kind of techniques described in the book Graph Algorithms in the Language of Linear Algebra and proposed in the GraphBLAS standard.

Answer 2

How about something like this:

• Copy the adjacency matrix.

• Count the out-valence of each node.

• Find all nodes X with 0 out-valence.

• Repeat until done:

  • For each node Y where Y→X is an edge:
    • Merge row X into row Y.
    • Reduce Y's out-valence by one.
  • Next X set will be the Y's whose out-valance just became 0.

• Each row of the resulting matrix will contain all descendant vertices of that node.

  E.g.

  A: B, C
  B: F
  C: G
  D: C, E
  E: H, I
  F: J
  G:
  H:
  I: J
  J:
  

  Adjacency:

     a b c d e f g h i j   #
  A: - 1 1 - - - - - - -   2
  B: - - - - - 1 - - - -   1
  C: - - - - - - 1 - - -   1
  D: - - 1 - 1 - - - - -   2
  E: - - - - - - - 1 1 -   2
  F: - - - - - - - - - 1   1
  G: - - - - - - - - - -   0
  H: - - - - - - - - - -   0
  I: - - - - - - - - - 1   1
  J: - - - - - - - - - -   0
  

  Resulting descendants:

  A: - 1 1 - - 1 1 - - 1
  B: - - - - - 1 - - - 1
  C: - - - - - - 1 - - -
  D: - - 1 - 1 - 1 1 1 1
  E: - - - - - - - 1 1 1
  F: - - - - - - - - - 1
  G: - - - - - - - - - -
  H: - - - - - - - - - -
  I: - - - - - - - - - 1
  J: - - - - - - - - - -
  

The use of matrices is an implementation detail. For sparse matrices, other representations would be better.

Answer 3

This is an interesting one. You could bring your graph into Reverse Polish Notation form, which allows you to create a stack of nodes and evaluate in one vector pass.

For what you want to do, you don't care about evaluation per se, but you can attach a "number of descendants" property to your nodes and propagate that organically as you would normally evaluate a graph - a "descendant arithmetic" if you will. The complexity for this should be roughly the same as evaluating the graph itself.