4
\$\begingroup\$

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

3 Answers 3

7
\$\begingroup\$

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

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

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.

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.