Debian Codegraph @

SYMPHONY/Applications/VRP/src/DrawGraph/vrp_dg_network.c

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs ([email protected]) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 /* system include files */
17 #include <string.h>
18
19 /* SYMPHONY include files */
20 #include "sym_macros.h"
21 #include "sym_constants.h"
22 #include "sym_dg.h"
23
24 /* VRP include files */
25 #include "vrp_dg.h"
26 #include "vrp_const.h"
27 #include "vrp_macros.h"
28
29 /*===========================================================================*/
30
31 /*===========================================================================*\
32 * This file contains additional user functions for the draw graph process.
33 \*===========================================================================*/
34
35 /*===========================================================================*\
36 * Create the solution graph using adjacency lists
37 \*===========================================================================*/
38
39 dg_net_network *dg_createnet(int vertnum, int length, int *xind, double *xval)
40 {
41 dg_net_edge *nedge;
42 dg_net_network *n;
43 dg_net_vertex *verts, *nv;
44 int v[2], i, j;
45 dg_net_elist *adjlist;
46
47 n = (dg_net_network *) calloc(1, sizeof(dg_net_network));
48 n->vertnum = vertnum;
49 n->edgenum = length;
50 n->verts = verts =
51 (dg_net_vertex *) calloc(n->vertnum, sizeof(dg_net_vertex));
52 n->adjlist = adjlist =
53 (dg_net_elist *) malloc(2 * n->edgenum*sizeof(dg_net_elist));
54 n->edges = nedge = (dg_net_edge *) calloc(n->edgenum, sizeof(dg_net_edge));
55
56 /*---- set up orignodenum ------------------------------------------------*/
57 for (i=vertnum-1; i>=0; i--){
58 verts[i].orignodenum = i;
59 }
60
61 /*---- set up the adjacency list -----------------------------------------*/
62 for (i=0; i<length; i++, xval++, xind++){
63 BOTH_ENDS(*xind, &v[1], &v[0]);
64 nedge->head = verts + v[0];
65 nedge->tail = verts + v[1];
66 nedge->weight = *xval;
67 for (j=1; j>=0; j--){
68 nv = verts + v[j];
69 if (!nv->first){
70 nv->first = nv->last = adjlist;
71 }else{
72 nv->last->next_edge = adjlist;
73 nv->last = adjlist;
74 }
75 adjlist->next_edge = NULL;
76 nv->degree++;
77 adjlist->data = nedge;
78 adjlist->other = verts + v[1-j];
79 adjlist++;
80 }
81 nedge++;
82 }
83 return(n);
84 }
85
86 /*===========================================================================*/
87
88 /*===========================================================================*\
89 * Free the network
90 \*===========================================================================*/
91
92 void dg_freenet(dg_net_network *n)
93 {
94 if (n){
95 FREE(n->adjlist);
96 FREE(n->edges);
97 FREE(n->verts);
98 FREE(n);
99 }
100 }
101
102 /*===========================================================================*/
103
104 /*===========================================================================*\
105 * This function shrinks the chains in the graph
106 \*===========================================================================*/
107
108 void dg_net_shrink_chains(dg_net_network *n)
109 {
110 int vertnum = n->vertnum;
111 dg_net_vertex *verts = n->verts;
112
113 dg_net_vertex *nw, *nv1, *nv, *nu;
114 dg_net_elist *ne;
115 dg_net_edge *dat;
116
117 int i;
118
119 /*------------------------------------------------------------------------*
120 * Here we contract all chains of 1-edges, called 1-paths. We simply
121 * look at all nodes of degree 2 and keep following the 1-path in each
122 * direction from that node until we reach a node that is not of degree 2.
123 *------------------------------------------------------------------------*/
124
125 for (i=0; i<vertnum-1; i++){
126 nv = verts+i;
127 /*-----------check whether we have a degree 2 node-----------*/
128 if (nv->scanned != NOT_SCANNED || nv->degree != 2)
129 continue;
130
131 nv->scanned = SCANNED_SHRUNK;
132
133 /*---------------------------------------------------------------------*
134 * follow the 1-path from i until we hit a node that is not of degree 2
135 * If during this process we come back to nv (i) that means we have a
136 * subtour we can contract into one node.
137 * Also, as we go along we contract all the nodes on the 1-path into i.
138 *---------------------------------------------------------------------*/
139 for (ne = nv->first, nw = ne->other; nw->degree == 2; nw = ne->other){
140 ne->data->deleted = TRUE;
141 if (nv == nw)
142 break;
143 nw->scanned = SCANNED_SHRUNK;
144 nv->snode_size++;
145 nw->snode_next = nv->snode_next;
146 nv->snode_next = nw;
147 ne = (nw->first->data->deleted ? nw->last : nw->first);
148 }
149
150 if (nv == nw){
151 /* in this case we had a subtour and so we don't need to go on*/
152 nv->first = nv->last = NULL;
153 nv->scanned = SCANNED_ALIVE;
154 continue;
155 }
156
157 /* Now nw is not a degree 2 node, but nv->snode_next is the node
158 * in the chain adjacent to nw and so on. The number of nodes
159 * hanging off nv is exactly nv->snode_size (not including nv) */
160 if (nv->snode_size){
161 nv1 = nv->snode_next;
162 if (nv1->first->other != nw){
163 ne = nv1->first;
164 nv1->first = nv1->last;
165 nv1->first->next_edge = ne;
166 nv1->last = ne;
167 ne->next_edge = NULL;
168 }
169 /* Follow the chain back and hang nv to the end */
170 nv1->snode_size = nv->snode_size;
171 for (nu = nv1; nu->snode_next; nu = nu->snode_next);
172 nu->snode_next = nv;
173 nv->snode_next = NULL;
174 nv->snode_size = 0;
175 }else{
176 nv1 = nv;
177 }
178
179 /* Now nw is next to nv1 and nv1->first->other = nw */
180
181 /* Continue to the other end. */
182 for (ne=nv->last, nu=ne->other; nu->degree == 2; nv=nu, nu=ne->other){
183 ne->data->deleted = TRUE;
184 nu->scanned = SCANNED_SHRUNK;
185 nv1->snode_size++;
186 nv->snode_next = nu;
187 ne = (nu->first->data->deleted ? nu->last : nu->first);
188 }
189
190 /* Now nv is the last node in the chain, nu the first not degree
191 * 2 node, (ne goes from nv to nu) the chain hangs off of nv1 in
192 * order, nv1->size is the number of degree 2 nodes in the chain
193 * -1 (nv1 itself).
194 *
195 * Now we update the adjacency lists appropriately. */
196 if (nv1->snode_size){
197 nv1->first->next_edge = nv1->last = ne;
198 ne->next_edge = NULL;
199 dat = ne->data;
200 if (dat->head == nu)
201 dat->tail = nv1;
202 else
203 dat->head = nv1;
204 for (ne=nu->first; ne->data != dat; ne=ne->next_edge);
205 ne->other = nv1;
206 }
207 nv1->scanned = SCANNED_ALIVE;
208 /* Now we are completely done. The whole chain is shrinked
209 * into nv1, nv1 is connected to appropriately to nw and nu. */
210 }
211
212 /* Note that the 'scanned' field is SCANNED_SHRUNK for nodes shrinked into
213 * another node; SCANNED_ALIVE for degree 2 nodes still alive and
214 * NOT_SCANNED for nodes of degree >= 3 */
215 }
216
217 /*===========================================================================*/
218
219 /*===========================================================================*\
220 * This function copies a network into a graph which already contains the
221 * nodes of the graph. Therefore we have to get rid of the shrunk nodes
222 * in the process.
223 \*===========================================================================*/
224
225 void copy_network_into_graph(dg_net_network *n, dg_graph *g)
226 {
227 int i, k, vertnum = n->vertnum, edgenum = n->edgenum;
228 dg_net_vertex *verts = n->verts;
229 dg_net_edge *ne, *nedges = n->edges;
230 dg_node *nod, *gnod, *nodes, *gnodes = g->nodes;
231 dg_edge *ge, *gedges = g->edges;
232
233 for (k = i = 0; i < vertnum; i++)
234 if (verts[i].scanned != SCANNED_SHRUNK)
235 k++;
236
237 nodes = (dg_node *) malloc(k * sizeof(dg_node));
238 for (k = i = 0; i < vertnum; i++){
239 if (verts[i].scanned != SCANNED_SHRUNK){
240 nod = nodes + k++;
241 gnod = gnodes + i;
242 *nod = *gnod;
243 if (verts[i].snode_size){ /* if anything is shrunk into this node */
244 sprintf(nod->weight, "%i", verts[i].snode_size);
245 }else{
246 *nod->weight = 0;
247 }
248 }
249 }
250 FREE(gnodes);
251 g->nodenum = k;
252 g->nodes = nodes;
253
254 for (k = i = 0; i < edgenum; i++)
255 if (! nedges[i].deleted)
256 k++;
257
258 gedges = g->edges = (dg_edge *) malloc(k * sizeof(dg_edge));
259 for (k = i = 0; i < edgenum; i++){
260 if (!(ne=nedges+i)->deleted){
261 ge = gedges + k++;
262 ge->edge_id = INDEX( (ge->tail = ne->tail->orignodenum),
263 (ge->head = ne->head->orignodenum) );
264 ge->deleted = FALSE;
265 if (ne->weight > .99999){
266 strcpy(ge->weight, "1");
267 ge->dash[0] = 0;
268 }else{
269 sprintf(ge->weight, "%.3f", ne->weight);
270 strcpy(ge->dash, "4 3");
271 }
272 }
273 }
274 g->edgenum = k;
275 }