COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpnet04.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

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