Do you think IIT Guwahati certified course can help you in your career?
Introduction
A graph is a non-linear type of data structure. A graph is defined as a group of vertices, and edges are used to connect these vertices. There are many different types of graphs, such as directed, undirected, weighted, unweighted, cyclic, acyclic, etc. Some applications of graphs include maps, social media, path optimization algorithms, etc.
In this blog, we will discuss counting the total number of hamiltonian paths in a graph. Before diving into the solution, let’s discuss briefly the problem statement once again.
Problem Statement
We are given a directed graph of ‘N’ vertices with vertices labeled from 0 to ‘N - 1’ and 2-D vector ‘edges’ where an edge from ‘a’ to ‘b’ denotes there is a directed edge from a to b, i.e., it is in a single direction only. The main task is to count the total number of hamiltonian paths in the given directed graph where the starting vertex = 0 and the final visited vertex = N - 1.
Note: A hamiltonian path is one in which every vertex in the graph is visited exactly once.
Total number of Hamiltonian paths in the given graph = 2
Explanation
Our graph looks like this:
1st Hamiltonian path starting from 0th vertex and ending at the 4th vertex looks like this:
2nd Hamiltonian path starting from 0th vertex and ending at the 4th vertex looks like this:
Therefore, there are 2 hamiltonian paths for the given input.
Solution Approach
The idea is to use Bit Masking with Dynamic Programming. All of the subsets of the given vertices represented by an N-size mask will be iterated over, and count all the hamiltonian path that starts at the 0th vertex and finishes at (N - 1)th vertex.
Let S represents a bitmask with S = 0 to S = (1<< N) - 1 for a graph with N vertices, and dp[i][S] represents the number of paths that visit every vertex in the mask S and end at i then the valid recurrence will be:
dp[i][S] = Summation of all dp[j][S XOR 2i]
Where j belongs to the mask S and there is a directed edge starting from j and ending at i,
Where [S XOR 2i] represents the sub-mask of mask S that does not contain the ith vertex, and there must be a directed edge from j to i.
We will use the top-down or recursive dynamic programming approach to implement the recurrence mentioned above. Let’s take a look at the algorithm of the whole solution approach.
Algorithm
Create a reverse adjacency list ‘rev_adj’ where each node stores from how many other nodes we can reach the current node via a directed edge.
Declare a 2-D dp[N][2N] array with initial values of all the states as -1(which means that this value is not calculated yet). Here, dp[i][j] means the total number of ways such that the last index is ‘i’ and all the vertices in mask ‘j’ are visited.
Call the ‘calculate’ function with initial parameters being last index = N - 1 and initial mask = (1<< N) -1 which indicates all the vertices are visited.
Consider all the possibilities from which we can reach our ‘current’ node by iterating over the ‘prev’ nodes using a reverse adjacency list.
If the ‘prev’ node lies in the mask that means we can reach our current node from the previous node and we will add its contribution to the ‘total’.
Else, just skip this previous node and continue to the next node.
Return the ‘total’ which stores the total number of ways and is displayed as the output.
Dry Run
Initially, we have taken N = 5 so, the last index = 4 (i.e., N - 1) and with mask = ( 2N - 1) = 35 and we will look the all the vertices from the reverse adjacency list from where we can reach the index = 4 which are indexes 1 and 3. Now, similarly, we will go on and look at the two indexes at 1 and 3 and our mask here will change to a new value which is equal to (Mask xor (2 ^ 4)), and similarly, the recursion calls go on.
We used a 2-D dp array to store the results to prevent the solution from reaching an exponential complexity.
Implementation in C++
#include <iostream>
#include <vector>
using namespace std;
// Storing adjacency list
vector <vector <int>> rev_adj;
// Initialising dp array
vector <vector <int>>dp;
int calculate(int current, int mask){
// Base conditions
if(current==0){
if(mask==1){
return 1;
}
else{
return 0;
}
}
// If 0th vertex is absent
if(!(mask & 1)){
return 0;
}
// Already calculated value
if(dp[current][mask]!=-1){
return dp[current][mask];
}
int total=0;
for(auto prev:rev_adj[current]){
// Checking if this index is present in the mask
if(mask & (1<<prev)){
total += calculate(prev, mask ^ (1 << current));
}
}
return dp[current][mask]=total;
}
int main(){
// Total number of vertices in the graph
int N = 5;
// Directed edges of the graph
vector <vector <int>>edges;
edges.push_back({0,2});
edges.push_back({2,3});
edges.push_back({3,1});
edges.push_back({1,3});
edges.push_back({2,1});
edges.push_back({3,4});
edges.push_back({1,4});
rev_adj.assign(N,vector <int>(0));
dp.assign(N,vector <int>((1 << N)));
// Setting all values of dp to 0
for(int i=0;i<N;i++){
for(int j=0;j<(1 << N);j++){
dp[i][j]=-1;
}
}
// Creating reverse adjacency list
for(auto i:edges)
{
// Edge from -> to
int from=i[0];
int to=i[1];
rev_adj[to].push_back(from);
}
cout<<"Total Number of Hamiltonian paths in given graph = ";
/*
Calling the function for the last index N - 1
and visiting all indexes before that.
*/
cout<<calculate(N - 1, (1 << N) - 1);
}
You can also try this code with Online C++ Compiler
import java.util.ArrayList;
public class MyClass {
static int dp[][];
static ArrayList<ArrayList<Integer> > rev_adj;
static int calculate(int current, int mask){
// Base conditions
if(current==0){
if(mask==1){
return 1;
}
else{
return 0;
}
}
// If 0th vertex is absent
if((mask & 1)==0){
return 0;
}
// Already calculated value
if(dp[current][mask]!=-1){
return dp[current][mask];
}
int total=0;
for(int j = 0; j < rev_adj.get(current).size(); j++){
int prev = rev_adj.get(current).get(j);
// Checking if this index is present in the mask
if((mask & (1<<prev))>0){
total += calculate(prev, mask ^ (1 << current));
}
else{
continue;
}
}
return dp[current][mask]=total;
}
// Driver code
public static void main(String args[]) {
// Total number of vertices in the graph
int N = 5;
int limit= (1 << N);
rev_adj = new ArrayList<ArrayList<Integer> >(N);
dp= new int[N][limit];
// Setting all values of dp to 0
for(int i=0;i<N;i++){
for(int j=0;j<(1 << N);j++){
dp[i][j]=-1;
}
}
for (int i = 0; i < N; i++)
rev_adj.add(new ArrayList<Integer>());
//Directed edges of the graph
rev_adj.get(2).add(0);
rev_adj.get(3).add(2);
rev_adj.get(1).add(3);
rev_adj.get(3).add(1);
rev_adj.get(1).add(2);
rev_adj.get(4).add(3);
rev_adj.get(4).add(1);
/*
Calling the function for last index N - 1
and visited all indexes before that.
*/
System.out.print("Total Number of Hamiltonian paths in given graph = ");
System.out.print(calculate(N - 1, (1 << N) - 1));
}
}
You can also try this code with Online Java Compiler
Explanation: Total possible masks are 2N, which lies from 0 to 2N - 1, and in the worst case, the total number of possible vertices from which you can reach the current index can be N. So, considering both these factors simultaneously yields a time complexity of O(N * 2N).
Space Complexity
O(N * 2N)
Explanation: For storing the results, we declared a 2-D dp array of size (N * 2N) which gives us a total space complexity of O(N * 2N).
Frequently Asked Questions
What is dynamic programming, and where is it used?
Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results to be used later when needed quickly.
What do you mean by a directed graph?
A directed graph is a collection of connected objects (or vertices or nodes) in which all edges are directed in a single direction from one vertex to another.
What do you mean by a Hamiltonian path?
Each vertex is visited by a Hamiltonian path, with each vertex being precisely visited once (NOT every edge). If it comes to an end at the starting vertex, it is a Hamiltonian cycle.
What do you mean by an Euler path?
A path known as an Euler path is one that precisely traverses each edge only once. If the Euler path ends at the same vertex from which it has started, it is called an Euler cycle.
Write some applications of Dynamic Programming.
DP finds applications in optimization, combinatorial, graph algorithms, and string problems.
Conclusion
In this blog, we discussed a problem based on counting the total number of hamiltonian paths in a directed graph and used dynamic programming along with the bitmasks approach to solving the problem. We saw the algorithm for the approach and implemented the solution in two different languages, C++ and Java. This problem helps us learn more about some complex topics in Data Structures and algorithms.
84+ registered