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