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

Edited 1 Year Ago by somjit{}

Apparantly,i had put the vertex count wrong. That led to a null pointer exception.. and a crash. Needed to code the whole thing in java to realise this. Code works perfectly :)

This question has already been answered. Start a new discussion instead.