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

• glampert: All your for loops could be range-based. It will make your code less verbose.
• user11881: @glampert do you know how to implement range-based loops for loops such as for(auto neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor) ?
• glampert: Ah, sorry, my mistake. That one is using find, so yeah, there's no escape from using the traditional for loop, unless you try the std::for_each function with a lambda, but that might be overkill...
• user11881: @glampert what about this one for ( auto local_it = range.first; local_it!= range.second; ++local_it ) ?
• glampert: Only with std::for_each I think. Wouldn't be a bad solution really. Give it a try perhaps.

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:

Sample 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.

• user11881: Thanks for this interesting addition. Unfortunately I wasn't able to get graphviz dot command to work on mac os yosemite (other people have reported similar problems). Do you know of any online renderer?
• user11881: webgraphviz.com