Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello Ninjas,
In this blog, we will determine how to assign directions to edges so that the directed graph remains acyclic with the help of an example. We will discuss the algorithm to solve this problem and look at the implementation for the same.
So let's go straight into this idea without further ado! Let’s first understand the problem statement.
Problem Statement
Given an acyclic graph containing both directed and undirected edges, assign the undirected edges a direction such that the graph remains acyclic. How can undirected edges be given directions while maintaining the graph's acyclic structure (with all directed edges)?
Let’s discuss this with an example.
Example
We are given the following directed acyclic graph. The blue dotted edges in the graph below don't have directions. We have to assign them directions such that the resulting graph is acyclic.
Explanation
The strategy is to make use of topological sorting. We need to assign edges in such a way that the one which comes before in the topological sort sequence will be the starting node for the directed edge.
Let’s divide this algorithm into two parts and solve it.
Step 1️: Find the Topological Sorting
The first step is to find the topological sorting of the graph by focusing on the directed edge subgraph. Following is the sequence:
Step 2: Assign the directions to undirected edges
Assign the direction to an undirected edge in such a way that If v comes after u in topological sorting, assign direction from u to v for each undirected edge (u, v); otherwise, assign direction from v to u.
Refer to this figure:
You must be wondering how this works. Let’s discuss this.
🔶 There is no path from a node that comes after another in a topological sort to a node that comes before it.
🔶 The node currently has all of its existing paths leading from itself to some of the nodes ahead of it; therefore, if we need a cyclic graph, we need a way to connect the node with itself.
🔶 And if it must become cyclic, it must connect a node in front of it to a node in the back, which violates the basic principle of the topological sort.
🔶 The graph won't become cyclic if we continue to connect all nodes to nodes ahead of them in the chain.
The following will be the resultant graph:
Let’s have a clear look at the steps.
Algorithm
Our approach to this solution is to find the topological sorting sequence. This will help us to find which nodes are ahead of a particular node, through which we can assign the direction to the undirected edges. Let’s look at the steps:
🎯 Start by taking a stack to find topological sort and a visited map to check which nodes we have already traversed.
🎯 Now, visit the nodes with the help of DFS Algorithm and push the node into the stack before backtracking.
🎯 The stack will give the sequence of topological sorting, empty elements from the stack, and store them into another data structure, say vector.
🎯 Now, one by one, take undirected edges; for an edge (u,v), If v comes after u in topological sorting, assign direction from u to v; otherwise, assign direction from v to u.
Now, let’s look at the C++ Code for the above-discussed example.
C++ Code
#include<bits/stdc++.h>
using namespace std;
// Function to find topological sort
void topoSort(unordered_map<int, vector<int>> &adj, int node , stack<int> &st , unordered_map<int,bool> &visited){
visited[node] = 1;
for(auto nbr:adj[node]){
if(!visited[nbr]){
topoSort(adj, nbr, st, visited);
}
}
st.push(node);
}
// Function to assign directions
void assignDirections(unordered_map<int, vector<int>> &adj, vector<pair<int, int>> &undir, vector<int> &result){
unordered_map<int, int> indexes;
int j = 0 ;
for(auto i:result){
indexes[i] = j ;
j++;
}
for(auto p:undir){
int firstNode = p.first;
int secondNode = p.second;
if(indexes[firstNode] < indexes[secondNode]){
adj[firstNode].push_back(secondNode);
}
else{
adj[secondNode].push_back(firstNode);
}
}
}
int main(){
// create a graph
unordered_map<int, vector<int>> adj;
adj[0] = {1};
adj[1] = {4};
adj[2] = {0,3};
adj[3] = {4};
// undirected edges
vector<pair<int, int>> undir;
undir = {{1,2}, {0,3}, {2,4}};
// use stack for topological sort and visited map
stack<int> st;
unordered_map<int, bool> visited;
// check for all nodes
for(int i=0;i<=4;i++){
if(!visited[i]){
topoSort(adj, i, st, visited);
}
}
// store topological sort
vector<int> result;
while(!st.empty()){
result.push_back(st.top());
st.pop();
}
// assign directions to undirected edges
assignDirections(adj, undir, result);
// print graph
for(auto i:adj){
cout<<i.first<<" : ";
for(auto j:i.second){
cout<<j<<" ";
}
cout<<endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
The updated adjacent list after providing directions is shown below:
Complexities
Time complexity
O(V + E) is the time complexity of this algorithm, where V denotes the count of the vertices and E refers to the number of edges in the graph as a result of the topological sorting.
Space complexity
O(V) is the space complexity of this algorithm, where V denotes the count of the vertices in the graph due to the initialization of a set of nodes.
Frequently Asked Questions
What is a directed acyclic graph?
A conceptual illustration of a sequence of actions is a directed acyclic graph (DAG). A graph is used to show the order of the activities visually. It consists of a collection of circles, each representing a different activity.
How do you determine whether a directed graph is acyclic?
Start a DFS on that node. As you go down each edge, ensure it doesn't lead back to a node already in your stack. This suggests that a cycle does indeed exist. The connected component has no cycles if you cannot locate such an edge.
How many edges are there in a directed acyclic graph?
If the number were more significant than n-1, one node would be in both the in-degree and out-degree, indicating a cycle. As a result, each node can have n-1 edges next to it; as a result, the maximum number of edges is n(n-1)/2.
Can a DAG have zero edges?
A set of vertices and directed edges is called a directed graph. A directed graph can exist with an empty set of edges since a set can be empty.
Why is topological sort helpful?
It has an O(V + E) linear time complexity with proper programming. Another reason why this topological sort is better is that it can find cycles in a directed graph.
Conclusion
In the article, we have discussed an important question: Assign Directions to Edges so that the Directed Graph remains Acyclic with the help of an example. We hope that this article will help you understand the concept of a graph, and if you want to learn more about the graph, check out our other blogs on graphs:
24+ registered 
