33 #include "../DdSpec.hpp" 34 #include "../util/Graph.hpp" 35 #include "../util/IntSubset.hpp" 39 class DegreeConstraint:
public PodArrayDdSpec<DegreeConstraint,int16_t,2> {
43 std::vector<IntSubset const*> constraints;
48 void shiftMate(Mate* mate,
int d)
const {
51 std::memmove(mate, mate + d, (mateSize - d) *
sizeof(*mate));
52 for (
int k = mateSize - d; k < mateSize; ++k) {
58 bool takable(IntSubset
const* c, Mate degree,
bool final)
const {
59 if (c == 0)
return true;
60 if (degree >= c->upperBound())
return false;
61 return !
final || c->contains(degree + 1);
64 bool leavable(IntSubset
const* c, Mate degree,
bool final)
const {
65 if (c == 0)
return true;
66 return !
final || c->contains(degree);
70 DegreeConstraint(Graph
const& graph, IntSubset
const* c = 0,
bool lookahead =
true)
71 : graph(graph), n(graph.edgeSize()),
72 mateSize(graph.maxFrontierSize()), lookahead(lookahead) {
73 setArraySize(mateSize);
75 int m = graph.vertexSize();
76 constraints.resize(m + 1);
77 for (
int v = 1; v <= m; ++v) {
82 void setConstraint(Graph::VertexNumber v, IntSubset
const* c) {
83 if (v < 1 || graph.vertexSize() < v)
throw std::runtime_error(
84 "ERROR: Vertex number is out of range");
88 void setConstraint(std::string v, IntSubset
const* c) {
89 constraints[graph.getVertex(v)] = c;
92 int getRoot(Mate* mate)
const {
93 for (
int k = 0; k < mateSize; ++k) {
99 int getChild(Mate* mate,
int level,
int take)
const {
100 assert(1 <= level && level <= n);
102 Graph::EdgeInfo
const& e = graph.edgeInfo(i);
103 Mate& w1 = mate[e.v1 - e.v0];
104 Mate& w2 = mate[e.v2 - e.v0];
105 IntSubset
const* c1 = constraints[e.v1];
106 IntSubset
const* c2 = constraints[e.v2];
107 assert(e.v1 <= e.v2);
110 if (!takable(c1, w1, e.v1final))
return 0;
111 if (!takable(c2, w2, e.v2final))
return 0;
116 if (!leavable(c1, w1, e.v1final))
return 0;
117 if (!leavable(c2, w2, e.v2final))
return 0;
120 if (e.v1final) w1 = 0;
121 if (e.v2final) w2 = 0;
123 if (++i == n)
return -1;
124 shiftMate(mate, graph.edgeInfo(i).v0 - e.v0);
127 Graph::EdgeInfo
const& e = graph.edgeInfo(i);
128 Mate& w1 = mate[e.v1 - e.v0];
129 Mate& w2 = mate[e.v2 - e.v0];
130 IntSubset
const* c1 = constraints[e.v1];
131 IntSubset
const* c2 = constraints[e.v2];
132 assert(e.v1 <= e.v2);
134 if (takable(c1, w1, e.v1final) && takable(c2, w2, e.v2final))
break;
135 if (!leavable(c1, w1, e.v1final))
return 0;
136 if (!leavable(c2, w2, e.v2final))
return 0;
138 if (e.v1final) w1 = 0;
139 if (e.v2final) w2 = 0;
141 if (++i == n)
return -1;
142 shiftMate(mate, graph.edgeInfo(i).v0 - e.v0);