Data Structures and Algorithms: Digraph Processing

In the last post, we saw about what is a digraph? How to build one from scratch? Where can it be used? In case, if you need a small recap on digraphs or if you’re new to digraph, check out my previous post:

Data Structures: Directed Graphs

In this post I’m going to discuss a few of the many digraph processing algorithms:

1. Digraph Search: a) DFS and b) BFS
2. Topological sort
3. Strongly connected components

Digraph Search

I’m not going into much detail on digraph search as it very similar to undirected graph search, every undirected graph is a digraph (with edges in both directions) .

DFS

The idea is pretty simple,

1. we arbitrarily select a vertex in a graph and
2. then we visit it’s neighboring vertices.
3. Continue this process recursively until there are no neighboring nodes for a particular node,
4. while doing so, we maintain an array to check if the particular adjacent vertex is visited or not, this to avoid visiting the same node more than once.
5. Then we backtrack and check for other unmarked vertices and traverse them in the same way we did earlier.

And that’s a lot of words to be honest! 😅. Maybe the illustration given below will help you better in visualization of the algo,

digraph dfs

Algorithm

a) Create a recursive function called DFS that takes the index of vertex to be visited.

b) Mark the current as vertex as visited in the boolean indexed array.

c) Traverse all the adjacent nodes if they are not visited and call the recursive function with index of adjacent vertex.

API

Code

BFS

BFS is another classical graph processing algorithm, similar to DFS it is used for traversing or searching a tree or graph data structure. The objective of a BFS algorithm is similar to that of DFS, only the strategy of execution differs.

digraph bfs

Algorithm

a) Select a vertex from a graph as the source vertex s.

b) Put s onto a FIFO queue, and mark s as visited.

c) Repeat this until queue is empty:

(i) remove the least recently added vertex v

(ii) add each of v’s unvisited neighbors to the queue, and mark them as visited.

API

Code

Note on DAGs

A directed acyclic graph (DAG) is a graph that is directed and without cycles connecting the other edges. This means that it is impossible to traverse the entire graph starting at one edge. The edges of the directed graph only go one way. The graph is a topological sorting, where each node is in a certain order.

Topological Sort

Let’s take a look at a task, given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks?

That’s where, the topological sort algorithm comes into the play where it takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to.

Algorithm

a) Identify a node with no incoming edges.

b) Add that node to the ordering.

c) Remove it from the graph.

d) Repeat.

API

Code

The depiction of the above code

Strongly Connected Components

Vertices v and w are strongly connected if there is both a directed path from v to w and a directed path from w to v.

Strong connectivity is an equivalence relation:

a) v is strongly connected to v.

b) If v is strongly connected to w, then w is strongly connected to v.

c) If v is strongly connected to w and w to x, then v is strongly connected to vertices.

Algorithm

1. Create an stack ‘st’ and do the DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in stack as 1, 2, 4, 3, 0.
2. Reverse directions of all arcs to obtain the transpose graph.
3. One by one pop vertex from ‘st’ while ‘st’ is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS. The DFS starting from v prints strongly connected component of v. In the above example, we process vertices in order 0, 3, 4, 2, 1.

API

Code

Depiction of the above code

So, we have come to the end of this post and thank you so much 😊 if you have made this far into this post. I will see you in the next post with introduction weighted graph!! Always grateful, never complacent!

References

1. Algorithms book by Robert Sedgewick
2. https://www.techopedia.com/definition/5739/directed-acyclic-graph-dag
3. https://www.interviewcake.com/concept/java/topological-sort
4. https://www.geeksforgeeks.org/topological-sorting/
5. https://www.geeksforgeeks.org/strongly-connected-components/

My Github Repository

1. https://github.com/Sethuram52001/DSA