/* Program for insertion and deletion of nodes and edges in a graph using adjacency list */
#include<stdio.h>
struct edge;
struct node
{
struct node *next;
char name;
struct edge *adj;
}*start=NULL;
struct edge
{
char dest;
struct edge *link;
};
struct node *find(char item);
main()
{
int choice;
char node,origin,destin;
while(1)
{
printf("1.Insert a node\n");
printf("2.Insert an edge\n");
printf("3.Delete a node\n");
printf("4.Delete an edge\n");
printf("5.Display\n");
printf("6.Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter a node to be inserted : ");
fflush(stdin);
scanf("%c",&node);
insert_node(node);
break;
case 2:
printf("Enter an edge to be inserted : ");
fflush(stdin);
scanf("%c %c",&origin,&destin);
insert_edge(origin,destin);
break;
case 3:
printf("Enter a node to be deleted : ");
fflush(stdin);
scanf("%c",&node);
/*This fn deletes the node from header node list*/
delete_node(node);
/* This fn deletes all edges coming to this node */
delnode_edge(node);
break;
case 4:
printf("Enter an edge to be deleted : ");
fflush(stdin);
scanf("%c %c",&origin,&destin);
del_edge(origin,destin);
break;
case 5:
display();
break;
case 6:
exit();
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
insert_node(char node_name)
{
struct node *tmp,*ptr;
tmp=malloc(sizeof(struct node));
tmp->name=node_name;
tmp->next=NULL;
tmp->adj=NULL;
if(start==NULL)
{
start=tmp;
return;
}
ptr=start;
while( ptr->next!=NULL)
ptr=ptr->next;
ptr->next=tmp;
}/*End of insert_node()*/
delete_node(char u)
{
struct node *tmp,*q;
if(start->name == u)
{
tmp=start;
start=start->next; /* first element deleted */
free(tmp);
return;
}
q=start;
while(q->next->next != NULL)
{
if(q->next->name==u) /* element deleted in between */
{
tmp=q->next;
q->next=tmp->next;
free(tmp);
return;
}
q=q->next;
}/*End of while*/
if(q->next->name==u) /* last element deleted */
{
tmp=q->next;
free(tmp);
q->next=NULL;
}
}/*End of delete_node()*/
delnode_edge(char u)
{
struct node *ptr;
struct edge *q,*start_edge,*tmp;
ptr=start;
while(ptr!=NULL)
{
/* ptr->adj points to first node of edge linked list */
if(ptr->adj->dest == u)
{
tmp=ptr->adj;
ptr->adj=ptr->adj->link; /* first element deleted */
free(tmp);
continue; /* continue searching in another edge lists */
}
q=ptr->adj;
while(q->link->link != NULL)
{
if(q->link->dest==u) /* element deleted in between */
{
tmp=q->link;
q->link=tmp->link;
free(tmp);
continue;
}
q=q->link;
}/*End of while*/
if(q->link->dest==u) /* last element deleted */
{
tmp=q->link;
free(tmp);
q->link=NULL;
}
ptr=ptr->next;
}/*End of while*/
}/*End of delnode_edge()*/
insert_edge(char u,char v)
{
struct node *locu,*locv;
struct edge *ptr,*tmp;
locu=find(u);
locv=find(v);
if(locu==NULL )
{
printf("Source node not present ,first insert node %c\n",u);
return;
}
if(locv==NULL )
{
printf("Destination node not present ,first insert node %c\n",v);
return;
}
tmp=malloc(sizeof(struct edge));
tmp->dest=v;
tmp->link=NULL;
if(locu->adj==NULL) /* item added at the begining */
{
locu->adj=tmp;
return;
}
ptr=locu->adj;
while(ptr->link!=NULL)
ptr=ptr->link;
ptr->link=tmp;
}/*End of insert_edge()*/
struct node *find(char item)
{
struct node *ptr,*loc;
ptr=start;
while(ptr!=NULL)
{
if(item==ptr->name)
{
loc=ptr;
return loc;
}
else
ptr=ptr->next;
}
loc=NULL;
return loc;
}/*End of find()*/
del_edge(char u,char v)
{
struct node *locu,*locv;
struct edge *ptr,*tmp,*q;
locu=find(u);
if(locu==NULL )
{
printf("Source node not present\n");
return;
}
if(locu->adj->dest == v)
{
tmp=locu->adj;
locu->adj=locu->adj->link; /* first element deleted */
free(tmp);
return;
}
q=locu->adj;
while(q->link->link != NULL)
{
if(q->link->dest==v) /* element deleted in between */
{
tmp=q->link;
q->link=tmp->link;
free(tmp);
return;
}
q=q->link;
}/*End of while*/
if(q->link->dest==v) /* last element deleted */
{
tmp=q->link;
free(tmp);
q->link=NULL;
return;
}
printf("This edge not present in the graph\n");
}/*End of del_edge()*/
display()
{
struct node *ptr;
struct edge *q;
ptr=start;
while(ptr!=NULL)
{
printf("%c ->",ptr->name);
q=ptr->adj;
while(q!=NULL)
{
printf(" %c",q->dest);
q=q->link;
}
printf("\n");
ptr=ptr->next;
}
}/*End of display()*/