summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--algos.c42
1 files changed, 27 insertions, 15 deletions
diff --git a/algos.c b/algos.c
index 34a1e15..fdf7243 100644
--- a/algos.c
+++ b/algos.c
@@ -13,7 +13,7 @@
* algorithme même en n^3 ou n^4 est acceptable (ou pas...)
*/
-void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
+void color_subgraph_aux(const graph g, int *colors, int *v, int *nneigh, const int n) {
int i, j, t;
if (n == 0) return;
@@ -24,15 +24,9 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
}
// Find element with smallest neighbours count
- int x = -1, m = n + 1;
- for (i = 0; i < n; i++) {
- t = 0;
- for (j = 0; j < n; j++) {
- if (set_mem(v[j], graph_neighbours(g, v[i]))) t++;
- }
- if (t < m) {
- x = i; m = t;
- }
+ int x = 0;
+ for (i = 1; i < n; i++) {
+ if (nneigh[i] < nneigh[x]) x = i;
}
// Put that element at the beginning of vector v, so that the remaining subgraph is defined by v[1..]
@@ -40,10 +34,19 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
t = v[x];
v[x] = v[0];
v[0] = t;
+
+ t = nneigh[x];
+ nneigh[x] = nneigh[0];
+ nneigh[0] = t;
+ }
+
+ // update nneigh
+ for (i = 1; i < n; i++) {
+ if (set_mem(v[i], graph_neighbours(g, v[0]))) nneigh[i]--;
}
// Color remaining subgraph (v[1..])
- color_subgraph_aux(g, colors + 1, v + 1, n - 1);
+ color_subgraph_aux(g, colors + 1, v + 1, nneigh + 1, n - 1);
// Find free color
colors[0] = -1;
@@ -63,12 +66,12 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
}
int color_subgraph(const graph g, set s, int dump_colors) {
- int i, m;
+ int i, j, m;
const int n = set_size(s);
if (n == 0) return 0;
- int colors[n], vertices[n];
+ int colors[n], vertices[n], nneigh[n];
for (i = 0; i < n; i++)
colors[i] = -1;
@@ -83,8 +86,17 @@ int color_subgraph(const graph g, set s, int dump_colors) {
}
assert(i == n);
+ // Calculate neighbour count for all nodes
+ for (i = 0; i < n; i++) nneigh[i] = 0;
+ for (i = 0; i < n; i++) {
+ for (j = 0; j < n; j++) {
+ if (set_mem(vertices[i], graph_neighbours(g, vertices[j])))
+ nneigh[i]++;
+ }
+ }
+
// Color graph
- color_subgraph_aux(g, colors, vertices, n);
+ color_subgraph_aux(g, colors, vertices, nneigh, n);
// Count colors
m = -1;
@@ -190,7 +202,7 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc, int prev_size) {
// If we have no possibility to explore, return
if (is_set_empty(c)) return;
- if (set_size(c) <= prev_size / 2 && set_size(c) >= g->N / 10) {
+ if (set_size(c) <= prev_size / 2 && set_size(c) >= g->N / 20) {
prev_size = set_size(c);
// Color graph : we may have no possibility
set c_copy = copy_set(c);