My Program is about Directed Graphs. It reads a list of edges like : 25 589 , and puts 589 into the adjacency list (a linked list) of 25. My input file has about 5 Million such v w edges, with about 800K nodes/vertices, for each of which there will be a linked list(adjacency list) containing edges going outward from that node.
My program wants to read this one edge per line input file, and create a adjacency list view of the graph.
So if the ip file be like :
25 589
27 881
4689 36
25 77489
then the output should be something like :
25 | 589 77489
27 | 881
4689 | 36
Now my program works for smaller inputs. But the above big file crashes my program at about 4.6 Million edge mark. I tried catching calls to malloc() and calloc() , to see if heap space is filled up, but perror() doesnt say anything , even though the program keeps crashing.
Below is the header file and the source file :
/*
* Bag.h
*
* Created on: 14-Feb-2015
* Author: Somjit
*/
#ifndef WEEK4_BAG_H_
#define WEEK4_BAG_H_
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct node{
long item;
void *next;
}node;
typedef struct Bag{
long size;
node *first;
}Bag;
Bag *new_Bag(){
Bag *b = malloc(sizeof(Bag));
if(b==NULL){
perror("malloc fail 2");
exit(EXIT_FAILURE);
}
b->size = 0;
b->first = NULL;
return b;
}
void add_node(Bag *bag,long item){
node *old = bag->first;
//create a new node
node *first = malloc(sizeof(node));
if(first==NULL){
perror("malloc fail 3");
exit(EXIT_FAILURE);
}
first->item = item;
first->next = old;
bag->first = first;
bag->size++;
}
bool bag_empty(Bag bag){
return bag.size <= 0;
}
#endif /* WEEK4_BAG_H_ */
/*
* DiGraph.c
*
* Created on: 14-Feb-2015
* Author: Somjit
*/
#include "Bag.h"
#define NUMOFNODES 739455L
typedef struct digraph{
long vertices;
long edges;
Bag **adj;
}digraph;
digraph *new_digraph(long num_of_vertices){
digraph *dg = malloc(sizeof(digraph));
if(dg==NULL){
perror("malloc fail 1");
exit(EXIT_FAILURE);
}
dg->vertices = num_of_vertices;
dg->edges = 0;
// create a bag for each vertices
dg->adj = calloc(num_of_vertices,sizeof(Bag*));
if(dg->adj==NULL){
perror("calloc fail 1");
exit(EXIT_FAILURE);
}
for(long i = 0 ; i < num_of_vertices ; i++){
dg->adj[i] = new_Bag();
}
puts("digraph created");
return dg;
}
void addEdge(digraph *dg, long v, long w){
add_node(dg->adj[v], w);
dg->edges++;
}
void displayGraph(digraph *dg,FILE *f){
//loop through the nodes
for(long i = 0; i < dg->vertices ; i++){
//looping through the bag/adj list of each node
Bag *thisBag = dg->adj[i];
fprintf(f," %7ld > ",i);
for(node *k = thisBag->first; k!= NULL ; k = k->next){
fprintf(f,"%7ld ",k->item);
}
fprintf(f,"\n");
}
}
long main(void){
FILE *f = fopen("ip.txt","r");
FILE *out = fopen("op.txt","w");
if(f==NULL){
perror("file not found");
exit(EXIT_FAILURE);
}
digraph *dg = new_digraph(NUMOFNODES);
char buf[20];
long num=0, v=0, w=0;
while(fgets(buf,19,f)!=NULL){
sscanf(buf,"%ld %ld",&v,&w);
// printf("adding : %ld > %ld\n",v,w);
addEdge(dg,v,w);
if(dg->edges%10000 == 0) printf("\ndg->edges : %d\n",dg->edges);
// printf("graphs edges : %ld\n",dg->edges);
}
printf("\ndigraph stats : %ld nodes, %ld edges\n\n",dg->vertices,dg->edges);
puts("adj list view of above digraph :");
displayGraph(dg,out);
fclose(f);
fclose(out);
printf("all done");
}