ad_del_a.c

Graph Programs in C

/* Program for addition and deletion of nodes and edges in a graph
   using adjacency matrix */
#include<stdio.h>
#define max 20
int adj[max][max];
int n;
main()
{
	int choice;
	int node,origin,destin;

	create_graph();
	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.Dispaly\n");
		printf("6.Exit\n");
		printf("Enter your choice : ");
		scanf("%d",&choice);

		switch(choice)
		{
		 case 1:
			insert_node();
			break;
		 case 2:
			printf("Enter an edge to be inserted : ");
			fflush(stdin);
			scanf("%d %d",&origin,&destin);
			insert_edge(origin,destin);
			break;
		 case 3:
			printf("Enter a node to be deleted : ");
			fflush(stdin);
			scanf("%d",&node);
			delete_node(node);
			break;
		 case 4:
			printf("Enter an edge to be deleted : ");
			fflush(stdin);
			scanf("%d %d",&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()*/

create_graph()
{
	int i,max_edges,origin,destin;

	printf("Enter number of nodes : ");
	scanf("%d",&n);
	max_edges=n*(n-1); /* Taking directed graph */

	for(i=1;i<=max_edges;i++)
	{
		printf("Enter edge %d( 0 0 ) to quit : ",i);
		scanf("%d %d",&origin,&destin);
		if((origin==0) && (destin==0))
			break;
		if( origin > n || destin > n || origin<=0 || destin<=0)
		{
			printf("Invalid edge!\n");
			i--;
		}
		else
			adj[origin][destin]=1;
	}/*End of for*/
}/*End of create_graph()*/

display()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj[i][j]);
		printf("\n");
	}
}/*End of display()*/

insert_node()
{
	int i;
	n++;    /*Increase number of nodes in the graph*/
	printf("The inserted node is %d \n",n);
	for(i=1;i<=n;i++)
	{
		adj[i][n]=0;
		adj[n][i]=0;
	}
}/*End of insert_node()*/

delete_node(char u)
{
	int i,j;
	if(n==0)
	{
		printf("Graph is empty\n");
		return;
	}
	if( u>n )
	{
		printf("This node is not present in the graph\n");
		return;
	}
	for(i=u;i<=n-1;i++)
	   for(j=1;j<=n;j++)
	   {
		adj[j][i]=adj[j][i+1];  /* Shift columns left */
		adj[i][j]=adj[i+1][j];  /* Shift rows up */
	   }
	n--; /*Decrease the number of nodes in the graph */
}/*End of delete_node*/

insert_edge(char u,char v)
{
	if(u > n)
	{
		printf("Source node does not exist\n");
		return;
	}
	if(v > n)
	{
		printf("Destination node does not exist\n");
		return;
	}
	adj[u][v]=1;
}/*End of insert_edge()*/

del_edge(char u,char v)
{
     if(u>n || v>n || adj[u][v]==0)
     {
	printf("This edge does not exist\n");
	return;
     }
     adj[u][v]=0;
}/*End of del_edge()*/