examples/smpi/NAS/DGraph.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "DGraph.h"
   6
   7 DGArc *newArc(DGNode *tl,DGNode *hd){
   8   DGArc *ar=(DGArc *)malloc(sizeof(DGArc));
   9   ar->tail=tl;
  10   ar->head=hd;
  11   return ar;
  12 }
  13
  14 void arcShow(DGArc *ar){
  15   DGNode *tl=(DGNode *)ar->tail,
  16          *hd=(DGNode *)ar->head;
  17   fprintf(stderr,"%d. |%s ->%s\n",ar->id,tl->name,hd->name);
  18 }
  19
  20 DGNode *newNode(char *nm){
  21   DGNode *nd=(DGNode *)malloc(sizeof(DGNode));
  22   nd->attribute=0;
  23   nd->color=0;
  24   nd->inDegree=0;
  25   nd->outDegree=0;
  26   nd->maxInDegree=SMALL_BLOCK_SIZE;
  27   nd->maxOutDegree=SMALL_BLOCK_SIZE;
  28   nd->inArc=(DGArc **)malloc(nd->maxInDegree*sizeof(DGArc*));
  29   nd->outArc=(DGArc **)malloc(nd->maxOutDegree*sizeof(DGArc*));
  30   nd->name=strdup(nm);
  31   nd->feat=NULL;
  32   return nd;
  33 }
  34
  35 void nodeShow(DGNode* nd){
  36   fprintf( stderr,"%3d.%s: (%d,%d)\n", nd->id,nd->name,nd->inDegree,nd->outDegree);
  37 /*
  38   if(nd->verified==1) fprintf(stderr,"%ld.%s\t: usable.",nd->id,nd->name);
  39   else if(nd->verified==0)  fprintf(stderr,"%ld.%s\t: unusable.",nd->id,nd->name);
  40   else  fprintf(stderr,"%ld.%s\t: notverified.",nd->id,nd->name);
  41 */
  42 }
  43
  44 DGraph* newDGraph(char* nm){
  45   DGraph *dg=(DGraph *)malloc(sizeof(DGraph));
  46   dg->numNodes=0;
  47   dg->numArcs=0;
  48   dg->maxNodes=BLOCK_SIZE;
  49   dg->maxArcs=BLOCK_SIZE;
  50   dg->node=(DGNode **)malloc(dg->maxNodes*sizeof(DGNode*));
  51   dg->arc=(DGArc **)malloc(dg->maxArcs*sizeof(DGArc*));
  52   dg->name=strdup(nm);
  53   return dg;
  54 }
  55
  56 int AttachNode(DGraph* dg, DGNode* nd) {
  57   int i = 0, j;
  58   unsigned len = 0;
  59   DGNode **nds =NULL, *tmpnd=NULL;
  60   DGArc **ar=NULL;
  61
  62   if (dg->numNodes == dg->maxNodes-1 ) {
  63     dg->maxNodes += BLOCK_SIZE;
  64     nds =(DGNode **) calloc(dg->maxNodes,sizeof(DGNode*));
  65     memcpy(nds,dg->node,(dg->maxNodes-BLOCK_SIZE)*sizeof(DGNode*));
  66     free(dg->node);
  67     dg->node=nds;
  68   }
  69
  70   len = strlen( nd->name);
  71   for (i = 0; i < dg->numNodes; i++) {
  72     tmpnd =dg->node[ i];
  73     ar=NULL;
  74     if ( strlen( tmpnd->name) != len ) continue;
  75     if ( strncmp( nd->name, tmpnd->name, len) ) continue;
  76     if ( nd->inDegree > 0 ) {
  77       tmpnd->maxInDegree += nd->maxInDegree;
  78       ar =(DGArc **) calloc(tmpnd->maxInDegree,sizeof(DGArc*));
  79       memcpy(ar,tmpnd->inArc,(tmpnd->inDegree)*sizeof(DGArc*));
  80       free(tmpnd->inArc);
  81       tmpnd->inArc=ar;
  82       for (j = 0; j < nd->inDegree; j++ ) {
  83         nd->inArc[ j]->head = tmpnd;
  84       }
  85       memcpy( &(tmpnd->inArc[ tmpnd->inDegree]), nd->inArc, nd->inDegree*sizeof( DGArc *));
  86       tmpnd->inDegree += nd->inDegree;
  87     }
  88     if ( nd->outDegree > 0 ) {
  89       tmpnd->maxOutDegree += nd->maxOutDegree;
  90       ar =(DGArc **) calloc(tmpnd->maxOutDegree,sizeof(DGArc*));
  91       memcpy(ar,tmpnd->outArc,(tmpnd->outDegree)*sizeof(DGArc*));
  92       free(tmpnd->outArc);
  93       tmpnd->outArc=ar;
  94       for (j = 0; j < nd->outDegree; j++ ) {
  95         nd->outArc[ j]->tail = tmpnd;
  96       }
  97       memcpy( &(tmpnd->outArc[tmpnd->outDegree]),nd->outArc,nd->outDegree*sizeof( DGArc *));
  98       tmpnd->outDegree += nd->outDegree;
  99     }
 100     free(nd);
 101     return i;
 102   }
 103   nd->id = dg->numNodes;
 104   dg->node[dg->numNodes] = nd;
 105   dg->numNodes++;
 106   return nd->id;
 107 }
 108
 109 int AttachArc(DGraph *dg,DGArc* nar){
 110   int  arcId = -1;
 111   int i=0,newNumber=0;
 112   DGNode  *head = nar->head,
 113           *tail = nar->tail;
 114   DGArc **ars=NULL,*probe=NULL;
 115   /*fprintf(stderr,"AttachArc %ld\n",dg->numArcs); */
 116   if ( !tail || !head ) return arcId;
 117   if ( dg->numArcs == dg->maxArcs-1 ) {
 118     dg->maxArcs += BLOCK_SIZE;
 119     ars =(DGArc **) calloc(dg->maxArcs,sizeof(DGArc*));
 120     memcpy(ars,dg->arc,(dg->maxArcs-BLOCK_SIZE)*sizeof(DGArc*));
 121     free(dg->arc);
 122     dg->arc=ars;
 123   }
 124   for(i = 0; i < tail->outDegree; i++ ) { /* parallel arc */
 125     probe = tail->outArc[ i];
 126     if(probe->head == head && probe->length == nar->length){
 127       free(nar);
 128       return probe->id;
 129     }
 130   }
 131
 132   nar->id = dg->numArcs;
 133   arcId=dg->numArcs;
 134   dg->arc[dg->numArcs] = nar;
 135   dg->numArcs++;
 136
 137   head->inArc[ head->inDegree] = nar;
 138   head->inDegree++;
 139   if ( head->inDegree >= head->maxInDegree ) {
 140     newNumber = head->maxInDegree + SMALL_BLOCK_SIZE;
 141     ars =(DGArc **) calloc(newNumber,sizeof(DGArc*));
 142     memcpy(ars,head->inArc,(head->inDegree)*sizeof(DGArc*));
 143     free(head->inArc);
 144     head->inArc=ars;
 145     head->maxInDegree = newNumber;
 146   }
 147   tail->outArc[ tail->outDegree] = nar;
 148   tail->outDegree++;
 149   if(tail->outDegree >= tail->maxOutDegree ) {
 150     newNumber = tail->maxOutDegree + SMALL_BLOCK_SIZE;
 151     ars =(DGArc **) calloc(newNumber,sizeof(DGArc*));
 152     memcpy(ars,tail->outArc,(tail->outDegree)*sizeof(DGArc*));
 153     free(tail->outArc);
 154     tail->outArc=ars;
 155     tail->maxOutDegree = newNumber;
 156   }
 157 /*fprintf(stderr,"AttachArc: head->in=%d tail->out=%ld\n",head->inDegree,tail->outDegree);*/
 158   return arcId;
 159 }
 160
 161 void graphShow(DGraph *dg,int DetailsLevel){
 162   int i=0,j=0;
 163   fprintf(stderr,"%d.%s: (%d,%d)\n",dg->id,dg->name,dg->numNodes,dg->numArcs);
 164   if ( DetailsLevel < 1) return;
 165   for (i = 0; i < dg->numNodes; i++ ) {
 166     DGNode *focusNode = dg->node[ i];
 167     if(DetailsLevel >= 2) {
 168       for (j = 0; j < focusNode->inDegree; j++ ) {
 169         fprintf(stderr,"\t ");
 170         nodeShow(focusNode->inArc[ j]->tail);
 171       }
 172     }
 173     nodeShow(focusNode);
 174     if ( DetailsLevel < 2) continue;
 175     for (j = 0; j < focusNode->outDegree; j++ ) {
 176       fprintf(stderr, "\t ");
 177       nodeShow(focusNode->outArc[ j]->head);
 178     }
 179     fprintf(stderr, "---\n");
 180   }
 181   fprintf(stderr,"----------------------------------------\n");
 182   if ( DetailsLevel < 3) return;
 183 }