The following code when compiled in unix environment (with g++) it is producing a segmentation fault. In Windows it's compiling fine but with some input files (like the one I include) it is producing the following message:
Degug Assertion Failed!
Program:....
File: dbgheap.c
Line: 1044
Expression:_CrtIsValidHeapPointer(pUserData)
and then it tells to refer to the c++ library to learn about how my program can cause an assertion failure...As much as I tried though, I couldn't do anything.
I don't know if it is because of the same reason, but I mostly care about the fact that it is not compiling in Linux...Any help would be really appreciated. Thank you!
The input file:
5
4
5
2
1
The code:
#include #include #include struct Node
{
int vertex;
Node *next;
};
int num_vertices;
const int WHITE=1,GRAY=2,BLACK=3; //status of node
void createGraph(ifstream& fin, Node** adj)
{
Node *new_node, *last;
int adj_vertex, vertex=1;
char ch;
fin >> num_vertices;
ch = fin.get();
for (int i=1; i> adj_vertex;
new_node = new Node;
new_node->vertex = adj_vertex;
new_node->next = NULL;
if(adj[vertex] == NULL)
{
adj[vertex] = last = new_node;
}
else
{
last->next = new_node;
last = new_node;
}
ch = fin.peek();
}
ch = fin.get();
vertex++;
}
}
void DFS_Visit(int vertex, Node** adj, int* color, int* pred)
{
int* cycle = new int [num_vertices];
int last_checked;
color[vertex] = GRAY;
while (adj[vertex] != NULL)
{
if (color[adj[vertex]->vertex] == GRAY ) //back edge detected ...(cycle!)
{
cout << "The graph has a cycle!!!"<<endl;
last_checked = vertex;
int start_of_cycle = adj[vertex]->vertex; // the code next is to print cycle in the
cout << start_of_cycle << " "; // correct order.
int j=0;
while(pred[vertex] != start_of_cycle)
{
vertex = pred[vertex];
cycle[j] = vertex;
j++;
}
for(j--; j>=0; j--)
{
cout << cycle[j] << " ";
}
cout << last_checked << " " <<start_of_cycle;
exit(0);
}
else if (color[adj[vertex]->vertex] == WHITE)
{
pred[adj[vertex]->vertex] = vertex;
DFS_Visit(adj[vertex]->vertex, adj, color, pred);
}
adj[vertex] = adj[vertex]->next;
}
color[vertex] = BLACK;
}
void DFS(Node** adj, int* color, int* pred)
{
for(int i=1; i<num_vertices+1; i++)
{
color[i] = WHITE;
pred[i] = -1;
}
for(int j=1; j<num_vertices+1; j++)
{
if (color[j]==WHITE)
{
DFS_Visit(j, adj, color, pred);
}
}
}
int main(int argc, char* argv[])
{
Node **adj = new Node* [num_vertices]; //holds the adjusted vertices
int *pred = new int[num_vertices]; //holds the predecessors of each vertex
int *color = new int[num_vertices]; //holds the color (status) of each vertex
ifstream fin; // input file
if (argc < 2)
{
cout << "Need to provide input file as command line argument..." << endl;
exit(1);
}
fin.open(argv[1]);
if (!fin.good())
{
cout << "Could not open " << argv[1] << " for input... " << endl;
exit(1);
}
createGraph(fin, adj);
fin.close();
DFS(adj, color, pred);
cout << "The graph is acyclic...";
return 0;
}
Comments
:
: Degug Assertion Failed!
:
: Program:....
: File: dbgheap.c
: Line: 1044
:
: Expression:_CrtIsValidHeapPointer(pUserData)
:
: and then it tells to refer to the c++ library to learn about how my program can cause an assertion failure...As much as I tried though, I couldn't do anything.
:
: I don't know if it is because of the same reason, but I mostly care about the fact that it is not compiling in Linux...Any help would be really appreciated. Thank you!
:
: The input file:
: 5
: 4
: 5
: 2
:
: 1
:
: The code:
: #include
: #include
: #include
:
: struct Node
: {
: int vertex;
: Node *next;
: };
:
: int num_vertices;
: const int WHITE=1,GRAY=2,BLACK=3; //status of node
:
:
: void createGraph(ifstream& fin, Node** adj)
: {
: Node *new_node, *last;
: int adj_vertex, vertex=1;
: char ch;
:
: fin >> num_vertices;
: ch = fin.get();
:
: for (int i=1; i> adj_vertex;
: new_node = new Node;
: new_node->vertex = adj_vertex;
: new_node->next = NULL;
: if(adj[vertex] == NULL)
: {
: adj[vertex] = last = new_node;
: }
: else
: {
: last->next = new_node;
: last = new_node;
: }
: ch = fin.peek();
: }
: ch = fin.get();
: vertex++;
: }
: }
:
: void DFS_Visit(int vertex, Node** adj, int* color, int* pred)
: {
: int* cycle = new int [num_vertices];
: int last_checked;
: color[vertex] = GRAY;
:
: while (adj[vertex] != NULL)
: {
: if (color[adj[vertex]->vertex] == GRAY ) //back edge detected ...(cycle!)
: {
: cout << "The graph has a cycle!!!"<<endl;
: last_checked = vertex;
: int start_of_cycle = adj[vertex]->vertex; // the code next is to print cycle in the
: cout << start_of_cycle << " "; // correct order.
:
: int j=0;
: while(pred[vertex] != start_of_cycle)
: {
: vertex = pred[vertex];
: cycle[j] = vertex;
: j++;
: }
: for(j--; j>=0; j--)
: {
: cout << cycle[j] << " ";
: }
:
: cout << last_checked << " " <<start_of_cycle;
: exit(0);
: }
: else if (color[adj[vertex]->vertex] == WHITE)
: {
: pred[adj[vertex]->vertex] = vertex;
: DFS_Visit(adj[vertex]->vertex, adj, color, pred);
: }
: adj[vertex] = adj[vertex]->next;
: }
: color[vertex] = BLACK;
: }
:
: void DFS(Node** adj, int* color, int* pred)
: {
: for(int i=1; i<num_vertices+1; i++)
: {
: color[i] = WHITE;
: pred[i] = -1;
: }
: for(int j=1; j<num_vertices+1; j++)
: {
: if (color[j]==WHITE)
: {
: DFS_Visit(j, adj, color, pred);
: }
: }
: }
:
: int main(int argc, char* argv[])
: {
: Node **adj = new Node* [num_vertices]; //holds the adjusted vertices
: int *pred = new int[num_vertices]; //holds the predecessors of each vertex
: int *color = new int[num_vertices]; //holds the color (status) of each vertex
:
: ifstream fin; // input file
:
: if (argc < 2)
: {
: cout << "Need to provide input file as command line argument..." << endl;
: exit(1);
: }
:
: fin.open(argv[1]);
:
: if (!fin.good())
: {
: cout << "Could not open " << argv[1] << " for input... " << endl;
: exit(1);
: }
:
: createGraph(fin, adj);
: fin.close();
: DFS(adj, color, pred);
: cout << "The graph is acyclic...";
: return 0;
: }
:
:
You are dynamically creating the adj, pred, and color variables based on the number of vertices expected, but you create these before you know how many vertices to expect - since this is read from the file. I would not new those at the beginning of main, but would new the adj array in createGraph and return the number of vertices so that main could then allocate pred and color appropriately. before calling DFS().
Of course, main will have to release all of these at the end.
When you read data in from the file, make sure you do not try to read more data than is expected (or the size of the allocated arrays). That is the basic problem here - you are trying to input data for which there is no location allocated. This is in regard to arrays of course. If you used a linked list, you could read in data, dynamically create a single node, add it to the list, then read the next. That way you do not depend having an accurate count as the first thing in your data file - you determine the count based on how many entries you actually read.
: :
: : Degug Assertion Failed!
: :
: : Program:....
: : File: dbgheap.c
: : Line: 1044
: :
: : Expression:_CrtIsValidHeapPointer(pUserData)
: :
: : and then it tells to refer to the c++ library to learn about how my program can cause an assertion failure...As much as I tried though, I couldn't do anything.
: :
: : I don't know if it is because of the same reason, but I mostly care about the fact that it is not compiling in Linux...Any help would be really appreciated. Thank you!
: :
: : The input file:
: : 5
: : 4
: : 5
: : 2
: :
: : 1
: :
: : The code:
: : #include
: : #include
: : #include
: :
: : struct Node
: : {
: : int vertex;
: : Node *next;
: : };
: :
: : int num_vertices;
: : const int WHITE=1,GRAY=2,BLACK=3; //status of node
: :
: :
: : void createGraph(ifstream& fin, Node** adj)
: : {
: : Node *new_node, *last;
: : int adj_vertex, vertex=1;
: : char ch;
: :
: : fin >> num_vertices;
: : ch = fin.get();
: :
: : for (int i=1; i> adj_vertex;
: : new_node = new Node;
: : new_node->vertex = adj_vertex;
: : new_node->next = NULL;
: : if(adj[vertex] == NULL)
: : {
: : adj[vertex] = last = new_node;
: : }
: : else
: : {
: : last->next = new_node;
: : last = new_node;
: : }
: : ch = fin.peek();
: : }
: : ch = fin.get();
: : vertex++;
: : }
: : }
: :
: : void DFS_Visit(int vertex, Node** adj, int* color, int* pred)
: : {
: : int* cycle = new int [num_vertices];
: : int last_checked;
: : color[vertex] = GRAY;
: :
: : while (adj[vertex] != NULL)
: : {
: : if (color[adj[vertex]->vertex] == GRAY ) //back edge detected ...(cycle!)
: : {
: : cout << "The graph has a cycle!!!"<<endl;
: : last_checked = vertex;
: : int start_of_cycle = adj[vertex]->vertex; // the code next is to print cycle in the
: : cout << start_of_cycle << " "; // correct order.
: :
: : int j=0;
: : while(pred[vertex] != start_of_cycle)
: : {
: : vertex = pred[vertex];
: : cycle[j] = vertex;
: : j++;
: : }
: : for(j--; j>=0; j--)
: : {
: : cout << cycle[j] << " ";
: : }
: :
: : cout << last_checked << " " <<start_of_cycle;
: : exit(0);
: : }
: : else if (color[adj[vertex]->vertex] == WHITE)
: : {
: : pred[adj[vertex]->vertex] = vertex;
: : DFS_Visit(adj[vertex]->vertex, adj, color, pred);
: : }
: : adj[vertex] = adj[vertex]->next;
: : }
: : color[vertex] = BLACK;
: : }
: :
: : void DFS(Node** adj, int* color, int* pred)
: : {
: : for(int i=1; i<num_vertices+1; i++)
: : {
: : color[i] = WHITE;
: : pred[i] = -1;
: : }
: : for(int j=1; j<num_vertices+1; j++)
: : {
: : if (color[j]==WHITE)
: : {
: : DFS_Visit(j, adj, color, pred);
: : }
: : }
: : }
: :
: : int main(int argc, char* argv[])
: : {
: : Node **adj = new Node* [num_vertices]; //holds the adjusted vertices
: : int *pred = new int[num_vertices]; //holds the predecessors of each vertex
: : int *color = new int[num_vertices]; //holds the color (status) of each vertex
: :
: : ifstream fin; // input file
: :
: : if (argc < 2)
: : {
: : cout << "Need to provide input file as command line argument..." << endl;
: : exit(1);
: : }
: :
: : fin.open(argv[1]);
: :
: : if (!fin.good())
: : {
: : cout << "Could not open " << argv[1] << " for input... " << endl;
: : exit(1);
: : }
: :
: : createGraph(fin, adj);
: : fin.close();
: : DFS(adj, color, pred);
: : cout << "The graph is acyclic...";
: : return 0;
: : }
: :
: :
: You are dynamically creating the adj, pred, and color variables based on the number of vertices expected, but you create these before you know how many vertices to expect - since this is read from the file. I would not new those at the beginning of main, but would new the adj array in createGraph and return the number of vertices so that main could then allocate pred and color appropriately. before calling DFS().
: Of course, main will have to release all of these at the end.
:
: When you read data in from the file, make sure you do not try to read more data than is expected (or the size of the allocated arrays). That is the basic problem here - you are trying to input data for which there is no location allocated. This is in regard to arrays of course. If you used a linked list, you could read in data, dynamically create a single node, add it to the list, then read the next. That way you do not depend having an accurate count as the first thing in your data file - you determine the count based on how many entries you actually read.
:
: :
: : Degug Assertion Failed!
: :
: : Program:....
: : File: dbgheap.c
: : Line: 1044
: :
: : Expression:_CrtIsValidHeapPointer(pUserData)
: :
: : and then it tells to refer to the c++ library to learn about how my program can cause an assertion failure...As much as I tried though, I couldn't do anything.
: :
: : I don't know if it is because of the same reason, but I mostly care about the fact that it is not compiling in Linux...Any help would be really appreciated. Thank you!
: :
: : The input file:
: : 5
: : 4
: : 5
: : 2
: :
: : 1
: :
: : The code:
: : #include
: : #include
: : #include
: :
: : struct Node
: : {
: : int vertex;
: : Node *next;
: : };
: :
: : int num_vertices;
: : const int WHITE=1,GRAY=2,BLACK=3; //status of node
: :
: :
: : void createGraph(ifstream& fin, Node** adj)
: : {
: : Node *new_node, *last;
: : int adj_vertex, vertex=1;
: : char ch;
: :
: : fin >> num_vertices;
: : ch = fin.get();
: :
: : for (int i=1; i> adj_vertex;
: : new_node = new Node;
: : new_node->vertex = adj_vertex;
: : new_node->next = NULL;
: : if(adj[vertex] == NULL)
: : {
: : adj[vertex] = last = new_node;
: : }
: : else
: : {
: : last->next = new_node;
: : last = new_node;
: : }
: : ch = fin.peek();
: : }
: : ch = fin.get();
: : vertex++;
: : }
: : }
: :
: : void DFS_Visit(int vertex, Node** adj, int* color, int* pred)
: : {
: : int* cycle = new int [num_vertices];
: : int last_checked;
: : color[vertex] = GRAY;
: :
: : while (adj[vertex] != NULL)
: : {
: : if (color[adj[vertex]->vertex] == GRAY ) //back edge detected ...(cycle!)
: : {
: : cout << "The graph has a cycle!!!"<<endl;
: : last_checked = vertex;
: : int start_of_cycle = adj[vertex]->vertex; // the code next is to print cycle in the
: : cout << start_of_cycle << " "; // correct order.
: :
: : int j=0;
: : while(pred[vertex] != start_of_cycle)
: : {
: : vertex = pred[vertex];
: : cycle[j] = vertex;
: : j++;
: : }
: : for(j--; j>=0; j--)
: : {
: : cout << cycle[j] << " ";
: : }
: :
: : cout << last_checked << " " <<start_of_cycle;
: : exit(0);
: : }
: : else if (color[adj[vertex]->vertex] == WHITE)
: : {
: : pred[adj[vertex]->vertex] = vertex;
: : DFS_Visit(adj[vertex]->vertex, adj, color, pred);
: : }
: : adj[vertex] = adj[vertex]->next;
: : }
: : color[vertex] = BLACK;
: : }
: :
: : void DFS(Node** adj, int* color, int* pred)
: : {
: : for(int i=1; i<num_vertices+1; i++)
: : {
: : color[i] = WHITE;
: : pred[i] = -1;
: : }
: : for(int j=1; j<num_vertices+1; j++)
: : {
: : if (color[j]==WHITE)
: : {
: : DFS_Visit(j, adj, color, pred);
: : }
: : }
: : }
: :
: : int main(int argc, char* argv[])
: : {
: : Node **adj = new Node* [num_vertices]; //holds the adjusted vertices
: : int *pred = new int[num_vertices]; //holds the predecessors of each vertex
: : int *color = new int[num_vertices]; //holds the color (status) of each vertex
: :
: : ifstream fin; // input file
: :
: : if (argc < 2)
: : {
: : cout << "Need to provide input file as command line argument..." << endl;
: : exit(1);
: : }
: :
: : fin.open(argv[1]);
: :
: : if (!fin.good())
: : {
: : cout << "Could not open " << argv[1] << " for input... " << endl;
: : exit(1);
: : }
: :
: : createGraph(fin, adj);
: : fin.close();
: : DFS(adj, color, pred);
: : cout << "The graph is acyclic...";
: : return 0;
: : }
: :
: :
: You are dynamically creating the adj, pred, and color variables based on the number of vertices expected, but you create these before you know how many vertices to expect - since this is read from the file. I would not new those at the beginning of main, but would new the adj array in createGraph and return the number of vertices so that main could then allocate pred and color appropriately. before calling DFS().
: Of course, main will have to release all of these at the end.
:
: When you read data in from the file, make sure you do not try to read more data than is expected (or the size of the allocated arrays). That is the basic problem here - you are trying to input data for which there is no location allocated. This is in regard to arrays of course. If you used a linked list, you could read in data, dynamically create a single node, add it to the list, then read the next. That way you do not depend having an accurate count as the first thing in your data file - you determine the count based on how many entries you actually read.
:
Thanks a lot for your answer.