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$
  • $\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$ – user3680510 Sep 2 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$ – LighTofHeaveN Sep 2 at 11:28
  • 1
    $\begingroup$ Might be helpful cs.stackexchange.com/questions/69180/… $\endgroup$ – user3680510 Sep 2 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$ – Kevin Dalmeijer Sep 2 at 20:23
  • $\begingroup$ @KevinDalmeijer Thank you. But it seems that the complexity of creating transitive closure is also O(n^3) $\endgroup$ – LighTofHeaveN Sep 3 at 7:06
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.

| improve this answer | |
$\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.

| improve this answer | |
$\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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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