alpar@1: /* glpnet05.c (Goldfarb's maximum flow problem generator) */ alpar@1: alpar@1: /*********************************************************************** alpar@1: * This code is part of GLPK (GNU Linear Programming Kit). alpar@1: * alpar@1: * This code is a modified version of the program RMFGEN, a maxflow alpar@1: * problem generator developed by D.Goldfarb and M.Grigoriadis, and alpar@1: * originally implemented by Tamas Badics . alpar@1: * The original code is publically available on the DIMACS ftp site at: alpar@1: * . alpar@1: * alpar@1: * All changes concern only the program interface, so this modified alpar@1: * version produces exactly the same instances as the original version. alpar@1: * alpar@1: * Changes were made by Andrew Makhorin . alpar@1: * alpar@1: * GLPK is free software: you can redistribute it and/or modify it alpar@1: * under the terms of the GNU General Public License as published by alpar@1: * the Free Software Foundation, either version 3 of the License, or alpar@1: * (at your option) any later version. alpar@1: * alpar@1: * GLPK is distributed in the hope that it will be useful, but WITHOUT alpar@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY alpar@1: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public alpar@1: * License for more details. alpar@1: * alpar@1: * You should have received a copy of the GNU General Public License alpar@1: * along with GLPK. If not, see . alpar@1: ***********************************************************************/ alpar@1: alpar@1: #include "glpapi.h" alpar@1: #include "glprng.h" alpar@1: alpar@1: /*********************************************************************** alpar@1: * NAME alpar@1: * alpar@1: * glp_rmfgen - Goldfarb's maximum flow problem generator alpar@1: * alpar@1: * SYNOPSIS alpar@1: * alpar@1: * int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap, alpar@1: * const int parm[1+5]); alpar@1: * alpar@1: * DESCRIPTION alpar@1: * alpar@1: * The routine glp_rmfgen is a maximum flow problem generator developed alpar@1: * by D.Goldfarb and M.Grigoriadis. alpar@1: * alpar@1: * The parameter G specifies the graph object, to which the generated alpar@1: * problem data have to be stored. Note that on entry the graph object alpar@1: * is erased with the routine glp_erase_graph. alpar@1: * alpar@1: * The pointer s specifies a location, to which the routine stores the alpar@1: * source node number. If s is NULL, the node number is not stored. alpar@1: * alpar@1: * The pointer t specifies a location, to which the routine stores the alpar@1: * sink node number. If t is NULL, the node number is not stored. alpar@1: * alpar@1: * The parameter a_cap specifies an offset of the field of type double alpar@1: * in the arc data block, to which the routine stores the arc capacity. alpar@1: * If a_cap < 0, the capacity is not stored. alpar@1: * alpar@1: * The array parm contains description of the network to be generated: alpar@1: * alpar@1: * parm[0] not used alpar@1: * parm[1] (seed) random number seed (a positive integer) alpar@1: * parm[2] (a) frame size alpar@1: * parm[3] (b) depth alpar@1: * parm[4] (c1) minimal arc capacity alpar@1: * parm[5] (c2) maximal arc capacity alpar@1: * alpar@1: * RETURNS alpar@1: * alpar@1: * If the instance was successfully generated, the routine glp_netgen alpar@1: * returns zero; otherwise, if specified parameters are inconsistent, alpar@1: * the routine returns a non-zero error code. alpar@1: * alpar@1: * COMMENTS alpar@1: * alpar@1: * The generated network is as follows. It has b pieces of frames of alpar@1: * size a * a. (So alltogether the number of vertices is a * a * b) alpar@1: * alpar@1: * In each frame all the vertices are connected with their neighbours alpar@1: * (forth and back). In addition the vertices of a frame are connected alpar@1: * one to one with the vertices of next frame using a random permutation alpar@1: * of those vertices. alpar@1: * alpar@1: * The source is the lower left vertex of the first frame, the sink is alpar@1: * the upper right vertex of the b'th frame. alpar@1: * alpar@1: * t alpar@1: * +-------+ alpar@1: * | .| alpar@1: * | . | alpar@1: * / | / | alpar@1: * +-------+/ -+ b alpar@1: * | | |/. alpar@1: * a | -v- |/ alpar@1: * | | |/ alpar@1: * +-------+ 1 alpar@1: * s a alpar@1: * alpar@1: * The capacities are randomly chosen integers from the range of [c1,c2] alpar@1: * in the case of interconnecting edges, and c2 * a * a for the in-frame alpar@1: * edges. alpar@1: * alpar@1: * REFERENCES alpar@1: * alpar@1: * D.Goldfarb and M.D.Grigoriadis, "A computational comparison of the alpar@1: * Dinic and network simplex methods for maximum flow." Annals of Op. alpar@1: * Res. 13 (1988), pp. 83-123. alpar@1: * alpar@1: * U.Derigs and W.Meier, "Implementing Goldberg's max-flow algorithm: alpar@1: * A computational investigation." Zeitschrift fuer Operations Research alpar@1: * 33 (1989), pp. 383-403. */ alpar@1: alpar@1: typedef struct VERTEX alpar@1: { struct EDGE **edgelist; alpar@1: /* Pointer to the list of pointers to the adjacent edges. alpar@1: (No matter that to or from edges) */ alpar@1: struct EDGE **current; alpar@1: /* Pointer to the current edge */ alpar@1: int degree; alpar@1: /* Number of adjacent edges (both direction) */ alpar@1: int index; alpar@1: } vertex; alpar@1: alpar@1: typedef struct EDGE alpar@1: { int from; alpar@1: int to; alpar@1: int cap; alpar@1: /* Capacity */ alpar@1: } edge; alpar@1: alpar@1: typedef struct NETWORK alpar@1: { struct NETWORK *next, *prev; alpar@1: int vertnum; alpar@1: int edgenum; alpar@1: vertex *verts; alpar@1: /* Vertex array[1..vertnum] */ alpar@1: edge *edges; alpar@1: /* Edge array[1..edgenum] */ alpar@1: int source; alpar@1: /* Pointer to the source */ alpar@1: int sink; alpar@1: /* Pointer to the sink */ alpar@1: } network; alpar@1: alpar@1: struct csa alpar@1: { /* common storage area */ alpar@1: glp_graph *G; alpar@1: int *s, *t, a_cap; alpar@1: RNG *rand; alpar@1: network *N; alpar@1: int *Parr; alpar@1: int A, AA, C2AA, Ec; alpar@1: }; alpar@1: alpar@1: #define G (csa->G) alpar@1: #define s (csa->s) alpar@1: #define t (csa->t) alpar@1: #define a_cap (csa->a_cap) alpar@1: #define N (csa->N) alpar@1: #define Parr (csa->Parr) alpar@1: #define A (csa->A) alpar@1: #define AA (csa->AA) alpar@1: #define C2AA (csa->C2AA) alpar@1: #define Ec (csa->Ec) alpar@1: alpar@1: #undef random alpar@1: #define random(A) (int)(rng_unif_01(csa->rand) * (double)(A)) alpar@1: #define RANDOM(A, B) (int)(random((B) - (A) + 1) + (A)) alpar@1: #define sgn(A) (((A) > 0) ? 1 : ((A) == 0) ? 0 : -1) alpar@1: alpar@1: static void make_edge(struct csa *csa, int from, int to, int c1, int c2) alpar@1: { Ec++; alpar@1: N->edges[Ec].from = from; alpar@1: N->edges[Ec].to = to; alpar@1: N->edges[Ec].cap = RANDOM(c1, c2); alpar@1: return; alpar@1: } alpar@1: alpar@1: static void permute(struct csa *csa) alpar@1: { int i, j, tmp; alpar@1: for (i = 1; i < AA; i++) alpar@1: { j = RANDOM(i, AA); alpar@1: tmp = Parr[i]; alpar@1: Parr[i] = Parr[j]; alpar@1: Parr[j] = tmp; alpar@1: } alpar@1: return; alpar@1: } alpar@1: alpar@1: static void connect(struct csa *csa, int offset, int cv, int x1, int y1) alpar@1: { int cv1; alpar@1: cv1 = offset + (x1 - 1) * A + y1; alpar@1: Ec++; alpar@1: N->edges[Ec].from = cv; alpar@1: N->edges[Ec].to = cv1; alpar@1: N->edges[Ec].cap = C2AA; alpar@1: return; alpar@1: } alpar@1: alpar@1: static network *gen_rmf(struct csa *csa, int a, int b, int c1, int c2) alpar@1: { /* generates a network with a*a*b nodes and 6a*a*b-4ab-2a*a edges alpar@1: random_frame network: alpar@1: Derigs & Meier, Methods & Models of OR (1989), 33:383-403 */ alpar@1: int x, y, z, offset, cv; alpar@1: A = a; alpar@1: AA = a * a; alpar@1: C2AA = c2 * AA; alpar@1: Ec = 0; alpar@1: N = (network *)xmalloc(sizeof(network)); alpar@1: N->vertnum = AA * b; alpar@1: N->edgenum = 5 * AA * b - 4 * A * b - AA; alpar@1: N->edges = (edge *)xcalloc(N->edgenum + 1, sizeof(edge)); alpar@1: N->source = 1; alpar@1: N->sink = N->vertnum; alpar@1: Parr = (int *)xcalloc(AA + 1, sizeof(int)); alpar@1: for (x = 1; x <= AA; x++) alpar@1: Parr[x] = x; alpar@1: for (z = 1; z <= b; z++) alpar@1: { offset = AA * (z - 1); alpar@1: if (z != b) alpar@1: permute(csa); alpar@1: for (x = 1; x <= A; x++) alpar@1: { for (y = 1; y <= A; y++) alpar@1: { cv = offset + (x - 1) * A + y; alpar@1: if (z != b) alpar@1: make_edge(csa, cv, offset + AA + Parr[cv - offset], alpar@1: c1, c2); /* the intermediate edges */ alpar@1: if (y < A) alpar@1: connect(csa, offset, cv, x, y + 1); alpar@1: if (y > 1) alpar@1: connect(csa, offset, cv, x, y - 1); alpar@1: if (x < A) alpar@1: connect(csa, offset, cv, x + 1, y); alpar@1: if (x > 1) alpar@1: connect(csa, offset, cv, x - 1, y); alpar@1: } alpar@1: } alpar@1: } alpar@1: xfree(Parr); alpar@1: return N; alpar@1: } alpar@1: alpar@1: static void print_max_format(struct csa *csa, network *n, char *comm[], alpar@1: int dim) alpar@1: { /* prints a network heading with dim lines of comments (no \n alpar@1: needs at the ends) */ alpar@1: int i, vnum, e_num; alpar@1: edge *e; alpar@1: vnum = n->vertnum; alpar@1: e_num = n->edgenum; alpar@1: if (G == NULL) alpar@1: { for (i = 0; i < dim; i++) alpar@1: xprintf("c %s\n", comm[i]); alpar@1: xprintf("p max %7d %10d\n", vnum, e_num); alpar@1: xprintf("n %7d s\n", n->source); alpar@1: xprintf("n %7d t\n", n->sink); alpar@1: } alpar@1: else alpar@1: { glp_add_vertices(G, vnum); alpar@1: if (s != NULL) *s = n->source; alpar@1: if (t != NULL) *t = n->sink; alpar@1: } alpar@1: for (i = 1; i <= e_num; i++) alpar@1: { e = &n->edges[i]; alpar@1: if (G == NULL) alpar@1: xprintf("a %7d %7d %10d\n", e->from, e->to, (int)e->cap); alpar@1: else alpar@1: { glp_arc *a = glp_add_arc(G, e->from, e->to); alpar@1: if (a_cap >= 0) alpar@1: { double temp = (double)e->cap; alpar@1: memcpy((char *)a->data + a_cap, &temp, sizeof(double)); alpar@1: } alpar@1: } alpar@1: } alpar@1: return; alpar@1: } alpar@1: alpar@1: static void gen_free_net(network *n) alpar@1: { xfree(n->edges); alpar@1: xfree(n); alpar@1: return; alpar@1: } alpar@1: alpar@1: int glp_rmfgen(glp_graph *G_, int *_s, int *_t, int _a_cap, alpar@1: const int parm[1+5]) alpar@1: { struct csa _csa, *csa = &_csa; alpar@1: network *n; alpar@1: char comm[10][80], *com1[10]; alpar@1: int seed, a, b, c1, c2, ret; alpar@1: G = G_; alpar@1: s = _s; alpar@1: t = _t; alpar@1: a_cap = _a_cap; alpar@1: if (G != NULL) alpar@1: { if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double)) alpar@1: xerror("glp_rmfgen: a_cap = %d; invalid offset\n", a_cap); alpar@1: } alpar@1: seed = parm[1]; alpar@1: a = parm[2]; alpar@1: b = parm[3]; alpar@1: c1 = parm[4]; alpar@1: c2 = parm[5]; alpar@1: if (!(seed > 0 && 1 <= a && a <= 1000 && 1 <= b && b <= 1000 && alpar@1: 0 <= c1 && c1 <= c2 && c2 <= 1000)) alpar@1: { ret = 1; alpar@1: goto done; alpar@1: } alpar@1: if (G != NULL) alpar@1: { glp_erase_graph(G, G->v_size, G->a_size); alpar@1: glp_set_graph_name(G, "RMFGEN"); alpar@1: } alpar@1: csa->rand = rng_create_rand(); alpar@1: rng_init_rand(csa->rand, seed); alpar@1: n = gen_rmf(csa, a, b, c1, c2); alpar@1: sprintf(comm[0], "This file was generated by genrmf."); alpar@1: sprintf(comm[1], "The parameters are: a: %d b: %d c1: %d c2: %d", alpar@1: a, b, c1, c2); alpar@1: com1[0] = comm[0]; alpar@1: com1[1] = comm[1]; alpar@1: print_max_format(csa, n, com1, 2); alpar@1: gen_free_net(n); alpar@1: rng_delete_rand(csa->rand); alpar@1: ret = 0; alpar@1: done: return ret; alpar@1: } alpar@1: alpar@1: /**********************************************************************/ alpar@1: alpar@1: #if 0 alpar@1: int main(int argc, char *argv[]) alpar@1: { int seed, a, b, c1, c2, i, parm[1+5]; alpar@1: seed = 123; alpar@1: a = b = c1 = c2 = -1; alpar@1: for (i = 1; i < argc; i++) alpar@1: { if (strcmp(argv[i], "-seed") == 0) alpar@1: seed = atoi(argv[++i]); alpar@1: else if (strcmp(argv[i], "-a") == 0) alpar@1: a = atoi(argv[++i]); alpar@1: else if (strcmp(argv[i], "-b") == 0) alpar@1: b = atoi(argv[++i]); alpar@1: else if (strcmp(argv[i], "-c1") == 0) alpar@1: c1 = atoi(argv[++i]); alpar@1: else if (strcmp(argv[i], "-c2") == 0) alpar@1: c2 = atoi(argv[++i]); alpar@1: } alpar@1: if (a < 0 || b < 0 || c1 < 0 || c2 < 0) alpar@1: { xprintf("Usage:\n"); alpar@1: xprintf("genrmf [-seed seed] -a frame_size -b depth\n"); alpar@1: xprintf(" -c1 cap_range1 -c2 cap_range2\n"); alpar@1: } alpar@1: else alpar@1: { parm[1] = seed; alpar@1: parm[2] = a; alpar@1: parm[3] = b; alpar@1: parm[4] = c1; alpar@1: parm[5] = c2; alpar@1: glp_rmfgen(NULL, NULL, NULL, 0, parm); alpar@1: } alpar@1: return 0; alpar@1: } alpar@1: #endif alpar@1: alpar@1: /* eof */