alpar@6: /*** Copyright 1989 Norbert Schlenker.  All rights reserved.
alpar@6: 
alpar@6:  *** This software is distributed subject to the following provisions:
alpar@6:  ***    - this notice may not be removed;
alpar@6:  ***    - you may modify the source code, as long as redistributed
alpar@6:  ***      versions have their modifications clearly marked;
alpar@6:  ***    - no charge, other than a nominal copying fee, may be made
alpar@6:  ***      when providing copies of this source code to others;
alpar@6:  ***    - if this source code is used as part of a product which is
alpar@6:  ***      distributed only as a binary, a copy of this source code
alpar@6:  ***      must be included in the distribution.
alpar@6:  ***
alpar@6:  *** Unlike the GNU GPL, use of this code does not obligate you to
alpar@6:  *** disclose your own proprietary source code.
alpar@6: 
alpar@6:  *** The author of this software provides no warranty, express or
alpar@6:  *** implied, as to its utility or correctness.  That said, reports
alpar@6:  *** of bugs or compatibility problems will be gladly received by
alpar@6:  *** nfs@princeton.edu, and fixes will be attempted.
alpar@6:  ***/
alpar@6: 
alpar@6: 
alpar@6: /*** netgen - C version of the standard NETGEN network generator 
alpar@6:  ***          This program is a functional equivalent of the
alpar@6:  ***          standard network generator NETGEN described in:
alpar@6:  ***		Klingman, D., A. Napier, and J. Stutz, "NETGEN:  A Program
alpar@6:  ***		  for Generating Large Scale Capacitated Assignment,
alpar@6:  ***		  Transportation, and Minimum Cost Flow Network Problems",
alpar@6:  ***		  Management Science 20, 5, 814-821 (1974)
alpar@6:  ***
alpar@6:  ***	      This software provides a number of interfaces for use by
alpar@6:  ***	      network solvers.  Standard call interfaces are supplied for
alpar@6:  ***	      use by (Unix) C and Fortran solvers, with generation parameters
alpar@6:  ***	      passed into the generator and the flow network passed back to
alpar@6:  ***	      the solver via large external (COMMON in Fortran) arrays.
alpar@6:  ***	      For the DIMACS challenge, this code will produce output files
alpar@6:  ***	      in the appropriate format for later reading by solvers.
alpar@6:  ***          Undefine the symbol DIMACS when using the call interface.
alpar@6:  ***
alpar@6:  ***          The generator produces exact duplicates of the networks
alpar@6:  ***          made by the Fortran code (even though that means bugs
alpar@6:  ***          are being perpetuated). It is faster by orders of magnitude
alpar@6:  ***          in generating large networks, primarily by imposing the
alpar@6:  ***          notion of the abstract data type INDEX_LIST and implementing
alpar@6:  ***          the type operations in a reasonably efficient fashion.
alpar@6:  ***/
alpar@6: 
alpar@6: /*** Generates transportation problems if:
alpar@6:  ***	SOURCES+SINKS == NODES && TSOURCES == TSINKS == 0
alpar@6:  ***
alpar@6:  *** Generates assignment problems if above conditions are satisfied, and:
alpar@6:  ***	SOURCES == SINKS && SUPPLY == SOURCES
alpar@6:  ***
alpar@6:  *** Generates maximum flow problems if not an assignment problem and:
alpar@6:  ***	MINCOST == MAXCOST == 1
alpar@6: 
alpar@6:  *** Implementation notes:
alpar@6:  ***
alpar@6:  ***	This file contains both a Fortran and a C interface. The
alpar@6:  ***	Fortran interface is suffixed with an underscore to make it
alpar@6:  ***	callable in the normal fashion from Fortran (a Unix convention).
alpar@6:  ***
alpar@6:  ***    Because Fortran has no facility for pointers, the common arrays
alpar@6:  ***    are statically allocated.  Static allocation has nothing to recommend
alpar@6:  ***    it except for the need for a Fortran interface.
alpar@6:  ***
alpar@6:  ***    This software expects input parameters to be long integers
alpar@6:  ***    (in the sense of C); that means no INTEGER*2 from Fortran callers.
alpar@6:  ***
alpar@6:  ***	Compiling with -DDIMACS produces a program that reads problem
alpar@6:  ***	parameters, generates the appropriate problem, and prints it.
alpar@6:  ***
alpar@6:  ***	Compiling with -DDEBUG produces code with externally visible
alpar@6:  ***	procedure names, useful for debugging and profiling.
alpar@6:  ***/
alpar@6: 
alpar@6: 
alpar@6: /*** System interfaces */
alpar@6: 
alpar@6: #include <stdio.h>
alpar@6: 
alpar@6: 
alpar@6: /*** Public interfaces */
alpar@6: 
alpar@6: #define ALLOCATE_NETWORK
alpar@6: #include "netgen.h"
alpar@6: 
alpar@7: #include "main.h"
alpar@6: 
alpar@6: /*** Private interfaces */
alpar@6: 
alpar@6: #ifdef DEBUG
alpar@6: #define PRIVATE
alpar@6: #else
alpar@6: #define PRIVATE static
alpar@6: #endif
alpar@6: 
alpar@6: #ifdef __STDC__
alpar@6: PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */
alpar@6: PRIVATE void create_assignment(long*);	/* create assignment problem */
alpar@6: PRIVATE void sort_skeleton(int);	/* sorts skeleton chains */
alpar@6: PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */
alpar@6: PRIVATE void error_exit(long);		/* print error message and exit */
alpar@6: #else
alpar@6: PRIVATE void create_supply();		/* create supply nodes */
alpar@6: PRIVATE void create_assignment();	/* create assignment problem */
alpar@6: PRIVATE void sort_skeleton();		/* sorts skeleton chains */
alpar@6: PRIVATE void pick_head();		/* chooses destination nodes for rubbish arcs */
alpar@6: PRIVATE void error_exit();		/* print error message and exit */
alpar@6: #endif
alpar@6: 
alpar@6: /*** Private variables */
alpar@6: 
alpar@6: static NODE nodes_left;
alpar@6: static ARC arc_count;
alpar@6: static NODE pred[MAXARCS];
alpar@6: static NODE head[MAXARCS];
alpar@6: static NODE tail[MAXARCS];
alpar@6: 
alpar@6: 
alpar@6: /*** Local macros */
alpar@6: 
alpar@6: #define MIN(x, y) ((x) < (y) ? (x) : (y))
alpar@6: #define MAX(x, y) ((x) > (y) ? (x) : (y))
alpar@6: #define SAVE_ARC(tail, head, cost, capacity)	/* records an arc where our caller can get it */ \
alpar@6:   {				\
alpar@6:     FROM[arc_count] = tail;	\
alpar@6:     TO  [arc_count] = head;	\
alpar@6:     C   [arc_count] = cost;	\
alpar@6:     U   [arc_count] = capacity; \
alpar@6:     arc_count++;		\
alpar@6:   }
alpar@6: 
alpar@6: 
alpar@6: /*** Fortran callable interface routine */
alpar@6: 
alpar@6: void netgen_(seed, parms, generated_nodes, generated_arcs)
alpar@6: long* seed;			/* pointer to random seed */
alpar@6: long parms[PROBLEM_PARMS];	/* problem parameters */
alpar@6: long* generated_nodes;		/* number of generated nodes */
alpar@6: long* generated_arcs;		/* number of generated arcs */
alpar@6: {
alpar@6:   *generated_nodes = NODES;
alpar@6:   if ((*generated_arcs = netgen(*seed, parms)) < 0)
alpar@6:     error_exit(*generated_arcs);
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: /*** C callable interface routine */
alpar@6: 
alpar@6: ARC netgen(seed, parms)
alpar@6: long seed;			/* random seed */
alpar@6: long parms[];			/* problem parameters */
alpar@6: {
alpar@6:   register NODE i,j,k;
alpar@6:   NODE source;
alpar@6:   NODE node;
alpar@6:   NODE sinks_per_source;
alpar@6:   NODE* sinks;
alpar@6:   NODE it;
alpar@6:   int chain_length;
alpar@6:   COST cost;
alpar@6:   CAPACITY cap;
alpar@6:   INDEX_LIST handle;
alpar@6:   int supply_per_sink;
alpar@6:   int partial_supply;
alpar@6:   int sort_count;
alpar@6: 
alpar@6: 
alpar@6: /*** Perform sanity checks on the input */
alpar@6: 
alpar@6:   if (seed <= 0)
alpar@6:     return BAD_SEED;
alpar@6:   if (NODES > MAXNODES || DENSITY > MAXARCS)
alpar@6:     return TOO_BIG;
alpar@6:   if ((NODES <= 0) ||
alpar@6:       (NODES > DENSITY) ||
alpar@6:       (SOURCES <= 0) ||
alpar@6:       (SINKS <= 0) ||
alpar@6:       (SOURCES + SINKS > NODES) ||
alpar@6:       (MINCOST > MAXCOST) ||
alpar@6:       (SUPPLY < SOURCES) ||
alpar@6:       (TSOURCES > SOURCES) ||
alpar@6:       (TSINKS > SINKS) ||
alpar@6:       (HICOST < 0 || HICOST > 100) ||
alpar@6:       (CAPACITATED < 0 || CAPACITATED > 100) ||
alpar@6:       (MINCAP > MAXCAP))
alpar@6:     return BAD_PARMS;
alpar@6: 
alpar@6: 
alpar@6: /*** Do a little bit of setting up. */
alpar@6: 
alpar@6:   set_random(seed);
alpar@6: 
alpar@6:   arc_count = 0;
alpar@6:   nodes_left = NODES - SINKS + TSINKS;
alpar@6: 
alpar@6:   if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
alpar@6:       (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
alpar@6:        SOURCES == SUPPLY) {
alpar@6:     create_assignment(parms);
alpar@6:     return arc_count;
alpar@6:   }
alpar@6: 
alpar@6:   (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */
alpar@6: 
alpar@6:   create_supply((NODE)SOURCES, (CAPACITY)SUPPLY);
alpar@6: 
alpar@6: 
alpar@6: /*** Form most of the network skeleton.  First, 60% of the transshipment
alpar@6:  *** nodes are divided evenly among the various sources; the remainder
alpar@6:  *** are chained onto the end of the chains belonging to random sources.
alpar@6:  ***/
alpar@6: 
alpar@6:   for (i = 1; i <= SOURCES; i++)	/* point SOURCES at themselves */
alpar@6:     pred[i] = i;
alpar@6:   handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS));
alpar@6:   source = 1;
alpar@6:   for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) {
alpar@6:     node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
alpar@6:     pred[node] = pred[source];
alpar@6:     pred[source] = node;
alpar@6:     if (++source > SOURCES)
alpar@6:       source = 1;
alpar@6:   }
alpar@6:   for ( ; i > 0; --i) {
alpar@6:     node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
alpar@6:     source = ng_random(1L, SOURCES);
alpar@6:     pred[node] = pred[source];
alpar@6:     pred[source] = node;
alpar@6:   }
alpar@6:   free_index_list(handle);
alpar@6: 
alpar@6: 
alpar@6: /*** For each source chain, hook it to an "appropriate" number of sinks,
alpar@6:  *** place capacities and costs on the skeleton edges, and then call
alpar@6:  *** pick_head to add a bunch of rubbish edges at each node on the chain.
alpar@6:  ***/
alpar@6: 
alpar@6:   for (source = 1; source <= SOURCES; source++) {
alpar@6:     sort_count = 0;
alpar@6:     node = pred[source];
alpar@6:     while (node != source) {
alpar@6:       sort_count++;
alpar@6:       head[sort_count] = node;
alpar@6:       node = tail[sort_count] = pred[node];
alpar@6:     }
alpar@6:     if ((NODES-SOURCES-SINKS) == 0)
alpar@6:       sinks_per_source = SINKS/SOURCES + 1;
alpar@6:     else
alpar@6: /* changing to handle overflows with large n; Mar 18 -- jc */
alpar@6:       sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS);
alpar@6:     sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS));
alpar@6:     sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE));
alpar@6:     handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1));
alpar@6:     for (i = 0; i < sinks_per_source; i++) {
alpar@6:       sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
alpar@6:     }
alpar@6:     if (source == SOURCES && index_size(handle) > 0) {
alpar@6:       sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE));
alpar@6:       while (index_size(handle) > 0) {
alpar@6: 	j = choose_index(handle, 1);
alpar@6: 	if (B[j] == 0)
alpar@6: 	  sinks[sinks_per_source++] = j;
alpar@6:       }
alpar@6:     }
alpar@6:     free_index_list(handle);
alpar@6: 
alpar@6:     chain_length = sort_count;
alpar@6:     supply_per_sink = B[source-1] / sinks_per_source;
alpar@6:     k = pred[source];
alpar@6:     for (i = 0; i < sinks_per_source; i++) {
alpar@6:       sort_count++;
alpar@6:       partial_supply = ng_random(1L, (long)supply_per_sink);
alpar@6:       j = ng_random(0L, (long)sinks_per_source - 1);
alpar@6:       tail[sort_count] = k;
alpar@6:       head[sort_count] = sinks[i] + 1;
alpar@6:       B[sinks[i]] -= partial_supply;
alpar@6:       B[sinks[j]] -= (supply_per_sink - partial_supply);
alpar@6:       k = source;
alpar@6:       for (j = ng_random(1L, (long)chain_length); j > 0; j--)
alpar@6: 	k = pred[k];
alpar@6:     }
alpar@6:     B[sinks[0]] -= (B[source-1] % sinks_per_source);
alpar@6:     free((void *)sinks);
alpar@6: 
alpar@6:     sort_skeleton(sort_count);
alpar@6:     tail[sort_count+1] = 0;
alpar@6:     for (i = 1; i <= sort_count; ) {
alpar@6:       handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
alpar@6:       remove_index(handle, (INDEX)tail[i]);
alpar@6:       it = tail[i];
alpar@6:       while (it == tail[i]) {
alpar@6: 	remove_index(handle, (INDEX)head[i]);
alpar@6: 	cap = SUPPLY;
alpar@6: 	if (ng_random(1L, 100L) <= CAPACITATED)
alpar@6: 	  cap = MAX(B[source-1], MINCAP);
alpar@6: 	cost = MAXCOST;
alpar@6: 	if (ng_random(1L, 100L) > HICOST)
alpar@6: 	  cost = ng_random(MINCOST, MAXCOST);
alpar@6: 	SAVE_ARC(it,head[i],cost,cap);
alpar@6: 	i++;
alpar@6:       }
alpar@6:       pick_head(parms, handle, it);
alpar@6:       free_index_list(handle);
alpar@6:     }
alpar@6:   }
alpar@6: 
alpar@6: 
alpar@6: /*** Add more rubbish edges out of the transshipment sinks. */
alpar@6: 
alpar@6:   for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) {
alpar@6:     handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
alpar@6:     remove_index(handle, (INDEX)i);
alpar@6:     pick_head(parms, handle, i);
alpar@6:     free_index_list(handle);
alpar@6:   }
alpar@6: 
alpar@6:   return arc_count;
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: PRIVATE void create_supply(sources, supply)
alpar@6: NODE sources;
alpar@6: CAPACITY supply;
alpar@6: {
alpar@6:   CAPACITY supply_per_source = supply / sources;
alpar@6:   CAPACITY partial_supply;
alpar@6:   NODE i;
alpar@6: 
alpar@6:   for (i = 0; i < sources; i++) {
alpar@6:     B[i] += (partial_supply = ng_random(1L, (long)supply_per_source));
alpar@6:     B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply;
alpar@6:   }
alpar@6:   B[ng_random(0L, (long)(sources - 1))] += supply % sources;
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: PRIVATE void create_assignment(parms)
alpar@6: long parms[];
alpar@6: {
alpar@6:   INDEX_LIST skeleton, handle;
alpar@6:   INDEX index;
alpar@6:   NODE source;
alpar@6: 
alpar@6:   for (source = 0; source < NODES/2; source++)
alpar@6:     B[source] = 1;
alpar@6:   for ( ; source < NODES; source++)
alpar@6:     B[source] = -1;
alpar@6: 
alpar@6:   skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
alpar@6:   for (source = 1; source <= NODES/2; source++) {
alpar@6:     index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton)));
alpar@6:     SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1);
alpar@6:     handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
alpar@6:     remove_index(handle, index);
alpar@6:     pick_head(parms, handle, source);
alpar@6:     free_index_list(handle);
alpar@6:   }
alpar@6:   free_index_list(skeleton);
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: PRIVATE void sort_skeleton(sort_count) 		/* Shell sort */
alpar@6: int sort_count;
alpar@6: {
alpar@6:   int m,i,j,k;
alpar@6:   int temp;
alpar@6: 
alpar@6:   m = sort_count;
alpar@6:   while ((m /= 2) != 0) {
alpar@6:     k = sort_count - m;
alpar@6:     for (j = 1; j <= k; j++) {
alpar@6:       i = j;
alpar@6:       while (i >= 1 && tail[i] > tail[i+m]) {
alpar@6: 	temp = tail[i];
alpar@6: 	tail[i] = tail[i+m];
alpar@6: 	tail[i+m] = temp;
alpar@6: 	temp = head[i];
alpar@6: 	head[i] = head[i+m];
alpar@6: 	head[i+m] = temp;
alpar@6: 	i -= m;
alpar@6:       }
alpar@6:     }
alpar@6:   }
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: PRIVATE void pick_head(parms, handle, desired_tail)
alpar@6: long parms[];
alpar@6: INDEX_LIST handle;
alpar@6: NODE desired_tail;
alpar@6: {
alpar@6:   NODE non_sources = NODES - SOURCES + TSOURCES;
alpar@6: 
alpar@6: /* changing Aug 29 -- jc
alpar@6:   ARC remaining_arcs = DENSITY - arc_count;
alpar@6: */
alpar@6:   int  remaining_arcs = (int) DENSITY - (int) arc_count;
alpar@6: 
alpar@6:   INDEX index;
alpar@6:   int limit;
alpar@6:   long upper_bound;
alpar@6:   CAPACITY cap;
alpar@6: 
alpar@6: /* changing Aug 29 -- jc
alpar@6: */
alpar@6:   nodes_left--;
alpar@6:   if ((2 * (int) nodes_left) >= (int) remaining_arcs)
alpar@6:     return;
alpar@6: 
alpar@6:   if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) {
alpar@6:     limit = non_sources;
alpar@6:   } else {
alpar@6:     upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1);
alpar@6:     do {
alpar@6:       limit = ng_random(1L, upper_bound);
alpar@6:       if (nodes_left == 0)
alpar@6: 	limit = remaining_arcs;
alpar@6: /* changing to handle overflows with large n; Mar 18 -- jc */
alpar@6:     } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit));
alpar@6:   }
alpar@6: 
alpar@6:   for ( ; limit > 0; limit--) {
alpar@6:     index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle)));
alpar@6:     cap = SUPPLY;
alpar@6:     if (ng_random(1L, 100L) <= CAPACITATED)
alpar@6:       cap = ng_random(MINCAP, MAXCAP);
alpar@6: 
alpar@6: /* adding Aug 29 -- jc */
alpar@6: if ((1 <= index) && (index <= NODES)) {
alpar@6:     SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap);
alpar@6:     }
alpar@6: 
alpar@6:   }
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: /*** Print an appropriate error message and then exit with a nonzero code. */
alpar@6: 
alpar@6: PRIVATE void error_exit(rc)
alpar@6: long rc;
alpar@6: {
alpar@6:   switch (rc) {
alpar@6:     case BAD_SEED:
alpar@6:       fprintf(stderr, "NETGEN requires a positive random seed\n");
alpar@6:       break;
alpar@6:     case TOO_BIG:
alpar@6:       fprintf(stderr, "Problem too large for generator\n");
alpar@6:       break;
alpar@6:     case BAD_PARMS:
alpar@6:       fprintf(stderr, "Inconsistent parameter settings - check the input\n");
alpar@6:       break;
alpar@6:     case ALLOCATION_FAILURE:
alpar@6:       fprintf(stderr, "Memory allocation failure\n");
alpar@6:       break;
alpar@6:     default:
alpar@6:       fprintf(stderr, "Internal error\n");
alpar@6:       break;
alpar@6:   }
alpar@6:   exit(1000 - (int)rc);
alpar@6: }
alpar@6: 
alpar@6: #ifdef DIMACS			/* generates network on standard output */
alpar@6: 
alpar@6: #define READ(v) 		     	/* read one variable using scanf */	\
alpar@6: 	switch( scanf("%ld", &v) ) {						\
alpar@6: 		case 1:								\
alpar@6: 			break;							\
alpar@6: 		default:							\
alpar@6: 			exit(0);						\
alpar@6: 		}
alpar@6: 
alpar@7: int orig_main(long seed,long problem,long *parms)
alpar@6: {
alpar@6:   long arcs;
alpar@6:   int i;
alpar@6: 
alpar@6: /*** Read problem parameters and generate networks */
alpar@7:   {
alpar@6:     printf("c NETGEN flow network generator (C version)\n");
alpar@6:     printf("c  Problem %2ld input parameters\n", problem);
alpar@6:     printf("c  ---------------------------\n");
alpar@6:     printf("c   Random seed:          %10ld\n",   seed);
alpar@6:     printf("c   Number of nodes:      %10ld\n",   NODES);
alpar@6:     printf("c   Source nodes:         %10ld\n",   SOURCES);
alpar@6:     printf("c   Sink nodes:           %10ld\n",   SINKS);
alpar@6:     printf("c   Number of arcs:       %10ld\n",   DENSITY);
alpar@6:     printf("c   Minimum arc cost:     %10ld\n",   MINCOST);
alpar@6:     printf("c   Maximum arc cost:     %10ld\n",   MAXCOST);
alpar@6:     printf("c   Total supply:         %10ld\n",   SUPPLY);
alpar@6:     printf("c   Transshipment -\n");
alpar@6:     printf("c     Sources:            %10ld\n",   TSOURCES);
alpar@6:     printf("c     Sinks:              %10ld\n",   TSINKS);
alpar@6:     printf("c   Skeleton arcs -\n");
alpar@6:     printf("c     With max cost:      %10ld%%\n", HICOST);
alpar@6:     printf("c     Capacitated:        %10ld%%\n", CAPACITATED);
alpar@6:     printf("c   Minimum arc capacity: %10ld\n",   MINCAP);
alpar@6:     printf("c   Maximum arc capacity: %10ld\n",   MAXCAP);
alpar@6: 
alpar@6:     if ((arcs = netgen(seed, parms)) < 0)
alpar@6:       error_exit(arcs);
alpar@6:     if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
alpar@6: 	(SOURCES-TSOURCES) == (SINKS-TSINKS) &&
alpar@6: 	 SOURCES == SUPPLY) {
alpar@6:       printf("c\n");
alpar@6:       printf("c  *** Assignment ***\n");
alpar@6:       printf("c\n");
alpar@6:       printf("p asn %ld %ld\n", NODES, arcs);
alpar@6:       for (i = 0; i < NODES; i++) {
alpar@6: 	if (B[i] > 0)
alpar@6: 	  printf("n %ld\n", i + 1);
alpar@6:       }
alpar@6:       for (i = 0; i < arcs; i++) {
alpar@6: 	printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]);
alpar@6:       }
alpar@6:     } else
alpar@6:     if (MINCOST == 1 && MAXCOST == 1) {
alpar@6:       printf("c\n");
alpar@6:       printf("c  *** Maximum flow ***\n");
alpar@6:       printf("c\n");
alpar@6:       printf("p max %ld %ld\n", NODES, arcs);
alpar@6:       for (i = 0; i < NODES; i++) {
alpar@6: 	if (B[i] > 0)
alpar@6: 	  printf("n %ld s\n", i + 1);
alpar@6: 	else
alpar@6: 	if (B[i] < 0)
alpar@6: 	  printf("n %ld t\n", i + 1);
alpar@6:       }
alpar@6:       for (i = 0; i < arcs; i++) {
alpar@6: 	printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]);
alpar@6:       }
alpar@6:     } else {
alpar@6:       printf("c\n");
alpar@6:       printf("c  *** Minimum cost flow ***\n");
alpar@6:       printf("c\n");
alpar@6:       printf("p min %ld %ld\n", NODES, arcs);
alpar@6:       for (i = 0; i < NODES; i++) {
alpar@6: 	if (B[i] != 0)
alpar@6: 	  printf("n %ld %ld\n", i + 1, B[i]);
alpar@6:       }
alpar@6:       for (i = 0; i < arcs; i++) {
alpar@6: 	printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]);
alpar@6:       }
alpar@6:     }
alpar@6:   }
alpar@6:   return 0;
alpar@6: }
alpar@6: 
alpar@6: #endif