Algorithmique Numérique Distribuée Public GIT Repository
f573786db8d4035bb56f3165a51edb547e1fd1e4
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
5 #include "DGraph.h"
7 DGArc *newArc(DGNode *tl,DGNode *hd){
8   DGArc *ar=(DGArc *)malloc(sizeof(DGArc));
9   ar->tail=tl;
11   return ar;
12 }
13 void arcShow(DGArc *ar){
14   DGNode *tl=(DGNode *)ar->tail,
16   fprintf(stderr,"%d. |%s ->%s\n",ar->id,tl->name,hd->name);
17 }
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 }
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;
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   }
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;
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];
123        &&
124        probe->length == nar->length
125             ){
126             free(nar);
127       return probe->id;
128     }
129   }
131   nar->id = dg->numArcs;
132   arcId=dg->numArcs;
133   dg->arc[dg->numArcs] = nar;
134   dg->numArcs++;
138   if ( head->inDegree >= head->maxInDegree ) {
139     newNumber = head->maxInDegree + SMALL_BLOCK_SIZE;
140           ars =(DGArc **) calloc(newNumber,sizeof(DGArc*));
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   }
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 ");