lemon-project-template-glpk
diff deps/glpk/src/glpnet09.c @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
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 */