Thanks for looking at it. Sorry, I posted in kindof a hurry and didn't really put enough to solve the problem. Also, input format does not need to be checked, just the values themselves. Also, also, when I comment out the call to addDirectedEdge it still crashes.
The program is designed to build a directed graph representation then find the strongly connected components (it builds lists of which nodes each node can get to, and searches through them to find which ones are part of a cycle) Here's the whole file:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "List.h"
#include "Graph.h"
int main(int argc, char **argv) {
ListHndl S;
GraphHndl G, GT;
FILE *in, *out;
int n, a, b, i, rents;
if(argc != 3) {
printf("Usage: %s input output", argv[0]);
exit(1);
}
in = fopen(argv[1], "r");
out = fopen(argv[2], "w");
if( in==NULL ){
printf("Unable to open file %s for reading\n", argv[1]);
exit(1);
}
if( out==NULL ){
printf("Unable to open file %s for writing\n", argv[2]);
exit(1);
}
/*build the graph*/
fscanf(in, "%d", &n);
G = NewGraph(n);
printGraph(G,stdout);
do {
printf("Start scan\n");
fscanf(in, "%d%d", &a, &b);
printf("scanned %d %d\n", a, b);
if(a!=0 && b!= 0) addDirectedEdge(G, a, b);
printf("return\n");
} while(a != 0 || b != 0);
printf("done");
for(i = 1; i<= getOrder(G); i++) {
printf("Build List");
insertAfterLast(S, i);
}
/*Run DFS*/
DFS(G, S);
GT = Transpose(G);
DFS(GT, S);
rents = 0;
for(i = 1; i<= getOrder(GT); i++) {
if(getParent(GT, i) == NULL) rents++;
}
fprintf(out, "Adjacency list representation of G:\n");
printGraph(G, out);
fprintf(out, "\n");
fprintf(out, "G contains %d strongly connected components:", rents);
moveFirst(S);
while(!offEnd(S)) {
if(getParent(GT, getCurrent(S)) == NULL)
fprintf(out, "\n%d", getCurrent(S));
else fprintf(out, " %d", getCurrent(S));
moveNext(S);
}
return 0;
}
List and Graph are implimentations we had to write for graph building. When I run my program in bcheck it gives me the error:
"signal SEGV (no mapping at the fault address) in insertAfterLast at 0x1239c
0x0001239c: insertAfterLast+0x0028: ba,a insertAfterLast+0x14410"
the function insertAfterLast is called in addDirectedEdge and uses the following code:
Code:
void addDirectedEdge(GraphHndl G, int u, int v) { /* Pre: 1<=u<=n, 1<=v<=n */
if(1 <= u && u <= getOrder(G) && 1 <= v && v <= getOrder(G)) {
insertAfterLast(G->near[u], v);
G->edges++;
printf("Edge added\n");
}
}
-------------------------------------------------------------------
void insertAfterLast(ListHndl L, ListItem data) {
ListNodeHndl newn = NewNode(data);
newn->prev = L->last;
if(L->last != NULL) L->last->next = newn;
else L->first = newn;
L->last = newn;
L->length += 1;
}
The structs being dealt with are as follows:
Code:
typedef struct Graph *GraphHndl;
struct Graph {
int n;
int edges;
char **color;
ListHndl *near;
int *parent;
int *disc;
int *fin;
};
---------------------------------------------
typedef struct ListNode *ListNodeHndl;
struct ListNode {
ListItem item;
ListNodeHndl prev;
ListNodeHndl next;
};
struct List {
int length;
ListNodeHndl first;
ListNodeHndl last;
ListNodeHndl curr;
};
the List implimentation was used in a previous program and as far as I know works w/o any problems.
and some constructors, too:
Code:
GraphHndl NewGraph(int n) {
int i;
printf("New Graph %d\n", n);
GraphHndl G = malloc(sizeof(struct Graph));
G->n = n;
G->edges = 0;
G->color = (char**)malloc(sizeof(char)*5*(n+1));
G->near = (ListHndl*)malloc((n+1)*sizeof(ListHndl));
G->parent = (int*)malloc(sizeof(int) * (n+1));
G->disc = (int*)malloc(sizeof(int) * (n+1));
G->fin = (int*)malloc(sizeof(int) * (n+1));
for(i = 1; i <= n; i++) {
G->color[i] = "white";
G->near[i] = New_List();
G->parent[i] = NULL;
G->disc[i] = NULL;
G->fin[i] = NULL;
}
printf("Graph done\n");
return G;
}
----------------------------------------------------------------------
ListHndl New_List(void){
ListHndl new = malloc(sizeof (struct List));
new->length = 0;
new->first = NULL;
new->last = NULL;
new->curr = NULL;
return new;
}