34 #include "../DdSpec.hpp" 35 #include "../util/Graph.hpp" 39 struct FrontierBasedSearchCount {
42 FrontierBasedSearchCount()
46 FrontierBasedSearchCount(int16_t uncoloredEdgeComponents)
47 : uec(uncoloredEdgeComponents) {
54 bool operator==(FrontierBasedSearchCount
const& o)
const {
58 friend std::ostream& operator<<(std::ostream& os,
59 FrontierBasedSearchCount
const& o) {
64 class FrontierBasedSearchMate {
66 typedef int16_t Offset;
67 static Offset
const UNCOLORED = 32766;
68 static Offset
const UNCOLORED_EDGE_COMPONENT = 32767;
86 FrontierBasedSearchMate(Offset hoc = 0)
90 bool operator==(FrontierBasedSearchMate
const& o)
const {
94 bool operator!=(FrontierBasedSearchMate
const& o)
const {
103 bool isHead()
const {
107 bool isTail()
const {
111 bool isIsolated()
const {
112 return isHead() && isTail();
115 FrontierBasedSearchMate& head() {
116 return isHead() ? *this : *(
this + hoc);
119 FrontierBasedSearchMate
const& head()
const {
120 return isHead() ? *this : *(
this + hoc);
123 FrontierBasedSearchMate& next() {
124 return *(
this + nxt);
127 FrontierBasedSearchMate
const& next()
const {
128 return *(
this + nxt);
131 bool isColored()
const {
132 return head().hoc < UNCOLORED;
135 bool isUncoloredEdgeComponent()
const {
136 return head().hoc == UNCOLORED_EDGE_COMPONENT;
139 bool isColoredTail()
const {
140 return hoc == 0 || (hoc < 0 && hoc + (
this + hoc)->hoc == 0);
143 bool hasSameColorAs(FrontierBasedSearchMate
const& o)
const {
144 FrontierBasedSearchMate
const* p = &head();
145 FrontierBasedSearchMate
const* q = &o.head();
146 return p + p->hoc == q + q->hoc;
149 FrontierBasedSearchMate
const* findColorPredecessor(
150 FrontierBasedSearchMate
const& o)
const {
151 assert(o.isColoredTail());
152 FrontierBasedSearchMate
const* p = &o;
154 while (--p >=
this) {
155 FrontierBasedSearchMate
const* p1 = &p->head();
156 if (p1 + p1->hoc == &o)
return p;
162 void mergeLists(FrontierBasedSearchMate& o1, FrontierBasedSearchMate& o2) {
163 FrontierBasedSearchMate* p1 = &o1.head();
164 FrontierBasedSearchMate* p2 = &o2.head();
165 if (p1 == p2)
return;
166 if (p1 > p2) std::swap(p1, p2);
170 if (p2->hoc < UNCOLORED) {
171 painting = (p1->hoc >= UNCOLORED);
173 if (painting || p1 + p1->hoc < p2 + p2->hoc) {
174 p1->hoc = p2->hoc + (p2 - p1);
178 painting = (p1->hoc < UNCOLORED);
180 if (p1->hoc == UNCOLORED) {
181 p1->hoc = UNCOLORED_EDGE_COMPONENT;
185 for (FrontierBasedSearchMate* q = p2;; q += q->nxt) {
187 if (q->nxt == 0)
break;
190 FrontierBasedSearchMate* p = p1;
191 FrontierBasedSearchMate* q = p2;
195 FrontierBasedSearchMate* pp = p + p->nxt;
196 assert(p <= pp && pp != q);
198 while (p < pp && pp < q) {
201 assert(p <= pp && pp != q);
204 assert(p == pp || q < pp);
215 FrontierBasedSearchMate* pp = p1 + p1->hoc;
218 for (p =
this; p <= pp; ++p) {
219 if (p + p->hoc == pp) p->hoc = q - p;
225 void replaceHeadWith(FrontierBasedSearchMate& newHead)
const {
226 FrontierBasedSearchMate
const* p = &head();
227 FrontierBasedSearchMate* q = &newHead;
229 q->hoc = (p->hoc < UNCOLORED) ? p->hoc + (p - q) : p->hoc;
233 q->hoc = &newHead - q;
237 void removeFromList(FrontierBasedSearchMate
const& o) {
238 if (o.isColoredTail()) {
240 FrontierBasedSearchMate
const* pp = findColorPredecessor(o);
243 for (FrontierBasedSearchMate* p =
this; p <= pp; ++p) {
244 if (p + p->hoc == &o) p->hoc = pp - p;
245 if (p + p->nxt == &o) p->nxt = 0;
248 else if (o.nxt == 0) {
249 for (FrontierBasedSearchMate* p =
this; p <= &o; ++p) {
250 if (p + p->nxt == &o) p->nxt = 0;
254 for (FrontierBasedSearchMate* p =
this; p <= &o; ++p) {
255 if (p + p->nxt == &o) p->nxt += o.nxt;
260 friend std::ostream& operator<<(std::ostream& os,
261 FrontierBasedSearchMate
const& o) {
262 return os <<
"<" << o.hoc <<
"," << o.nxt <<
">";
267 FrontierBasedSearchCount,FrontierBasedSearchMate,2> {
268 typedef FrontierBasedSearchCount Count;
269 typedef FrontierBasedSearchMate Mate;
275 std::vector<Mate> initialMate;
278 bool const lookahead;
280 int takable(Count& c, Mate
const* mate, Graph::EdgeInfo
const& e)
const {
281 Mate
const& w1 = mate[e.v1 - e.v0];
282 Mate
const& w2 = mate[e.v2 - e.v0];
285 if (noLoop && w1.head() == w2.head())
return false;
288 if (w1.isColored() && w2.isColored() && !w1.hasSameColorAs(w2))
return false;
290 if (e.v1final && e.v2final) {
291 if (w1.isIsolated() && w2.isIsolated()) {
292 if (w2.isColored()) {
294 if (!w2.isColoredTail())
return false;
295 if (mate[1].findColorPredecessor(w2))
return false;
298 if (w1.isColored()) {
300 if (!w1.isColoredTail())
return false;
303 if (c.uec == 0)
return false;
304 if (c.uec > 0) --c.uec;
308 else if (w1.isHead() && w2 == w1.next() && w2.isTail()) {
309 if (w1.isColored()) {
311 if (!w2.isColoredTail())
return false;
312 if (w2.findColorPredecessor(mate[1]))
return false;
315 assert(w1.isUncoloredEdgeComponent());
316 if (c.uec == 0)
return false;
317 if (c.uec > 0) --c.uec;
322 if (e.finalEdge && c.uec > 0)
return false;
326 bool doTake(Count& count, Mate* mate, Graph::EdgeInfo
const& e)
const {
329 if (!takable(c, mate, e))
return false;
332 mate[0].mergeLists(mate[e.v1 - e.v0], mate[e.v2 - e.v0]);
336 bool doNotTake(Count& count, Mate* mate, Graph::EdgeInfo
const& e)
const {
338 Mate
const& w1 = mate[e.v1 - e.v0];
339 Mate
const& w2 = mate[e.v2 - e.v0];
341 if (e.v1final && w1.isIsolated()) {
342 if (w1.isColored()) {
344 if (!w1.isColoredTail())
return false;
346 else if (c.uec >= 0 && w1.isUncoloredEdgeComponent()) {
347 if (c.uec == 0)
return false;
352 if (e.v2final && w2.isIsolated()) {
353 if (w2.isColored()) {
355 if (!w2.isColoredTail())
return false;
356 if (mate[1].findColorPredecessor(w2))
return false;
358 else if (c.uec >= 0 && w2.isUncoloredEdgeComponent()) {
359 if (c.uec == 0)
return false;
364 if (e.v1final && e.v2final && w1.isHead() && w2 == w1.next()
366 if (w1.isColored()) {
368 if (!w2.isColoredTail())
return false;
369 if (w2.findColorPredecessor(mate[1]))
return false;
372 assert(w1.isUncoloredEdgeComponent());
373 if (c.uec == 0)
return false;
374 if (c.uec > 0) --c.uec;
378 if (e.finalEdge && c.uec > 0)
return false;
383 void update(Mate* mate, Graph::EdgeInfo
const& e,
384 Graph::EdgeInfo
const& ee)
const {
385 int const d = ee.v0 - e.v0;
387 Mate* p1 = &mate[e.v1 - e.v0];
388 Mate* p2 = &mate[e.v2 - e.v0];
391 for (Mate* q = p1; q < pd; ++q) {
392 Mate* qq = &q->next();
394 q->replaceHeadWith(*qq);
399 mate[0].removeFromList(*p2);
404 mate[0].removeFromList(*p1);
409 std::memmove(p1, pd, (mateSize - d) *
sizeof(*mate));
410 for (
int i = mateSize - d; i < mateSize; ++i) {
411 p1[i] = initialMate[ee.v0 + i];
417 FrontierBasedSearch(Graph
const& graph,
int numUEC = -1,
418 bool noLoop =
false,
bool lookahead =
true)
419 : graph(graph), m(graph.vertexSize()), n(graph.edgeSize()),
420 mateSize(graph.maxFrontierSize()), initialMate(1 + m + mateSize),
421 numUEC(numUEC), noLoop(noLoop), lookahead(lookahead) {
422 this->setArraySize(mateSize);
424 std::vector<int> rootOfColor(graph.numColor() + 1);
425 for (
int v = 1; v <= m; ++v) {
426 rootOfColor[graph.colorNumber(v)] = v;
428 for (
int v = 1; v <= m; ++v) {
429 int k = graph.colorNumber(v);
430 int hoc = (k > 0) ? rootOfColor[k] - v : Mate::UNCOLORED;
431 initialMate[v] = Mate(hoc);
435 int getRoot(Count& count, Mate* mate)
const {
436 int const v0 = graph.edgeInfo(0).v0;
438 count = Count(numUEC);
440 for (
int i = 0; i < mateSize; ++i) {
441 mate[i] = initialMate[v0 + i];
447 int getChild(Count& count, Mate* mate,
int level,
int take)
const {
448 assert(1 <= level && level <= n);
450 Graph::EdgeInfo
const* e = &graph.edgeInfo(i);
453 if (!doTake(count, mate, *e))
return 0;
456 if (!doNotTake(count, mate, *e))
return 0;
459 if (++i == n)
return -1;
461 Graph::EdgeInfo
const* ee = &graph.edgeInfo(i);
462 update(mate, *e, *ee);
468 if (takable(c, mate, *e))
break;
469 if (!doNotTake(count, mate, *e))
return 0;
471 if (++i == n)
return -1;
473 ee = &graph.edgeInfo(i);
474 update(mate, *e, *ee);
481 size_t hashCode(Count
const& count)
const {
Abstract class of DD specifications using both scalar and POD array states.