graph implementation with adjacency lists in C

Question

I just started learning C and as a self-learning excercise, I am implementing data structures and algos in C. Right now I am working on a graph and this is the data structure representation of it.

typedef int graphElementT;
typedef struct graphCDT *graphADT;

typedef struct vertexTag
{
    graphElementT element;
    int visited;
    struct edgeTag *edges;
    struct vertexTag *next; 
} vertexT;

typedef struct edgeTag
{
    int weight;
    vertexT *connectsTo;
    struct edgeTag *next;
} edgeT;

typedef struct graphCDT
{
    vertexT *vertices;
} graphCDT;

To this graph I added a addVertex function.

int addVertex(graphADT graph, graphElementT value)
{
    vertexT *new = malloc(sizeof(*new));

    vertexT *vert;
    new->element = value;
    new->visited = 0;
    new->edges = NULL;
    new->next = NULL;

    int i = 0;

    for(vert=graph->vertices; vert->next != NULL; vert=vert->next)
    {
        if(vert->element == value)
        {
            printf("already exists\n");
            return 0;
        }
    }   

    vert->next = new;

    //free(new);
    printf("\ninserted %d\n", vert->element);   

    return 1;       
}

This works fine except for three things.

if the newly added vertex is the same as the last vertex in the list, it fails to see it. To prevent this i changed the for loop limiting condition to vert != NULL, but that gives a seg fault.
if i try to free the temporarily allocated pointer, it resets the memory pointer by the pointer and this adds an infinite loop at the end of the vertex list. Is there no way to free the pointer without writing over the memory it points to? Or is it not really needed to free the pointer?
Also would destroying the graph mean destroying every edge and vertices? or is there a better approach?

Also if this data structure for graph is not a good one and there are better implementations, i would appreciate that being pointed out.

int addVertex(graphADT graph - did you mean graphCDT here? — kotlomoy
– kotlomoy, Commented Jun 1, 2013 at 21:37
for(vert=graph->vertices; vert->next - make sure graph->vertices is not NULL before using it. vert->element == value - you didn't provide graphElementT implementation, so it's hard to say what's happening here. printf("\ninserted %d\n", vert->element); - you print wrong vertex here, should be new->element — kotlomoy
– kotlomoy, Commented Jun 1, 2013 at 21:38
also, avoid using new as identifier because it's keyword in C++ — kotlomoy
– kotlomoy, Commented Jun 1, 2013 at 21:41
Oh my bad I had a typedef graphCDT *graphADT; typedef char graphElementT. Also I do know it is a keyword in c++ but does it really matter in C? — Anurag Ramdasan
– Anurag Ramdasan, Commented Jun 2, 2013 at 5:16
It does matter if there's posibility of converting your project to C++ in future. Otherwise it's just bad style. — kotlomoy
– kotlomoy, Commented Jun 2, 2013 at 9:38

Spandan · Accepted Answer · 2013-06-02 08:12:56Z

1

If you change the limiting condition to vert!=NULL , and if the loop ends with vert==NULL ,i.e. ,the vertex to be added isn't present , then you will be reading next statement :

vert->next = new;

That means you are accesing the NULL ,vert pointer , hence the seg fault .

Now to allow checking if the last element isn't the vertex to be added ,and also to prevent seg fault ,do this :

for(vert=graph->vertices; vert->next != NULL; vert=vert->next)
{
    if(vert->element == value)
    {
        printf("already exists\n");
        return 0;
    }
}   

if(vert->element == value)
    {
        printf("already exists\n");
        return 0;
    }

vert->next = new;

2

The temporary "new" pointer is the memory location allocated to the Vertex you added .IT IS NOT to be freed ,as freeing it will mean that you deleted the vertex you just added :O .

3

Yes , detroying the graph essentialy means the same .

It is always a good practice to implement linked list as a adjacency list implementation of graph .Although you can always use a c++ "2 D Vector" to implement the same .

VAT69 · Accepted Answer · 2013-06-02 09:25:08Z

Here's a working addVertex function that you can use. I am keeping the original declarations as it is. I have added a main () to which you can give command line arguments to test.

int addVertex(graphADT graph, graphElementT value)
{
   vertexT *tmpvert , *vert ;
   vert=graph->vertices ;
  /*check to see whether we really need to create a new vertex*/
   tmpvert = vert;
     while(tmpvert != NULL)
     {
       /* U can put a debug printf here to check what's there in graph:
        *  printf("tmpvert->elem=%d   ", tmpvert->element);
        */
        vert = tmpvert;
        if(tmpvert->element == value)
             return 0;
        tmpvert=tmpvert->next ;
    }
   /*If we are here , then we HAVE to allocate memory and add to our graph.*/
   tmpvert = (vertexT*)malloc(sizeof(vertexT));
   if ( NULL == tmpvert )
        return 0; /* malloc failure */
   tmpvert->element = value;
   tmpvert->visited = 0;
   tmpvert->edges = NULL;
   tmpvert->next = NULL;

   if ( NULL == vert )
        graph->vertices = tmpvert; /*Notice that I dont use virt=tmpvert */
   else
        vert->next = tmpvert; /*putting stuff in next is fine */

    return 1;
/* Dont try printing vert->element here ..vert will be NULL first time */
/*return code for success is normally 0 others are error.
 *That way you can have your printfs and error code
 *handling outside this function.But its ok for a test code here */
}

Now for the main () snippet for testing :

int main (int argc , char* argv[]) {
        graphADT graph ;
        graph =(graphADT) malloc ( sizeof(struct graphCDT) );
        graph->vertices = NULL;
        while ( --argc >0)
        {
                int value = atoi(argv[argc]);
                addVertex(graph,value);
        }
}

Collectives™ on Stack Overflow

graph implementation with adjacency lists in C

2 Answers 2

1

2

3

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1

2

3

1 Comment

Comments

Related