| 253 | } |
| 254 | |
| 255 | forceinline ExecStatus |
| 256 | ConflictGraph::post(void) { |
| 257 | // Find some simple cliques of sizes 2 and 3. |
| 258 | Region reg; |
| 259 | { |
| 260 | // Nodes can be entered twice (for degree 2 and later for degree 1) |
| 261 | Support::StaticStack<int,Region> n(reg,2*nodes()); |
| 262 | // Make a copy of the degree information to be used as weights |
| 263 | // and record all nodes of degree 1 and 2. |
| 264 | for (int i=0; i<nodes(); i++) { |
| 265 | if ((node[i].d == 1) || (node[i].d == 2)) |
| 266 | n.push(i); |
| 267 | } |
| 268 | while (!n.empty()) { |
| 269 | int i = n.pop(); |
| 270 | switch (node[i].d) { |
| 271 | case 0: |
| 272 | // Might happen as the edges have already been removed |
| 273 | break; |
| 274 | case 1: { |
| 275 | Nodes ii(node[i].n); |
| 276 | int j=ii(); |
| 277 | GECODE_ES_CHECK(clique(i,j)); |
| 278 | // Remove edge |
| 279 | edge(i,j,false); |
| 280 | if ((node[j].d == 1) || (node[j].d == 2)) |
| 281 | n.push(j); |
| 282 | break; |
| 283 | } |
| 284 | case 2: { |
| 285 | Nodes ii(node[i].n); |
| 286 | int j=ii(); ++ii; |
| 287 | int k=ii(); |
| 288 | if (adjacent(j,k)) { |
| 289 | GECODE_ES_CHECK(clique(i,j,k)); |
| 290 | // Can the edge j-k still be member of another clique? |
| 291 | if ((node[j].d == 2) || (node[k].d == 2)) |
| 292 | edge(j,k,false); |
| 293 | } else { |
| 294 | GECODE_ES_CHECK(clique(i,j)); |
| 295 | GECODE_ES_CHECK(clique(i,k)); |
| 296 | } |
| 297 | edge(i,j,false); |
| 298 | edge(i,k,false); |
| 299 | if ((node[j].d == 1) || (node[j].d == 2)) |
| 300 | n.push(j); |
| 301 | if ((node[k].d == 1) || (node[k].d == 2)) |
| 302 | n.push(k); |
| 303 | break; |
| 304 | } |
| 305 | default: GECODE_NEVER; |
| 306 | } |
| 307 | } |
| 308 | reg.free(); |
| 309 | } |
| 310 | // Initialize for Bron-Kerbosch |
| 311 | { |
| 312 | NodeSet p(reg,nodes()), x(reg,nodes()); |