aboutsummaryrefslogtreecommitdiffstats
path: root/subprojects/store-dse/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'subprojects/store-dse/src/main')
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java14
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java66
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java48
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java11
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java13
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java14
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java292
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java67
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java62
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java89
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java52
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java132
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java26
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java30
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java101
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java59
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java199
-rw-r--r--subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java117
18 files changed, 1392 insertions, 0 deletions
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java
new file mode 100644
index 00000000..524c2f55
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/ActionFactory.java
@@ -0,0 +1,14 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse;
7
8import org.eclipse.collections.api.block.procedure.Procedure;
9import tools.refinery.store.model.Model;
10import tools.refinery.store.tuple.Tuple;
11
12public interface ActionFactory {
13 Procedure<Tuple> prepare(Model model);
14}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java
new file mode 100644
index 00000000..8963a496
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationAdapter.java
@@ -0,0 +1,66 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse;
7
8import tools.refinery.store.adapter.ModelAdapter;
9import tools.refinery.store.map.Version;
10import tools.refinery.store.dse.internal.Activation;
11import tools.refinery.store.dse.internal.DesignSpaceExplorationBuilderImpl;
12import tools.refinery.store.dse.objectives.Fitness;
13import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper;
14import tools.refinery.store.tuple.Tuple;
15import tools.refinery.store.tuple.Tuple1;
16
17import java.util.Collection;
18import java.util.List;
19import java.util.Random;
20
21public interface DesignSpaceExplorationAdapter extends ModelAdapter {
22 @Override
23 DesignSpaceExplorationStoreAdapter getStoreAdapter();
24
25 static DesignSpaceExplorationBuilder builder() {
26 return new DesignSpaceExplorationBuilderImpl();
27 }
28
29 Collection<Version> explore();
30
31 public int getModelSize();
32
33 public Tuple1 createObject();
34
35 public Tuple deleteObject(Tuple tuple);
36
37 public boolean checkGlobalConstraints();
38
39 public boolean backtrack();
40
41 public Fitness calculateFitness();
42
43 public void newSolution();
44
45 public int getDepth();
46
47 public Collection<Activation> getUntraversedActivations();
48
49 public boolean fireActivation(Activation activation);
50
51 public void fireRandomActivation();
52
53 public boolean isCurrentInTrajectory();
54
55 public List<Version> getTrajectory();
56
57 public boolean isCurrentStateAlreadyTraversed();
58
59 public ObjectiveComparatorHelper getObjectiveComparatorHelper();
60
61 public void restoreTrajectory(List<Version> trajectory);
62
63 public void setRandom(Random random);
64
65 public void setRandom(long seed);
66}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java
new file mode 100644
index 00000000..4def5cb2
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationBuilder.java
@@ -0,0 +1,48 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse;
7
8import tools.refinery.store.adapter.ModelAdapterBuilder;
9import tools.refinery.store.query.dnf.RelationalQuery;
10import tools.refinery.store.dse.internal.TransformationRule;
11import tools.refinery.store.dse.objectives.Objective;
12
13import java.util.Collection;
14import java.util.List;
15
16public interface DesignSpaceExplorationBuilder extends ModelAdapterBuilder {
17 default DesignSpaceExplorationBuilder transformations(TransformationRule... transformationRules) {
18 return transformations(List.of(transformationRules));
19 }
20
21 default DesignSpaceExplorationBuilder transformations(Collection<? extends TransformationRule> transformationRules) {
22 transformationRules.forEach(this::transformation);
23 return this;
24 }
25
26 default DesignSpaceExplorationBuilder globalConstraints(RelationalQuery... globalConstraints) {
27 return globalConstraints(List.of(globalConstraints));
28 }
29
30 default DesignSpaceExplorationBuilder globalConstraints(Collection<RelationalQuery> globalConstraints) {
31 globalConstraints.forEach(this::globalConstraint);
32 return this;
33 }
34
35 default DesignSpaceExplorationBuilder objectives(Objective... objectives) {
36 return objectives(List.of(objectives));
37 }
38
39 default DesignSpaceExplorationBuilder objectives(Collection<? extends Objective> objectives) {
40 objectives.forEach(this::objective);
41 return this;
42 }
43
44 DesignSpaceExplorationBuilder transformation(TransformationRule transformationRule);
45 DesignSpaceExplorationBuilder globalConstraint(RelationalQuery globalConstraint);
46 DesignSpaceExplorationBuilder objective(Objective objective);
47 DesignSpaceExplorationBuilder strategy(Strategy strategy);
48}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java
new file mode 100644
index 00000000..186bfebb
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/DesignSpaceExplorationStoreAdapter.java
@@ -0,0 +1,11 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse;
7
8import tools.refinery.store.adapter.ModelStoreAdapter;
9
10public interface DesignSpaceExplorationStoreAdapter extends ModelStoreAdapter {
11}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java
new file mode 100644
index 00000000..e240f478
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/Strategy.java
@@ -0,0 +1,13 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse;
7
8public interface Strategy {
9
10 public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter);
11
12 public void explore();
13}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java
new file mode 100644
index 00000000..1893ce2e
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/Activation.java
@@ -0,0 +1,14 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse.internal;
7
8import tools.refinery.store.tuple.Tuple;
9
10public record Activation(TransformationRule transformationRule, Tuple activation) {
11 public boolean fire() {
12 return transformationRule.fireActivation(activation);
13 }
14}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java
new file mode 100644
index 00000000..b32e9696
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationAdapterImpl.java
@@ -0,0 +1,292 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.internal;
11
12import tools.refinery.store.map.Version;
13import tools.refinery.store.model.Interpretation;
14import tools.refinery.store.model.Model;
15import tools.refinery.store.query.ModelQueryAdapter;
16import tools.refinery.store.query.dnf.RelationalQuery;
17import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
18import tools.refinery.store.dse.DesignSpaceExplorationStoreAdapter;
19import tools.refinery.store.dse.Strategy;
20import tools.refinery.store.dse.objectives.Fitness;
21import tools.refinery.store.dse.objectives.Objective;
22import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper;
23import tools.refinery.store.query.resultset.ResultSet;
24import tools.refinery.store.representation.Symbol;
25import tools.refinery.store.tuple.Tuple;
26import tools.refinery.store.tuple.Tuple1;
27import tools.refinery.visualization.ModelVisualizerAdapter;
28
29import java.util.*;
30
31public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExplorationAdapter {
32 static final Symbol<Integer> NODE_COUNT_SYMBOL = Symbol.of("MODEL_SIZE", 0, Integer.class, 0);
33 private final Model model;
34 private final ModelQueryAdapter queryEngine;
35 private final DesignSpaceExplorationStoreAdapterImpl storeAdapter;
36 private final LinkedHashSet<TransformationRule> transformationRules;
37 private final LinkedHashSet<RelationalQuery> globalConstraints;
38 private final List<Objective> objectives;
39 private final LinkedHashSet<ResultSet<Boolean>> globalConstraintResultSets = new LinkedHashSet<>();
40 private final Interpretation<Integer> sizeInterpretation;
41 private final Strategy strategy;
42
43 private ObjectiveComparatorHelper objectiveComparatorHelper;
44 private List<Version> trajectory = new LinkedList<>();
45 private Fitness lastFitness;
46 private final LinkedHashSet<Version> solutions = new LinkedHashSet<>();
47 private Map<Version, LinkedHashSet<Activation>> statesAndUntraversedActivations;
48 private Map<Version, LinkedHashSet<Activation>> statesAndTraversedActivations;
49 private Random random = new Random();
50 private boolean isNewState = false;
51 private final boolean isVisualizationEnabled;
52 private final ModelVisualizerAdapter modelVisualizerAdapter;
53
54 public List<Version> getTrajectory() {
55 return new LinkedList<>(trajectory);
56 }
57
58 public DesignSpaceExplorationAdapterImpl(Model model, DesignSpaceExplorationStoreAdapterImpl storeAdapter) {
59 this.model = model;
60 this.storeAdapter = storeAdapter;
61 this.sizeInterpretation = model.getInterpretation(NODE_COUNT_SYMBOL);
62 queryEngine = model.getAdapter(ModelQueryAdapter.class);
63
64 globalConstraints = storeAdapter.getGlobalConstraints();
65 for (var constraint : globalConstraints) {
66 globalConstraintResultSets.add(queryEngine.getResultSet(constraint));
67 }
68
69 transformationRules = storeAdapter.getTransformationSpecifications();
70 for (var rule : transformationRules) {
71 rule.prepare(model, queryEngine);
72 }
73
74 objectives = storeAdapter.getObjectives();
75 statesAndUntraversedActivations = new HashMap<>();
76 statesAndTraversedActivations = new HashMap<>();
77 strategy = storeAdapter.getStrategy();
78 modelVisualizerAdapter = model.tryGetAdapter(ModelVisualizerAdapter.class).orElse(null);
79 isVisualizationEnabled = modelVisualizerAdapter != null;
80
81 }
82
83 @Override
84 public Model getModel() {
85 return model;
86 }
87
88 @Override
89 public DesignSpaceExplorationStoreAdapter getStoreAdapter() {
90 return storeAdapter;
91 }
92
93 @Override
94 public LinkedHashSet<Version> explore() {
95 var state = model.commit();
96 trajectory.add(state);
97 statesAndUntraversedActivations.put(state, getAllActivations());
98 statesAndTraversedActivations.put(state, new LinkedHashSet<>());
99 strategy.initStrategy(this);
100 strategy.explore();
101 return solutions;
102 }
103
104 @Override
105 public int getModelSize() {
106 return sizeInterpretation.get(Tuple.of());
107 }
108
109 @Override
110 public Tuple1 createObject() {
111 var newNodeId = getModelSize();
112 sizeInterpretation.put(Tuple.of(), newNodeId + 1);
113 return Tuple.of(newNodeId);
114 }
115
116 @Override
117 public Tuple deleteObject(Tuple tuple) {
118 if (tuple.getSize() != 1) {
119 throw new IllegalArgumentException("Tuple size must be 1");
120 }
121// TODO: implement more efficient deletion
122// if (tuple.get(0) == getModelSize() - 1) {
123// sizeInterpretation.put(Tuple.of(), getModelSize() - 1);
124// }
125 return tuple;
126 }
127
128 @Override
129 public boolean checkGlobalConstraints() {
130 for (var resultSet : globalConstraintResultSets) {
131 if (resultSet.size() > 0) {
132 return false;
133 }
134 }
135 return true;
136 }
137
138 @Override
139 public boolean backtrack() {
140 if (trajectory.size() < 2) {
141 return false;
142 }
143 if (isVisualizationEnabled) {
144 modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 1),
145 trajectory.get(trajectory.size() - 2), "backtrack");
146 }
147 model.restore(trajectory.get(trajectory.size() - 2));
148 trajectory.remove(trajectory.size() - 1);
149 return true;
150 }
151
152 @Override
153 public void restoreTrajectory(List<Version> trajectory) {
154 model.restore(trajectory.get(trajectory.size() - 1));
155// if (isVisualizationEnabled) {
156// modelVisualizerAdapter.addTransition(this.trajectory.get(trajectory.size() - 1),
157// trajectory.get(trajectory.size() - 1), "restore");
158// }
159 this.trajectory = trajectory;
160
161 }
162
163 @Override
164 public void setRandom(Random random) {
165 this.random = random;
166 }
167
168 @Override
169 public void setRandom(long seed) {
170 this.random = new Random(seed);
171 }
172
173 @Override
174 public Fitness calculateFitness() {
175 Fitness result = new Fitness();
176 boolean satisfiesHardObjectives = true;
177 for (Objective objective : objectives) {
178 var fitness = objective.getFitness(this);
179 result.put(objective.getName(), fitness);
180 if (objective.isHardObjective() && !objective.satisfiesHardObjective(fitness)) {
181 satisfiesHardObjectives = false;
182 }
183 }
184 result.setSatisfiesHardObjectives(satisfiesHardObjectives);
185
186 lastFitness = result;
187
188 return result;
189 }
190
191 @Override
192 public void newSolution() {
193 var state = model.getState();
194 solutions.add(state);
195 if (isVisualizationEnabled) {
196 modelVisualizerAdapter.addSolution(state);
197 }
198 }
199
200 @Override
201 public int getDepth() {
202 return trajectory.size() - 1;
203 }
204
205 public LinkedHashSet<Activation> getUntraversedActivations() {
206// return statesAndUntraversedActivations.get(model.getState());
207 LinkedHashSet<Activation> untraversedActivations = new LinkedHashSet<>();
208 for (Activation activation : getAllActivations()) {
209 if (!statesAndTraversedActivations.get(model.getState()).contains(activation)) {
210 untraversedActivations.add(activation);
211 }
212 }
213
214 return untraversedActivations;
215 }
216
217 @Override
218 public boolean fireActivation(Activation activation) {
219 if (activation == null) {
220 return false;
221 }
222 var previousState = model.getState();
223 if (!statesAndUntraversedActivations.get(previousState).contains(activation)) {
224// TODO: throw exception?
225 return false;
226 }
227 if (!activation.fire()) {
228 return false;
229 }
230 statesAndUntraversedActivations.get(previousState).remove(activation);
231 statesAndTraversedActivations.get(previousState).add(activation);
232 var newState = model.commit();
233 trajectory.add(newState);
234 isNewState = !statesAndUntraversedActivations.containsKey(newState);
235 statesAndUntraversedActivations.put(newState, getAllActivations());
236 statesAndTraversedActivations.put(newState, new LinkedHashSet<>());
237 if (isVisualizationEnabled) {
238 if (isNewState) {
239 modelVisualizerAdapter.addState(newState);
240 }
241 modelVisualizerAdapter.addTransition(trajectory.get(trajectory.size() - 2),
242 trajectory.get(trajectory.size() - 1), activation.transformationRule().getName(),
243 activation.activation());
244 }
245 return true;
246 }
247
248 @Override
249 public void fireRandomActivation() {
250 var activations = getUntraversedActivations();
251 if (activations.isEmpty()) {
252// TODO: throw exception
253 return;
254 }
255 int index = random.nextInt(activations.size());
256 var iterator = activations.iterator();
257 while (index-- > 0) {
258 iterator.next();
259 }
260 var activationId = iterator.next();
261 fireActivation(activationId);
262 }
263
264 @Override
265 public boolean isCurrentInTrajectory() {
266 return trajectory.contains(model.getState());
267 }
268
269 public LinkedHashSet<Activation> getAllActivations() {
270 LinkedHashSet<Activation> result = new LinkedHashSet<>();
271 for (var rule : transformationRules) {
272 result.addAll(rule.getAllActivations());
273 }
274 return result;
275 }
276
277 public boolean isCurrentStateAlreadyTraversed() {
278// TODO: check isomorphism?
279 return !isNewState;
280 }
281
282 public Fitness getLastFitness() {
283 return lastFitness;
284 }
285
286 public ObjectiveComparatorHelper getObjectiveComparatorHelper() {
287 if (objectiveComparatorHelper == null) {
288 objectiveComparatorHelper = new ObjectiveComparatorHelper(objectives);
289 }
290 return objectiveComparatorHelper;
291 }
292}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java
new file mode 100644
index 00000000..8f7056f2
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationBuilderImpl.java
@@ -0,0 +1,67 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse.internal;
7
8import tools.refinery.store.adapter.AbstractModelAdapterBuilder;
9import tools.refinery.store.model.ModelStore;
10import tools.refinery.store.model.ModelStoreBuilder;
11import tools.refinery.store.query.dnf.RelationalQuery;
12import tools.refinery.store.dse.DesignSpaceExplorationBuilder;
13import tools.refinery.store.dse.Strategy;
14import tools.refinery.store.dse.objectives.Objective;
15
16import java.util.LinkedHashSet;
17import java.util.LinkedList;
18import java.util.List;
19
20public class DesignSpaceExplorationBuilderImpl
21 extends AbstractModelAdapterBuilder<DesignSpaceExplorationStoreAdapterImpl>
22 implements DesignSpaceExplorationBuilder {
23 private final LinkedHashSet<TransformationRule> transformationSpecifications = new LinkedHashSet<>();
24 private final LinkedHashSet<RelationalQuery> globalConstraints = new LinkedHashSet<>();
25 private final List<Objective> objectives = new LinkedList<>();
26 private Strategy strategy;
27
28 @Override
29 protected DesignSpaceExplorationStoreAdapterImpl doBuild(ModelStore store) {
30 return new DesignSpaceExplorationStoreAdapterImpl(store, transformationSpecifications, globalConstraints,
31 objectives, strategy);
32 }
33
34 @Override
35 public DesignSpaceExplorationBuilder transformation(TransformationRule transformationRule) {
36 checkNotConfigured();
37 transformationSpecifications.add(transformationRule);
38 return this;
39 }
40
41 @Override
42 public DesignSpaceExplorationBuilder globalConstraint(RelationalQuery globalConstraint) {
43 checkNotConfigured();
44 globalConstraints.add(globalConstraint);
45 return this;
46 }
47
48 @Override
49 public DesignSpaceExplorationBuilder objective(Objective objective) {
50 checkNotConfigured();
51 objectives.add(objective);
52 return this;
53 }
54
55 @Override
56 public DesignSpaceExplorationBuilder strategy(Strategy strategy) {
57 checkNotConfigured();
58 this.strategy = strategy;
59 return this;
60 }
61
62 @Override
63 protected void doConfigure(ModelStoreBuilder storeBuilder) {
64 storeBuilder.symbols(DesignSpaceExplorationAdapterImpl.NODE_COUNT_SYMBOL);
65 super.doConfigure(storeBuilder);
66 }
67}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java
new file mode 100644
index 00000000..09925ae7
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/DesignSpaceExplorationStoreAdapterImpl.java
@@ -0,0 +1,62 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse.internal;
7
8import tools.refinery.store.adapter.ModelAdapter;
9import tools.refinery.store.model.Model;
10import tools.refinery.store.model.ModelStore;
11import tools.refinery.store.query.dnf.RelationalQuery;
12import tools.refinery.store.dse.DesignSpaceExplorationStoreAdapter;
13import tools.refinery.store.dse.Strategy;
14import tools.refinery.store.dse.objectives.Objective;
15
16import java.util.LinkedHashSet;
17import java.util.List;
18
19public class DesignSpaceExplorationStoreAdapterImpl implements DesignSpaceExplorationStoreAdapter {
20 private final ModelStore store;
21 private final LinkedHashSet<TransformationRule> transformationSpecifications;
22 private final LinkedHashSet<RelationalQuery> globalConstraints;
23 private final List<Objective> objectives;
24 private final Strategy strategy;
25
26 public DesignSpaceExplorationStoreAdapterImpl(ModelStore store,
27 LinkedHashSet<TransformationRule> transformationSpecifications,
28 LinkedHashSet<RelationalQuery> globalConstraints,
29 List<Objective> objectives, Strategy strategy) {
30 this.store = store;
31 this.transformationSpecifications = transformationSpecifications;
32 this.globalConstraints = globalConstraints;
33 this.objectives = objectives;
34 this.strategy = strategy;
35 }
36
37 @Override
38 public ModelStore getStore() {
39 return store;
40 }
41
42 @Override
43 public ModelAdapter createModelAdapter(Model model) {
44 return new DesignSpaceExplorationAdapterImpl(model, this);
45 }
46
47 public LinkedHashSet<TransformationRule> getTransformationSpecifications() {
48 return transformationSpecifications;
49 }
50
51 public LinkedHashSet<RelationalQuery> getGlobalConstraints() {
52 return globalConstraints;
53 }
54
55 public List<Objective> getObjectives() {
56 return objectives;
57 }
58
59 public Strategy getStrategy() {
60 return strategy;
61 }
62}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java
new file mode 100644
index 00000000..015d4815
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/internal/TransformationRule.java
@@ -0,0 +1,89 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.store.dse.internal;
7
8import org.eclipse.collections.api.block.procedure.Procedure;
9import tools.refinery.store.model.Model;
10import tools.refinery.store.query.ModelQueryAdapter;
11import tools.refinery.store.query.dnf.RelationalQuery;
12import tools.refinery.store.dse.ActionFactory;
13import tools.refinery.store.query.resultset.OrderedResultSet;
14import tools.refinery.store.query.resultset.ResultSet;
15import tools.refinery.store.tuple.Tuple;
16
17import java.util.LinkedHashSet;
18import java.util.Random;
19
20public class TransformationRule {
21
22 private final String name;
23 private final RelationalQuery precondition;
24 private final ActionFactory actionFactory;
25 private Procedure<Tuple> action;
26 private OrderedResultSet<Boolean> activations;
27 private Random random;
28 private ModelQueryAdapter queryEngine;
29
30 public TransformationRule(String name, RelationalQuery precondition, ActionFactory actionFactory) {
31 this(name, precondition, actionFactory, new Random());
32 }
33
34 public TransformationRule(String name, RelationalQuery precondition, ActionFactory actionFactory, long seed) {
35 this(name, precondition, actionFactory, new Random(seed));
36 }
37
38 public TransformationRule(String name, RelationalQuery precondition, ActionFactory actionFactory, Random random) {
39 this.name = name;
40 this.precondition = precondition;
41 this.actionFactory = actionFactory;
42 this.random = random;
43 }
44 public boolean prepare(Model model, ModelQueryAdapter queryEngine) {
45 action = actionFactory.prepare(model);
46 this.queryEngine = queryEngine;
47 activations = new OrderedResultSet<>(queryEngine.getResultSet(precondition));
48 return true;
49 }
50
51 public boolean fireActivation(Tuple activation) {
52 action.accept(activation);
53 queryEngine.flushChanges();
54 return true;
55 }
56
57 public boolean fireRandomActivation() {
58 return getRandomActivation().fire();
59 }
60
61 public String getName() {
62 return name;
63 }
64
65 public RelationalQuery getPrecondition() {
66 return precondition;
67 }
68
69 public ResultSet<Boolean> getAllActivationsAsSets() {
70 return activations;
71 }
72
73 public LinkedHashSet<Activation> getAllActivations() {
74 var result = new LinkedHashSet<Activation>();
75 var cursor = activations.getAll();
76 while (cursor.move()) {
77 result.add(new Activation(this, cursor.getKey()));
78 }
79 return result;
80 }
81
82 public Activation getRandomActivation() {
83 return new Activation(this, activations.getKey(random.nextInt(activations.size())));
84 }
85
86 public Activation getActivation(int index) {
87 return new Activation(this, activations.getKey(index));
88 }
89}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java
new file mode 100644
index 00000000..afed75fd
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/AlwaysSatisfiedDummyHardObjective.java
@@ -0,0 +1,52 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.objectives;
11
12import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
13
14/**
15 * This hard objective is fulfilled in any circumstances. Use it if all states should be regarded as a valid solution.
16 *
17 * @author Andras Szabolcs Nagy
18 *
19 */
20public class AlwaysSatisfiedDummyHardObjective extends BaseObjective {
21
22 private static final String DEFAULT_NAME = "AlwaysSatisfiedDummyHardObjective";
23
24 public AlwaysSatisfiedDummyHardObjective() {
25 super(DEFAULT_NAME);
26 }
27
28 public AlwaysSatisfiedDummyHardObjective(String name) {
29 super(name);
30 }
31
32 @Override
33 public Double getFitness(DesignSpaceExplorationAdapter context) {
34 return 0d;
35 }
36
37 @Override
38 public boolean isHardObjective() {
39 return true;
40 }
41
42 @Override
43 public boolean satisfiesHardObjective(Double fitness) {
44 return true;
45 }
46
47 @Override
48 public Objective createNew() {
49 return this;
50 }
51
52}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java
new file mode 100644
index 00000000..7df33efe
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/BaseObjective.java
@@ -0,0 +1,132 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.objectives;
11
12import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
13
14import java.util.Comparator;
15import java.util.Objects;
16
17/**
18 * This abstract class implements the basic functionality of an objective ({@link Objective} namely its name,
19 * comparator, level and fitness hard constraint.
20 *
21 * @author Andras Szabolcs Nagy
22 *
23 */
24public abstract class BaseObjective implements Objective {
25
26 protected final String name;
27 protected Comparator<Double> comparator = Comparators.HIGHER_IS_BETTER;
28
29 protected double fitnessConstraint;
30 protected boolean isThereFitnessConstraint = false;
31 protected Comparator<Double> fitnessConstraintComparator;
32
33 public BaseObjective(String name) {
34 Objects.requireNonNull(name, "Name of the objective cannot be null.");
35 this.name = name;
36 }
37
38 @Override
39 public String getName() {
40 return name;
41 }
42
43 @Override
44 public void setComparator(Comparator<Double> comparator) {
45 this.comparator = comparator;
46 }
47
48 @Override
49 public Comparator<Double> getComparator() {
50 return comparator;
51 }
52
53 public BaseObjective withComparator(Comparator<Double> comparator) {
54 setComparator(comparator);
55 return this;
56 }
57
58 /**
59 * Adds a hard constraint on the fitness value. For example, the fitness value must be better than 10 to accept the
60 * current state as a solution.
61 *
62 * @param fitnessConstraint
63 * Solutions should be better than this value.
64 * @param fitnessConstraintComparator
65 * {@link Comparator} to determine if the current state is better than the given value.
66 * @return The actual instance to enable builder pattern like usage.
67 */
68 public BaseObjective withHardConstraintOnFitness(double fitnessConstraint,
69 Comparator<Double> fitnessConstraintComparator) {
70 this.fitnessConstraint = fitnessConstraint;
71 this.fitnessConstraintComparator = fitnessConstraintComparator;
72 this.isThereFitnessConstraint = true;
73 return this;
74 }
75
76 /**
77 * Adds a hard constraint on the fitness value. For example, the fitness value must be better than 10 to accept the
78 * current state as a solution. The provided comparator will be used.
79 *
80 * @param fitnessConstraint
81 * Solutions should be better than this value.
82 * @return The actual instance to enable builder pattern like usage.
83 */
84 public BaseObjective withHardConstraintOnFitness(double fitnessConstraint) {
85 return withHardConstraintOnFitness(fitnessConstraint, null);
86 }
87
88 @Override
89 public void init(DesignSpaceExplorationAdapter context) {
90 if (fitnessConstraintComparator == null) {
91 fitnessConstraintComparator = comparator;
92 }
93 }
94
95 @Override
96 public boolean isHardObjective() {
97 return isThereFitnessConstraint;
98 }
99
100 @Override
101 public boolean satisfiesHardObjective(Double fitness) {
102 if (isThereFitnessConstraint) {
103 int compare = fitnessConstraintComparator.compare(fitness, fitnessConstraint);
104 if (compare < 0) {
105 return false;
106 }
107 }
108 return true;
109 }
110
111 @Override
112 public int hashCode() {
113 return name.hashCode();
114 }
115
116 @Override
117 public boolean equals(Object obj) {
118 if (this == obj) {
119 return true;
120 }
121 if (obj instanceof BaseObjective baseObjective) {
122 return name.equals(baseObjective.getName());
123 }
124 return false;
125 }
126
127 @Override
128 public String toString() {
129 return name;
130 }
131
132}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java
new file mode 100644
index 00000000..476504b0
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Comparators.java
@@ -0,0 +1,26 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.objectives;
11
12import java.util.Comparator;
13
14public class Comparators {
15
16 private Comparators() { /*Utility class constructor*/ }
17
18 public static final Comparator<Double> HIGHER_IS_BETTER = (o1, o2) -> o1.compareTo(o2);
19
20 public static final Comparator<Double> LOWER_IS_BETTER = (o1, o2) -> o2.compareTo(o1);
21
22 private static final Double ZERO = (double) 0;
23
24 public static final Comparator<Double> DIFFERENCE_TO_ZERO_IS_BETTER = (o1, o2) -> ZERO.compareTo(Math.abs(o1)-Math.abs(o2));
25
26}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java
new file mode 100644
index 00000000..92709d3e
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Fitness.java
@@ -0,0 +1,30 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.objectives;
11
12import java.util.HashMap;
13
14public class Fitness extends HashMap<String, Double> {
15
16 private boolean satisfiesHardObjectives;
17
18 public boolean isSatisfiesHardObjectives() {
19 return satisfiesHardObjectives;
20 }
21
22 public void setSatisfiesHardObjectives(boolean satisfiesHardObjectives) {
23 this.satisfiesHardObjectives = satisfiesHardObjectives;
24 }
25
26 @Override
27 public String toString() {
28 return super.toString() + " hardObjectives=" + satisfiesHardObjectives;
29 }
30}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java
new file mode 100644
index 00000000..c7313622
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/Objective.java
@@ -0,0 +1,101 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2014, Miklos Foldenyi, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.objectives;
11
12import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
13
14import java.util.Comparator;
15
16/**
17 *
18 * Implementation of this interface represents a single objective of the DSE problem, which can assess a solution
19 * (trajectory) in a single number. It has a name and a comparator which orders two solution based on the calculated
20 * value.
21 * <p>
22 * Objectives can be either hard or soft objectives. Hard objectives can be satisfied or unsatisfied. If all of the hard
23 * objectives are satisfied on a single solution, then it is considered to be a valid (or goal) solution.
24 * <p>
25 * Certain objectives can have inner state for calculating the fitness value. In this case a new instance is necessary
26 * for every new thread, and the {@code createNew} method should not return the same instance more than once.
27 *
28 * @author Andras Szabolcs Nagy
29 *
30 */
31public interface Objective {
32
33 /**
34 * Returns the name of the objective.
35 *
36 * @return The name of the objective.
37 */
38 String getName();
39
40 /**
41 * Sets the {@link Comparator} which is used to compare fitness (doubles). It determines whether the objective is to
42 * minimize or maximize (or minimize or maximize a delta from a given number).
43 *
44 * @param comparator The comparator.
45 */
46 void setComparator(Comparator<Double> comparator);
47
48 /**
49 * Returns a {@link Comparator} which is used to compare fitness (doubles). It determines whether the objective is
50 * to minimize or maximize (or minimize or maximize a delta from a given number).
51 *
52 * @return The comparator.
53 */
54 Comparator<Double> getComparator();
55
56 /**
57 * Calculates the value of the objective on a given solution (trajectory).
58 *
59 * @param context
60 * The {@link DesignSpaceExplorationAdapter}
61 * @return The objective value in double.
62 */
63 Double getFitness(DesignSpaceExplorationAdapter context);
64
65 /**
66 * Initializes the objective. It is called exactly once for every thread starts.
67 *
68 * @param context
69 * The {@link DesignSpaceExplorationAdapter}.
70 */
71 void init(DesignSpaceExplorationAdapter context);
72
73 /**
74 * Returns an instance of the {@link Objective}. If it returns the same instance, all the methods has to be thread
75 * save as they are called concurrently.
76 *
77 * @return An instance of the objective.
78 */
79 Objective createNew();
80
81 /**
82 * Returns true if the objective is a hard objective. In such a case the method
83 * {@link Objective#satisfiesHardObjective(Double)} is called.
84 *
85 * @return True if the objective is a hard objective.
86 * @see Objective#satisfiesHardObjective(Double)
87 * @see Objective
88 */
89 boolean isHardObjective();
90
91 /**
92 * Determines if the given fitness value satisfies the hard objective.
93 *
94 * @param fitness
95 * The fitness value of a solution.
96 * @return True if it satisfies the hard objective or it is a soft constraint.
97 * @see Objective
98 */
99 boolean satisfiesHardObjective(Double fitness);
100
101}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java
new file mode 100644
index 00000000..1d676562
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/objectives/ObjectiveComparatorHelper.java
@@ -0,0 +1,59 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2015, Andras Szabolcs Nagy, Abel Hegedus, Akos Horvath, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.objectives;
11
12import java.util.List;
13
14/**
15 * This class is responsible to compare and sort fitness values.
16 *
17 * @author András Szabolcs Nagy
18 */
19public class ObjectiveComparatorHelper {
20
21 private final List<Objective> objectives;
22
23 public ObjectiveComparatorHelper(List<Objective> objectives) {
24 this.objectives = objectives;
25 }
26
27 /**
28 * Compares two fitnesses based on dominance. Returns -1 if the second parameter {@code o2} is a better
29 * solution ({@code o2} dominates {@code o1}), 1 if the first parameter {@code o1} is better ({@code o1} dominates
30 * {@code o2}) and returns 0 if they are non-dominating each other.
31 */
32 public int compare(Fitness o1, Fitness o2) {
33
34 boolean o1HasBetterFitness = false;
35 boolean o2HasBetterFitness = false;
36
37 for (Objective objective : objectives) {
38 String objectiveName = objective.getName();
39 int sgn = objective.getComparator().compare(o1.get(objectiveName), o2.get(objectiveName));
40
41 if (sgn < 0) {
42 o2HasBetterFitness = true;
43 }
44 if (sgn > 0) {
45 o1HasBetterFitness = true;
46 }
47 if (o1HasBetterFitness && o2HasBetterFitness) {
48 break;
49 }
50 }
51 if (o2HasBetterFitness) {
52 } else if (o1HasBetterFitness) {
53 return 1;
54 }
55
56 return 0;
57
58 }
59}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java
new file mode 100644
index 00000000..8648864c
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/BestFirstStrategy.java
@@ -0,0 +1,199 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.strategy;
11
12import tools.refinery.store.map.Version;
13import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
14import tools.refinery.store.dse.Strategy;
15import tools.refinery.store.dse.internal.Activation;
16import tools.refinery.store.dse.objectives.Fitness;
17import tools.refinery.store.dse.objectives.ObjectiveComparatorHelper;
18
19import java.util.Collection;
20import java.util.Iterator;
21import java.util.List;
22import java.util.PriorityQueue;
23
24public class BestFirstStrategy implements Strategy {
25
26 private DesignSpaceExplorationAdapter dseAdapter;
27
28 private int maxDepth;
29 private boolean backTrackIfSolution = true;
30 private boolean onlyBetterFirst = false;
31
32 private PriorityQueue<TrajectoryWithFitness> trajectoriesToExplore;
33
34 private static class TrajectoryWithFitness {
35
36 public List<Version> trajectory;
37 public Fitness fitness;
38
39 public TrajectoryWithFitness(List<Version> trajectory, Fitness fitness) {
40 super();
41 this.trajectory = trajectory;
42 this.fitness = fitness;
43 }
44
45 @Override
46 public String toString() {
47 return trajectory.toString() + fitness.toString();
48 }
49
50 }
51
52 public BestFirstStrategy() {
53 this(-1);
54 }
55
56 public BestFirstStrategy(int maxDepth) {
57 if (maxDepth < 0) {
58 this.maxDepth = Integer.MAX_VALUE;
59 } else {
60 this.maxDepth = maxDepth;
61 }
62 }
63
64 public BestFirstStrategy continueIfHardObjectivesFulfilled() {
65 backTrackIfSolution = false;
66 return this;
67 }
68
69 public BestFirstStrategy goOnOnlyIfFitnessIsBetter() {
70 onlyBetterFirst = true;
71 return this;
72 }
73
74 @Override
75 public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) {
76 this.dseAdapter = designSpaceExplorationAdapter;
77 final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper();
78
79 trajectoriesToExplore = new PriorityQueue<TrajectoryWithFitness>(11,
80 (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness));
81 }
82
83 @Override
84 public void explore() {
85 final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper();
86
87 boolean globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints();
88 if (!globalConstraintsAreSatisfied) {
89 // "Global constraint is not satisfied in the first state. Terminate.");
90 return;
91 }
92
93 final Fitness firstFitness = dseAdapter.calculateFitness();
94 if (firstFitness.isSatisfiesHardObjectives()) {
95 dseAdapter.newSolution();
96 // "First state is a solution. Terminate.");
97 if (backTrackIfSolution) {
98 return;
99 }
100 }
101
102 if (maxDepth == 0) {
103 return;
104 }
105
106 final List<Version> firstTrajectory = dseAdapter.getTrajectory();
107 TrajectoryWithFitness currentTrajectoryWithFitness = new TrajectoryWithFitness(firstTrajectory, firstFitness);
108 trajectoriesToExplore.add(currentTrajectoryWithFitness);
109
110 mainLoop: while (true) {
111
112 if (currentTrajectoryWithFitness == null) {
113 if (trajectoriesToExplore.isEmpty()) {
114 // "State space is fully traversed.");
115 return;
116 } else {
117 currentTrajectoryWithFitness = trajectoriesToExplore.element();
118// if (logger.isDebugEnabled()) {
119// "New trajectory is chosen: " + currentTrajectoryWithFitness);
120// }
121 dseAdapter.restoreTrajectory(currentTrajectoryWithFitness.trajectory);
122 }
123 }
124
125 Collection<Activation> activations = dseAdapter.getUntraversedActivations();
126 Iterator<Activation> iterator = activations.iterator();
127
128
129
130 while (iterator.hasNext()) {
131 final Activation nextActivation = iterator.next();
132 if (!iterator.hasNext()) {
133 // "Last untraversed activation of the state.");
134 trajectoriesToExplore.remove(currentTrajectoryWithFitness);
135 }
136
137// if (logger.isDebugEnabled()) {
138// "Executing new activation: " + nextActivation);
139// }
140 dseAdapter.fireActivation(nextActivation);
141 if (dseAdapter.isCurrentStateAlreadyTraversed()) {
142 // "The new state is already visited.");
143 dseAdapter.backtrack();
144 } else if (!dseAdapter.checkGlobalConstraints()) {
145 // "Global constraint is not satisfied.");
146 dseAdapter.backtrack();
147 } else {
148 final Fitness nextFitness = dseAdapter.calculateFitness();
149 if (nextFitness.isSatisfiesHardObjectives()) {
150 dseAdapter.newSolution();
151 // "Found a solution.");
152 if (backTrackIfSolution) {
153 dseAdapter.backtrack();
154 continue;
155 }
156 }
157 if (dseAdapter.getDepth() >= maxDepth) {
158 // "Reached max depth.");
159 dseAdapter.backtrack();
160 continue;
161 }
162
163 TrajectoryWithFitness nextTrajectoryWithFitness = new TrajectoryWithFitness(
164 dseAdapter.getTrajectory(), nextFitness);
165 trajectoriesToExplore.add(nextTrajectoryWithFitness);
166
167 int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFitness.fitness,
168 nextTrajectoryWithFitness.fitness);
169 if (compare < 0) {
170 // "Better fitness, moving on: " + nextFitness);
171 currentTrajectoryWithFitness = nextTrajectoryWithFitness;
172 continue mainLoop;
173 } else if (compare == 0) {
174 if (onlyBetterFirst) {
175 // "Equally good fitness, backtrack: " + nextFitness);
176 dseAdapter.backtrack();
177 continue;
178 } else {
179 // "Equally good fitness, moving on: " + nextFitness);
180 currentTrajectoryWithFitness = nextTrajectoryWithFitness;
181 continue mainLoop;
182 }
183 } else {
184 // "Worse fitness.");
185 currentTrajectoryWithFitness = null;
186 continue mainLoop;
187 }
188 }
189 }
190
191 // "State is fully traversed.");
192 trajectoriesToExplore.remove(currentTrajectoryWithFitness);
193 currentTrajectoryWithFitness = null;
194
195 }
196 // "Interrupted.");
197
198 }
199}
diff --git a/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java
new file mode 100644
index 00000000..1405789b
--- /dev/null
+++ b/subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java
@@ -0,0 +1,117 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro
3 * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v. 2.0 which is available at
6 * http://www.eclipse.org/legal/epl-v20.html.
7 *
8 * SPDX-License-Identifier: EPL-2.0
9 *******************************************************************************/
10package tools.refinery.store.dse.strategy;
11
12import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
13import tools.refinery.store.dse.Strategy;
14import tools.refinery.store.dse.internal.Activation;
15import tools.refinery.store.dse.objectives.Fitness;
16
17import java.util.Collection;
18
19public class DepthFirstStrategy implements Strategy {
20
21 private DesignSpaceExplorationAdapter dseAdapter;
22
23 private int maxDepth;
24 private boolean backTrackIfSolution = true;
25
26 public DepthFirstStrategy() {
27 this(-1);
28 }
29
30 public DepthFirstStrategy(int maxDepth) {
31 if (maxDepth < 0) {
32 this.maxDepth = Integer.MAX_VALUE;
33 } else {
34 this.maxDepth = maxDepth;
35 }
36 }
37
38 public DepthFirstStrategy continueIfHardObjectivesFulfilled() {
39 backTrackIfSolution = false;
40 return this;
41 }
42
43 @Override
44 public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) {
45 this.dseAdapter = designSpaceExplorationAdapter;
46 }
47
48 @Override
49 public void explore() {
50 mainloop: while (true) {
51 var globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints();
52 if (!globalConstraintsAreSatisfied) {
53 var isSuccessfulUndo = dseAdapter.backtrack();
54 if (!isSuccessfulUndo) {
55// "Global constraint is not satisfied and cannot backtrack."
56 break;
57 }
58 else {
59// "Global constraint is not satisfied, backtrack."
60 continue;
61 }
62 }
63
64 Fitness fitness = dseAdapter.calculateFitness();
65 if (fitness.isSatisfiesHardObjectives()) {
66 dseAdapter.newSolution();
67 if (backTrackIfSolution) {
68 var isSuccessfulUndo = dseAdapter.backtrack();
69 if (!isSuccessfulUndo) {
70// "Found a solution but cannot backtrack."
71 break;
72 } else {
73// "Found a solution, backtrack."
74 continue;
75 }
76 }
77 }
78
79 var depth = dseAdapter.getDepth();
80 if (dseAdapter.getDepth() >= maxDepth) {
81 var isSuccessfulUndo = dseAdapter.backtrack();
82 if (!isSuccessfulUndo) {
83// "Reached max depth but cannot backtrack."
84 break;
85 }
86 }
87
88 Collection<Activation> activations;
89 do {
90 activations = dseAdapter.getUntraversedActivations();
91 if (activations.isEmpty()) {
92 if (!dseAdapter.backtrack()) {
93 // "No more transitions from current state and cannot backtrack."
94 break mainloop;
95 }
96 else {
97 // "No more transitions from current state, backtrack."
98 continue;
99 }
100 }
101 } while (activations.isEmpty());
102
103 dseAdapter.fireRandomActivation();
104// if (dseAdapter.isCurrentInTrajectory()) {
105// if (!dseAdapter.backtrack()) {
106//// TODO: throw exception
107//// "The new state is present in the trajectory but cannot backtrack. Should never happen!"
108// break;
109// }
110// else {
111//// "The new state is already visited in the trajectory, backtrack."
112// continue;
113// }
114// }
115 }
116 }
117}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-09-16 05:24:48 +0000