Unable to allocate memory for a new node in my c implementation of graph

Question

I'm implementing a graph in C, here is my program:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
typedef  struct EdgeNode{
     int adjvex;
     struct EdgeNode *nextarc;
 }ENode, *PENode;
typedef struct VertexNode{
     char *data; 
     ENode *firstarc; 
 }VNode;

typedef  struct MyGraph{
     VNode vertices[INT_MAX];

}Graph;

static int get_pos(Graph g, char* name, int num_ver){
    int i;
    for (i = 0; i < num_ver; i++){
        if(strcmp(g.vertices[i].data,name) == 0)
            return i;
    }
    return -1;
}


void add_node(ENode *mylist, ENode *newEdge){
    ENode *p = mylist;
    while(p->nextarc)
        p = p->nextarc;
    p->nextarc = newEdge;
}

void DFS(Graph G, int first_node, int* visited){
    ENode *new_edge;
    visited[first_node] = 1;
    new_edge = G.vertices[first_node].firstarc;
    while (new_edge != NULL){
        if (!visited[new_edge->adjvex])
            DFS(G, new_edge->adjvex, visited);
        new_edge = new_edge -> nextarc;
    }
}

static int dfs_traverse(Graph G, int first_node, int second_node, int number_of_nodes){
    int visited[INT_MAX];
    int i;
    for (i = 0; i < number_of_nodes; i++){
        visited[i] = 0;
    }
    DFS(G, first_node, visited);
    if (visited[second_node] == 1){
        return 1;
    }else{
        return 0;
    }

}


void print_graph(Graph G, int num_vertex)
{
    int i;
    ENode *node;

    printf("List Graph:\n");
    for (i = 0; i < num_vertex; i++)
    {
        printf("%d(%s): ", i, G.vertices[i].data);
        node = G.vertices[i].firstarc;
        while (node != NULL)
        {
            printf("%d(%s) ", node->adjvex, G.vertices[node->adjvex].data);
            node = node->nextarc;
        }
        printf("\n");
    }
}




int main (){                                                                                        
    size_t sz1;
    char *line = NULL;
    //char line[1024];
    char make_nodes[] = "@n";
    char make_edges[] = "@e";
    char check_edges[] = "@q";
    static int  i = 0;
    int  index_1, index_2;
    int  dfs_1, dfs_2;
    int  pathExists;
    ENode* Edge1;

    Graph* pGraph = malloc(sizeof(Graph));
    if (pGraph == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(1);
    }


    while(getline(&line, &sz1, stdin) > 0){
    char cmd[3],n1[65],n2[65],dummy[2];
    int num_args;
    num_args = sscanf(line,"%3s%64s%64s%2s",cmd,n1,n2,dummy);
        if (strcmp(cmd,make_nodes) == 0){
      if(num_args != 2){
        printf("error\n");
      }else{
        pGraph->vertices[i].data = strdup(n1);
        pGraph->vertices[i].firstarc = NULL;
        i++;
        printf("the node is %s\n",pGraph->vertices[i].data);
      }
    }if (strcmp(cmd,make_edges) == 0){
      if (num_args != 3){
        printf("error\n");
      }else{
        index_1 = get_pos(*pGraph, n1, i);
        index_2 = get_pos(*pGraph, n2, i);
        Edge1 = (ENode*)malloc(sizeof(ENode));
        Edge1 -> adjvex = index_2;
        if (pGraph -> vertices[index_1].firstarc == NULL)
          pGraph -> vertices[index_1].firstarc = Edge1;
        else{
          add_node(pGraph->vertices[index_1].firstarc, Edge1);
        }


      }
    }



  }
    print_graph(*pGraph,i);

     return 0;
}

While the program should be working as follows:

@n [somenode]  for adding a new node
@e [somenode] [somenode] for adding a new edge
@q [somenode] [somenode] for testing the connection between two nodes

Which should be like:

@n first
@n second
@e first second
@q first second
1 //which means first and second is connected

However, given all those information, my program crash, when I use valgrind, it simply returns the message:

==7758== Memcheck, a memory error detector
==7758== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==7758== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==7758== Command: ./reach
==7758== 
Unable to allocate memory for new node
==7758== 
==7758== HEAP SUMMARY:
==7758==     in use at exit: 0 bytes in 0 blocks
==7758==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==7758== 
==7758== All heap blocks were freed -- no leaks are possible
==7758== 
==7758== For counts of detected and suppressed errors, rerun with: -v
==7758== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

If I just test by reading from stdin, it works like that:

@n first
the node is (null)
@n second
the node is (null)
@e first second 
Segmentation fault (core dumped)
@q first second
Segmentation fault (core dumped)

I don't know if there's sufficient information for that, but anyone has ideas what may have happended?

Answer 1

You are trying to allocate memory for a Graph:

typedef  struct MyGraph{
     VNode vertices[INT_MAX];
} Graph;

INT_MAX is probably quite a large number, something like 2,147,483,647, and each VNode contains two pointers. If you have a hope of allocating that structure, it will be because pointers on your system are eight bytes, so you are trying to allocate 32 GB.

If you don't have 32 GB, that might well explain why you can't allocate the memory. Some systems will let you allocate more memory than you have -- as long as you don't actually intend to use it -- but I think valgrind's malloc is not so generous.

Perhaps you should try allocating a graph of a more manageable size.

Also, this attempt to stack-allocate a huge vector:

int visited[INT_MAX];

will certainly overflow your stack, which is likely to be no more than 8 megabytes, far less than the 8 gigabytes you are attempting to allocate.

Overflowing the stack with an automatic object is undefined behaviour; segfaults are likely since the runtime will not verify that you didn't overrun the stack.