What is wrong with my vector of vectors?

0
votes
class Graph {


public:

    std::vector<std::vector<int>> adj;

    Graph(int V) {
        std::vector<std::vector<int> > adj(V, std::vector<int>());
    }

    void insert_edge(int v, int u);
    void print_adjacencylist();


};


void Graph::insert_edge(int v, int u) {

adj[v].push_back(u);


}

I'm calling 

Graph G(8);

G.insert_edge(4, 1);

and I get an error:

Debug Assertion Failed! Expression: vector subscript out of range

I'm trying to create a graph, which will have V vertices. I am using a vector of vectors to represent the graph (as an adjacency list). The nodes in my graph are numbered from 0 to V-1, so the index of the adj vector represents the number of the node. Unless I'm mistaken, adj[u] represents a vector, so I should be able to use adj[u].push_back(v) to push the vertex v into the adjacency list of the vertex u. So in my example, adj[4] should get the vector where the vertices adjacent to the node 4 are, and .push_back(1)

This is not happening. I'm thinking it has to do with me not initializing everything correctly but I've tried like a million things (even tried using a for loop to push_back a vector to each index of the adj vector) and I just keep getting the same error.

4
c++vectorgraph

4 Answers

3
votes

Your data member vector is empty and you are accessing it out of bounds. The reason for this is that you default initialized it in the constructor. You also initialized a local variable that doesn't get used anywhere:

Graph(int V) {
  // Oops! Local variable adj, nothing to do with member
  // of same name
  std::vector<std::vector<int> > adj(V, std::vector<int>());
}

What you intended to do was initialize the data member adj, which you can do in the constructor initialization list

Graph(int V) : adj(V, std::vector<int>()) {}

Or, with less typing,

Graph(int V) : adj(V) {}

Note that this problem can be avoided by using suitable flags on some popular compilers. For instance, using the -Wshadow flag on clang or gcc would yield a warning such as

warning: declaration shadows a field of 'Graph' [-Wshadow]
std::vector > adj(V, std::vector());

0
votes

At this line:

adj[v].push_back(u);

You evoke undefined behaviour. because adj is empty (i.e., it doesn't have vectors in it).

0
votes

Your first statement within the constructor does not initialise the adj member, but instead declares a local variable. You should try:

Graph(int V) : adj(V, std::vector<int>()){

}
0
votes

In your constructor

Graph(int V) {
    std::vector<std::vector<int> > adj(V, std::vector<int>());
}

you are not initialising your member variable, but rather creating a new variable adj which is destroyed after the constructor is finished.

What you should do instead is use an initializer list to initialise your member variable:

Graph(int V) : adj{V, std::vector<int>{}} {}