7 DGArc *newArc(DGNode *tl,DGNode *hd){
8 DGArc *ar=(DGArc *)malloc(sizeof(DGArc));
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);
20 DGNode *newNode(char *nm){
21 DGNode *nd=(DGNode *)malloc(sizeof(DGNode));
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*));
35 void nodeShow(DGNode* nd){
36 fprintf( stderr,"%3d.%s: (%d,%d)\n", nd->id,nd->name,nd->inDegree,nd->outDegree);
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);
44 DGraph* newDGraph(char* nm){
45 DGraph *dg=(DGraph *)malloc(sizeof(DGraph));
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*));
56 int AttachNode(DGraph* dg, DGNode* nd) {
58 DGNode **nds =NULL, *tmpnd=NULL;
61 if (dg->numNodes == dg->maxNodes-1 ) {
62 dg->maxNodes += BLOCK_SIZE;
63 nds =(DGNode **) calloc(dg->maxNodes,sizeof(DGNode*));
64 memcpy(nds,dg->node,(dg->maxNodes-BLOCK_SIZE)*sizeof(DGNode*));
69 len = strlen( nd->name);
70 for (i = 0; i < dg->numNodes; i++) {
73 if ( strlen( tmpnd->name) != len ) continue;
74 if ( strncmp( nd->name, tmpnd->name, len) ) continue;
75 if ( nd->inDegree > 0 ) {
76 tmpnd->maxInDegree += nd->maxInDegree;
77 ar =(DGArc **) calloc(tmpnd->maxInDegree,sizeof(DGArc*));
78 memcpy(ar,tmpnd->inArc,(tmpnd->inDegree)*sizeof(DGArc*));
81 for (j = 0; j < nd->inDegree; j++ ) {
82 nd->inArc[ j]->head = tmpnd;
84 memcpy( &(tmpnd->inArc[ tmpnd->inDegree]), nd->inArc, nd->inDegree*sizeof( DGArc *));
85 tmpnd->inDegree += nd->inDegree;
87 if ( nd->outDegree > 0 ) {
88 tmpnd->maxOutDegree += nd->maxOutDegree;
89 ar =(DGArc **) calloc(tmpnd->maxOutDegree,sizeof(DGArc*));
90 memcpy(ar,tmpnd->outArc,(tmpnd->outDegree)*sizeof(DGArc*));
93 for (j = 0; j < nd->outDegree; j++ ) {
94 nd->outArc[ j]->tail = tmpnd;
96 memcpy( &(tmpnd->outArc[tmpnd->outDegree]),nd->outArc,nd->outDegree*sizeof( DGArc *));
97 tmpnd->outDegree += nd->outDegree;
102 nd->id = dg->numNodes;
103 dg->node[dg->numNodes] = nd;
108 int AttachArc(DGraph *dg,DGArc* nar){
111 DGNode *head = nar->head,
113 DGArc **ars=NULL,*probe=NULL;
114 /*fprintf(stderr,"AttachArc %ld\n",dg->numArcs); */
115 if ( !tail || !head ) return arcId;
116 if ( dg->numArcs == dg->maxArcs-1 ) {
117 dg->maxArcs += BLOCK_SIZE;
118 ars =(DGArc **) calloc(dg->maxArcs,sizeof(DGArc*));
119 memcpy(ars,dg->arc,(dg->maxArcs-BLOCK_SIZE)*sizeof(DGArc*));
123 for(i = 0; i < tail->outDegree; i++ ) { /* parallel arc */
124 probe = tail->outArc[ i];
125 if(probe->head == head && probe->length == nar->length){
131 nar->id = dg->numArcs;
133 dg->arc[dg->numArcs] = nar;
136 head->inArc[ head->inDegree] = nar;
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*));
144 head->maxInDegree = newNumber;
146 tail->outArc[ tail->outDegree] = nar;
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*));
154 tail->maxOutDegree = newNumber;
156 /*fprintf(stderr,"AttachArc: head->in=%d tail->out=%ld\n",head->inDegree,tail->outDegree);*/
160 void graphShow(DGraph *dg,int DetailsLevel){
162 fprintf(stderr,"%d.%s: (%d,%d)\n",dg->id,dg->name,dg->numNodes,dg->numArcs);
163 if ( DetailsLevel < 1) return;
164 for (i = 0; i < dg->numNodes; i++ ) {
165 DGNode *focusNode = dg->node[ i];
166 if(DetailsLevel >= 2) {
167 for (j = 0; j < focusNode->inDegree; j++ ) {
168 fprintf(stderr,"\t ");
169 nodeShow(focusNode->inArc[ j]->tail);
173 if ( DetailsLevel < 2) continue;
174 for (j = 0; j < focusNode->outDegree; j++ ) {
175 fprintf(stderr, "\t ");
176 nodeShow(focusNode->outArc[ j]->head);
178 fprintf(stderr, "---\n");
180 fprintf(stderr,"----------------------------------------\n");
181 if ( DetailsLevel < 3) return;