Help Please...! - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Help Please...!

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;
}


Sign In or Register to comment.