# Graph theory using C++ STL

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:
// Graph traversal functions
void BFS(Key v);
void DFS(Key v);
private:
};

{
{
std::cout << 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
{
// 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;
{
// 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;
std::cout << "Printing the adjacency list:\n";
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");
}

• All your for loops could be range-based. It will make your code less verbose. Dec 22, 2015 at 13:22
• @glampert do you know how to implement range-based loops for loops such as for(auto neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor) ? Dec 23, 2015 at 5:15
• 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... Dec 23, 2015 at 5:24
• @glampert what about this one for ( auto local_it = range.first; local_it!= range.second; ++local_it ) ? Dec 23, 2015 at 5:43
• Only with std::for_each I think. Wouldn't be a bad solution really. Give it a try perhaps. Dec 23, 2015 at 5:46

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.

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.

• 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? Dec 23, 2015 at 6:10
• webgraphviz.com Dec 23, 2015 at 6:12