COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpnet05.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 11.0 KB
Line 
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
117typedef 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
128typedef struct EDGE
129{     int from;
130      int to;
131      int cap;
132      /* Capacity */
133} edge;
134
135typedef 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
149struct 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
175static 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
183static 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
194static 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
204static 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
247static 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
282static void gen_free_net(network *n)
283{     xfree(n->edges);
284      xfree(n);
285      return;
286}
287
288int 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;
328done: return ret;
329}
330
331/**********************************************************************/
332
333#if 0
334int 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 */
Note: See TracBrowser for help on using the repository browser.