Graph Adjacency List

Question

Spent some time implementing a graph as an adjacency list. Looking for suggestions on how to improve this implementation.

#include<vector>
#include<iostream>
class Graph{
public:
 //n is the number of vertices in graph
 Graph(int n)
 {
 N=n;
 E=0;
 //for(int i=0;i < n; ++i)
 for(;n > 0; n--)
 {
 std::vector<int> row;
 adjList.push_back(row);
 }
 }
 //# of vertices
 int Vertices()
 {
 return N;
 }
 //# of Edges
 int Edges()
 {
 return E;
 }
 void addEdge(int v, int w)
 {
 adjList[v].push_back(w);
 adjList[w].push_back(v);
 ++E;
 }
 void adjVertices(int v)
 {
 std::cout<<"Adjacent vertices of"<< v <<std::endl;
 for(auto &x : adjList[v])
 std::cout<< x << std::endl;
 }
private:
 int N;
 int E;
 std::vector< std::vector<int> > adjList;
};
int main()
{
 Graph G(10);
 G.addEdge(3, 4);
 G.addEdge(0, 2);
 G.addEdge(0, 4);
 G.addEdge(0, 9);
 G.adjVertices(0);
 G.adjVertices(4);
}

Answer 1

First very important thing: Good/clear code without comments is better than bad code with comments. I say this because you are using comments to make up for vague variable and method names. For instance:

 //n is the number of vertices in graph
 Graph(int n)
 {
 ....

Then why not rename n to numberOfVerts?

Other instances:

 //# of vertices
 int Vertices() { ... }
 //# of Edges
 int Edges() { ... }

Would be more clear about their intent if named getNumOfVertices() or getVertexCount(). Conversely, getNumOfEdges() and getEdgeCount().

Still talking about naming, the members N and E are also very poor names. One is the number of vertices (N) and the other the number of edges (E). Single letter variable names should generally be avoided, as they are very ambiguous and unclear. One exception to this rule is in loop counters, which historically have been named with i, j, k, and so on, and thus have become a known idiom in programming.

---

You don't need to and should not use a loop to initialize the adjList vector.

 for(;n > 0; n--)
 {
 std::vector<int> row;
 adjList.push_back(row);
 }

That is a very inefficient way of initializing it. push_back() might grow the vector several times, incurring a few expensive memory re-allocations. Just construct the vector with its size, using the constructor initialization list:

 Graph(int numVerts)
 : numOfVerts(numVerts)
 , numOfEdges(0)
 , adjList(numVerts)
 { }

Also worth noting that C++11 allows you to replace the ( ) in the constructor call for the member variables with { }. This is the so called uniform initialization syntax.

---

Be const correct. Add const to methods that don't mutate member data. Get* methods are the common candidates:

int Edges() const { return E; }
 ^^^^^

---

Don't use endl unless you are meant to flush stdout. Otherwise, a "\n" should be used. Flushing at every print call can significantly bring performance down at no benefit.

• Steephen: Thank you for the review comments. I will take care and make changes in code. Does const correct change guaranteed any positive performance impact?
• glampert: @Steephen, I don't think it would improve performance. Proper use of const is meant to make code clearer to the reader and to avoid some common programming errors. Constness can also have implications related to multi-threading, so concurrent programs should pay extra attention to it.