1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/generators/netgen/netgen.c Fri Nov 26 19:23:47 2010 +0100
1.3 @@ -0,0 +1,574 @@
1.4 +/*** Copyright 1989 Norbert Schlenker. All rights reserved.
1.5 +
1.6 + *** This software is distributed subject to the following provisions:
1.7 + *** - this notice may not be removed;
1.8 + *** - you may modify the source code, as long as redistributed
1.9 + *** versions have their modifications clearly marked;
1.10 + *** - no charge, other than a nominal copying fee, may be made
1.11 + *** when providing copies of this source code to others;
1.12 + *** - if this source code is used as part of a product which is
1.13 + *** distributed only as a binary, a copy of this source code
1.14 + *** must be included in the distribution.
1.15 + ***
1.16 + *** Unlike the GNU GPL, use of this code does not obligate you to
1.17 + *** disclose your own proprietary source code.
1.18 +
1.19 + *** The author of this software provides no warranty, express or
1.20 + *** implied, as to its utility or correctness. That said, reports
1.21 + *** of bugs or compatibility problems will be gladly received by
1.22 + *** nfs@princeton.edu, and fixes will be attempted.
1.23 + ***/
1.24 +
1.25 +
1.26 +/*** netgen - C version of the standard NETGEN network generator
1.27 + *** This program is a functional equivalent of the
1.28 + *** standard network generator NETGEN described in:
1.29 + *** Klingman, D., A. Napier, and J. Stutz, "NETGEN: A Program
1.30 + *** for Generating Large Scale Capacitated Assignment,
1.31 + *** Transportation, and Minimum Cost Flow Network Problems",
1.32 + *** Management Science 20, 5, 814-821 (1974)
1.33 + ***
1.34 + *** This software provides a number of interfaces for use by
1.35 + *** network solvers. Standard call interfaces are supplied for
1.36 + *** use by (Unix) C and Fortran solvers, with generation parameters
1.37 + *** passed into the generator and the flow network passed back to
1.38 + *** the solver via large external (COMMON in Fortran) arrays.
1.39 + *** For the DIMACS challenge, this code will produce output files
1.40 + *** in the appropriate format for later reading by solvers.
1.41 + *** Undefine the symbol DIMACS when using the call interface.
1.42 + ***
1.43 + *** The generator produces exact duplicates of the networks
1.44 + *** made by the Fortran code (even though that means bugs
1.45 + *** are being perpetuated). It is faster by orders of magnitude
1.46 + *** in generating large networks, primarily by imposing the
1.47 + *** notion of the abstract data type INDEX_LIST and implementing
1.48 + *** the type operations in a reasonably efficient fashion.
1.49 + ***/
1.50 +
1.51 +/*** Generates transportation problems if:
1.52 + *** SOURCES+SINKS == NODES && TSOURCES == TSINKS == 0
1.53 + ***
1.54 + *** Generates assignment problems if above conditions are satisfied, and:
1.55 + *** SOURCES == SINKS && SUPPLY == SOURCES
1.56 + ***
1.57 + *** Generates maximum flow problems if not an assignment problem and:
1.58 + *** MINCOST == MAXCOST == 1
1.59 +
1.60 + *** Implementation notes:
1.61 + ***
1.62 + *** This file contains both a Fortran and a C interface. The
1.63 + *** Fortran interface is suffixed with an underscore to make it
1.64 + *** callable in the normal fashion from Fortran (a Unix convention).
1.65 + ***
1.66 + *** Because Fortran has no facility for pointers, the common arrays
1.67 + *** are statically allocated. Static allocation has nothing to recommend
1.68 + *** it except for the need for a Fortran interface.
1.69 + ***
1.70 + *** This software expects input parameters to be long integers
1.71 + *** (in the sense of C); that means no INTEGER*2 from Fortran callers.
1.72 + ***
1.73 + *** Compiling with -DDIMACS produces a program that reads problem
1.74 + *** parameters, generates the appropriate problem, and prints it.
1.75 + ***
1.76 + *** Compiling with -DDEBUG produces code with externally visible
1.77 + *** procedure names, useful for debugging and profiling.
1.78 + ***/
1.79 +
1.80 +
1.81 +/*** System interfaces */
1.82 +
1.83 +#include <stdio.h>
1.84 +
1.85 +
1.86 +/*** Public interfaces */
1.87 +
1.88 +#define ALLOCATE_NETWORK
1.89 +#include "netgen.h"
1.90 +
1.91 +#define PROBLEM_PARMS 13 /* aliases for generation parameters */
1.92 +#define NODES parms[0] /* number of nodes */
1.93 +#define SOURCES parms[1] /* number of sources (including transshipment) */
1.94 +#define SINKS parms[2] /* number of sinks (including transshipment) */
1.95 +#define DENSITY parms[3] /* number of (requested) arcs */
1.96 +#define MINCOST parms[4] /* minimum cost of arcs */
1.97 +#define MAXCOST parms[5] /* maximum cost of arcs */
1.98 +#define SUPPLY parms[6] /* total supply */
1.99 +#define TSOURCES parms[7] /* transshipment sources */
1.100 +#define TSINKS parms[8] /* transshipment sinks */
1.101 +#define HICOST parms[9] /* percent of skeleton arcs given maximum cost */
1.102 +#define CAPACITATED parms[10] /* percent of arcs to be capacitated */
1.103 +#define MINCAP parms[11] /* minimum capacity for capacitated arcs */
1.104 +#define MAXCAP parms[12] /* maximum capacity for capacitated arcs */
1.105 +
1.106 +
1.107 +/*** Private interfaces */
1.108 +
1.109 +#ifdef DEBUG
1.110 +#define PRIVATE
1.111 +#else
1.112 +#define PRIVATE static
1.113 +#endif
1.114 +
1.115 +#ifdef __STDC__
1.116 +PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */
1.117 +PRIVATE void create_assignment(long*); /* create assignment problem */
1.118 +PRIVATE void sort_skeleton(int); /* sorts skeleton chains */
1.119 +PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */
1.120 +PRIVATE void error_exit(long); /* print error message and exit */
1.121 +#else
1.122 +PRIVATE void create_supply(); /* create supply nodes */
1.123 +PRIVATE void create_assignment(); /* create assignment problem */
1.124 +PRIVATE void sort_skeleton(); /* sorts skeleton chains */
1.125 +PRIVATE void pick_head(); /* chooses destination nodes for rubbish arcs */
1.126 +PRIVATE void error_exit(); /* print error message and exit */
1.127 +#endif
1.128 +
1.129 +/*** Private variables */
1.130 +
1.131 +static NODE nodes_left;
1.132 +static ARC arc_count;
1.133 +static NODE pred[MAXARCS];
1.134 +static NODE head[MAXARCS];
1.135 +static NODE tail[MAXARCS];
1.136 +
1.137 +
1.138 +/*** Local macros */
1.139 +
1.140 +#define MIN(x, y) ((x) < (y) ? (x) : (y))
1.141 +#define MAX(x, y) ((x) > (y) ? (x) : (y))
1.142 +#define SAVE_ARC(tail, head, cost, capacity) /* records an arc where our caller can get it */ \
1.143 + { \
1.144 + FROM[arc_count] = tail; \
1.145 + TO [arc_count] = head; \
1.146 + C [arc_count] = cost; \
1.147 + U [arc_count] = capacity; \
1.148 + arc_count++; \
1.149 + }
1.150 +
1.151 +
1.152 +/*** Fortran callable interface routine */
1.153 +
1.154 +void netgen_(seed, parms, generated_nodes, generated_arcs)
1.155 +long* seed; /* pointer to random seed */
1.156 +long parms[PROBLEM_PARMS]; /* problem parameters */
1.157 +long* generated_nodes; /* number of generated nodes */
1.158 +long* generated_arcs; /* number of generated arcs */
1.159 +{
1.160 + *generated_nodes = NODES;
1.161 + if ((*generated_arcs = netgen(*seed, parms)) < 0)
1.162 + error_exit(*generated_arcs);
1.163 +}
1.164 +
1.165 +
1.166 +/*** C callable interface routine */
1.167 +
1.168 +ARC netgen(seed, parms)
1.169 +long seed; /* random seed */
1.170 +long parms[]; /* problem parameters */
1.171 +{
1.172 + register NODE i,j,k;
1.173 + NODE source;
1.174 + NODE node;
1.175 + NODE sinks_per_source;
1.176 + NODE* sinks;
1.177 + NODE it;
1.178 + int chain_length;
1.179 + COST cost;
1.180 + CAPACITY cap;
1.181 + INDEX_LIST handle;
1.182 + int supply_per_sink;
1.183 + int partial_supply;
1.184 + int sort_count;
1.185 +
1.186 +
1.187 +/*** Perform sanity checks on the input */
1.188 +
1.189 + if (seed <= 0)
1.190 + return BAD_SEED;
1.191 + if (NODES > MAXNODES || DENSITY > MAXARCS)
1.192 + return TOO_BIG;
1.193 + if ((NODES <= 0) ||
1.194 + (NODES > DENSITY) ||
1.195 + (SOURCES <= 0) ||
1.196 + (SINKS <= 0) ||
1.197 + (SOURCES + SINKS > NODES) ||
1.198 + (MINCOST > MAXCOST) ||
1.199 + (SUPPLY < SOURCES) ||
1.200 + (TSOURCES > SOURCES) ||
1.201 + (TSINKS > SINKS) ||
1.202 + (HICOST < 0 || HICOST > 100) ||
1.203 + (CAPACITATED < 0 || CAPACITATED > 100) ||
1.204 + (MINCAP > MAXCAP))
1.205 + return BAD_PARMS;
1.206 +
1.207 +
1.208 +/*** Do a little bit of setting up. */
1.209 +
1.210 + set_random(seed);
1.211 +
1.212 + arc_count = 0;
1.213 + nodes_left = NODES - SINKS + TSINKS;
1.214 +
1.215 + if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
1.216 + (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
1.217 + SOURCES == SUPPLY) {
1.218 + create_assignment(parms);
1.219 + return arc_count;
1.220 + }
1.221 +
1.222 + (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */
1.223 +
1.224 + create_supply((NODE)SOURCES, (CAPACITY)SUPPLY);
1.225 +
1.226 +
1.227 +/*** Form most of the network skeleton. First, 60% of the transshipment
1.228 + *** nodes are divided evenly among the various sources; the remainder
1.229 + *** are chained onto the end of the chains belonging to random sources.
1.230 + ***/
1.231 +
1.232 + for (i = 1; i <= SOURCES; i++) /* point SOURCES at themselves */
1.233 + pred[i] = i;
1.234 + handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS));
1.235 + source = 1;
1.236 + for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) {
1.237 + node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
1.238 + pred[node] = pred[source];
1.239 + pred[source] = node;
1.240 + if (++source > SOURCES)
1.241 + source = 1;
1.242 + }
1.243 + for ( ; i > 0; --i) {
1.244 + node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
1.245 + source = ng_random(1L, SOURCES);
1.246 + pred[node] = pred[source];
1.247 + pred[source] = node;
1.248 + }
1.249 + free_index_list(handle);
1.250 +
1.251 +
1.252 +/*** For each source chain, hook it to an "appropriate" number of sinks,
1.253 + *** place capacities and costs on the skeleton edges, and then call
1.254 + *** pick_head to add a bunch of rubbish edges at each node on the chain.
1.255 + ***/
1.256 +
1.257 + for (source = 1; source <= SOURCES; source++) {
1.258 + sort_count = 0;
1.259 + node = pred[source];
1.260 + while (node != source) {
1.261 + sort_count++;
1.262 + head[sort_count] = node;
1.263 + node = tail[sort_count] = pred[node];
1.264 + }
1.265 + if ((NODES-SOURCES-SINKS) == 0)
1.266 + sinks_per_source = SINKS/SOURCES + 1;
1.267 + else
1.268 +/* changing to handle overflows with large n; Mar 18 -- jc */
1.269 + sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS);
1.270 + sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS));
1.271 + sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE));
1.272 + handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1));
1.273 + for (i = 0; i < sinks_per_source; i++) {
1.274 + sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
1.275 + }
1.276 + if (source == SOURCES && index_size(handle) > 0) {
1.277 + sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE));
1.278 + while (index_size(handle) > 0) {
1.279 + j = choose_index(handle, 1);
1.280 + if (B[j] == 0)
1.281 + sinks[sinks_per_source++] = j;
1.282 + }
1.283 + }
1.284 + free_index_list(handle);
1.285 +
1.286 + chain_length = sort_count;
1.287 + supply_per_sink = B[source-1] / sinks_per_source;
1.288 + k = pred[source];
1.289 + for (i = 0; i < sinks_per_source; i++) {
1.290 + sort_count++;
1.291 + partial_supply = ng_random(1L, (long)supply_per_sink);
1.292 + j = ng_random(0L, (long)sinks_per_source - 1);
1.293 + tail[sort_count] = k;
1.294 + head[sort_count] = sinks[i] + 1;
1.295 + B[sinks[i]] -= partial_supply;
1.296 + B[sinks[j]] -= (supply_per_sink - partial_supply);
1.297 + k = source;
1.298 + for (j = ng_random(1L, (long)chain_length); j > 0; j--)
1.299 + k = pred[k];
1.300 + }
1.301 + B[sinks[0]] -= (B[source-1] % sinks_per_source);
1.302 + free((void *)sinks);
1.303 +
1.304 + sort_skeleton(sort_count);
1.305 + tail[sort_count+1] = 0;
1.306 + for (i = 1; i <= sort_count; ) {
1.307 + handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
1.308 + remove_index(handle, (INDEX)tail[i]);
1.309 + it = tail[i];
1.310 + while (it == tail[i]) {
1.311 + remove_index(handle, (INDEX)head[i]);
1.312 + cap = SUPPLY;
1.313 + if (ng_random(1L, 100L) <= CAPACITATED)
1.314 + cap = MAX(B[source-1], MINCAP);
1.315 + cost = MAXCOST;
1.316 + if (ng_random(1L, 100L) > HICOST)
1.317 + cost = ng_random(MINCOST, MAXCOST);
1.318 + SAVE_ARC(it,head[i],cost,cap);
1.319 + i++;
1.320 + }
1.321 + pick_head(parms, handle, it);
1.322 + free_index_list(handle);
1.323 + }
1.324 + }
1.325 +
1.326 +
1.327 +/*** Add more rubbish edges out of the transshipment sinks. */
1.328 +
1.329 + for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) {
1.330 + handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
1.331 + remove_index(handle, (INDEX)i);
1.332 + pick_head(parms, handle, i);
1.333 + free_index_list(handle);
1.334 + }
1.335 +
1.336 + return arc_count;
1.337 +}
1.338 +
1.339 +
1.340 +PRIVATE void create_supply(sources, supply)
1.341 +NODE sources;
1.342 +CAPACITY supply;
1.343 +{
1.344 + CAPACITY supply_per_source = supply / sources;
1.345 + CAPACITY partial_supply;
1.346 + NODE i;
1.347 +
1.348 + for (i = 0; i < sources; i++) {
1.349 + B[i] += (partial_supply = ng_random(1L, (long)supply_per_source));
1.350 + B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply;
1.351 + }
1.352 + B[ng_random(0L, (long)(sources - 1))] += supply % sources;
1.353 +}
1.354 +
1.355 +
1.356 +PRIVATE void create_assignment(parms)
1.357 +long parms[];
1.358 +{
1.359 + INDEX_LIST skeleton, handle;
1.360 + INDEX index;
1.361 + NODE source;
1.362 +
1.363 + for (source = 0; source < NODES/2; source++)
1.364 + B[source] = 1;
1.365 + for ( ; source < NODES; source++)
1.366 + B[source] = -1;
1.367 +
1.368 + skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
1.369 + for (source = 1; source <= NODES/2; source++) {
1.370 + index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton)));
1.371 + SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1);
1.372 + handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
1.373 + remove_index(handle, index);
1.374 + pick_head(parms, handle, source);
1.375 + free_index_list(handle);
1.376 + }
1.377 + free_index_list(skeleton);
1.378 +}
1.379 +
1.380 +
1.381 +PRIVATE void sort_skeleton(sort_count) /* Shell sort */
1.382 +int sort_count;
1.383 +{
1.384 + int m,i,j,k;
1.385 + int temp;
1.386 +
1.387 + m = sort_count;
1.388 + while ((m /= 2) != 0) {
1.389 + k = sort_count - m;
1.390 + for (j = 1; j <= k; j++) {
1.391 + i = j;
1.392 + while (i >= 1 && tail[i] > tail[i+m]) {
1.393 + temp = tail[i];
1.394 + tail[i] = tail[i+m];
1.395 + tail[i+m] = temp;
1.396 + temp = head[i];
1.397 + head[i] = head[i+m];
1.398 + head[i+m] = temp;
1.399 + i -= m;
1.400 + }
1.401 + }
1.402 + }
1.403 +}
1.404 +
1.405 +
1.406 +PRIVATE void pick_head(parms, handle, desired_tail)
1.407 +long parms[];
1.408 +INDEX_LIST handle;
1.409 +NODE desired_tail;
1.410 +{
1.411 + NODE non_sources = NODES - SOURCES + TSOURCES;
1.412 +
1.413 +/* changing Aug 29 -- jc
1.414 + ARC remaining_arcs = DENSITY - arc_count;
1.415 +*/
1.416 + int remaining_arcs = (int) DENSITY - (int) arc_count;
1.417 +
1.418 + INDEX index;
1.419 + int limit;
1.420 + long upper_bound;
1.421 + CAPACITY cap;
1.422 +
1.423 +/* changing Aug 29 -- jc
1.424 +*/
1.425 + nodes_left--;
1.426 + if ((2 * (int) nodes_left) >= (int) remaining_arcs)
1.427 + return;
1.428 +
1.429 + if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) {
1.430 + limit = non_sources;
1.431 + } else {
1.432 + upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1);
1.433 + do {
1.434 + limit = ng_random(1L, upper_bound);
1.435 + if (nodes_left == 0)
1.436 + limit = remaining_arcs;
1.437 +/* changing to handle overflows with large n; Mar 18 -- jc */
1.438 + } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit));
1.439 + }
1.440 +
1.441 + for ( ; limit > 0; limit--) {
1.442 + index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle)));
1.443 + cap = SUPPLY;
1.444 + if (ng_random(1L, 100L) <= CAPACITATED)
1.445 + cap = ng_random(MINCAP, MAXCAP);
1.446 +
1.447 +/* adding Aug 29 -- jc */
1.448 +if ((1 <= index) && (index <= NODES)) {
1.449 + SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap);
1.450 + }
1.451 +
1.452 + }
1.453 +}
1.454 +
1.455 +
1.456 +/*** Print an appropriate error message and then exit with a nonzero code. */
1.457 +
1.458 +PRIVATE void error_exit(rc)
1.459 +long rc;
1.460 +{
1.461 + switch (rc) {
1.462 + case BAD_SEED:
1.463 + fprintf(stderr, "NETGEN requires a positive random seed\n");
1.464 + break;
1.465 + case TOO_BIG:
1.466 + fprintf(stderr, "Problem too large for generator\n");
1.467 + break;
1.468 + case BAD_PARMS:
1.469 + fprintf(stderr, "Inconsistent parameter settings - check the input\n");
1.470 + break;
1.471 + case ALLOCATION_FAILURE:
1.472 + fprintf(stderr, "Memory allocation failure\n");
1.473 + break;
1.474 + default:
1.475 + fprintf(stderr, "Internal error\n");
1.476 + break;
1.477 + }
1.478 + exit(1000 - (int)rc);
1.479 +}
1.480 +
1.481 +#ifdef DIMACS /* generates network on standard output */
1.482 +
1.483 +#define READ(v) /* read one variable using scanf */ \
1.484 + switch( scanf("%ld", &v) ) { \
1.485 + case 1: \
1.486 + break; \
1.487 + default: \
1.488 + exit(0); \
1.489 + }
1.490 +
1.491 +int main()
1.492 +{
1.493 + long seed;
1.494 + long problem;
1.495 + long parms[PROBLEM_PARMS];
1.496 + long arcs;
1.497 + int i;
1.498 +
1.499 +/*** Read problem parameters and generate networks */
1.500 +
1.501 + while (1) {
1.502 + READ(seed);
1.503 + if (seed <= 0) exit(0);
1.504 + READ(problem);
1.505 + if (problem <= 0) exit(0);
1.506 + for (i = 0; i < PROBLEM_PARMS; i++)
1.507 + READ(parms[i]);
1.508 + printf("c NETGEN flow network generator (C version)\n");
1.509 + printf("c Problem %2ld input parameters\n", problem);
1.510 + printf("c ---------------------------\n");
1.511 + printf("c Random seed: %10ld\n", seed);
1.512 + printf("c Number of nodes: %10ld\n", NODES);
1.513 + printf("c Source nodes: %10ld\n", SOURCES);
1.514 + printf("c Sink nodes: %10ld\n", SINKS);
1.515 + printf("c Number of arcs: %10ld\n", DENSITY);
1.516 + printf("c Minimum arc cost: %10ld\n", MINCOST);
1.517 + printf("c Maximum arc cost: %10ld\n", MAXCOST);
1.518 + printf("c Total supply: %10ld\n", SUPPLY);
1.519 + printf("c Transshipment -\n");
1.520 + printf("c Sources: %10ld\n", TSOURCES);
1.521 + printf("c Sinks: %10ld\n", TSINKS);
1.522 + printf("c Skeleton arcs -\n");
1.523 + printf("c With max cost: %10ld%%\n", HICOST);
1.524 + printf("c Capacitated: %10ld%%\n", CAPACITATED);
1.525 + printf("c Minimum arc capacity: %10ld\n", MINCAP);
1.526 + printf("c Maximum arc capacity: %10ld\n", MAXCAP);
1.527 +
1.528 + if ((arcs = netgen(seed, parms)) < 0)
1.529 + error_exit(arcs);
1.530 + if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
1.531 + (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
1.532 + SOURCES == SUPPLY) {
1.533 + printf("c\n");
1.534 + printf("c *** Assignment ***\n");
1.535 + printf("c\n");
1.536 + printf("p asn %ld %ld\n", NODES, arcs);
1.537 + for (i = 0; i < NODES; i++) {
1.538 + if (B[i] > 0)
1.539 + printf("n %ld\n", i + 1);
1.540 + }
1.541 + for (i = 0; i < arcs; i++) {
1.542 + printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]);
1.543 + }
1.544 + } else
1.545 + if (MINCOST == 1 && MAXCOST == 1) {
1.546 + printf("c\n");
1.547 + printf("c *** Maximum flow ***\n");
1.548 + printf("c\n");
1.549 + printf("p max %ld %ld\n", NODES, arcs);
1.550 + for (i = 0; i < NODES; i++) {
1.551 + if (B[i] > 0)
1.552 + printf("n %ld s\n", i + 1);
1.553 + else
1.554 + if (B[i] < 0)
1.555 + printf("n %ld t\n", i + 1);
1.556 + }
1.557 + for (i = 0; i < arcs; i++) {
1.558 + printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]);
1.559 + }
1.560 + } else {
1.561 + printf("c\n");
1.562 + printf("c *** Minimum cost flow ***\n");
1.563 + printf("c\n");
1.564 + printf("p min %ld %ld\n", NODES, arcs);
1.565 + for (i = 0; i < NODES; i++) {
1.566 + if (B[i] != 0)
1.567 + printf("n %ld %ld\n", i + 1, B[i]);
1.568 + }
1.569 + for (i = 0; i < arcs; i++) {
1.570 + printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]);
1.571 + }
1.572 + }
1.573 + }
1.574 + return 0;
1.575 +}
1.576 +
1.577 +#endif