Question

(b) A source in a directed graph is a node with no incoming edges. A sink is a node with no outgoing edges. Assume that we know that every DAG has at least one sink. Use this fact to explain why every DAG must have at least one source. (c) Consider the following graph algorithm which takes a DAG G as input. function COMPUTESOMETHING(DAG G) Lempty linked list S stack of all source nodes in G while S is non-empty do u+ POP(S) INSERTATTAIL (L,u) for each outgoing edge (u, v) do remove edge (u, v) from graph G if v has no other incoming edges then PUSH(S,v) return L Explain what the output of this algorithm is, and briefly explain why it works.

Answer 1

Answer for part b)

DAG are Directed Acyclic Graphs. Graph contains nodes and nodes are connected with eaach other through edges. These edges in DAG are directed, meaning they will have a directed arrow in the end of the edge showing the way in which we can go if we are at particular node.

Now as per the question we need to prove that if a DAG should contain atleast 1 sink then it should also have atleast one source.

Lets take an example of 2 Nodes creating a DAG as shown in the picture:

Source Sink

If we take this into consideration we can see that to make it a DAG the node from which the sink is receiving an incoming edge needs to be the source as the sink wont be able to produce any out going node back to that single node which I have labeled as source so it can be proved using this simple example that if there is a DAG and containing atleast one sink then it will definitely have atleast one source.

Answer for part c)

This algorithm which is written can be said to titled as "Listing all reachable nodes of DAG " . Lets take a simple example to understand the flow of link list L and Stack S using the following picture.

3 4 5 6 7

Candier this a DAG we will be taking for part c). I will be jotting down the List L and Stack S intermeditae and final results by showing the data they store at each step.

Initially Stack S contains all sources and hence we can say that

S -> 1                // SHowing S contains Node 1

L -> $                // $ sign will depict NULL

Step 1.

u = 1, S-> $   // Popping from the stack and saving in u

L -> 1            // Pushing u to the list

S -> 2,3        // removing the edges and pushing those with only No more incoming nodes in S

Step 2.

u = 2, S->3 // Poppd the value from S

L -> 1,2       // Pushing u to the list

S -> 3         // Removed only the edges going out from 2 and no node is pushed back

Step 3.

u = 3, S->$ // Popped the value from S

L -> 1,2,3       // Pushing u to the list

S -> 4,5      // Pushed 4 and 5 into the S

Step 4.

u = 4, S->5 // Popped the value from S

L -> 1,2,3,4       // Pushing u to the list

S -> 6,5      // Pushed 6 into the S

Step 5.

u = 6, S->5 // Popped the value from S

L -> 1,2,3,4,6       // Pushing u to the list

S -> 5      // Nothing pushed into S as Node 6 is sink.

Step 6.

u = 5, S->$ // Popped the value from S

L -> 1,2,3,4,6,5       // Pushing u to the list

S -> 7      // Pushed Node 7 into the S

Step 7.

u = 7, S -> $ // Popped the value from S

L -> 1,2,3,4,6,5,7       // Pushing u to the list

S -> $      // Nothing pushed into S as Node 7 is sink.

After this L is returned which contains all reachable nodes of given DAG by removing the multi-edges and moving in a hybrid BFS and DFS fashion.

It would have been easier to explain it verbally. I have tried my level best to explain it in the best way possible. Hope I gave your answer.Happy learning and feel free to raise any question if needed.