alpar@1: /* glpapi18.c (maximum clique problem) */
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: <mao@gnu.org>.
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 <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #include "glpapi.h"
alpar@1: #include "glpnet.h"
alpar@1: 
alpar@1: static void set_edge(int nv, unsigned char a[], int i, int j)
alpar@1: {     int k;
alpar@1:       xassert(1 <= j && j < i && i <= nv);
alpar@1:       k = ((i - 1) * (i - 2)) / 2 + (j - 1);
alpar@1:       a[k / CHAR_BIT] |=
alpar@1:          (unsigned char)(1 << ((CHAR_BIT - 1) - k % CHAR_BIT));
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol, int v_set)
alpar@1: {     /* find maximum weight clique with exact algorithm */
alpar@1:       glp_arc *e;
alpar@1:       int i, j, k, len, x, *w, *ind, ret = 0;
alpar@1:       unsigned char *a;
alpar@1:       double s, t;
alpar@1:       if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
alpar@1:          xerror("glp_wclique_exact: v_wgt = %d; invalid parameter\n",
alpar@1:             v_wgt);
alpar@1:       if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
alpar@1:          xerror("glp_wclique_exact: v_set = %d; invalid parameter\n",
alpar@1:             v_set);
alpar@1:       if (G->nv == 0)
alpar@1:       {  /* empty graph has only empty clique */
alpar@1:          if (sol != NULL) *sol = 0.0;
alpar@1:          return 0;
alpar@1:       }
alpar@1:       /* allocate working arrays */
alpar@1:       w = xcalloc(1+G->nv, sizeof(int));
alpar@1:       ind = xcalloc(1+G->nv, sizeof(int));
alpar@1:       len = G->nv; /* # vertices */
alpar@1:       len = len * (len - 1) / 2; /* # entries in lower triangle */
alpar@1:       len = (len + (CHAR_BIT - 1)) / CHAR_BIT; /* # bytes needed */
alpar@1:       a = xcalloc(len, sizeof(char));
alpar@1:       memset(a, 0, len * sizeof(char));
alpar@1:       /* determine vertex weights */
alpar@1:       s = 0.0;
alpar@1:       for (i = 1; i <= G->nv; i++)
alpar@1:       {  if (v_wgt >= 0)
alpar@1:          {  memcpy(&t, (char *)G->v[i]->data + v_wgt, sizeof(double));
alpar@1:             if (!(0.0 <= t && t <= (double)INT_MAX && t == floor(t)))
alpar@1:             {  ret = GLP_EDATA;
alpar@1:                goto done;
alpar@1:             }
alpar@1:             w[i] = (int)t;
alpar@1:          }
alpar@1:          else
alpar@1:             w[i] = 1;
alpar@1:          s += (double)w[i];
alpar@1:       }
alpar@1:       if (s > (double)INT_MAX)
alpar@1:       {  ret = GLP_EDATA;
alpar@1:          goto done;
alpar@1:       }
alpar@1:       /* build the adjacency matrix */
alpar@1:       for (i = 1; i <= G->nv; i++)
alpar@1:       {  for (e = G->v[i]->in; e != NULL; e = e->h_next)
alpar@1:          {  j = e->tail->i;
alpar@1:             /* there exists edge (j,i) in the graph */
alpar@1:             if (i > j) set_edge(G->nv, a, i, j);
alpar@1:          }
alpar@1:          for (e = G->v[i]->out; e != NULL; e = e->t_next)
alpar@1:          {  j = e->head->i;
alpar@1:             /* there exists edge (i,j) in the graph */
alpar@1:             if (i > j) set_edge(G->nv, a, i, j);
alpar@1:          }
alpar@1:       }
alpar@1:       /* find maximum weight clique in the graph */
alpar@1:       len = wclique(G->nv, w, a, ind);
alpar@1:       /* compute the clique weight */
alpar@1:       s = 0.0;
alpar@1:       for (k = 1; k <= len; k++)
alpar@1:       {  i = ind[k];
alpar@1:          xassert(1 <= i && i <= G->nv);
alpar@1:          s += (double)w[i];
alpar@1:       }
alpar@1:       if (sol != NULL) *sol = s;
alpar@1:       /* mark vertices included in the clique */
alpar@1:       if (v_set >= 0)
alpar@1:       {  x = 0;
alpar@1:          for (i = 1; i <= G->nv; i++)
alpar@1:             memcpy((char *)G->v[i]->data + v_set, &x, sizeof(int));
alpar@1:          x = 1;
alpar@1:          for (k = 1; k <= len; k++)
alpar@1:          {  i = ind[k];
alpar@1:             memcpy((char *)G->v[i]->data + v_set, &x, sizeof(int));
alpar@1:          }
alpar@1:       }
alpar@1: done: /* free working arrays */
alpar@1:       xfree(w);
alpar@1:       xfree(ind);
alpar@1:       xfree(a);
alpar@1:       return ret;
alpar@1: }
alpar@1: 
alpar@1: /* eof */