diff options
author | Attila Ficsor <ficsorattila96@gmail.com> | 2023-08-07 16:23:57 +0200 |
---|---|---|
committer | Attila Ficsor <ficsorattila96@gmail.com> | 2023-08-08 13:17:03 +0200 |
commit | 0c26310fc48b5359da11b32b04e008e64f91c10e (patch) | |
tree | 3b10c8bf1233b4e5cfaad1ebfe65882de03b1cd9 /subprojects/store-dse/src/main/java/tools | |
parent | Remove visualization from DSE tests (diff) | |
download | refinery-0c26310fc48b5359da11b32b04e008e64f91c10e.tar.gz refinery-0c26310fc48b5359da11b32b04e008e64f91c10e.tar.zst refinery-0c26310fc48b5359da11b32b04e008e64f91c10e.zip |
Reduce complexity of Depth first search
Diffstat (limited to 'subprojects/store-dse/src/main/java/tools')
-rw-r--r-- | subprojects/store-dse/src/main/java/tools/refinery/store/dse/strategy/DepthFirstStrategy.java | 89 |
1 files changed, 36 insertions, 53 deletions
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 15529371..425e1e01 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 | |||
@@ -11,11 +11,8 @@ package tools.refinery.store.dse.strategy; | |||
11 | 11 | ||
12 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; | 12 | import tools.refinery.store.dse.DesignSpaceExplorationAdapter; |
13 | import tools.refinery.store.dse.Strategy; | 13 | import tools.refinery.store.dse.Strategy; |
14 | import tools.refinery.store.dse.internal.Activation; | ||
15 | import tools.refinery.store.dse.objectives.Fitness; | 14 | import tools.refinery.store.dse.objectives.Fitness; |
16 | 15 | ||
17 | import java.util.Collection; | ||
18 | |||
19 | public class DepthFirstStrategy implements Strategy { | 16 | public class DepthFirstStrategy implements Strategy { |
20 | 17 | ||
21 | private DesignSpaceExplorationAdapter dseAdapter; | 18 | private DesignSpaceExplorationAdapter dseAdapter; |
@@ -60,69 +57,55 @@ public class DepthFirstStrategy implements Strategy { | |||
60 | if (maxSolutions == 0) { | 57 | if (maxSolutions == 0) { |
61 | return; | 58 | return; |
62 | } | 59 | } |
63 | mainloop: while (true) { | 60 | while (dseAdapter.getSolutions().size() < maxSolutions) { |
64 | var globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints(); | 61 | if (!checkAndHandleGlobalConstraints()) { |
65 | if (!globalConstraintsAreSatisfied) { | 62 | // Global constraint is not satisfied and cannot backtrack. |
66 | var isSuccessfulUndo = dseAdapter.backtrack(); | 63 | return; |
67 | if (!isSuccessfulUndo) { | ||
68 | // Global constraint is not satisfied and cannot backtrack. | ||
69 | break; | ||
70 | } | ||
71 | else { | ||
72 | // Global constraint is not satisfied, backtrack. | ||
73 | continue; | ||
74 | } | ||
75 | } | 64 | } |
65 | // Global constraint is not satisfied, backtrack. | ||
76 | 66 | ||
77 | Fitness fitness = dseAdapter.getFitness(); | 67 | Fitness fitness = dseAdapter.getFitness(); |
78 | if (fitness.isSatisfiesHardObjectives()) { | 68 | if (fitness.isSatisfiesHardObjectives()) { |
79 | dseAdapter.newSolution(); | 69 | dseAdapter.newSolution(); |
80 | var solutions = dseAdapter.getSolutions().size(); | 70 | if (backTrackIfSolution && !dseAdapter.backtrack()) { |
81 | if (solutions >= maxSolutions) { | 71 | // Found a solution but cannot backtrack. |
82 | return; | 72 | return; |
83 | } | 73 | } |
84 | if (backTrackIfSolution) { | ||
85 | var isSuccessfulUndo = dseAdapter.backtrack(); | ||
86 | if (!isSuccessfulUndo) { | ||
87 | // Found a solution but cannot backtrack. | ||
88 | break; | ||
89 | } else { | ||
90 | // Found a solution, backtrack. | ||
91 | continue; | ||
92 | } | ||
93 | } | ||
94 | } | 74 | } |
95 | 75 | ||
96 | if (dseAdapter.getDepth() >= maxDepth) { | 76 | if (!checkAndHandleDepth()) { |
97 | var isSuccessfulUndo = dseAdapter.backtrack(); | 77 | // Reached max depth but cannot backtrack. |
98 | if (!isSuccessfulUndo) { | 78 | return; |
99 | // Reached max depth but cannot backtrack. | ||
100 | break; | ||
101 | } | ||
102 | } | 79 | } |
103 | 80 | ||
104 | Collection<Activation> activations; | 81 | if (!backtrackToLastUntraversed()) { |
105 | do { | 82 | return; |
106 | activations = dseAdapter.getUntraversedActivations(); | 83 | } |
107 | if (activations.isEmpty() && !dseAdapter.backtrack()) { | ||
108 | // No more transitions from current state and cannot backtrack. | ||
109 | break mainloop; | ||
110 | } | ||
111 | // No more transitions from current state, backtrack. | ||
112 | } while (activations.isEmpty()); | ||
113 | 84 | ||
114 | dseAdapter.fireRandomActivation(); | 85 | dseAdapter.fireRandomActivation(); |
115 | // if (dseAdapter.isCurrentInTrajectory()) { | ||
116 | // if (!dseAdapter.backtrack()) { | ||
117 | //// TODO: throw exception | ||
118 | //// "The new state is present in the trajectory but cannot backtrack. Should never happen!" | ||
119 | // break; | ||
120 | // } | ||
121 | // else { | ||
122 | //// "The new state is already visited in the trajectory, backtrack." | ||
123 | // continue; | ||
124 | // } | ||
125 | // } | ||
126 | } | 86 | } |
127 | } | 87 | } |
88 | |||
89 | private boolean checkAndHandleGlobalConstraints() { | ||
90 | // Global constraint is not satisfied and cannot backtrack. | ||
91 | return dseAdapter.checkGlobalConstraints() || dseAdapter.backtrack(); | ||
92 | // Global constraint is satisfied or backtrack. | ||
93 | } | ||
94 | |||
95 | private boolean checkAndHandleDepth() { | ||
96 | // Reached max depth but cannot backtrack. | ||
97 | return dseAdapter.getDepth() < maxDepth || dseAdapter.backtrack(); | ||
98 | // Reached max depth or backtrack. | ||
99 | } | ||
100 | |||
101 | private boolean backtrackToLastUntraversed() { | ||
102 | while (dseAdapter.getUntraversedActivations().isEmpty()) { | ||
103 | if (!dseAdapter.backtrack()) { | ||
104 | // No more transitions from current state and cannot backtrack. | ||
105 | return false; | ||
106 | } | ||
107 | // No more transitions from current state, backtrack. | ||
108 | } | ||
109 | return true; | ||
110 | } | ||
128 | } | 111 | } |