# HG changeset patch # User Alpar Juttner # Date 1290795827 -3600 # Node ID a3ef33a8694ab99191623f6b948fdbd5926fb212 # Parent 723af8fef5295490e64b5512e115961ef3a98d4b Add netgen generator diff -r 723af8fef529 -r a3ef33a8694a CMakeLists.txt --- a/CMakeLists.txt Fri Nov 26 17:59:31 2010 +0100 +++ b/CMakeLists.txt Fri Nov 26 19:23:47 2010 +0100 @@ -61,25 +61,6 @@ ${LEMON_INCLUDE_DIRS} ) -## Here we define an executable target. Its name is 'lemon-project' and -## is compiled from 'main.cc'. You can add more source files separated -## with whitespaces (including newlines). If you want to build more -## executables, simple repeat (and edit) the following ADD_EXECUTABLE and -## TARGET_LINK_LIBRARIES statements. - -ADD_EXECUTABLE(lemon-project main.cc) -TARGET_LINK_LIBRARIES(lemon-project ${LEMON_LIBRARIES}) - -## This tells cmake to install 'lemon-project' to $PREFIX/bin when -## 'make install' is executed. You can give more targets separated -## by whitespaces. - -INSTALL( - TARGETS lemon-project - RUNTIME DESTINATION bin - COMPONENT bin -) - ## Sometimes MSVC overwhelms you with compiler warnings which are impossible to ## avoid. Then comment out these sections. Normally you won't need it as the ## LEMON include headers suppress these warnings anyway. @@ -103,6 +84,8 @@ ADD_SUBDIRECTORY(doc) +ADD_SUBDIRECTORY(generators/netgen) + ####################################################################### ## CPACK configuration ## diff -r 723af8fef529 -r a3ef33a8694a generators/netgen/CMakeLists.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/generators/netgen/CMakeLists.txt Fri Nov 26 19:23:47 2010 +0100 @@ -0,0 +1,14 @@ +INCLUDE_DIRECTORIES( + # ${CMAKE_SOURCE_DIR}/tests + # ${CMAKE_BINARY_DIR}/src +) + +LINK_DIRECTORIES( + # ${CMAKE_BINARY_DIR}/lemon +) + +ADD_EXECUTABLE(netgen + netgen.c index.c random.c +) + +SET_TARGET_PROPERTIES(netgen PROPERTIES COMPILE_DEFINITIONS "DIMACS") \ No newline at end of file diff -r 723af8fef529 -r a3ef33a8694a generators/netgen/index.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/generators/netgen/index.c Fri Nov 26 19:23:47 2010 +0100 @@ -0,0 +1,342 @@ +/*** Copyright 1989 Norbert Schlenker. All rights reserved. + + *** This software is distributed subject to the following provisions: + *** - this notice may not be removed; + *** - you may modify the source code, as long as redistributed + *** versions have their modifications clearly marked; + *** - no charge, other than a nominal copying fee, may be made + *** when providing copies of this source code to others; + *** - if this source code is used as part of a product which is + *** distributed only as a binary, a copy of this source code + *** must be included in the distribution. + *** + *** Unlike the GNU GPL, use of this code does not obligate you to + *** disclose your own proprietary source code. + + *** The author of this software provides no warranty, express or + *** implied, as to its utility or correctness. That said, reports + *** of bugs or compatibility problems will be gladly received by + *** nfs@princeton.edu, and fixes will be attempted. + ***/ + + +/*** index.c - routines to manipulate index lists */ + +/*** Definition: An "index list" is an ascending sequence of positive + *** integers that can be operated upon as follows: + *** + *** make_index_list - makes an index list of consecutive + *** integers from some lower bound through an upper bound. + *** choose_index - given a number "k", removes the integer + *** in the k'th position in the index list and returns it. + *** Requests for positions less than 1 or greater than + *** the current list length return zero. + *** remove_index - removes a specified integer from the + *** index list. Requests to remove integers not in the + *** list are ignored, except that they reduce the list's + *** "pseudo_size" (see below). + *** index_size - returns the number of integers in the + *** index list. + *** pseudo_size - returns the number of integers in the + *** index list, less the number for which remove_index + *** failed due to a request to remove a non-existent one. + *** (Note that this is here solely to support an apparent + *** bug in the original definition of the NETGEN program.) + + *** Two simple methods of accomplishing these functions are: + *** - allocating an array of flags that indicate whether a particular + *** integer is valid, and searching the array during the choose_index + *** operation for the k'th valid integer. + *** - allocating a linked list for the indices and updating the list + *** during both the choose_index and remove_index operations. + *** + *** For small index lists, the first of these methods is quite efficient + *** and is, in fact, implemented in the following code. Unfortunately, + *** for the uses we have in mind (i.e. NETGEN), the typical access pattern + *** to index lists involves a large list, with both choose_index and + *** remove_index operations occurring at random positions in the list. + *** + *** As a result, the code has been extended for the case of large lists. + *** The enclosed implementation makes use of a binary interval tree, which + *** records information regarding the valid intervals from which indices + *** may be chosen. At a cost of a substantial increase in space requirements, + *** and under rather generous assumptions regarding the randomness of the + *** positions supplied to choose_index, running time becomes logarithmic + *** per choose_index and remove_index operation. + ***/ + +#include "netgen.h" + +/*** Useful constants */ +#define FLAG_LIMIT 100 /* upper limit for simple implementation */ + + +/*** Internally useful types */ +typedef unsigned char FLAG; + +typedef struct index_header { + INDEX original_size; /* original size of index */ + INDEX index_size; /* number of indices in the index */ + INDEX pseudo_size; /* almost the number of indices in the index */ + union { + INDEX index_base; /* base of index list - small case */ + INDEX index_nodes; /* number of nodes in the interval tree - large case */ + } i; + union { + FLAG* flag; /* pointer to flag array - small */ + struct interval_node* first_node; /* pointer to root of interval tree - large */ + } p; +} HEADER; + +typedef struct interval_node { + INDEX base; /* smallest integer in this subtree */ + INDEX count; /* count of indices in this subtree */ + struct interval_node* left_child; /* pointers down the tree */ +} INODE; + + +/*** Static storage */ + +static INDEX_LIST active_handles = 0; +static HEADER* index_headers = NULL; + + +/*** Make a new index list with a specified range. Returns an integer handle + *** to identify the list, or -1 if an error occurs. + ***/ +INDEX_LIST make_index_list(from, to) +INDEX from; /* lower limit of index list */ +INDEX to; /* upper limit of index list */ +{ + INDEX_LIST handle = 0; + HEADER* hp; + INODE* np; + + if (from <= 0 || from > to) /* sanity check */ + return -1; + +/*** Find an inactive list header or allocate a new one. */ + for (hp = index_headers; handle < active_handles; hp++, handle++) { + if (hp->original_size == 0) + break; + } + if (handle == active_handles) { + ++active_handles; + if (handle == 0) + index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER)); + else + index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER)); + } + if (index_headers == NULL) + return -1; + + +/*** Fill in the list header and allocate space for the list. */ + hp = &index_headers[handle]; + hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1; + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */ + hp->i.index_base = from; + hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG)); + if (hp->p.flag == NULL) + return -1; + (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG)); + } else { /* LARGE */ + hp->i.index_nodes = 1; + np = (INODE*) malloc(hp->original_size * sizeof(INODE)); + if (np == NULL) + return -1; + hp->p.first_node = np; + np->base = from; + np->count = hp->original_size; + np->left_child = NULL; + } + return handle; +} + + +/*** Free an existing index list. The header is zeroed afterwards + *** to indicate that it can be reused. + ***/ +void free_index_list(handle) +INDEX_LIST handle; +{ + HEADER* hp; + + if (handle < 0 || handle >= active_handles) /* sanity check */ + return; + + hp = &index_headers[handle]; + if (hp->p.flag) + free((void *)hp->p.flag); + (void)memset((void *)hp, 0, sizeof(HEADER)); +} + +/*** Choose the integer at a certain position in an index list. The + *** integer is then removed from the list so that it won't be chosen + *** again. Choose_index returns 0 if the position is invalid. + ***/ +INDEX choose_index(handle, position) +INDEX_LIST handle; +INDEX position; +{ + HEADER* hp; + FLAG* cp; + INODE* np; + INODE* npl; + INODE* npr; + INDEX index; + + if (handle < 0 || handle >= active_handles) /* sanity checks */ + return 0; + hp = &index_headers[handle]; + if (hp->p.flag == NULL) + return 0; + if (position < 1 || position > hp->index_size) + return 0; + +/*** Adjust counts of remaining indices. */ + hp->index_size--; + hp->pseudo_size--; + + +/*** Find the index we want and remove it from the list. */ + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */ + for (cp = hp->p.flag; position > 0; cp++) + if (!*cp) + position--; + *(--cp) = 1; + return hp->i.index_base + (INDEX)(cp - hp->p.flag); + } else { /* LARGE */ + np = hp->p.first_node; + while (np->left_child) { + np->count--; + np = np->left_child; + if (position > np->count) { + position -= np->count; + np++; + } + } + np->count--; + if (position == 1) { /* beginning of interval */ + index = np->base++; + } + else + if (position > np->count) { /* end of interval */ + index = np->base + np->count; + } + else /* middle of interval - split it */ + { + index = np->base + position - 1; + npl = np->left_child = hp->p.first_node + hp->i.index_nodes; + npr = npl + 1; + hp->i.index_nodes += 2; + npl->base = np->base; + npl->count = position - 1; + npl->left_child = NULL; + npr->base = index + 1; + npr->count = np->count - npl->count; + npr->left_child = NULL; + } + return index; + } +} + +/*** Remove a particular integer from an index list. If the integer + *** does not exist in the list, we reduce the list's pseudo-size, + *** but return no error indication. + ***/ +void remove_index(handle, index) +INDEX_LIST handle; +INDEX index; +{ + HEADER* hp; + FLAG* cp; + INODE* np; + INODE* npl; + INODE* npr; + + if (handle < 0 || handle >= active_handles) /* sanity checks */ + return; + hp = &index_headers[handle]; + if (hp->p.flag == NULL) + return; + +/*** Adjust the pseudo-size before looking for the index. */ + hp->pseudo_size--; + +/*** Remove the index from the index list. */ + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */ + if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size) + return; + cp = hp->p.flag + (index - hp->i.index_base); + if (!*cp) { + *cp = 1; + hp->index_size--; + } + return; + } else { /* LARGE */ + np = hp->p.first_node; + while (np->left_child) { + np->count--; + np = np->left_child + 1; + if (index < np->base) + np--; + } + if (index < np->base || index >= np->base + np->count) { /* mistake - back out */ + np = hp->p.first_node; + while (np->left_child) { + np->count++; + np = np->left_child + 1; + if (index < np->base) + np--; + } + return; + } + np->count--; + if (index == np->base) { /* beginning of interval */ + np->base++; + } + else + if (index == np->base + np->count) { /* end of interval */ + } + else /* middle of interval - split it */ + { + npl = np->left_child = hp->p.first_node + hp->i.index_nodes; + npr = npl + 1; + hp->i.index_nodes += 2; + npl->base = np->base; + npl->count = index - np->base; + npl->left_child = NULL; + npr->base = index + 1; + npr->count = np->count - npl->count; + npr->left_child = NULL; + } + hp->index_size--; + return; + } +} + + +/*** Return actual number of remaining entries in the index list. + ***/ +INDEX index_size(handle) +INDEX_LIST handle; +{ + if (handle < 0 || handle >= active_handles) /* sanity check */ + return 0; + + return index_headers[handle].index_size; +} + + +/*** Return a peculiar number, vaguely related to the number of + *** remaining entries in the index list. Required by NETGEN. + ***/ +INDEX pseudo_size(handle) +INDEX_LIST handle; +{ + if (handle < 0 || handle >= active_handles) /* sanity check */ + return 0; + + return index_headers[handle].pseudo_size; +} diff -r 723af8fef529 -r a3ef33a8694a generators/netgen/netgen.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/generators/netgen/netgen.c Fri Nov 26 19:23:47 2010 +0100 @@ -0,0 +1,574 @@ +/*** Copyright 1989 Norbert Schlenker. All rights reserved. + + *** This software is distributed subject to the following provisions: + *** - this notice may not be removed; + *** - you may modify the source code, as long as redistributed + *** versions have their modifications clearly marked; + *** - no charge, other than a nominal copying fee, may be made + *** when providing copies of this source code to others; + *** - if this source code is used as part of a product which is + *** distributed only as a binary, a copy of this source code + *** must be included in the distribution. + *** + *** Unlike the GNU GPL, use of this code does not obligate you to + *** disclose your own proprietary source code. + + *** The author of this software provides no warranty, express or + *** implied, as to its utility or correctness. That said, reports + *** of bugs or compatibility problems will be gladly received by + *** nfs@princeton.edu, and fixes will be attempted. + ***/ + + +/*** netgen - C version of the standard NETGEN network generator + *** This program is a functional equivalent of the + *** standard network generator NETGEN described in: + *** Klingman, D., A. Napier, and J. Stutz, "NETGEN: A Program + *** for Generating Large Scale Capacitated Assignment, + *** Transportation, and Minimum Cost Flow Network Problems", + *** Management Science 20, 5, 814-821 (1974) + *** + *** This software provides a number of interfaces for use by + *** network solvers. Standard call interfaces are supplied for + *** use by (Unix) C and Fortran solvers, with generation parameters + *** passed into the generator and the flow network passed back to + *** the solver via large external (COMMON in Fortran) arrays. + *** For the DIMACS challenge, this code will produce output files + *** in the appropriate format for later reading by solvers. + *** Undefine the symbol DIMACS when using the call interface. + *** + *** The generator produces exact duplicates of the networks + *** made by the Fortran code (even though that means bugs + *** are being perpetuated). It is faster by orders of magnitude + *** in generating large networks, primarily by imposing the + *** notion of the abstract data type INDEX_LIST and implementing + *** the type operations in a reasonably efficient fashion. + ***/ + +/*** Generates transportation problems if: + *** SOURCES+SINKS == NODES && TSOURCES == TSINKS == 0 + *** + *** Generates assignment problems if above conditions are satisfied, and: + *** SOURCES == SINKS && SUPPLY == SOURCES + *** + *** Generates maximum flow problems if not an assignment problem and: + *** MINCOST == MAXCOST == 1 + + *** Implementation notes: + *** + *** This file contains both a Fortran and a C interface. The + *** Fortran interface is suffixed with an underscore to make it + *** callable in the normal fashion from Fortran (a Unix convention). + *** + *** Because Fortran has no facility for pointers, the common arrays + *** are statically allocated. Static allocation has nothing to recommend + *** it except for the need for a Fortran interface. + *** + *** This software expects input parameters to be long integers + *** (in the sense of C); that means no INTEGER*2 from Fortran callers. + *** + *** Compiling with -DDIMACS produces a program that reads problem + *** parameters, generates the appropriate problem, and prints it. + *** + *** Compiling with -DDEBUG produces code with externally visible + *** procedure names, useful for debugging and profiling. + ***/ + + +/*** System interfaces */ + +#include + + +/*** Public interfaces */ + +#define ALLOCATE_NETWORK +#include "netgen.h" + +#define PROBLEM_PARMS 13 /* aliases for generation parameters */ +#define NODES parms[0] /* number of nodes */ +#define SOURCES parms[1] /* number of sources (including transshipment) */ +#define SINKS parms[2] /* number of sinks (including transshipment) */ +#define DENSITY parms[3] /* number of (requested) arcs */ +#define MINCOST parms[4] /* minimum cost of arcs */ +#define MAXCOST parms[5] /* maximum cost of arcs */ +#define SUPPLY parms[6] /* total supply */ +#define TSOURCES parms[7] /* transshipment sources */ +#define TSINKS parms[8] /* transshipment sinks */ +#define HICOST parms[9] /* percent of skeleton arcs given maximum cost */ +#define CAPACITATED parms[10] /* percent of arcs to be capacitated */ +#define MINCAP parms[11] /* minimum capacity for capacitated arcs */ +#define MAXCAP parms[12] /* maximum capacity for capacitated arcs */ + + +/*** Private interfaces */ + +#ifdef DEBUG +#define PRIVATE +#else +#define PRIVATE static +#endif + +#ifdef __STDC__ +PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */ +PRIVATE void create_assignment(long*); /* create assignment problem */ +PRIVATE void sort_skeleton(int); /* sorts skeleton chains */ +PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */ +PRIVATE void error_exit(long); /* print error message and exit */ +#else +PRIVATE void create_supply(); /* create supply nodes */ +PRIVATE void create_assignment(); /* create assignment problem */ +PRIVATE void sort_skeleton(); /* sorts skeleton chains */ +PRIVATE void pick_head(); /* chooses destination nodes for rubbish arcs */ +PRIVATE void error_exit(); /* print error message and exit */ +#endif + +/*** Private variables */ + +static NODE nodes_left; +static ARC arc_count; +static NODE pred[MAXARCS]; +static NODE head[MAXARCS]; +static NODE tail[MAXARCS]; + + +/*** Local macros */ + +#define MIN(x, y) ((x) < (y) ? (x) : (y)) +#define MAX(x, y) ((x) > (y) ? (x) : (y)) +#define SAVE_ARC(tail, head, cost, capacity) /* records an arc where our caller can get it */ \ + { \ + FROM[arc_count] = tail; \ + TO [arc_count] = head; \ + C [arc_count] = cost; \ + U [arc_count] = capacity; \ + arc_count++; \ + } + + +/*** Fortran callable interface routine */ + +void netgen_(seed, parms, generated_nodes, generated_arcs) +long* seed; /* pointer to random seed */ +long parms[PROBLEM_PARMS]; /* problem parameters */ +long* generated_nodes; /* number of generated nodes */ +long* generated_arcs; /* number of generated arcs */ +{ + *generated_nodes = NODES; + if ((*generated_arcs = netgen(*seed, parms)) < 0) + error_exit(*generated_arcs); +} + + +/*** C callable interface routine */ + +ARC netgen(seed, parms) +long seed; /* random seed */ +long parms[]; /* problem parameters */ +{ + register NODE i,j,k; + NODE source; + NODE node; + NODE sinks_per_source; + NODE* sinks; + NODE it; + int chain_length; + COST cost; + CAPACITY cap; + INDEX_LIST handle; + int supply_per_sink; + int partial_supply; + int sort_count; + + +/*** Perform sanity checks on the input */ + + if (seed <= 0) + return BAD_SEED; + if (NODES > MAXNODES || DENSITY > MAXARCS) + return TOO_BIG; + if ((NODES <= 0) || + (NODES > DENSITY) || + (SOURCES <= 0) || + (SINKS <= 0) || + (SOURCES + SINKS > NODES) || + (MINCOST > MAXCOST) || + (SUPPLY < SOURCES) || + (TSOURCES > SOURCES) || + (TSINKS > SINKS) || + (HICOST < 0 || HICOST > 100) || + (CAPACITATED < 0 || CAPACITATED > 100) || + (MINCAP > MAXCAP)) + return BAD_PARMS; + + +/*** Do a little bit of setting up. */ + + set_random(seed); + + arc_count = 0; + nodes_left = NODES - SINKS + TSINKS; + + if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES && + (SOURCES-TSOURCES) == (SINKS-TSINKS) && + SOURCES == SUPPLY) { + create_assignment(parms); + return arc_count; + } + + (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */ + + create_supply((NODE)SOURCES, (CAPACITY)SUPPLY); + + +/*** Form most of the network skeleton. First, 60% of the transshipment + *** nodes are divided evenly among the various sources; the remainder + *** are chained onto the end of the chains belonging to random sources. + ***/ + + for (i = 1; i <= SOURCES; i++) /* point SOURCES at themselves */ + pred[i] = i; + handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS)); + source = 1; + for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) { + node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle))); + pred[node] = pred[source]; + pred[source] = node; + if (++source > SOURCES) + source = 1; + } + for ( ; i > 0; --i) { + node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle))); + source = ng_random(1L, SOURCES); + pred[node] = pred[source]; + pred[source] = node; + } + free_index_list(handle); + + +/*** For each source chain, hook it to an "appropriate" number of sinks, + *** place capacities and costs on the skeleton edges, and then call + *** pick_head to add a bunch of rubbish edges at each node on the chain. + ***/ + + for (source = 1; source <= SOURCES; source++) { + sort_count = 0; + node = pred[source]; + while (node != source) { + sort_count++; + head[sort_count] = node; + node = tail[sort_count] = pred[node]; + } + if ((NODES-SOURCES-SINKS) == 0) + sinks_per_source = SINKS/SOURCES + 1; + else +/* changing to handle overflows with large n; Mar 18 -- jc */ + sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS); + sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS)); + sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE)); + handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1)); + for (i = 0; i < sinks_per_source; i++) { + sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle))); + } + if (source == SOURCES && index_size(handle) > 0) { + sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE)); + while (index_size(handle) > 0) { + j = choose_index(handle, 1); + if (B[j] == 0) + sinks[sinks_per_source++] = j; + } + } + free_index_list(handle); + + chain_length = sort_count; + supply_per_sink = B[source-1] / sinks_per_source; + k = pred[source]; + for (i = 0; i < sinks_per_source; i++) { + sort_count++; + partial_supply = ng_random(1L, (long)supply_per_sink); + j = ng_random(0L, (long)sinks_per_source - 1); + tail[sort_count] = k; + head[sort_count] = sinks[i] + 1; + B[sinks[i]] -= partial_supply; + B[sinks[j]] -= (supply_per_sink - partial_supply); + k = source; + for (j = ng_random(1L, (long)chain_length); j > 0; j--) + k = pred[k]; + } + B[sinks[0]] -= (B[source-1] % sinks_per_source); + free((void *)sinks); + + sort_skeleton(sort_count); + tail[sort_count+1] = 0; + for (i = 1; i <= sort_count; ) { + handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES); + remove_index(handle, (INDEX)tail[i]); + it = tail[i]; + while (it == tail[i]) { + remove_index(handle, (INDEX)head[i]); + cap = SUPPLY; + if (ng_random(1L, 100L) <= CAPACITATED) + cap = MAX(B[source-1], MINCAP); + cost = MAXCOST; + if (ng_random(1L, 100L) > HICOST) + cost = ng_random(MINCOST, MAXCOST); + SAVE_ARC(it,head[i],cost,cap); + i++; + } + pick_head(parms, handle, it); + free_index_list(handle); + } + } + + +/*** Add more rubbish edges out of the transshipment sinks. */ + + for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) { + handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES); + remove_index(handle, (INDEX)i); + pick_head(parms, handle, i); + free_index_list(handle); + } + + return arc_count; +} + + +PRIVATE void create_supply(sources, supply) +NODE sources; +CAPACITY supply; +{ + CAPACITY supply_per_source = supply / sources; + CAPACITY partial_supply; + NODE i; + + for (i = 0; i < sources; i++) { + B[i] += (partial_supply = ng_random(1L, (long)supply_per_source)); + B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply; + } + B[ng_random(0L, (long)(sources - 1))] += supply % sources; +} + + +PRIVATE void create_assignment(parms) +long parms[]; +{ + INDEX_LIST skeleton, handle; + INDEX index; + NODE source; + + for (source = 0; source < NODES/2; source++) + B[source] = 1; + for ( ; source < NODES; source++) + B[source] = -1; + + skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES); + for (source = 1; source <= NODES/2; source++) { + index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton))); + SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1); + handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES); + remove_index(handle, index); + pick_head(parms, handle, source); + free_index_list(handle); + } + free_index_list(skeleton); +} + + +PRIVATE void sort_skeleton(sort_count) /* Shell sort */ +int sort_count; +{ + int m,i,j,k; + int temp; + + m = sort_count; + while ((m /= 2) != 0) { + k = sort_count - m; + for (j = 1; j <= k; j++) { + i = j; + while (i >= 1 && tail[i] > tail[i+m]) { + temp = tail[i]; + tail[i] = tail[i+m]; + tail[i+m] = temp; + temp = head[i]; + head[i] = head[i+m]; + head[i+m] = temp; + i -= m; + } + } + } +} + + +PRIVATE void pick_head(parms, handle, desired_tail) +long parms[]; +INDEX_LIST handle; +NODE desired_tail; +{ + NODE non_sources = NODES - SOURCES + TSOURCES; + +/* changing Aug 29 -- jc + ARC remaining_arcs = DENSITY - arc_count; +*/ + int remaining_arcs = (int) DENSITY - (int) arc_count; + + INDEX index; + int limit; + long upper_bound; + CAPACITY cap; + +/* changing Aug 29 -- jc +*/ + nodes_left--; + if ((2 * (int) nodes_left) >= (int) remaining_arcs) + return; + + if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) { + limit = non_sources; + } else { + upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1); + do { + limit = ng_random(1L, upper_bound); + if (nodes_left == 0) + limit = remaining_arcs; +/* changing to handle overflows with large n; Mar 18 -- jc */ + } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit)); + } + + for ( ; limit > 0; limit--) { + index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle))); + cap = SUPPLY; + if (ng_random(1L, 100L) <= CAPACITATED) + cap = ng_random(MINCAP, MAXCAP); + +/* adding Aug 29 -- jc */ +if ((1 <= index) && (index <= NODES)) { + SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap); + } + + } +} + + +/*** Print an appropriate error message and then exit with a nonzero code. */ + +PRIVATE void error_exit(rc) +long rc; +{ + switch (rc) { + case BAD_SEED: + fprintf(stderr, "NETGEN requires a positive random seed\n"); + break; + case TOO_BIG: + fprintf(stderr, "Problem too large for generator\n"); + break; + case BAD_PARMS: + fprintf(stderr, "Inconsistent parameter settings - check the input\n"); + break; + case ALLOCATION_FAILURE: + fprintf(stderr, "Memory allocation failure\n"); + break; + default: + fprintf(stderr, "Internal error\n"); + break; + } + exit(1000 - (int)rc); +} + +#ifdef DIMACS /* generates network on standard output */ + +#define READ(v) /* read one variable using scanf */ \ + switch( scanf("%ld", &v) ) { \ + case 1: \ + break; \ + default: \ + exit(0); \ + } + +int main() +{ + long seed; + long problem; + long parms[PROBLEM_PARMS]; + long arcs; + int i; + +/*** Read problem parameters and generate networks */ + + while (1) { + READ(seed); + if (seed <= 0) exit(0); + READ(problem); + if (problem <= 0) exit(0); + for (i = 0; i < PROBLEM_PARMS; i++) + READ(parms[i]); + printf("c NETGEN flow network generator (C version)\n"); + printf("c Problem %2ld input parameters\n", problem); + printf("c ---------------------------\n"); + printf("c Random seed: %10ld\n", seed); + printf("c Number of nodes: %10ld\n", NODES); + printf("c Source nodes: %10ld\n", SOURCES); + printf("c Sink nodes: %10ld\n", SINKS); + printf("c Number of arcs: %10ld\n", DENSITY); + printf("c Minimum arc cost: %10ld\n", MINCOST); + printf("c Maximum arc cost: %10ld\n", MAXCOST); + printf("c Total supply: %10ld\n", SUPPLY); + printf("c Transshipment -\n"); + printf("c Sources: %10ld\n", TSOURCES); + printf("c Sinks: %10ld\n", TSINKS); + printf("c Skeleton arcs -\n"); + printf("c With max cost: %10ld%%\n", HICOST); + printf("c Capacitated: %10ld%%\n", CAPACITATED); + printf("c Minimum arc capacity: %10ld\n", MINCAP); + printf("c Maximum arc capacity: %10ld\n", MAXCAP); + + if ((arcs = netgen(seed, parms)) < 0) + error_exit(arcs); + if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES && + (SOURCES-TSOURCES) == (SINKS-TSINKS) && + SOURCES == SUPPLY) { + printf("c\n"); + printf("c *** Assignment ***\n"); + printf("c\n"); + printf("p asn %ld %ld\n", NODES, arcs); + for (i = 0; i < NODES; i++) { + if (B[i] > 0) + printf("n %ld\n", i + 1); + } + for (i = 0; i < arcs; i++) { + printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]); + } + } else + if (MINCOST == 1 && MAXCOST == 1) { + printf("c\n"); + printf("c *** Maximum flow ***\n"); + printf("c\n"); + printf("p max %ld %ld\n", NODES, arcs); + for (i = 0; i < NODES; i++) { + if (B[i] > 0) + printf("n %ld s\n", i + 1); + else + if (B[i] < 0) + printf("n %ld t\n", i + 1); + } + for (i = 0; i < arcs; i++) { + printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]); + } + } else { + printf("c\n"); + printf("c *** Minimum cost flow ***\n"); + printf("c\n"); + printf("p min %ld %ld\n", NODES, arcs); + for (i = 0; i < NODES; i++) { + if (B[i] != 0) + printf("n %ld %ld\n", i + 1, B[i]); + } + for (i = 0; i < arcs; i++) { + printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]); + } + } + } + return 0; +} + +#endif diff -r 723af8fef529 -r a3ef33a8694a generators/netgen/netgen.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/generators/netgen/netgen.h Fri Nov 26 19:23:47 2010 +0100 @@ -0,0 +1,95 @@ +/*** netgen.h + *** Prototype code for inclusion into network generation routines + ***/ + +/*** Constant definitions */ + +#ifndef NULL +#define NULL 0 +#endif + +#define BAD_SEED -1 /* error indicators */ +#define TOO_BIG -2 +#define BAD_PARMS -3 +#define ALLOCATION_FAILURE -4 + + +/*** Type definitions */ + +typedef unsigned long NODE; /* node number */ +typedef unsigned long ARC; /* arc number */ +typedef long CAPACITY; /* arc capacity */ +typedef long COST; /* arc cost */ +typedef unsigned long INDEX; /* index element */ +typedef int INDEX_LIST; /* index list handle */ + + +/*** Function prototypes */ + +#ifdef __STDC__ + +#include +#include + +void netgen_(long*, long[], long*, long*); /* Fortran external interface */ +ARC netgen(long, long*); /* C external interface */ + +INDEX_LIST make_index_list(INDEX, INDEX); /* allocates a new index list */ +void free_index_list(INDEX_LIST); /* frees an existing list */ +INDEX choose_index(INDEX_LIST, INDEX); /* chooses index at specified position */ +void remove_index(INDEX_LIST, INDEX); /* removes specified index from list */ +INDEX index_size(INDEX_LIST); /* number of indices remaining */ +INDEX pseudo_size(INDEX_LIST); /* "modified" index size */ + +void set_random(long); /* initialize random seed */ +long ng_random(long, long); /* generate random integer in interval */ + +#else + +void *malloc(); /* some standard header should define this */ +void *realloc(); /* ditto */ +void free(); /* ditto */ +void *memset(); /* ditto */ +void exit(); /* ditto */ + +void netgen_(); /* Fortran external interface */ +ARC netgen(); /* C external interface */ + +INDEX_LIST make_index_list(); /* allocates a new index list */ +void free_index_list(); /* frees an existing list */ +INDEX choose_index(); /* chooses index at specified position */ +void remove_index(); /* removes specified index from list */ +INDEX index_size(); /* number of indices remaining */ +INDEX pseudo_size(); /* "modified" index size */ + +void set_random(); /* initialize random seed */ +long ng_random(); /* generate random integer in interval */ + +#endif + +/*** To maintain compatibility with the old Fortran network generator, + *** the following are defined. This allows linking the generator code + *** with the solver, with the generated network passed to the solver + *** through arrays in memory. + ***/ + +#define MAXNODES 10000000 /* maximum problem sizes */ +#define MAXARCS 40000000 + +#define FROM arrays_ /* aliases for network storage */ +#define TO arraye_ +#define U arrayu_ +#define C arrayc_ +#define B arrayb_ + +#ifdef ALLOCATE_NETWORK /* storage definitions */ +#define EXTERN +#else +#define EXTERN extern +#endif + +EXTERN NODE FROM[MAXARCS]; /* origin of each arc */ +EXTERN NODE TO [MAXARCS]; /* destination */ +EXTERN CAPACITY U [MAXARCS]; /* capacity */ +EXTERN COST C [MAXARCS]; /* cost */ +EXTERN CAPACITY B [MAXNODES]; /* supply (demand) at each node */ diff -r 723af8fef529 -r a3ef33a8694a generators/netgen/random.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/generators/netgen/random.c Fri Nov 26 19:23:47 2010 +0100 @@ -0,0 +1,47 @@ +/*** This is a portable random number generator whose origins are + *** unknown. As far as can be told, this is public domain software. + + +/*** portable random number generator */ + +/*** Note that every variable used here must have at least 31 bits + *** of precision, exclusive of sign. Long integers should be enough. + *** The generator is the congruential: i = 7**5 * i mod (2^31-1). + ***/ + +#define MULTIPLIER 16807 +#define MODULUS 2147483647 + +static long saved_seed; + + +/*** set_random - initialize constants and seed */ + +void set_random(seed) +long seed; +{ + saved_seed = seed; +} + + +/*** ng_random - generate a random integer in the interval [a,b] (b >= a >= 0) */ + +long ng_random(a, b) +long a, b; +{ + register long hi, lo; + + hi = MULTIPLIER * (saved_seed >> 16); + lo = MULTIPLIER * (saved_seed & 0xffff); + hi += (lo>>16); + lo &= 0xffff; + lo += (hi>>15); + hi &= 0x7fff; + lo -= MODULUS; + if ((saved_seed = (hi<<16) + lo) < 0) + saved_seed += MODULUS; + + if (b <= a) + return b; + return a + saved_seed % (b - a + 1); +} diff -r 723af8fef529 -r a3ef33a8694a main.cc --- a/main.cc Fri Nov 26 17:59:31 2010 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,26 +0,0 @@ -/* -*- mode: C++; indent-tabs-mode: nil; -*- - * - * This file is a part of LEMON, a generic C++ optimization library. - * - * Copyright (C) 2003-2009 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#include - -///The main entry point -int main() -{ - lemon::ListGraph g; - g.addNode(); -}