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

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

        }
    }
}

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.

Answer 3

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