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

/* glpnet05.c (Goldfarb's maximum flow problem generator) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  This code is a modified version of the program RMFGEN, a maxflow
*  problem generator developed by D.Goldfarb and M.Grigoriadis, and
*  originally implemented by Tamas Badics <badics@rutcor.rutgers.edu>.
*  The original code is publically available on the DIMACS ftp site at:
*  <ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf>.
*
*  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 "glpapi.h"
#include "glprng.h"

/***********************************************************************
*  NAME
*
*  glp_rmfgen - Goldfarb's maximum flow problem generator
*
*  SYNOPSIS
*
*  int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap,
*     const int parm[1+5]);
*
*  DESCRIPTION
*
*  The routine glp_rmfgen is a maximum flow problem generator developed
*  by D.Goldfarb and M.Grigoriadis.
*
*  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 pointer s specifies a location, to which the routine stores the
*  source node number. If s is NULL, the node number is not stored.
*
*  The pointer t specifies a location, to which the routine stores the
*  sink node number. If t is NULL, the node number 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 array parm contains description of the network to be generated:
*
*  parm[0]  not used
*  parm[1]  (seed)   random number seed (a positive integer)
*  parm[2]  (a)      frame size
*  parm[3]  (b)      depth
*  parm[4]  (c1)     minimal arc capacity
*  parm[5]  (c2)     maximal arc capacity
*
*  RETURNS
*
*  If the instance was successfully generated, the routine glp_netgen
*  returns zero; otherwise, if specified parameters are inconsistent,
*  the routine returns a non-zero error code.
*
*  COMMENTS
*
*  The generated network is as follows. It has b pieces of frames of
*  size a * a. (So alltogether the number of vertices is a * a * b)
*
*  In each frame all the vertices are connected with their neighbours
*  (forth and back). In addition the vertices of a frame are connected
*  one to one with the vertices of next frame using a random permutation
*  of those vertices.
*
*  The source is the lower left vertex of the first frame, the sink is
*  the upper right vertex of the b'th frame.
*
*                    t
*           +-------+
*           |      .|
*           |     . |
*        /  |    /  |
*       +-------+/ -+ b
*       |    |  |/.
*     a |   -v- |/
*       |    |  |/
*       +-------+ 1
*      s    a
*
*  The capacities are randomly chosen integers from the range of [c1,c2]
*  in the case of interconnecting edges, and c2 * a * a for the in-frame
*  edges.
*
*  REFERENCES
*
*  D.Goldfarb and M.D.Grigoriadis, "A computational comparison of the
*  Dinic and network simplex methods for maximum flow." Annals of Op.
*  Res. 13 (1988), pp. 83-123.
*
*  U.Derigs and W.Meier, "Implementing Goldberg's max-flow algorithm:
*  A computational investigation." Zeitschrift fuer Operations Research
*  33 (1989), pp. 383-403. */

typedef struct VERTEX
{     struct EDGE **edgelist;
      /* Pointer to the list of pointers to the adjacent edges.
         (No matter that to or from edges) */
      struct EDGE **current;
      /* Pointer to the current edge */
      int degree;
      /* Number of adjacent edges (both direction) */
      int index;
} vertex;

typedef struct EDGE
{     int from;
      int to;
      int cap;
      /* Capacity */
} edge;

typedef struct NETWORK
{     struct NETWORK *next, *prev;
      int vertnum;
      int edgenum;
      vertex *verts;
      /* Vertex array[1..vertnum] */
      edge *edges;
      /* Edge array[1..edgenum] */
      int source;
      /* Pointer to the source */
      int sink;
      /* Pointer to the sink */
} network;

struct csa
{     /* common storage area */
      glp_graph *G;
      int *s, *t, a_cap;
      RNG *rand;
      network *N;
      int *Parr;
      int A, AA, C2AA, Ec;
};

#define G      (csa->G)
#define s      (csa->s)
#define t      (csa->t)
#define a_cap  (csa->a_cap)
#define N      (csa->N)
#define Parr   (csa->Parr)
#define A      (csa->A)
#define AA     (csa->AA)
#define C2AA   (csa->C2AA)
#define Ec     (csa->Ec)

#undef random
#define random(A) (int)(rng_unif_01(csa->rand) * (double)(A))
#define RANDOM(A, B) (int)(random((B) - (A) + 1) + (A))
#define sgn(A) (((A) > 0) ? 1 : ((A) == 0) ? 0 : -1)

static void make_edge(struct csa *csa, int from, int to, int c1, int c2)
{     Ec++;
      N->edges[Ec].from = from;
      N->edges[Ec].to = to;
      N->edges[Ec].cap = RANDOM(c1, c2);
      return;
}

static void permute(struct csa *csa)
{     int i, j, tmp;
      for (i = 1; i < AA; i++)
      {  j = RANDOM(i, AA);
         tmp = Parr[i];
         Parr[i] = Parr[j];
         Parr[j] = tmp;
      }
      return;
}

static void connect(struct csa *csa, int offset, int cv, int x1, int y1)
{     int cv1;
      cv1 = offset + (x1 - 1) * A + y1;
      Ec++;
      N->edges[Ec].from = cv;
      N->edges[Ec].to = cv1;
      N->edges[Ec].cap = C2AA;
      return;
}

static network *gen_rmf(struct csa *csa, int a, int b, int c1, int c2)
{     /* generates a network with a*a*b nodes and 6a*a*b-4ab-2a*a edges
         random_frame network:
         Derigs & Meier, Methods & Models of OR (1989), 33:383-403 */
      int x, y, z, offset, cv;
      A = a;
      AA = a * a;
      C2AA = c2 * AA;
      Ec = 0;
      N = (network *)xmalloc(sizeof(network));
      N->vertnum = AA * b;
      N->edgenum = 5 * AA * b - 4 * A * b - AA;
      N->edges = (edge *)xcalloc(N->edgenum + 1, sizeof(edge));
      N->source = 1;
      N->sink = N->vertnum;
      Parr = (int *)xcalloc(AA + 1, sizeof(int));
      for (x = 1; x <= AA; x++)
         Parr[x] = x;
      for (z = 1; z <= b; z++)
      {  offset = AA * (z - 1);
         if (z != b)
            permute(csa);
         for (x = 1; x <= A; x++)
         {  for (y = 1; y <= A; y++)
            {  cv = offset + (x - 1) * A + y;
               if (z != b)
                  make_edge(csa, cv, offset + AA + Parr[cv - offset],
                     c1, c2); /* the intermediate edges */
               if (y < A)
                  connect(csa, offset, cv, x, y + 1);
               if (y > 1)
                  connect(csa, offset, cv, x, y - 1);
               if (x < A)
                  connect(csa, offset, cv, x + 1, y);
               if (x > 1)
                  connect(csa, offset, cv, x - 1, y);
            }
         }
      }
      xfree(Parr);
      return N;
}

static void print_max_format(struct csa *csa, network *n, char *comm[],
      int dim)
{     /* prints a network heading with dim lines of comments (no \n
         needs at the ends) */
      int i, vnum, e_num;
      edge *e;
      vnum = n->vertnum;
      e_num = n->edgenum;
      if (G == NULL)
      {  for (i = 0; i < dim; i++)
            xprintf("c %s\n", comm[i]);
         xprintf("p max %7d %10d\n", vnum, e_num);
         xprintf("n %7d s\n", n->source);
         xprintf("n %7d t\n", n->sink);
      }
      else
      {  glp_add_vertices(G, vnum);
         if (s != NULL) *s = n->source;
         if (t != NULL) *t = n->sink;
      }
      for (i = 1; i <= e_num; i++)
      {  e = &n->edges[i];
         if (G == NULL)
            xprintf("a %7d %7d %10d\n", e->from, e->to, (int)e->cap);
         else
         {  glp_arc *a = glp_add_arc(G, e->from, e->to);
            if (a_cap >= 0)
            {  double temp = (double)e->cap;
               memcpy((char *)a->data + a_cap, &temp, sizeof(double));
            }
         }
      }
      return;
}

static void gen_free_net(network *n)
{     xfree(n->edges);
      xfree(n);
      return;
}

int glp_rmfgen(glp_graph *G_, int *_s, int *_t, int _a_cap,
      const int parm[1+5])
{     struct csa _csa, *csa = &_csa;
      network *n;
      char comm[10][80], *com1[10];
      int seed, a, b, c1, c2, ret;
      G = G_;
      s = _s;
      t = _t;
      a_cap = _a_cap;
      if (G != NULL)
      {  if (a_cap >= 0 && a_cap > G->a_size - (int)sizeof(double))
           xerror("glp_rmfgen: a_cap = %d; invalid offset\n", a_cap);
      }
      seed = parm[1];
      a = parm[2];
      b = parm[3];
      c1 = parm[4];
      c2 = parm[5];
      if (!(seed > 0 && 1 <= a && a <= 1000 && 1 <= b && b <= 1000 &&
            0 <= c1 && c1 <= c2 && c2 <= 1000))
      {  ret = 1;
         goto done;
      }
      if (G != NULL)
      {  glp_erase_graph(G, G->v_size, G->a_size);
         glp_set_graph_name(G, "RMFGEN");
      }
      csa->rand = rng_create_rand();
      rng_init_rand(csa->rand, seed);
      n = gen_rmf(csa, a, b, c1, c2);
      sprintf(comm[0], "This file was generated by genrmf.");
      sprintf(comm[1], "The parameters are: a: %d b: %d c1: %d c2: %d",
         a, b, c1, c2);
      com1[0] = comm[0];
      com1[1] = comm[1];
      print_max_format(csa, n, com1, 2);
      gen_free_net(n);
      rng_delete_rand(csa->rand);
      ret = 0;
done: return ret;
}

/**********************************************************************/

#if 0
int main(int argc, char *argv[])
{     int seed, a, b, c1, c2, i, parm[1+5];
      seed = 123;
      a = b = c1 = c2 = -1;
      for (i = 1; i < argc; i++)
      {  if (strcmp(argv[i], "-seed") == 0)
            seed = atoi(argv[++i]);
         else if (strcmp(argv[i], "-a") == 0)
            a = atoi(argv[++i]);
         else if (strcmp(argv[i], "-b") == 0)
            b = atoi(argv[++i]);
         else if (strcmp(argv[i], "-c1") == 0)
            c1 = atoi(argv[++i]);
         else if (strcmp(argv[i], "-c2") == 0)
            c2 = atoi(argv[++i]);
      }
      if (a < 0 || b < 0 || c1 < 0 || c2 < 0)
      {  xprintf("Usage:\n");
         xprintf("genrmf [-seed seed] -a frame_size -b depth\n");
         xprintf("        -c1 cap_range1 -c2 cap_range2\n");
      }
      else
      {  parm[1] = seed;
         parm[2] = a;
         parm[3] = b;
         parm[4] = c1;
         parm[5] = c2;
         glp_rmfgen(NULL, NULL, NULL, 0, parm);
      }
      return 0;
}
#endif

/* eof */