Breadth First Search using adjacency list

Question

I want to improve this code using STL. Let me know if I should add any other function in this code.

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <limits>
class Graph
{
 int vertex_count;
 enum Color {WHITE, GRAY, BLACK};
 enum { INFINITY = std::numeric_limits<int>::max() };
 struct Vertex
 {
 int id;
 int distance;
 Color color;
 Vertex(int _id) : id(_id),
 color(Color::WHITE),
 distance(INFINITY)
 {}
 };
public:
 std::vector<Vertex> vertices;
 std::vector< std::list<int> > adjList;
 Graph(int);
 void addEdge(int, int);
 void breadthFirstSearch(int);
};
Graph::Graph(int v)
{
 vertex_count = v;
 adjList.resize(vertex_count);
 for (int i = 0; i < vertex_count; i++)
 {
 vertices.push_back( Vertex(i) );
 }
}
void Graph::addEdge(int src, int dest)
{
 //undirected graph
 adjList[src].push_back(dest);
 adjList[dest].push_back(src);
}
void Graph::breadthFirstSearch(int s)
{
 vertices[s].color = GRAY;
 vertices[s].distance = 0;
 std::queue<Vertex> q;
 q.push(vertices[s]);
 while (!q.empty())
 {
 auto u = q.front();
 q.pop();
 for (auto v = adjList[u.id].begin(); v != adjList[u.id].end(); v++)
 {
 if (vertices[*v].color == WHITE)
 {
 vertices[*v].color = GRAY;
 vertices[*v].distance = u.distance + 1;
 q.push(vertices[*v]);
 }
 }
 u.color = BLACK;
 std::cout << vertices[u.id].id << " at level " << vertices[u.id].distance <<'\n';
 }
}
int main()
{
 Graph grp(5);
 grp.addEdge(0, 1);
 grp.addEdge(0, 4);
 grp.addEdge(1, 3);
 grp.addEdge(1, 4);
 grp.addEdge(1, 2);
 grp.addEdge(2, 3);
 grp.addEdge(3, 4);
 grp.breadthFirstSearch(2);
}

• Ben Steffan: What do you mean by "efficient"? Are you referring to runtime/execution speed? If yes, please do some benchmarks first and tell us what exactly is slow. If not, please elaborate on what you actually want to have reviewed.
• coder: @BenSteffan I have edited the question
• coderodde: Oops. There is a problem with my review. I will revisit it today evening.

Answer 1

Will be fixed soon

Advice 1

In BFS, you don't really need colors. (See alternative implementation.)

Advice 2 (Exposing internals)

public:
 std::vector<Vertex> vertices;
 std::vector< std::list<int> > adjList;

I suggest you put the two fields under private:.

Advice 3

Since an undirected graph is a special case of a directed graph (in which each edge \$\{u, v\}\$ can be simulated by two directed arcs \$(u, v), (v, u)\$), I suggest you implement it as a directed graph, but add a method that inserts an undirected edge by two directed arcs.

Advice 4

I would rip off the actual BFS from the Graph. This is, however, a matter of taste.

Advice 5

Graph::Graph(int v)
{
 vertex_count = v;
 adjList.resize(vertex_count);
 for (int i = 0; i < vertex_count; i++)
 {
 vertices.push_back( Vertex(i) );
 }
}

Why not name int v int vertex_count in the first place? Also, I would go for, for example, std::unordered_map<int, list<int>> since it is not restricted to non-negative integers.

Alternative implementation

This is by no means a best possible implementation, but it demonstrates the overall structure I had in mind:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iterator>
class Graph
{
public:
 void addEdge(int node1, int node2);
 void addArc(int tailNode, int headNode);
 std::unordered_set<int>& getChildNodesOf(int node);
private:
 std::unordered_map<int, std::unordered_set<int>> m_adjacency_list;
};
void Graph::addArc(int tail, int head)
{
 m_adjacency_list[tail].insert(head);
}
void Graph::addEdge(int tail, int head)
{
 // Simulate an undirected edge via two bidirectional arcs:
 addArc(tail, head);
 addArc(head, tail);
}
std::unordered_set<int>& Graph::getChildNodesOf(int node)
{
 return m_adjacency_list[node];
}
std::unordered_map<int, int*>
computeUnweightedShortestPathTree(Graph& graph, int sourceNode)
{
 std::unordered_map<int, int*> parentMap = { { sourceNode, nullptr }};
 std::queue<int> open;
 open.push(sourceNode);
 while (!open.empty())
 {
 int currentNode = open.front();
 open.pop();
 int* parentNode = new int{currentNode};
 for (int childNode : graph.getChildNodesOf(currentNode))
 {
 if (parentMap.find(childNode) == parentMap.end())
 {
 parentMap[childNode] = parentNode;
 open.push(childNode);
 }
 }
 }
 return parentMap;
}
std::vector<int> tracebackPath(int targetNode,
 std::unordered_map<int, int*>& shortestPathTree)
{
 std::vector<int> path;
 int currentNode = targetNode;
 int* nextNode = shortestPathTree[currentNode];
 while (true) {
 path.push_back(currentNode);
 nextNode = shortestPathTree[currentNode];
 if (nextNode == nullptr)
 {
 break;
 }
 currentNode = *nextNode;
 } 
 std::reverse(path.begin(), path.end());
 return path;
}
int main()
{
 Graph graph;
 graph.addEdge(0, 1);
 graph.addEdge(0, 4);
 graph.addEdge(1, 3);
 graph.addEdge(1, 4);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(3, 4);
 for (int sourceNode : { 0, 1, 2, 3, 4 })
 {
 std::unordered_map<int, int*> shortestPathTree =
 computeUnweightedShortestPathTree(graph, sourceNode);
 for (int targetNode : { 0, 1, 2, 3, 4 })
 {
 std::cout << "Shortest path from " << sourceNode << " to " << targetNode << ": ";
 std::vector<int> path = tracebackPath(targetNode, shortestPathTree);
 std::copy(path.cbegin(),
 path.cend(),
 std::ostream_iterator<int>(std::cout, " "));
 std::cout << "\n";
 }
 }
}

• coderodde: @StPiere Wrong. std::unordered_map is a hash-table that runs access in constant time on average. What you had in mind is std::map that is a balanced binary search tree and runs indeed in logarithmic time.
• Yuushi: +1, but your getChildNodesOf(int node) method should be const - otherwise you allow the user a very easy way to break class invariants.
• StPiere: @coderodde yes indeed, I had std::map in mind.

Answer 2

One small thing I would like to mention is C++11 introduces a syntax known as a range-based for loop, which allows you to loop over a container without having to deal with iterators. Thus, you can replace:

 for (auto v = adjList[u.id].begin(); v != adjList[u.id].end(); v++)
 {
 if (vertices[*v].color == WHITE)
 {
 vertices[*v].color = GRAY;
 vertices[*v].distance = u.distance + 1;
 q.push(vertices[*v]);
 }
 }

with:

for (const auto& v : adjList[u.id])
{
 if (vertices[v].color == WHITE)
 {
 vertices[v].color = GRAY;
 vertices[v].distance = u.distance + 1;
 q.push(vertices[v]);
 }
}

I personally find this syntax easier to read than the other one, since it is more compact horizontally, and the dereference operator (*) is completely removed.

• coder: Why should we write auto& instead of auto ?
• Arnav Borborah: @coder So we don't unnecessarily copy the elements, which can be expensive for large objects.

Answer 3

What I always find useful is when using enums is this library