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 alpar@6: alpar@6: alpar@6: /*** Public interfaces */ alpar@6: alpar@6: #define ALLOCATE_NETWORK alpar@6: #include "netgen.h" alpar@6: alpar@6: #define PROBLEM_PARMS 13 /* aliases for generation parameters */ alpar@6: #define NODES parms[0] /* number of nodes */ alpar@6: #define SOURCES parms[1] /* number of sources (including transshipment) */ alpar@6: #define SINKS parms[2] /* number of sinks (including transshipment) */ alpar@6: #define DENSITY parms[3] /* number of (requested) arcs */ alpar@6: #define MINCOST parms[4] /* minimum cost of arcs */ alpar@6: #define MAXCOST parms[5] /* maximum cost of arcs */ alpar@6: #define SUPPLY parms[6] /* total supply */ alpar@6: #define TSOURCES parms[7] /* transshipment sources */ alpar@6: #define TSINKS parms[8] /* transshipment sinks */ alpar@6: #define HICOST parms[9] /* percent of skeleton arcs given maximum cost */ alpar@6: #define CAPACITATED parms[10] /* percent of arcs to be capacitated */ alpar@6: #define MINCAP parms[11] /* minimum capacity for capacitated arcs */ alpar@6: #define MAXCAP parms[12] /* maximum capacity for capacitated arcs */ alpar@6: 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@6: int main() alpar@6: { alpar@6: long seed; alpar@6: long problem; alpar@6: long parms[PROBLEM_PARMS]; alpar@6: long arcs; alpar@6: int i; alpar@6: alpar@6: /*** Read problem parameters and generate networks */ alpar@6: alpar@6: while (1) { alpar@6: READ(seed); alpar@6: if (seed <= 0) exit(0); alpar@6: READ(problem); alpar@6: if (problem <= 0) exit(0); alpar@6: for (i = 0; i < PROBLEM_PARMS; i++) alpar@6: READ(parms[i]); 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