ADJACENCY LIST
(Representation of Graph through Adjacency LIST )
Implemented using C Language
ADJLIST.H
/* Name : Adjlist.h
Purpose : This files defines node structure and all basic Graph opearations
Operations :
Graph * GetGraph(void);
void InsNode(Graph *g, int v);
NodeEdge * FindNode(Graph *g, int v);
void InsEdge(Graph *g, int v, int x);
void print(Graph *s);
void DelEdge(Graph *g, int v, int x);
void DelNode(Graph *g, int v);
void PrintEdge(Graph *g, int v);
void BreadthFirst(Graph *g,int v,int w);
void DepthFirst(Graph *g,char v); */
#include "stack.h"
#include <string.h>
typedef union nodeedge {
struct node {
char info; //Node name or number
int status; //Status of node, status will be 1-Ready State,
//2-Waiting State and 3-Processed State
union nodeedge * nextnode;
union nodeedge * edgeptr;
}Node;
struct edge {
union nodeedge * nextedge;
union nodeedge * nodeptr;
}Edge;
}NodeEdge;
typedef struct {
union nodeedge * start;
}Graph;
Graph * GetGraph(void)
{
Graph *s;
s=(Graph *)malloc(sizeof(Graph));
s->start=NULL;
return s;
}
// operations on Graph
//Inserting a new node in the Graph
void InsNode(Graph *g, char v)
{
NodeEdge *new1;
new1=(NodeEdge *)malloc(sizeof(NodeEdge));
new1->Node.info=v;
new1->Node.nextnode=g->start;
new1->Node.edgeptr=NULL;
new1->Node.status=1; //Initially status of all the nodes
//will be 1
g->start=new1;
}
//Finding a node in the graph
NodeEdge * FindNode(Graph *g, char v)
{
NodeEdge *temp;
temp=g->start;
// printf("Testing(Inside find node): %c\n",v);
// printf("\nTesting(Inside find node): %c %c\n",v,temp->Node.info);
while(temp)
{
if(temp->Node.info==v)
break;
else
temp=temp->Node.nextnode;
}
return temp;
}
//Adding an edge in the graph
void InsEdge(Graph *g, char v, char x)
{
NodeEdge *newedge, *start, *end;
newedge=(NodeEdge *)malloc(sizeof(NodeEdge));
start=FindNode(g,v);
if(start==NULL)
{
printf("Starting Node %c does not exist\n",v);
exit(1);
}
end=FindNode(g,x);
if(end==NULL)
{
printf("Ending Node %c does not exist\n",x);
exit(1);
}
newedge->Edge.nextedge=start->Node.edgeptr;
start->Node.edgeptr=newedge;
newedge->Edge.nodeptr=end;
}
//Deleting an edge from the graph
void DelEdge(Graph *g, char v, char x)
{
NodeEdge *start, *end, *q, *q1;
start=FindNode(g,v);
if(start==NULL)
{
printf("Starting Node %c does not exist\n",v);
exit(1);
}
if(start->Node.edgeptr)
{
printf("This node does not have any edge\n");
exit(1);
}
end=FindNode(g,x);
if(end==NULL)
{
printf("Ending Node %c does not exist\n",x);
exit(1);
}
q=start->Node.edgeptr;
while(q)
{
if(q->Edge.nodeptr==end)
break;
else
{
q1=q;
q=q->Edge.nextedge;
}
}
if(q==start->Node.edgeptr && q->Edge.nodeptr==end)
{
start->Node.edgeptr=q->Edge.nextedge;
free(q);
}
else
{
if(q) //if edge exist only then
{
q1->Edge.nextedge=q->Edge.nextedge;
free(q);
}
}
}
//Deleting a node
void DelNode(Graph *g, char v)
{
NodeEdge *start, *del, *q;
del=g->start;
start=FindNode(g,v);
if(start==NULL)
{
printf("Node %c does not exist\n",v);
exit(1);
}
while(del) //deleting all the edges pointing to this node if any
{
DelEdge(g,del->Node.info, v);
del=del->Node.nextnode;
}
del=g->start;
while(del)
{
if(del->Node.nextnode==start)
{
del->Node.nextnode=start->Node.nextnode;
free(start);
break;
}
del=del->Node.nextnode;
}
}
//printing all the edges of the node
void PrintEdge(Graph *g, char v)
{
NodeEdge *q,*q1,*q2;
q=FindNode(g,v);
if(q==NULL)
{
printf("Node %c does not exist\n",v);
exit(1);
}
printf("----All the edges starting from %c are--->\n",v);
if(q->Node.edgeptr==NULL)
{
printf("This Node does not have any edge\n");
return;
}
else
{
q1=q->Node.edgeptr;
while(q1)
{
q2=q1->Edge.nodeptr;
printf("To Node: %c\n", q2->Node.info);
q1=q1->Edge.nextedge;
}
}
}
//printing the graph
void print(Graph *g)
{
NodeEdge *t;
t=g->start;
while(t)
{
PrintEdge(g,t->Node.info); //printing all the edges of current node
t=t->Node.nextnode;
fflush(stdin);
getchar();
}
}
//Breadth first algorithm---------------
void BreadthFirst(Graph *g,char v,char w)
{
NodeEdge *start,*end,*q,*p;
char c;
int front,rear;
int flag=0;
char *queue,*orig;
//char *path;
void detpath(char *a,char *b,int c,char d);
start=FindNode(g,v);
if(start==NULL)
{
printf("Starting Node %c does not exist\n",v);
exit(1);
}
end=FindNode(g,w);
if(end==NULL)
{
printf("Ending Node %c does not exist\n",w);
exit(1);
}
//put starting node in Queue and Change its Status to 2
front=0; //initially queue is empty
queue[front]=start->Node.info;
orig[front]=' ';
start->Node.status=2;
rear=1;
while(front<=rear)
{
//remove top node of queue and change its status to 3
c=queue[front];
q=FindNode(g,c);
q->Node.status=3;
//add to queue all the neighbors of current node whose status is 1
p=q->Node.edgeptr;
while(p)
{
if(p->Edge.nodeptr->Node.status==1)
{
queue[rear]=p->Edge.nodeptr->Node.info;
orig[rear]=q->Node.info;
p->Edge.nodeptr->Node.status=2;
if(queue[rear]==w) //if target node is found then quit
{
queue[rear+1]='\0';
orig[rear+1]='\0';
flag=1;
break;
}
rear++;
}
p=p->Edge.nextedge;
}
//-------------------------------------------------------------
if(flag)
{
printf("Queue is : %s\n",queue);
printf("Originating: %s\n",orig);
break;
}
front++;
}
//determining path
detpath(queue,orig,rear,v);
}
//Finding the position of a info
int find(char *arr,char c)
{
int i;
for(i=0;i<strlen(arr);i++)
{
if(arr[i]==c)
return i;
}
return -1;
}
//determining the path-------------------------
void detpath(char *q,char *o,int r,char st)
{
char *path;
int f;
char c;
f=0;
c=o[r];
path[f++]=q[r];
// printf("test: %x %x %x\n",q,o,path);
while(r>=0 && c!=st)
{
path[f++]=c;
r=find(q,c);
/* printf("here1:%s %s\n",q,o);
printf("here2:%d %c %c %c\n",r,c,o[r],o[3]);*/
c=o[r];
}
path[f]=c;
//displaying path
while(f>=0)
{
printf(" -> %c",path[f]);
f--;
}
fflush(stdin);
getchar();
}
//Depth first algorithm---------------
void DepthFirst(Graph *g,char v)
{
NodeEdge *start,*q,*p;
char c;
Stack *s;
s=GetStack();
start=FindNode(g,v);
if(start==NULL)
{
printf("Node %c does not exist\n",v);
exit(1);
}
//push starting node in Stack and Change its Status to 2
//initially stack is empty
start->Node.status=2;
push(s, start->Node.info);
while(!empty(s))
{
//pop top node of stack and change its status to 3
c=pop(s);
q=FindNode(g,c);
printf("%c ",q->Node.info);
q->Node.status=3;
//push to stack all the neighbors of current node whose status is 1
p=q->Node.edgeptr;
while(p)
{
if(p->Edge.nodeptr->Node.status==1)
{
push(s, p->Edge.nodeptr->Node.info);
p->Edge.nodeptr->Node.status=2;
}
p=p->Edge.nextedge;
}
//-------------------------------------------------------------
}
fflush(stdin);
getchar();
}
ADJLIST.CPP
/* Name : AdjList.cpp
Purpose: Linked representation of a Graph */
#include <conio.h>
#include "adjlist.h"
void main()
{
int menu(void);
Graph *g;
char c,start,end,info;
/* char tNode[]="KJGFEDCBA";
char sNode[]="ABCDEFGJK";
char eNode[9][4]={"BCF","CG","F","C","JCD","D","EC","KD","GE"};
int i,j; */
clrscr();
g=GetGraph();
while(1)
{
c=menu();
if(c==8)
break;
switch(c) {
case 1:
printf("Enter Node Number: ");
fflush(stdin);
scanf("%c", &info);
//for(i=0;i<9;i++)
//InsNode(g,tNode[i]);
InsNode(g,info);
break;
case 2:
printf("Enter Node Number: ");
fflush(stdin);
scanf("%c", &info);
DelNode(g,info);
break;
case 3:
printf("Enter starting Node: ");
fflush(stdin);
scanf("%c", &start);
printf("Enter ending Node: ");
fflush(stdin);
scanf("%c", &end);
InsEdge(g,start,end);
// }
// }
break;
case 4:
printf("Enter starting Node: ");
fflush(stdin);
scanf("%c", &start);
printf("Enter ending Node: ");
fflush(stdin);
scanf("%c", &end);
DelEdge(g,start,end);
break;
case 5:
print(g);
break;
case 6:
printf("Enter starting Node: ");
fflush(stdin);
scanf("%c", &start);
printf("Enter ending Node: ");
fflush(stdin);
scanf("%c", &end);
BreadthFirst(g,start,end);
break;
case 7:
printf("Enter Node: ");
fflush(stdin);
scanf("%c", &start);
DepthFirst(g,start);
break;
}
}
}
int menu(void)
{
int ch;
while(1)
{
printf("1. Inserting a Node\n");
printf("2. Deleting a Node\n");
printf("3. Inserting an Edge\n");
printf("4. Deleting an Edge\n");
printf("5. Printing the Graph\n");
printf("6. Breadth First Search\n");
printf("7. Depth First Search\n");
printf("8. Quit\n");
printf("Enter the choice: ");
scanf("%d", &ch);
if(ch<1 || ch > 8)
printf("Invalid choice\n");
else
return ch;
}
}
No comments:
Post a Comment