I have written one simple graph Adj Matrix from one Adj List from gitHub .
The first one is Adj list, Second is Adj matrix.
The first One work well. But the second is wrong with int Num which represent the vertices number like the first one int numOfVertices.
It seed like the 'int Num' become a read only variable. It crash into Process finished with exit code 11 .
I have looked for wiki to find "segmentation default", there are 4 reasons , one of them is trying to modify a read only variable.
Then I cancel the modify for "Num" in constructor for the Adj Matrix. It work well.
But I don't know why the first one is well but the second is wrong? And how to solve it? Because I need to modify the value of Num...
The Adj List code
#ifndef ALTHGORITHM_GRAPH_ADJ_LIST_H
#define ALTHGORITHM_GRAPH_ADJ_LIST_H
#include <iostream>
#include <vector>
#include <queue>
namespace graph_adj_list {
template <class dataType> // Type of data vertex will hold
class Graph {
int numOfVertices; // number of vertices.
struct Vertex; // forward declaration of vertex structure
struct Node { // linkedlist for mapping edges in the graph
Vertex * vertexPtr; // points to the vertex to which the edge is adjecent
Node * next; // points to the next edge belonging to same vertex
};
enum visitedState{ // Enum representing visited state of vertex
WHITE, // not yet visited
GRAY, // being visited
BLACK // visited
};
struct Vertex {
visitedState state; // state of vertex, visited/being visited/done
dataType data; // the template data
Node * list; // Pointer to all edges (linkedlist)
};
std::vector<Vertex> vertices; // vector of all vertices.
//private methods
Node * getNode( Vertex * ); // allocate and initialize a newnode for the adj list.
void insertAtEnd( Node * & , Vertex * ); // insert at the end of adjacency list of vertex.
void deleteAllAfter( Node * ); // delete the adjacency list of the vertex.
public:
Graph() = default; // Default constructor
Graph(std::vector<dataType> &);
~Graph();
}
template <typename dataType>
typename Graph<dataType>::Node *
Graph<dataType>::getNode(Vertex * v) // allocate and initialize a newnode for the adj list.
{
Node * newNode = new Node;
newNode->vertexPtr = v;
newNode->next = nullptr;
return newNode;
}
template <typename dataType>
void Graph<dataType>::insertAtEnd( Node * & node, Vertex * v) // insert at the end of adjacency list of vertex.
{
Node *newNode = getNode(v);
if ( node == nullptr ) {
node = newNode;
} else {
Node * temp = node;
while( temp->next != nullptr ) {
temp = temp->next;
}
temp->next = newNode;
}
}
template <typename dataType>
void Graph<dataType>::deleteAllAfter( Node * node ) // delete the adjacency list of the vertex.
{
Node * nextNode;
while( node != nullptr ) {
nextNode = node->next;
delete(node);
node = nextNode;
}
}
template <typename dataType>
Graph<dataType>::Graph(std::vector<dataType> & values) // Non default constructor, takes a vector of vertices data
: numOfVertices(values.size()),
vertices(numOfVertices)
{
for ( int i = 0; i < numOfVertices; ++i ) {
vertices[i].data = values[i];
vertices[i].list = nullptr;
vertices[i].state = WHITE;
}
}
template <typename dataType>
Graph<dataType>::~Graph()
{
for( int i = 0; i < numOfVertices; ++i ) {
deleteAllAfter(vertices[i].list);
}
}
} //end of namespace graph
The Adj Matrix code
#ifndef ALTHGORITHM_GRAPH_ADJ_MATRIX_H
#define ALTHGORITHM_GRAPH_ADJ_MATRIX_H
#include <iostream>
#include <vector>
namespace graph_adj_matrix {
template<typename T>
class Graph {
int Num ;
enum visitedState {
NO_VISIT,
VISITING,
VISITED
};
struct vertex {
T data;
visitedState state;
};
std::vector<std::vector<int>> Matrix;
std::vector<vertex> matrix_list;
public:
Graph() = default;
Graph(std::vector<T> &);
~Graph();
void setMatrix(size_t index1, size_t index2);
void display();
};
template<typename T>
Graph<T>::Graph(std::vector<T> &values) :
Num(values.size())
,matrix_list(Num){
for (typename std::vector<T>::size_type i = 0; i < Num; ++i)
{
matrix_list[i].data = values[i];
matrix_list[i].state = NO_VISIT;
}
for (typename std::vector<T>::size_type i = 0; i < Num; ++i)
for (typename std::vector<T>::size_type j = 0; j < Num; ++j)
Matrix[i].push_back(0);
}
template<typename T>
void Graph<T>::setMatrix(size_t index1, size_t index2) {
for (size_t i = 0; i < Num; ++i) {
if (i == index1 || i == index2) {
for (size_t j = 0; j < Num; ++j) {
if (((i == index1) && (j == index2)) || ((i == index2) && (j == index1))) {
Matrix[i][j] = 1;
break;
}
}
break;
}
}
}
template<typename T>
void Graph<T>::display() {
for (size_t i = 0; i < Num; ++i) {
for (size_t j = 0; j < Num; j++)
std::cout << Matrix[i][j] << " ";
std::cout << std::endl;
}
}
template <typename T>
Graph<T>::~Graph() {}
}
#endif //ALTHGORITHM_GRAPH_ADJ_MATRIX_H
Cpp:
#include "Graph_Adj_List.h"
#include "Graph_Adj_Matrix.h"
int main() {
std::vector<std::string> myVec{"ABC","DEF","GHI","ZZZ"};
graph_adj_list::Graph<std::string> myGraph(myVec);
graph_adj_matrix::Graph<std::string> myGraph_matrix(myVec);
}
I have debugger the program
graph_adj_list::Graph<std::string> myGraph(myVec);
work well. But the
graph_adj_matrix::Graph<std::string> myGraph_matrix(myVec);
stop at
#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
void
vector<_Tp, _Allocator>::push_back(value_type&& __x)
{
if (this->__end_ < this->__end_cap())
{
__RAII_IncreaseAnnotator __annotator(*this);
__alloc_traits::construct(this->__alloc(),
_VSTD::__to_raw_pointer(this->__end_),
_VSTD::move(__x));
__annotator.__done();
++this->__end_;
}
else
__push_back_slow_path(_VSTD::move(__x));
}
A function from vector header Row from 1635 to 1653. Debugger report this
Exception = EXC_BAD_ACCESS (code=1, address=0x8)
this = {std::_11::vector<int,std::_1::allocator> * |0x0 } NULL
When I enter the body that sets the ```Matrix[i].push_back(0)''' It crashes the wrong condition.
The following is just an gues, after short playing around with your code:
Process finished with exit code 11
Probably could mean that your program encountered signal 11 (SIGSEGV, aka Segmentation fault)
My guess: you forgot to initialize Matrix, so Matrix[i].push_back(0); causes undefined behaviour and luckily resultet in a segmentation fault.
Edit: you can easily initialize the inner vectors with the vector constructor: std::vector<std::vector<int>>(Num, std::vector<int>(Num));. This will create a vector with Num copies of a vector with Num ints.