From 2093fa9ebcbd79f4cee2c224c78fb58d26ca568e Mon Sep 17 00:00:00 2001
From: Oszkar Semerath <semerath@mit.bme.hu>
Date: Mon, 15 Jul 2019 19:02:29 +0200
Subject: https://github.com/kris7t graph width calculation ->

from https://github.com/kris7t/VIATRA-Generator/blob/c0c5a1644cc221352b8b9b370eea6a87677ba948/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage/src/hu/bme/mit/inf/dslreasoner/viatrasolver/partialinterpretationlanguage/neighbourhood/PartialInterpretation2NeighbourhoodRepresentation.xtend#L99-L138
---
 ...nterpretation2NeighbourhoodRepresentation.xtend | 45 +++++++++++++---------
 1 file changed, 27 insertions(+), 18 deletions(-)

diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage/src/hu/bme/mit/inf/dslreasoner/viatrasolver/partialinterpretationlanguage/neighbourhood/PartialInterpretation2NeighbourhoodRepresentation.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage/src/hu/bme/mit/inf/dslreasoner/viatrasolver/partialinterpretationlanguage/neighbourhood/PartialInterpretation2NeighbourhoodRepresentation.xtend
index 6dc40705..d1bf0348 100644
--- a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage/src/hu/bme/mit/inf/dslreasoner/viatrasolver/partialinterpretationlanguage/neighbourhood/PartialInterpretation2NeighbourhoodRepresentation.xtend
+++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage/src/hu/bme/mit/inf/dslreasoner/viatrasolver/partialinterpretationlanguage/neighbourhood/PartialInterpretation2NeighbourhoodRepresentation.xtend
@@ -81,39 +81,48 @@ abstract class PartialInterpretation2NeighbourhoodRepresentation<ModelRepresenta
 	/**
 	 * Gets the largest 
 	 */
+/**
+
+	 * Gets the minimal neighbourhood size such that every reachable node appears in the shape of every other at least once.
+
+	 */
+
 	def private getWidth(Map<DefinedElement, Set<String>> types,
 		Map<DefinedElement, List<IncomingRelation<DefinedElement>>> IncomingRelations,
-		Map<DefinedElement, List<OutgoingRelation<DefinedElement>>> OutgoingRelations)
-	{
-		val elements =  types.keySet
-		val Map<DefinedElement,Set<DefinedElement>> reachable = new HashMap
-		for(element : elements) {
+		Map<DefinedElement, List<OutgoingRelation<DefinedElement>>> OutgoingRelations) {
+		val elements = types.keySet
+		var Map<DefinedElement, Set<DefinedElement>> reachable = new HashMap
+		var Map<DefinedElement, Set<DefinedElement>> newReachable = new HashMap
+		for (element : elements) {
 			val set = new HashSet
 			set.add(element)
-			reachable.put(element,set)
+			reachable.put(element, new HashSet)
+			newReachable.put(element, set)
 		}
-		
 		var int width = 0
 		var boolean newAdded
 		do {
+			var tmp = reachable
+			reachable = newReachable
+			newReachable = tmp
 			newAdded = false
-			for(element : elements) {
+			for (element : elements) {
 				val elementNeigbours = element.lookup(reachable)
-				val size = elementNeigbours.size
-				for(incoming : element.lookup(IncomingRelations)) {
-					elementNeigbours.addAll(incoming.from.lookup(reachable))
+				val newElementNeigbours = element.lookup(newReachable)
+				newElementNeigbours.addAll(elementNeigbours)
+				for (incoming : element.lookup(IncomingRelations)) {
+					newElementNeigbours.addAll(incoming.from.lookup(reachable))
 				}
-				for(outgoing : element.lookup(OutgoingRelations)) {
-					elementNeigbours.addAll(outgoing.to.lookup(reachable))
+				for (outgoing : element.lookup(OutgoingRelations)) {
+					newElementNeigbours.addAll(outgoing.to.lookup(reachable))
 				}
-				newAdded = newAdded || (elementNeigbours.size > size)
+				newAdded = newAdded || (newElementNeigbours.size > elementNeigbours.size)
 			}
-			
-			width +=1
-		} while(newAdded)
+			width += 1
+		} while (newAdded)
 		return width
 	}
-	
+		
 	/**
 	 * Creates a neighbourhood representation with traces
 	 * @param model The model to be represented.
-- 
cgit v1.2.3-54-g00ecf