1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpnet09.c	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,235 @@
     1.4 +/* glpnet09.c */
     1.5 +
     1.6 +/***********************************************************************
     1.7 +*  This code is part of GLPK (GNU Linear Programming Kit).
     1.8 +*
     1.9 +*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
    1.10 +*  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
    1.11 +*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.12 +*  E-mail: <mao@gnu.org>.
    1.13 +*
    1.14 +*  GLPK is free software: you can redistribute it and/or modify it
    1.15 +*  under the terms of the GNU General Public License as published by
    1.16 +*  the Free Software Foundation, either version 3 of the License, or
    1.17 +*  (at your option) any later version.
    1.18 +*
    1.19 +*  GLPK is distributed in the hope that it will be useful, but WITHOUT
    1.20 +*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.21 +*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
    1.22 +*  License for more details.
    1.23 +*
    1.24 +*  You should have received a copy of the GNU General Public License
    1.25 +*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
    1.26 +***********************************************************************/
    1.27 +
    1.28 +#include "glpapi.h"
    1.29 +#include "glpnet.h"
    1.30 +
    1.31 +/***********************************************************************
    1.32 +*  NAME
    1.33 +*
    1.34 +*  kellerman - cover edges by cliques with Kellerman's heuristic
    1.35 +*
    1.36 +*  SYNOPSIS
    1.37 +*
    1.38 +*  #include "glpnet.h"
    1.39 +*  int kellerman(int n, int (*func)(void *info, int i, int ind[]),
    1.40 +*     void *info, glp_graph *H);
    1.41 +*
    1.42 +*  DESCRIPTION
    1.43 +*
    1.44 +*  The routine kellerman implements Kellerman's heuristic algorithm
    1.45 +*  to find a minimal set of cliques which cover all edges of specified
    1.46 +*  graph G = (V, E).
    1.47 +*
    1.48 +*  The parameter n specifies the number of vertices |V|, n >= 0.
    1.49 +*
    1.50 +*  Formal routine func specifies the set of edges E in the following
    1.51 +*  way. Running the routine kellerman calls the routine func and passes
    1.52 +*  to it parameter i, which is the number of some vertex, 1 <= i <= n.
    1.53 +*  In response the routine func should store numbers of all vertices
    1.54 +*  adjacent to vertex i to locations ind[1], ind[2], ..., ind[len] and
    1.55 +*  return the value of len, which is the number of adjacent vertices,
    1.56 +*  0 <= len <= n. Self-loops are allowed, but ignored. Multiple edges
    1.57 +*  are not allowed.
    1.58 +*
    1.59 +*  The parameter info is a transit pointer (magic cookie) passed to the
    1.60 +*  formal routine func as its first parameter.
    1.61 +*
    1.62 +*  The result provided by the routine kellerman is the bipartite graph
    1.63 +*  H = (V union C, F), which defines the covering found. (The program
    1.64 +*  object of type glp_graph specified by the parameter H should be
    1.65 +*  previously created with the routine glp_create_graph. On entry the
    1.66 +*  routine kellerman erases the content of this object with the routine
    1.67 +*  glp_erase_graph.) Vertices of first part V correspond to vertices of
    1.68 +*  the graph G and have the same ordinal numbers 1, 2, ..., n. Vertices
    1.69 +*  of second part C correspond to cliques and have ordinal numbers
    1.70 +*  n+1, n+2, ..., n+k, where k is the total number of cliques in the
    1.71 +*  edge covering found. Every edge f in F in the program object H is
    1.72 +*  represented as arc f = (i->j), where i in V and j in C, which means
    1.73 +*  that vertex i of the graph G is in clique C[j], 1 <= j <= k. (Thus,
    1.74 +*  if two vertices of the graph G are in the same clique, these vertices
    1.75 +*  are adjacent in G, and corresponding edge is covered by that clique.)
    1.76 +*
    1.77 +*  RETURNS
    1.78 +*
    1.79 +*  The routine Kellerman returns k, the total number of cliques in the
    1.80 +*  edge covering found.
    1.81 +*
    1.82 +*  REFERENCE
    1.83 +*
    1.84 +*  For more details see: glpk/doc/notes/keller.pdf (in Russian). */
    1.85 +
    1.86 +struct set
    1.87 +{     /* set of vertices */
    1.88 +      int size;
    1.89 +      /* size (cardinality) of the set, 0 <= card <= n */
    1.90 +      int *list; /* int list[1+n]; */
    1.91 +      /* the set contains vertices list[1,...,size] */
    1.92 +      int *pos; /* int pos[1+n]; */
    1.93 +      /* pos[i] > 0 means that vertex i is in the set and
    1.94 +         list[pos[i]] = i; pos[i] = 0 means that vertex i is not in
    1.95 +         the set */
    1.96 +};
    1.97 +
    1.98 +int kellerman(int n, int (*func)(void *info, int i, int ind[]),
    1.99 +      void *info, void /* glp_graph */ *H_)
   1.100 +{     glp_graph *H = H_;
   1.101 +      struct set W_, *W = &W_, V_, *V = &V_;
   1.102 +      glp_arc *a;
   1.103 +      int i, j, k, m, t, len, card, best;
   1.104 +      xassert(n >= 0);
   1.105 +      /* H := (V, 0; 0), where V is the set of vertices of graph G */
   1.106 +      glp_erase_graph(H, H->v_size, H->a_size);
   1.107 +      glp_add_vertices(H, n);
   1.108 +      /* W := 0 */
   1.109 +      W->size = 0;
   1.110 +      W->list = xcalloc(1+n, sizeof(int));
   1.111 +      W->pos = xcalloc(1+n, sizeof(int));
   1.112 +      memset(&W->pos[1], 0, sizeof(int) * n);
   1.113 +      /* V := 0 */
   1.114 +      V->size = 0;
   1.115 +      V->list = xcalloc(1+n, sizeof(int));
   1.116 +      V->pos = xcalloc(1+n, sizeof(int));
   1.117 +      memset(&V->pos[1], 0, sizeof(int) * n);
   1.118 +      /* main loop */
   1.119 +      for (i = 1; i <= n; i++)
   1.120 +      {  /* W must be empty */
   1.121 +         xassert(W->size == 0);
   1.122 +         /* W := { j : i > j and (i,j) in E } */
   1.123 +         len = func(info, i, W->list);
   1.124 +         xassert(0 <= len && len <= n);
   1.125 +         for (t = 1; t <= len; t++)
   1.126 +         {  j = W->list[t];
   1.127 +            xassert(1 <= j && j <= n);
   1.128 +            if (j >= i) continue;
   1.129 +            xassert(W->pos[j] == 0);
   1.130 +            W->list[++W->size] = j, W->pos[j] = W->size;
   1.131 +         }
   1.132 +         /* on i-th iteration we need to cover edges (i,j) for all
   1.133 +            j in W */
   1.134 +         /* if W is empty, it is a special case */
   1.135 +         if (W->size == 0)
   1.136 +         {  /* set k := k + 1 and create new clique C[k] = { i } */
   1.137 +            k = glp_add_vertices(H, 1) - n;
   1.138 +            glp_add_arc(H, i, n + k);
   1.139 +            continue;
   1.140 +         }
   1.141 +         /* try to include vertex i into existing cliques */
   1.142 +         /* V must be empty */
   1.143 +         xassert(V->size == 0);
   1.144 +         /* k is the number of cliques found so far */
   1.145 +         k = H->nv - n;
   1.146 +         for (m = 1; m <= k; m++)
   1.147 +         {  /* do while V != W; since here V is within W, we can use
   1.148 +               equivalent condition: do while |V| < |W| */
   1.149 +            if (V->size == W->size) break;
   1.150 +            /* check if C[m] is within W */
   1.151 +            for (a = H->v[n + m]->in; a != NULL; a = a->h_next)
   1.152 +            {  j = a->tail->i;
   1.153 +               if (W->pos[j] == 0) break;
   1.154 +            }
   1.155 +            if (a != NULL) continue;
   1.156 +            /* C[m] is within W, expand clique C[m] with vertex i */
   1.157 +            /* C[m] := C[m] union {i} */
   1.158 +            glp_add_arc(H, i, n + m);
   1.159 +            /* V is a set of vertices whose incident edges are already
   1.160 +               covered by existing cliques */
   1.161 +            /* V := V union C[m] */
   1.162 +            for (a = H->v[n + m]->in; a != NULL; a = a->h_next)
   1.163 +            {  j = a->tail->i;
   1.164 +               if (V->pos[j] == 0)
   1.165 +                  V->list[++V->size] = j, V->pos[j] = V->size;
   1.166 +            }
   1.167 +         }
   1.168 +         /* remove from set W the vertices whose incident edges are
   1.169 +            already covered by existing cliques */
   1.170 +         /* W := W \ V, V := 0 */
   1.171 +         for (t = 1; t <= V->size; t++)
   1.172 +         {  j = V->list[t], V->pos[j] = 0;
   1.173 +            if (W->pos[j] != 0)
   1.174 +            {  /* remove vertex j from W */
   1.175 +               if (W->pos[j] != W->size)
   1.176 +               {  int jj = W->list[W->size];
   1.177 +                  W->list[W->pos[j]] = jj;
   1.178 +                  W->pos[jj] = W->pos[j];
   1.179 +               }
   1.180 +               W->size--, W->pos[j] = 0;
   1.181 +            }
   1.182 +         }
   1.183 +         V->size = 0;
   1.184 +         /* now set W contains only vertices whose incident edges are
   1.185 +            still not covered by existing cliques; create new cliques
   1.186 +            to cover remaining edges until set W becomes empty */
   1.187 +         while (W->size > 0)
   1.188 +         {  /* find clique C[m], 1 <= m <= k, which shares maximal
   1.189 +               number of vertices with W; to break ties choose clique
   1.190 +               having smallest number m */
   1.191 +            m = 0, best = -1;
   1.192 +            k = H->nv - n;
   1.193 +            for (t = 1; t <= k; t++)
   1.194 +            {  /* compute cardinality of intersection of W and C[t] */
   1.195 +               card = 0;
   1.196 +               for (a = H->v[n + t]->in; a != NULL; a = a->h_next)
   1.197 +               {  j = a->tail->i;
   1.198 +                  if (W->pos[j] != 0) card++;
   1.199 +               }
   1.200 +               if (best < card)
   1.201 +                  m = t, best = card;
   1.202 +            }
   1.203 +            xassert(m > 0);
   1.204 +            /* set k := k + 1 and create new clique:
   1.205 +               C[k] := (W intersect C[m]) union { i }, which covers all
   1.206 +               edges incident to vertices from (W intersect C[m]) */
   1.207 +            k = glp_add_vertices(H, 1) - n;
   1.208 +            for (a = H->v[n + m]->in; a != NULL; a = a->h_next)
   1.209 +            {  j = a->tail->i;
   1.210 +               if (W->pos[j] != 0)
   1.211 +               {  /* vertex j is in both W and C[m]; include it in new
   1.212 +                     clique C[k] */
   1.213 +                  glp_add_arc(H, j, n + k);
   1.214 +                  /* remove vertex j from W, since edge (i,j) will be
   1.215 +                     covered by new clique C[k] */
   1.216 +                  if (W->pos[j] != W->size)
   1.217 +                  {  int jj = W->list[W->size];
   1.218 +                     W->list[W->pos[j]] = jj;
   1.219 +                     W->pos[jj] = W->pos[j];
   1.220 +                  }
   1.221 +                  W->size--, W->pos[j] = 0;
   1.222 +               }
   1.223 +            }
   1.224 +            /* include vertex i to new clique C[k] to cover edges (i,j)
   1.225 +               incident to all vertices j just removed from W */
   1.226 +            glp_add_arc(H, i, n + k);
   1.227 +         }
   1.228 +      }
   1.229 +      /* free working arrays */
   1.230 +      xfree(W->list);
   1.231 +      xfree(W->pos);
   1.232 +      xfree(V->list);
   1.233 +      xfree(V->pos);
   1.234 +      /* return the number of cliques in the edge covering found */
   1.235 +      return H->nv - n;
   1.236 +}
   1.237 +
   1.238 +/* eof */