lemon-project-template-glpk

annotate deps/glpk/src/glpnet05.c @ 9:33de93886c88

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