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
#include
#include
#include
#include

template
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 Adj_;
};

template void Graph::printAdj()
{
auto it = Adj_.begin();
while( it != Adj_.end() )
{
std::cout first first);
for ( auto local_it = range.first; local_it!= range.second; ++local_it )
{
std::cout second void Graph::BFS(Key v)
{
// set of visited vertices
std::unordered_set visited;
std::deque 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 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 void Graph::DFS(Key v)
{
// set of visited vertices
std::unordered_set visited;
std::vector S;
visited.insert(v);
S.push_back(v);
std::cout 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::iterator neighbor;
for(neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor)
{

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
template
void Graph::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 
std::string Graph::dot() const
{
    std::stringstream stm;
    stm  " << 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.

StackExchange Code Review Q#114714, answer score: 5