lemon-project-template-glpk

annotate deps/glpk/src/glpnet09.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpnet09.c */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #include "glpapi.h"
alpar@9 26 #include "glpnet.h"
alpar@9 27
alpar@9 28 /***********************************************************************
alpar@9 29 * NAME
alpar@9 30 *
alpar@9 31 * kellerman - cover edges by cliques with Kellerman's heuristic
alpar@9 32 *
alpar@9 33 * SYNOPSIS
alpar@9 34 *
alpar@9 35 * #include "glpnet.h"
alpar@9 36 * int kellerman(int n, int (*func)(void *info, int i, int ind[]),
alpar@9 37 * void *info, glp_graph *H);
alpar@9 38 *
alpar@9 39 * DESCRIPTION
alpar@9 40 *
alpar@9 41 * The routine kellerman implements Kellerman's heuristic algorithm
alpar@9 42 * to find a minimal set of cliques which cover all edges of specified
alpar@9 43 * graph G = (V, E).
alpar@9 44 *
alpar@9 45 * The parameter n specifies the number of vertices |V|, n >= 0.
alpar@9 46 *
alpar@9 47 * Formal routine func specifies the set of edges E in the following
alpar@9 48 * way. Running the routine kellerman calls the routine func and passes
alpar@9 49 * to it parameter i, which is the number of some vertex, 1 <= i <= n.
alpar@9 50 * In response the routine func should store numbers of all vertices
alpar@9 51 * adjacent to vertex i to locations ind[1], ind[2], ..., ind[len] and
alpar@9 52 * return the value of len, which is the number of adjacent vertices,
alpar@9 53 * 0 <= len <= n. Self-loops are allowed, but ignored. Multiple edges
alpar@9 54 * are not allowed.
alpar@9 55 *
alpar@9 56 * The parameter info is a transit pointer (magic cookie) passed to the
alpar@9 57 * formal routine func as its first parameter.
alpar@9 58 *
alpar@9 59 * The result provided by the routine kellerman is the bipartite graph
alpar@9 60 * H = (V union C, F), which defines the covering found. (The program
alpar@9 61 * object of type glp_graph specified by the parameter H should be
alpar@9 62 * previously created with the routine glp_create_graph. On entry the
alpar@9 63 * routine kellerman erases the content of this object with the routine
alpar@9 64 * glp_erase_graph.) Vertices of first part V correspond to vertices of
alpar@9 65 * the graph G and have the same ordinal numbers 1, 2, ..., n. Vertices
alpar@9 66 * of second part C correspond to cliques and have ordinal numbers
alpar@9 67 * n+1, n+2, ..., n+k, where k is the total number of cliques in the
alpar@9 68 * edge covering found. Every edge f in F in the program object H is
alpar@9 69 * represented as arc f = (i->j), where i in V and j in C, which means
alpar@9 70 * that vertex i of the graph G is in clique C[j], 1 <= j <= k. (Thus,
alpar@9 71 * if two vertices of the graph G are in the same clique, these vertices
alpar@9 72 * are adjacent in G, and corresponding edge is covered by that clique.)
alpar@9 73 *
alpar@9 74 * RETURNS
alpar@9 75 *
alpar@9 76 * The routine Kellerman returns k, the total number of cliques in the
alpar@9 77 * edge covering found.
alpar@9 78 *
alpar@9 79 * REFERENCE
alpar@9 80 *
alpar@9 81 * For more details see: glpk/doc/notes/keller.pdf (in Russian). */
alpar@9 82
alpar@9 83 struct set
alpar@9 84 { /* set of vertices */
alpar@9 85 int size;
alpar@9 86 /* size (cardinality) of the set, 0 <= card <= n */
alpar@9 87 int *list; /* int list[1+n]; */
alpar@9 88 /* the set contains vertices list[1,...,size] */
alpar@9 89 int *pos; /* int pos[1+n]; */
alpar@9 90 /* pos[i] > 0 means that vertex i is in the set and
alpar@9 91 list[pos[i]] = i; pos[i] = 0 means that vertex i is not in
alpar@9 92 the set */
alpar@9 93 };
alpar@9 94
alpar@9 95 int kellerman(int n, int (*func)(void *info, int i, int ind[]),
alpar@9 96 void *info, void /* glp_graph */ *H_)
alpar@9 97 { glp_graph *H = H_;
alpar@9 98 struct set W_, *W = &W_, V_, *V = &V_;
alpar@9 99 glp_arc *a;
alpar@9 100 int i, j, k, m, t, len, card, best;
alpar@9 101 xassert(n >= 0);
alpar@9 102 /* H := (V, 0; 0), where V is the set of vertices of graph G */
alpar@9 103 glp_erase_graph(H, H->v_size, H->a_size);
alpar@9 104 glp_add_vertices(H, n);
alpar@9 105 /* W := 0 */
alpar@9 106 W->size = 0;
alpar@9 107 W->list = xcalloc(1+n, sizeof(int));
alpar@9 108 W->pos = xcalloc(1+n, sizeof(int));
alpar@9 109 memset(&W->pos[1], 0, sizeof(int) * n);
alpar@9 110 /* V := 0 */
alpar@9 111 V->size = 0;
alpar@9 112 V->list = xcalloc(1+n, sizeof(int));
alpar@9 113 V->pos = xcalloc(1+n, sizeof(int));
alpar@9 114 memset(&V->pos[1], 0, sizeof(int) * n);
alpar@9 115 /* main loop */
alpar@9 116 for (i = 1; i <= n; i++)
alpar@9 117 { /* W must be empty */
alpar@9 118 xassert(W->size == 0);
alpar@9 119 /* W := { j : i > j and (i,j) in E } */
alpar@9 120 len = func(info, i, W->list);
alpar@9 121 xassert(0 <= len && len <= n);
alpar@9 122 for (t = 1; t <= len; t++)
alpar@9 123 { j = W->list[t];
alpar@9 124 xassert(1 <= j && j <= n);
alpar@9 125 if (j >= i) continue;
alpar@9 126 xassert(W->pos[j] == 0);
alpar@9 127 W->list[++W->size] = j, W->pos[j] = W->size;
alpar@9 128 }
alpar@9 129 /* on i-th iteration we need to cover edges (i,j) for all
alpar@9 130 j in W */
alpar@9 131 /* if W is empty, it is a special case */
alpar@9 132 if (W->size == 0)
alpar@9 133 { /* set k := k + 1 and create new clique C[k] = { i } */
alpar@9 134 k = glp_add_vertices(H, 1) - n;
alpar@9 135 glp_add_arc(H, i, n + k);
alpar@9 136 continue;
alpar@9 137 }
alpar@9 138 /* try to include vertex i into existing cliques */
alpar@9 139 /* V must be empty */
alpar@9 140 xassert(V->size == 0);
alpar@9 141 /* k is the number of cliques found so far */
alpar@9 142 k = H->nv - n;
alpar@9 143 for (m = 1; m <= k; m++)
alpar@9 144 { /* do while V != W; since here V is within W, we can use
alpar@9 145 equivalent condition: do while |V| < |W| */
alpar@9 146 if (V->size == W->size) break;
alpar@9 147 /* check if C[m] is within W */
alpar@9 148 for (a = H->v[n + m]->in; a != NULL; a = a->h_next)
alpar@9 149 { j = a->tail->i;
alpar@9 150 if (W->pos[j] == 0) break;
alpar@9 151 }
alpar@9 152 if (a != NULL) continue;
alpar@9 153 /* C[m] is within W, expand clique C[m] with vertex i */
alpar@9 154 /* C[m] := C[m] union {i} */
alpar@9 155 glp_add_arc(H, i, n + m);
alpar@9 156 /* V is a set of vertices whose incident edges are already
alpar@9 157 covered by existing cliques */
alpar@9 158 /* V := V union C[m] */
alpar@9 159 for (a = H->v[n + m]->in; a != NULL; a = a->h_next)
alpar@9 160 { j = a->tail->i;
alpar@9 161 if (V->pos[j] == 0)
alpar@9 162 V->list[++V->size] = j, V->pos[j] = V->size;
alpar@9 163 }
alpar@9 164 }
alpar@9 165 /* remove from set W the vertices whose incident edges are
alpar@9 166 already covered by existing cliques */
alpar@9 167 /* W := W \ V, V := 0 */
alpar@9 168 for (t = 1; t <= V->size; t++)
alpar@9 169 { j = V->list[t], V->pos[j] = 0;
alpar@9 170 if (W->pos[j] != 0)
alpar@9 171 { /* remove vertex j from W */
alpar@9 172 if (W->pos[j] != W->size)
alpar@9 173 { int jj = W->list[W->size];
alpar@9 174 W->list[W->pos[j]] = jj;
alpar@9 175 W->pos[jj] = W->pos[j];
alpar@9 176 }
alpar@9 177 W->size--, W->pos[j] = 0;
alpar@9 178 }
alpar@9 179 }
alpar@9 180 V->size = 0;
alpar@9 181 /* now set W contains only vertices whose incident edges are
alpar@9 182 still not covered by existing cliques; create new cliques
alpar@9 183 to cover remaining edges until set W becomes empty */
alpar@9 184 while (W->size > 0)
alpar@9 185 { /* find clique C[m], 1 <= m <= k, which shares maximal
alpar@9 186 number of vertices with W; to break ties choose clique
alpar@9 187 having smallest number m */
alpar@9 188 m = 0, best = -1;
alpar@9 189 k = H->nv - n;
alpar@9 190 for (t = 1; t <= k; t++)
alpar@9 191 { /* compute cardinality of intersection of W and C[t] */
alpar@9 192 card = 0;
alpar@9 193 for (a = H->v[n + t]->in; a != NULL; a = a->h_next)
alpar@9 194 { j = a->tail->i;
alpar@9 195 if (W->pos[j] != 0) card++;
alpar@9 196 }
alpar@9 197 if (best < card)
alpar@9 198 m = t, best = card;
alpar@9 199 }
alpar@9 200 xassert(m > 0);
alpar@9 201 /* set k := k + 1 and create new clique:
alpar@9 202 C[k] := (W intersect C[m]) union { i }, which covers all
alpar@9 203 edges incident to vertices from (W intersect C[m]) */
alpar@9 204 k = glp_add_vertices(H, 1) - n;
alpar@9 205 for (a = H->v[n + m]->in; a != NULL; a = a->h_next)
alpar@9 206 { j = a->tail->i;
alpar@9 207 if (W->pos[j] != 0)
alpar@9 208 { /* vertex j is in both W and C[m]; include it in new
alpar@9 209 clique C[k] */
alpar@9 210 glp_add_arc(H, j, n + k);
alpar@9 211 /* remove vertex j from W, since edge (i,j) will be
alpar@9 212 covered by new clique C[k] */
alpar@9 213 if (W->pos[j] != W->size)
alpar@9 214 { int jj = W->list[W->size];
alpar@9 215 W->list[W->pos[j]] = jj;
alpar@9 216 W->pos[jj] = W->pos[j];
alpar@9 217 }
alpar@9 218 W->size--, W->pos[j] = 0;
alpar@9 219 }
alpar@9 220 }
alpar@9 221 /* include vertex i to new clique C[k] to cover edges (i,j)
alpar@9 222 incident to all vertices j just removed from W */
alpar@9 223 glp_add_arc(H, i, n + k);
alpar@9 224 }
alpar@9 225 }
alpar@9 226 /* free working arrays */
alpar@9 227 xfree(W->list);
alpar@9 228 xfree(W->pos);
alpar@9 229 xfree(V->list);
alpar@9 230 xfree(V->pos);
alpar@9 231 /* return the number of cliques in the edge covering found */
alpar@9 232 return H->nv - n;
alpar@9 233 }
alpar@9 234
alpar@9 235 /* eof */