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;

Graph(int);
};

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

{
//undirected graph
}

{
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();
{
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);
}
• 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. Feb 25, 2018 at 14:48
• @BenSteffan I have edited the question Feb 25, 2018 at 15:31
• Oops. There is a problem with my review. I will revisit it today evening. Feb 26, 2018 at 8:26

Will be fixed soon

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

public:

std::vector<Vertex> vertices;

I suggest you put the two fields under private:.

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.

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

Graph::Graph(int v)
{
vertex_count = v;
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:
std::unordered_set<int>& getChildNodesOf(int node);

private:
};

{
}

{
// Simulate an undirected edge via two bidirectional arcs:
}

std::unordered_set<int>& Graph::getChildNodesOf(int 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;

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

}
}
}
• @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. Feb 25, 2018 at 21:07
• +1, but your getChildNodesOf(int node) method should be const - otherwise you allow the user a very easy way to break class invariants. Feb 26, 2018 at 7:18
• @coderodde yes indeed, I had std::map in mind. Feb 26, 2018 at 7:21

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:

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

• Why should we write auto& instead of auto ? Feb 26, 2018 at 14:03
• @coder So we don't unnecessarily copy the elements, which can be expensive for large objects. Feb 26, 2018 at 14:04

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