lemon-project-template-glpk

annotate deps/glpk/src/glpnet04.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpnet04.c (grid-like network problem generator) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * This code is a modified version of the program GRIDGEN, a grid-like
alpar@9 7 * network problem generator developed by Yusin Lee and Jim Orlin.
alpar@9 8 * The original code is publically available on the DIMACS ftp site at:
alpar@9 9 * <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>.
alpar@9 10 *
alpar@9 11 * All changes concern only the program interface, so this modified
alpar@9 12 * version produces exactly the same instances as the original version.
alpar@9 13 *
alpar@9 14 * Changes were made by Andrew Makhorin <mao@gnu.org>.
alpar@9 15 *
alpar@9 16 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 17 * under the terms of the GNU General Public License as published by
alpar@9 18 * the Free Software Foundation, either version 3 of the License, or
alpar@9 19 * (at your option) any later version.
alpar@9 20 *
alpar@9 21 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 22 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 23 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 24 * License for more details.
alpar@9 25 *
alpar@9 26 * You should have received a copy of the GNU General Public License
alpar@9 27 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 28 ***********************************************************************/
alpar@9 29
alpar@9 30 #include "glpapi.h"
alpar@9 31
alpar@9 32 /***********************************************************************
alpar@9 33 * NAME
alpar@9 34 *
alpar@9 35 * glp_gridgen - grid-like network problem generator
alpar@9 36 *
alpar@9 37 * SYNOPSIS
alpar@9 38 *
alpar@9 39 * int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
alpar@9 40 * const int parm[1+14]);
alpar@9 41 *
alpar@9 42 * DESCRIPTION
alpar@9 43 *
alpar@9 44 * The routine glp_gridgen is a grid-like network problem generator
alpar@9 45 * developed by Yusin Lee and Jim Orlin.
alpar@9 46 *
alpar@9 47 * The parameter G specifies the graph object, to which the generated
alpar@9 48 * problem data have to be stored. Note that on entry the graph object
alpar@9 49 * is erased with the routine glp_erase_graph.
alpar@9 50 *
alpar@9 51 * The parameter v_rhs specifies an offset of the field of type double
alpar@9 52 * in the vertex data block, to which the routine stores the supply or
alpar@9 53 * demand value. If v_rhs < 0, the value is not stored.
alpar@9 54 *
alpar@9 55 * The parameter a_cap specifies an offset of the field of type double
alpar@9 56 * in the arc data block, to which the routine stores the arc capacity.
alpar@9 57 * If a_cap < 0, the capacity is not stored.
alpar@9 58 *
alpar@9 59 * The parameter a_cost specifies an offset of the field of type double
alpar@9 60 * in the arc data block, to which the routine stores the per-unit cost
alpar@9 61 * if the arc flow. If a_cost < 0, the cost is not stored.
alpar@9 62 *
alpar@9 63 * The array parm contains description of the network to be generated:
alpar@9 64 *
alpar@9 65 * parm[0] not used
alpar@9 66 * parm[1] two-ways arcs indicator:
alpar@9 67 * 1 - if links in both direction should be generated
alpar@9 68 * 0 - otherwise
alpar@9 69 * parm[2] random number seed (a positive integer)
alpar@9 70 * parm[3] number of nodes (the number of nodes generated might be
alpar@9 71 * slightly different to make the network a grid)
alpar@9 72 * parm[4] grid width
alpar@9 73 * parm[5] number of sources
alpar@9 74 * parm[6] number of sinks
alpar@9 75 * parm[7] average degree
alpar@9 76 * parm[8] total flow
alpar@9 77 * parm[9] distribution of arc costs:
alpar@9 78 * 1 - uniform
alpar@9 79 * 2 - exponential
alpar@9 80 * parm[10] lower bound for arc cost (uniform)
alpar@9 81 * 100 * lambda (exponential)
alpar@9 82 * parm[11] upper bound for arc cost (uniform)
alpar@9 83 * not used (exponential)
alpar@9 84 * parm[12] distribution of arc capacities:
alpar@9 85 * 1 - uniform
alpar@9 86 * 2 - exponential
alpar@9 87 * parm[13] lower bound for arc capacity (uniform)
alpar@9 88 * 100 * lambda (exponential)
alpar@9 89 * parm[14] upper bound for arc capacity (uniform)
alpar@9 90 * not used (exponential)
alpar@9 91 *
alpar@9 92 * RETURNS
alpar@9 93 *
alpar@9 94 * If the instance was successfully generated, the routine glp_gridgen
alpar@9 95 * returns zero; otherwise, if specified parameters are inconsistent,
alpar@9 96 * the routine returns a non-zero error code.
alpar@9 97 *
alpar@9 98 * COMMENTS
alpar@9 99 *
alpar@9 100 * This network generator generates a grid-like network plus a super
alpar@9 101 * node. In additional to the arcs connecting the nodes in the grid,
alpar@9 102 * there is an arc from each supply node to the super node and from the
alpar@9 103 * super node to each demand node to guarantee feasiblity. These arcs
alpar@9 104 * have very high costs and very big capacities.
alpar@9 105 *
alpar@9 106 * The idea of this network generator is as follows: First, a grid of
alpar@9 107 * n1 * n2 is generated. For example, 5 * 3. The nodes are numbered as
alpar@9 108 * 1 to 15, and the supernode is numbered as n1*n2+1. Then arcs between
alpar@9 109 * adjacent nodes are generated. For these arcs, the user is allowed to
alpar@9 110 * specify either to generate two-way arcs or one-way arcs. If two-way
alpar@9 111 * arcs are to be generated, two arcs, one in each direction, will be
alpar@9 112 * generated between each adjacent node pairs. Otherwise, only one arc
alpar@9 113 * will be generated. If this is the case, the arcs will be generated
alpar@9 114 * in alterntive directions as shown below.
alpar@9 115 *
alpar@9 116 * 1 ---> 2 ---> 3 ---> 4 ---> 5
alpar@9 117 * | ^ | ^ |
alpar@9 118 * | | | | |
alpar@9 119 * V | V | V
alpar@9 120 * 6 <--- 7 <--- 8 <--- 9 <--- 10
alpar@9 121 * | ^ | ^ |
alpar@9 122 * | | | | |
alpar@9 123 * V | V | V
alpar@9 124 * 11 --->12 --->13 --->14 ---> 15
alpar@9 125 *
alpar@9 126 * Then the arcs between the super node and the source/sink nodes are
alpar@9 127 * added as mentioned before. If the number of arcs still doesn't reach
alpar@9 128 * the requirement, additional arcs will be added by uniformly picking
alpar@9 129 * random node pairs. There is no checking to prevent multiple arcs
alpar@9 130 * between any pair of nodes. However, there will be no self-arcs (arcs
alpar@9 131 * that poins back to its tail node) in the network.
alpar@9 132 *
alpar@9 133 * The source and sink nodes are selected uniformly in the network, and
alpar@9 134 * the imbalances of each source/sink node are also assigned by uniform
alpar@9 135 * distribution. */
alpar@9 136
alpar@9 137 struct stat_para
alpar@9 138 { /* structure for statistical distributions */
alpar@9 139 int distribution;
alpar@9 140 /* the distribution: */
alpar@9 141 #define UNIFORM 1 /* uniform distribution */
alpar@9 142 #define EXPONENTIAL 2 /* exponential distribution */
alpar@9 143 double parameter[5];
alpar@9 144 /* the parameters of the distribution */
alpar@9 145 };
alpar@9 146
alpar@9 147 struct arcs
alpar@9 148 { int from;
alpar@9 149 /* the FROM node of that arc */
alpar@9 150 int to;
alpar@9 151 /* the TO node of that arc */
alpar@9 152 int cost;
alpar@9 153 /* original cost of that arc */
alpar@9 154 int u;
alpar@9 155 /* capacity of the arc */
alpar@9 156 };
alpar@9 157
alpar@9 158 struct imbalance
alpar@9 159 { int node;
alpar@9 160 /* Node ID */
alpar@9 161 int supply;
alpar@9 162 /* Supply of that node */
alpar@9 163 };
alpar@9 164
alpar@9 165 struct csa
alpar@9 166 { /* common storage area */
alpar@9 167 glp_graph *G;
alpar@9 168 int v_rhs, a_cap, a_cost;
alpar@9 169 int seed;
alpar@9 170 /* random number seed */
alpar@9 171 int seed_original;
alpar@9 172 /* the original seed from input */
alpar@9 173 int two_way;
alpar@9 174 /* 0: generate arcs in both direction for the basic grid, except
alpar@9 175 for the arcs to/from the super node. 1: o/w */
alpar@9 176 int n_node;
alpar@9 177 /* total number of nodes in the network, numbered 1 to n_node,
alpar@9 178 including the super node, which is the last one */
alpar@9 179 int n_arc;
alpar@9 180 /* total number of arcs in the network, counting EVERY arc. */
alpar@9 181 int n_grid_arc;
alpar@9 182 /* number of arcs in the basic grid, including the arcs to/from
alpar@9 183 the super node */
alpar@9 184 int n_source, n_sink;
alpar@9 185 /* number of source and sink nodes */
alpar@9 186 int avg_degree;
alpar@9 187 /* average degree, arcs to and from the super node are counted */
alpar@9 188 int t_supply;
alpar@9 189 /* total supply in the network */
alpar@9 190 int n1, n2;
alpar@9 191 /* the two edges of the network grid. n1 >= n2 */
alpar@9 192 struct imbalance *source_list, *sink_list;
alpar@9 193 /* head of the array of source/sink nodes */
alpar@9 194 struct stat_para arc_costs;
alpar@9 195 /* the distribution of arc costs */
alpar@9 196 struct stat_para capacities;
alpar@9 197 /* distribution of the capacities of the arcs */
alpar@9 198 struct arcs *arc_list;
alpar@9 199 /* head of the arc list array. Arcs in this array are in the
alpar@9 200 order of grid_arcs, arcs to/from super node, and other arcs */
alpar@9 201 };
alpar@9 202
alpar@9 203 #define G (csa->G)
alpar@9 204 #define v_rhs (csa->v_rhs)
alpar@9 205 #define a_cap (csa->a_cap)
alpar@9 206 #define a_cost (csa->a_cost)
alpar@9 207 #define seed (csa->seed)
alpar@9 208 #define seed_original (csa->seed_original)
alpar@9 209 #define two_way (csa->two_way)
alpar@9 210 #define n_node (csa->n_node)
alpar@9 211 #define n_arc (csa->n_arc)
alpar@9 212 #define n_grid_arc (csa->n_grid_arc)
alpar@9 213 #define n_source (csa->n_source)
alpar@9 214 #define n_sink (csa->n_sink)
alpar@9 215 #define avg_degree (csa->avg_degree)
alpar@9 216 #define t_supply (csa->t_supply)
alpar@9 217 #define n1 (csa->n1)
alpar@9 218 #define n2 (csa->n2)
alpar@9 219 #define source_list (csa->source_list)
alpar@9 220 #define sink_list (csa->sink_list)
alpar@9 221 #define arc_costs (csa->arc_costs)
alpar@9 222 #define capacities (csa->capacities)
alpar@9 223 #define arc_list (csa->arc_list)
alpar@9 224
alpar@9 225 static void assign_capacities(struct csa *csa);
alpar@9 226 static void assign_costs(struct csa *csa);
alpar@9 227 static void assign_imbalance(struct csa *csa);
alpar@9 228 static int exponential(struct csa *csa, double lambda[1]);
alpar@9 229 static struct arcs *gen_additional_arcs(struct csa *csa, struct arcs
alpar@9 230 *arc_ptr);
alpar@9 231 static struct arcs *gen_basic_grid(struct csa *csa, struct arcs
alpar@9 232 *arc_ptr);
alpar@9 233 static void gen_more_arcs(struct csa *csa, struct arcs *arc_ptr);
alpar@9 234 static void generate(struct csa *csa);
alpar@9 235 static void output(struct csa *csa);
alpar@9 236 static double randy(struct csa *csa);
alpar@9 237 static void select_source_sinks(struct csa *csa);
alpar@9 238 static int uniform(struct csa *csa, double a[2]);
alpar@9 239
alpar@9 240 int glp_gridgen(glp_graph *G_, int _v_rhs, int _a_cap, int _a_cost,
alpar@9 241 const int parm[1+14])
alpar@9 242 { struct csa _csa, *csa = &_csa;
alpar@9 243 int n, ret;
alpar@9 244 G = G_;
alpar@9 245 v_rhs = _v_rhs;
alpar@9 246 a_cap = _a_cap;
alpar@9 247 a_cost = _a_cost;
alpar@9 248 if (G != NULL)
alpar@9 249 { if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
alpar@9 250 xerror("glp_gridgen: v_rhs = %d; invalid offset\n", v_rhs);
alpar@9 251 if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
alpar@9 252 xerror("glp_gridgen: a_cap = %d; invalid offset\n", a_cap);
alpar@9 253 if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
alpar@9 254 xerror("glp_gridgen: a_cost = %d; invalid offset\n", a_cost)
alpar@9 255 ;
alpar@9 256 }
alpar@9 257 /* Check the parameters for consistency. */
alpar@9 258 if (!(parm[1] == 0 || parm[1] == 1))
alpar@9 259 { ret = 1;
alpar@9 260 goto done;
alpar@9 261 }
alpar@9 262 if (parm[2] < 1)
alpar@9 263 { ret = 2;
alpar@9 264 goto done;
alpar@9 265 }
alpar@9 266 if (!(10 <= parm[3] && parm[3] <= 40000))
alpar@9 267 { ret = 3;
alpar@9 268 goto done;
alpar@9 269 }
alpar@9 270 if (!(1 <= parm[4] && parm[4] <= 40000))
alpar@9 271 { ret = 4;
alpar@9 272 goto done;
alpar@9 273 }
alpar@9 274 if (!(parm[5] >= 0 && parm[6] >= 0 && parm[5] + parm[6] <=
alpar@9 275 parm[3]))
alpar@9 276 { ret = 5;
alpar@9 277 goto done;
alpar@9 278 }
alpar@9 279 if (!(1 <= parm[7] && parm[7] <= parm[3]))
alpar@9 280 { ret = 6;
alpar@9 281 goto done;
alpar@9 282 }
alpar@9 283 if (parm[8] < 0)
alpar@9 284 { ret = 7;
alpar@9 285 goto done;
alpar@9 286 }
alpar@9 287 if (!(parm[9] == 1 || parm[9] == 2))
alpar@9 288 { ret = 8;
alpar@9 289 goto done;
alpar@9 290 }
alpar@9 291 if (parm[9] == 1 && parm[10] > parm[11] ||
alpar@9 292 parm[9] == 2 && parm[10] < 1)
alpar@9 293 { ret = 9;
alpar@9 294 goto done;
alpar@9 295 }
alpar@9 296 if (!(parm[12] == 1 || parm[12] == 2))
alpar@9 297 { ret = 10;
alpar@9 298 goto done;
alpar@9 299 }
alpar@9 300 if (parm[12] == 1 && !(0 <= parm[13] && parm[13] <= parm[14]) ||
alpar@9 301 parm[12] == 2 && parm[13] < 1)
alpar@9 302 { ret = 11;
alpar@9 303 goto done;
alpar@9 304 }
alpar@9 305 /* Initialize the graph object. */
alpar@9 306 if (G != NULL)
alpar@9 307 { glp_erase_graph(G, G->v_size, G->a_size);
alpar@9 308 glp_set_graph_name(G, "GRIDGEN");
alpar@9 309 }
alpar@9 310 /* Copy the generator parameters. */
alpar@9 311 two_way = parm[1];
alpar@9 312 seed_original = seed = parm[2];
alpar@9 313 n_node = parm[3];
alpar@9 314 n = parm[4];
alpar@9 315 n_source = parm[5];
alpar@9 316 n_sink = parm[6];
alpar@9 317 avg_degree = parm[7];
alpar@9 318 t_supply = parm[8];
alpar@9 319 arc_costs.distribution = parm[9];
alpar@9 320 if (parm[9] == 1)
alpar@9 321 { arc_costs.parameter[0] = parm[10];
alpar@9 322 arc_costs.parameter[1] = parm[11];
alpar@9 323 }
alpar@9 324 else
alpar@9 325 { arc_costs.parameter[0] = (double)parm[10] / 100.0;
alpar@9 326 arc_costs.parameter[1] = 0.0;
alpar@9 327 }
alpar@9 328 capacities.distribution = parm[12];
alpar@9 329 if (parm[12] == 1)
alpar@9 330 { capacities.parameter[0] = parm[13];
alpar@9 331 capacities.parameter[1] = parm[14];
alpar@9 332 }
alpar@9 333 else
alpar@9 334 { capacities.parameter[0] = (double)parm[13] / 100.0;
alpar@9 335 capacities.parameter[1] = 0.0;
alpar@9 336 }
alpar@9 337 /* Calculate the edge lengths of the grid according to the
alpar@9 338 input. */
alpar@9 339 if (n * n >= n_node)
alpar@9 340 { n1 = n;
alpar@9 341 n2 = (int)((double)n_node / (double)n + 0.5);
alpar@9 342 }
alpar@9 343 else
alpar@9 344 { n2 = n;
alpar@9 345 n1 = (int)((double)n_node / (double)n + 0.5);
alpar@9 346 }
alpar@9 347 /* Recalculate the total number of nodes and plus 1 for the super
alpar@9 348 node. */
alpar@9 349 n_node = n1 * n2 + 1;
alpar@9 350 n_arc = n_node * avg_degree;
alpar@9 351 n_grid_arc = (two_way + 1) * ((n1 - 1) * n2 + (n2 - 1) * n1) +
alpar@9 352 n_source + n_sink;
alpar@9 353 if (n_grid_arc > n_arc) n_arc = n_grid_arc;
alpar@9 354 arc_list = xcalloc(n_arc, sizeof(struct arcs));
alpar@9 355 source_list = xcalloc(n_source, sizeof(struct imbalance));
alpar@9 356 sink_list = xcalloc(n_sink, sizeof(struct imbalance));
alpar@9 357 /* Generate a random network. */
alpar@9 358 generate(csa);
alpar@9 359 /* Output the network. */
alpar@9 360 output(csa);
alpar@9 361 /* Free all allocated memory. */
alpar@9 362 xfree(arc_list);
alpar@9 363 xfree(source_list);
alpar@9 364 xfree(sink_list);
alpar@9 365 /* The instance has been successfully generated. */
alpar@9 366 ret = 0;
alpar@9 367 done: return ret;
alpar@9 368 }
alpar@9 369
alpar@9 370 #undef random
alpar@9 371
alpar@9 372 static void assign_capacities(struct csa *csa)
alpar@9 373 { /* Assign a capacity to each arc. */
alpar@9 374 struct arcs *arc_ptr = arc_list;
alpar@9 375 int (*random)(struct csa *csa, double *);
alpar@9 376 int i;
alpar@9 377 /* Determine the random number generator to use. */
alpar@9 378 switch (arc_costs.distribution)
alpar@9 379 { case UNIFORM:
alpar@9 380 random = uniform;
alpar@9 381 break;
alpar@9 382 case EXPONENTIAL:
alpar@9 383 random = exponential;
alpar@9 384 break;
alpar@9 385 default:
alpar@9 386 xassert(csa != csa);
alpar@9 387 }
alpar@9 388 /* Assign capacities to grid arcs. */
alpar@9 389 for (i = n_source + n_sink; i < n_grid_arc; i++, arc_ptr++)
alpar@9 390 arc_ptr->u = random(csa, capacities.parameter);
alpar@9 391 i = i - n_source - n_sink;
alpar@9 392 /* Assign capacities to arcs to/from supernode. */
alpar@9 393 for (; i < n_grid_arc; i++, arc_ptr++)
alpar@9 394 arc_ptr->u = t_supply;
alpar@9 395 /* Assign capacities to all other arcs. */
alpar@9 396 for (; i < n_arc; i++, arc_ptr++)
alpar@9 397 arc_ptr->u = random(csa, capacities.parameter);
alpar@9 398 return;
alpar@9 399 }
alpar@9 400
alpar@9 401 static void assign_costs(struct csa *csa)
alpar@9 402 { /* Assign a cost to each arc. */
alpar@9 403 struct arcs *arc_ptr = arc_list;
alpar@9 404 int (*random)(struct csa *csa, double *);
alpar@9 405 int i;
alpar@9 406 /* A high cost assigned to arcs to/from the supernode. */
alpar@9 407 int high_cost;
alpar@9 408 /* The maximum cost assigned to arcs in the base grid. */
alpar@9 409 int max_cost = 0;
alpar@9 410 /* Determine the random number generator to use. */
alpar@9 411 switch (arc_costs.distribution)
alpar@9 412 { case UNIFORM:
alpar@9 413 random = uniform;
alpar@9 414 break;
alpar@9 415 case EXPONENTIAL:
alpar@9 416 random = exponential;
alpar@9 417 break;
alpar@9 418 default:
alpar@9 419 xassert(csa != csa);
alpar@9 420 }
alpar@9 421 /* Assign costs to arcs in the base grid. */
alpar@9 422 for (i = n_source + n_sink; i < n_grid_arc; i++, arc_ptr++)
alpar@9 423 { arc_ptr->cost = random(csa, arc_costs.parameter);
alpar@9 424 if (max_cost < arc_ptr->cost) max_cost = arc_ptr->cost;
alpar@9 425 }
alpar@9 426 i = i - n_source - n_sink;
alpar@9 427 /* Assign costs to arcs to/from the super node. */
alpar@9 428 high_cost = max_cost * 2;
alpar@9 429 for (; i < n_grid_arc; i++, arc_ptr++)
alpar@9 430 arc_ptr->cost = high_cost;
alpar@9 431 /* Assign costs to all other arcs. */
alpar@9 432 for (; i < n_arc; i++, arc_ptr++)
alpar@9 433 arc_ptr->cost = random(csa, arc_costs.parameter);
alpar@9 434 return;
alpar@9 435 }
alpar@9 436
alpar@9 437 static void assign_imbalance(struct csa *csa)
alpar@9 438 { /* Assign an imbalance to each node. */
alpar@9 439 int total, i;
alpar@9 440 double avg;
alpar@9 441 struct imbalance *ptr;
alpar@9 442 /* assign the supply nodes */
alpar@9 443 avg = 2.0 * t_supply / n_source;
alpar@9 444 do
alpar@9 445 { for (i = 1, total = t_supply, ptr = source_list + 1;
alpar@9 446 i < n_source; i++, ptr++)
alpar@9 447 { ptr->supply = (int)(randy(csa) * avg + 0.5);
alpar@9 448 total -= ptr->supply;
alpar@9 449 }
alpar@9 450 source_list->supply = total;
alpar@9 451 }
alpar@9 452 /* redo all if the assignment "overshooted" */
alpar@9 453 while (total <= 0);
alpar@9 454 /* assign the demand nodes */
alpar@9 455 avg = -2.0 * t_supply / n_sink;
alpar@9 456 do
alpar@9 457 { for (i = 1, total = t_supply, ptr = sink_list + 1;
alpar@9 458 i < n_sink; i++, ptr++)
alpar@9 459 { ptr->supply = (int)(randy(csa) * avg - 0.5);
alpar@9 460 total += ptr->supply;
alpar@9 461 }
alpar@9 462 sink_list->supply = - total;
alpar@9 463 }
alpar@9 464 while (total <= 0);
alpar@9 465 return;
alpar@9 466 }
alpar@9 467
alpar@9 468 static int exponential(struct csa *csa, double lambda[1])
alpar@9 469 { /* Returns an "exponentially distributed" integer with parameter
alpar@9 470 lambda. */
alpar@9 471 return ((int)(- lambda[0] * log((double)randy(csa)) + 0.5));
alpar@9 472 }
alpar@9 473
alpar@9 474 static struct arcs *gen_additional_arcs(struct csa *csa, struct arcs
alpar@9 475 *arc_ptr)
alpar@9 476 { /* Generate an arc from each source to the supernode and from
alpar@9 477 supernode to each sink. */
alpar@9 478 int i;
alpar@9 479 for (i = 0; i < n_source; i++, arc_ptr++)
alpar@9 480 { arc_ptr->from = source_list[i].node;
alpar@9 481 arc_ptr->to = n_node;
alpar@9 482 }
alpar@9 483 for (i = 0; i < n_sink; i++, arc_ptr++)
alpar@9 484 { arc_ptr->to = sink_list[i].node;
alpar@9 485 arc_ptr->from = n_node;
alpar@9 486 }
alpar@9 487 return arc_ptr;
alpar@9 488 }
alpar@9 489
alpar@9 490 static struct arcs *gen_basic_grid(struct csa *csa, struct arcs
alpar@9 491 *arc_ptr)
alpar@9 492 { /* Generate the basic grid. */
alpar@9 493 int direction = 1, i, j, k;
alpar@9 494 if (two_way)
alpar@9 495 { /* Generate an arc in each direction. */
alpar@9 496 for (i = 1; i < n_node; i += n1)
alpar@9 497 { for (j = i, k = j + n1 - 1; j < k; j++)
alpar@9 498 { arc_ptr->from = j;
alpar@9 499 arc_ptr->to = j + 1;
alpar@9 500 arc_ptr++;
alpar@9 501 arc_ptr->from = j + 1;
alpar@9 502 arc_ptr->to = j;
alpar@9 503 arc_ptr++;
alpar@9 504 }
alpar@9 505 }
alpar@9 506 for (i = 1; i <= n1; i++)
alpar@9 507 { for (j = i + n1; j < n_node; j += n1)
alpar@9 508 { arc_ptr->from = j;
alpar@9 509 arc_ptr->to = j - n1;
alpar@9 510 arc_ptr++;
alpar@9 511 arc_ptr->from = j - n1;
alpar@9 512 arc_ptr->to = j;
alpar@9 513 arc_ptr++;
alpar@9 514 }
alpar@9 515 }
alpar@9 516 }
alpar@9 517 else
alpar@9 518 { /* Generate one arc in each direction. */
alpar@9 519 for (i = 1; i < n_node; i += n1)
alpar@9 520 { if (direction == 1)
alpar@9 521 j = i;
alpar@9 522 else
alpar@9 523 j = i + 1;
alpar@9 524 for (k = j + n1 - 1; j < k; j++)
alpar@9 525 { arc_ptr->from = j;
alpar@9 526 arc_ptr->to = j + direction;
alpar@9 527 arc_ptr++;
alpar@9 528 }
alpar@9 529 direction = - direction;
alpar@9 530 }
alpar@9 531 for (i = 1; i <= n1; i++)
alpar@9 532 { j = i + n1;
alpar@9 533 if (direction == 1)
alpar@9 534 { for (; j < n_node; j += n1)
alpar@9 535 { arc_ptr->from = j - n1;
alpar@9 536 arc_ptr->to = j;
alpar@9 537 arc_ptr++;
alpar@9 538 }
alpar@9 539 }
alpar@9 540 else
alpar@9 541 { for (; j < n_node; j += n1)
alpar@9 542 { arc_ptr->from = j - n1;
alpar@9 543 arc_ptr->to = j;
alpar@9 544 arc_ptr++;
alpar@9 545 }
alpar@9 546 }
alpar@9 547 direction = - direction;
alpar@9 548 }
alpar@9 549 }
alpar@9 550 return arc_ptr;
alpar@9 551 }
alpar@9 552
alpar@9 553 static void gen_more_arcs(struct csa *csa, struct arcs *arc_ptr)
alpar@9 554 { /* Generate random arcs to meet the specified density. */
alpar@9 555 int i;
alpar@9 556 double ab[2];
alpar@9 557 ab[0] = 0.9;
alpar@9 558 ab[1] = n_node - 0.99; /* upper limit is n_node-1 because the
alpar@9 559 supernode cannot be selected */
alpar@9 560 for (i = n_grid_arc; i < n_arc; i++, arc_ptr++)
alpar@9 561 { arc_ptr->from = uniform(csa, ab);
alpar@9 562 arc_ptr->to = uniform(csa, ab);
alpar@9 563 if (arc_ptr->from == arc_ptr->to)
alpar@9 564 { arc_ptr--;
alpar@9 565 i--;
alpar@9 566 }
alpar@9 567 }
alpar@9 568 return;
alpar@9 569 }
alpar@9 570
alpar@9 571 static void generate(struct csa *csa)
alpar@9 572 { /* Generate a random network. */
alpar@9 573 struct arcs *arc_ptr = arc_list;
alpar@9 574 arc_ptr = gen_basic_grid(csa, arc_ptr);
alpar@9 575 select_source_sinks(csa);
alpar@9 576 arc_ptr = gen_additional_arcs(csa, arc_ptr);
alpar@9 577 gen_more_arcs(csa, arc_ptr);
alpar@9 578 assign_costs(csa);
alpar@9 579 assign_capacities(csa);
alpar@9 580 assign_imbalance(csa);
alpar@9 581 return;
alpar@9 582 }
alpar@9 583
alpar@9 584 static void output(struct csa *csa)
alpar@9 585 { /* Output the network in DIMACS format. */
alpar@9 586 struct arcs *arc_ptr;
alpar@9 587 struct imbalance *imb_ptr;
alpar@9 588 int i;
alpar@9 589 if (G != NULL) goto skip;
alpar@9 590 /* Output "c", "p" records. */
alpar@9 591 xprintf("c generated by GRIDGEN\n");
alpar@9 592 xprintf("c seed %d\n", seed_original);
alpar@9 593 xprintf("c nodes %d\n", n_node);
alpar@9 594 xprintf("c grid size %d X %d\n", n1, n2);
alpar@9 595 xprintf("c sources %d sinks %d\n", n_source, n_sink);
alpar@9 596 xprintf("c avg. degree %d\n", avg_degree);
alpar@9 597 xprintf("c supply %d\n", t_supply);
alpar@9 598 switch (arc_costs.distribution)
alpar@9 599 { case UNIFORM:
alpar@9 600 xprintf("c arc costs: UNIFORM distr. min %d max %d\n",
alpar@9 601 (int)arc_costs.parameter[0],
alpar@9 602 (int)arc_costs.parameter[1]);
alpar@9 603 break;
alpar@9 604 case EXPONENTIAL:
alpar@9 605 xprintf("c arc costs: EXPONENTIAL distr. lambda %d\n",
alpar@9 606 (int)arc_costs.parameter[0]);
alpar@9 607 break;
alpar@9 608 default:
alpar@9 609 xassert(csa != csa);
alpar@9 610 }
alpar@9 611 switch (capacities.distribution)
alpar@9 612 { case UNIFORM:
alpar@9 613 xprintf("c arc caps : UNIFORM distr. min %d max %d\n",
alpar@9 614 (int)capacities.parameter[0],
alpar@9 615 (int)capacities.parameter[1]);
alpar@9 616 break;
alpar@9 617 case EXPONENTIAL:
alpar@9 618 xprintf("c arc caps : EXPONENTIAL distr. %d lambda %d\n",
alpar@9 619 (int)capacities.parameter[0]);
alpar@9 620 break;
alpar@9 621 default:
alpar@9 622 xassert(csa != csa);
alpar@9 623 }
alpar@9 624 skip: if (G == NULL)
alpar@9 625 xprintf("p min %d %d\n", n_node, n_arc);
alpar@9 626 else
alpar@9 627 { glp_add_vertices(G, n_node);
alpar@9 628 if (v_rhs >= 0)
alpar@9 629 { double zero = 0.0;
alpar@9 630 for (i = 1; i <= n_node; i++)
alpar@9 631 { glp_vertex *v = G->v[i];
alpar@9 632 memcpy((char *)v->data + v_rhs, &zero, sizeof(double));
alpar@9 633 }
alpar@9 634 }
alpar@9 635 }
alpar@9 636 /* Output "n node supply". */
alpar@9 637 for (i = 0, imb_ptr = source_list; i < n_source; i++, imb_ptr++)
alpar@9 638 { if (G == NULL)
alpar@9 639 xprintf("n %d %d\n", imb_ptr->node, imb_ptr->supply);
alpar@9 640 else
alpar@9 641 { if (v_rhs >= 0)
alpar@9 642 { double temp = (double)imb_ptr->supply;
alpar@9 643 glp_vertex *v = G->v[imb_ptr->node];
alpar@9 644 memcpy((char *)v->data + v_rhs, &temp, sizeof(double));
alpar@9 645 }
alpar@9 646 }
alpar@9 647 }
alpar@9 648 for (i = 0, imb_ptr = sink_list; i < n_sink; i++, imb_ptr++)
alpar@9 649 { if (G == NULL)
alpar@9 650 xprintf("n %d %d\n", imb_ptr->node, imb_ptr->supply);
alpar@9 651 else
alpar@9 652 { if (v_rhs >= 0)
alpar@9 653 { double temp = (double)imb_ptr->supply;
alpar@9 654 glp_vertex *v = G->v[imb_ptr->node];
alpar@9 655 memcpy((char *)v->data + v_rhs, &temp, sizeof(double));
alpar@9 656 }
alpar@9 657 }
alpar@9 658 }
alpar@9 659 /* Output "a from to lowcap=0 hicap cost". */
alpar@9 660 for (i = 0, arc_ptr = arc_list; i < n_arc; i++, arc_ptr++)
alpar@9 661 { if (G == NULL)
alpar@9 662 xprintf("a %d %d 0 %d %d\n", arc_ptr->from, arc_ptr->to,
alpar@9 663 arc_ptr->u, arc_ptr->cost);
alpar@9 664 else
alpar@9 665 { glp_arc *a = glp_add_arc(G, arc_ptr->from, arc_ptr->to);
alpar@9 666 if (a_cap >= 0)
alpar@9 667 { double temp = (double)arc_ptr->u;
alpar@9 668 memcpy((char *)a->data + a_cap, &temp, sizeof(double));
alpar@9 669 }
alpar@9 670 if (a_cost >= 0)
alpar@9 671 { double temp = (double)arc_ptr->cost;
alpar@9 672 memcpy((char *)a->data + a_cost, &temp, sizeof(double));
alpar@9 673 }
alpar@9 674 }
alpar@9 675 }
alpar@9 676 return;
alpar@9 677 }
alpar@9 678
alpar@9 679 static double randy(struct csa *csa)
alpar@9 680 { /* Returns a random number between 0.0 and 1.0.
alpar@9 681 See Ward Cheney & David Kincaid, "Numerical Mathematics and
alpar@9 682 Computing," 2Ed, pp. 335. */
alpar@9 683 seed = 16807 * seed % 2147483647;
alpar@9 684 if (seed < 0) seed = - seed;
alpar@9 685 return seed * 4.6566128752459e-10;
alpar@9 686 }
alpar@9 687
alpar@9 688 static void select_source_sinks(struct csa *csa)
alpar@9 689 { /* Randomly select the source nodes and sink nodes. */
alpar@9 690 int i, *int_ptr;
alpar@9 691 int *temp_list; /* a temporary list of nodes */
alpar@9 692 struct imbalance *ptr;
alpar@9 693 double ab[2]; /* parameter for random number generator */
alpar@9 694 ab[0] = 0.9;
alpar@9 695 ab[1] = n_node - 0.99; /* upper limit is n_node-1 because the
alpar@9 696 supernode cannot be selected */
alpar@9 697 temp_list = xcalloc(n_node, sizeof(int));
alpar@9 698 for (i = 0, int_ptr = temp_list; i < n_node; i++, int_ptr++)
alpar@9 699 *int_ptr = 0;
alpar@9 700 /* Select the source nodes. */
alpar@9 701 for (i = 0, ptr = source_list; i < n_source; i++, ptr++)
alpar@9 702 { ptr->node = uniform(csa, ab);
alpar@9 703 if (temp_list[ptr->node] == 1) /* check for duplicates */
alpar@9 704 { ptr--;
alpar@9 705 i--;
alpar@9 706 }
alpar@9 707 else
alpar@9 708 temp_list[ptr->node] = 1;
alpar@9 709 }
alpar@9 710 /* Select the sink nodes. */
alpar@9 711 for (i = 0, ptr = sink_list; i < n_sink; i++, ptr++)
alpar@9 712 { ptr->node = uniform(csa, ab);
alpar@9 713 if (temp_list[ptr->node] == 1)
alpar@9 714 { ptr--;
alpar@9 715 i--;
alpar@9 716 }
alpar@9 717 else
alpar@9 718 temp_list[ptr->node] = 1;
alpar@9 719 }
alpar@9 720 xfree(temp_list);
alpar@9 721 return;
alpar@9 722 }
alpar@9 723
alpar@9 724 int uniform(struct csa *csa, double a[2])
alpar@9 725 { /* Generates an integer uniformly selected from [a[0],a[1]]. */
alpar@9 726 return (int)((a[1] - a[0]) * randy(csa) + a[0] + 0.5);
alpar@9 727 }
alpar@9 728
alpar@9 729 /**********************************************************************/
alpar@9 730
alpar@9 731 #if 0
alpar@9 732 int main(void)
alpar@9 733 { int parm[1+14];
alpar@9 734 double temp;
alpar@9 735 scanf("%d", &parm[1]);
alpar@9 736 scanf("%d", &parm[2]);
alpar@9 737 scanf("%d", &parm[3]);
alpar@9 738 scanf("%d", &parm[4]);
alpar@9 739 scanf("%d", &parm[5]);
alpar@9 740 scanf("%d", &parm[6]);
alpar@9 741 scanf("%d", &parm[7]);
alpar@9 742 scanf("%d", &parm[8]);
alpar@9 743 scanf("%d", &parm[9]);
alpar@9 744 if (parm[9] == 1)
alpar@9 745 { scanf("%d", &parm[10]);
alpar@9 746 scanf("%d", &parm[11]);
alpar@9 747 }
alpar@9 748 else
alpar@9 749 { scanf("%le", &temp);
alpar@9 750 parm[10] = (int)(100.0 * temp + .5);
alpar@9 751 parm[11] = 0;
alpar@9 752 }
alpar@9 753 scanf("%d", &parm[12]);
alpar@9 754 if (parm[12] == 1)
alpar@9 755 { scanf("%d", &parm[13]);
alpar@9 756 scanf("%d", &parm[14]);
alpar@9 757 }
alpar@9 758 else
alpar@9 759 { scanf("%le", &temp);
alpar@9 760 parm[13] = (int)(100.0 * temp + .5);
alpar@9 761 parm[14] = 0;
alpar@9 762 }
alpar@9 763 glp_gridgen(NULL, 0, 0, 0, parm);
alpar@9 764 return 0;
alpar@9 765 }
alpar@9 766 #endif
alpar@9 767
alpar@9 768 /* eof */