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