diff options
Diffstat (limited to 'Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java')
-rw-r--r-- | Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java new file mode 100644 index 00000000..6b7d9817 --- /dev/null +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BreadthFirstStrategy.java | |||
@@ -0,0 +1,220 @@ | |||
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.Iterator; | ||
13 | import java.util.concurrent.BrokenBarrierException; | ||
14 | import java.util.concurrent.ConcurrentLinkedQueue; | ||
15 | import java.util.concurrent.CyclicBarrier; | ||
16 | import java.util.concurrent.atomic.AtomicBoolean; | ||
17 | |||
18 | import org.apache.log4j.Logger; | ||
19 | import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; | ||
20 | import org.eclipse.viatra.dse.base.GlobalContext; | ||
21 | import org.eclipse.viatra.dse.base.ThreadContext; | ||
22 | import org.eclipse.viatra.dse.objectives.Fitness; | ||
23 | import org.eclipse.viatra.dse.solutionstore.SolutionStore; | ||
24 | |||
25 | /** | ||
26 | * A breadth-first search algorithm implementation, that | ||
27 | * <ul> | ||
28 | * <li>can work with multiple threads,</li> | ||
29 | * <li>indeterministic,</li> | ||
30 | * <li>saves all states (trajectories) as solutions that fulfill all the hard objectives,</li> | ||
31 | * <li>can have a depth limit,</li> | ||
32 | * <li>will backtrack when a model satisfies the hard objectives (after saving it as a solution) and will not explore | ||
33 | * beyond that state.</li> | ||
34 | * </ul> | ||
35 | * | ||
36 | * @author Andras Szabolcs Nagy | ||
37 | * | ||
38 | */ | ||
39 | public class BreadthFirstStrategy implements IStrategy { | ||
40 | |||
41 | private static final class BfsSharedObject { | ||
42 | private final ConcurrentLinkedQueue<Object[]> trajectoryQueue1 = new ConcurrentLinkedQueue<>(); | ||
43 | private final ConcurrentLinkedQueue<Object[]> trajectoryQueue2 = new ConcurrentLinkedQueue<>(); | ||
44 | |||
45 | private final AtomicBoolean pushToQueue1 = new AtomicBoolean(false); | ||
46 | private final AtomicBoolean designSpaceTraversed = new AtomicBoolean(false); | ||
47 | |||
48 | public final CyclicBarrier barrier; | ||
49 | |||
50 | public BfsSharedObject(int numberOfThreads) { | ||
51 | barrier = new CyclicBarrier(numberOfThreads, () -> { | ||
52 | boolean oldValue = pushToQueue1.get(); | ||
53 | pushToQueue1.set(!oldValue); | ||
54 | if (trajectoryQueue1.isEmpty() && trajectoryQueue2.isEmpty()) { | ||
55 | designSpaceTraversed.set(true); | ||
56 | } | ||
57 | }); | ||
58 | } | ||
59 | |||
60 | public Object[] poll() { | ||
61 | if (pushToQueue1.get()) { | ||
62 | return trajectoryQueue2.poll(); | ||
63 | } else { | ||
64 | return trajectoryQueue1.poll(); | ||
65 | } | ||
66 | } | ||
67 | |||
68 | public void push(Object[] trajectory) { | ||
69 | if (pushToQueue1.get()) { | ||
70 | trajectoryQueue1.add(trajectory); | ||
71 | } else { | ||
72 | trajectoryQueue2.add(trajectory); | ||
73 | } | ||
74 | } | ||
75 | |||
76 | public boolean isDesignSpaceTraversed() { | ||
77 | return designSpaceTraversed.get(); | ||
78 | } | ||
79 | } | ||
80 | |||
81 | private int maxDepth = 0; | ||
82 | private BfsSharedObject shared; | ||
83 | private boolean isInterrupted = false; | ||
84 | private ThreadContext context; | ||
85 | private Logger logger = Logger.getLogger(IStrategy.class); | ||
86 | private SolutionStore solutionStore; | ||
87 | private boolean isFirstThread = false; | ||
88 | |||
89 | /** | ||
90 | * Creates a new breadth-first search algorithm without depth limit. | ||
91 | */ | ||
92 | public BreadthFirstStrategy() { | ||
93 | this.maxDepth = Integer.MAX_VALUE; | ||
94 | } | ||
95 | |||
96 | /** | ||
97 | * Creates a new breadth-first search algorithm with depth limit. | ||
98 | * | ||
99 | * @param maxDepth | ||
100 | * A negative <code>maxDepth</code> means no depth limit, zero means the checking of the initial state. | ||
101 | */ | ||
102 | public BreadthFirstStrategy(int maxDepth) { | ||
103 | if (maxDepth < 0) { | ||
104 | this.maxDepth = Integer.MAX_VALUE; | ||
105 | } else { | ||
106 | this.maxDepth = maxDepth; | ||
107 | } | ||
108 | } | ||
109 | |||
110 | @Override | ||
111 | public void initStrategy(ThreadContext context) { | ||
112 | this.context = context; | ||
113 | this.solutionStore = context.getGlobalContext().getSolutionStore(); | ||
114 | |||
115 | GlobalContext globalContext = context.getGlobalContext(); | ||
116 | if (globalContext.getSharedObject() == null) { | ||
117 | isFirstThread = true; | ||
118 | shared = new BfsSharedObject(globalContext.getThreadPool().getMaximumPoolSize()); | ||
119 | globalContext.setSharedObject(shared); | ||
120 | logger.info("Breadth-first exploration strategy is inited."); | ||
121 | } else { | ||
122 | shared = (BfsSharedObject) globalContext.getSharedObject(); | ||
123 | } | ||
124 | } | ||
125 | |||
126 | @Override | ||
127 | public void explore() { | ||
128 | |||
129 | if (isFirstThread) { | ||
130 | |||
131 | boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints(); | ||
132 | if (!globalConstraintsAreSatisfied) { | ||
133 | logger.info("Global contraint is not satisifed in the first state. Terminate."); | ||
134 | return; | ||
135 | } | ||
136 | |||
137 | Fitness fitness = context.calculateFitness(); | ||
138 | if (fitness.isSatisifiesHardObjectives()) { | ||
139 | context.newSolution(); | ||
140 | logger.info("First state is a solution. Terminate."); | ||
141 | return; | ||
142 | } | ||
143 | |||
144 | Object[] currentTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
145 | |||
146 | shared.push(currentTrajectory); | ||
147 | |||
148 | startThreads(); | ||
149 | } else { | ||
150 | try { | ||
151 | shared.barrier.await(); | ||
152 | } catch (InterruptedException | BrokenBarrierException e) { | ||
153 | } | ||
154 | } | ||
155 | |||
156 | mainLoop: while (!isInterrupted && !shared.isDesignSpaceTraversed()) { | ||
157 | |||
158 | Object[] next = shared.poll(); | ||
159 | while (next == null) { | ||
160 | try { | ||
161 | logger.debug("Reached barrier."); | ||
162 | shared.barrier.await(); | ||
163 | } catch (InterruptedException | BrokenBarrierException e1) { | ||
164 | } | ||
165 | if (isInterrupted || shared.isDesignSpaceTraversed()) { | ||
166 | break mainLoop; | ||
167 | } | ||
168 | next = shared.poll(); | ||
169 | } | ||
170 | |||
171 | context.backtrackUntilRoot(); | ||
172 | |||
173 | context.executeTrajectory(next); | ||
174 | |||
175 | Collection<Object> activationIds = context.getCurrentActivationIds(); | ||
176 | int i = activationIds.size() - 1; | ||
177 | |||
178 | while (!isInterrupted && i >= 0) { | ||
179 | |||
180 | Iterator<Object> iterator = activationIds.iterator(); | ||
181 | int index = i--; | ||
182 | while (iterator.hasNext() && index > 0) { | ||
183 | index--; | ||
184 | iterator.next(); | ||
185 | } | ||
186 | Object activationIdToTry = iterator.next(); | ||
187 | |||
188 | context.executeAcitvationId(activationIdToTry); | ||
189 | |||
190 | if (context.isCurrentStateAlreadyTraversed()) { | ||
191 | logger.info("The new state is already visited."); | ||
192 | } else if (!context.checkGlobalConstraints()) { | ||
193 | logger.debug("Global contraint is not satisifed."); | ||
194 | } else if (context.calculateFitness().isSatisifiesHardObjectives()) { | ||
195 | solutionStore.newSolution(context); | ||
196 | logger.debug("Found a solution."); | ||
197 | } else if (context.getDepth() >= maxDepth) { | ||
198 | logger.debug("Reached max depth."); | ||
199 | } else { | ||
200 | Object[] currentTrajectory = context.getTrajectory().toArray(new Object[0]); | ||
201 | shared.push(currentTrajectory); | ||
202 | } | ||
203 | |||
204 | context.backtrack(); | ||
205 | } | ||
206 | |||
207 | } | ||
208 | } | ||
209 | |||
210 | private void startThreads() { | ||
211 | context.startAllThreads(() -> new BreadthFirstStrategy(maxDepth)); | ||
212 | } | ||
213 | |||
214 | @Override | ||
215 | public void interruptStrategy() { | ||
216 | isInterrupted = true; | ||
217 | shared.barrier.reset(); | ||
218 | } | ||
219 | |||
220 | } | ||