lemon-project-template-glpk

annotate deps/glpk/src/glpapi18.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpapi18.c (maximum clique problem) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #include "glpapi.h"
alpar@9 26 #include "glpnet.h"
alpar@9 27
alpar@9 28 static void set_edge(int nv, unsigned char a[], int i, int j)
alpar@9 29 { int k;
alpar@9 30 xassert(1 <= j && j < i && i <= nv);
alpar@9 31 k = ((i - 1) * (i - 2)) / 2 + (j - 1);
alpar@9 32 a[k / CHAR_BIT] |=
alpar@9 33 (unsigned char)(1 << ((CHAR_BIT - 1) - k % CHAR_BIT));
alpar@9 34 return;
alpar@9 35 }
alpar@9 36
alpar@9 37 int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol, int v_set)
alpar@9 38 { /* find maximum weight clique with exact algorithm */
alpar@9 39 glp_arc *e;
alpar@9 40 int i, j, k, len, x, *w, *ind, ret = 0;
alpar@9 41 unsigned char *a;
alpar@9 42 double s, t;
alpar@9 43 if (v_wgt >= 0 && v_wgt > G->v_size - (int)sizeof(double))
alpar@9 44 xerror("glp_wclique_exact: v_wgt = %d; invalid parameter\n",
alpar@9 45 v_wgt);
alpar@9 46 if (v_set >= 0 && v_set > G->v_size - (int)sizeof(int))
alpar@9 47 xerror("glp_wclique_exact: v_set = %d; invalid parameter\n",
alpar@9 48 v_set);
alpar@9 49 if (G->nv == 0)
alpar@9 50 { /* empty graph has only empty clique */
alpar@9 51 if (sol != NULL) *sol = 0.0;
alpar@9 52 return 0;
alpar@9 53 }
alpar@9 54 /* allocate working arrays */
alpar@9 55 w = xcalloc(1+G->nv, sizeof(int));
alpar@9 56 ind = xcalloc(1+G->nv, sizeof(int));
alpar@9 57 len = G->nv; /* # vertices */
alpar@9 58 len = len * (len - 1) / 2; /* # entries in lower triangle */
alpar@9 59 len = (len + (CHAR_BIT - 1)) / CHAR_BIT; /* # bytes needed */
alpar@9 60 a = xcalloc(len, sizeof(char));
alpar@9 61 memset(a, 0, len * sizeof(char));
alpar@9 62 /* determine vertex weights */
alpar@9 63 s = 0.0;
alpar@9 64 for (i = 1; i <= G->nv; i++)
alpar@9 65 { if (v_wgt >= 0)
alpar@9 66 { memcpy(&t, (char *)G->v[i]->data + v_wgt, sizeof(double));
alpar@9 67 if (!(0.0 <= t && t <= (double)INT_MAX && t == floor(t)))
alpar@9 68 { ret = GLP_EDATA;
alpar@9 69 goto done;
alpar@9 70 }
alpar@9 71 w[i] = (int)t;
alpar@9 72 }
alpar@9 73 else
alpar@9 74 w[i] = 1;
alpar@9 75 s += (double)w[i];
alpar@9 76 }
alpar@9 77 if (s > (double)INT_MAX)
alpar@9 78 { ret = GLP_EDATA;
alpar@9 79 goto done;
alpar@9 80 }
alpar@9 81 /* build the adjacency matrix */
alpar@9 82 for (i = 1; i <= G->nv; i++)
alpar@9 83 { for (e = G->v[i]->in; e != NULL; e = e->h_next)
alpar@9 84 { j = e->tail->i;
alpar@9 85 /* there exists edge (j,i) in the graph */
alpar@9 86 if (i > j) set_edge(G->nv, a, i, j);
alpar@9 87 }
alpar@9 88 for (e = G->v[i]->out; e != NULL; e = e->t_next)
alpar@9 89 { j = e->head->i;
alpar@9 90 /* there exists edge (i,j) in the graph */
alpar@9 91 if (i > j) set_edge(G->nv, a, i, j);
alpar@9 92 }
alpar@9 93 }
alpar@9 94 /* find maximum weight clique in the graph */
alpar@9 95 len = wclique(G->nv, w, a, ind);
alpar@9 96 /* compute the clique weight */
alpar@9 97 s = 0.0;
alpar@9 98 for (k = 1; k <= len; k++)
alpar@9 99 { i = ind[k];
alpar@9 100 xassert(1 <= i && i <= G->nv);
alpar@9 101 s += (double)w[i];
alpar@9 102 }
alpar@9 103 if (sol != NULL) *sol = s;
alpar@9 104 /* mark vertices included in the clique */
alpar@9 105 if (v_set >= 0)
alpar@9 106 { x = 0;
alpar@9 107 for (i = 1; i <= G->nv; i++)
alpar@9 108 memcpy((char *)G->v[i]->data + v_set, &x, sizeof(int));
alpar@9 109 x = 1;
alpar@9 110 for (k = 1; k <= len; k++)
alpar@9 111 { i = ind[k];
alpar@9 112 memcpy((char *)G->v[i]->data + v_set, &x, sizeof(int));
alpar@9 113 }
alpar@9 114 }
alpar@9 115 done: /* free working arrays */
alpar@9 116 xfree(w);
alpar@9 117 xfree(ind);
alpar@9 118 xfree(a);
alpar@9 119 return ret;
alpar@9 120 }
alpar@9 121
alpar@9 122 /* eof */