/*Orthogonal list representation of a graph */
#include <stdio.h>
#include<stdlib.h>
typedef struct node
{
int u,v;
struct node *next,*down;
}node;
node *rows[10],*cols[10];
int nodecount=0;
void insert(node *p)
{
//address of the node to be inserted is in p
node *q;
//insert the node pointed by p in the linked list of the row
q=rows[p->u];//head of the linked list for the row to be used for insertion
if(q==NULL || p->u < q->u)//first node
{
p->next=q;
rows[p->u]=p;
}
else
{
//Locate the point of insertion
while(q->next != NULL && p->u > q->next->u)
q=q->next;
p->next=q->next;
q->next=p;
}
//insert the node pointed by p in the linked list of the column
q=cols[p->v];//head of the linked list for the column to be used for insertion
if(q==NULL || p->v < q->v)//first node
{
p->down=q;
cols[p->v]=p;
}
else
{
//Locate the point of insertion
while(q->down != NULL && p->v > q->down->v)
q=q->down;
p->down=q->down;
q->down=p;
}
}
int main()
{
int edgecount=0,i,j,k;
node *p;
printf("\nEnter No of vertices : ");
scanf("%d",&nodecount);
for(i=0;i<nodecount;i++)
rows[i]=cols[i]=NULL;
printf("\nEnter No. of edges : ");
scanf("%d",&edgecount);
printf("\nEnter edges as (u,v) pair : ");
for(i=0;i<edgecount;i++)
{ fflush(stdin);
p=(node*)malloc(sizeof(node));
scanf("%d%d",&p->u,&p->v);
p->next=p->down=NULL;
insert(p);
}
//display the list
printf("\nList(Row-wise):");
for(i=0;i<nodecount;i++)
{
printf("\nRow=%d",i);
for(p=rows[i];p!=NULL;p=p->next)
printf(" (%d,%d)",p->u,p->v);
}
printf("\n\nList(Column-wise):");
for(i=0;i<nodecount;i++)
{
printf("\nColumn=%d",i);
for(p=cols[i];p!=NULL;p=p->down)
printf(" (%d,%d)",p->u,p->v);
}
return(0);
}
No comments:
Post a Comment