COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpapi18.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

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