Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Explanation
4.1.
Step 1️: Find the Topological Sorting
4.2.
Step 2: Assign the directions to undirected edges
5.
Algorithm
6.
C++ Code
7.
Complexities
7.1.
Time complexity
7.2.
Space complexity
8.
Frequently Asked Questions
8.1.
What is a directed acyclic graph?
8.2.
How do you determine whether a directed graph is acyclic?
8.3.
How many edges are there in a directed acyclic graph?
8.4.
Can a DAG have zero edges?
8.5.
Why is topological sort helpful?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Assign Directions to Edges so that the Directed Graph remains Acyclic

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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.

Introduction

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)?

Problem Statement

Let’s discuss this with an example.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Example

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:

Topological Sorting

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:

assign directions to undirected edges

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:

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;
}

 

The updated adjacent list after providing directions is shown below:

updated adjacent list

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 algorithmwhere 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:

👉 Introduction to Graphs

👉 Graph Theory

👉 Graph Representation

👉 Properties of Graph
 

Recommended Problems - 


You can refer to our guided paths on the Coding Ninjas Studio platform to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. To practice and improve yourself in the interview, you can also check out Top 100 SQL problemsInterview experienceCoding interview questions, and the Ultimate guide path for interviews. Do upvote our blog to help other ninjas grow.

Happy Coding !!

Live masterclass