diff options
| -rw-r--r-- | algos.c | 42 |
1 files changed, 27 insertions, 15 deletions
@@ -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); |