diff options
author | Attila Ficsor <ficsorattila96@gmail.com> | 2023-08-08 13:57:19 +0200 |
---|---|---|
committer | Attila Ficsor <ficsorattila96@gmail.com> | 2023-08-08 14:33:16 +0200 |
commit | 1f853e4590d7f235bf8a63fa017fc92369a80a5a (patch) | |
tree | bd586d45d473b68a8d26fba2808e0489ab469217 /subprojects/store-dse/src/main | |
parent | Improve performance of best first earch (diff) | |
download | refinery-1f853e4590d7f235bf8a63fa017fc92369a80a5a.tar.gz refinery-1f853e4590d7f235bf8a63fa017fc92369a80a5a.tar.zst refinery-1f853e4590d7f235bf8a63fa017fc92369a80a5a.zip |
Refactor search strategy to improve readability
Diffstat (limited to 'subprojects/store-dse/src/main')
4 files changed, 34 insertions, 62 deletions
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 index 409fe8a6..c60a4410 100644 --- 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 | |||
@@ -7,7 +7,7 @@ package tools.refinery.store.dse; | |||
7 | 7 | ||
8 | public interface Strategy { | 8 | public interface Strategy { |
9 | 9 | ||
10 | void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter); | 10 | void initialize(DesignSpaceExplorationAdapter designSpaceExplorationAdapter); |
11 | 11 | ||
12 | void explore(); | 12 | void explore(); |
13 | } | 13 | } |
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 index 008b2dab..04bba885 100644 --- 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 | |||
@@ -52,10 +52,6 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
52 | 52 | ||
53 | private final Map<Version, Fitness> fitnessCache = new HashMap<>(); | 53 | private final Map<Version, Fitness> fitnessCache = new HashMap<>(); |
54 | 54 | ||
55 | public List<Version> getTrajectory() { | ||
56 | return new ArrayList<>(trajectory); | ||
57 | } | ||
58 | |||
59 | public DesignSpaceExplorationAdapterImpl(Model model, DesignSpaceExplorationStoreAdapterImpl storeAdapter) { | 55 | public DesignSpaceExplorationAdapterImpl(Model model, DesignSpaceExplorationStoreAdapterImpl storeAdapter) { |
60 | this.model = model; | 56 | this.model = model; |
61 | this.storeAdapter = storeAdapter; | 57 | this.storeAdapter = storeAdapter; |
@@ -75,11 +71,16 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
75 | objectives = storeAdapter.getObjectives(); | 71 | objectives = storeAdapter.getObjectives(); |
76 | statesAndTraversedActivations = new HashMap<>(); | 72 | statesAndTraversedActivations = new HashMap<>(); |
77 | strategy = storeAdapter.getStrategy(); | 73 | strategy = storeAdapter.getStrategy(); |
74 | strategy.initialize(this); | ||
78 | modelVisualizerAdapter = model.tryGetAdapter(ModelVisualizerAdapter.class).orElse(null); | 75 | modelVisualizerAdapter = model.tryGetAdapter(ModelVisualizerAdapter.class).orElse(null); |
79 | isVisualizationEnabled = modelVisualizerAdapter != null; | 76 | isVisualizationEnabled = modelVisualizerAdapter != null; |
80 | 77 | ||
81 | } | 78 | } |
82 | 79 | ||
80 | public List<Version> getTrajectory() { | ||
81 | return new ArrayList<>(trajectory); | ||
82 | } | ||
83 | |||
83 | @Override | 84 | @Override |
84 | public Model getModel() { | 85 | public Model getModel() { |
85 | return model; | 86 | return model; |
@@ -94,7 +95,6 @@ public class DesignSpaceExplorationAdapterImpl implements DesignSpaceExploration | |||
94 | public List<Version> explore() { | 95 | public List<Version> explore() { |
95 | var state = model.commit(); | 96 | var state = model.commit(); |
96 | trajectory.add(state); | 97 | trajectory.add(state); |
97 | strategy.initStrategy(this); | ||
98 | strategy.explore(); | 98 | strategy.explore(); |
99 | if (isVisualizationEnabled) { | 99 | if (isVisualizationEnabled) { |
100 | modelVisualizerAdapter.visualize(); | 100 | modelVisualizerAdapter.visualize(); |
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 index 0883d3d7..047b204a 100644 --- 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 | |||
@@ -22,8 +22,8 @@ public class BestFirstStrategy implements Strategy { | |||
22 | 22 | ||
23 | private DesignSpaceExplorationAdapter dseAdapter; | 23 | private DesignSpaceExplorationAdapter dseAdapter; |
24 | 24 | ||
25 | private final int maxDepth; | 25 | private int maxDepth = Integer.MAX_VALUE; |
26 | private final int maxSolutions; | 26 | private int maxSolutions = Integer.MAX_VALUE; |
27 | private boolean backTrackIfSolution = true; | 27 | private boolean backTrackIfSolution = true; |
28 | private boolean onlyBetterFirst = false; | 28 | private boolean onlyBetterFirst = false; |
29 | 29 | ||
@@ -50,25 +50,18 @@ public class BestFirstStrategy implements Strategy { | |||
50 | } | 50 | } |
51 | } | 51 | } |
52 | 52 | ||
53 | public BestFirstStrategy() { | 53 | public BestFirstStrategy withDepthLimit(int maxDepth) { |
54 | this(-1); | 54 | if (maxDepth >= 0) { |
55 | } | ||
56 | |||
57 | public BestFirstStrategy(int maxDepth) { | ||
58 | this(maxDepth, -1); | ||
59 | } | ||
60 | |||
61 | public BestFirstStrategy(int maxDepth, int maxSolutions) { | ||
62 | if (maxDepth < 0) { | ||
63 | this.maxDepth = Integer.MAX_VALUE; | ||
64 | } else { | ||
65 | this.maxDepth = maxDepth; | 55 | this.maxDepth = maxDepth; |
66 | } | 56 | } |
67 | if (maxSolutions < 0) { | 57 | return this; |
68 | this.maxSolutions = Integer.MAX_VALUE; | 58 | } |
69 | } else { | 59 | |
60 | public BestFirstStrategy withSolutionLimit(int maxSolutions) { | ||
61 | if (maxSolutions >= 0) { | ||
70 | this.maxSolutions = maxSolutions; | 62 | this.maxSolutions = maxSolutions; |
71 | } | 63 | } |
64 | return this; | ||
72 | } | 65 | } |
73 | 66 | ||
74 | public BestFirstStrategy continueIfHardObjectivesFulfilled() { | 67 | public BestFirstStrategy continueIfHardObjectivesFulfilled() { |
@@ -82,7 +75,7 @@ public class BestFirstStrategy implements Strategy { | |||
82 | } | 75 | } |
83 | 76 | ||
84 | @Override | 77 | @Override |
85 | public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { | 78 | public void initialize(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { |
86 | this.dseAdapter = designSpaceExplorationAdapter; | 79 | this.dseAdapter = designSpaceExplorationAdapter; |
87 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); | 80 | final ObjectiveComparatorHelper objectiveComparatorHelper = dseAdapter.getObjectiveComparatorHelper(); |
88 | 81 | ||
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 index 425e1e01..5f7f61b8 100644 --- 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 | |||
@@ -1,12 +1,8 @@ | |||
1 | /******************************************************************************* | 1 | /* |
2 | * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro | 2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> |
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 | * | 3 | * |
8 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
9 | *******************************************************************************/ | 5 | */ |
10 | package tools.refinery.store.dse.strategy; | 6 | package tools.refinery.store.dse.strategy; |
11 | 7 | ||
12 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; | 8 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; |
@@ -17,38 +13,31 @@ public class DepthFirstStrategy implements Strategy { | |||
17 | 13 | ||
18 | private DesignSpaceExplorationAdapter dseAdapter; | 14 | private DesignSpaceExplorationAdapter dseAdapter; |
19 | 15 | ||
20 | private int maxDepth; | 16 | private int maxDepth = Integer.MAX_VALUE; |
21 | private int maxSolutions; | 17 | private int maxSolutions = Integer.MAX_VALUE; |
22 | private boolean backTrackIfSolution = true; | 18 | private boolean backtrackFromSolution = true; |
23 | 19 | ||
24 | public DepthFirstStrategy() { | 20 | public DepthFirstStrategy withDepthLimit(int maxDepth) { |
25 | this(-1); | 21 | if (maxDepth >= 0) { |
26 | } | ||
27 | |||
28 | public DepthFirstStrategy(int maxDepth) { | ||
29 | this(maxDepth, -1); | ||
30 | } | ||
31 | |||
32 | public DepthFirstStrategy(int maxDepth, int maxSolutions) { | ||
33 | if (maxDepth < 0) { | ||
34 | this.maxDepth = Integer.MAX_VALUE; | ||
35 | } else { | ||
36 | this.maxDepth = maxDepth; | 22 | this.maxDepth = maxDepth; |
37 | } | 23 | } |
38 | if (maxSolutions < 0) { | 24 | return this; |
39 | this.maxSolutions = Integer.MAX_VALUE; | 25 | } |
40 | } else { | 26 | |
27 | public DepthFirstStrategy withSolutionLimit(int maxSolutions) { | ||
28 | if (maxSolutions >= 0) { | ||
41 | this.maxSolutions = maxSolutions; | 29 | this.maxSolutions = maxSolutions; |
42 | } | 30 | } |
31 | return this; | ||
43 | } | 32 | } |
44 | 33 | ||
45 | public DepthFirstStrategy continueIfHardObjectivesFulfilled() { | 34 | public DepthFirstStrategy continueIfHardObjectivesFulfilled() { |
46 | backTrackIfSolution = false; | 35 | backtrackFromSolution = false; |
47 | return this; | 36 | return this; |
48 | } | 37 | } |
49 | 38 | ||
50 | @Override | 39 | @Override |
51 | public void initStrategy(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { | 40 | public void initialize(DesignSpaceExplorationAdapter designSpaceExplorationAdapter) { |
52 | this.dseAdapter = designSpaceExplorationAdapter; | 41 | this.dseAdapter = designSpaceExplorationAdapter; |
53 | } | 42 | } |
54 | 43 | ||
@@ -59,22 +48,18 @@ public class DepthFirstStrategy implements Strategy { | |||
59 | } | 48 | } |
60 | while (dseAdapter.getSolutions().size() < maxSolutions) { | 49 | while (dseAdapter.getSolutions().size() < maxSolutions) { |
61 | if (!checkAndHandleGlobalConstraints()) { | 50 | if (!checkAndHandleGlobalConstraints()) { |
62 | // Global constraint is not satisfied and cannot backtrack. | ||
63 | return; | 51 | return; |
64 | } | 52 | } |
65 | // Global constraint is not satisfied, backtrack. | ||
66 | 53 | ||
67 | Fitness fitness = dseAdapter.getFitness(); | 54 | Fitness fitness = dseAdapter.getFitness(); |
68 | if (fitness.isSatisfiesHardObjectives()) { | 55 | if (fitness.isSatisfiesHardObjectives()) { |
69 | dseAdapter.newSolution(); | 56 | dseAdapter.newSolution(); |
70 | if (backTrackIfSolution && !dseAdapter.backtrack()) { | 57 | if (backtrackFromSolution && !dseAdapter.backtrack()) { |
71 | // Found a solution but cannot backtrack. | ||
72 | return; | 58 | return; |
73 | } | 59 | } |
74 | } | 60 | } |
75 | 61 | ||
76 | if (!checkAndHandleDepth()) { | 62 | if (!checkAndHandleDepth()) { |
77 | // Reached max depth but cannot backtrack. | ||
78 | return; | 63 | return; |
79 | } | 64 | } |
80 | 65 | ||
@@ -87,24 +72,18 @@ public class DepthFirstStrategy implements Strategy { | |||
87 | } | 72 | } |
88 | 73 | ||
89 | private boolean checkAndHandleGlobalConstraints() { | 74 | private boolean checkAndHandleGlobalConstraints() { |
90 | // Global constraint is not satisfied and cannot backtrack. | ||
91 | return dseAdapter.checkGlobalConstraints() || dseAdapter.backtrack(); | 75 | return dseAdapter.checkGlobalConstraints() || dseAdapter.backtrack(); |
92 | // Global constraint is satisfied or backtrack. | ||
93 | } | 76 | } |
94 | 77 | ||
95 | private boolean checkAndHandleDepth() { | 78 | private boolean checkAndHandleDepth() { |
96 | // Reached max depth but cannot backtrack. | ||
97 | return dseAdapter.getDepth() < maxDepth || dseAdapter.backtrack(); | 79 | return dseAdapter.getDepth() < maxDepth || dseAdapter.backtrack(); |
98 | // Reached max depth or backtrack. | ||
99 | } | 80 | } |
100 | 81 | ||
101 | private boolean backtrackToLastUntraversed() { | 82 | private boolean backtrackToLastUntraversed() { |
102 | while (dseAdapter.getUntraversedActivations().isEmpty()) { | 83 | while (dseAdapter.getUntraversedActivations().isEmpty()) { |
103 | if (!dseAdapter.backtrack()) { | 84 | if (!dseAdapter.backtrack()) { |
104 | // No more transitions from current state and cannot backtrack. | ||
105 | return false; | 85 | return false; |
106 | } | 86 | } |
107 | // No more transitions from current state, backtrack. | ||
108 | } | 87 | } |
109 | return true; | 88 | return true; |
110 | } | 89 | } |