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 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Andras Szabolcs Nagy, Zoltan Ujhelyi and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package org.eclipse.viatra.dse.api.strategy.impl;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.concurrent.BrokenBarrierException;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.CyclicBarrier;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+import org.apache.log4j.Logger;
+import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy;
+import org.eclipse.viatra.dse.base.GlobalContext;
+import org.eclipse.viatra.dse.base.ThreadContext;
+import org.eclipse.viatra.dse.objectives.Fitness;
+import org.eclipse.viatra.dse.solutionstore.SolutionStore;
+
+/**
+ * A breadth-first search algorithm implementation, that
+ * <ul>
+ * <li>can work with multiple threads,</li>
+ * <li>indeterministic,</li>
+ * <li>saves all states (trajectories) as solutions that fulfill all the hard objectives,</li>
+ * <li>can have a depth limit,</li>
+ * <li>will backtrack when a model satisfies the hard objectives (after saving it as a solution) and will not explore
+ * beyond that state.</li>
+ * </ul>
+ * 
+ * @author Andras Szabolcs Nagy
+ *
+ */
+public class BreadthFirstStrategy implements IStrategy {
+
+    private static final class BfsSharedObject {
+        private final ConcurrentLinkedQueue<Object[]> trajectoryQueue1 = new ConcurrentLinkedQueue<>();
+        private final ConcurrentLinkedQueue<Object[]> trajectoryQueue2 = new ConcurrentLinkedQueue<>();
+
+        private final AtomicBoolean pushToQueue1 = new AtomicBoolean(false);
+        private final AtomicBoolean designSpaceTraversed = new AtomicBoolean(false);
+
+        public final CyclicBarrier barrier;
+
+        public BfsSharedObject(int numberOfThreads) {
+            barrier = new CyclicBarrier(numberOfThreads, () -> {
+                boolean oldValue = pushToQueue1.get();
+                pushToQueue1.set(!oldValue);
+                if (trajectoryQueue1.isEmpty() && trajectoryQueue2.isEmpty()) {
+                    designSpaceTraversed.set(true);
+                }
+            });
+        }
+
+        public Object[] poll() {
+            if (pushToQueue1.get()) {
+                return trajectoryQueue2.poll();
+            } else {
+                return trajectoryQueue1.poll();
+            }
+        }
+
+        public void push(Object[] trajectory) {
+            if (pushToQueue1.get()) {
+                trajectoryQueue1.add(trajectory);
+            } else {
+                trajectoryQueue2.add(trajectory);
+            }
+        }
+
+        public boolean isDesignSpaceTraversed() {
+            return designSpaceTraversed.get();
+        }
+    }
+
+    private int maxDepth = 0;
+    private BfsSharedObject shared;
+    private boolean isInterrupted = false;
+    private ThreadContext context;
+    private Logger logger = Logger.getLogger(IStrategy.class);
+    private SolutionStore solutionStore;
+    private boolean isFirstThread = false;
+
+    /**
+     * Creates a new breadth-first search algorithm without depth limit.
+     */
+    public BreadthFirstStrategy() {
+        this.maxDepth = Integer.MAX_VALUE;
+    }
+
+    /**
+     * Creates a new breadth-first search algorithm with depth limit.
+     * 
+     * @param maxDepth
+     *            A negative <code>maxDepth</code> means no depth limit, zero means the checking of the initial state.
+     */
+    public BreadthFirstStrategy(int maxDepth) {
+        if (maxDepth < 0) {
+            this.maxDepth = Integer.MAX_VALUE;
+        } else {
+            this.maxDepth = maxDepth;
+        }
+    }
+
+    @Override
+    public void initStrategy(ThreadContext context) {
+        this.context = context;
+        this.solutionStore = context.getGlobalContext().getSolutionStore();
+
+        GlobalContext globalContext = context.getGlobalContext();
+        if (globalContext.getSharedObject() == null) {
+            isFirstThread = true;
+            shared = new BfsSharedObject(globalContext.getThreadPool().getMaximumPoolSize());
+            globalContext.setSharedObject(shared);
+            logger.info("Breadth-first exploration strategy is inited.");
+        } else {
+            shared = (BfsSharedObject) globalContext.getSharedObject();
+        }
+    }
+
+    @Override
+    public void explore() {
+
+        if (isFirstThread) {
+
+            boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints();
+            if (!globalConstraintsAreSatisfied) {
+                logger.info("Global contraint is not satisifed in the first state. Terminate.");
+                return;
+            }
+
+            Fitness fitness = context.calculateFitness();
+            if (fitness.isSatisifiesHardObjectives()) {
+                context.newSolution();
+                logger.info("First state is a solution. Terminate.");
+                return;
+            }
+
+            Object[] currentTrajectory = context.getTrajectory().toArray(new Object[0]);
+
+            shared.push(currentTrajectory);
+
+            startThreads();
+        } else {
+            try {
+                shared.barrier.await();
+            } catch (InterruptedException | BrokenBarrierException e) {
+            }
+        }
+
+        mainLoop: while (!isInterrupted && !shared.isDesignSpaceTraversed()) {
+
+            Object[] next = shared.poll();
+            while (next == null) {
+                try {
+                    logger.debug("Reached barrier.");
+                    shared.barrier.await();
+                } catch (InterruptedException | BrokenBarrierException e1) {
+                }
+                if (isInterrupted || shared.isDesignSpaceTraversed()) {
+                    break mainLoop;
+                }
+                next = shared.poll();
+            }
+
+            context.backtrackUntilRoot();
+
+            context.executeTrajectory(next);
+
+            Collection<Object> activationIds = context.getCurrentActivationIds();
+            int i = activationIds.size() - 1;
+
+            while (!isInterrupted && i >= 0) {
+
+                Iterator<Object> iterator = activationIds.iterator();
+                int index = i--;
+                while (iterator.hasNext() && index > 0) {
+                    index--;
+                    iterator.next();
+                }
+                Object activationIdToTry = iterator.next();
+
+                context.executeAcitvationId(activationIdToTry);
+
+                if (context.isCurrentStateAlreadyTraversed()) {
+                    logger.info("The new state is already visited.");
+                } else if (!context.checkGlobalConstraints()) {
+                    logger.debug("Global contraint is not satisifed.");
+                } else if (context.calculateFitness().isSatisifiesHardObjectives()) {
+                    solutionStore.newSolution(context);
+                    logger.debug("Found a solution.");
+                } else if (context.getDepth() >= maxDepth) {
+                    logger.debug("Reached max depth.");
+                } else {
+                    Object[] currentTrajectory = context.getTrajectory().toArray(new Object[0]);
+                    shared.push(currentTrajectory);
+                }
+
+                context.backtrack();
+            }
+
+        }
+    }
+
+    private void startThreads() {
+        context.startAllThreads(() -> new BreadthFirstStrategy(maxDepth));
+    }
+
+    @Override
+    public void interruptStrategy() {
+        isInterrupted = true;
+        shared.barrier.reset();
+    }
+
+}