diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/cardinality/PolyhedronSolver.xtend')
-rw-r--r-- | Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/cardinality/PolyhedronSolver.xtend | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/cardinality/PolyhedronSolver.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/cardinality/PolyhedronSolver.xtend new file mode 100644 index 00000000..4e046190 --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra/src/hu/bme/mit/inf/dslreasoner/viatrasolver/logic2viatra/cardinality/PolyhedronSolver.xtend | |||
@@ -0,0 +1,179 @@ | |||
1 | package hu.bme.mit.inf.dslreasoner.viatrasolver.logic2viatra.cardinality | ||
2 | |||
3 | import java.util.List | ||
4 | import java.util.Map | ||
5 | import org.eclipse.xtend.lib.annotations.Accessors | ||
6 | import org.eclipse.xtend.lib.annotations.Data | ||
7 | import org.eclipse.xtend.lib.annotations.FinalFieldsConstructor | ||
8 | |||
9 | interface PolyhedronSolver { | ||
10 | def PolyhedronSaturationOperator createSaturationOperator(Polyhedron polyhedron) | ||
11 | } | ||
12 | |||
13 | enum PolyhedronSaturationResult { | ||
14 | SATURATED, | ||
15 | EMPTY, | ||
16 | UNKNOWN | ||
17 | } | ||
18 | |||
19 | interface PolyhedronSaturationOperator extends AutoCloseable { | ||
20 | def Polyhedron getPolyhedron() | ||
21 | |||
22 | def PolyhedronSaturationResult saturate() | ||
23 | } | ||
24 | |||
25 | @FinalFieldsConstructor | ||
26 | @Accessors | ||
27 | class Polyhedron { | ||
28 | /** | ||
29 | * The list of dimensions (variables) for this polyhedron. | ||
30 | * | ||
31 | * This list must not be modified after the polyhedron was created. | ||
32 | * However, lower and upper bounds of the dimensions may be changed. | ||
33 | * | ||
34 | * Names of dimensions in this list are assumed to be unique. | ||
35 | */ | ||
36 | val List<Dimension> dimensions | ||
37 | |||
38 | /** | ||
39 | * The list of constraints defining this polyhedron. | ||
40 | * | ||
41 | * The list and its elements may be freely modified. | ||
42 | */ | ||
43 | val List<LinearConstraint> constraints | ||
44 | |||
45 | /** | ||
46 | * The list of constraints that should be saturated (tightened) | ||
47 | * when a {@link PolyhedronSaturationOperator} is invoked. | ||
48 | * | ||
49 | * This list may be freely modified. | ||
50 | * | ||
51 | * Place all dimensions and constraints here to saturate all the bounds. | ||
52 | */ | ||
53 | val List<LinearBoundedExpression> expressionsToSaturate | ||
54 | |||
55 | override toString() ''' | ||
56 | Dimensions: | ||
57 | «FOR dimension : dimensions» | ||
58 | «dimension» | ||
59 | «ENDFOR» | ||
60 | Constraints: | ||
61 | «FOR constraint : constraints» | ||
62 | «constraint» | ||
63 | «ENDFOR» | ||
64 | ''' | ||
65 | |||
66 | def createSignature() { | ||
67 | val size = dimensions.size + constraints.size | ||
68 | val lowerBounds = newArrayOfSize(size) | ||
69 | val upperBounds = newArrayOfSize(size) | ||
70 | var int i = 0 | ||
71 | for (dimension : dimensions) { | ||
72 | lowerBounds.set(i, dimension.lowerBound) | ||
73 | upperBounds.set(i, dimension.upperBound) | ||
74 | i++ | ||
75 | } | ||
76 | for (constraint : constraints) { | ||
77 | lowerBounds.set(i, constraint.lowerBound) | ||
78 | upperBounds.set(i, constraint.upperBound) | ||
79 | i++ | ||
80 | } | ||
81 | new PolyhedronSignature.Bounds(lowerBounds, upperBounds) | ||
82 | } | ||
83 | |||
84 | def applySignature(PolyhedronSignature.Bounds signature) { | ||
85 | val lowerBounds = signature.lowerBounds | ||
86 | val upperBounds = signature.upperBounds | ||
87 | var int i = 0 | ||
88 | for (dimension : dimensions) { | ||
89 | dimension.lowerBound = lowerBounds.get(i) | ||
90 | dimension.upperBound = upperBounds.get(i) | ||
91 | i++ | ||
92 | } | ||
93 | for (constraint : constraints) { | ||
94 | constraint.lowerBound = lowerBounds.get(i) | ||
95 | constraint.upperBound = upperBounds.get(i) | ||
96 | i++ | ||
97 | } | ||
98 | } | ||
99 | } | ||
100 | |||
101 | abstract class PolyhedronSignature { | ||
102 | public static val EMPTY = new PolyhedronSignature { | ||
103 | override toString() { | ||
104 | "PolyhedronSignature.EMPTY" | ||
105 | } | ||
106 | } | ||
107 | |||
108 | private new() { | ||
109 | } | ||
110 | |||
111 | @Data | ||
112 | static class Bounds extends PolyhedronSignature { | ||
113 | val Integer[] lowerBounds | ||
114 | val Integer[] upperBounds | ||
115 | } | ||
116 | } | ||
117 | |||
118 | @Accessors | ||
119 | abstract class LinearBoundedExpression { | ||
120 | var Integer lowerBound | ||
121 | var Integer upperBound | ||
122 | |||
123 | def void tightenLowerBound(Integer tighterBound) { | ||
124 | if (lowerBound === null || (tighterBound !== null && lowerBound < tighterBound)) { | ||
125 | lowerBound = tighterBound | ||
126 | } | ||
127 | } | ||
128 | |||
129 | def void tightenUpperBound(Integer tighterBound) { | ||
130 | if (upperBound === null || (tighterBound !== null && upperBound > tighterBound)) { | ||
131 | upperBound = tighterBound | ||
132 | } | ||
133 | } | ||
134 | |||
135 | def void assertEqualsTo(int bound) { | ||
136 | tightenLowerBound(bound) | ||
137 | tightenUpperBound(bound) | ||
138 | } | ||
139 | } | ||
140 | |||
141 | @Accessors | ||
142 | class Dimension extends LinearBoundedExpression { | ||
143 | val String name | ||
144 | |||
145 | @FinalFieldsConstructor | ||
146 | new() { | ||
147 | } | ||
148 | |||
149 | new(String name, Integer lowerBound, Integer upperBound) { | ||
150 | this(name) | ||
151 | this.lowerBound = lowerBound | ||
152 | this.upperBound = upperBound | ||
153 | } | ||
154 | |||
155 | override toString() { | ||
156 | '''«IF lowerBound !== null»«lowerBound» <= «ENDIF»«name»«IF upperBound !== null» <= «upperBound»«ENDIF»''' | ||
157 | } | ||
158 | |||
159 | } | ||
160 | |||
161 | @Accessors | ||
162 | class LinearConstraint extends LinearBoundedExpression { | ||
163 | val Map<Dimension, Integer> coefficients | ||
164 | |||
165 | @FinalFieldsConstructor | ||
166 | new() { | ||
167 | } | ||
168 | |||
169 | new(Map<Dimension, Integer> coefficients, Integer lowerBound, Integer upperBound) { | ||
170 | this(coefficients) | ||
171 | this.lowerBound = lowerBound | ||
172 | this.upperBound = upperBound | ||
173 | } | ||
174 | |||
175 | override toString() { | ||
176 | '''«IF lowerBound !== null»«lowerBound» <= «ENDIF»«FOR pair : coefficients.entrySet SEPARATOR " + "»«IF pair.value != 1»«pair.value» * «ENDIF»«pair.key.name»«ENDFOR»«IF upperBound !== null» <= «upperBound»«ENDIF»''' | ||
177 | } | ||
178 | |||
179 | } | ||