alpar@9: /* glpnet09.c */ alpar@9: alpar@9: /*********************************************************************** alpar@9: * This code is part of GLPK (GNU Linear Programming Kit). alpar@9: * alpar@9: * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, alpar@9: * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, alpar@9: * Moscow Aviation Institute, Moscow, Russia. All rights reserved. alpar@9: * E-mail: . alpar@9: * alpar@9: * GLPK is free software: you can redistribute it and/or modify it alpar@9: * under the terms of the GNU General Public License as published by alpar@9: * the Free Software Foundation, either version 3 of the License, or alpar@9: * (at your option) any later version. alpar@9: * alpar@9: * GLPK is distributed in the hope that it will be useful, but WITHOUT alpar@9: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY alpar@9: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public alpar@9: * License for more details. alpar@9: * alpar@9: * You should have received a copy of the GNU General Public License alpar@9: * along with GLPK. If not, see . alpar@9: ***********************************************************************/ alpar@9: alpar@9: #include "glpapi.h" alpar@9: #include "glpnet.h" alpar@9: alpar@9: /*********************************************************************** alpar@9: * NAME alpar@9: * alpar@9: * kellerman - cover edges by cliques with Kellerman's heuristic alpar@9: * alpar@9: * SYNOPSIS alpar@9: * alpar@9: * #include "glpnet.h" alpar@9: * int kellerman(int n, int (*func)(void *info, int i, int ind[]), alpar@9: * void *info, glp_graph *H); alpar@9: * alpar@9: * DESCRIPTION alpar@9: * alpar@9: * The routine kellerman implements Kellerman's heuristic algorithm alpar@9: * to find a minimal set of cliques which cover all edges of specified alpar@9: * graph G = (V, E). alpar@9: * alpar@9: * The parameter n specifies the number of vertices |V|, n >= 0. alpar@9: * alpar@9: * Formal routine func specifies the set of edges E in the following alpar@9: * way. Running the routine kellerman calls the routine func and passes alpar@9: * to it parameter i, which is the number of some vertex, 1 <= i <= n. alpar@9: * In response the routine func should store numbers of all vertices alpar@9: * adjacent to vertex i to locations ind[1], ind[2], ..., ind[len] and alpar@9: * return the value of len, which is the number of adjacent vertices, alpar@9: * 0 <= len <= n. Self-loops are allowed, but ignored. Multiple edges alpar@9: * are not allowed. alpar@9: * alpar@9: * The parameter info is a transit pointer (magic cookie) passed to the alpar@9: * formal routine func as its first parameter. alpar@9: * alpar@9: * The result provided by the routine kellerman is the bipartite graph alpar@9: * H = (V union C, F), which defines the covering found. (The program alpar@9: * object of type glp_graph specified by the parameter H should be alpar@9: * previously created with the routine glp_create_graph. On entry the alpar@9: * routine kellerman erases the content of this object with the routine alpar@9: * glp_erase_graph.) Vertices of first part V correspond to vertices of alpar@9: * the graph G and have the same ordinal numbers 1, 2, ..., n. Vertices alpar@9: * of second part C correspond to cliques and have ordinal numbers alpar@9: * n+1, n+2, ..., n+k, where k is the total number of cliques in the alpar@9: * edge covering found. Every edge f in F in the program object H is alpar@9: * represented as arc f = (i->j), where i in V and j in C, which means alpar@9: * that vertex i of the graph G is in clique C[j], 1 <= j <= k. (Thus, alpar@9: * if two vertices of the graph G are in the same clique, these vertices alpar@9: * are adjacent in G, and corresponding edge is covered by that clique.) alpar@9: * alpar@9: * RETURNS alpar@9: * alpar@9: * The routine Kellerman returns k, the total number of cliques in the alpar@9: * edge covering found. alpar@9: * alpar@9: * REFERENCE alpar@9: * alpar@9: * For more details see: glpk/doc/notes/keller.pdf (in Russian). */ alpar@9: alpar@9: struct set alpar@9: { /* set of vertices */ alpar@9: int size; alpar@9: /* size (cardinality) of the set, 0 <= card <= n */ alpar@9: int *list; /* int list[1+n]; */ alpar@9: /* the set contains vertices list[1,...,size] */ alpar@9: int *pos; /* int pos[1+n]; */ alpar@9: /* pos[i] > 0 means that vertex i is in the set and alpar@9: list[pos[i]] = i; pos[i] = 0 means that vertex i is not in alpar@9: the set */ alpar@9: }; alpar@9: alpar@9: int kellerman(int n, int (*func)(void *info, int i, int ind[]), alpar@9: void *info, void /* glp_graph */ *H_) alpar@9: { glp_graph *H = H_; alpar@9: struct set W_, *W = &W_, V_, *V = &V_; alpar@9: glp_arc *a; alpar@9: int i, j, k, m, t, len, card, best; alpar@9: xassert(n >= 0); alpar@9: /* H := (V, 0; 0), where V is the set of vertices of graph G */ alpar@9: glp_erase_graph(H, H->v_size, H->a_size); alpar@9: glp_add_vertices(H, n); alpar@9: /* W := 0 */ alpar@9: W->size = 0; alpar@9: W->list = xcalloc(1+n, sizeof(int)); alpar@9: W->pos = xcalloc(1+n, sizeof(int)); alpar@9: memset(&W->pos[1], 0, sizeof(int) * n); alpar@9: /* V := 0 */ alpar@9: V->size = 0; alpar@9: V->list = xcalloc(1+n, sizeof(int)); alpar@9: V->pos = xcalloc(1+n, sizeof(int)); alpar@9: memset(&V->pos[1], 0, sizeof(int) * n); alpar@9: /* main loop */ alpar@9: for (i = 1; i <= n; i++) alpar@9: { /* W must be empty */ alpar@9: xassert(W->size == 0); alpar@9: /* W := { j : i > j and (i,j) in E } */ alpar@9: len = func(info, i, W->list); alpar@9: xassert(0 <= len && len <= n); alpar@9: for (t = 1; t <= len; t++) alpar@9: { j = W->list[t]; alpar@9: xassert(1 <= j && j <= n); alpar@9: if (j >= i) continue; alpar@9: xassert(W->pos[j] == 0); alpar@9: W->list[++W->size] = j, W->pos[j] = W->size; alpar@9: } alpar@9: /* on i-th iteration we need to cover edges (i,j) for all alpar@9: j in W */ alpar@9: /* if W is empty, it is a special case */ alpar@9: if (W->size == 0) alpar@9: { /* set k := k + 1 and create new clique C[k] = { i } */ alpar@9: k = glp_add_vertices(H, 1) - n; alpar@9: glp_add_arc(H, i, n + k); alpar@9: continue; alpar@9: } alpar@9: /* try to include vertex i into existing cliques */ alpar@9: /* V must be empty */ alpar@9: xassert(V->size == 0); alpar@9: /* k is the number of cliques found so far */ alpar@9: k = H->nv - n; alpar@9: for (m = 1; m <= k; m++) alpar@9: { /* do while V != W; since here V is within W, we can use alpar@9: equivalent condition: do while |V| < |W| */ alpar@9: if (V->size == W->size) break; alpar@9: /* check if C[m] is within W */ alpar@9: for (a = H->v[n + m]->in; a != NULL; a = a->h_next) alpar@9: { j = a->tail->i; alpar@9: if (W->pos[j] == 0) break; alpar@9: } alpar@9: if (a != NULL) continue; alpar@9: /* C[m] is within W, expand clique C[m] with vertex i */ alpar@9: /* C[m] := C[m] union {i} */ alpar@9: glp_add_arc(H, i, n + m); alpar@9: /* V is a set of vertices whose incident edges are already alpar@9: covered by existing cliques */ alpar@9: /* V := V union C[m] */ alpar@9: for (a = H->v[n + m]->in; a != NULL; a = a->h_next) alpar@9: { j = a->tail->i; alpar@9: if (V->pos[j] == 0) alpar@9: V->list[++V->size] = j, V->pos[j] = V->size; alpar@9: } alpar@9: } alpar@9: /* remove from set W the vertices whose incident edges are alpar@9: already covered by existing cliques */ alpar@9: /* W := W \ V, V := 0 */ alpar@9: for (t = 1; t <= V->size; t++) alpar@9: { j = V->list[t], V->pos[j] = 0; alpar@9: if (W->pos[j] != 0) alpar@9: { /* remove vertex j from W */ alpar@9: if (W->pos[j] != W->size) alpar@9: { int jj = W->list[W->size]; alpar@9: W->list[W->pos[j]] = jj; alpar@9: W->pos[jj] = W->pos[j]; alpar@9: } alpar@9: W->size--, W->pos[j] = 0; alpar@9: } alpar@9: } alpar@9: V->size = 0; alpar@9: /* now set W contains only vertices whose incident edges are alpar@9: still not covered by existing cliques; create new cliques alpar@9: to cover remaining edges until set W becomes empty */ alpar@9: while (W->size > 0) alpar@9: { /* find clique C[m], 1 <= m <= k, which shares maximal alpar@9: number of vertices with W; to break ties choose clique alpar@9: having smallest number m */ alpar@9: m = 0, best = -1; alpar@9: k = H->nv - n; alpar@9: for (t = 1; t <= k; t++) alpar@9: { /* compute cardinality of intersection of W and C[t] */ alpar@9: card = 0; alpar@9: for (a = H->v[n + t]->in; a != NULL; a = a->h_next) alpar@9: { j = a->tail->i; alpar@9: if (W->pos[j] != 0) card++; alpar@9: } alpar@9: if (best < card) alpar@9: m = t, best = card; alpar@9: } alpar@9: xassert(m > 0); alpar@9: /* set k := k + 1 and create new clique: alpar@9: C[k] := (W intersect C[m]) union { i }, which covers all alpar@9: edges incident to vertices from (W intersect C[m]) */ alpar@9: k = glp_add_vertices(H, 1) - n; alpar@9: for (a = H->v[n + m]->in; a != NULL; a = a->h_next) alpar@9: { j = a->tail->i; alpar@9: if (W->pos[j] != 0) alpar@9: { /* vertex j is in both W and C[m]; include it in new alpar@9: clique C[k] */ alpar@9: glp_add_arc(H, j, n + k); alpar@9: /* remove vertex j from W, since edge (i,j) will be alpar@9: covered by new clique C[k] */ alpar@9: if (W->pos[j] != W->size) alpar@9: { int jj = W->list[W->size]; alpar@9: W->list[W->pos[j]] = jj; alpar@9: W->pos[jj] = W->pos[j]; alpar@9: } alpar@9: W->size--, W->pos[j] = 0; alpar@9: } alpar@9: } alpar@9: /* include vertex i to new clique C[k] to cover edges (i,j) alpar@9: incident to all vertices j just removed from W */ alpar@9: glp_add_arc(H, i, n + k); alpar@9: } alpar@9: } alpar@9: /* free working arrays */ alpar@9: xfree(W->list); alpar@9: xfree(W->pos); alpar@9: xfree(V->list); alpar@9: xfree(V->pos); alpar@9: /* return the number of cliques in the edge covering found */ alpar@9: return H->nv - n; alpar@9: } alpar@9: alpar@9: /* eof */