|
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 |
|
28 static 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 |
|
37 int 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 } |
|
115 done: /* free working arrays */ |
|
116 xfree(w); |
|
117 xfree(ind); |
|
118 xfree(a); |
|
119 return ret; |
|
120 } |
|
121 |
|
122 /* eof */ |