COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpnet09.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 14 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 9.2 KB
Line 
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
83struct 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
95int 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 */
Note: See TracBrowser for help on using the repository browser.