1 files changed, 184 insertions, 0 deletions
diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/DiversityChecker.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/DiversityChecker.xtend
new file mode 100644
index 00000000..fb1b2066
--- /dev/null
+++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/DiversityChecker.xtend
@@ -0,0 +1,184 @@
+package hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.dse
+import com.google.common.collect.HashMultiset
+import com.google.common.collect.ImmutableSet
+import com.google.common.collect.Multiset
+import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.neighbourhood.AbstractNodeDescriptor
+import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.neighbourhood.NeighbourhoodWithTraces
+import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.neighbourhood.PartialInterpretation2ImmutableTypeLattice
+import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialInterpretation
+import hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.DiversityDescriptor
+import java.util.Collection
+import java.util.HashSet
+import java.util.Map
+import java.util.Set
+import org.eclipse.viatra.dse.base.ThreadContext
+import org.eclipse.xtend.lib.annotations.Accessors
+interface DiversityChecker {
+        public static val NO_DIVERSITY_CHECKER = new DiversityChecker {
+                override isActive() {
+                        false
+                }
+                override getTotalRuntime() {
+                        0
+                }
+                override getSuccessRate() {
+                        1.0
+                }
+                override newSolution(ThreadContext threadContext, Object solutionId, Collection<Object> dominatedSolutionIds) {
+                        true
+                }
+        }
+        def boolean isActive()
+        def long getTotalRuntime()
+        def double getSuccessRate()
+        def boolean newSolution(ThreadContext threadContext, Object solutionId, Collection<Object> dominatedSolutionIds)
+        static def of(DiversityDescriptor descriptor) {
+                if (descriptor.ensureDiversity) {
+                        new NodewiseDiversityChecker(descriptor)
+                } else {
+                        NO_DIVERSITY_CHECKER
+                }
+        }
+}
+abstract class AbstractDiversityChecker implements DiversityChecker {
+        val DiversityDescriptor descriptor
+        val PartialInterpretation2ImmutableTypeLattice solutionCoder = new PartialInterpretation2ImmutableTypeLattice
+        @Accessors(PUBLIC_GETTER) var long totalRuntime = 0
+        var int allCheckCount = 0
+        var int successfulCheckCount = 0
+        protected new(DiversityDescriptor descriptor) {
+                if (!descriptor.ensureDiversity) {
+                        throw new IllegalArgumentException(
+                                "Diversity description should enforce diversity or NO_DIVERSITY_CHECKER should be used instead.")
+                }
+                this.descriptor = descriptor
+        }
+        override isActive() {
+                true
+        }
+        override getTotalRuntime() {
+                throw new UnsupportedOperationException("TODO: auto-generated method stub")
+        }
+        override getSuccessRate() {
+                (allCheckCount as double) / (successfulCheckCount as double)
+        }
+        override newSolution(ThreadContext threadContext, Object solutionId, Collection<Object> dominatedSolutionIds) {
+                val start = System.nanoTime
+                val model = threadContext.model as PartialInterpretation
+                val representation = solutionCoder.createRepresentation(model, descriptor.range, descriptor.parallels,
+                        descriptor.maxNumber, descriptor.relevantTypes, descriptor.relevantRelations)
+                val isDifferent = internalNewSolution(representation, solutionId, dominatedSolutionIds)
+                totalRuntime += System.nanoTime - start
+                allCheckCount++
+                if (isDifferent) {
+                        successfulCheckCount++
+                }
+                isDifferent
+        }
+        protected abstract def boolean internalNewSolution(
+                NeighbourhoodWithTraces<Map<? extends AbstractNodeDescriptor, Integer>, AbstractNodeDescriptor> representation,
+                Object solutionId, Collection<Object> dominatedSolutionIds)
+}
+class NodewiseDiversityChecker extends AbstractDiversityChecker {
+        var Multiset<Integer> nodeCodes = HashMultiset.create
+        val Map<Object, Set<Integer>> tracedNodeCodes = newHashMap
+        new(DiversityDescriptor descriptor) {
+                super(descriptor)
+        }
+        override protected internalNewSolution(
+                NeighbourhoodWithTraces<Map<? extends AbstractNodeDescriptor, Integer>, AbstractNodeDescriptor> representation,
+                Object solutionId, Collection<Object> dominatedSolutionIds) {
+                val nodeCodesInSolution = ImmutableSet.copyOf(representation.modelRepresentation.keySet.map[hashCode])
+                val remainingNodeCodes = if (dominatedSolutionIds.empty) {
+                                nodeCodes
+                        } else {
+                                getRemainingNodeCodes(dominatedSolutionIds)
+                        }
+                val hasNewCode = nodeCodesInSolution.exists[!remainingNodeCodes.contains(it)]
+                if (hasNewCode) {
+                        nodeCodes = remainingNodeCodes
+                        nodeCodes.addAll(nodeCodesInSolution)
+                        for (dominatedSolutionId : dominatedSolutionIds) {
+                                tracedNodeCodes.remove(dominatedSolutionId)
+                        }
+                        tracedNodeCodes.put(solutionId, nodeCodesInSolution)
+                }
+                hasNewCode
+        }
+        private def getRemainingNodeCodes(Collection<Object> dominatedSolutionIds) {
+                // TODO Optimize multiset operations.
+                val copyOfNodeCodes = HashMultiset.create(nodeCodes)
+                for (dominatedSolutionId : dominatedSolutionIds) {
+                        val dominatedModelCode = tracedNodeCodes.get(dominatedSolutionId)
+                        if (dominatedModelCode === null) {
+                                throw new IllegalArgumentException("Unknown dominated solution: " + dominatedSolutionId)
+                        }
+                        copyOfNodeCodes.removeAll(dominatedModelCode)
+                }
+                copyOfNodeCodes
+        }
+}
+class GraphwiseDiversityChecker extends AbstractDiversityChecker {
+        var Set<Integer> modelCodes = newHashSet
+        val Map<Object, Integer> tracedModelCodes = newHashMap
+        new(DiversityDescriptor descriptor) {
+                super(descriptor)
+        }
+        override protected internalNewSolution(
+                NeighbourhoodWithTraces<Map<? extends AbstractNodeDescriptor, Integer>, AbstractNodeDescriptor> representation,
+                Object solutionId, Collection<Object> dominatedSolutionIds) {
+                val modelCodeOfSolution = representation.modelRepresentation.hashCode
+                val remainingModelCodes = if (dominatedSolutionIds.empty) {
+                                modelCodes
+                        } else {
+                                getRemainingModelCodes(dominatedSolutionIds)
+                        }
+                val isNewCode = !remainingModelCodes.contains(modelCodeOfSolution)
+                if (isNewCode) {
+                        modelCodes = remainingModelCodes
+                        modelCodes += modelCodeOfSolution
+                        for (dominatedSolutionId : dominatedSolutionIds) {
+                                tracedModelCodes.remove(dominatedSolutionId)
+                        }
+                        tracedModelCodes.put(solutionId, modelCodeOfSolution)
+                }
+                isNewCode
+        }
+        private def getRemainingModelCodes(Collection<Object> dominatedSolutionIds) {
+                val copyOfModelCodes = new HashSet(modelCodes)
+                for (dominatedSolutionId : dominatedSolutionIds) {
+                        val dominatedModelCode = tracedModelCodes.get(dominatedSolutionId)
+                        if (dominatedModelCode === null) {
+                                throw new IllegalArgumentException("Unknown dominated solution: " + dominatedSolutionId)
+                        }
+                        copyOfModelCodes -= dominatedModelCode
+                }
+                copyOfModelCodes
+        }
+}

diff --git a/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/DiversityChecker.xtend b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/DiversityChecker.xtend new file mode 100644 index 00000000..fb1b2066 --- /dev/null +++ b/Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner/src/hu/bme/mit/inf/dslreasoner/viatrasolver/reasoner/dse/DiversityChecker.xtend
@@ -0,0 +1,184 @@
	1	package hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.dse
	2
	3	import com.google.common.collect.HashMultiset
	4	import com.google.common.collect.ImmutableSet
	5	import com.google.common.collect.Multiset
	6	import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.neighbourhood.AbstractNodeDescriptor
	7	import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.neighbourhood.NeighbourhoodWithTraces
	8	import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.neighbourhood.PartialInterpretation2ImmutableTypeLattice
	9	import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialInterpretation
	10	import hu.bme.mit.inf.dslreasoner.viatrasolver.reasoner.DiversityDescriptor
	11	import java.util.Collection
	12	import java.util.HashSet
	13	import java.util.Map
	14	import java.util.Set
	15	import org.eclipse.viatra.dse.base.ThreadContext
	16	import org.eclipse.xtend.lib.annotations.Accessors
	17
	18	interface DiversityChecker {
	19	public static val NO_DIVERSITY_CHECKER = new DiversityChecker {
	20	override isActive() {
	21	false
	22	}
	23
	24	override getTotalRuntime() {
	25	0
	26	}
	27
	28	override getSuccessRate() {
	29	1.0
	30	}
	31
	32	override newSolution(ThreadContext threadContext, Object solutionId, Collection<Object> dominatedSolutionIds) {
	33	true
	34	}
	35	}
	36
	37	def boolean isActive()
	38
	39	def long getTotalRuntime()
	40
	41	def double getSuccessRate()
	42
	43	def boolean newSolution(ThreadContext threadContext, Object solutionId, Collection<Object> dominatedSolutionIds)
	44
	45	static def of(DiversityDescriptor descriptor) {
	46	if (descriptor.ensureDiversity) {
	47	new NodewiseDiversityChecker(descriptor)
	48	} else {
	49	NO_DIVERSITY_CHECKER
	50	}
	51	}
	52	}
	53
	54	abstract class AbstractDiversityChecker implements DiversityChecker {
	55	val DiversityDescriptor descriptor
	56	val PartialInterpretation2ImmutableTypeLattice solutionCoder = new PartialInterpretation2ImmutableTypeLattice
	57
	58	@Accessors(PUBLIC_GETTER) var long totalRuntime = 0
	59	var int allCheckCount = 0
	60	var int successfulCheckCount = 0
	61
	62	protected new(DiversityDescriptor descriptor) {
	63	if (!descriptor.ensureDiversity) {
	64	throw new IllegalArgumentException(
	65	"Diversity description should enforce diversity or NO_DIVERSITY_CHECKER should be used instead.")
	66	}
	67	this.descriptor = descriptor
	68	}
	69
	70	override isActive() {
	71	true
	72	}
	73
	74	override getTotalRuntime() {
	75	throw new UnsupportedOperationException("TODO: auto-generated method stub")
	76	}
	77
	78	override getSuccessRate() {
	79	(allCheckCount as double) / (successfulCheckCount as double)
	80	}
	81
	82	override newSolution(ThreadContext threadContext, Object solutionId, Collection<Object> dominatedSolutionIds) {
	83	val start = System.nanoTime
	84	val model = threadContext.model as PartialInterpretation
	85	val representation = solutionCoder.createRepresentation(model, descriptor.range, descriptor.parallels,
	86	descriptor.maxNumber, descriptor.relevantTypes, descriptor.relevantRelations)
	87	val isDifferent = internalNewSolution(representation, solutionId, dominatedSolutionIds)
	88	totalRuntime += System.nanoTime - start
	89	allCheckCount++
	90	if (isDifferent) {
	91	successfulCheckCount++
	92	}
	93	isDifferent
	94	}
	95
	96	protected abstract def boolean internalNewSolution(
	97	NeighbourhoodWithTraces<Map<? extends AbstractNodeDescriptor, Integer>, AbstractNodeDescriptor> representation,
	98	Object solutionId, Collection<Object> dominatedSolutionIds)
	99	}
	100
	101	class NodewiseDiversityChecker extends AbstractDiversityChecker {
	102	var Multiset<Integer> nodeCodes = HashMultiset.create
	103	val Map<Object, Set<Integer>> tracedNodeCodes = newHashMap
	104
	105	new(DiversityDescriptor descriptor) {
	106	super(descriptor)
	107	}
	108
	109	override protected internalNewSolution(
	110	NeighbourhoodWithTraces<Map<? extends AbstractNodeDescriptor, Integer>, AbstractNodeDescriptor> representation,
	111	Object solutionId, Collection<Object> dominatedSolutionIds) {
	112	val nodeCodesInSolution = ImmutableSet.copyOf(representation.modelRepresentation.keySet.map[hashCode])
	113	val remainingNodeCodes = if (dominatedSolutionIds.empty) {
	114	nodeCodes
	115	} else {
	116	getRemainingNodeCodes(dominatedSolutionIds)
	117	}
	118	val hasNewCode = nodeCodesInSolution.exists[!remainingNodeCodes.contains(it)]
	119	if (hasNewCode) {
	120	nodeCodes = remainingNodeCodes
	121	nodeCodes.addAll(nodeCodesInSolution)
	122	for (dominatedSolutionId : dominatedSolutionIds) {
	123	tracedNodeCodes.remove(dominatedSolutionId)
	124	}
	125	tracedNodeCodes.put(solutionId, nodeCodesInSolution)
	126	}
	127	hasNewCode
	128	}
	129
	130	private def getRemainingNodeCodes(Collection<Object> dominatedSolutionIds) {
	131	// TODO Optimize multiset operations.
	132	val copyOfNodeCodes = HashMultiset.create(nodeCodes)
	133	for (dominatedSolutionId : dominatedSolutionIds) {
	134	val dominatedModelCode = tracedNodeCodes.get(dominatedSolutionId)
	135	if (dominatedModelCode === null) {
	136	throw new IllegalArgumentException("Unknown dominated solution: " + dominatedSolutionId)
	137	}
	138	copyOfNodeCodes.removeAll(dominatedModelCode)
	139	}
	140	copyOfNodeCodes
	141	}
	142	}
	143
	144	class GraphwiseDiversityChecker extends AbstractDiversityChecker {
	145	var Set<Integer> modelCodes = newHashSet
	146	val Map<Object, Integer> tracedModelCodes = newHashMap
	147
	148	new(DiversityDescriptor descriptor) {
	149	super(descriptor)
	150	}
	151
	152	override protected internalNewSolution(
	153	NeighbourhoodWithTraces<Map<? extends AbstractNodeDescriptor, Integer>, AbstractNodeDescriptor> representation,
	154	Object solutionId, Collection<Object> dominatedSolutionIds) {
	155	val modelCodeOfSolution = representation.modelRepresentation.hashCode
	156	val remainingModelCodes = if (dominatedSolutionIds.empty) {
	157	modelCodes
	158	} else {
	159	getRemainingModelCodes(dominatedSolutionIds)
	160	}
	161	val isNewCode = !remainingModelCodes.contains(modelCodeOfSolution)
	162	if (isNewCode) {
	163	modelCodes = remainingModelCodes
	164	modelCodes += modelCodeOfSolution
	165	for (dominatedSolutionId : dominatedSolutionIds) {
	166	tracedModelCodes.remove(dominatedSolutionId)
	167	}
	168	tracedModelCodes.put(solutionId, modelCodeOfSolution)
	169	}
	170	isNewCode
	171	}
	172
	173	private def getRemainingModelCodes(Collection<Object> dominatedSolutionIds) {
	174	val copyOfModelCodes = new HashSet(modelCodes)
	175	for (dominatedSolutionId : dominatedSolutionIds) {
	176	val dominatedModelCode = tracedModelCodes.get(dominatedSolutionId)
	177	if (dominatedModelCode === null) {
	178	throw new IllegalArgumentException("Unknown dominated solution: " + dominatedSolutionId)
	179	}
	180	copyOfModelCodes -= dominatedModelCode
	181	}
	182	copyOfModelCodes
	183	}
	184	}