1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpnet09.c Mon Dec 06 13:09:21 2010 +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 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 */