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