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 */
|