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 */ |
---|