src/conv-ldb/edgelist.C

   1 /* The data structure/ ADT for the edge-list */
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include "graphdefs.h"
   5
   6 /*extern VerticesListType graph; */
   7
   8 CMI_EXTERNC
   9 EdgeListType * InitEdgeList(int E)
  10 {
  11   EdgeListType * edgesRec;
  12
  13   edgesRec = (EdgeListType *) malloc(sizeof(EdgeListType));
  14   _MEMCHECK(edgesRec);
  15   edgesRec->next = 0;
  16   edgesRec->edges = (Edge *) malloc(E*sizeof(Edge));
  17   _MEMCHECK(edgesRec->edges);
  18   return(edgesRec);
  19 }
  20
  21 void addEdge(VerticesListType *graph, EdgeListType * EdgeList, int v, int w)
  22 {
  23   int n, index;
  24   n = EdgeList->next;
  25   EdgeList->next++;
  26
  27   /* printf("adding edge: (%d, %d)\n", v, w); */
  28   ((EdgeList->edges)[n]).node1 = v;
  29   (EdgeList->edges[n]).node2 = w;
  30    index =  graph->vertexArray[v].next++;
  31    graph->adjArray[ index ] = w;
  32    index =  graph->vertexArray[w].next++;
  33    graph->adjArray[ index ] = v;
  34
  35    graph->vertexArray[v].degree++;
  36    graph->vertexArray[w].degree++;
  37 }
  38
  39 void printEdges(EdgeListType *EdgeList)
  40 {
  41  int i;
  42  Edge * edges;
  43  edges = EdgeList->edges;
  44  for (i=0; i< (EdgeList->next ); i++)
  45    {printf("%d\t%d\n", edges[i].node1, edges[i].node2);
  46   }
  47 }
  48
  49 int edgeExists(VerticesListType *graph, int x, int y)
  50 {
  51   int i, ind;
  52   ind = graph->vertexArray[x].adjListInd;
  53
  54   for(i=0; i< graph->vertexArray[x].degree; i++)
  55     { if (graph->adjArray[ind + i] == y) return 1;}
  56
  57   return 0;
  58 }
  59
  60 /*
  61   If we are adding an edge between two nodes already connected then we
  62   need special changes. We open some distinct edge say x,y and
  63   connect v with y and x with w
  64 */
  65
  66 void addspEdge(VerticesListType *graph, EdgeListType * EdgeList, int v, int w)
  67 {
  68   int n, index,i,x,y,ind;
  69   n = EdgeList->next;
  70   EdgeList->next++;
  71
  72   /* printf("adding edge: (%d, %d)\n", v, w); */
  73   /*((EdgeList->edges)[n]).node1 = v;*/
  74   /*(EdgeList->edges[n]).node2 = w;*/
  75    for (i=0;i<n-1;i++)
  76      if (((EdgeList->edges[i]).node1!=v) && ((EdgeList->edges[i]).node2!=w))
  77         {
  78             x=(EdgeList->edges[i]).node1;
  79             y=(EdgeList->edges[i]).node2;
  80             (EdgeList->edges[i]).node2=w;
  81             (EdgeList->edges[n]).node1=v;
  82             (EdgeList->edges[n]).node2=y;
  83
  84
  85             ind =  graph->vertexArray[x].adjListInd;
  86             for(i=0; i< graph->vertexArray[x].degree; i++)
  87                     { if (graph->adjArray[ind + i] == y) graph->adjArray[ind+i]=w;}
  88
  89             ind =  graph->vertexArray[y].adjListInd;
  90             for(i=0; i< graph->vertexArray[y].degree; i++)
  91                     { if (graph->adjArray[ind + i] == x) graph->adjArray[ind+i]=y;}
  92
  93             index =  graph->vertexArray[v].next++;
  94             graph->adjArray[ index ] = y;
  95             index =  graph->vertexArray[w].next++;
  96             graph->adjArray[ index ] = x;
  97             graph->vertexArray[v].degree++;
  98             graph->vertexArray[w].degree++;
  99             break;
 100
 101         }
 102 }
 103