Debian Codegraph @

SYMPHONY/Applications/VRP/src/CutGen/MinCut/capforest.c

raw
1 #include <stdio.h>
2
3 #include "capforest.h"
4
5 #define tnodenum degree
6
7 /*=======================================================================*/
8
9 /* This routine builds up the "capacitated forests" as it is
10 in the Nagamochi - Ibaraki paper */
11
12 float capforest(network *n, int Vertnum, char scannedmark)
13 {
14 int i;
15 int last_tnode;
16 register vertex *nv = NULL;
17 register elist *ne;
18 register edge *ned;
19 vertex **tnodes = n->tnodes;
20 vertex **nen = n->enodes;
21 int nomark = 1-scannedmark;
22 float max_q = 0;
23
24 /*------------------- Initialization -------------*/
25
26 for (i=0; i<Vertnum; i++){
27 nv = nen[i];
28 nv->r = 0;
29 ne=nv->first;
30 do{
31 ne->data->q = 0;
32 ne->data->scanned = nomark; /*this is unnecessary*/
33 }while ((ne=ne->next_edge) != NULL);
34 }
35
36 last_tnode = 0;
37
38 /*------------------- The big while loop ---------*/
39
40 do{
41 ne=nv->first;
42 do{
43 if ((ned=ne->data)->scanned != scannedmark){
44 ned->scanned = scannedmark;
45 ned->q = increment((n->verts)+(OTHER_END(ne, nv->orignodenum)),
46 ned->weight, tnodes, &last_tnode);
47 if (ned->q > max_q) max_q = ned->q;
48 }
49 }while ((ne=ne->next_edge) != NULL);
50 nv = delmax(tnodes, &last_tnode);
51 }while (last_tnode != 0);
52 return(max_q);
53 }
54
55 /*=======================================================================*/
56
57 vertex *delmax(tnodes, ltn)
58 vertex **tnodes;
59 int *ltn;
60 {
61 vertex *temp, *retnode;
62 int last = *ltn;
63 int pos, ch;
64 float actual;
65
66 retnode = tnodes[1];
67 temp = tnodes[1] = tnodes[last];
68 actual = temp->r;
69 *ltn = --last;
70 pos = 1;
71 while ((ch=2*pos) < last){
72 if (tnodes[ch]->r < tnodes[ch+1]->r)
73 ch++;
74 if (actual >= tnodes[ch]->r){
75 tnodes[pos] = temp;
76 temp->tnodenum = pos;
77 return(retnode);
78 }
79 tnodes[pos] = tnodes[ch];
80 tnodes[ch]->tnodenum = pos;
81 pos = ch;
82 }
83 if (ch == last){
84 if (actual < tnodes[ch]->r){
85 tnodes[pos] = tnodes[ch];
86 tnodes[ch]->tnodenum = pos;
87 pos=ch;
88 }
89 }
90 tnodes[pos] = temp;
91 temp->tnodenum = pos;
92 return(retnode);
93 }
94
95 /*=======================================================================*/
96
97 float increment(vertex *v, float inc, vertex **tnodes, int *ltn)
98 {
99 float actval;
100 int pos, ch;
101 int last = *ltn;
102
103 if (v->r == 0){ /* We have to insert it into the tree */
104 *ltn = ++last;
105 pos = last;
106 }else{
107 pos = v->tnodenum;
108 }
109
110 /*************
111 pos = (v->r == 0) ? (*ltn = ++last) : v->tnodenum;
112 *************/
113 actval = (v->r += inc);
114
115 while ((ch=pos/2) != 0){
116 if (tnodes[ch]->r < actval){
117 tnodes[pos] = tnodes[ch];
118 tnodes[ch]->tnodenum = pos;
119 pos = ch;
120 }else{
121 tnodes[pos] = v;
122 v->tnodenum = pos;
123 return(actval);
124 }
125 }
126 tnodes[pos] = v;
127 v->tnodenum = pos;
128 return(actval);
129 }
130
131 /*=======================================================================*/