| 36 | namespace Gecode { namespace Int { namespace BinPacking { |
| 37 | |
| 38 | ExecStatus |
| 39 | ConflictGraph::bk(NodeSet& p, NodeSet& x) { |
| 40 | assert(!(p.none(nodes()) && x.none(nodes()))); |
| 41 | // Iterate over neighbors of pivot node |
| 42 | Nodes n(node[pivot(p,x)].n); |
| 43 | // Iterate over elements of p |
| 44 | Nodes i(p); |
| 45 | // The loop iterates over elements in i - n |
| 46 | while (i() < nodes()) { |
| 47 | int iv = i(), nv = n(); |
| 48 | if ((n() < nodes()) && (iv == nv)) { |
| 49 | ++i; ++n; |
| 50 | } else if ((n() < nodes()) && (iv > nv)) { |
| 51 | ++n; |
| 52 | } else { |
| 53 | ++i; ++n; |
| 54 | |
| 55 | Region reg; |
| 56 | |
| 57 | // Found i.val() to be in i - n |
| 58 | |
| 59 | NodeSet np, nx; |
| 60 | np.allocate(reg,nodes()); |
| 61 | nx.allocate(reg,nodes()); |
| 62 | |
| 63 | bool empty = NodeSet::iwn(np,p,nx,x,node[iv].n,nodes()); |
| 64 | |
| 65 | p.excl(iv); x.incl(iv); |
| 66 | |
| 67 | // Update current clique |
| 68 | cur.incl(iv,node[iv].w); |
| 69 | |
| 70 | if (empty) { |
| 71 | // Found a max clique |
| 72 | GECODE_ES_CHECK(clique()); |
| 73 | } else { |
| 74 | GECODE_ES_CHECK(bk(np,nx)); |
| 75 | } |
| 76 | |
| 77 | // Reset current clique |
| 78 | cur.excl(iv,node[iv].w); |
| 79 | } |
| 80 | } |
| 81 | return ES_OK; |
| 82 | } |
| 83 | |
| 84 | }}} |
| 85 | |