Incorrect adjacency list representation of a graph

Question

I am trying to represent a graph using the adjacency list representation of graphs. My code compiles correctly but shows incorrect result, I can't seem to find the logical inconsistency in my code. This is a sample input and output

Enter the number of Vertices 
 4

Enter the number of Edges
 6

Enter the Edges

0 1

1 2

2 3

3 0

0 2

1 3

Adjacency list of vertex 0 head -> 0-> 2

Adjacency list of vertex 1 head -> 1-> 3

Adjacency list of vertex 2 head -> 2

Adjacency list of vertex 3 head -> 3

Note here that 0 is also connected to 1

2 is also connected to 1 and 0

struct grnode {

long long num;
struct grnode *next;
};

struct graph {

long long v;
long long e;
struct grnode *adj;
};

struct graph *adjlistgr(){

long long i,x,y;
struct grnode *temp;
struct graph *g = (struct graph*)malloc(sizeof(struct graph));
if (!g) {
    printf("memory error");
    return;
}
// here we scanf  the num of vertices and edges
printf("Enter the number of Vertices \n");
scanf("%lld", &g->v);
printf("Enter the number of Edges\n");
scanf("%lld", &g->e);
g->adj = malloc(g->v*sizeof(struct grnode));
for (i = 0; i < g->v; i++)
{

    g->adj[i].num = i;
    g->adj[i].next = &g->adj[i];
}
printf("Enter the Edges\n");
for (i = 0; i < g->e;i++)
{   // now we scan the edges

    scanf("%lld %lld", &x,&y);

    temp = (struct grnode*)malloc( sizeof( struct grnode*));
    temp->num = y;
    temp->next = &g->adj[x];
    g->adj[x].next = temp;
    temp = (struct grnode*)malloc( sizeof( struct grnode*));
    temp->num = y;
    temp->next = &g->adj[y];
    g->adj[y].next = temp;
}return g;
}

 void printgraph(struct graph* graph)
{                   

int n;                         
for (n = 0; n < graph->v; ++n)               
{                                      
    // struct grnode *pCrawl = graph->adj[n].num;
    struct grnode *temp;
    temp = (struct grnode*)malloc( sizeof( struct grnode*));
    temp->next=&graph->adj[n];
    temp=temp->next;
    printf("\n Adjacency list of vertex %d\n head ", n);
    long long s=temp->num;
    do 
    {
        printf("-> %d", temp->num);
        temp = temp->next;
    }while(temp->num!=s);
    printf("\n");
}}    
  int main(){      
  struct graph *mylist=adjlistgr();          
  printgraph(mylist);    
}

Answer 1

The expression malloc( sizeof( struct grnode*)) allocates a pointer and returns to you a pointer to the allocated pointer. If you don't use this as a pointer to a pointer, like you don't, then you have undefined behavior.

I suspect you really want malloc( sizeof( struct grnode)).

By the way, in C you should not cast the result of malloc. And in C++ you should not use malloc anyway.

Answer 2

Besides the allocation issue, your data organisation needs rethinking.

You also seem to have misconceptions about malloc. For example, you allocate memory inside the printing function. That function should just inspect the data and then print it. The allocation is unnecessary. In your code, you overwrite the handle to the allocated data immediately:

temp = (struct grnode*)malloc( sizeof( struct grnode*));
temp->next=&graph->adj[n];
temp=temp->next;

That means that you lose access to the new data (and cannot free it later). That's like buying a house and throwing away the keys. It is enough to say:

temp = &graph->adj[n];

When you work with pointers, keep in mind: A pointer should point to valid data or it should be NULL. When you allocate memory, don't change the handle to that memory and make sure tofree it via that handle later.

About your graph: You have four nodes. These nodes are fixed once you initialise them. You cann add edges between them, but you cannot re-use them to do double duty as elements of what should be four independent linked lists. Which is what your code wants to do.

There are several ways to describe adjacency. You could add a matrix to your graph or you could make an edge structure that holds the two connecting nodes and that is organised by graph. Or you could make a linked list of connactions for each node. Choose one.

The main point is that you need two idependent data structures for your nodes and edges.

Edit Based on your principal idea of using linked lists to represent connections, I've implemented a simple framework for unidirectional graphs below. You can see thet each grnode maintains its own linked list of grconn connections. The code also shows how to clean up used memoy after using it.

#include <stdlib.h>
#include <stdio.h>

struct grnode;
struct grconn;

struct grconn {                 /* Connection to node (linked list) */
    struct grnode *dest;
    struct grconn *next;
};

struct grnode {                 /* Node in graph */
    int id;
    struct grconn *conn;
};

struct graph {
    int nnode;
    struct grnode *node;
};



/*
 *      Create new connection to given node
 */
struct grconn *grconn_new(struct grnode *nd)
{
    struct grconn *c = malloc(sizeof(*c));

    if (c) {
        c->dest = nd;
        c->next = NULL;
    }

    return c;
}

/*
 *      Clean up linked list of connections
 */
void grconn_delete(struct grconn *c)
{ 
    while (c) {
        struct grconn *p = c->next;

        free(c);
        c = p;
    }
}

/*
 *      Print connectivity list of a node
 */
void grnode_print(struct grnode *nd)
{
    struct grconn *c;

    printf("%d:", nd->id);

    c = nd->conn;
    while (c) {
        printf(" %d", c->dest->id);
        c = c->next;
    }

    printf("\n");
}



/*
 *      Create new graph with given number of nodes
 */
struct graph *graph_new(int n)
{
    struct graph *g = malloc(sizeof(*g));
    int i;

    if (g == NULL) return g;

    g->nnode = n;
    g->node = malloc(n * sizeof(*g->node));
    if (g->node == NULL) {
        free(g);
        return NULL;
    }

    for (i = 0; i < n; i++) {
        g->node[i].id = i;
        g->node[i].conn = NULL;
    }

    return g;
}

/*
 *      Delete graph and all dependent data
 */
void graph_delete(struct graph *g)
{
    int i;

    for (i = 0; i < g->nnode; i++) {
        grconn_delete(g->node[i].conn);
    }

    free(g->node);
    free(g);
}

/*
 *      Print connectivity of all nodes in graph
 */
void graph_print(struct graph *g)
{
    int i;

    for (i = 0; i < g->nnode; i++) {
        grnode_print(&g->node[i]);
    }
}

/*
 *      Create one-way connection from node a to node b
 */
void graph_connect(struct graph *g, int a, int b)
{
    struct grnode *nd;
    struct grconn *c;

    if (a < 0 || a >= g->nnode) return;
    if (b < 0 || b >= g->nnode) return;

    nd = &g->node[a];
    c = grconn_new(&g->node[b]);

    c->next = nd->conn;
    nd->conn = c;
}

/*
 *      Create two-way connection between nodes a and b
 */
void graph_connect_both(struct graph *g, int a, int b)
{
    graph_connect(g, a, b);
    graph_connect(g, b, a);
}



/*
 *      Example client code
 */
int main()
{
    struct graph *g = graph_new(4);

    graph_connect_both(g, 0, 1);
    graph_connect_both(g, 1, 2);
    graph_connect_both(g, 2, 3);
    graph_connect_both(g, 0, 2);
    graph_connect_both(g, 1, 3);

    graph_print(g);

    graph_delete(g);

    return 0;
}