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