6
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ what do mean by descendant vertices? Do you want to know which vertex is connected to which other vertex? How is your graph stored? $\endgroup$ Sep 2, 2020 at 10:38
  • $\begingroup$ Thank you for response! For a vertex in a DAG, its descendant vertices are the vertices that it can reach through the directed edges. For example, in the simple graph a->b->c, a has two descendant vertices (b and c), and b has one descendant vertex (c). For every vertex in the graph, I want to know its descendant vertices. The graph storage format is not certain, any format (such as adjacent list) can be used. $\endgroup$ Sep 2, 2020 at 11:28
  • 1
    $\begingroup$ Might be helpful cs.stackexchange.com/questions/69180/… $\endgroup$ Sep 2, 2020 at 14:17
  • $\begingroup$ You can create the transitive closure of the graph, and then answer reachability questions in $O(1)$. Algorithms are discussed in this CS.SE question. $\endgroup$ Sep 2, 2020 at 20:23
  • $\begingroup$ @KevinDalmeijer Thank you. But it seems that the complexity of creating transitive closure is also O(n^3) $\endgroup$ Sep 3, 2020 at 7:06

3 Answers 3

3
$\begingroup$

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:

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.