| 66 | |
| 67 | template<class View, class Offset> |
| 68 | ExecStatus |
| 69 | Base<View,Offset>::connected(Space& home) { |
| 70 | int n = x.size(); |
| 71 | |
| 72 | /// First non-assigned node reachable from start |
| 73 | { |
| 74 | int v = start; |
| 75 | /// Number of nodes not yet visited |
| 76 | int m = n; |
| 77 | while (x[v].assigned()) { |
| 78 | m--; |
| 79 | v = o(x[v]).val(); |
| 80 | // Reached start node again, check whether all nodes have been visited |
| 81 | if (start == v) |
| 82 | return (m == 0) ? home.ES_SUBSUMED(*this) : ES_FAILED; |
| 83 | } |
| 84 | start = v; |
| 85 | } |
| 86 | |
| 87 | /// Information needed for checking scc's |
| 88 | Region r; |
| 89 | typedef typename Offset::ViewType OView; |
| 90 | NodeInfo<OView>* si = r.alloc<NodeInfo<OView> >(n); |
| 91 | unsigned int n_edges = 0; |
| 92 | for (int i=0; i<n; i++) { |
| 93 | n_edges += x[i].size(); |
| 94 | si[i].pre=-1; |
| 95 | } |
| 96 | |
| 97 | // Stack to remember which nodes have not been processed completely |
| 98 | Support::StaticStack<int,Region> next(r,n); |
| 99 | |
| 100 | // Array to remember which mandatory tells need to be done |
| 101 | TellInfo<OView>* eq = r.alloc<TellInfo<OView> >(n); |
| 102 | int n_eq = 0; |
| 103 | |
| 104 | // Array to remember which edges need to be pruned |
| 105 | TellInfo<OView>* nq = r.alloc<TellInfo<OView> >(n_edges); |
| 106 | int n_nq = 0; |
| 107 | |
| 108 | /* |
| 109 | * Check whether there is a single strongly connected component. |
| 110 | * This is a downstripped version of Tarjan's algorithm as |
| 111 | * the computation of sccs proper is not needed. In addition, it |
| 112 | * checks a mandatory condition for a graph to be Hamiltonian |
| 113 | * (due to Mats Carlsson). |
| 114 | * |
| 115 | * To quote Mats: Suppose you do a depth-first search of the graph. |
| 116 | * In that search, the root node will have a number of child subtrees |
| 117 | * T1, ..., Tn. By construction, if i<j then there is no edge from |
| 118 | * Ti to Tj. The necessary condition for Hamiltonianicity is that |
| 119 | * there be an edge from Ti+1 to Ti, for 0 < i < n. |
| 120 | * |
| 121 | * In addition, we do the following: if there is only a single edge |
| 122 | * from Ti+1 to Ti, then it must be mandatory and the variable must |
| 123 | * be assigned to that value. |
| 124 | * |
| 125 | * The same holds true for a back edge from T0 to the root node. |
nothing calls this directly
no test coverage detected