Graph theory using C++ STL

Question

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object.

Any feedback would be appreciated

#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

template<class Key>
class Graph {
public:
    // adds an undirected edge
    void addEdge(Key v1, Key v2) { Adj_.insert( {v1,v2} ); }
    // prints the adjacency list
    void printAdj();
    // Graph traversal functions
    void BFS(Key v);
    void DFS(Key v);
private:
    // Adjacency list
    std::unordered_multimap<Key,Key> Adj_;
};

template<class Key> void Graph<Key>::printAdj()
{
    auto it = Adj_.begin();
    while( it != Adj_.end() )
    {
        std::cout << it->first << ": ";
        auto range = Adj_.equal_range(it->first);
        for ( auto local_it = range.first; local_it!= range.second; ++local_it )
        {
            std::cout << local_it->second << " ";
            ++it;
        }
        std::cout << "\n";

    }
}


//BFS starting from vertex v
//create a queue Q
// mark v as visited and put v into Q
// while Q is non-empty
//  remove the head u of Q
//  mark and enqueue all (unvisited) neighbours of u


template<class Key> void Graph<Key>::BFS(Key v)
{
    // set of visited vertices
    std::unordered_set<Key> visited;
    std::deque<Key> Q;
    Q.push_back(v);
    visited.insert(v);
    while(Q.size() > 0) // while the queue is non-empty do
    {
        // store vertex at the front of the queue
        v = Q.front();
        // remove vertex at the front of the queue
        Q.pop_front();
        std::cout << v << " ";
        // iterate over v's neighbors
        for(auto neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor)
        {
            // check if neighbor has been visited
            auto isthere = visited.find(neighbor->second);
            if(isthere == visited.end()) // if neighbor has not been visited then
            {
                // update visited set
                visited.insert(neighbor->second);
                // add neighbor to back of the queue
                Q.push_back(neighbor->second);
            }
        }
    }
    std::cout << "\n";
}

//DFS starting from vertex v
//create a stack S
//mark v as visited and push v onto S
//while S is non-empty
//  peek at the top v of S
//  if v has an (unvisited) neighbor u, mark u and push it onto S
//  else pop S

template<class Key> void Graph<Key>::DFS(Key v)
{
    // set of visited vertices
    std::unordered_set<Key> visited;
    std::vector<Key> S;
    visited.insert(v);
    S.push_back(v);
    std::cout << v << " ";
    while(S.size() > 0)
    {
        // peek the top v of the stack
        v = S.back();
        // find the index of the first unvisited neighbor of v
        typename std::unordered_multimap<Key,Key>::iterator neighbor;
        for(neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor)
        {
            // check if neighbor has been visited
            auto isthere = visited.find( neighbor->second );
            if( isthere == visited.end() ) break;
        }
        if(neighbor != Adj_.end() ) // the case in which an unvisited neighbor is found
        {
            // mark the neighbor u as visited
            visited.insert(neighbor->second);
            // push u onto the stack
            S.push_back(neighbor->second);
            std::cout << neighbor->second << " ";
        }
        else
        {
            S.pop_back();
        }
    }
}

int main()
{
//example
    Graph<std::string> myGraph;
    myGraph.addEdge("a","b"); myGraph.addEdge("b","c"); myGraph.addEdge("c","d");
    myGraph.addEdge("b","a"); myGraph.addEdge("c","b"); myGraph.addEdge("d","c");
    myGraph.addEdge("c","e"); myGraph.addEdge("e","f"); myGraph.addEdge("b","f");
    myGraph.addEdge("e","c"); myGraph.addEdge("f","e"); myGraph.addEdge("f","b");
    myGraph.addEdge("f","g"); myGraph.addEdge("a","g");
    myGraph.addEdge("g","f"); myGraph.addEdge("g","a");
    std::cout << "Printing the adjacency list:\n";
    myGraph.printAdj();
    std::cout << "Performing BFS exploration starting at vertex a:\n";
    myGraph.BFS("a");
    std::cout << "Performing DFS exploration starting at vertex a:\n";
    myGraph.DFS("a");
}

Answer 1

I see some things that may help you improve your program, but first let me thank you for asking a good question with a complete sample program. It makes things much easier to review and provides context for what you intend to do with your program.

Use const where practical

The current Graph<>::printAdj() routine does not (and should not) modify the underlying object, and so it should be declared const:

void printAdj() const; 

The same is true of all of other routines which don't modify the underlying object.

Don't hard code std::cout

The current printAdj has a very limited use. It traverses the graph and prints the adjacencies by node in a particular format to std::cout. One simple way to improve flexibility would be to at least take the stream as a paramater. That way, I could use a std::stringstream for instance to print to a string or buffer of my own choosing.

Add more flexibility

Think about how one might actually use a Graph object. It's unlikely that only operations to print are going to be sufficient. For that reason, I'd recommend keeping your existing functions but adding another template for an operation that could be used on each node pair. For example:

template<class Key>
template<class BinaryOperation>
void Graph<Key>::processNodes(BinaryOperation op) const
{
    for (const auto &node : Adj_) {
        op(node.first, node.second);
    }
}

Now each pair is passed to a binary operation op. Note also how the use of a "range-for" makes things much simpler and easier to read. Here how it can be used:

template <typename Key>
std::string Graph<Key>::dot() const
{
    std::stringstream stm;
    stm << "digraph {\n";
    processNodes([&stm](const Key &a, const Key &b){
            stm << a << " -> " << b << ";\n";
    });
    stm << "}\n";
    return stm.str();
}

I passed a lambda into the processNodes and created a new member function dot to create a form that can be used by graphviz's dot program. Processing that, in turn, produces this graph:

Consider exposing more of the underlying structure

This is somewhat counter to the usual object-oriented advice, but in this case, I think there's good reason to actually expose a bit more of the underlying std::unordered_multimap via a safe interface. For example, exposing const_iterator interfaces would be helpful in a number of ways.