Friday, November 6, 2015

Graph implementation using adjacency list

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int key;
    struct node * next;
}node;
typedef struct list
{
    struct node * head;
}list;
typedef struct GRAPH
{
    int V;
    struct list * array;
}GRAPH;
node * newnode(int k)
{
    node *n=(node *)malloc(1*sizeof(node));
    n->key=k;
    return n;
}
GRAPH *newgraph(GRAPH * g,int v)
{   g=(GRAPH *)malloc(sizeof(GRAPH));
    g->V=v;int i;
    g->array=(list *)malloc(v*sizeof(g->array));
    for(i=0;i<v;i++)
         g->array[i].head=NULL;
    return g;
}
void add_edge(GRAPH * g,int s , int t)
{
    node *n=newnode(t);
    n->next=g->array[s].head;
    g->array[s].head=n;
    node *n2=newnode(s);
    n2->next=g->array[t].head;
    g->array[t].head=n2;
}

void delete_edge(GRAPH * g,int s , int t)
{
     if(g->array[s].head==NULL){printf("There is no edge between %d and %d \n", s , t);return;}
    node * ptr1=g->array[s].head;
    if(ptr1->next==NULL)
        {if(ptr1->key==t){free(ptr1);ptr1=NULL;}return;}
    if(ptr1->key==t)
    {  g->array[s].head=ptr1->next;free(ptr1);return;}

    node * ptr2=g->array[s].head->next;

    while(ptr2!=NULL)
    {
        if(ptr2->key!=t)
          {
            ptr1=ptr2;
            ptr2=ptr2->next;
           }
          else break;

    }
   if(ptr2!=NULL)
    {
      if(ptr2->key==t)
        {ptr1->next=ptr2->next;
        free(ptr2);
        }
      else printf("There is no edge between %d and %d \n", s , t);
    }
    else
         printf("There is no edge between %d and %d \n", s , t);

}
void printgraph(GRAPH *g)
{
    int v,i;
    v=g->V;
    for(i=0;i<v;i++)
        {   node * ptr=g->array[i].head;            printf("%d->",i);

            while(ptr!=NULL)
            {
                printf("%d->",ptr->key);
                ptr=ptr->next;
            }
            printf("\n");
        }
}
void remove_edge(GRAPH *graph ,int a , int b)
{   printf("deleting edge %d-%d \n",a,b);
    delete_edge(graph,a,b);delete_edge(graph,b,a);

}
int main()
{   int size=5;
    GRAPH *graph=newgraph(graph,size);
    add_edge(graph,0,1);add_edge(graph,0,2);add_edge(graph,0,4);
    add_edge(graph,1,4);add_edge(graph,1,2);add_edge(graph,1,3);
    add_edge(graph,2,3);add_edge(graph,2,4);
    add_edge(graph,3,4);
    printgraph(graph);
    remove_edge(graph,2,3);
    remove_edge(graph,1,4);
    remove_edge(graph,1,3);


           printgraph(graph);
    printf("success\n");
return 0;
}