/******************************************************************************* * 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.Random; import java.util.concurrent.atomic.AtomicBoolean; import org.apache.log4j.Logger; import org.eclipse.viatra.dse.api.DSEException; import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy; import org.eclipse.viatra.dse.base.ThreadContext; import org.eclipse.viatra.dse.objectives.Fitness; /** * A depth-first search algorithm implementation, that *
maxDepth
means no depth limit, zero means the checking of the initial state.
*/
public DepthFirstStrategy(int maxDepth) {
if (maxDepth < 0) {
this.maxDepth = Integer.MAX_VALUE;
} else {
this.maxDepth = maxDepth;
}
}
/**
* If called, the algorithm will not backtrack after the hard objectives are fulfilled, instead it goes deeper in
* the search space.
*/
public DepthFirstStrategy continueIfHardObjectivesFulfilled() {
backTrackIfSolution = false;
return this;
}
@Override
public void initStrategy(ThreadContext context) {
this.context = context;
if (context.getSharedObject() == null) {
context.setSharedObject(new Object());
logger.info("Depth-first exploration strategy is initied.");
startThreads();
}
}
private void startThreads() {
context.startAllThreads(() -> new DepthFirstStrategy(maxDepth));
}
@Override
public void explore() {
mainloop: do {
boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints();
if (!globalConstraintsAreSatisfied) {
boolean isSuccessfulUndo = context.backtrack();
if (!isSuccessfulUndo) {
logger.info("Global contraint is not satisifed and cannot backtrack.");
break;
} else {
logger.debug("Global contraint is not satisifed, backtrack.");
continue;
}
}
Fitness fitness = context.calculateFitness();
if (fitness.isSatisifiesHardObjectives()) {
context.newSolution();
if (backTrackIfSolution) {
boolean isSuccessfulUndo = context.backtrack();
if (!isSuccessfulUndo) {
logger.info("Found a solution but cannot backtrack.");
break;
} else {
logger.debug("Found a solution, backtrack.");
continue;
}
}
}
if (context.getDepth() >= maxDepth) {
boolean isSuccessfulUndo = context.backtrack();
if (!isSuccessfulUndo) {
logger.info("Reached max depth but cannot bactrack.");
break;
} else {
logger.debug("Reached max depth, bactrack.");
continue;
}
}
if (isInterrupted.get()) {
logger.info("Interrupted, stop exploration.");
break;
}
Object activationId = null;
Collection