aboutsummaryrefslogtreecommitdiffstats
path: root/test/monniaux/glpk-4.65/src/api/gridgen.c
diff options
context:
space:
mode:
Diffstat (limited to 'test/monniaux/glpk-4.65/src/api/gridgen.c')
-rw-r--r--test/monniaux/glpk-4.65/src/api/gridgen.c769
1 files changed, 769 insertions, 0 deletions
diff --git a/test/monniaux/glpk-4.65/src/api/gridgen.c b/test/monniaux/glpk-4.65/src/api/gridgen.c
new file mode 100644
index 00000000..8cd3517f
--- /dev/null
+++ b/test/monniaux/glpk-4.65/src/api/gridgen.c
@@ -0,0 +1,769 @@
+/* gridgen.c (grid-like network problem generator) */
+
+/***********************************************************************
+* This code is part of GLPK (GNU Linear Programming Kit).
+*
+* This code is a modified version of the program GRIDGEN, a grid-like
+* network problem generator developed by Yusin Lee and Jim Orlin.
+* The original code is publically available on the DIMACS ftp site at:
+* <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen>.
+*
+* All changes concern only the program interface, so this modified
+* version produces exactly the same instances as the original version.
+*
+* Changes were made by Andrew Makhorin <mao@gnu.org>.
+*
+* GLPK is free software: you can redistribute it and/or modify it
+* under the terms of the GNU General Public License as published by
+* the Free Software Foundation, either version 3 of the License, or
+* (at your option) any later version.
+*
+* GLPK is distributed in the hope that it will be useful, but WITHOUT
+* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+* License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
+***********************************************************************/
+
+#include "env.h"
+#include "glpk.h"
+
+/***********************************************************************
+* NAME
+*
+* glp_gridgen - grid-like network problem generator
+*
+* SYNOPSIS
+*
+* int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
+* const int parm[1+14]);
+*
+* DESCRIPTION
+*
+* The routine glp_gridgen is a grid-like network problem generator
+* developed by Yusin Lee and Jim Orlin.
+*
+* The parameter G specifies the graph object, to which the generated
+* problem data have to be stored. Note that on entry the graph object
+* is erased with the routine glp_erase_graph.
+*
+* The parameter v_rhs specifies an offset of the field of type double
+* in the vertex data block, to which the routine stores the supply or
+* demand value. If v_rhs < 0, the value is not stored.
+*
+* The parameter a_cap specifies an offset of the field of type double
+* in the arc data block, to which the routine stores the arc capacity.
+* If a_cap < 0, the capacity is not stored.
+*
+* The parameter a_cost specifies an offset of the field of type double
+* in the arc data block, to which the routine stores the per-unit cost
+* if the arc flow. If a_cost < 0, the cost is not stored.
+*
+* The array parm contains description of the network to be generated:
+*
+* parm[0] not used
+* parm[1] two-ways arcs indicator:
+* 1 - if links in both direction should be generated
+* 0 - otherwise
+* parm[2] random number seed (a positive integer)
+* parm[3] number of nodes (the number of nodes generated might be
+* slightly different to make the network a grid)
+* parm[4] grid width
+* parm[5] number of sources
+* parm[6] number of sinks
+* parm[7] average degree
+* parm[8] total flow
+* parm[9] distribution of arc costs:
+* 1 - uniform
+* 2 - exponential
+* parm[10] lower bound for arc cost (uniform)
+* 100 * lambda (exponential)
+* parm[11] upper bound for arc cost (uniform)
+* not used (exponential)
+* parm[12] distribution of arc capacities:
+* 1 - uniform
+* 2 - exponential
+* parm[13] lower bound for arc capacity (uniform)
+* 100 * lambda (exponential)
+* parm[14] upper bound for arc capacity (uniform)
+* not used (exponential)
+*
+* RETURNS
+*
+* If the instance was successfully generated, the routine glp_gridgen
+* returns zero; otherwise, if specified parameters are inconsistent,
+* the routine returns a non-zero error code.
+*
+* COMMENTS
+*
+* This network generator generates a grid-like network plus a super
+* node. In additional to the arcs connecting the nodes in the grid,
+* there is an arc from each supply node to the super node and from the
+* super node to each demand node to guarantee feasiblity. These arcs
+* have very high costs and very big capacities.
+*
+* The idea of this network generator is as follows: First, a grid of
+* n1 * n2 is generated. For example, 5 * 3. The nodes are numbered as
+* 1 to 15, and the supernode is numbered as n1*n2+1. Then arcs between
+* adjacent nodes are generated. For these arcs, the user is allowed to
+* specify either to generate two-way arcs or one-way arcs. If two-way
+* arcs are to be generated, two arcs, one in each direction, will be
+* generated between each adjacent node pairs. Otherwise, only one arc
+* will be generated. If this is the case, the arcs will be generated
+* in alterntive directions as shown below.
+*
+* 1 ---> 2 ---> 3 ---> 4 ---> 5
+* | ^ | ^ |
+* | | | | |
+* V | V | V
+* 6 <--- 7 <--- 8 <--- 9 <--- 10
+* | ^ | ^ |
+* | | | | |
+* V | V | V
+* 11 --->12 --->13 --->14 ---> 15
+*
+* Then the arcs between the super node and the source/sink nodes are
+* added as mentioned before. If the number of arcs still doesn't reach
+* the requirement, additional arcs will be added by uniformly picking
+* random node pairs. There is no checking to prevent multiple arcs
+* between any pair of nodes. However, there will be no self-arcs (arcs
+* that poins back to its tail node) in the network.
+*
+* The source and sink nodes are selected uniformly in the network, and
+* the imbalances of each source/sink node are also assigned by uniform
+* distribution. */
+
+struct stat_para
+{ /* structure for statistical distributions */
+ int distribution;
+ /* the distribution: */
+#define UNIFORM 1 /* uniform distribution */
+#define EXPONENTIAL 2 /* exponential distribution */
+ double parameter[5];
+ /* the parameters of the distribution */
+};
+
+struct arcs
+{ int from;
+ /* the FROM node of that arc */
+ int to;
+ /* the TO node of that arc */
+ int cost;
+ /* original cost of that arc */
+ int u;
+ /* capacity of the arc */
+};
+
+struct imbalance
+{ int node;
+ /* Node ID */
+ int supply;
+ /* Supply of that node */
+};
+
+struct csa
+{ /* common storage area */
+ glp_graph *G;
+ int v_rhs, a_cap, a_cost;
+ int seed;
+ /* random number seed */
+ int seed_original;
+ /* the original seed from input */
+ int two_way;
+ /* 0: generate arcs in both direction for the basic grid, except
+ for the arcs to/from the super node. 1: o/w */
+ int n_node;
+ /* total number of nodes in the network, numbered 1 to n_node,
+ including the super node, which is the last one */
+ int n_arc;
+ /* total number of arcs in the network, counting EVERY arc. */
+ int n_grid_arc;
+ /* number of arcs in the basic grid, including the arcs to/from
+ the super node */
+ int n_source, n_sink;
+ /* number of source and sink nodes */
+ int avg_degree;
+ /* average degree, arcs to and from the super node are counted */
+ int t_supply;
+ /* total supply in the network */
+ int n1, n2;
+ /* the two edges of the network grid. n1 >= n2 */
+ struct imbalance *source_list, *sink_list;
+ /* head of the array of source/sink nodes */
+ struct stat_para arc_costs;
+ /* the distribution of arc costs */
+ struct stat_para capacities;
+ /* distribution of the capacities of the arcs */
+ struct arcs *arc_list;
+ /* head of the arc list array. Arcs in this array are in the
+ order of grid_arcs, arcs to/from super node, and other arcs */
+};
+
+#define G (csa->G)
+#define v_rhs (csa->v_rhs)
+#define a_cap (csa->a_cap)
+#define a_cost (csa->a_cost)
+#define seed (csa->seed)
+#define seed_original (csa->seed_original)
+#define two_way (csa->two_way)
+#define n_node (csa->n_node)
+#define n_arc (csa->n_arc)
+#define n_grid_arc (csa->n_grid_arc)
+#define n_source (csa->n_source)
+#define n_sink (csa->n_sink)
+#define avg_degree (csa->avg_degree)
+#define t_supply (csa->t_supply)
+#define n1 (csa->n1)
+#define n2 (csa->n2)
+#define source_list (csa->source_list)
+#define sink_list (csa->sink_list)
+#define arc_costs (csa->arc_costs)
+#define capacities (csa->capacities)
+#define arc_list (csa->arc_list)
+
+static void assign_capacities(struct csa *csa);
+static void assign_costs(struct csa *csa);
+static void assign_imbalance(struct csa *csa);
+static int exponential(struct csa *csa, double lambda[1]);
+static struct arcs *gen_additional_arcs(struct csa *csa, struct arcs
+ *arc_ptr);
+static struct arcs *gen_basic_grid(struct csa *csa, struct arcs
+ *arc_ptr);
+static void gen_more_arcs(struct csa *csa, struct arcs *arc_ptr);
+static void generate(struct csa *csa);
+static void output(struct csa *csa);
+static double randy(struct csa *csa);
+static void select_source_sinks(struct csa *csa);
+static int uniform(struct csa *csa, double a[2]);
+
+int glp_gridgen(glp_graph *G_, int _v_rhs, int _a_cap, int _a_cost,
+ const int parm[1+14])
+{ struct csa _csa, *csa = &_csa;
+ int n, ret;
+ G = G_;
+ v_rhs = _v_rhs;
+ a_cap = _a_cap;
+ a_cost = _a_cost;
+ if (G != NULL)
+ { if (v_rhs >= 0 && v_rhs > G->v_size - (int)sizeof(double))
+ xerror("glp_gridgen: v_rhs = %d; invalid offset\n", v_rhs);
+ if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
+ xerror("glp_gridgen: a_cap = %d; invalid offset\n", a_cap);
+ if (a_cost >= 0 && a_cost > G->a_size - (int)sizeof(double))
+ xerror("glp_gridgen: a_cost = %d; invalid offset\n", a_cost)
+ ;
+ }
+ /* Check the parameters for consistency. */
+ if (!(parm[1] == 0 || parm[1] == 1))
+ { ret = 1;
+ goto done;
+ }
+ if (parm[2] < 1)
+ { ret = 2;
+ goto done;
+ }
+ if (!(10 <= parm[3] && parm[3] <= 40000))
+ { ret = 3;
+ goto done;
+ }
+ if (!(1 <= parm[4] && parm[4] <= 40000))
+ { ret = 4;
+ goto done;
+ }
+ if (!(parm[5] >= 0 && parm[6] >= 0 && parm[5] + parm[6] <=
+ parm[3]))
+ { ret = 5;
+ goto done;
+ }
+ if (!(1 <= parm[7] && parm[7] <= parm[3]))
+ { ret = 6;
+ goto done;
+ }
+ if (parm[8] < 0)
+ { ret = 7;
+ goto done;
+ }
+ if (!(parm[9] == 1 || parm[9] == 2))
+ { ret = 8;
+ goto done;
+ }
+ if (parm[9] == 1 && parm[10] > parm[11] ||
+ parm[9] == 2 && parm[10] < 1)
+ { ret = 9;
+ goto done;
+ }
+ if (!(parm[12] == 1 || parm[12] == 2))
+ { ret = 10;
+ goto done;
+ }
+ if (parm[12] == 1 && !(0 <= parm[13] && parm[13] <= parm[14]) ||
+ parm[12] == 2 && parm[13] < 1)
+ { ret = 11;
+ goto done;
+ }
+ /* Initialize the graph object. */
+ if (G != NULL)
+ { glp_erase_graph(G, G->v_size, G->a_size);
+ glp_set_graph_name(G, "GRIDGEN");
+ }
+ /* Copy the generator parameters. */
+ two_way = parm[1];
+ seed_original = seed = parm[2];
+ n_node = parm[3];
+ n = parm[4];
+ n_source = parm[5];
+ n_sink = parm[6];
+ avg_degree = parm[7];
+ t_supply = parm[8];
+ arc_costs.distribution = parm[9];
+ if (parm[9] == 1)
+ { arc_costs.parameter[0] = parm[10];
+ arc_costs.parameter[1] = parm[11];
+ }
+ else
+ { arc_costs.parameter[0] = (double)parm[10] / 100.0;
+ arc_costs.parameter[1] = 0.0;
+ }
+ capacities.distribution = parm[12];
+ if (parm[12] == 1)
+ { capacities.parameter[0] = parm[13];
+ capacities.parameter[1] = parm[14];
+ }
+ else
+ { capacities.parameter[0] = (double)parm[13] / 100.0;
+ capacities.parameter[1] = 0.0;
+ }
+ /* Calculate the edge lengths of the grid according to the
+ input. */
+ if (n * n >= n_node)
+ { n1 = n;
+ n2 = (int)((double)n_node / (double)n + 0.5);
+ }
+ else
+ { n2 = n;
+ n1 = (int)((double)n_node / (double)n + 0.5);
+ }
+ /* Recalculate the total number of nodes and plus 1 for the super
+ node. */
+ n_node = n1 * n2 + 1;
+ n_arc = n_node * avg_degree;
+ n_grid_arc = (two_way + 1) * ((n1 - 1) * n2 + (n2 - 1) * n1) +
+ n_source + n_sink;
+ if (n_grid_arc > n_arc) n_arc = n_grid_arc;
+ arc_list = xcalloc(n_arc, sizeof(struct arcs));
+ source_list = xcalloc(n_source, sizeof(struct imbalance));
+ sink_list = xcalloc(n_sink, sizeof(struct imbalance));
+ /* Generate a random network. */
+ generate(csa);
+ /* Output the network. */
+ output(csa);
+ /* Free all allocated memory. */
+ xfree(arc_list);
+ xfree(source_list);
+ xfree(sink_list);
+ /* The instance has been successfully generated. */
+ ret = 0;
+done: return ret;
+}
+
+#undef random
+
+static void assign_capacities(struct csa *csa)
+{ /* Assign a capacity to each arc. */
+ struct arcs *arc_ptr = arc_list;
+ int (*random)(struct csa *csa, double *);
+ int i;
+ /* Determine the random number generator to use. */
+ switch (arc_costs.distribution)
+ { case UNIFORM:
+ random = uniform;
+ break;
+ case EXPONENTIAL:
+ random = exponential;
+ break;
+ default:
+ xassert(csa != csa);
+ }
+ /* Assign capacities to grid arcs. */
+ for (i = n_source + n_sink; i < n_grid_arc; i++, arc_ptr++)
+ arc_ptr->u = random(csa, capacities.parameter);
+ i = i - n_source - n_sink;
+ /* Assign capacities to arcs to/from supernode. */
+ for (; i < n_grid_arc; i++, arc_ptr++)
+ arc_ptr->u = t_supply;
+ /* Assign capacities to all other arcs. */
+ for (; i < n_arc; i++, arc_ptr++)
+ arc_ptr->u = random(csa, capacities.parameter);
+ return;
+}
+
+static void assign_costs(struct csa *csa)
+{ /* Assign a cost to each arc. */
+ struct arcs *arc_ptr = arc_list;
+ int (*random)(struct csa *csa, double *);
+ int i;
+ /* A high cost assigned to arcs to/from the supernode. */
+ int high_cost;
+ /* The maximum cost assigned to arcs in the base grid. */
+ int max_cost = 0;
+ /* Determine the random number generator to use. */
+ switch (arc_costs.distribution)
+ { case UNIFORM:
+ random = uniform;
+ break;
+ case EXPONENTIAL:
+ random = exponential;
+ break;
+ default:
+ xassert(csa != csa);
+ }
+ /* Assign costs to arcs in the base grid. */
+ for (i = n_source + n_sink; i < n_grid_arc; i++, arc_ptr++)
+ { arc_ptr->cost = random(csa, arc_costs.parameter);
+ if (max_cost < arc_ptr->cost) max_cost = arc_ptr->cost;
+ }
+ i = i - n_source - n_sink;
+ /* Assign costs to arcs to/from the super node. */
+ high_cost = max_cost * 2;
+ for (; i < n_grid_arc; i++, arc_ptr++)
+ arc_ptr->cost = high_cost;
+ /* Assign costs to all other arcs. */
+ for (; i < n_arc; i++, arc_ptr++)
+ arc_ptr->cost = random(csa, arc_costs.parameter);
+ return;
+}
+
+static void assign_imbalance(struct csa *csa)
+{ /* Assign an imbalance to each node. */
+ int total, i;
+ double avg;
+ struct imbalance *ptr;
+ /* assign the supply nodes */
+ avg = 2.0 * t_supply / n_source;
+ do
+ { for (i = 1, total = t_supply, ptr = source_list + 1;
+ i < n_source; i++, ptr++)
+ { ptr->supply = (int)(randy(csa) * avg + 0.5);
+ total -= ptr->supply;
+ }
+ source_list->supply = total;
+ }
+ /* redo all if the assignment "overshooted" */
+ while (total <= 0);
+ /* assign the demand nodes */
+ avg = -2.0 * t_supply / n_sink;
+ do
+ { for (i = 1, total = t_supply, ptr = sink_list + 1;
+ i < n_sink; i++, ptr++)
+ { ptr->supply = (int)(randy(csa) * avg - 0.5);
+ total += ptr->supply;
+ }
+ sink_list->supply = - total;
+ }
+ while (total <= 0);
+ return;
+}
+
+static int exponential(struct csa *csa, double lambda[1])
+{ /* Returns an "exponentially distributed" integer with parameter
+ lambda. */
+ return ((int)(- lambda[0] * log((double)randy(csa)) + 0.5));
+}
+
+static struct arcs *gen_additional_arcs(struct csa *csa, struct arcs
+ *arc_ptr)
+{ /* Generate an arc from each source to the supernode and from
+ supernode to each sink. */
+ int i;
+ for (i = 0; i < n_source; i++, arc_ptr++)
+ { arc_ptr->from = source_list[i].node;
+ arc_ptr->to = n_node;
+ }
+ for (i = 0; i < n_sink; i++, arc_ptr++)
+ { arc_ptr->to = sink_list[i].node;
+ arc_ptr->from = n_node;
+ }
+ return arc_ptr;
+}
+
+static struct arcs *gen_basic_grid(struct csa *csa, struct arcs
+ *arc_ptr)
+{ /* Generate the basic grid. */
+ int direction = 1, i, j, k;
+ if (two_way)
+ { /* Generate an arc in each direction. */
+ for (i = 1; i < n_node; i += n1)
+ { for (j = i, k = j + n1 - 1; j < k; j++)
+ { arc_ptr->from = j;
+ arc_ptr->to = j + 1;
+ arc_ptr++;
+ arc_ptr->from = j + 1;
+ arc_ptr->to = j;
+ arc_ptr++;
+ }
+ }
+ for (i = 1; i <= n1; i++)
+ { for (j = i + n1; j < n_node; j += n1)
+ { arc_ptr->from = j;
+ arc_ptr->to = j - n1;
+ arc_ptr++;
+ arc_ptr->from = j - n1;
+ arc_ptr->to = j;
+ arc_ptr++;
+ }
+ }
+ }
+ else
+ { /* Generate one arc in each direction. */
+ for (i = 1; i < n_node; i += n1)
+ { if (direction == 1)
+ j = i;
+ else
+ j = i + 1;
+ for (k = j + n1 - 1; j < k; j++)
+ { arc_ptr->from = j;
+ arc_ptr->to = j + direction;
+ arc_ptr++;
+ }
+ direction = - direction;
+ }
+ for (i = 1; i <= n1; i++)
+ { j = i + n1;
+ if (direction == 1)
+ { for (; j < n_node; j += n1)
+ { arc_ptr->from = j - n1;
+ arc_ptr->to = j;
+ arc_ptr++;
+ }
+ }
+ else
+ { for (; j < n_node; j += n1)
+ { arc_ptr->from = j - n1;
+ arc_ptr->to = j;
+ arc_ptr++;
+ }
+ }
+ direction = - direction;
+ }
+ }
+ return arc_ptr;
+}
+
+static void gen_more_arcs(struct csa *csa, struct arcs *arc_ptr)
+{ /* Generate random arcs to meet the specified density. */
+ int i;
+ double ab[2];
+ ab[0] = 0.9;
+ ab[1] = n_node - 0.99; /* upper limit is n_node-1 because the
+ supernode cannot be selected */
+ for (i = n_grid_arc; i < n_arc; i++, arc_ptr++)
+ { arc_ptr->from = uniform(csa, ab);
+ arc_ptr->to = uniform(csa, ab);
+ if (arc_ptr->from == arc_ptr->to)
+ { arc_ptr--;
+ i--;
+ }
+ }
+ return;
+}
+
+static void generate(struct csa *csa)
+{ /* Generate a random network. */
+ struct arcs *arc_ptr = arc_list;
+ arc_ptr = gen_basic_grid(csa, arc_ptr);
+ select_source_sinks(csa);
+ arc_ptr = gen_additional_arcs(csa, arc_ptr);
+ gen_more_arcs(csa, arc_ptr);
+ assign_costs(csa);
+ assign_capacities(csa);
+ assign_imbalance(csa);
+ return;
+}
+
+static void output(struct csa *csa)
+{ /* Output the network in DIMACS format. */
+ struct arcs *arc_ptr;
+ struct imbalance *imb_ptr;
+ int i;
+ if (G != NULL) goto skip;
+ /* Output "c", "p" records. */
+ xprintf("c generated by GRIDGEN\n");
+ xprintf("c seed %d\n", seed_original);
+ xprintf("c nodes %d\n", n_node);
+ xprintf("c grid size %d X %d\n", n1, n2);
+ xprintf("c sources %d sinks %d\n", n_source, n_sink);
+ xprintf("c avg. degree %d\n", avg_degree);
+ xprintf("c supply %d\n", t_supply);
+ switch (arc_costs.distribution)
+ { case UNIFORM:
+ xprintf("c arc costs: UNIFORM distr. min %d max %d\n",
+ (int)arc_costs.parameter[0],
+ (int)arc_costs.parameter[1]);
+ break;
+ case EXPONENTIAL:
+ xprintf("c arc costs: EXPONENTIAL distr. lambda %d\n",
+ (int)arc_costs.parameter[0]);
+ break;
+ default:
+ xassert(csa != csa);
+ }
+ switch (capacities.distribution)
+ { case UNIFORM:
+ xprintf("c arc caps : UNIFORM distr. min %d max %d\n",
+ (int)capacities.parameter[0],
+ (int)capacities.parameter[1]);
+ break;
+ case EXPONENTIAL:
+ xprintf("c arc caps : EXPONENTIAL distr. %d lambda %d\n",
+ (int)capacities.parameter[0]);
+ break;
+ default:
+ xassert(csa != csa);
+ }
+skip: if (G == NULL)
+ xprintf("p min %d %d\n", n_node, n_arc);
+ else
+ { glp_add_vertices(G, n_node);
+ if (v_rhs >= 0)
+ { double zero = 0.0;
+ for (i = 1; i <= n_node; i++)
+ { glp_vertex *v = G->v[i];
+ memcpy((char *)v->data + v_rhs, &zero, sizeof(double));
+ }
+ }
+ }
+ /* Output "n node supply". */
+ for (i = 0, imb_ptr = source_list; i < n_source; i++, imb_ptr++)
+ { if (G == NULL)
+ xprintf("n %d %d\n", imb_ptr->node, imb_ptr->supply);
+ else
+ { if (v_rhs >= 0)
+ { double temp = (double)imb_ptr->supply;
+ glp_vertex *v = G->v[imb_ptr->node];
+ memcpy((char *)v->data + v_rhs, &temp, sizeof(double));
+ }
+ }
+ }
+ for (i = 0, imb_ptr = sink_list; i < n_sink; i++, imb_ptr++)
+ { if (G == NULL)
+ xprintf("n %d %d\n", imb_ptr->node, imb_ptr->supply);
+ else
+ { if (v_rhs >= 0)
+ { double temp = (double)imb_ptr->supply;
+ glp_vertex *v = G->v[imb_ptr->node];
+ memcpy((char *)v->data + v_rhs, &temp, sizeof(double));
+ }
+ }
+ }
+ /* Output "a from to lowcap=0 hicap cost". */
+ for (i = 0, arc_ptr = arc_list; i < n_arc; i++, arc_ptr++)
+ { if (G == NULL)
+ xprintf("a %d %d 0 %d %d\n", arc_ptr->from, arc_ptr->to,
+ arc_ptr->u, arc_ptr->cost);
+ else
+ { glp_arc *a = glp_add_arc(G, arc_ptr->from, arc_ptr->to);
+ if (a_cap >= 0)
+ { double temp = (double)arc_ptr->u;
+ memcpy((char *)a->data + a_cap, &temp, sizeof(double));
+ }
+ if (a_cost >= 0)
+ { double temp = (double)arc_ptr->cost;
+ memcpy((char *)a->data + a_cost, &temp, sizeof(double));
+ }
+ }
+ }
+ return;
+}
+
+static double randy(struct csa *csa)
+{ /* Returns a random number between 0.0 and 1.0.
+ See Ward Cheney & David Kincaid, "Numerical Mathematics and
+ Computing," 2Ed, pp. 335. */
+ seed = 16807 * seed % 2147483647;
+ if (seed < 0) seed = - seed;
+ return seed * 4.6566128752459e-10;
+}
+
+static void select_source_sinks(struct csa *csa)
+{ /* Randomly select the source nodes and sink nodes. */
+ int i, *int_ptr;
+ int *temp_list; /* a temporary list of nodes */
+ struct imbalance *ptr;
+ double ab[2]; /* parameter for random number generator */
+ ab[0] = 0.9;
+ ab[1] = n_node - 0.99; /* upper limit is n_node-1 because the
+ supernode cannot be selected */
+ temp_list = xcalloc(n_node, sizeof(int));
+ for (i = 0, int_ptr = temp_list; i < n_node; i++, int_ptr++)
+ *int_ptr = 0;
+ /* Select the source nodes. */
+ for (i = 0, ptr = source_list; i < n_source; i++, ptr++)
+ { ptr->node = uniform(csa, ab);
+ if (temp_list[ptr->node] == 1) /* check for duplicates */
+ { ptr--;
+ i--;
+ }
+ else
+ temp_list[ptr->node] = 1;
+ }
+ /* Select the sink nodes. */
+ for (i = 0, ptr = sink_list; i < n_sink; i++, ptr++)
+ { ptr->node = uniform(csa, ab);
+ if (temp_list[ptr->node] == 1)
+ { ptr--;
+ i--;
+ }
+ else
+ temp_list[ptr->node] = 1;
+ }
+ xfree(temp_list);
+ return;
+}
+
+int uniform(struct csa *csa, double a[2])
+{ /* Generates an integer uniformly selected from [a[0],a[1]]. */
+ return (int)((a[1] - a[0]) * randy(csa) + a[0] + 0.5);
+}
+
+/**********************************************************************/
+
+#if 0
+int main(void)
+{ int parm[1+14];
+ double temp;
+ scanf("%d", &parm[1]);
+ scanf("%d", &parm[2]);
+ scanf("%d", &parm[3]);
+ scanf("%d", &parm[4]);
+ scanf("%d", &parm[5]);
+ scanf("%d", &parm[6]);
+ scanf("%d", &parm[7]);
+ scanf("%d", &parm[8]);
+ scanf("%d", &parm[9]);
+ if (parm[9] == 1)
+ { scanf("%d", &parm[10]);
+ scanf("%d", &parm[11]);
+ }
+ else
+ { scanf("%le", &temp);
+ parm[10] = (int)(100.0 * temp + .5);
+ parm[11] = 0;
+ }
+ scanf("%d", &parm[12]);
+ if (parm[12] == 1)
+ { scanf("%d", &parm[13]);
+ scanf("%d", &parm[14]);
+ }
+ else
+ { scanf("%le", &temp);
+ parm[13] = (int)(100.0 * temp + .5);
+ parm[14] = 0;
+ }
+ glp_gridgen(NULL, 0, 0, 0, parm);
+ return 0;
+}
+#endif
+
+/* eof */
generated by cgit (git 2.34.1) at 2024-06-12 04:17:26 +0000