COIN-OR::LEMON - Graph Library

source: lemon-benchmark/generators/netgen/netgen.c @ 6:a3ef33a8694a

Last change on this file since 6:a3ef33a8694a was 6:a3ef33a8694a, checked in by Alpar Juttner <alpar@…>, 9 years ago

Add netgen generator

File size: 17.5 KB
Line 
1/*** Copyright 1989 Norbert Schlenker.  All rights reserved.
2
3 *** This software is distributed subject to the following provisions:
4 ***    - this notice may not be removed;
5 ***    - you may modify the source code, as long as redistributed
6 ***      versions have their modifications clearly marked;
7 ***    - no charge, other than a nominal copying fee, may be made
8 ***      when providing copies of this source code to others;
9 ***    - if this source code is used as part of a product which is
10 ***      distributed only as a binary, a copy of this source code
11 ***      must be included in the distribution.
12 ***
13 *** Unlike the GNU GPL, use of this code does not obligate you to
14 *** disclose your own proprietary source code.
15
16 *** The author of this software provides no warranty, express or
17 *** implied, as to its utility or correctness.  That said, reports
18 *** of bugs or compatibility problems will be gladly received by
19 *** nfs@princeton.edu, and fixes will be attempted.
20 ***/
21
22
23/*** netgen - C version of the standard NETGEN network generator
24 ***          This program is a functional equivalent of the
25 ***          standard network generator NETGEN described in:
26 ***            Klingman, D., A. Napier, and J. Stutz, "NETGEN:  A Program
27 ***              for Generating Large Scale Capacitated Assignment,
28 ***              Transportation, and Minimum Cost Flow Network Problems",
29 ***              Management Science 20, 5, 814-821 (1974)
30 ***
31 ***          This software provides a number of interfaces for use by
32 ***          network solvers.  Standard call interfaces are supplied for
33 ***          use by (Unix) C and Fortran solvers, with generation parameters
34 ***          passed into the generator and the flow network passed back to
35 ***          the solver via large external (COMMON in Fortran) arrays.
36 ***          For the DIMACS challenge, this code will produce output files
37 ***          in the appropriate format for later reading by solvers.
38 ***          Undefine the symbol DIMACS when using the call interface.
39 ***
40 ***          The generator produces exact duplicates of the networks
41 ***          made by the Fortran code (even though that means bugs
42 ***          are being perpetuated). It is faster by orders of magnitude
43 ***          in generating large networks, primarily by imposing the
44 ***          notion of the abstract data type INDEX_LIST and implementing
45 ***          the type operations in a reasonably efficient fashion.
46 ***/
47
48/*** Generates transportation problems if:
49 ***    SOURCES+SINKS == NODES && TSOURCES == TSINKS == 0
50 ***
51 *** Generates assignment problems if above conditions are satisfied, and:
52 ***    SOURCES == SINKS && SUPPLY == SOURCES
53 ***
54 *** Generates maximum flow problems if not an assignment problem and:
55 ***    MINCOST == MAXCOST == 1
56
57 *** Implementation notes:
58 ***
59 ***    This file contains both a Fortran and a C interface. The
60 ***    Fortran interface is suffixed with an underscore to make it
61 ***    callable in the normal fashion from Fortran (a Unix convention).
62 ***
63 ***    Because Fortran has no facility for pointers, the common arrays
64 ***    are statically allocated.  Static allocation has nothing to recommend
65 ***    it except for the need for a Fortran interface.
66 ***
67 ***    This software expects input parameters to be long integers
68 ***    (in the sense of C); that means no INTEGER*2 from Fortran callers.
69 ***
70 ***    Compiling with -DDIMACS produces a program that reads problem
71 ***    parameters, generates the appropriate problem, and prints it.
72 ***
73 ***    Compiling with -DDEBUG produces code with externally visible
74 ***    procedure names, useful for debugging and profiling.
75 ***/
76
77
78/*** System interfaces */
79
80#include <stdio.h>
81
82
83/*** Public interfaces */
84
85#define ALLOCATE_NETWORK
86#include "netgen.h"
87
88#define PROBLEM_PARMS 13                /* aliases for generation parameters */
89#define NODES       parms[0]            /* number of nodes */
90#define SOURCES     parms[1]            /* number of sources (including transshipment) */
91#define SINKS       parms[2]            /* number of sinks (including transshipment) */
92#define DENSITY     parms[3]            /* number of (requested) arcs */
93#define MINCOST     parms[4]            /* minimum cost of arcs */
94#define MAXCOST     parms[5]            /* maximum cost of arcs */
95#define SUPPLY      parms[6]            /* total supply */
96#define TSOURCES    parms[7]            /* transshipment sources */
97#define TSINKS      parms[8]            /* transshipment sinks */
98#define HICOST      parms[9]            /* percent of skeleton arcs given maximum cost */
99#define CAPACITATED parms[10]           /* percent of arcs to be capacitated */
100#define MINCAP      parms[11]           /* minimum capacity for capacitated arcs */
101#define MAXCAP      parms[12]           /* maximum capacity for capacitated arcs */
102
103
104/*** Private interfaces */
105
106#ifdef DEBUG
107#define PRIVATE
108#else
109#define PRIVATE static
110#endif
111
112#ifdef __STDC__
113PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */
114PRIVATE void create_assignment(long*);  /* create assignment problem */
115PRIVATE void sort_skeleton(int);        /* sorts skeleton chains */
116PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */
117PRIVATE void error_exit(long);          /* print error message and exit */
118#else
119PRIVATE void create_supply();           /* create supply nodes */
120PRIVATE void create_assignment();       /* create assignment problem */
121PRIVATE void sort_skeleton();           /* sorts skeleton chains */
122PRIVATE void pick_head();               /* chooses destination nodes for rubbish arcs */
123PRIVATE void error_exit();              /* print error message and exit */
124#endif
125
126/*** Private variables */
127
128static NODE nodes_left;
129static ARC arc_count;
130static NODE pred[MAXARCS];
131static NODE head[MAXARCS];
132static NODE tail[MAXARCS];
133
134
135/*** Local macros */
136
137#define MIN(x, y) ((x) < (y) ? (x) : (y))
138#define MAX(x, y) ((x) > (y) ? (x) : (y))
139#define SAVE_ARC(tail, head, cost, capacity)    /* records an arc where our caller can get it */ \
140  {                             \
141    FROM[arc_count] = tail;     \
142    TO  [arc_count] = head;     \
143    C   [arc_count] = cost;     \
144    U   [arc_count] = capacity; \
145    arc_count++;                \
146  }
147
148
149/*** Fortran callable interface routine */
150
151void netgen_(seed, parms, generated_nodes, generated_arcs)
152long* seed;                     /* pointer to random seed */
153long parms[PROBLEM_PARMS];      /* problem parameters */
154long* generated_nodes;          /* number of generated nodes */
155long* generated_arcs;           /* number of generated arcs */
156{
157  *generated_nodes = NODES;
158  if ((*generated_arcs = netgen(*seed, parms)) < 0)
159    error_exit(*generated_arcs);
160}
161
162
163/*** C callable interface routine */
164
165ARC netgen(seed, parms)
166long seed;                      /* random seed */
167long parms[];                   /* problem parameters */
168{
169  register NODE i,j,k;
170  NODE source;
171  NODE node;
172  NODE sinks_per_source;
173  NODE* sinks;
174  NODE it;
175  int chain_length;
176  COST cost;
177  CAPACITY cap;
178  INDEX_LIST handle;
179  int supply_per_sink;
180  int partial_supply;
181  int sort_count;
182
183
184/*** Perform sanity checks on the input */
185
186  if (seed <= 0)
187    return BAD_SEED;
188  if (NODES > MAXNODES || DENSITY > MAXARCS)
189    return TOO_BIG;
190  if ((NODES <= 0) ||
191      (NODES > DENSITY) ||
192      (SOURCES <= 0) ||
193      (SINKS <= 0) ||
194      (SOURCES + SINKS > NODES) ||
195      (MINCOST > MAXCOST) ||
196      (SUPPLY < SOURCES) ||
197      (TSOURCES > SOURCES) ||
198      (TSINKS > SINKS) ||
199      (HICOST < 0 || HICOST > 100) ||
200      (CAPACITATED < 0 || CAPACITATED > 100) ||
201      (MINCAP > MAXCAP))
202    return BAD_PARMS;
203
204
205/*** Do a little bit of setting up. */
206
207  set_random(seed);
208
209  arc_count = 0;
210  nodes_left = NODES - SINKS + TSINKS;
211
212  if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
213      (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
214       SOURCES == SUPPLY) {
215    create_assignment(parms);
216    return arc_count;
217  }
218
219  (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */
220
221  create_supply((NODE)SOURCES, (CAPACITY)SUPPLY);
222
223
224/*** Form most of the network skeleton.  First, 60% of the transshipment
225 *** nodes are divided evenly among the various sources; the remainder
226 *** are chained onto the end of the chains belonging to random sources.
227 ***/
228
229  for (i = 1; i <= SOURCES; i++)        /* point SOURCES at themselves */
230    pred[i] = i;
231  handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS));
232  source = 1;
233  for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) {
234    node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
235    pred[node] = pred[source];
236    pred[source] = node;
237    if (++source > SOURCES)
238      source = 1;
239  }
240  for ( ; i > 0; --i) {
241    node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
242    source = ng_random(1L, SOURCES);
243    pred[node] = pred[source];
244    pred[source] = node;
245  }
246  free_index_list(handle);
247
248
249/*** For each source chain, hook it to an "appropriate" number of sinks,
250 *** place capacities and costs on the skeleton edges, and then call
251 *** pick_head to add a bunch of rubbish edges at each node on the chain.
252 ***/
253
254  for (source = 1; source <= SOURCES; source++) {
255    sort_count = 0;
256    node = pred[source];
257    while (node != source) {
258      sort_count++;
259      head[sort_count] = node;
260      node = tail[sort_count] = pred[node];
261    }
262    if ((NODES-SOURCES-SINKS) == 0)
263      sinks_per_source = SINKS/SOURCES + 1;
264    else
265/* changing to handle overflows with large n; Mar 18 -- jc */
266      sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS);
267    sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS));
268    sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE));
269    handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1));
270    for (i = 0; i < sinks_per_source; i++) {
271      sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
272    }
273    if (source == SOURCES && index_size(handle) > 0) {
274      sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE));
275      while (index_size(handle) > 0) {
276        j = choose_index(handle, 1);
277        if (B[j] == 0)
278          sinks[sinks_per_source++] = j;
279      }
280    }
281    free_index_list(handle);
282
283    chain_length = sort_count;
284    supply_per_sink = B[source-1] / sinks_per_source;
285    k = pred[source];
286    for (i = 0; i < sinks_per_source; i++) {
287      sort_count++;
288      partial_supply = ng_random(1L, (long)supply_per_sink);
289      j = ng_random(0L, (long)sinks_per_source - 1);
290      tail[sort_count] = k;
291      head[sort_count] = sinks[i] + 1;
292      B[sinks[i]] -= partial_supply;
293      B[sinks[j]] -= (supply_per_sink - partial_supply);
294      k = source;
295      for (j = ng_random(1L, (long)chain_length); j > 0; j--)
296        k = pred[k];
297    }
298    B[sinks[0]] -= (B[source-1] % sinks_per_source);
299    free((void *)sinks);
300
301    sort_skeleton(sort_count);
302    tail[sort_count+1] = 0;
303    for (i = 1; i <= sort_count; ) {
304      handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
305      remove_index(handle, (INDEX)tail[i]);
306      it = tail[i];
307      while (it == tail[i]) {
308        remove_index(handle, (INDEX)head[i]);
309        cap = SUPPLY;
310        if (ng_random(1L, 100L) <= CAPACITATED)
311          cap = MAX(B[source-1], MINCAP);
312        cost = MAXCOST;
313        if (ng_random(1L, 100L) > HICOST)
314          cost = ng_random(MINCOST, MAXCOST);
315        SAVE_ARC(it,head[i],cost,cap);
316        i++;
317      }
318      pick_head(parms, handle, it);
319      free_index_list(handle);
320    }
321  }
322
323
324/*** Add more rubbish edges out of the transshipment sinks. */
325
326  for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) {
327    handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
328    remove_index(handle, (INDEX)i);
329    pick_head(parms, handle, i);
330    free_index_list(handle);
331  }
332
333  return arc_count;
334}
335
336
337PRIVATE void create_supply(sources, supply)
338NODE sources;
339CAPACITY supply;
340{
341  CAPACITY supply_per_source = supply / sources;
342  CAPACITY partial_supply;
343  NODE i;
344
345  for (i = 0; i < sources; i++) {
346    B[i] += (partial_supply = ng_random(1L, (long)supply_per_source));
347    B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply;
348  }
349  B[ng_random(0L, (long)(sources - 1))] += supply % sources;
350}
351
352
353PRIVATE void create_assignment(parms)
354long parms[];
355{
356  INDEX_LIST skeleton, handle;
357  INDEX index;
358  NODE source;
359
360  for (source = 0; source < NODES/2; source++)
361    B[source] = 1;
362  for ( ; source < NODES; source++)
363    B[source] = -1;
364
365  skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
366  for (source = 1; source <= NODES/2; source++) {
367    index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton)));
368    SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1);
369    handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
370    remove_index(handle, index);
371    pick_head(parms, handle, source);
372    free_index_list(handle);
373  }
374  free_index_list(skeleton);
375}
376
377
378PRIVATE void sort_skeleton(sort_count)          /* Shell sort */
379int sort_count;
380{
381  int m,i,j,k;
382  int temp;
383
384  m = sort_count;
385  while ((m /= 2) != 0) {
386    k = sort_count - m;
387    for (j = 1; j <= k; j++) {
388      i = j;
389      while (i >= 1 && tail[i] > tail[i+m]) {
390        temp = tail[i];
391        tail[i] = tail[i+m];
392        tail[i+m] = temp;
393        temp = head[i];
394        head[i] = head[i+m];
395        head[i+m] = temp;
396        i -= m;
397      }
398    }
399  }
400}
401
402
403PRIVATE void pick_head(parms, handle, desired_tail)
404long parms[];
405INDEX_LIST handle;
406NODE desired_tail;
407{
408  NODE non_sources = NODES - SOURCES + TSOURCES;
409
410/* changing Aug 29 -- jc
411  ARC remaining_arcs = DENSITY - arc_count;
412*/
413  int  remaining_arcs = (int) DENSITY - (int) arc_count;
414
415  INDEX index;
416  int limit;
417  long upper_bound;
418  CAPACITY cap;
419
420/* changing Aug 29 -- jc
421*/
422  nodes_left--;
423  if ((2 * (int) nodes_left) >= (int) remaining_arcs)
424    return;
425
426  if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) {
427    limit = non_sources;
428  } else {
429    upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1);
430    do {
431      limit = ng_random(1L, upper_bound);
432      if (nodes_left == 0)
433        limit = remaining_arcs;
434/* changing to handle overflows with large n; Mar 18 -- jc */
435    } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit));
436  }
437
438  for ( ; limit > 0; limit--) {
439    index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle)));
440    cap = SUPPLY;
441    if (ng_random(1L, 100L) <= CAPACITATED)
442      cap = ng_random(MINCAP, MAXCAP);
443
444/* adding Aug 29 -- jc */
445if ((1 <= index) && (index <= NODES)) {
446    SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap);
447    }
448
449  }
450}
451
452
453/*** Print an appropriate error message and then exit with a nonzero code. */
454
455PRIVATE void error_exit(rc)
456long rc;
457{
458  switch (rc) {
459    case BAD_SEED:
460      fprintf(stderr, "NETGEN requires a positive random seed\n");
461      break;
462    case TOO_BIG:
463      fprintf(stderr, "Problem too large for generator\n");
464      break;
465    case BAD_PARMS:
466      fprintf(stderr, "Inconsistent parameter settings - check the input\n");
467      break;
468    case ALLOCATION_FAILURE:
469      fprintf(stderr, "Memory allocation failure\n");
470      break;
471    default:
472      fprintf(stderr, "Internal error\n");
473      break;
474  }
475  exit(1000 - (int)rc);
476}
477
478#ifdef DIMACS                   /* generates network on standard output */
479
480#define READ(v)                         /* read one variable using scanf */     \
481        switch( scanf("%ld", &v) ) {                                            \
482                case 1:                                                         \
483                        break;                                                  \
484                default:                                                        \
485                        exit(0);                                                \
486                }
487
488int main()
489{
490  long seed;
491  long problem;
492  long parms[PROBLEM_PARMS];
493  long arcs;
494  int i;
495
496/*** Read problem parameters and generate networks */
497
498  while (1) {
499    READ(seed);
500    if (seed <= 0) exit(0);
501    READ(problem);
502    if (problem <= 0) exit(0);
503    for (i = 0; i < PROBLEM_PARMS; i++)
504      READ(parms[i]);
505    printf("c NETGEN flow network generator (C version)\n");
506    printf("c  Problem %2ld input parameters\n", problem);
507    printf("c  ---------------------------\n");
508    printf("c   Random seed:          %10ld\n",   seed);
509    printf("c   Number of nodes:      %10ld\n",   NODES);
510    printf("c   Source nodes:         %10ld\n",   SOURCES);
511    printf("c   Sink nodes:           %10ld\n",   SINKS);
512    printf("c   Number of arcs:       %10ld\n",   DENSITY);
513    printf("c   Minimum arc cost:     %10ld\n",   MINCOST);
514    printf("c   Maximum arc cost:     %10ld\n",   MAXCOST);
515    printf("c   Total supply:         %10ld\n",   SUPPLY);
516    printf("c   Transshipment -\n");
517    printf("c     Sources:            %10ld\n",   TSOURCES);
518    printf("c     Sinks:              %10ld\n",   TSINKS);
519    printf("c   Skeleton arcs -\n");
520    printf("c     With max cost:      %10ld%%\n", HICOST);
521    printf("c     Capacitated:        %10ld%%\n", CAPACITATED);
522    printf("c   Minimum arc capacity: %10ld\n",   MINCAP);
523    printf("c   Maximum arc capacity: %10ld\n",   MAXCAP);
524
525    if ((arcs = netgen(seed, parms)) < 0)
526      error_exit(arcs);
527    if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
528        (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
529         SOURCES == SUPPLY) {
530      printf("c\n");
531      printf("c  *** Assignment ***\n");
532      printf("c\n");
533      printf("p asn %ld %ld\n", NODES, arcs);
534      for (i = 0; i < NODES; i++) {
535        if (B[i] > 0)
536          printf("n %ld\n", i + 1);
537      }
538      for (i = 0; i < arcs; i++) {
539        printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]);
540      }
541    } else
542    if (MINCOST == 1 && MAXCOST == 1) {
543      printf("c\n");
544      printf("c  *** Maximum flow ***\n");
545      printf("c\n");
546      printf("p max %ld %ld\n", NODES, arcs);
547      for (i = 0; i < NODES; i++) {
548        if (B[i] > 0)
549          printf("n %ld s\n", i + 1);
550        else
551        if (B[i] < 0)
552          printf("n %ld t\n", i + 1);
553      }
554      for (i = 0; i < arcs; i++) {
555        printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]);
556      }
557    } else {
558      printf("c\n");
559      printf("c  *** Minimum cost flow ***\n");
560      printf("c\n");
561      printf("p min %ld %ld\n", NODES, arcs);
562      for (i = 0; i < NODES; i++) {
563        if (B[i] != 0)
564          printf("n %ld %ld\n", i + 1, B[i]);
565      }
566      for (i = 0; i < arcs; i++) {
567        printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]);
568      }
569    }
570  }
571  return 0;
572}
573
574#endif
Note: See TracBrowser for help on using the repository browser.