COIN-OR::LEMON - Graph Library

source: lemon-benchmark/generators/netgen/netgen.c @ 11:cf6519daa7fa

Last change on this file since 11:cf6519daa7fa was 7:79d9c9f6c446, checked in by Alpar Juttner <alpar@…>, 14 years ago

Command line parameter support for netgen

File size: 16.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#include "main.h"
89
90/*** Private interfaces */
91
92#ifdef DEBUG
93#define PRIVATE
94#else
95#define PRIVATE static
96#endif
97
98#ifdef __STDC__
99PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */
100PRIVATE void create_assignment(long*);  /* create assignment problem */
101PRIVATE void sort_skeleton(int);        /* sorts skeleton chains */
102PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */
103PRIVATE void error_exit(long);          /* print error message and exit */
104#else
105PRIVATE void create_supply();           /* create supply nodes */
106PRIVATE void create_assignment();       /* create assignment problem */
107PRIVATE void sort_skeleton();           /* sorts skeleton chains */
108PRIVATE void pick_head();               /* chooses destination nodes for rubbish arcs */
109PRIVATE void error_exit();              /* print error message and exit */
110#endif
111
112/*** Private variables */
113
114static NODE nodes_left;
115static ARC arc_count;
116static NODE pred[MAXARCS];
117static NODE head[MAXARCS];
118static NODE tail[MAXARCS];
119
120
121/*** Local macros */
122
123#define MIN(x, y) ((x) < (y) ? (x) : (y))
124#define MAX(x, y) ((x) > (y) ? (x) : (y))
125#define SAVE_ARC(tail, head, cost, capacity)    /* records an arc where our caller can get it */ \
126  {                             \
127    FROM[arc_count] = tail;     \
128    TO  [arc_count] = head;     \
129    C   [arc_count] = cost;     \
130    U   [arc_count] = capacity; \
131    arc_count++;                \
132  }
133
134
135/*** Fortran callable interface routine */
136
137void netgen_(seed, parms, generated_nodes, generated_arcs)
138long* seed;                     /* pointer to random seed */
139long parms[PROBLEM_PARMS];      /* problem parameters */
140long* generated_nodes;          /* number of generated nodes */
141long* generated_arcs;           /* number of generated arcs */
142{
143  *generated_nodes = NODES;
144  if ((*generated_arcs = netgen(*seed, parms)) < 0)
145    error_exit(*generated_arcs);
146}
147
148
149/*** C callable interface routine */
150
151ARC netgen(seed, parms)
152long seed;                      /* random seed */
153long parms[];                   /* problem parameters */
154{
155  register NODE i,j,k;
156  NODE source;
157  NODE node;
158  NODE sinks_per_source;
159  NODE* sinks;
160  NODE it;
161  int chain_length;
162  COST cost;
163  CAPACITY cap;
164  INDEX_LIST handle;
165  int supply_per_sink;
166  int partial_supply;
167  int sort_count;
168
169
170/*** Perform sanity checks on the input */
171
172  if (seed <= 0)
173    return BAD_SEED;
174  if (NODES > MAXNODES || DENSITY > MAXARCS)
175    return TOO_BIG;
176  if ((NODES <= 0) ||
177      (NODES > DENSITY) ||
178      (SOURCES <= 0) ||
179      (SINKS <= 0) ||
180      (SOURCES + SINKS > NODES) ||
181      (MINCOST > MAXCOST) ||
182      (SUPPLY < SOURCES) ||
183      (TSOURCES > SOURCES) ||
184      (TSINKS > SINKS) ||
185      (HICOST < 0 || HICOST > 100) ||
186      (CAPACITATED < 0 || CAPACITATED > 100) ||
187      (MINCAP > MAXCAP))
188    return BAD_PARMS;
189
190
191/*** Do a little bit of setting up. */
192
193  set_random(seed);
194
195  arc_count = 0;
196  nodes_left = NODES - SINKS + TSINKS;
197
198  if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
199      (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
200       SOURCES == SUPPLY) {
201    create_assignment(parms);
202    return arc_count;
203  }
204
205  (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */
206
207  create_supply((NODE)SOURCES, (CAPACITY)SUPPLY);
208
209
210/*** Form most of the network skeleton.  First, 60% of the transshipment
211 *** nodes are divided evenly among the various sources; the remainder
212 *** are chained onto the end of the chains belonging to random sources.
213 ***/
214
215  for (i = 1; i <= SOURCES; i++)        /* point SOURCES at themselves */
216    pred[i] = i;
217  handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS));
218  source = 1;
219  for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) {
220    node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
221    pred[node] = pred[source];
222    pred[source] = node;
223    if (++source > SOURCES)
224      source = 1;
225  }
226  for ( ; i > 0; --i) {
227    node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
228    source = ng_random(1L, SOURCES);
229    pred[node] = pred[source];
230    pred[source] = node;
231  }
232  free_index_list(handle);
233
234
235/*** For each source chain, hook it to an "appropriate" number of sinks,
236 *** place capacities and costs on the skeleton edges, and then call
237 *** pick_head to add a bunch of rubbish edges at each node on the chain.
238 ***/
239
240  for (source = 1; source <= SOURCES; source++) {
241    sort_count = 0;
242    node = pred[source];
243    while (node != source) {
244      sort_count++;
245      head[sort_count] = node;
246      node = tail[sort_count] = pred[node];
247    }
248    if ((NODES-SOURCES-SINKS) == 0)
249      sinks_per_source = SINKS/SOURCES + 1;
250    else
251/* changing to handle overflows with large n; Mar 18 -- jc */
252      sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS);
253    sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS));
254    sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE));
255    handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1));
256    for (i = 0; i < sinks_per_source; i++) {
257      sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
258    }
259    if (source == SOURCES && index_size(handle) > 0) {
260      sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE));
261      while (index_size(handle) > 0) {
262        j = choose_index(handle, 1);
263        if (B[j] == 0)
264          sinks[sinks_per_source++] = j;
265      }
266    }
267    free_index_list(handle);
268
269    chain_length = sort_count;
270    supply_per_sink = B[source-1] / sinks_per_source;
271    k = pred[source];
272    for (i = 0; i < sinks_per_source; i++) {
273      sort_count++;
274      partial_supply = ng_random(1L, (long)supply_per_sink);
275      j = ng_random(0L, (long)sinks_per_source - 1);
276      tail[sort_count] = k;
277      head[sort_count] = sinks[i] + 1;
278      B[sinks[i]] -= partial_supply;
279      B[sinks[j]] -= (supply_per_sink - partial_supply);
280      k = source;
281      for (j = ng_random(1L, (long)chain_length); j > 0; j--)
282        k = pred[k];
283    }
284    B[sinks[0]] -= (B[source-1] % sinks_per_source);
285    free((void *)sinks);
286
287    sort_skeleton(sort_count);
288    tail[sort_count+1] = 0;
289    for (i = 1; i <= sort_count; ) {
290      handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
291      remove_index(handle, (INDEX)tail[i]);
292      it = tail[i];
293      while (it == tail[i]) {
294        remove_index(handle, (INDEX)head[i]);
295        cap = SUPPLY;
296        if (ng_random(1L, 100L) <= CAPACITATED)
297          cap = MAX(B[source-1], MINCAP);
298        cost = MAXCOST;
299        if (ng_random(1L, 100L) > HICOST)
300          cost = ng_random(MINCOST, MAXCOST);
301        SAVE_ARC(it,head[i],cost,cap);
302        i++;
303      }
304      pick_head(parms, handle, it);
305      free_index_list(handle);
306    }
307  }
308
309
310/*** Add more rubbish edges out of the transshipment sinks. */
311
312  for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) {
313    handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
314    remove_index(handle, (INDEX)i);
315    pick_head(parms, handle, i);
316    free_index_list(handle);
317  }
318
319  return arc_count;
320}
321
322
323PRIVATE void create_supply(sources, supply)
324NODE sources;
325CAPACITY supply;
326{
327  CAPACITY supply_per_source = supply / sources;
328  CAPACITY partial_supply;
329  NODE i;
330
331  for (i = 0; i < sources; i++) {
332    B[i] += (partial_supply = ng_random(1L, (long)supply_per_source));
333    B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply;
334  }
335  B[ng_random(0L, (long)(sources - 1))] += supply % sources;
336}
337
338
339PRIVATE void create_assignment(parms)
340long parms[];
341{
342  INDEX_LIST skeleton, handle;
343  INDEX index;
344  NODE source;
345
346  for (source = 0; source < NODES/2; source++)
347    B[source] = 1;
348  for ( ; source < NODES; source++)
349    B[source] = -1;
350
351  skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
352  for (source = 1; source <= NODES/2; source++) {
353    index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton)));
354    SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1);
355    handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
356    remove_index(handle, index);
357    pick_head(parms, handle, source);
358    free_index_list(handle);
359  }
360  free_index_list(skeleton);
361}
362
363
364PRIVATE void sort_skeleton(sort_count)          /* Shell sort */
365int sort_count;
366{
367  int m,i,j,k;
368  int temp;
369
370  m = sort_count;
371  while ((m /= 2) != 0) {
372    k = sort_count - m;
373    for (j = 1; j <= k; j++) {
374      i = j;
375      while (i >= 1 && tail[i] > tail[i+m]) {
376        temp = tail[i];
377        tail[i] = tail[i+m];
378        tail[i+m] = temp;
379        temp = head[i];
380        head[i] = head[i+m];
381        head[i+m] = temp;
382        i -= m;
383      }
384    }
385  }
386}
387
388
389PRIVATE void pick_head(parms, handle, desired_tail)
390long parms[];
391INDEX_LIST handle;
392NODE desired_tail;
393{
394  NODE non_sources = NODES - SOURCES + TSOURCES;
395
396/* changing Aug 29 -- jc
397  ARC remaining_arcs = DENSITY - arc_count;
398*/
399  int  remaining_arcs = (int) DENSITY - (int) arc_count;
400
401  INDEX index;
402  int limit;
403  long upper_bound;
404  CAPACITY cap;
405
406/* changing Aug 29 -- jc
407*/
408  nodes_left--;
409  if ((2 * (int) nodes_left) >= (int) remaining_arcs)
410    return;
411
412  if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) {
413    limit = non_sources;
414  } else {
415    upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1);
416    do {
417      limit = ng_random(1L, upper_bound);
418      if (nodes_left == 0)
419        limit = remaining_arcs;
420/* changing to handle overflows with large n; Mar 18 -- jc */
421    } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit));
422  }
423
424  for ( ; limit > 0; limit--) {
425    index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle)));
426    cap = SUPPLY;
427    if (ng_random(1L, 100L) <= CAPACITATED)
428      cap = ng_random(MINCAP, MAXCAP);
429
430/* adding Aug 29 -- jc */
431if ((1 <= index) && (index <= NODES)) {
432    SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap);
433    }
434
435  }
436}
437
438
439/*** Print an appropriate error message and then exit with a nonzero code. */
440
441PRIVATE void error_exit(rc)
442long rc;
443{
444  switch (rc) {
445    case BAD_SEED:
446      fprintf(stderr, "NETGEN requires a positive random seed\n");
447      break;
448    case TOO_BIG:
449      fprintf(stderr, "Problem too large for generator\n");
450      break;
451    case BAD_PARMS:
452      fprintf(stderr, "Inconsistent parameter settings - check the input\n");
453      break;
454    case ALLOCATION_FAILURE:
455      fprintf(stderr, "Memory allocation failure\n");
456      break;
457    default:
458      fprintf(stderr, "Internal error\n");
459      break;
460  }
461  exit(1000 - (int)rc);
462}
463
464#ifdef DIMACS                   /* generates network on standard output */
465
466#define READ(v)                         /* read one variable using scanf */     \
467        switch( scanf("%ld", &v) ) {                                            \
468                case 1:                                                         \
469                        break;                                                  \
470                default:                                                        \
471                        exit(0);                                                \
472                }
473
474int orig_main(long seed,long problem,long *parms)
475{
476  long arcs;
477  int i;
478
479/*** Read problem parameters and generate networks */
480  {
481    printf("c NETGEN flow network generator (C version)\n");
482    printf("c  Problem %2ld input parameters\n", problem);
483    printf("c  ---------------------------\n");
484    printf("c   Random seed:          %10ld\n",   seed);
485    printf("c   Number of nodes:      %10ld\n",   NODES);
486    printf("c   Source nodes:         %10ld\n",   SOURCES);
487    printf("c   Sink nodes:           %10ld\n",   SINKS);
488    printf("c   Number of arcs:       %10ld\n",   DENSITY);
489    printf("c   Minimum arc cost:     %10ld\n",   MINCOST);
490    printf("c   Maximum arc cost:     %10ld\n",   MAXCOST);
491    printf("c   Total supply:         %10ld\n",   SUPPLY);
492    printf("c   Transshipment -\n");
493    printf("c     Sources:            %10ld\n",   TSOURCES);
494    printf("c     Sinks:              %10ld\n",   TSINKS);
495    printf("c   Skeleton arcs -\n");
496    printf("c     With max cost:      %10ld%%\n", HICOST);
497    printf("c     Capacitated:        %10ld%%\n", CAPACITATED);
498    printf("c   Minimum arc capacity: %10ld\n",   MINCAP);
499    printf("c   Maximum arc capacity: %10ld\n",   MAXCAP);
500
501    if ((arcs = netgen(seed, parms)) < 0)
502      error_exit(arcs);
503    if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
504        (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
505         SOURCES == SUPPLY) {
506      printf("c\n");
507      printf("c  *** Assignment ***\n");
508      printf("c\n");
509      printf("p asn %ld %ld\n", NODES, arcs);
510      for (i = 0; i < NODES; i++) {
511        if (B[i] > 0)
512          printf("n %ld\n", i + 1);
513      }
514      for (i = 0; i < arcs; i++) {
515        printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]);
516      }
517    } else
518    if (MINCOST == 1 && MAXCOST == 1) {
519      printf("c\n");
520      printf("c  *** Maximum flow ***\n");
521      printf("c\n");
522      printf("p max %ld %ld\n", NODES, arcs);
523      for (i = 0; i < NODES; i++) {
524        if (B[i] > 0)
525          printf("n %ld s\n", i + 1);
526        else
527        if (B[i] < 0)
528          printf("n %ld t\n", i + 1);
529      }
530      for (i = 0; i < arcs; i++) {
531        printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]);
532      }
533    } else {
534      printf("c\n");
535      printf("c  *** Minimum cost flow ***\n");
536      printf("c\n");
537      printf("p min %ld %ld\n", NODES, arcs);
538      for (i = 0; i < NODES; i++) {
539        if (B[i] != 0)
540          printf("n %ld %ld\n", i + 1, B[i]);
541      }
542      for (i = 0; i < arcs; i++) {
543        printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]);
544      }
545    }
546  }
547  return 0;
548}
549
550#endif
Note: See TracBrowser for help on using the repository browser.