How to return a 2D array of all possible paths between 2 nodes in a graph? (C++)

Question

I have the following code taken which was taken from online, for me to use as a reference. In int main() {}, it first adds edges to the graph, then using calls the function which uses recursion to output all possible paths.

// C++ program to print all paths from a source to destination. 
#include<iostream> 
#include <list> 
using namespace std; 

// A directed graph using adjacency list representation 
class Graph 
{ 
    int V; // No. of vertices in graph 
    list<int> *adj; // Pointer to an array containing adjacency lists 

    // A recursive function used by printAllPaths() 
    void printAllPathsUtil(int , int , bool [], int [], int &); 

public: 
    Graph(int V); // Constructor 
    void addEdge(int u, int v); 
    void printAllPaths(int s, int d); 
}; 

Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 

void Graph::addEdge(int u, int v) 
{ 
    adj[u].push_back(v); // Add v to u’s list. 
} 

// Prints all paths from 's' to 'd' 
void Graph::printAllPaths(int s, int d) 
{ 
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]; 

    // Create an array to store paths 
    int *path = new int[V]; 
    int path_index = 0; // Initialize path[] as empty 

    // Initialize all vertices as not visited 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 

    // Call the recursive helper function to print all paths 
    printAllPathsUtil(s, d, visited, path, path_index); 
} 

// A recursive function to print all paths from 'u' to 'd'. 
// visited[] keeps track of vertices in current path. 
// path[] stores actual vertices and path_index is current 
// index in path[] 
void Graph::printAllPathsUtil(int u, int d, bool visited[], 
                            int path[], int &path_index) 
{ 
    // Mark the current node and store it in path[] 
    visited[u] = true; 
    path[path_index] = u; 
    path_index++; 

    // If current vertex is same as destination, then print 
    // current path[] 
    if (u == d) 
    { 
        for (int i = 0; i<path_index; i++) 
            cout << path[i] << " "; 
        cout << endl; 

    } 
    else // If current vertex is not destination 
    { 
        // Recur for all the vertices adjacent to current vertex 
        list<int>::iterator i; 
        for (i = adj[u].begin(); i != adj[u].end(); ++i) 
            if (!visited[*i]) 
                printAllPathsUtil(*i, d, visited, path, path_index); 
    } 

    // Remove current vertex from path[] and mark it as unvisited 
    path_index--; 
    visited[u] = false; 
} 

// Driver program 
int main() 
{ 
    // Create a graph given in the above diagram 
    Graph g(4); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(0, 3); 
    g.addEdge(2, 0); 
    g.addEdge(2, 1); 
    g.addEdge(1, 3); 

    int s = 2, d = 3; 
    cout << "Following are all different paths from " << s 
        << " to " << d << endl; 
    g.printAllPaths(s, d); 

    return 0; 
} 

How can I modify this code such that I can make the function return list<list<int> > instead of printing the paths? This is so I can use this list for further processing?

Thank you!

Answer 1

One way is to pass a list by reference to the util function. And whenever you reach the end, just make a list with the path and push it inside the result list.

The code should look something like this:

// C++ program to print all paths from a source to destination. 
#include<iostream> 
#include <list> 
using namespace std;

// A directed graph using adjacency list representation 
class Graph
{
    int V; // No. of vertices in graph 
    list<int>* adj; // Pointer to an array containing adjacency lists 

    // A recursive function used by printAllPaths() 
    void printAllPathsUtil(int, int, bool[], int[], int&, list<list<int>>&);

public:
    Graph(int V); // Constructor 
    void addEdge(int u, int v);
    list<list<int>> printAllPaths(int s, int d);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v); // Add v to u’s list. 
}

// Prints all paths from 's' to 'd' 
list<list<int>> Graph::printAllPaths(int s, int d)
{
    // Mark all the vertices as not visited 
    bool* visited = new bool[V];

    // Create an array to store paths 
    int* path = new int[V];
    int path_index = 0; // Initialize path[] as empty 

    // Initialize all vertices as not visited 
    for (int i = 0; i < V; i++)
        visited[i] = false;

    list<list<int>> result;

    // Call the recursive helper function to print all paths 
    printAllPathsUtil(s, d, visited, path, path_index, result);

    return result;
}

// A recursive function to print all paths from 'u' to 'd'. 
// visited[] keeps track of vertices in current path. 
// path[] stores actual vertices and path_index is current 
// index in path[] 
void Graph::printAllPathsUtil(int u, int d, bool visited[],
    int path[], int& path_index, list<list<int>>& result)
{
    // Mark the current node and store it in path[] 
    visited[u] = true;
    path[path_index] = u;
    path_index++;

    // If current vertex is same as destination, then print 
    // current path[] 
    if (u == d)
    {
        list<int> tempList;
        for (int i = 0; i < path_index; i++)
            tempList.push_back(path[i]);
        result.push_back(tempList);
    }
    else // If current vertex is not destination 
    {
        // Recur for all the vertices adjacent to current vertex 
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                printAllPathsUtil(*i, d, visited, path, path_index, result);
    }

    // Remove current vertex from path[] and mark it as unvisited 
    path_index--;
    visited[u] = false;
}

// Driver program 
int main()
{
    // Create a graph given in the above diagram 
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(1, 3);

    int s = 2, d = 3;
    cout << "Following are all different paths from " << s
        << " to " << d << endl;

    list<list<int>> result = g.printAllPaths(s, d);

    for (auto path : result)
    {
        for (auto node : path)
            std::cout << node << ' ';
        std::cout << std::endl;
    }

    return 0;
}

Output:

Following are all different paths from 2 to 3
2 0 1 3
2 0 3
2 1 3

I won't recommend using a list tho. I think using an std::vector will be better in terms of speed and memory. But since you asked for a list, this code returns a list. Alos I have to say that I didn't read the code, I just changed what needs to be changed to return a list.

Here is another code that does the same thing but using std::vector instead.

#include <iostream>
#include <vector>

class Graph
{
    std::vector<std::vector<int>> graph;
    std::vector<std::vector<int>> paths;
    std::vector<bool> visited;

    void DFS(int currentNode, int destNode, std::vector<int>& currentPath)
    {
        visited[currentNode] = true;
        currentPath.push_back(currentNode);

        if (currentNode == destNode)
            paths.push_back(currentPath);
        else
        {
            for (auto node : graph[currentNode])
                if (!visited[node])
                    DFS(node, destNode, currentPath);
        }

        currentPath.pop_back();
        visited[currentNode] = false;
    }

public:

    Graph(int size)
    {
        graph.resize(size);
        visited.resize(size);
    }

    void addEdge(int from, int to)
    {
        graph[from].push_back(to);
    }

    std::vector<std::vector<int>> GetAllPossiblePaths(int source, int dest)
    {
        paths.clear();
        std::fill(visited.begin(), visited.end(), false);

        std::vector<int> temp;

        DFS(source, dest, temp);

        return paths;
    }
};

int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(1, 3);

    auto result = g.GetAllPossiblePaths(2, 3);

    for (auto& path : result)
    {
        for (auto node : path)
            std::cout << node << ' ';
        std::cout << std::endl;
    }
}