DFS for Graph search with generic data types

Question

This question is a follow up to this. I am learning Graph data structure and have implemented DFS and BFS in a way that it can handle data types other than int. These function try to search an end or goal node from a start node.

1. How can I design DFS better? As of now, I need to reset visited nodes and flag every time the search happens.
2. Any suggestions for improvement of BFS and other parts of code?
3. Any logical errors?

The complete commented code is given below:

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>

// The Helper function to print and check Adjacency List of the graph
template<typename T>
void print_list(const std::list<T>& l)
{
    //typename std::list<T>::const_iterator it;
    for(auto it = l.cbegin(); it != l.cend(); it++)
    {
        std::cout << *it << "\t";
    }
    std::cout << std::endl;
}

// The class for Graph
template<typename T>
class Graph
{
    //Undirected Graph
    std::map<T, std::list<T>> adj_list;
public:
    Graph(const std::vector<std::pair<T, T>>&);
    void add_edge(std::pair<T, T>);
    size_t size();
    void print_adj_list();
    void bfs(T, T);
    void dfs(T, T, std::set<T>&, int&);
};

// The graph constructor. Takes in a vector of edges and builds graph.
template<typename T>
Graph<T>::Graph(const std::vector<std::pair<T, T>>& edges)
{
    for(size_t i = 0; i < edges.size(); i++)
    {
        this -> add_edge(edges[i]);
    }
}

// Undirected Graph
// Add additional edges specified by pair
template<typename T>
void Graph<T>::add_edge(std::pair<T, T> edge)
{
        adj_list[edge.first].push_back(edge.second);
        adj_list[edge.second].push_back(edge.first);
}

// Returns no. of vertices / nodes in the graph
template<typename T>
size_t Graph<T>::size()
{
    std::cout << "Size of Graph(no. of vertices): " << std::endl;
    return adj_list.size();
}

// Function to print Adjacency List with the help of print_list function.
template<typename T>
void Graph<T>::print_adj_list()
{
    std::cout << "The Adjacency List: " << std::endl;
    //typename std::map<T, std::list<T>>::const_iterator it;
    for(auto it = adj_list.cbegin(); it != adj_list.cend(); it++)
    {
        std::cout << it -> first << "\t";
        print_list(it -> second);
    }

}

// DFS using queue. The search starts from 'start' node and ends when 'end' node is found or
// the entire graph is traversed. The set `visited` and `flag` needs to be reset before search.
template<typename T>
void Graph<T>::dfs(T start, T end, std::set<T>& visited, int& flag)
{
    visited.insert(start);
    std::cout << start << "\t";

    if(start == end)
    {
        flag = 1;
        std::cout << "Found" << std::endl;
        return;
    }

    if(visited.size() == adj_list.size())
    {
        std::cout << "Not found" << std::endl;
        return;
    }

    for(auto it = adj_list[start].cbegin(); it != adj_list[start].cend(); it++)
    {
        if(flag)
        {
            return;
        }
        if(visited.find(*it) == visited.end())
        {
            dfs((*it), end, visited, flag);
        }
    }
}

// BFS using queue. The search starts from 'start' node and ends when 'end' node is found or
// the entire graph is traversed.
template<typename T>
void Graph<T>::bfs(T start, T end)
{
    std::set<T> visited;
    std::queue<T> q;
    q.push(start);
    visited.insert(start);
    while(!q.empty())
    {
        T node = q.front();
        q.pop();
        std::cout << node << "\t";
        if(node == end)
        {
            std::cout << "Found" << std::endl;
            return;
        }
        for(auto it = adj_list[node].cbegin(); it != adj_list[node].cend(); it++)
        {
            if(visited.find(*it) == visited.end())
            {
                q.push(*it);
                visited.insert(*it);
            }
        }
    }
    std::cout << "Not Found" <<std::endl;
}

//Main
int main()
{
    // Uncomment the block below to test with int
    /*std::vector<std::pair<int, int>> v;
    v.push_back({1, 2});
    v.push_back({2, 8});
    v.push_back({2, 5});
    v.push_back({2, 4});
    v.push_back({3, 4});
    v.push_back({5, 9});
    v.push_back({5, 7});
    v.push_back({5, 6});
    Graph<int> g{v};*/

    // Uncomment the block below to test with char
    std::vector<std::pair<char, char>> v;
    v.push_back({'a', 'b'});
    v.push_back({'b', 'h'});
    v.push_back({'b', 'e'});
    v.push_back({'b', 'd'});
    v.push_back({'c', 'd'});
    v.push_back({'e', 'i'});
    v.push_back({'e', 'g'});
    v.push_back({'e', 'f'});
    //Create graph
    Graph<char> g{v};
    // Check adjacency list by printing it
    g.print_adj_list();
    // Print size of graph
    std::cout << g.size() << std::endl;

    // Adding additional edges
    g.add_edge({'i', 'k'});
    g.add_edge({'f', 'k'});
    g.print_adj_list();
    std::cout << g.size() << std::endl;

    // Test case 1 for DFS and BFS (Result is "Found")
    std::set<char>visited;
    int flag = 0;
    g.dfs('d', 'i', visited, flag);
    g.bfs('d', 'i');

    // Test case 2 for DFS and BFS (Result is "Found")
    flag = 0;
    visited.clear();
    g.dfs('d', 'c', visited, flag);
    g.bfs('d', 'c');

    // Test case 3 for DFS and BFS (Result is "Not Found")
    flag = 0;
    visited.clear();
    g.dfs('d', 'q', visited, flag);
    g.bfs('d', 'q');
    return 0;
}

Answer 1

This is a good start on making a generic graph class not tied to a specific type. Your naming is reasonable. Here are some things I would do differently.

Improving Depth-First Search

If you want to keep the structure of your depth-first search the same but remove the need to have a caller to create and/or clear the visited list, you can make a private function that's called by the public one. Something like this:

template<typename T>
void Graph<T>::dfs(T start, T end)
{
    std::set<T> visited;
    int flag = 0;
    dfs_impl(start, end, visited, flag);
}

Then you would take your current Graph<T>::dfs would be renamed dfs_impl() and pass in the visited and flag from the new dfs function.

Separate Display Logic and Business Logic

You are printing various things within your class methods. Generally, this is a bad idea. There's a principle called Separation of Concerns. The idea is that a method like dfs() will perform the task of finding the path to the end node and return whether it succeeded or not to the caller. The caller will then either print the result or call another function to print it.

The reason you want to do something like this is because it's likely in the future that you will use this method in many different ways. For example, you might determine if there's a path from one node to another and then perform some action, like sending the result over the network to another machine, or displaying an alert to the user, or anything else. If the depth-first search prints out its result, that would be odd if you're using it to determine another action to take. Likewise with the bread-first search.

I would also have the functions return either whether they succeeded or return the actual path through the graph from start to end. That would allow the caller to determine what they want to do with the information.

Breadth-first Search

I think your breadth-first search looks great! Other than moving the print statements out of it, I don't see a lot that needs to change. I'd probably write it in a similar way.

One thing I've seen done to improve performance is to have a flag in each element of the graph that says whether they've already been visited. If you did that, you could avoid searching the visited list on every iteration of the for loop. You would have to start the function by clearing the flags in every node. That single pass over all the nodes would be more efficient in cases where the path between start and end is very long. Of course, when the paths you're searching tend to be very short, it would be less efficient. So there's a trade-off.

Other Things

I would test the performance of using a std::list vs. a std::vector for the adjacency list. You have the option of pre-allocating a number of spaces in the std::vector which might make insertions faster, and iterating over it might also be faster, depending on the implementation. (As always, profile to be sure.)

Answer 2

In dfs(), visited and flag is kind of weird, using stack to implement dfs is more better in my view.