diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java')
-rw-r--r-- | Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java new file mode 100644 index 00000000..4ccda4ce --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/FixedPriorityStrategy.java | |||
@@ -0,0 +1,208 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | package org.eclipse.viatra.dse.api.strategy.impl; | ||
10 | |||
11 | import java.util.Collection; | ||
12 | import java.util.HashMap; | ||
13 | import java.util.List; | ||
14 | import java.util.Map; | ||
15 | import java.util.Random; | ||
16 | import java.util.concurrent.atomic.AtomicBoolean; | ||
17 | |||
18 | import org.apache.log4j.Logger; | ||
19 | import org.eclipse.viatra.dse.api.DSEException; | ||
20 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
21 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
22 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
23 | import org.eclipse.viatra.transformation.runtime.emf.rules.batch.BatchTransformationRule; | ||
24 | |||
25 | import com.google.common.collect.Lists; | ||
26 | |||
27 | /** | ||
28 | * Works as {@link DepthFirstStrategy} but: | ||
29 | * <ul> | ||
30 | * <li>works only with single thread,</li> | ||
31 | * <li>in a given state, it only traverses the activations with locally the highest priority.</li> | ||
32 | * </ul> | ||
33 | * | ||
34 | * @author Andras Szabolcs Nagy | ||
35 | * | ||
36 | */ | ||
37 | public class FixedPriorityStrategy implements IStrategy { | ||
38 | |||
39 | private int maxDepth = Integer.MAX_VALUE; | ||
40 | private AtomicBoolean isInterrupted = new AtomicBoolean(false); | ||
41 | private ThreadContext context; | ||
42 | |||
43 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
44 | private Map<BatchTransformationRule<?, ?>, Integer> priorities = new HashMap<BatchTransformationRule<?, ?>, Integer>(); | ||
45 | |||
46 | private Random random = new Random(); | ||
47 | private Map<Object, List<Object>> bestPriorityInState = new HashMap<>(); | ||
48 | |||
49 | /** | ||
50 | * Adds a depth limit to the strategy. | ||
51 | * | ||
52 | * @param depthLimit | ||
53 | * The depth limit. | ||
54 | * @return The actual instance to enable a builder pattern like usage. | ||
55 | */ | ||
56 | public FixedPriorityStrategy withDepthLimit(int maxDepth) { | ||
57 | if (maxDepth < 0) { | ||
58 | this.maxDepth = Integer.MAX_VALUE; | ||
59 | } else { | ||
60 | this.maxDepth = maxDepth; | ||
61 | } | ||
62 | return this; | ||
63 | } | ||
64 | |||
65 | /** | ||
66 | * Assigns a priority to a rule. Unassigned rule will have a priority of 0. | ||
67 | * | ||
68 | * @param rule | ||
69 | * The transformation rule. | ||
70 | * @param priority | ||
71 | * The priority of the rule. Higher is better. | ||
72 | * @return The actual instance to enable a builder pattern like usage. | ||
73 | */ | ||
74 | public FixedPriorityStrategy withRulePriority(BatchTransformationRule<?, ?> rule, int priority) { | ||
75 | priorities.put(rule, priority); | ||
76 | return this; | ||
77 | } | ||
78 | |||
79 | public Map<BatchTransformationRule<?, ?>, Integer> getPriorities() { | ||
80 | return priorities; | ||
81 | } | ||
82 | |||
83 | @Override | ||
84 | public void initStrategy(ThreadContext context) { | ||
85 | this.context = context; | ||
86 | |||
87 | logger.info("Fixed priority exploration strategy is initied."); | ||
88 | } | ||
89 | |||
90 | @Override | ||
91 | public void explore() { | ||
92 | |||
93 | mainloop: do { | ||
94 | |||
95 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
96 | if (!globalConstraintsAreSatisfied) { | ||
97 | boolean isSuccessfulUndo = context.backtrack(); | ||
98 | if (!isSuccessfulUndo) { | ||
99 | logger.info("Global contraint is not satisifed and cannot backtrack."); | ||
100 | break; | ||
101 | } else { | ||
102 | logger.debug("Global contraint is not satisifed, backtrack."); | ||
103 | continue; | ||
104 | } | ||
105 | } | ||
106 | |||
107 | Fitness fitness = context.calculateFitness(); | ||
108 | if (fitness.isSatisifiesHardObjectives()) { | ||
109 | context.newSolution(); | ||
110 | boolean isSuccessfulUndo = context.backtrack(); | ||
111 | if (!isSuccessfulUndo) { | ||
112 | logger.info("Found a solution but cannot backtrack."); | ||
113 | break; | ||
114 | } else { | ||
115 | logger.debug("Found a solution, backtrack."); | ||
116 | continue; | ||
117 | } | ||
118 | } | ||
119 | |||
120 | if (context.getDepth() >= maxDepth) { | ||
121 | boolean isSuccessfulUndo = context.backtrack(); | ||
122 | if (!isSuccessfulUndo) { | ||
123 | logger.info("Reached max depth but cannot bactrack."); | ||
124 | break; | ||
125 | } else { | ||
126 | logger.debug("Reached max depth, bactrack."); | ||
127 | continue; | ||
128 | } | ||
129 | } | ||
130 | |||
131 | if (isInterrupted.get()) { | ||
132 | logger.info("Interrupted, stop exploration."); | ||
133 | break; | ||
134 | } | ||
135 | |||
136 | List<Object> transitions; | ||
137 | |||
138 | do { | ||
139 | |||
140 | transitions = bestPriorityInState.get(context.getCurrentStateId()); | ||
141 | |||
142 | if (transitions == null) { | ||
143 | Integer bestPriority = getBestPriority(context.getCurrentActivationIds()); | ||
144 | transitions = Lists.newArrayList(); | ||
145 | for (Object iTransition : context.getCurrentActivationIds()) { | ||
146 | Integer integer = priorities.get(context.getRuleByActivationId(iTransition)); | ||
147 | if (integer == null) { | ||
148 | integer = Integer.valueOf(0); | ||
149 | } | ||
150 | if (integer.equals(bestPriority)) { | ||
151 | transitions.add(iTransition); | ||
152 | } | ||
153 | } | ||
154 | bestPriorityInState.put(context.getCurrentStateId(), transitions); | ||
155 | } | ||
156 | |||
157 | if (transitions.isEmpty()) { | ||
158 | boolean isSuccessfulUndo = context.backtrack(); | ||
159 | if (!isSuccessfulUndo) { | ||
160 | logger.info("No more transitions from current state and cannot backtrack."); | ||
161 | break mainloop; | ||
162 | } else { | ||
163 | logger.debug("No more transitions from current state, backtrack."); | ||
164 | continue; | ||
165 | } | ||
166 | } | ||
167 | } while (transitions.isEmpty()); | ||
168 | |||
169 | int index = random.nextInt(transitions.size()); | ||
170 | Object transition = transitions.remove(index); | ||
171 | |||
172 | context.executeAcitvationId(transition); | ||
173 | |||
174 | boolean loopInTrajectory = context.isCurrentStateInTrajectory(); | ||
175 | if (loopInTrajectory) { | ||
176 | boolean isSuccessfulUndo = context.backtrack(); | ||
177 | if (!isSuccessfulUndo) { | ||
178 | throw new DSEException( | ||
179 | "The new state is present in the trajectoy but cannot bactkrack. Should never happen!"); | ||
180 | } else { | ||
181 | logger.info("The new state is already visited in the trajectory, backtrack."); | ||
182 | } | ||
183 | } | ||
184 | |||
185 | } while (true); | ||
186 | |||
187 | logger.info("Terminated."); | ||
188 | } | ||
189 | |||
190 | @Override | ||
191 | public void interruptStrategy() { | ||
192 | isInterrupted.set(true); | ||
193 | } | ||
194 | |||
195 | private Integer getBestPriority(Collection<? extends Object> transitions) { | ||
196 | Integer bestPriority = Integer.MIN_VALUE; | ||
197 | for (Object iTransition : transitions) { | ||
198 | Integer priority = priorities.get(context.getRuleByActivationId(iTransition)); | ||
199 | if (priority == null) { | ||
200 | priority = Integer.valueOf(0); | ||
201 | } | ||
202 | if (priority > bestPriority) { | ||
203 | bestPriority = priority; | ||
204 | } | ||
205 | } | ||
206 | return bestPriority; | ||
207 | } | ||
208 | } | ||