Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Solution Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is dynamic programming, and where is it used?
4.2.
What do you mean by a directed graph?
4.3.
What do you mean by a Hamiltonian path?
4.4.
What do you mean by an Euler path?
4.5.
Write some applications of Dynamic Programming.
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count all Hamiltonian Paths in a Directed Graph

Author Sahil Setia
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

Title image

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.

Input

N = 5 

Edges = [ [0, 2], [2, 3], [3, 1], [1, 3], [2, 1], [3, 4], [1, 4]]

Output

Total number of Hamiltonian paths in the given graph = 2

Explanation

Our graph looks like this:

Explanation image 1

1st Hamiltonian path starting from 0th vertex and ending at the 4th vertex looks like this:

Explanation image 2

2nd Hamiltonian path starting from 0th vertex and ending at the 4th vertex looks like this:

Explanation image 3

Therefore, there are 2 hamiltonian paths for the given input. 

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

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

  1. 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. 
     
  2. 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.
     
  3. 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.
     
  4. Consider all the possibilities from which we can reach our ‘current’ node by iterating over the ‘prev’ nodes using a reverse adjacency list.
     
  5. 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’.
     
  6. Else, just skip this previous node and continue to the next node.
     
  7. Return the ‘total’ which stores the total number of ways and is displayed as the output.

Dry Run

Dry run image

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


Output

Output image 1

Implementation in Java

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


Output

Output image 2

Time Complexity

O(N * 2N) 

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.

Recommended Reading:

Do check out The Interview guide for Product Based Companies, as well as some of the popular interview problems asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
Find Eventual Safe States
Next article
Bipartite Graph
Live masterclass