7 DGArc *newArc(DGNode *tl,DGNode *hd){
8 DGArc *ar=(DGArc *)malloc(sizeof(DGArc));
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);
19 DGNode *newNode(char *nm){
20 DGNode *nd=(DGNode *)malloc(sizeof(DGNode));
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*));
33 void nodeShow(DGNode* nd){
34 fprintf( stderr,"%3d.%s: (%d,%d)\n", nd->id,nd->name,nd->inDegree,nd->outDegree);
36 if(nd->verified==1) fprintf(stderr,"%ld.%s\t: usable.",nd->id,nd->name);
37 else if(nd->verified==0) fprintf(stderr,"%ld.%s\t: unusable.",nd->id,nd->name);
38 else fprintf(stderr,"%ld.%s\t: notverified.",nd->id,nd->name);
42 DGraph* newDGraph(char* nm){
43 DGraph *dg=(DGraph *)malloc(sizeof(DGraph));
46 dg->maxNodes=BLOCK_SIZE;
47 dg->maxArcs=BLOCK_SIZE;
48 dg->node=(DGNode **)malloc(dg->maxNodes*sizeof(DGNode*));
49 dg->arc=(DGArc **)malloc(dg->maxArcs*sizeof(DGArc*));
54 int AttachNode(DGraph* dg, DGNode* nd) {
56 DGNode **nds =NULL, *tmpnd=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*));
67 len = strlen( nd->name);
68 for (i = 0; i < dg->numNodes; i++) {
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*));
79 for (j = 0; j < nd->inDegree; j++ ) {
80 nd->inArc[ j]->head = tmpnd;
82 memcpy( &(tmpnd->inArc[ tmpnd->inDegree]), nd->inArc, nd->inDegree*sizeof( DGArc *));
83 tmpnd->inDegree += nd->inDegree;
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*));
91 for (j = 0; j < nd->outDegree; j++ ) {
92 nd->outArc[ j]->tail = tmpnd;
94 memcpy( &(tmpnd->outArc[tmpnd->outDegree]),nd->outArc,nd->outDegree*sizeof( DGArc *));
95 tmpnd->outDegree += nd->outDegree;
100 nd->id = dg->numNodes;
101 dg->node[dg->numNodes] = nd;
106 int AttachArc(DGraph *dg,DGArc* nar){
109 DGNode *head = nar->head,
111 DGArc **ars=NULL,*probe=NULL;
112 /*fprintf(stderr,"AttachArc %ld\n",dg->numArcs); */
113 if ( !tail || !head ) return arcId;
114 if ( dg->numArcs == dg->maxArcs-1 ) {
115 dg->maxArcs += BLOCK_SIZE;
116 ars =(DGArc **) calloc(dg->maxArcs,sizeof(DGArc*));
117 memcpy(ars,dg->arc,(dg->maxArcs-BLOCK_SIZE)*sizeof(DGArc*));
121 for(i = 0; i < tail->outDegree; i++ ) { /* parallel arc */
122 probe = tail->outArc[ i];
123 if(probe->head == head && probe->length == nar->length){
129 nar->id = dg->numArcs;
131 dg->arc[dg->numArcs] = nar;
134 head->inArc[ head->inDegree] = nar;
136 if ( head->inDegree >= head->maxInDegree ) {
137 newNumber = head->maxInDegree + SMALL_BLOCK_SIZE;
138 ars =(DGArc **) calloc(newNumber,sizeof(DGArc*));
139 memcpy(ars,head->inArc,(head->inDegree)*sizeof(DGArc*));
142 head->maxInDegree = newNumber;
144 tail->outArc[ tail->outDegree] = nar;
146 if(tail->outDegree >= tail->maxOutDegree ) {
147 newNumber = tail->maxOutDegree + SMALL_BLOCK_SIZE;
148 ars =(DGArc **) calloc(newNumber,sizeof(DGArc*));
149 memcpy(ars,tail->outArc,(tail->outDegree)*sizeof(DGArc*));
152 tail->maxOutDegree = newNumber;
154 /*fprintf(stderr,"AttachArc: head->in=%d tail->out=%ld\n",head->inDegree,tail->outDegree);*/
158 void graphShow(DGraph *dg,int DetailsLevel){
160 fprintf(stderr,"%d.%s: (%d,%d)\n",dg->id,dg->name,dg->numNodes,dg->numArcs);
161 if ( DetailsLevel < 1) return;
162 for (i = 0; i < dg->numNodes; i++ ) {
163 DGNode *focusNode = dg->node[ i];
164 if(DetailsLevel >= 2) {
165 for (j = 0; j < focusNode->inDegree; j++ ) {
166 fprintf(stderr,"\t ");
167 nodeShow(focusNode->inArc[ j]->tail);
171 if ( DetailsLevel < 2) continue;
172 for (j = 0; j < focusNode->outDegree; j++ ) {
173 fprintf(stderr, "\t ");
174 nodeShow(focusNode->outArc[ j]->head);
176 fprintf(stderr, "---\n");
178 fprintf(stderr,"----------------------------------------\n");
179 if ( DetailsLevel < 3) return;