29 #include "../DdSpec.hpp" 30 #include "../util/Graph.hpp" 34 enum SimpathBasedImplType {
38 template<
typename S, SimpathBasedImplType type,
bool hamilton = false>
47 int const mateArraySize_;
48 std::vector<Mate> initialMate;
56 void shiftMate(Mate* mate,
int v0,
int vv0)
const {
57 int const d = vv0 - v0;
59 std::memmove(mate, mate + d, (mateArraySize_ - d) *
sizeof(*mate));
60 for (
int k = mateArraySize_ - d; k < mateArraySize_; ++k) {
61 mate[k] = initialMate[vv0 + k];
66 Takable takable(Mate
const* mate, Graph::EdgeInfo
const& e)
const {
67 int const w1 = mate[e.v1 - e.v0];
68 int const w2 = mate[e.v2 - e.v0];
70 if (w1 == 0)
return NO;
71 if (e.v1final && w1 == e.v1)
return NO;
73 if (w2 == 0)
return NO;
74 if (e.v2final && w2 == e.v2)
return NO;
78 if (w1 == e.v2)
return NO;
80 if (w1 < 0 && w2 < 0) {
81 if (w1 != w2)
return NO;
82 if (!e.allColorsSeen)
return YES;
85 for (
int k = 0; k < mateArraySize_; ++k) {
86 if (e.v0 + k == e.v1)
continue;
87 if (e.v0 + k == e.v2)
continue;
89 if (w < 0)
return YES;
90 if (w != 0 && (hamilton || w != e.v0 + k)) clean =
false;
92 return clean ? HIT : NO;
99 for (
int k = 1; k < mateArraySize_; ++k) {
100 if (e.v0 + k == e.v1)
continue;
101 if (e.v0 + k == e.v2)
continue;
103 if (w != 0 && (hamilton || w != e.v0 + k))
return NO;
113 bool leavable(Mate
const* mate, Graph::EdgeInfo
const& e)
const {
114 int const w1 = mate[e.v1 - e.v0];
115 int const w2 = mate[e.v2 - e.v0];
118 if (e.v1final && w1 != 0)
return false;
119 if (e.v2final && w2 != 0)
return false;
120 if (e.v1final2 && w1 == e.v1)
return false;
121 if (e.v2final2 && w2 == e.v2)
return false;
124 if (e.v1final && w1 != 0 && w1 != e.v1)
return false;
125 if (e.v2final && w2 != 0 && w2 != e.v2)
return false;
132 SimpathBasedImpl(Graph
const& graph,
bool lookahead)
133 : graph(graph), m(graph.vertexSize()), n(graph.edgeSize()),
134 mateArraySize_(graph.maxFrontierSize()),
135 initialMate(m + mateArraySize_), lookahead(lookahead) {
136 this->setArraySize(mateArraySize_);
138 for (
int v = 1; v <= m; ++v) {
139 int c = graph.colorNumber(v);
140 initialMate[v] = (c > 0) ? -c : v;
143 for (
int v = m + 1; v < m + mateArraySize_; ++v) {
148 int mateArraySize()
const {
149 return mateArraySize_;
152 int getRoot(Mate* mate)
const {
153 int const v0 = graph.edgeInfo(0).v0;
155 for (
int k = 0; k < mateArraySize_; ++k) {
156 mate[k] = initialMate[v0 + k];
162 int getChild(Mate* mate,
int level,
int take)
const {
163 assert(1 <= level && level <= n);
165 Graph::EdgeInfo
const& e = graph.edgeInfo(i);
166 assert(e.v1 <= e.v2);
169 switch (takable(mate, e)) {
178 int w1 = mate[e.v1 - e.v0];
179 int w2 = mate[e.v2 - e.v0];
180 if (w1 > 0) mate[w1 - e.v0] = w2;
181 if (w2 > 0) mate[w2 - e.v0] = w1;
182 if (e.v1final || w1 != e.v1) mate[e.v1 - e.v0] = 0;
183 if (e.v2final || w2 != e.v2) mate[e.v2 - e.v0] = 0;
186 if (!leavable(mate, e))
return 0;
188 Mate& w1 = mate[e.v1 - e.v0];
189 Mate& w2 = mate[e.v2 - e.v0];
190 if (e.v1final || (e.v1final2 && w1 == e.v1)) w1 = 0;
191 if (e.v2final || (e.v2final2 && w2 == e.v2)) w2 = 0;
194 if (++i == n)
return 0;
195 shiftMate(mate, e.v0, graph.edgeInfo(i).v0);
198 Graph::EdgeInfo
const& e = graph.edgeInfo(i);
199 assert(e.v1 <= e.v2);
201 if (takable(mate, e) != NO)
break;
202 if (!leavable(mate, e))
return 0;
203 if (++i == n)
return 0;
205 Mate& w1 = mate[e.v1 - e.v0];
206 Mate& w2 = mate[e.v2 - e.v0];
207 if (e.v1final || (e.v1final2 && w1 == e.v1)) w1 = 0;
208 if (e.v2final || (e.v2final2 && w2 == e.v2)) w2 = 0;
210 shiftMate(mate, e.v0, graph.edgeInfo(i).v0);
218 struct PathZdd:
public SimpathBasedImpl<PathZdd,Path,false> {
219 PathZdd(Graph
const& graph,
bool lookahead =
true)
220 : SimpathBasedImpl<PathZdd,Path,false>(graph, lookahead) {
224 struct HamiltonPathZdd:
public SimpathBasedImpl<HamiltonPathZdd,Path,true> {
225 HamiltonPathZdd(Graph
const& graph,
bool lookahead =
true)
226 : SimpathBasedImpl<HamiltonPathZdd,Path,true>(graph, lookahead) {
230 struct CycleZdd:
public SimpathBasedImpl<CycleZdd,Cycle,false> {
231 CycleZdd(Graph
const& graph,
bool lookahead =
true)
232 : SimpathBasedImpl<CycleZdd,Cycle,false>(graph, lookahead) {
236 struct HamiltonCycleZdd:
public SimpathBasedImpl<HamiltonCycleZdd,Cycle,true> {
237 HamiltonCycleZdd(Graph
const& graph,
bool lookahead =
true)
238 : SimpathBasedImpl<HamiltonCycleZdd,Cycle,true>(graph, lookahead) {
Abstract class of DD specifications using POD array states.