1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi18.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,122 @@
1.4 +/* glpapi18.c (maximum clique problem) */
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 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 +static void set_edge(int nv, unsigned char a[], int i, int j)
1.32 +{ int k;
1.33 + xassert(1 <= j && j < i && i <= nv);
1.34 + k = ((i - 1) * (i - 2)) / 2 + (j - 1);
1.35 + a[k / CHAR_BIT] |=
1.36 + (unsigned char)(1 << ((CHAR_BIT - 1) - k % CHAR_BIT));
1.37 + return;
1.38 +}
1.39 +
1.40 +int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol, int v_set)
1.41 +{ /* find maximum weight clique with exact algorithm */
1.42 + glp_arc *e;
1.43 + int i, j, k, len, x, *w, *ind, ret = 0;
1.44 + unsigned char *a;
1.45 + double s, t;
1.46 + if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
1.47 + xerror("glp_wclique_exact: v_wgt = %d; invalid parameter\n",
1.48 + v_wgt);
1.49 + if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
1.50 + xerror("glp_wclique_exact: v_set = %d; invalid parameter\n",
1.51 + v_set);
1.52 + if (G->nv == 0)
1.53 + { /* empty graph has only empty clique */
1.54 + if (sol != NULL) *sol = 0.0;
1.55 + return 0;
1.56 + }
1.57 + /* allocate working arrays */
1.58 + w = xcalloc(1+G->nv, sizeof(int));
1.59 + ind = xcalloc(1+G->nv, sizeof(int));
1.60 + len = G->nv; /* # vertices */
1.61 + len = len * (len - 1) / 2; /* # entries in lower triangle */
1.62 + len = (len + (CHAR_BIT - 1)) / CHAR_BIT; /* # bytes needed */
1.63 + a = xcalloc(len, sizeof(char));
1.64 + memset(a, 0, len * sizeof(char));
1.65 + /* determine vertex weights */
1.66 + s = 0.0;
1.67 + for (i = 1; i <= G->nv; i++)
1.68 + { if (v_wgt >= 0)
1.69 + { memcpy(&t, (char *)G->v[i]->data + v_wgt, sizeof(double));
1.70 + if (!(0.0 <= t && t <= (double)INT_MAX && t == floor(t)))
1.71 + { ret = GLP_EDATA;
1.72 + goto done;
1.73 + }
1.74 + w[i] = (int)t;
1.75 + }
1.76 + else
1.77 + w[i] = 1;
1.78 + s += (double)w[i];
1.79 + }
1.80 + if (s > (double)INT_MAX)
1.81 + { ret = GLP_EDATA;
1.82 + goto done;
1.83 + }
1.84 + /* build the adjacency matrix */
1.85 + for (i = 1; i <= G->nv; i++)
1.86 + { for (e = G->v[i]->in; e != NULL; e = e->h_next)
1.87 + { j = e->tail->i;
1.88 + /* there exists edge (j,i) in the graph */
1.89 + if (i > j) set_edge(G->nv, a, i, j);
1.90 + }
1.91 + for (e = G->v[i]->out; e != NULL; e = e->t_next)
1.92 + { j = e->head->i;
1.93 + /* there exists edge (i,j) in the graph */
1.94 + if (i > j) set_edge(G->nv, a, i, j);
1.95 + }
1.96 + }
1.97 + /* find maximum weight clique in the graph */
1.98 + len = wclique(G->nv, w, a, ind);
1.99 + /* compute the clique weight */
1.100 + s = 0.0;
1.101 + for (k = 1; k <= len; k++)
1.102 + { i = ind[k];
1.103 + xassert(1 <= i && i <= G->nv);
1.104 + s += (double)w[i];
1.105 + }
1.106 + if (sol != NULL) *sol = s;
1.107 + /* mark vertices included in the clique */
1.108 + if (v_set >= 0)
1.109 + { x = 0;
1.110 + for (i = 1; i <= G->nv; i++)
1.111 + memcpy((char *)G->v[i]->data + v_set, &x, sizeof(int));
1.112 + x = 1;
1.113 + for (k = 1; k <= len; k++)
1.114 + { i = ind[k];
1.115 + memcpy((char *)G->v[i]->data + v_set, &x, sizeof(int));
1.116 + }
1.117 + }
1.118 +done: /* free working arrays */
1.119 + xfree(w);
1.120 + xfree(ind);
1.121 + xfree(a);
1.122 + return ret;
1.123 +}
1.124 +
1.125 +/* eof */