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",
35 nd->id,nd->name,nd->inDegree,nd->outDegree);
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);
43 DGraph* newDGraph(char* nm){
44 DGraph *dg=(DGraph *)malloc(sizeof(DGraph));
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*));
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;
105 int AttachArc(DGraph *dg,DGArc* nar){
108 DGNode *head = nar->head,
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*));
120 for(i = 0; i < tail->outDegree; i++ ) { /* parallel arc */
121 probe = tail->outArc[ i];
122 if(probe->head == head
124 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);*/
159 void graphShow(DGraph *dg,int DetailsLevel){
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);
172 if ( DetailsLevel < 2) continue;
173 for (j = 0; j < focusNode->outDegree; j++ ) {
174 fprintf(stderr, "\t ");
175 nodeShow(focusNode->outArc[ j]->head);
177 fprintf(stderr, "---\n");
179 fprintf(stderr,"----------------------------------------\n");
180 if ( DetailsLevel < 3) return;