A function definition for directed acyclic graphs

Question

Let's consider the following problem: For a directed acyclic graph G = (V,E) we define the function "levels" for each vertex u, as l(u) such that:
1. l(u)>=0 for every u
2. If there is a path from u to v (u -> v) then l(u)>l(v)
3. For each vertex u, l(u) is the minimum integer that satisfies both conditions 1 and 2.

The problem says:
a. Prove that for every DAG the above function is uniquely defined, i.e. it's the only function that satisfies conditions 1,2 and 3.
b. Find an O(|V| + |E|) algorithm that calculates this function for every vertex.

Here is a possible algorithm based on topological sort: First we find the transpose of G which is G^T, defined as G^T = (V,E^T), where E^T={(u,v): (v,u) is in E} which takes O(|V|+|E|) in total if based on adjacency list implementation: (O(|V|) for allocation and sum for all v in V of |Adj[v]| = O(|E|)). Topological sort takes Theta(|V|+|E|) since it includes a BFS and |V| insertions in list each of which take O(1).

TRANSPOSE(G){
    Allocate |V| list pointers for G^T i.e. (Adj'[])
    for(i = 1, i <= |V|, i++){
        for every vertex v in Adj[i]{
            add vertex i to Adj'[v]
        }
    }
}
L = TopSort(G)

IVlad IVlad · Accepted Answer · 2015-02-20T20:28:29

a. Prove that for every DAG the above function is uniquely defined, i.e. it's the only function that satisfies conditions 1,2 and 3.

Maybe I am missing something, but this seems really obvious to me: if you define it as the minimum that satisfies those conditions, how can there be more than one?

b. Find an O(|V| + |E|) algorithm that calculates this function for every vertex.

I think your topological sort idea is correct (note that a topological sort is a BFS), but it should be performed on the transposed graph (reverse the direction of every edge). Then the first values in the topological sort get 0, the next get 1 etc. For example, for the transposed graph:

1   2   3
*-->*-->*
        ^
*-------|
1

I have numbered the nodes with their positions in the topological sort. You number the nodes by implementing the topological sort using a BFS. When you extract a node from your FIFO queue, you subtract 1 from the indegree of all of its reachable nodes. When that indegree becomes 0 you insert the node it became 0 for in the queue and you number it as exracted_node + 1. In my example, the nodes numbered 1 start with indegree 0. Then, the bottom-most 1 subtract one from the indegree of the node labeled 3, but that indegree will be 1, not zero, so we don't insert it in the queue. We insert 2 however because its indegree will become 0.

Pseudocode:

G = G^t
Q = a FIFO queue
push all nodes with indegree 0 in Q
set l(v) = 0 for all nodes with indegree 0
indegree(v) = how many edges are going into node v
while not Q.Empty():
  x = Q.Pop()
  for all nodes v reachable from x:
    if indegree[v] > 0:
      indegree[v] = indegree[v] - 1
      if indegree[v] == 0:
        Q.Push(v)
        l[v] = l[x] + 1

You can also do it with a DFS that computes the value of each node once the recursion returns, as:

value(v) = 1 + max{value(c), c a child of v}

Note that the DFS is not dont on the transposed graph, because we'll let the recursion handle the traversal in topological sort order.

A function definition for directed acyclic graphs

2 Answers