1.1 --- a/CMakeLists.txt Fri Nov 26 17:59:31 2010 +0100
1.2 +++ b/CMakeLists.txt Fri Nov 26 19:23:47 2010 +0100
1.3 @@ -61,25 +61,6 @@
1.4 ${LEMON_INCLUDE_DIRS}
1.5 )
1.6
1.7 -## Here we define an executable target. Its name is 'lemon-project' and
1.8 -## is compiled from 'main.cc'. You can add more source files separated
1.9 -## with whitespaces (including newlines). If you want to build more
1.10 -## executables, simple repeat (and edit) the following ADD_EXECUTABLE and
1.11 -## TARGET_LINK_LIBRARIES statements.
1.12 -
1.13 -ADD_EXECUTABLE(lemon-project main.cc)
1.14 -TARGET_LINK_LIBRARIES(lemon-project ${LEMON_LIBRARIES})
1.15 -
1.16 -## This tells cmake to install 'lemon-project' to $PREFIX/bin when
1.17 -## 'make install' is executed. You can give more targets separated
1.18 -## by whitespaces.
1.19 -
1.20 -INSTALL(
1.21 - TARGETS lemon-project
1.22 - RUNTIME DESTINATION bin
1.23 - COMPONENT bin
1.24 -)
1.25 -
1.26 ## Sometimes MSVC overwhelms you with compiler warnings which are impossible to
1.27 ## avoid. Then comment out these sections. Normally you won't need it as the
1.28 ## LEMON include headers suppress these warnings anyway.
1.29 @@ -103,6 +84,8 @@
1.30
1.31 ADD_SUBDIRECTORY(doc)
1.32
1.33 +ADD_SUBDIRECTORY(generators/netgen)
1.34 +
1.35 #######################################################################
1.36 ## CPACK configuration
1.37 ##
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/generators/netgen/CMakeLists.txt Fri Nov 26 19:23:47 2010 +0100
2.3 @@ -0,0 +1,14 @@
2.4 +INCLUDE_DIRECTORIES(
2.5 + # ${CMAKE_SOURCE_DIR}/tests
2.6 + # ${CMAKE_BINARY_DIR}/src
2.7 +)
2.8 +
2.9 +LINK_DIRECTORIES(
2.10 + # ${CMAKE_BINARY_DIR}/lemon
2.11 +)
2.12 +
2.13 +ADD_EXECUTABLE(netgen
2.14 + netgen.c index.c random.c
2.15 +)
2.16 +
2.17 +SET_TARGET_PROPERTIES(netgen PROPERTIES COMPILE_DEFINITIONS "DIMACS")
2.18 \ No newline at end of file
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/generators/netgen/index.c Fri Nov 26 19:23:47 2010 +0100
3.3 @@ -0,0 +1,342 @@
3.4 +/*** Copyright 1989 Norbert Schlenker. All rights reserved.
3.5 +
3.6 + *** This software is distributed subject to the following provisions:
3.7 + *** - this notice may not be removed;
3.8 + *** - you may modify the source code, as long as redistributed
3.9 + *** versions have their modifications clearly marked;
3.10 + *** - no charge, other than a nominal copying fee, may be made
3.11 + *** when providing copies of this source code to others;
3.12 + *** - if this source code is used as part of a product which is
3.13 + *** distributed only as a binary, a copy of this source code
3.14 + *** must be included in the distribution.
3.15 + ***
3.16 + *** Unlike the GNU GPL, use of this code does not obligate you to
3.17 + *** disclose your own proprietary source code.
3.18 +
3.19 + *** The author of this software provides no warranty, express or
3.20 + *** implied, as to its utility or correctness. That said, reports
3.21 + *** of bugs or compatibility problems will be gladly received by
3.22 + *** nfs@princeton.edu, and fixes will be attempted.
3.23 + ***/
3.24 +
3.25 +
3.26 +/*** index.c - routines to manipulate index lists */
3.27 +
3.28 +/*** Definition: An "index list" is an ascending sequence of positive
3.29 + *** integers that can be operated upon as follows:
3.30 + ***
3.31 + *** make_index_list - makes an index list of consecutive
3.32 + *** integers from some lower bound through an upper bound.
3.33 + *** choose_index - given a number "k", removes the integer
3.34 + *** in the k'th position in the index list and returns it.
3.35 + *** Requests for positions less than 1 or greater than
3.36 + *** the current list length return zero.
3.37 + *** remove_index - removes a specified integer from the
3.38 + *** index list. Requests to remove integers not in the
3.39 + *** list are ignored, except that they reduce the list's
3.40 + *** "pseudo_size" (see below).
3.41 + *** index_size - returns the number of integers in the
3.42 + *** index list.
3.43 + *** pseudo_size - returns the number of integers in the
3.44 + *** index list, less the number for which remove_index
3.45 + *** failed due to a request to remove a non-existent one.
3.46 + *** (Note that this is here solely to support an apparent
3.47 + *** bug in the original definition of the NETGEN program.)
3.48 +
3.49 + *** Two simple methods of accomplishing these functions are:
3.50 + *** - allocating an array of flags that indicate whether a particular
3.51 + *** integer is valid, and searching the array during the choose_index
3.52 + *** operation for the k'th valid integer.
3.53 + *** - allocating a linked list for the indices and updating the list
3.54 + *** during both the choose_index and remove_index operations.
3.55 + ***
3.56 + *** For small index lists, the first of these methods is quite efficient
3.57 + *** and is, in fact, implemented in the following code. Unfortunately,
3.58 + *** for the uses we have in mind (i.e. NETGEN), the typical access pattern
3.59 + *** to index lists involves a large list, with both choose_index and
3.60 + *** remove_index operations occurring at random positions in the list.
3.61 + ***
3.62 + *** As a result, the code has been extended for the case of large lists.
3.63 + *** The enclosed implementation makes use of a binary interval tree, which
3.64 + *** records information regarding the valid intervals from which indices
3.65 + *** may be chosen. At a cost of a substantial increase in space requirements,
3.66 + *** and under rather generous assumptions regarding the randomness of the
3.67 + *** positions supplied to choose_index, running time becomes logarithmic
3.68 + *** per choose_index and remove_index operation.
3.69 + ***/
3.70 +
3.71 +#include "netgen.h"
3.72 +
3.73 +/*** Useful constants */
3.74 +#define FLAG_LIMIT 100 /* upper limit for simple implementation */
3.75 +
3.76 +
3.77 +/*** Internally useful types */
3.78 +typedef unsigned char FLAG;
3.79 +
3.80 +typedef struct index_header {
3.81 + INDEX original_size; /* original size of index */
3.82 + INDEX index_size; /* number of indices in the index */
3.83 + INDEX pseudo_size; /* almost the number of indices in the index */
3.84 + union {
3.85 + INDEX index_base; /* base of index list - small case */
3.86 + INDEX index_nodes; /* number of nodes in the interval tree - large case */
3.87 + } i;
3.88 + union {
3.89 + FLAG* flag; /* pointer to flag array - small */
3.90 + struct interval_node* first_node; /* pointer to root of interval tree - large */
3.91 + } p;
3.92 +} HEADER;
3.93 +
3.94 +typedef struct interval_node {
3.95 + INDEX base; /* smallest integer in this subtree */
3.96 + INDEX count; /* count of indices in this subtree */
3.97 + struct interval_node* left_child; /* pointers down the tree */
3.98 +} INODE;
3.99 +
3.100 +
3.101 +/*** Static storage */
3.102 +
3.103 +static INDEX_LIST active_handles = 0;
3.104 +static HEADER* index_headers = NULL;
3.105 +
3.106 +
3.107 +/*** Make a new index list with a specified range. Returns an integer handle
3.108 + *** to identify the list, or -1 if an error occurs.
3.109 + ***/
3.110 +INDEX_LIST make_index_list(from, to)
3.111 +INDEX from; /* lower limit of index list */
3.112 +INDEX to; /* upper limit of index list */
3.113 +{
3.114 + INDEX_LIST handle = 0;
3.115 + HEADER* hp;
3.116 + INODE* np;
3.117 +
3.118 + if (from <= 0 || from > to) /* sanity check */
3.119 + return -1;
3.120 +
3.121 +/*** Find an inactive list header or allocate a new one. */
3.122 + for (hp = index_headers; handle < active_handles; hp++, handle++) {
3.123 + if (hp->original_size == 0)
3.124 + break;
3.125 + }
3.126 + if (handle == active_handles) {
3.127 + ++active_handles;
3.128 + if (handle == 0)
3.129 + index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER));
3.130 + else
3.131 + index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER));
3.132 + }
3.133 + if (index_headers == NULL)
3.134 + return -1;
3.135 +
3.136 +
3.137 +/*** Fill in the list header and allocate space for the list. */
3.138 + hp = &index_headers[handle];
3.139 + hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1;
3.140 + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
3.141 + hp->i.index_base = from;
3.142 + hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG));
3.143 + if (hp->p.flag == NULL)
3.144 + return -1;
3.145 + (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG));
3.146 + } else { /* LARGE */
3.147 + hp->i.index_nodes = 1;
3.148 + np = (INODE*) malloc(hp->original_size * sizeof(INODE));
3.149 + if (np == NULL)
3.150 + return -1;
3.151 + hp->p.first_node = np;
3.152 + np->base = from;
3.153 + np->count = hp->original_size;
3.154 + np->left_child = NULL;
3.155 + }
3.156 + return handle;
3.157 +}
3.158 +
3.159 +
3.160 +/*** Free an existing index list. The header is zeroed afterwards
3.161 + *** to indicate that it can be reused.
3.162 + ***/
3.163 +void free_index_list(handle)
3.164 +INDEX_LIST handle;
3.165 +{
3.166 + HEADER* hp;
3.167 +
3.168 + if (handle < 0 || handle >= active_handles) /* sanity check */
3.169 + return;
3.170 +
3.171 + hp = &index_headers[handle];
3.172 + if (hp->p.flag)
3.173 + free((void *)hp->p.flag);
3.174 + (void)memset((void *)hp, 0, sizeof(HEADER));
3.175 +}
3.176 +
3.177 +/*** Choose the integer at a certain position in an index list. The
3.178 + *** integer is then removed from the list so that it won't be chosen
3.179 + *** again. Choose_index returns 0 if the position is invalid.
3.180 + ***/
3.181 +INDEX choose_index(handle, position)
3.182 +INDEX_LIST handle;
3.183 +INDEX position;
3.184 +{
3.185 + HEADER* hp;
3.186 + FLAG* cp;
3.187 + INODE* np;
3.188 + INODE* npl;
3.189 + INODE* npr;
3.190 + INDEX index;
3.191 +
3.192 + if (handle < 0 || handle >= active_handles) /* sanity checks */
3.193 + return 0;
3.194 + hp = &index_headers[handle];
3.195 + if (hp->p.flag == NULL)
3.196 + return 0;
3.197 + if (position < 1 || position > hp->index_size)
3.198 + return 0;
3.199 +
3.200 +/*** Adjust counts of remaining indices. */
3.201 + hp->index_size--;
3.202 + hp->pseudo_size--;
3.203 +
3.204 +
3.205 +/*** Find the index we want and remove it from the list. */
3.206 + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
3.207 + for (cp = hp->p.flag; position > 0; cp++)
3.208 + if (!*cp)
3.209 + position--;
3.210 + *(--cp) = 1;
3.211 + return hp->i.index_base + (INDEX)(cp - hp->p.flag);
3.212 + } else { /* LARGE */
3.213 + np = hp->p.first_node;
3.214 + while (np->left_child) {
3.215 + np->count--;
3.216 + np = np->left_child;
3.217 + if (position > np->count) {
3.218 + position -= np->count;
3.219 + np++;
3.220 + }
3.221 + }
3.222 + np->count--;
3.223 + if (position == 1) { /* beginning of interval */
3.224 + index = np->base++;
3.225 + }
3.226 + else
3.227 + if (position > np->count) { /* end of interval */
3.228 + index = np->base + np->count;
3.229 + }
3.230 + else /* middle of interval - split it */
3.231 + {
3.232 + index = np->base + position - 1;
3.233 + npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
3.234 + npr = npl + 1;
3.235 + hp->i.index_nodes += 2;
3.236 + npl->base = np->base;
3.237 + npl->count = position - 1;
3.238 + npl->left_child = NULL;
3.239 + npr->base = index + 1;
3.240 + npr->count = np->count - npl->count;
3.241 + npr->left_child = NULL;
3.242 + }
3.243 + return index;
3.244 + }
3.245 +}
3.246 +
3.247 +/*** Remove a particular integer from an index list. If the integer
3.248 + *** does not exist in the list, we reduce the list's pseudo-size,
3.249 + *** but return no error indication.
3.250 + ***/
3.251 +void remove_index(handle, index)
3.252 +INDEX_LIST handle;
3.253 +INDEX index;
3.254 +{
3.255 + HEADER* hp;
3.256 + FLAG* cp;
3.257 + INODE* np;
3.258 + INODE* npl;
3.259 + INODE* npr;
3.260 +
3.261 + if (handle < 0 || handle >= active_handles) /* sanity checks */
3.262 + return;
3.263 + hp = &index_headers[handle];
3.264 + if (hp->p.flag == NULL)
3.265 + return;
3.266 +
3.267 +/*** Adjust the pseudo-size before looking for the index. */
3.268 + hp->pseudo_size--;
3.269 +
3.270 +/*** Remove the index from the index list. */
3.271 + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
3.272 + if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size)
3.273 + return;
3.274 + cp = hp->p.flag + (index - hp->i.index_base);
3.275 + if (!*cp) {
3.276 + *cp = 1;
3.277 + hp->index_size--;
3.278 + }
3.279 + return;
3.280 + } else { /* LARGE */
3.281 + np = hp->p.first_node;
3.282 + while (np->left_child) {
3.283 + np->count--;
3.284 + np = np->left_child + 1;
3.285 + if (index < np->base)
3.286 + np--;
3.287 + }
3.288 + if (index < np->base || index >= np->base + np->count) { /* mistake - back out */
3.289 + np = hp->p.first_node;
3.290 + while (np->left_child) {
3.291 + np->count++;
3.292 + np = np->left_child + 1;
3.293 + if (index < np->base)
3.294 + np--;
3.295 + }
3.296 + return;
3.297 + }
3.298 + np->count--;
3.299 + if (index == np->base) { /* beginning of interval */
3.300 + np->base++;
3.301 + }
3.302 + else
3.303 + if (index == np->base + np->count) { /* end of interval */
3.304 + }
3.305 + else /* middle of interval - split it */
3.306 + {
3.307 + npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
3.308 + npr = npl + 1;
3.309 + hp->i.index_nodes += 2;
3.310 + npl->base = np->base;
3.311 + npl->count = index - np->base;
3.312 + npl->left_child = NULL;
3.313 + npr->base = index + 1;
3.314 + npr->count = np->count - npl->count;
3.315 + npr->left_child = NULL;
3.316 + }
3.317 + hp->index_size--;
3.318 + return;
3.319 + }
3.320 +}
3.321 +
3.322 +
3.323 +/*** Return actual number of remaining entries in the index list.
3.324 + ***/
3.325 +INDEX index_size(handle)
3.326 +INDEX_LIST handle;
3.327 +{
3.328 + if (handle < 0 || handle >= active_handles) /* sanity check */
3.329 + return 0;
3.330 +
3.331 + return index_headers[handle].index_size;
3.332 +}
3.333 +
3.334 +
3.335 +/*** Return a peculiar number, vaguely related to the number of
3.336 + *** remaining entries in the index list. Required by NETGEN.
3.337 + ***/
3.338 +INDEX pseudo_size(handle)
3.339 +INDEX_LIST handle;
3.340 +{
3.341 + if (handle < 0 || handle >= active_handles) /* sanity check */
3.342 + return 0;
3.343 +
3.344 + return index_headers[handle].pseudo_size;
3.345 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/generators/netgen/netgen.c Fri Nov 26 19:23:47 2010 +0100
4.3 @@ -0,0 +1,574 @@
4.4 +/*** Copyright 1989 Norbert Schlenker. All rights reserved.
4.5 +
4.6 + *** This software is distributed subject to the following provisions:
4.7 + *** - this notice may not be removed;
4.8 + *** - you may modify the source code, as long as redistributed
4.9 + *** versions have their modifications clearly marked;
4.10 + *** - no charge, other than a nominal copying fee, may be made
4.11 + *** when providing copies of this source code to others;
4.12 + *** - if this source code is used as part of a product which is
4.13 + *** distributed only as a binary, a copy of this source code
4.14 + *** must be included in the distribution.
4.15 + ***
4.16 + *** Unlike the GNU GPL, use of this code does not obligate you to
4.17 + *** disclose your own proprietary source code.
4.18 +
4.19 + *** The author of this software provides no warranty, express or
4.20 + *** implied, as to its utility or correctness. That said, reports
4.21 + *** of bugs or compatibility problems will be gladly received by
4.22 + *** nfs@princeton.edu, and fixes will be attempted.
4.23 + ***/
4.24 +
4.25 +
4.26 +/*** netgen - C version of the standard NETGEN network generator
4.27 + *** This program is a functional equivalent of the
4.28 + *** standard network generator NETGEN described in:
4.29 + *** Klingman, D., A. Napier, and J. Stutz, "NETGEN: A Program
4.30 + *** for Generating Large Scale Capacitated Assignment,
4.31 + *** Transportation, and Minimum Cost Flow Network Problems",
4.32 + *** Management Science 20, 5, 814-821 (1974)
4.33 + ***
4.34 + *** This software provides a number of interfaces for use by
4.35 + *** network solvers. Standard call interfaces are supplied for
4.36 + *** use by (Unix) C and Fortran solvers, with generation parameters
4.37 + *** passed into the generator and the flow network passed back to
4.38 + *** the solver via large external (COMMON in Fortran) arrays.
4.39 + *** For the DIMACS challenge, this code will produce output files
4.40 + *** in the appropriate format for later reading by solvers.
4.41 + *** Undefine the symbol DIMACS when using the call interface.
4.42 + ***
4.43 + *** The generator produces exact duplicates of the networks
4.44 + *** made by the Fortran code (even though that means bugs
4.45 + *** are being perpetuated). It is faster by orders of magnitude
4.46 + *** in generating large networks, primarily by imposing the
4.47 + *** notion of the abstract data type INDEX_LIST and implementing
4.48 + *** the type operations in a reasonably efficient fashion.
4.49 + ***/
4.50 +
4.51 +/*** Generates transportation problems if:
4.52 + *** SOURCES+SINKS == NODES && TSOURCES == TSINKS == 0
4.53 + ***
4.54 + *** Generates assignment problems if above conditions are satisfied, and:
4.55 + *** SOURCES == SINKS && SUPPLY == SOURCES
4.56 + ***
4.57 + *** Generates maximum flow problems if not an assignment problem and:
4.58 + *** MINCOST == MAXCOST == 1
4.59 +
4.60 + *** Implementation notes:
4.61 + ***
4.62 + *** This file contains both a Fortran and a C interface. The
4.63 + *** Fortran interface is suffixed with an underscore to make it
4.64 + *** callable in the normal fashion from Fortran (a Unix convention).
4.65 + ***
4.66 + *** Because Fortran has no facility for pointers, the common arrays
4.67 + *** are statically allocated. Static allocation has nothing to recommend
4.68 + *** it except for the need for a Fortran interface.
4.69 + ***
4.70 + *** This software expects input parameters to be long integers
4.71 + *** (in the sense of C); that means no INTEGER*2 from Fortran callers.
4.72 + ***
4.73 + *** Compiling with -DDIMACS produces a program that reads problem
4.74 + *** parameters, generates the appropriate problem, and prints it.
4.75 + ***
4.76 + *** Compiling with -DDEBUG produces code with externally visible
4.77 + *** procedure names, useful for debugging and profiling.
4.78 + ***/
4.79 +
4.80 +
4.81 +/*** System interfaces */
4.82 +
4.83 +#include <stdio.h>
4.84 +
4.85 +
4.86 +/*** Public interfaces */
4.87 +
4.88 +#define ALLOCATE_NETWORK
4.89 +#include "netgen.h"
4.90 +
4.91 +#define PROBLEM_PARMS 13 /* aliases for generation parameters */
4.92 +#define NODES parms[0] /* number of nodes */
4.93 +#define SOURCES parms[1] /* number of sources (including transshipment) */
4.94 +#define SINKS parms[2] /* number of sinks (including transshipment) */
4.95 +#define DENSITY parms[3] /* number of (requested) arcs */
4.96 +#define MINCOST parms[4] /* minimum cost of arcs */
4.97 +#define MAXCOST parms[5] /* maximum cost of arcs */
4.98 +#define SUPPLY parms[6] /* total supply */
4.99 +#define TSOURCES parms[7] /* transshipment sources */
4.100 +#define TSINKS parms[8] /* transshipment sinks */
4.101 +#define HICOST parms[9] /* percent of skeleton arcs given maximum cost */
4.102 +#define CAPACITATED parms[10] /* percent of arcs to be capacitated */
4.103 +#define MINCAP parms[11] /* minimum capacity for capacitated arcs */
4.104 +#define MAXCAP parms[12] /* maximum capacity for capacitated arcs */
4.105 +
4.106 +
4.107 +/*** Private interfaces */
4.108 +
4.109 +#ifdef DEBUG
4.110 +#define PRIVATE
4.111 +#else
4.112 +#define PRIVATE static
4.113 +#endif
4.114 +
4.115 +#ifdef __STDC__
4.116 +PRIVATE void create_supply(NODE, CAPACITY); /* create supply nodes */
4.117 +PRIVATE void create_assignment(long*); /* create assignment problem */
4.118 +PRIVATE void sort_skeleton(int); /* sorts skeleton chains */
4.119 +PRIVATE void pick_head(long*, int, NODE); /* choose destination nodes for rubbish arcs */
4.120 +PRIVATE void error_exit(long); /* print error message and exit */
4.121 +#else
4.122 +PRIVATE void create_supply(); /* create supply nodes */
4.123 +PRIVATE void create_assignment(); /* create assignment problem */
4.124 +PRIVATE void sort_skeleton(); /* sorts skeleton chains */
4.125 +PRIVATE void pick_head(); /* chooses destination nodes for rubbish arcs */
4.126 +PRIVATE void error_exit(); /* print error message and exit */
4.127 +#endif
4.128 +
4.129 +/*** Private variables */
4.130 +
4.131 +static NODE nodes_left;
4.132 +static ARC arc_count;
4.133 +static NODE pred[MAXARCS];
4.134 +static NODE head[MAXARCS];
4.135 +static NODE tail[MAXARCS];
4.136 +
4.137 +
4.138 +/*** Local macros */
4.139 +
4.140 +#define MIN(x, y) ((x) < (y) ? (x) : (y))
4.141 +#define MAX(x, y) ((x) > (y) ? (x) : (y))
4.142 +#define SAVE_ARC(tail, head, cost, capacity) /* records an arc where our caller can get it */ \
4.143 + { \
4.144 + FROM[arc_count] = tail; \
4.145 + TO [arc_count] = head; \
4.146 + C [arc_count] = cost; \
4.147 + U [arc_count] = capacity; \
4.148 + arc_count++; \
4.149 + }
4.150 +
4.151 +
4.152 +/*** Fortran callable interface routine */
4.153 +
4.154 +void netgen_(seed, parms, generated_nodes, generated_arcs)
4.155 +long* seed; /* pointer to random seed */
4.156 +long parms[PROBLEM_PARMS]; /* problem parameters */
4.157 +long* generated_nodes; /* number of generated nodes */
4.158 +long* generated_arcs; /* number of generated arcs */
4.159 +{
4.160 + *generated_nodes = NODES;
4.161 + if ((*generated_arcs = netgen(*seed, parms)) < 0)
4.162 + error_exit(*generated_arcs);
4.163 +}
4.164 +
4.165 +
4.166 +/*** C callable interface routine */
4.167 +
4.168 +ARC netgen(seed, parms)
4.169 +long seed; /* random seed */
4.170 +long parms[]; /* problem parameters */
4.171 +{
4.172 + register NODE i,j,k;
4.173 + NODE source;
4.174 + NODE node;
4.175 + NODE sinks_per_source;
4.176 + NODE* sinks;
4.177 + NODE it;
4.178 + int chain_length;
4.179 + COST cost;
4.180 + CAPACITY cap;
4.181 + INDEX_LIST handle;
4.182 + int supply_per_sink;
4.183 + int partial_supply;
4.184 + int sort_count;
4.185 +
4.186 +
4.187 +/*** Perform sanity checks on the input */
4.188 +
4.189 + if (seed <= 0)
4.190 + return BAD_SEED;
4.191 + if (NODES > MAXNODES || DENSITY > MAXARCS)
4.192 + return TOO_BIG;
4.193 + if ((NODES <= 0) ||
4.194 + (NODES > DENSITY) ||
4.195 + (SOURCES <= 0) ||
4.196 + (SINKS <= 0) ||
4.197 + (SOURCES + SINKS > NODES) ||
4.198 + (MINCOST > MAXCOST) ||
4.199 + (SUPPLY < SOURCES) ||
4.200 + (TSOURCES > SOURCES) ||
4.201 + (TSINKS > SINKS) ||
4.202 + (HICOST < 0 || HICOST > 100) ||
4.203 + (CAPACITATED < 0 || CAPACITATED > 100) ||
4.204 + (MINCAP > MAXCAP))
4.205 + return BAD_PARMS;
4.206 +
4.207 +
4.208 +/*** Do a little bit of setting up. */
4.209 +
4.210 + set_random(seed);
4.211 +
4.212 + arc_count = 0;
4.213 + nodes_left = NODES - SINKS + TSINKS;
4.214 +
4.215 + if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
4.216 + (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
4.217 + SOURCES == SUPPLY) {
4.218 + create_assignment(parms);
4.219 + return arc_count;
4.220 + }
4.221 +
4.222 + (void)memset((void *)B, 0, sizeof(B));/* set supplies and demands to zero */
4.223 +
4.224 + create_supply((NODE)SOURCES, (CAPACITY)SUPPLY);
4.225 +
4.226 +
4.227 +/*** Form most of the network skeleton. First, 60% of the transshipment
4.228 + *** nodes are divided evenly among the various sources; the remainder
4.229 + *** are chained onto the end of the chains belonging to random sources.
4.230 + ***/
4.231 +
4.232 + for (i = 1; i <= SOURCES; i++) /* point SOURCES at themselves */
4.233 + pred[i] = i;
4.234 + handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)(NODES - SINKS));
4.235 + source = 1;
4.236 + for (i = NODES-SOURCES-SINKS; i > (4*(NODES-SOURCES-SINKS)+9)/10; i--) {
4.237 + node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
4.238 + pred[node] = pred[source];
4.239 + pred[source] = node;
4.240 + if (++source > SOURCES)
4.241 + source = 1;
4.242 + }
4.243 + for ( ; i > 0; --i) {
4.244 + node = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
4.245 + source = ng_random(1L, SOURCES);
4.246 + pred[node] = pred[source];
4.247 + pred[source] = node;
4.248 + }
4.249 + free_index_list(handle);
4.250 +
4.251 +
4.252 +/*** For each source chain, hook it to an "appropriate" number of sinks,
4.253 + *** place capacities and costs on the skeleton edges, and then call
4.254 + *** pick_head to add a bunch of rubbish edges at each node on the chain.
4.255 + ***/
4.256 +
4.257 + for (source = 1; source <= SOURCES; source++) {
4.258 + sort_count = 0;
4.259 + node = pred[source];
4.260 + while (node != source) {
4.261 + sort_count++;
4.262 + head[sort_count] = node;
4.263 + node = tail[sort_count] = pred[node];
4.264 + }
4.265 + if ((NODES-SOURCES-SINKS) == 0)
4.266 + sinks_per_source = SINKS/SOURCES + 1;
4.267 + else
4.268 +/* changing to handle overflows with large n; Mar 18 -- jc */
4.269 + sinks_per_source = ((double) 2*sort_count*SINKS) / ((double) NODES-SOURCES-SINKS);
4.270 + sinks_per_source = MAX(2, MIN(sinks_per_source, SINKS));
4.271 + sinks = (NODE*) malloc(sinks_per_source * sizeof(NODE));
4.272 + handle = make_index_list((INDEX)(NODES - SINKS), (INDEX)(NODES - 1));
4.273 + for (i = 0; i < sinks_per_source; i++) {
4.274 + sinks[i] = choose_index(handle, (INDEX)ng_random(1L, (long)index_size(handle)));
4.275 + }
4.276 + if (source == SOURCES && index_size(handle) > 0) {
4.277 + sinks = (NODE*) realloc((void *)sinks, (sinks_per_source + index_size(handle)) * sizeof(NODE));
4.278 + while (index_size(handle) > 0) {
4.279 + j = choose_index(handle, 1);
4.280 + if (B[j] == 0)
4.281 + sinks[sinks_per_source++] = j;
4.282 + }
4.283 + }
4.284 + free_index_list(handle);
4.285 +
4.286 + chain_length = sort_count;
4.287 + supply_per_sink = B[source-1] / sinks_per_source;
4.288 + k = pred[source];
4.289 + for (i = 0; i < sinks_per_source; i++) {
4.290 + sort_count++;
4.291 + partial_supply = ng_random(1L, (long)supply_per_sink);
4.292 + j = ng_random(0L, (long)sinks_per_source - 1);
4.293 + tail[sort_count] = k;
4.294 + head[sort_count] = sinks[i] + 1;
4.295 + B[sinks[i]] -= partial_supply;
4.296 + B[sinks[j]] -= (supply_per_sink - partial_supply);
4.297 + k = source;
4.298 + for (j = ng_random(1L, (long)chain_length); j > 0; j--)
4.299 + k = pred[k];
4.300 + }
4.301 + B[sinks[0]] -= (B[source-1] % sinks_per_source);
4.302 + free((void *)sinks);
4.303 +
4.304 + sort_skeleton(sort_count);
4.305 + tail[sort_count+1] = 0;
4.306 + for (i = 1; i <= sort_count; ) {
4.307 + handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
4.308 + remove_index(handle, (INDEX)tail[i]);
4.309 + it = tail[i];
4.310 + while (it == tail[i]) {
4.311 + remove_index(handle, (INDEX)head[i]);
4.312 + cap = SUPPLY;
4.313 + if (ng_random(1L, 100L) <= CAPACITATED)
4.314 + cap = MAX(B[source-1], MINCAP);
4.315 + cost = MAXCOST;
4.316 + if (ng_random(1L, 100L) > HICOST)
4.317 + cost = ng_random(MINCOST, MAXCOST);
4.318 + SAVE_ARC(it,head[i],cost,cap);
4.319 + i++;
4.320 + }
4.321 + pick_head(parms, handle, it);
4.322 + free_index_list(handle);
4.323 + }
4.324 + }
4.325 +
4.326 +
4.327 +/*** Add more rubbish edges out of the transshipment sinks. */
4.328 +
4.329 + for (i = NODES - SINKS + 1; i <= NODES - SINKS + TSINKS; i++) {
4.330 + handle = make_index_list((INDEX)(SOURCES - TSOURCES + 1), (INDEX)NODES);
4.331 + remove_index(handle, (INDEX)i);
4.332 + pick_head(parms, handle, i);
4.333 + free_index_list(handle);
4.334 + }
4.335 +
4.336 + return arc_count;
4.337 +}
4.338 +
4.339 +
4.340 +PRIVATE void create_supply(sources, supply)
4.341 +NODE sources;
4.342 +CAPACITY supply;
4.343 +{
4.344 + CAPACITY supply_per_source = supply / sources;
4.345 + CAPACITY partial_supply;
4.346 + NODE i;
4.347 +
4.348 + for (i = 0; i < sources; i++) {
4.349 + B[i] += (partial_supply = ng_random(1L, (long)supply_per_source));
4.350 + B[ng_random(0L, (long)(sources - 1))] += supply_per_source - partial_supply;
4.351 + }
4.352 + B[ng_random(0L, (long)(sources - 1))] += supply % sources;
4.353 +}
4.354 +
4.355 +
4.356 +PRIVATE void create_assignment(parms)
4.357 +long parms[];
4.358 +{
4.359 + INDEX_LIST skeleton, handle;
4.360 + INDEX index;
4.361 + NODE source;
4.362 +
4.363 + for (source = 0; source < NODES/2; source++)
4.364 + B[source] = 1;
4.365 + for ( ; source < NODES; source++)
4.366 + B[source] = -1;
4.367 +
4.368 + skeleton = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
4.369 + for (source = 1; source <= NODES/2; source++) {
4.370 + index = choose_index(skeleton, (INDEX)ng_random(1L, (long)index_size(skeleton)));
4.371 + SAVE_ARC(source, index, ng_random(MINCOST, MAXCOST), 1);
4.372 + handle = make_index_list((INDEX)(SOURCES + 1), (INDEX)NODES);
4.373 + remove_index(handle, index);
4.374 + pick_head(parms, handle, source);
4.375 + free_index_list(handle);
4.376 + }
4.377 + free_index_list(skeleton);
4.378 +}
4.379 +
4.380 +
4.381 +PRIVATE void sort_skeleton(sort_count) /* Shell sort */
4.382 +int sort_count;
4.383 +{
4.384 + int m,i,j,k;
4.385 + int temp;
4.386 +
4.387 + m = sort_count;
4.388 + while ((m /= 2) != 0) {
4.389 + k = sort_count - m;
4.390 + for (j = 1; j <= k; j++) {
4.391 + i = j;
4.392 + while (i >= 1 && tail[i] > tail[i+m]) {
4.393 + temp = tail[i];
4.394 + tail[i] = tail[i+m];
4.395 + tail[i+m] = temp;
4.396 + temp = head[i];
4.397 + head[i] = head[i+m];
4.398 + head[i+m] = temp;
4.399 + i -= m;
4.400 + }
4.401 + }
4.402 + }
4.403 +}
4.404 +
4.405 +
4.406 +PRIVATE void pick_head(parms, handle, desired_tail)
4.407 +long parms[];
4.408 +INDEX_LIST handle;
4.409 +NODE desired_tail;
4.410 +{
4.411 + NODE non_sources = NODES - SOURCES + TSOURCES;
4.412 +
4.413 +/* changing Aug 29 -- jc
4.414 + ARC remaining_arcs = DENSITY - arc_count;
4.415 +*/
4.416 + int remaining_arcs = (int) DENSITY - (int) arc_count;
4.417 +
4.418 + INDEX index;
4.419 + int limit;
4.420 + long upper_bound;
4.421 + CAPACITY cap;
4.422 +
4.423 +/* changing Aug 29 -- jc
4.424 +*/
4.425 + nodes_left--;
4.426 + if ((2 * (int) nodes_left) >= (int) remaining_arcs)
4.427 + return;
4.428 +
4.429 + if ((remaining_arcs + non_sources - pseudo_size(handle) - 1) / (nodes_left + 1) >= non_sources - 1) {
4.430 + limit = non_sources;
4.431 + } else {
4.432 + upper_bound = 2 * (remaining_arcs / (nodes_left + 1) - 1);
4.433 + do {
4.434 + limit = ng_random(1L, upper_bound);
4.435 + if (nodes_left == 0)
4.436 + limit = remaining_arcs;
4.437 +/* changing to handle overflows with large n; Mar 18 -- jc */
4.438 + } while ( ((double) nodes_left * (non_sources - 1)) < ((double) remaining_arcs - limit));
4.439 + }
4.440 +
4.441 + for ( ; limit > 0; limit--) {
4.442 + index = choose_index(handle, (INDEX)ng_random(1L, (long)pseudo_size(handle)));
4.443 + cap = SUPPLY;
4.444 + if (ng_random(1L, 100L) <= CAPACITATED)
4.445 + cap = ng_random(MINCAP, MAXCAP);
4.446 +
4.447 +/* adding Aug 29 -- jc */
4.448 +if ((1 <= index) && (index <= NODES)) {
4.449 + SAVE_ARC(desired_tail, index, ng_random(MINCOST, MAXCOST), cap);
4.450 + }
4.451 +
4.452 + }
4.453 +}
4.454 +
4.455 +
4.456 +/*** Print an appropriate error message and then exit with a nonzero code. */
4.457 +
4.458 +PRIVATE void error_exit(rc)
4.459 +long rc;
4.460 +{
4.461 + switch (rc) {
4.462 + case BAD_SEED:
4.463 + fprintf(stderr, "NETGEN requires a positive random seed\n");
4.464 + break;
4.465 + case TOO_BIG:
4.466 + fprintf(stderr, "Problem too large for generator\n");
4.467 + break;
4.468 + case BAD_PARMS:
4.469 + fprintf(stderr, "Inconsistent parameter settings - check the input\n");
4.470 + break;
4.471 + case ALLOCATION_FAILURE:
4.472 + fprintf(stderr, "Memory allocation failure\n");
4.473 + break;
4.474 + default:
4.475 + fprintf(stderr, "Internal error\n");
4.476 + break;
4.477 + }
4.478 + exit(1000 - (int)rc);
4.479 +}
4.480 +
4.481 +#ifdef DIMACS /* generates network on standard output */
4.482 +
4.483 +#define READ(v) /* read one variable using scanf */ \
4.484 + switch( scanf("%ld", &v) ) { \
4.485 + case 1: \
4.486 + break; \
4.487 + default: \
4.488 + exit(0); \
4.489 + }
4.490 +
4.491 +int main()
4.492 +{
4.493 + long seed;
4.494 + long problem;
4.495 + long parms[PROBLEM_PARMS];
4.496 + long arcs;
4.497 + int i;
4.498 +
4.499 +/*** Read problem parameters and generate networks */
4.500 +
4.501 + while (1) {
4.502 + READ(seed);
4.503 + if (seed <= 0) exit(0);
4.504 + READ(problem);
4.505 + if (problem <= 0) exit(0);
4.506 + for (i = 0; i < PROBLEM_PARMS; i++)
4.507 + READ(parms[i]);
4.508 + printf("c NETGEN flow network generator (C version)\n");
4.509 + printf("c Problem %2ld input parameters\n", problem);
4.510 + printf("c ---------------------------\n");
4.511 + printf("c Random seed: %10ld\n", seed);
4.512 + printf("c Number of nodes: %10ld\n", NODES);
4.513 + printf("c Source nodes: %10ld\n", SOURCES);
4.514 + printf("c Sink nodes: %10ld\n", SINKS);
4.515 + printf("c Number of arcs: %10ld\n", DENSITY);
4.516 + printf("c Minimum arc cost: %10ld\n", MINCOST);
4.517 + printf("c Maximum arc cost: %10ld\n", MAXCOST);
4.518 + printf("c Total supply: %10ld\n", SUPPLY);
4.519 + printf("c Transshipment -\n");
4.520 + printf("c Sources: %10ld\n", TSOURCES);
4.521 + printf("c Sinks: %10ld\n", TSINKS);
4.522 + printf("c Skeleton arcs -\n");
4.523 + printf("c With max cost: %10ld%%\n", HICOST);
4.524 + printf("c Capacitated: %10ld%%\n", CAPACITATED);
4.525 + printf("c Minimum arc capacity: %10ld\n", MINCAP);
4.526 + printf("c Maximum arc capacity: %10ld\n", MAXCAP);
4.527 +
4.528 + if ((arcs = netgen(seed, parms)) < 0)
4.529 + error_exit(arcs);
4.530 + if ((SOURCES-TSOURCES)+(SINKS-TSINKS) == NODES &&
4.531 + (SOURCES-TSOURCES) == (SINKS-TSINKS) &&
4.532 + SOURCES == SUPPLY) {
4.533 + printf("c\n");
4.534 + printf("c *** Assignment ***\n");
4.535 + printf("c\n");
4.536 + printf("p asn %ld %ld\n", NODES, arcs);
4.537 + for (i = 0; i < NODES; i++) {
4.538 + if (B[i] > 0)
4.539 + printf("n %ld\n", i + 1);
4.540 + }
4.541 + for (i = 0; i < arcs; i++) {
4.542 + printf("a %ld %ld %ld\n", FROM[i], TO[i], C[i]);
4.543 + }
4.544 + } else
4.545 + if (MINCOST == 1 && MAXCOST == 1) {
4.546 + printf("c\n");
4.547 + printf("c *** Maximum flow ***\n");
4.548 + printf("c\n");
4.549 + printf("p max %ld %ld\n", NODES, arcs);
4.550 + for (i = 0; i < NODES; i++) {
4.551 + if (B[i] > 0)
4.552 + printf("n %ld s\n", i + 1);
4.553 + else
4.554 + if (B[i] < 0)
4.555 + printf("n %ld t\n", i + 1);
4.556 + }
4.557 + for (i = 0; i < arcs; i++) {
4.558 + printf("a %ld %ld %ld\n", FROM[i], TO[i], U[i]);
4.559 + }
4.560 + } else {
4.561 + printf("c\n");
4.562 + printf("c *** Minimum cost flow ***\n");
4.563 + printf("c\n");
4.564 + printf("p min %ld %ld\n", NODES, arcs);
4.565 + for (i = 0; i < NODES; i++) {
4.566 + if (B[i] != 0)
4.567 + printf("n %ld %ld\n", i + 1, B[i]);
4.568 + }
4.569 + for (i = 0; i < arcs; i++) {
4.570 + printf("a %ld %ld %ld %ld %ld\n", FROM[i], TO[i], 0, U[i], C[i]);
4.571 + }
4.572 + }
4.573 + }
4.574 + return 0;
4.575 +}
4.576 +
4.577 +#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/generators/netgen/netgen.h Fri Nov 26 19:23:47 2010 +0100
5.3 @@ -0,0 +1,95 @@
5.4 +/*** netgen.h
5.5 + *** Prototype code for inclusion into network generation routines
5.6 + ***/
5.7 +
5.8 +/*** Constant definitions */
5.9 +
5.10 +#ifndef NULL
5.11 +#define NULL 0
5.12 +#endif
5.13 +
5.14 +#define BAD_SEED -1 /* error indicators */
5.15 +#define TOO_BIG -2
5.16 +#define BAD_PARMS -3
5.17 +#define ALLOCATION_FAILURE -4
5.18 +
5.19 +
5.20 +/*** Type definitions */
5.21 +
5.22 +typedef unsigned long NODE; /* node number */
5.23 +typedef unsigned long ARC; /* arc number */
5.24 +typedef long CAPACITY; /* arc capacity */
5.25 +typedef long COST; /* arc cost */
5.26 +typedef unsigned long INDEX; /* index element */
5.27 +typedef int INDEX_LIST; /* index list handle */
5.28 +
5.29 +
5.30 +/*** Function prototypes */
5.31 +
5.32 +#ifdef __STDC__
5.33 +
5.34 +#include <stdlib.h>
5.35 +#include <string.h>
5.36 +
5.37 +void netgen_(long*, long[], long*, long*); /* Fortran external interface */
5.38 +ARC netgen(long, long*); /* C external interface */
5.39 +
5.40 +INDEX_LIST make_index_list(INDEX, INDEX); /* allocates a new index list */
5.41 +void free_index_list(INDEX_LIST); /* frees an existing list */
5.42 +INDEX choose_index(INDEX_LIST, INDEX); /* chooses index at specified position */
5.43 +void remove_index(INDEX_LIST, INDEX); /* removes specified index from list */
5.44 +INDEX index_size(INDEX_LIST); /* number of indices remaining */
5.45 +INDEX pseudo_size(INDEX_LIST); /* "modified" index size */
5.46 +
5.47 +void set_random(long); /* initialize random seed */
5.48 +long ng_random(long, long); /* generate random integer in interval */
5.49 +
5.50 +#else
5.51 +
5.52 +void *malloc(); /* some standard header should define this */
5.53 +void *realloc(); /* ditto */
5.54 +void free(); /* ditto */
5.55 +void *memset(); /* ditto */
5.56 +void exit(); /* ditto */
5.57 +
5.58 +void netgen_(); /* Fortran external interface */
5.59 +ARC netgen(); /* C external interface */
5.60 +
5.61 +INDEX_LIST make_index_list(); /* allocates a new index list */
5.62 +void free_index_list(); /* frees an existing list */
5.63 +INDEX choose_index(); /* chooses index at specified position */
5.64 +void remove_index(); /* removes specified index from list */
5.65 +INDEX index_size(); /* number of indices remaining */
5.66 +INDEX pseudo_size(); /* "modified" index size */
5.67 +
5.68 +void set_random(); /* initialize random seed */
5.69 +long ng_random(); /* generate random integer in interval */
5.70 +
5.71 +#endif
5.72 +
5.73 +/*** To maintain compatibility with the old Fortran network generator,
5.74 + *** the following are defined. This allows linking the generator code
5.75 + *** with the solver, with the generated network passed to the solver
5.76 + *** through arrays in memory.
5.77 + ***/
5.78 +
5.79 +#define MAXNODES 10000000 /* maximum problem sizes */
5.80 +#define MAXARCS 40000000
5.81 +
5.82 +#define FROM arrays_ /* aliases for network storage */
5.83 +#define TO arraye_
5.84 +#define U arrayu_
5.85 +#define C arrayc_
5.86 +#define B arrayb_
5.87 +
5.88 +#ifdef ALLOCATE_NETWORK /* storage definitions */
5.89 +#define EXTERN
5.90 +#else
5.91 +#define EXTERN extern
5.92 +#endif
5.93 +
5.94 +EXTERN NODE FROM[MAXARCS]; /* origin of each arc */
5.95 +EXTERN NODE TO [MAXARCS]; /* destination */
5.96 +EXTERN CAPACITY U [MAXARCS]; /* capacity */
5.97 +EXTERN COST C [MAXARCS]; /* cost */
5.98 +EXTERN CAPACITY B [MAXNODES]; /* supply (demand) at each node */
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/generators/netgen/random.c Fri Nov 26 19:23:47 2010 +0100
6.3 @@ -0,0 +1,47 @@
6.4 +/*** This is a portable random number generator whose origins are
6.5 + *** unknown. As far as can be told, this is public domain software.
6.6 +
6.7 +
6.8 +/*** portable random number generator */
6.9 +
6.10 +/*** Note that every variable used here must have at least 31 bits
6.11 + *** of precision, exclusive of sign. Long integers should be enough.
6.12 + *** The generator is the congruential: i = 7**5 * i mod (2^31-1).
6.13 + ***/
6.14 +
6.15 +#define MULTIPLIER 16807
6.16 +#define MODULUS 2147483647
6.17 +
6.18 +static long saved_seed;
6.19 +
6.20 +
6.21 +/*** set_random - initialize constants and seed */
6.22 +
6.23 +void set_random(seed)
6.24 +long seed;
6.25 +{
6.26 + saved_seed = seed;
6.27 +}
6.28 +
6.29 +
6.30 +/*** ng_random - generate a random integer in the interval [a,b] (b >= a >= 0) */
6.31 +
6.32 +long ng_random(a, b)
6.33 +long a, b;
6.34 +{
6.35 + register long hi, lo;
6.36 +
6.37 + hi = MULTIPLIER * (saved_seed >> 16);
6.38 + lo = MULTIPLIER * (saved_seed & 0xffff);
6.39 + hi += (lo>>16);
6.40 + lo &= 0xffff;
6.41 + lo += (hi>>15);
6.42 + hi &= 0x7fff;
6.43 + lo -= MODULUS;
6.44 + if ((saved_seed = (hi<<16) + lo) < 0)
6.45 + saved_seed += MODULUS;
6.46 +
6.47 + if (b <= a)
6.48 + return b;
6.49 + return a + saved_seed % (b - a + 1);
6.50 +}
7.1 --- a/main.cc Fri Nov 26 17:59:31 2010 +0100
7.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
7.3 @@ -1,26 +0,0 @@
7.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 - *
7.6 - * This file is a part of LEMON, a generic C++ optimization library.
7.7 - *
7.8 - * Copyright (C) 2003-2009
7.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 - *
7.12 - * Permission to use, modify and distribute this software is granted
7.13 - * provided that this copyright notice appears in all copies. For
7.14 - * precise terms see the accompanying LICENSE file.
7.15 - *
7.16 - * This software is provided "AS IS" with no warranty of any kind,
7.17 - * express or implied, and with no claim as to its suitability for any
7.18 - * purpose.
7.19 - *
7.20 - */
7.21 -
7.22 -#include<lemon/list_graph.h>
7.23 -
7.24 -///The main entry point
7.25 -int main()
7.26 -{
7.27 - lemon::ListGraph g;
7.28 - g.addNode();
7.29 -}