From 0c26310fc48b5359da11b32b04e008e64f91c10e Mon Sep 17 00:00:00 2001
From: Attila Ficsor <ficsorattila96@gmail.com>
Date: Mon, 7 Aug 2023 16:23:57 +0200
Subject: Reduce complexity of Depth first search

---
 .../store/dse/strategy/DepthFirstStrategy.java     | 89 +++++++++-------------
 1 file changed, 36 insertions(+), 53 deletions(-)

(limited to 'subprojects/store-dse/src/main')

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;
 
 import tools.refinery.store.dse.DesignSpaceExplorationAdapter;
 import tools.refinery.store.dse.Strategy;
-import tools.refinery.store.dse.internal.Activation;
 import tools.refinery.store.dse.objectives.Fitness;
 
-import java.util.Collection;
-
 public class DepthFirstStrategy implements Strategy {
 
 	private DesignSpaceExplorationAdapter dseAdapter;
@@ -60,69 +57,55 @@ public class DepthFirstStrategy implements Strategy {
 		if (maxSolutions == 0) {
 			return;
 		}
-		mainloop: while (true) {
-			var globalConstraintsAreSatisfied = dseAdapter.checkGlobalConstraints();
-			if (!globalConstraintsAreSatisfied) {
-				var isSuccessfulUndo = dseAdapter.backtrack();
-				if (!isSuccessfulUndo) {
-					// Global constraint is not satisfied and cannot backtrack.
-					break;
-				}
-				else {
-					// Global constraint is not satisfied, backtrack.
-					continue;
-				}
+		while (dseAdapter.getSolutions().size() < maxSolutions) {
+			if (!checkAndHandleGlobalConstraints()) {
+				// Global constraint is not satisfied and cannot backtrack.
+				return;
 			}
+			// Global constraint is not satisfied, backtrack.
 
 			Fitness fitness = dseAdapter.getFitness();
 			if (fitness.isSatisfiesHardObjectives()) {
 				dseAdapter.newSolution();
-				var solutions = dseAdapter.getSolutions().size();
-				if (solutions >= maxSolutions) {
+				if (backTrackIfSolution && !dseAdapter.backtrack()) {
+					// Found a solution but cannot backtrack.
 					return;
 				}
-				if (backTrackIfSolution) {
-					var isSuccessfulUndo = dseAdapter.backtrack();
-					if (!isSuccessfulUndo) {
-						// Found a solution but cannot backtrack.
-						break;
-					} else {
-						// Found a solution, backtrack.
-						continue;
-					}
-				}
 			}
 
-			if (dseAdapter.getDepth() >= maxDepth) {
-				var isSuccessfulUndo = dseAdapter.backtrack();
-				if (!isSuccessfulUndo) {
-					// Reached max depth but cannot backtrack.
-					break;
-				}
+			if (!checkAndHandleDepth()) {
+				// Reached max depth but cannot backtrack.
+				return;
 			}
 
-			Collection<Activation> activations;
-			do {
-				activations = dseAdapter.getUntraversedActivations();
-				if (activations.isEmpty() && !dseAdapter.backtrack()) {
-					// No more transitions from current state and cannot backtrack.
-					break mainloop;
-				}
-				// No more transitions from current state, backtrack.
-			} while (activations.isEmpty());
+			if (!backtrackToLastUntraversed()) {
+				return;
+			}
 
 			dseAdapter.fireRandomActivation();
-//			if (dseAdapter.isCurrentInTrajectory()) {
-//				if (!dseAdapter.backtrack()) {
-////					TODO: throw exception
-////					"The new state is present in the trajectory but cannot backtrack. Should never happen!"
-//					break;
-//				}
-//				else {
-////					"The new state is already visited in the trajectory, backtrack."
-//					continue;
-//				}
-//			}
 		}
 	}
+
+	private boolean checkAndHandleGlobalConstraints() {
+		// Global constraint is not satisfied and cannot backtrack.
+		return dseAdapter.checkGlobalConstraints() || dseAdapter.backtrack();
+		// Global constraint is satisfied or backtrack.
+	}
+
+	private boolean checkAndHandleDepth() {
+		// Reached max depth but cannot backtrack.
+		return dseAdapter.getDepth() < maxDepth || dseAdapter.backtrack();
+		// Reached max depth or backtrack.
+	}
+
+	private boolean backtrackToLastUntraversed() {
+		while (dseAdapter.getUntraversedActivations().isEmpty()) {
+			if (!dseAdapter.backtrack()) {
+				// No more transitions from current state and cannot backtrack.
+				return false;
+			}
+			// No more transitions from current state, backtrack.
+		}
+		return true;
+	}
 }
-- 
cgit v1.2.3-54-g00ecf