lemon-project-template-glpk
comparison deps/glpk/src/glpnet05.c @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 21:43:29 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:c85accbaa747 |
---|---|
1 /* glpnet05.c (Goldfarb's maximum flow problem generator) */ | |
2 | |
3 /*********************************************************************** | |
4 * This code is part of GLPK (GNU Linear Programming Kit). | |
5 * | |
6 * This code is a modified version of the program RMFGEN, a maxflow | |
7 * problem generator developed by D.Goldfarb and M.Grigoriadis, and | |
8 * originally implemented by Tamas Badics <badics@rutcor.rutgers.edu>. | |
9 * The original code is publically available on the DIMACS ftp site at: | |
10 * <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>. | |
11 * | |
12 * All changes concern only the program interface, so this modified | |
13 * version produces exactly the same instances as the original version. | |
14 * | |
15 * Changes were made by Andrew Makhorin <mao@gnu.org>. | |
16 * | |
17 * GLPK is free software: you can redistribute it and/or modify it | |
18 * under the terms of the GNU General Public License as published by | |
19 * the Free Software Foundation, either version 3 of the License, or | |
20 * (at your option) any later version. | |
21 * | |
22 * GLPK is distributed in the hope that it will be useful, but WITHOUT | |
23 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
24 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
25 * License for more details. | |
26 * | |
27 * You should have received a copy of the GNU General Public License | |
28 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. | |
29 ***********************************************************************/ | |
30 | |
31 #include "glpapi.h" | |
32 #include "glprng.h" | |
33 | |
34 /*********************************************************************** | |
35 * NAME | |
36 * | |
37 * glp_rmfgen - Goldfarb's maximum flow problem generator | |
38 * | |
39 * SYNOPSIS | |
40 * | |
41 * int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap, | |
42 * const int parm[1+5]); | |
43 * | |
44 * DESCRIPTION | |
45 * | |
46 * The routine glp_rmfgen is a maximum flow problem generator developed | |
47 * by D.Goldfarb and M.Grigoriadis. | |
48 * | |
49 * The parameter G specifies the graph object, to which the generated | |
50 * problem data have to be stored. Note that on entry the graph object | |
51 * is erased with the routine glp_erase_graph. | |
52 * | |
53 * The pointer s specifies a location, to which the routine stores the | |
54 * source node number. If s is NULL, the node number is not stored. | |
55 * | |
56 * The pointer t specifies a location, to which the routine stores the | |
57 * sink node number. If t is NULL, the node number is not stored. | |
58 * | |
59 * The parameter a_cap specifies an offset of the field of type double | |
60 * in the arc data block, to which the routine stores the arc capacity. | |
61 * If a_cap < 0, the capacity is not stored. | |
62 * | |
63 * The array parm contains description of the network to be generated: | |
64 * | |
65 * parm[0] not used | |
66 * parm[1] (seed) random number seed (a positive integer) | |
67 * parm[2] (a) frame size | |
68 * parm[3] (b) depth | |
69 * parm[4] (c1) minimal arc capacity | |
70 * parm[5] (c2) maximal arc capacity | |
71 * | |
72 * RETURNS | |
73 * | |
74 * If the instance was successfully generated, the routine glp_netgen | |
75 * returns zero; otherwise, if specified parameters are inconsistent, | |
76 * the routine returns a non-zero error code. | |
77 * | |
78 * COMMENTS | |
79 * | |
80 * The generated network is as follows. It has b pieces of frames of | |
81 * size a * a. (So alltogether the number of vertices is a * a * b) | |
82 * | |
83 * In each frame all the vertices are connected with their neighbours | |
84 * (forth and back). In addition the vertices of a frame are connected | |
85 * one to one with the vertices of next frame using a random permutation | |
86 * of those vertices. | |
87 * | |
88 * The source is the lower left vertex of the first frame, the sink is | |
89 * the upper right vertex of the b'th frame. | |
90 * | |
91 * t | |
92 * +-------+ | |
93 * | .| | |
94 * | . | | |
95 * / | / | | |
96 * +-------+/ -+ b | |
97 * | | |/. | |
98 * a | -v- |/ | |
99 * | | |/ | |
100 * +-------+ 1 | |
101 * s a | |
102 * | |
103 * The capacities are randomly chosen integers from the range of [c1,c2] | |
104 * in the case of interconnecting edges, and c2 * a * a for the in-frame | |
105 * edges. | |
106 * | |
107 * REFERENCES | |
108 * | |
109 * D.Goldfarb and M.D.Grigoriadis, "A computational comparison of the | |
110 * Dinic and network simplex methods for maximum flow." Annals of Op. | |
111 * Res. 13 (1988), pp. 83-123. | |
112 * | |
113 * U.Derigs and W.Meier, "Implementing Goldberg's max-flow algorithm: | |
114 * A computational investigation." Zeitschrift fuer Operations Research | |
115 * 33 (1989), pp. 383-403. */ | |
116 | |
117 typedef struct VERTEX | |
118 { struct EDGE **edgelist; | |
119 /* Pointer to the list of pointers to the adjacent edges. | |
120 (No matter that to or from edges) */ | |
121 struct EDGE **current; | |
122 /* Pointer to the current edge */ | |
123 int degree; | |
124 /* Number of adjacent edges (both direction) */ | |
125 int index; | |
126 } vertex; | |
127 | |
128 typedef struct EDGE | |
129 { int from; | |
130 int to; | |
131 int cap; | |
132 /* Capacity */ | |
133 } edge; | |
134 | |
135 typedef struct NETWORK | |
136 { struct NETWORK *next, *prev; | |
137 int vertnum; | |
138 int edgenum; | |
139 vertex *verts; | |
140 /* Vertex array[1..vertnum] */ | |
141 edge *edges; | |
142 /* Edge array[1..edgenum] */ | |
143 int source; | |
144 /* Pointer to the source */ | |
145 int sink; | |
146 /* Pointer to the sink */ | |
147 } network; | |
148 | |
149 struct csa | |
150 { /* common storage area */ | |
151 glp_graph *G; | |
152 int *s, *t, a_cap; | |
153 RNG *rand; | |
154 network *N; | |
155 int *Parr; | |
156 int A, AA, C2AA, Ec; | |
157 }; | |
158 | |
159 #define G (csa->G) | |
160 #define s (csa->s) | |
161 #define t (csa->t) | |
162 #define a_cap (csa->a_cap) | |
163 #define N (csa->N) | |
164 #define Parr (csa->Parr) | |
165 #define A (csa->A) | |
166 #define AA (csa->AA) | |
167 #define C2AA (csa->C2AA) | |
168 #define Ec (csa->Ec) | |
169 | |
170 #undef random | |
171 #define random(A) (int)(rng_unif_01(csa->rand) * (double)(A)) | |
172 #define RANDOM(A, B) (int)(random((B) - (A) + 1) + (A)) | |
173 #define sgn(A) (((A) > 0) ? 1 : ((A) == 0) ? 0 : -1) | |
174 | |
175 static void make_edge(struct csa *csa, int from, int to, int c1, int c2) | |
176 { Ec++; | |
177 N->edges[Ec].from = from; | |
178 N->edges[Ec].to = to; | |
179 N->edges[Ec].cap = RANDOM(c1, c2); | |
180 return; | |
181 } | |
182 | |
183 static void permute(struct csa *csa) | |
184 { int i, j, tmp; | |
185 for (i = 1; i < AA; i++) | |
186 { j = RANDOM(i, AA); | |
187 tmp = Parr[i]; | |
188 Parr[i] = Parr[j]; | |
189 Parr[j] = tmp; | |
190 } | |
191 return; | |
192 } | |
193 | |
194 static void connect(struct csa *csa, int offset, int cv, int x1, int y1) | |
195 { int cv1; | |
196 cv1 = offset + (x1 - 1) * A + y1; | |
197 Ec++; | |
198 N->edges[Ec].from = cv; | |
199 N->edges[Ec].to = cv1; | |
200 N->edges[Ec].cap = C2AA; | |
201 return; | |
202 } | |
203 | |
204 static network *gen_rmf(struct csa *csa, int a, int b, int c1, int c2) | |
205 { /* generates a network with a*a*b nodes and 6a*a*b-4ab-2a*a edges | |
206 random_frame network: | |
207 Derigs & Meier, Methods & Models of OR (1989), 33:383-403 */ | |
208 int x, y, z, offset, cv; | |
209 A = a; | |
210 AA = a * a; | |
211 C2AA = c2 * AA; | |
212 Ec = 0; | |
213 N = (network *)xmalloc(sizeof(network)); | |
214 N->vertnum = AA * b; | |
215 N->edgenum = 5 * AA * b - 4 * A * b - AA; | |
216 N->edges = (edge *)xcalloc(N->edgenum + 1, sizeof(edge)); | |
217 N->source = 1; | |
218 N->sink = N->vertnum; | |
219 Parr = (int *)xcalloc(AA + 1, sizeof(int)); | |
220 for (x = 1; x <= AA; x++) | |
221 Parr[x] = x; | |
222 for (z = 1; z <= b; z++) | |
223 { offset = AA * (z - 1); | |
224 if (z != b) | |
225 permute(csa); | |
226 for (x = 1; x <= A; x++) | |
227 { for (y = 1; y <= A; y++) | |
228 { cv = offset + (x - 1) * A + y; | |
229 if (z != b) | |
230 make_edge(csa, cv, offset + AA + Parr[cv - offset], | |
231 c1, c2); /* the intermediate edges */ | |
232 if (y < A) | |
233 connect(csa, offset, cv, x, y + 1); | |
234 if (y > 1) | |
235 connect(csa, offset, cv, x, y - 1); | |
236 if (x < A) | |
237 connect(csa, offset, cv, x + 1, y); | |
238 if (x > 1) | |
239 connect(csa, offset, cv, x - 1, y); | |
240 } | |
241 } | |
242 } | |
243 xfree(Parr); | |
244 return N; | |
245 } | |
246 | |
247 static void print_max_format(struct csa *csa, network *n, char *comm[], | |
248 int dim) | |
249 { /* prints a network heading with dim lines of comments (no \n | |
250 needs at the ends) */ | |
251 int i, vnum, e_num; | |
252 edge *e; | |
253 vnum = n->vertnum; | |
254 e_num = n->edgenum; | |
255 if (G == NULL) | |
256 { for (i = 0; i < dim; i++) | |
257 xprintf("c %s\n", comm[i]); | |
258 xprintf("p max %7d %10d\n", vnum, e_num); | |
259 xprintf("n %7d s\n", n->source); | |
260 xprintf("n %7d t\n", n->sink); | |
261 } | |
262 else | |
263 { glp_add_vertices(G, vnum); | |
264 if (s != NULL) *s = n->source; | |
265 if (t != NULL) *t = n->sink; | |
266 } | |
267 for (i = 1; i <= e_num; i++) | |
268 { e = &n->edges[i]; | |
269 if (G == NULL) | |
270 xprintf("a %7d %7d %10d\n", e->from, e->to, (int)e->cap); | |
271 else | |
272 { glp_arc *a = glp_add_arc(G, e->from, e->to); | |
273 if (a_cap >= 0) | |
274 { double temp = (double)e->cap; | |
275 memcpy((char *)a->data + a_cap, &temp, sizeof(double)); | |
276 } | |
277 } | |
278 } | |
279 return; | |
280 } | |
281 | |
282 static void gen_free_net(network *n) | |
283 { xfree(n->edges); | |
284 xfree(n); | |
285 return; | |
286 } | |
287 | |
288 int glp_rmfgen(glp_graph *G_, int *_s, int *_t, int _a_cap, | |
289 const int parm[1+5]) | |
290 { struct csa _csa, *csa = &_csa; | |
291 network *n; | |
292 char comm[10][80], *com1[10]; | |
293 int seed, a, b, c1, c2, ret; | |
294 G = G_; | |
295 s = _s; | |
296 t = _t; | |
297 a_cap = _a_cap; | |
298 if (G != NULL) | |
299 { if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double)) | |
300 xerror("glp_rmfgen: a_cap = %d; invalid offset\n", a_cap); | |
301 } | |
302 seed = parm[1]; | |
303 a = parm[2]; | |
304 b = parm[3]; | |
305 c1 = parm[4]; | |
306 c2 = parm[5]; | |
307 if (!(seed > 0 && 1 <= a && a <= 1000 && 1 <= b && b <= 1000 && | |
308 0 <= c1 && c1 <= c2 && c2 <= 1000)) | |
309 { ret = 1; | |
310 goto done; | |
311 } | |
312 if (G != NULL) | |
313 { glp_erase_graph(G, G->v_size, G->a_size); | |
314 glp_set_graph_name(G, "RMFGEN"); | |
315 } | |
316 csa->rand = rng_create_rand(); | |
317 rng_init_rand(csa->rand, seed); | |
318 n = gen_rmf(csa, a, b, c1, c2); | |
319 sprintf(comm[0], "This file was generated by genrmf."); | |
320 sprintf(comm[1], "The parameters are: a: %d b: %d c1: %d c2: %d", | |
321 a, b, c1, c2); | |
322 com1[0] = comm[0]; | |
323 com1[1] = comm[1]; | |
324 print_max_format(csa, n, com1, 2); | |
325 gen_free_net(n); | |
326 rng_delete_rand(csa->rand); | |
327 ret = 0; | |
328 done: return ret; | |
329 } | |
330 | |
331 /**********************************************************************/ | |
332 | |
333 #if 0 | |
334 int main(int argc, char *argv[]) | |
335 { int seed, a, b, c1, c2, i, parm[1+5]; | |
336 seed = 123; | |
337 a = b = c1 = c2 = -1; | |
338 for (i = 1; i < argc; i++) | |
339 { if (strcmp(argv[i], "-seed") == 0) | |
340 seed = atoi(argv[++i]); | |
341 else if (strcmp(argv[i], "-a") == 0) | |
342 a = atoi(argv[++i]); | |
343 else if (strcmp(argv[i], "-b") == 0) | |
344 b = atoi(argv[++i]); | |
345 else if (strcmp(argv[i], "-c1") == 0) | |
346 c1 = atoi(argv[++i]); | |
347 else if (strcmp(argv[i], "-c2") == 0) | |
348 c2 = atoi(argv[++i]); | |
349 } | |
350 if (a < 0 || b < 0 || c1 < 0 || c2 < 0) | |
351 { xprintf("Usage:\n"); | |
352 xprintf("genrmf [-seed seed] -a frame_size -b depth\n"); | |
353 xprintf(" -c1 cap_range1 -c2 cap_range2\n"); | |
354 } | |
355 else | |
356 { parm[1] = seed; | |
357 parm[2] = a; | |
358 parm[3] = b; | |
359 parm[4] = c1; | |
360 parm[5] = c2; | |
361 glp_rmfgen(NULL, NULL, NULL, 0, parm); | |
362 } | |
363 return 0; | |
364 } | |
365 #endif | |
366 | |
367 /* eof */ |