glpnet04.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

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