Saturday, September 3, 2011

Orthogonal list representation of a graph


/*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