Directed Acyclic Graph (DAG)

A Directed Acyclic Graph (DAG) is a graph where each edge is directed and there is no path cycle. The above graph is a directed acyclic graph. Note that each edge has an arrowhead which shows its direction. There are five vertexes numbered: 0, 1, 2, 3, and 4. Acyclic means there is no path cycle. That is, one cannot go from one vertex, following a directed edge, and then, after visiting zero or more vertexes, arrive back at that same vertex.

In-Degree

The in-degree of a vertex is the number of edges directed to (or arriving at) that vertex. Leaving a vertex is out-degree. Out-degree is not addressed in this document. In the above graph, the in-degree of vertex 0 is zero. The in-degree of vertex 1 is 2. The reader should be verifying these as the description continuous. The in-degree of vertex 2 is 2. The in-degree of vertex 3 is 1 (and the out degree is 3). The in-degree to vertex 4 is 1

Breadth-First-Search (BFS) Algorithm

The name Breadth-First Search Algorithm is not a very good name for the Breadth-First Search algorithm itself. This bad name falsely gives the impression that for a grid graph, where the intersections of the edges are the vertexes, the algorithm visits the vertexes from the top-left vertex, moving rightwards to the end of the first line, then go to the next line below and visits from the left end to the right end, then go to the third line below and visits from the left to the right, then go to the fourth line below, visits from left to right; and so on (downwards).

In the author's opinion, the best way to describe Breadth-First-Search algorithm is as follows: Consider a graph, where the start vertex is at the center of the graph. The algorithm visits the start vertex first. Then the algorithm visits all the neighbors of the center-start vertex, one-by-one. That should be considered as the first level of vertexes, which is not any first line at the top of the graph. Next, the algorithm visits all the neighbors of the first neighbors, of the center-start vertex. That should be considered as the second level of vertexes, going outwards. Next, the algorithm visits all the neighbors of the second neighbors, of the center-start vertex, going outwards. That should be considered as the third level of vertexes. These visits continue outwards.

Of course, in a practical graph, as the algorithm visits vertexes outwards, some vertexes will not be present in some assumed radial lines, and there would be even some new vertexes which do not fit into any assumed radial line, from the center.

Breadth-First Search Algorithm is used in Kahn's algorithm (see program below).

The graph used for the program below is the one given above, which is presented here, again, for easy reading access:

The vertexes here represent software programming tasks (and not physical quantities). If vertex 0 is considered as a central vertex, then vertexes 1 and 3 are the immediate neighbors of the center vertex. Vertex 1 and 3 form level 1 vertexes. Vertexes 2 and 4 are the neighbors of the first level vertexes, going outwards. In practice, the center vertex is not usually at the very center of the graph. In this graph, to be used for the program below (Kahn's algorithm), there is no real vertex at the center. So vertex 0 has to be considered as the center-start vertex.

Task Dependencies

In programming, more than one tasks would be waiting to use the microprocessor. There are different types of task dependencies. However, concerning this interview question, one task has to finish using the microprocessor, before the other tasks have access to the microprocessor, one-by-one. The above directed acyclic graph shows the order in which the tasks need to have access to the microprocessor, as follows:

The first task to have access to the microprocessor is task 0 (vertex 0). Task 0 does not have to wait for any other task to complete before it uses the microprocessor. In other words, task 0 (i.e. vertex 0) has no dependencies. A dependency is a task that has to operate (use the microprocessor) before the current one operates (executes). Dependencies are synonymous to "prerequisites", so far as Kahn’s algorithm is concerned.

A directed arrow, connects a dependency task (vertex) to a current task (another vertex) in a graph. Task 1 (vertex 1) in the graph, has to wait for task 0 and task 3 to finish, before it can operate (use the microprocessor). So far as task 1 is concerned, it does not matter if task 0 or task 3 operates first. That is, the order in which task 0 and task 3 operated before, does not matter to task 1. Note that the naming of the tasks (with integers) does not follow the order of operations (executions).

Task 2 (vertex 2) has two dependencies (for two separate in-degrees). The dependencies are tasks 1 and task 3. Task 2 in the graph, has to wait for task 1 and task 3 to finish, before it can operate (use the microprocessor). So far as task 2 is concerned, it does not matter if task 1 or task 3 operates first. That is, the order in which task 1 and task 3 operated before, does not matter to task 2.

Task 3 (vertex 3) has only one dependency (for one in-degree). The dependency is tasks 0. Task 3 is a dependency for task 1, and it is also a dependency for task 2 and task 4. It has an out-degree of 3: one directed arrow to each of the three tasks after. Task 3 in the graph, has to wait for task 0 to finish, before it can operate (use the microprocessor).

Task 4 (vertex 4) also has only one dependency (for one in-degree). The dependency is tasks 3. Task 4 has 0 out-degree. Task 4 in the graph, has to wait for task 3 to finish, before it can operate (use the microprocessor).

Topological Sort

Topological sort, also known as topological ordering, is the ordering of tasks according to how they will wait and operate (use the microprocessor). There can be more than one topological sort, for the same graph, because one task (vertex) can have an in-degree of more than one. Possible topological sorts for the above graph are:

    0 - 3 - 1 - 2 - 4

    0 - 3 - 2 - 1 - 4

    0 - 3 - 4 - 1 – 2

    0 - 3 - 1 - 4 - 2

Each number identifies a task. The order of operation (execution), begins from the left of each series.

So topological sorting converts a directed-acyclic-graph into a linear (line) order.

Illustration

In this document, a manual-run-through of Kahn's algorithm is made before a summary of steps is presented. The above graph of tasks will be used . For easy reader access view, the graph is re-displayed as follows:

This is a Directed Acyclic Graph (DAG). It indicates the order in which tasks have to operate (use the microprocessor). Each task is represented by a vertex. With the exception of task 0, in order for any other task to operate, one or more other tasks (dependencies) must have operated.

At the start, a task with 0 in-degree has to be identified. It is task 0 in this case. If the graph is truly a directed-acyclic-graph, then a central task (vertex) with 0 in-degree will exist. In theory this task with 0 in-degree has to be at the center of the graph. However, in practice, it can be anywhere in the graph. In this case it is task 0.

Note: any vertex connected to another vertex, contributes an in-degree of only 1, to that vertex.

There is need for an array (called in_degree), to have all the vertexes in the graph, with their in-degrees. This array is produced in the main calling function in the program below. An index of the array identifies a particular vertex (task) in the graph. The value of the indexed element is the in-degree of the vertex. Remember, the in-degree is the number of in-coming edges to a vertex, in the graph.

From the array, the vertexes (tasks) are sent to a queue object (First-In-First-Out), in accordance with Kahn's algorithm. As the tasks are sent to the queue, they are being dequeued from the first end of the queue, to the microprocessor, for operation (execution). For the purpose of this document, the algorithm does not say what happens in the microprocessor. And so there will be de-queuing without any further important action below, in this document. Breadth-First-Search Algorithm engagement is present at this stage.

Manual Run Through

In the main calling function, the array of in-degrees for each task (vertex), of the above graph, is determined as:

There can be more than one task with in-degree of 0. There will always be at least one task (vertex) with in-degree of 0, if the graph is truly a directed-acyclic-graph.

After the main function call, all the vertexes with in-degree of zero are removed from the graph and sent to the queue, one-by-one. Since they are no longer in the graph, the one out-going edge each contributed to each neighboring vertex, is also removed.

For the above graph, only task 0 (vertex 0) is removed at this point. The in-degree it contributed to vertex 1 is reduced by 1, and the in-degree it contributed to vertex 3 is also reduced by 1. The resulting graph is:

And the in-degree array becomes:

Note from the new graph form and the new array data, that the in-degrees of the neighbors (to vertex 0) have each been reduced by 1. Vertex 1 now has an in-degree of 1 and vertex 3 now has an in-degree of 0. The queue content at this point consists of just vertex 0.

Vertex (task) 3 is the next vertex to be removed and sent to the queue. When the in-degree of any vertex becomes 0, the vertex has to be removed and sent to the queue.

Task (vertex) 3 is removed from the graph and sent to the queue, at the back. Before that, task (vertex) 0 is removed from the queue at the front. Sending something to the back of the queue is en-queuing and removing something at the front of the queue is de-queuing. Actually task 0 is removed from the queue and sent to the microprocessor for operation (that operation is not addressed in this document). Do not confuse between removing something from the graph and removing another thing from the queue.

After task (vertex) 3 has been removed and sent to the back of the queue, the out-going edges it contributed to its neighboring vertexes have to be removed as well. Remember, a task cannot contribute more than one out-going vertex to any of its neighboring tasks (vertexes).

Vertex 3 had three out-going edges: one to vertex 1, one to vertex 2 and one to vertex 4; it had no in-coming edge, at its last state.

So the in-degree (number of in-coming edges) to each of task 3's neighbors, is reduced by one (by the algorithm). And so, the resulting graph and array are:

and the new array state is:

Note from the diagram that task 1 (vertex 1) and task 4 (vertex 4) no longer have any in-coming edge. That is, either now has 0 in-degree. Whenever a task has 0 in-degree, it has to be removed from the graph and sent to the back of the queue. Before that, the current first task in the queue has to be removed (and sent to the microprocessor).

Removing a vertex from the graph, means identifying it's index in the graph table and reducing each in-degree for each of its forward neighbors by 1. There should be no backward neighbor at this state.

Task 3 which was at the front of the queue is removed from the queue and sent to the microprocessor (what happens in the microprocessor is not addressed in this tutorial).

Since the order of the resulting topological sort does not matter, as long as the tasks that were supposed to be executed before the current task, have finish executing, either task 1 or task 4 can be removed from the graph and sent to the back of the queue. For this tutorial, task 1 is removed.

The resulting graph and array are:

and the new array state is:

The in-degree of task 2 is now 0 as task 1 and its out-going edge were removed. Task 1 was sent to the back of the queue.

The in-degree of task 2 is now 0 and the in-degree of task 4 is also 0. Either task (vertex) can be removed and sent to the back of the queue. For this tutorial, task 2 is removed. The in-degree of task 4 still remains at 0.

Before that, task 1 is removed from the queue (and sent to the microprocessor).

The resulting graph and array are:

and the new array state is:

Any task with 0 in-degree has to be removed from graph and sent to the back of the queue. There is only one task with 0 in-degree left, so this last task is removed from the graph and sent to the back of the queue. Before that, task 2 is removed from the front of the queue and sent to the microprocessor. The array state indicates the in-degree of the current vertex, which is 0 and the previous in-degrees of the other vertexes, some of which are 0.

Task 4 is removed from the graph and sent to the back of the queue. Before that, task 2 is removed from the front of the queue (then sent to the microprocessor).

The queue will have to be emptied. So ultimately, task 4 will be removed from the front of the queue (and sent to the microprocessor). The algorithm ends !

Now, in the above manual-run-through, all the vertexes are removed from the graph before the queue becomes empty. If the queue is empty while there is one or more vertexes still in the graph, then this means that the graph had one or more cycles, and so all the work done has to be abandoned. Preventive code to this effect, has to be made in the program.

For the preventive code, there is need for a counter, to be counting the number of vertexes that leave the queue, in order to compare its final value with the number of vertexes that were in the graph, at the beginning.

Summary of Kahn's Algorithm

Kahn's algorithm only works with Directed Acyclic Graph.

- All the vertexes with zero in-degree are removed from the graph and sent to a queue. Any single edge to a neighboring vertex in the graph, which was from a vertex with zero in-degree, is considered removed from the graph. In the algorithm, whenever an edge to a vertex is considered as removed from the graph, that vertex may end up with an in-degree of 0. In fact, at each stage in the algorithm, there is always at least one vertex with a resulting in-degree of 0.

- While the queue is not empty, the vertex at the front of the queue is removed and sent to the microprocessor. Then a vertex with 0 in-degree in the graph, is removed from the graph and sent to the back of the queue. Any out-going edge from the vertex removed from the graph, is considered removed as well.

- The above step repeats until there is no vertex in the queue.

The Kahn's Algorithm Program

Queue in Language C

C neither has an in-built queue object nor a queue object from its default library. So the queue object for the program, has to be mimicked, using an array, as follows:

An array, called queue, with a length (size) of the maximum number of elements that the array can ever have is created. Two independent integer variables, front and back are created to be associated with the queue array. Elements are inserted into the queue array, beginning from index zero, going backwards with no index skipped.

Assume that there are already elements in the array: The back variable is always adjusted to point to the last inserted element in the array. This does not necessarily correspond to the very last location of the array. Assume that there are 3 inserted elements already in the array: When a new element is said to be put at the back of the queue (enqueue), that element will be inserted in the location for index 3 (= 4-1). The back variable had the value 2. Now it would have the value 3 (remember, array indexing is zero based).

The front variable is always adjusted to point to the next element to be removed (dequeued) from the front of the queue. At the start of the algorithm, the front variable has the value 0. When the first element is copied out, which is interpreted as removed from the front of the queue (dequeued), the front variable will be adjusted to have the value 1. When the next element is copied out, the front variable is adjusted to have the value 2. Actually, no element is removed from the array.

In the program below, the array, topologicalOrder has the topological sort order. The content of this array (topologicalOrder) is printed, in order, by the program.

Input

The input that represents the above graph, is an adjacency matrix, which is

    v     0     1     2     3     4
u
0         1           1

1               1

2    

3        1      2           4

4

The rows are identified by u and the columns are identified by v. This means that the previous vertex in the graph is u and the current vertex is v.

In the following program, the in-degrees are produced in the main calling function:

The complete program is (read the code and comments):

#include 
#include 

#define MAX_TASKS 10

// Graph structure
int adj[MAX_TASKS][MAX_TASKS];
int in_degree[MAX_TASKS];
int num_tasks;

// Queue structure for Breadth First Search
int queue[MAX_TASKS];
int front = -1, back = -1;

void enqueue(int v) {
    if (back == MAX_TASKS - 1) return;
    if (front == -1) front = 0;
    queue[++back] = v;    //it is "++back" and not "back++"
}

int dequeue() {
    if (front == -1 || front > back) return -1;
    return queue[front++];
}

void topologicalSort() {
    int topologicalOrder[MAX_TASKS];    //to display topological sort (order)
    int count = 0;

    // Push back vertexes with zero dependencies (0 in-degree) to queue, at start
    for (int i = 0; i < num_tasks; i++) {
        if (in_degree[i] == 0) {
            enqueue(i);
        }
    }

    // Process the queue
    while (front != -1 && front <= back) {    //queue is not empty
        int u = dequeue();    //to microprocessor
        topologicalOrder[count++] = u;    //to display topological order and count dequeuing 

        // Remove dependency (decrement in-degree) for forward children (v's),
        // then push to back of queue if in-degree is 0 
        for (int v = 0; v < num_tasks; v++) {
            if (adj[u][v] == 1) {
                if (--in_degree[v] == 0) {    //reduce in-degree by 1
                    enqueue(v);    //push to back of queue
                }
            }
        }
    }

    // Check for cycles
    if (count != num_tasks) {
        printf("Error: Circular dependency detected. No solution.\n");
    } else {
        printf("Schedule: ");
        for (int i = 0; i < count; i++) {
            printf("%d ", topologicalOrder[i]);
        }
        printf("\n");
    }
}

int main() {
    num_tasks = 5;
    
    // Initialize graph (to all zeros)
    for(int i=0; i v: u must complete before v)
    adj[0][1] = 1; in_degree[1]++;
    adj[0][3] = 1; in_degree[3]++;
    adj[1][2] = 1; in_degree[2]++;
    adj[3][1] = 1; in_degree[1]++;
    adj[3][2] = 1; in_degree[2]++;
    adj[3][4] = 1; in_degree[4]++;
    //Representation of dependencies: 1 depends on 0 and 3; 3 depends on 0; 2 depends on 1 and 3;
    //4 depends on 3

    topologicalSort();
    
    return 0;
}

The output is:

    Schedule: 0 3 1 4 2 

Thanks for reading.