I am fairly new to C++ and I am trying to make sense out of these exhausting error messages so far. I really got stuck in this one and it really makes no sense at all. The code that I shared below is a part of a personal directed graph header file I was working on. I won't be sharing everything since it is sort of long and other parts seems irrelevant to my problem. But if required please specify, I'll share. Now the function below is to assess if a vertex (i.e. node) is reachable or not from a given root vertex. It employs a Depth First Search defined iteratively in order to do this.
The code compiles but I keep getting this error message in the runtime which makes no sense at all since it seems to be caused by pushing an int to an std::stack (when I comment out the line I do this, the code runs). Such that it->first is an int. It is an index in my adjacency list which is of type std::unordered_map and also represents a vertex id.
I tried two different things so far. I assigned it->first to a separate int id variable and tried to push it that way. And I tried to change std::stack to std::stack<Vertex> and tried to push vertices instead of ids as ints (and configured the rest of the code accordingly). Nothing worked, I still get the same error.
I am using Visual Studio 2017 and MSVC compiler.
template <typename T>
class Vertex {
private:
int id; //Id of the vertex
double weight; //Weight of the vertex
T data; //Custom data to be stored inside the vertex
public:
Vertex() {} //Default constructor.
Vertex(int x, double y, T d) : id(x), weight(y), data(d) {} //Constructor with custom data type T
Vertex(int x, double y) : id(x), weight(y) {} //Alternative constructor without type T, for graph use only
int getId() { return id; }
double getWeight() { return weight; }
T getData() { return data; }
};
template <typename T>
class DirectedGraph {
private:
std::unordered_map<int, Vertex<T>> vertices; //Stores vertices
std::unordered_map<int, std::unordered_map<int, double>> adj_list; //Stores the graph in adjacency list format. Inner-most double type variable stores edge weight.
size_t n_edges; //Stores total number of edges
size_t n_vertices; //Stores total number of vertices
int is_acyclic; //Variable to record if the graph is acyclic or not. Convention for this is following, 1: Graph is acyclic, 0: Graph is not acyclic, -1: Not tested yet
public:
DirectedGraph();
~DirectedGraph();
bool contains(const int&) const; //Returns true if the graph contains the given vertex_id, false otherwise.
bool adjacent(const int&, const int&); //Returns true if the first vertex is adjacent to the second, false otherwise.
void addVertex(Vertex<T>&); //Adds the passed in vertex to the graph (with no edges).
void addEdge(const int&, const int&, const double&); //Adds a weighted edge from the first vertex to the second.
void removeVertex(const int&); //Removes the given vertex. Should also clear any incident edges.
void removeEdge(const int&, const int&); //Removes the edge between the two vertices, if it exists.
size_t inDegree(const int&); //Returns number of edges coming in to a vertex.
size_t outDegree(const int&); //Returns the number of edges leaving a vertex.
size_t degree(const int&); //Returns the degree of the vertex (both in edges and out edges).
size_t numVertices(); //Returns the total number of vertices in the graph.
size_t numEdges() const; //Returns the total number of edges in the graph.
std::unordered_map<int, Vertex<T>> getVertices(); //Returns a vector containing all the vertices.
Vertex<T> getVertex(const int& u_id); //Retruns specified vertex. If vertex doesn't exist, the id and weight of the returned vertex are both -1.
double getEdgeWeight(const int& u_id, const int& v_id); //Returns the weight of the specified edge. If the edge doesn't exist, it returns -1.
std::vector<Vertex<T>> getNeighbours(const int&); //Returns a vector containing all the vertices reachable from the given vertex. The vertex is not considered a neighbour of itself.
std::vector<Vertex<T>> getSecondOrderNeighbours(const int&); // Returns a vector containing all the second_order_neighbours (i.e., neighbours of neighbours) of the given vertex.
// A vector cannot be considered a second_order_neighbour of itself.
bool reachable(const int&, const int&); //Returns true if the second vertex is reachable from the first (can you follow a path of out-edges to get from the first to the second?). Returns false otherwise.
bool containsCycles(); // Return true if the graph contains cycles (there is a path from any vertices directly/indirectly to itself), false otherwise.
std::vector<Vertex<T>> depthFirstTraversal(const int&); //Returns the vertices of the graph in the order they are visited in by a depth-first traversal starting at the given vertex.
std::vector<Vertex<T>> breadthFirstTraversal(const int&); //Returns the vertices of the graph in the order they are visited in by a breadth-first traversal starting at the given vertex.
/*
* Following function is an iterative implementation of Dijkstra's SP algorithm.
* It returns a pair consisting of an array of shortest distances to all other
* vertices from the given root vertex u_id (vertices are identified via
* indexes in the array such that shortest distance to vertex i is placed to
* the i th element in the array), and a "previous vertex" unordered_map. (If
* you are unsure about what a "previous vertex" list is,
* see https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
*/
std::pair<int *, std::unordered_map<int, int>> dijkstra(int u_id);
std::pair<int, std::vector<Vertex<T>>> shortestPath(int u_id, int v_id); //This function finds the shortest path to a single given target vertex (v_id) from a given vertex (u_id) as a pair that contains <distance, path>
std::vector<std::vector<Vertex<T>>> stronglyConnectedComponents(); //Identifies and returns strongly connected components as a vector of vectors
std::vector<Vertex<T>> topologicalSort(); //Returns a topologically sorted list of the graph. It requires the graph to be acyclic. If the graph isn't acyclic, it returns an empty vector.
};
template <typename T>
bool DirectedGraph<T>::reachable(const int& u_id, const int& v_id)
{
//This function is a Depth First Search Algorithm that halts when latter vertex is found
//Returns true if v_id is reachable from u_id
std::stack<int> track; //Stack for DFS
bool* visited = new bool[numVertices()]{};
track.push(u_id);
while (!track.empty())
{
bool found = false;
auto it = adj_list[track.top()].begin();
while (it != adj_list[track.top()].end() && !found)
{
if (!visited[it->first])
{
if (it->first == v_id)
{
delete[] visited;
return true;
}
visited[it->first] = true;
track.push(it->first);// <--When I comment out this line, the code runs.
found = true;
}
++it;
}
if (!found) { track.pop(); }
}
delete[] visited;
return false;
}
Debug Assertion Failed!
Filec:\program files(x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.15.26726\include\list
Line: 240
Expression: list iterators incompatible
The code is comparing incompatible iterators. It is illegal to compare two iterators that come from different container instances. The standard says: The domain of == for forward iterators is that of iterators over the same underlying sequence.
This requirement is not satisfied by the code, where it may iterate over one std::unordered_map<int, double>, and adj_list[track.top()] may be another std::unordered_map<int, double> object. This incompatibility is caused by the changing of the value of track.top(), due to the line:
track.push(it->first);// <--When I comment out this line, the code runs.
When not running under debug mode, the code may suddenly start running, since the compiler no longer generates this validation code, but it also may trash your memory and crash in weird ways.
The error is quite clear: the code compares iterators that come from different container objects. The iterators must come from the same container object.