From c0c5a1644cc221352b8b9b370eea6a87677ba948 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Sat, 15 Jun 2019 20:56:47 -0400 Subject: Try fix statecode bug Modified graph width calculation to not depend on order of nodes --- ...nterpretation2NeighbourhoodRepresentation.xtend | 456 +++++++++++---------- 1 file changed, 245 insertions(+), 211 deletions(-) (limited to 'Solvers/VIATRA-Solver/hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage/src/hu/bme/mit/inf/dslreasoner/viatrasolver/partialinterpretationlanguage/neighbourhood/PartialInterpretation2NeighbourhoodRepresentation.xtend') 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..54b0f54a 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 @@ -4,32 +4,34 @@ import hu.bme.mit.inf.dslreasoner.logic.model.logiclanguage.DefinedElement import hu.bme.mit.inf.dslreasoner.logic.model.logiclanguage.RelationDeclaration import hu.bme.mit.inf.dslreasoner.logic.model.logiclanguage.TypeDeclaration import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.BinaryElementRelationLink +import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialComplexTypeInterpretation import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialInterpretation +import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialPrimitiveInterpretation +import java.util.ArrayList import java.util.HashMap import java.util.HashSet -import java.util.LinkedList import java.util.List import java.util.Map import java.util.Set import static extension hu.bme.mit.inf.dslreasoner.util.CollectionsUtil.* -import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialPrimitiveInterpretation -import hu.bme.mit.inf.dslreasoner.viatrasolver.partialinterpretationlanguage.partialinterpretation.PartialComplexTypeInterpretation -abstract class PartialInterpretation2NeighbourhoodRepresentation { - private val boolean deepRepresentation - private val boolean mergeSimilarNeighbourhood +abstract class PartialInterpretation2NeighbourhoodRepresentation { + val boolean deepRepresentation + val boolean mergeSimilarNeighbourhood protected new(boolean deeprepresentation, boolean mergeSimilarNeighbourhood) { this.deepRepresentation = deeprepresentation this.mergeSimilarNeighbourhood = mergeSimilarNeighbourhood } - - public static val FixPointRage = -1 - public static val GraphWidthRange = -2 - public static val FullParallels = Integer.MAX_VALUE - public static val MaxNumbers = Integer.MAX_VALUE - + + public static val FixPointRage = NeighbourhoodOptions.FixPointRage + public static val GraphWidthRange = NeighbourhoodOptions.GraphWidthRange + public static val FullParallels = NeighbourhoodOptions.FullParallels + public static val MaxNumbers = NeighbourhoodOptions.MaxNumbers + + static val FOCUSED_ELEMENT_NAME = "<>" + /** * Creates a neighbourhood representation with traces * @param model The model to be represented. @@ -37,10 +39,15 @@ abstract class PartialInterpretation2NeighbourhoodRepresentation relevantTypes, Set relevantRelations) - { + def createRepresentation(PartialInterpretation model, int range, int parallels, int maxNumber, + Set relevantTypes, Set relevantRelations) { + createRepresentationWithFocus(model, range, parallels, maxNumber, relevantTypes, relevantRelations, null) + } + + def createRepresentationWithFocus(PartialInterpretation model, NeighbourhoodOptions options, + DefinedElement focusedElement) { + createRepresentationWithFocus(model, options.range, options.parallels, options.maxNumber, options.relevantTypes, + options.relevantRelations, focusedElement) + } + + def createRepresentationWithFocus(PartialInterpretation model, int range, int parallels, int maxNumber, + Set relevantTypes, Set relevantRelations, DefinedElement focusedElement) { val Map> types = new HashMap - fillTypes(model,types,relevantTypes) + fillTypes(model, types, relevantTypes) val Map>> IncomingRelations = new HashMap; val Map>> OutgoingRelations = new HashMap; - fillReferences(model,IncomingRelations,OutgoingRelations,relevantRelations) - - val res = doRecursiveNeighbourCalculation(model,types,IncomingRelations,OutgoingRelations,range,parallels,maxNumber); - + fillReferences(model, IncomingRelations, OutgoingRelations, relevantRelations) + + val res = doRecursiveNeighbourCalculation(model, types, IncomingRelations, OutgoingRelations, range, parallels, + maxNumber, focusedElement); + return res; } - + def private isRelevant(TypeDeclaration t, Set relevantTypes) { - if(relevantTypes === null) { + if (relevantTypes === null) { return true } else { return relevantTypes.contains(t) } } + def private isRelevant(RelationDeclaration r, Set relevantRelations) { - if(relevantRelations === null) { + if (relevantRelations === null) { return true } else { return relevantRelations.contains(r) } } + /** - * 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> types, Map>> IncomingRelations, - Map>> OutgoingRelations) - { - val elements = types.keySet - val Map> reachable = new HashMap - for(element : elements) { + Map>> OutgoingRelations) { + val elements = types.keySet + var Map> reachable = new HashMap + var Map> 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. @@ -122,68 +145,71 @@ abstract class PartialInterpretation2NeighbourhoodRepresentation doRecursiveNeighbourCalculation( - PartialInterpretation model, - Map> types, + def private NeighbourhoodWithTraces doRecursiveNeighbourCalculation( + PartialInterpretation model, Map> types, Map>> IncomingRelations, - Map>> OutgoingRelations, - int range, int parallels, int maxNumber) - { - if(range == 0){ - val r = calculateLocalNodeDescriptors(model,types,maxNumber) - val res = this.createLocalRepresentation(r.value,r.key) - if(res.modelRepresentation === null) { + Map>> OutgoingRelations, int range, int parallels, + int maxNumber, DefinedElement focusedElement) { + if (range == 0) { + val r = calculateLocalNodeDescriptors(model, types, maxNumber, focusedElement) + val res = this.createLocalRepresentation(r.value, r.key) + if (res.modelRepresentation === null) { throw new IllegalArgumentException('''Model representation is null''') - } else if(res.nodeRepresentations === null || res.nodeRepresentations.empty) { + } else if (res.nodeRepresentations === null || res.nodeRepresentations.empty) { throw new IllegalArgumentException('''No node representation''') - } else if(res.previousRepresentation !== null) { + } else if (res.previousRepresentation !== null) { throw new IllegalArgumentException('''The previous representation of the first neighbourhood have to be null''') - } else return res - } else if(range > 0) { - val previous = doRecursiveNeighbourCalculation(model,types,IncomingRelations,OutgoingRelations,range-1,parallels,maxNumber) - val r = calculateFurtherNodeDescriptors(model,previous,IncomingRelations,OutgoingRelations,parallels,maxNumber) - //println('''Level «range» finished.''') - val res = createFurtherRepresentation(r.key,r.value,previous,deepRepresentation) - if(res.modelRepresentation === null) { + } else + return res + } else if (range > 0) { + val previous = doRecursiveNeighbourCalculation(model, types, IncomingRelations, OutgoingRelations, + range - 1, parallels, maxNumber, focusedElement) + val r = calculateFurtherNodeDescriptors(model, previous, IncomingRelations, OutgoingRelations, parallels, + maxNumber) + // println('''Level «range» finished.''') + val res = createFurtherRepresentation(r.key, r.value, previous, deepRepresentation) + if (res.modelRepresentation === null) { throw new IllegalArgumentException('''Model representation is null''') - } else if(res.nodeRepresentations === null || res.nodeRepresentations.empty) { + } else if (res.nodeRepresentations === null || res.nodeRepresentations.empty) { throw new IllegalArgumentException('''No node representation''') - } else if(res.previousRepresentation === null && deepRepresentation) { + } else if (res.previousRepresentation === null && deepRepresentation) { throw new IllegalArgumentException('''Need previous representations''') - } else return res + } else + return res } else if (range == FixPointRage) { - return refineUntilFixpoint(model,types,IncomingRelations,OutgoingRelations,parallels,maxNumber) + return refineUntilFixpoint(model, types, IncomingRelations, OutgoingRelations, parallels, maxNumber, + focusedElement) } else if (range == GraphWidthRange) { - val width = this.getWidth(types,IncomingRelations,OutgoingRelations) - //println(width) - return doRecursiveNeighbourCalculation(model,types,IncomingRelations,OutgoingRelations,width,parallels,maxNumber) + val width = this.getWidth(types, IncomingRelations, OutgoingRelations) + // println(width) + return doRecursiveNeighbourCalculation(model, types, IncomingRelations, OutgoingRelations, width, parallels, + maxNumber, focusedElement) } } - - def private refineUntilFixpoint( - PartialInterpretation model, - Map> types, + + def private refineUntilFixpoint(PartialInterpretation model, Map> types, Map>> IncomingRelations, - Map>> OutgoingRelations, - int parallels, int maxNumbers) - { + Map>> OutgoingRelations, int parallels, int maxNumbers, + DefinedElement focusedElement) { var lastRange = 0 - val last = calculateLocalNodeDescriptors(model,types,maxNumbers) - var lastRepresentation = this.createLocalRepresentation(last.value,last.key) - //println('''Level 0 finished.''') + val last = calculateLocalNodeDescriptors(model, types, maxNumbers, focusedElement) + var lastRepresentation = this.createLocalRepresentation(last.value, last.key) + // println('''Level 0 finished.''') var boolean hasRefined do { - val nextRange = lastRange+1 - val next = calculateFurtherNodeDescriptors(model,lastRepresentation,IncomingRelations,OutgoingRelations,parallels,maxNumbers) - val nextRepresentation = createFurtherRepresentation(next.key,next.value,lastRepresentation,deepRepresentation) - - val previousNumberOfTypes =lastRepresentation.nodeRepresentations.values.toSet.size + val nextRange = lastRange + 1 + val next = calculateFurtherNodeDescriptors(model, lastRepresentation, IncomingRelations, OutgoingRelations, + parallels, maxNumbers) + val nextRepresentation = createFurtherRepresentation(next.key, next.value, lastRepresentation, + deepRepresentation) + + val previousNumberOfTypes = lastRepresentation.nodeRepresentations.values.toSet.size val nextNumberOfTypes = nextRepresentation.nodeRepresentations.values.toSet.size - hasRefined = nextNumberOfTypes > previousNumberOfTypes - + hasRefined = nextNumberOfTypes > previousNumberOfTypes + lastRange = nextRange lastRepresentation = nextRepresentation - + // if(hasRefined) { // println('''Level «nextRange» is calculated, number of types is refined: «previousNumberOfTypes» -> «nextNumberOfTypes»''') // } else { @@ -192,211 +218,219 @@ abstract class PartialInterpretation2NeighbourhoodRepresentation> node2Type, Set relevantTypes) { - for(element : model.elements) { + + def private fillTypes(PartialInterpretation model, Map> node2Type, + Set relevantTypes) { + for (element : model.elements) { node2Type.put(element, new HashSet) } - + // for(typeDefinition : model.problem.types.filter(TypeDefinition)) { // // Dont need // } - for(typeInterpretation : model.partialtypeinterpratation) { - if(typeInterpretation instanceof PartialPrimitiveInterpretation) { - - } else if(typeInterpretation instanceof PartialComplexTypeInterpretation) { + for (typeInterpretation : model.partialtypeinterpratation) { + if (typeInterpretation instanceof PartialPrimitiveInterpretation) { + } else if (typeInterpretation instanceof PartialComplexTypeInterpretation) { val type = typeInterpretation.interpretationOf - if(type.isRelevant(relevantTypes)) { - for(element : typeInterpretation.elements) { + if (type.isRelevant(relevantTypes)) { + for (element : typeInterpretation.elements) { element.lookup(node2Type).add(type.name) } } } } } - + /** * Indexes the references */ def private fillReferences(PartialInterpretation model, Map>> IncomingRelations, Map>> OutgoingRelations, - Set relevantRelations) - { - for(object : model.elements) { - IncomingRelations.put(object,new LinkedList) - OutgoingRelations.put(object,new LinkedList) + Set relevantRelations) { + for (object : model.elements) { + IncomingRelations.put(object, new ArrayList) + OutgoingRelations.put(object, new ArrayList) } - for(relationInterpretation : model.partialrelationinterpretation) { + for (relationInterpretation : model.partialrelationinterpretation) { val type = relationInterpretation.interpretationOf - if(type.isRelevant(relevantRelations)) { - for(link : relationInterpretation.relationlinks) { - if(link instanceof BinaryElementRelationLink) { - OutgoingRelations.get(link.param1) += new OutgoingRelation(link.param2,type.name) - IncomingRelations.get(link.param2) += new IncomingRelation(link.param1,type.name) - } else throw new UnsupportedOperationException + if (type.isRelevant(relevantRelations)) { + for (link : relationInterpretation.relationlinks) { + if (link instanceof BinaryElementRelationLink) { + OutgoingRelations.get(link.param1) += new OutgoingRelation(link.param2, type.name) + IncomingRelations.get(link.param2) += new IncomingRelation(link.param1, type.name) + } else + throw new UnsupportedOperationException } } } } - + /** * Creates a local representation of the objects (aka zero range neighbourhood) */ - def abstract protected NeighbourhoodWithTraces createLocalRepresentation( + def abstract protected NeighbourhoodWithTraces createLocalRepresentation( Map node2Representation, Map representation2Amount ) - + /** * Creates a */ - def abstract protected NeighbourhoodWithTraces createFurtherRepresentation( + def abstract protected NeighbourhoodWithTraces createFurtherRepresentation( Map, Integer> nodeDescriptors, Map> node2Representation, - NeighbourhoodWithTraces previous, + NeighbourhoodWithTraces previous, boolean deepRepresentation ) - + def private addOne(int original, int max) { if(original == Integer.MAX_VALUE) return Integer.MAX_VALUE - if(original +1 > max) return Integer.MAX_VALUE - else return original+1 + if(original + 1 > max) return Integer.MAX_VALUE else return original + 1 } - + private def calculateIncomingEdges(Map>> IncomingRelations, - DefinedElement object, Map previousNodeRepresentations, int parallel) - { + DefinedElement object, Map previousNodeRepresentations, + int parallel) { val Map, Integer> res = new HashMap for (incomingConcreteEdge : IncomingRelations.get(object)) { val IncomingRelation e = new IncomingRelation( previousNodeRepresentations.get(incomingConcreteEdge.from), incomingConcreteEdge.type) if (res.containsKey(e)) { - res.put(e, addOne(res.get(e),parallel)) + res.put(e, addOne(res.get(e), parallel)) } else { res.put(e, 1) } } return res } - - private def calcuateOutgoingEdges(Map>> OutgoingRelations, - DefinedElement object, Map previousNodeRepresentations, int parallel) - { - val Map,Integer> res= new HashMap - for(outgoingConcreteEdge : OutgoingRelations.get(object)) { - val OutgoingRelation e = - new OutgoingRelation( - previousNodeRepresentations.get(outgoingConcreteEdge.to), - outgoingConcreteEdge.type) - if(res.containsKey(e)) { - res.put(e,addOne(res.get(e),parallel)) + + private def calcuateOutgoingEdges(Map>> OutgoingRelations, + DefinedElement object, Map previousNodeRepresentations, + int parallel) { + val Map, Integer> res = new HashMap + for (outgoingConcreteEdge : OutgoingRelations.get(object)) { + val OutgoingRelation e = new OutgoingRelation( + previousNodeRepresentations.get(outgoingConcreteEdge.to), outgoingConcreteEdge.type) + if (res.containsKey(e)) { + res.put(e, addOne(res.get(e), parallel)) } else { - res.put(e,1) + res.put(e, 1) } } return res; } - + /*def private void addOrCreate_Set(Map> map, KEY key, VALUE value) { - var Set s; - if(map.containsKey(key)) { - s = map.get(key); - } else { - s = new HashSet - map.put(key,s) - } - s.add(value) - }*/ - - - private def calculateFurtherNodeDescriptors( - PartialInterpretation model, + * var Set s; + * if(map.containsKey(key)) { + * s = map.get(key); + * } else { + * s = new HashSet + * map.put(key,s) + * } + * s.add(value) + }*/ + private def calculateFurtherNodeDescriptors(PartialInterpretation model, NeighbourhoodWithTraces previous, Map>> IncomingRelations, - Map>> OutgoingRelations, - int parallels, int maxNumber) - { + Map>> OutgoingRelations, int parallels, int maxNumber) { val previousNodeRepresentations = previous.nodeRepresentations - val node2Representation = new HashMap> - val Map,Integer> descriptor2Number = - if(this.mergeSimilarNeighbourhood){ new HashMap } else { null } - val Map,FurtherNodeDescriptor> uniqueDescription = - if(this.mergeSimilarNeighbourhood){ new HashMap } else { null } - - for(object: model.elements) { - val incomingEdges = this.calculateIncomingEdges(IncomingRelations, object, previousNodeRepresentations,parallels) - val outgoingEdges = this.calcuateOutgoingEdges(OutgoingRelations,object, previousNodeRepresentations,parallels) - + val node2Representation = new HashMap> + val Map, Integer> descriptor2Number = if (this. + mergeSimilarNeighbourhood) { + new HashMap + } else { + null + } + val Map, FurtherNodeDescriptor> uniqueDescription = if (this. + mergeSimilarNeighbourhood) { + new HashMap + } else { + null + } + + for (object : model.elements) { + val incomingEdges = this.calculateIncomingEdges(IncomingRelations, object, previousNodeRepresentations, + parallels) + val outgoingEdges = this.calcuateOutgoingEdges(OutgoingRelations, object, previousNodeRepresentations, + parallels) + val previousType = previousNodeRepresentations.get(object) - - if(previousType === null) { + + if (previousType === null) { println("Error in state coder") } - - val nodeDescriptor = new FurtherNodeDescriptor( - previousType, - incomingEdges, - outgoingEdges) - - if(this.mergeSimilarNeighbourhood) { - if(descriptor2Number.containsKey(nodeDescriptor)) { + + val nodeDescriptor = new FurtherNodeDescriptor(previousType, incomingEdges, outgoingEdges) + + if (this.mergeSimilarNeighbourhood) { + if (descriptor2Number.containsKey(nodeDescriptor)) { descriptor2Number.put( nodeDescriptor, - addOne(descriptor2Number.get(nodeDescriptor),maxNumber) + addOne(descriptor2Number.get(nodeDescriptor), maxNumber) ) - node2Representation.put(object,uniqueDescription.get(nodeDescriptor)) + node2Representation.put(object, uniqueDescription.get(nodeDescriptor)) } else { - descriptor2Number.put(nodeDescriptor,if(1>maxNumber){Integer.MAX_VALUE}else{1}) - uniqueDescription.put(nodeDescriptor,nodeDescriptor) - node2Representation.put(object,nodeDescriptor) + descriptor2Number.put(nodeDescriptor, if (1 > maxNumber) { + Integer.MAX_VALUE + } else { + 1 + }) + uniqueDescription.put(nodeDescriptor, nodeDescriptor) + node2Representation.put(object, nodeDescriptor) } } else { - node2Representation.put(object,nodeDescriptor) + node2Representation.put(object, nodeDescriptor) } } - + return descriptor2Number -> node2Representation } - - private def calculateLocalNodeDescriptors( - PartialInterpretation model, - Map> types, - int maxNumber) - { + + private def calculateLocalNodeDescriptors(PartialInterpretation model, Map> types, + int maxNumber, DefinedElement focusedElement) { val Map node2Representation = new HashMap - val Map representation2Amount = - if(mergeSimilarNeighbourhood){ new HashMap } else { null } - val Map uniqueRepresentation = - if(this.mergeSimilarNeighbourhood){ new HashMap } else { null } - - for(element : model.elements) { - var newDescriptor = new LocalNodeDescriptor(element.name,element.lookup(types)) - if(this.mergeSimilarNeighbourhood){ - if(uniqueRepresentation.containsKey(newDescriptor)) { + val Map representation2Amount = if (mergeSimilarNeighbourhood) { + new HashMap + } else { + null + } + val Map uniqueRepresentation = if (this.mergeSimilarNeighbourhood) { + new HashMap + } else { + null + } + + for (element : model.elements) { + val name = if(element == focusedElement) FOCUSED_ELEMENT_NAME else element.name + var newDescriptor = new LocalNodeDescriptor(name, element.lookup(types)) + if (this.mergeSimilarNeighbourhood) { + if (uniqueRepresentation.containsKey(newDescriptor)) { newDescriptor = newDescriptor.lookup(uniqueRepresentation) - node2Representation.put(element,newDescriptor) + node2Representation.put(element, newDescriptor) representation2Amount.put( newDescriptor, - addOne(newDescriptor.lookup(representation2Amount),maxNumber) + addOne(newDescriptor.lookup(representation2Amount), maxNumber) ) } else { - uniqueRepresentation.put(newDescriptor,newDescriptor) - node2Representation.put(element,newDescriptor) - representation2Amount.put(newDescriptor, if(1>maxNumber){Integer.MAX_VALUE}else{1}) + uniqueRepresentation.put(newDescriptor, newDescriptor) + node2Representation.put(element, newDescriptor) + representation2Amount.put(newDescriptor, if (1 > maxNumber) { + Integer.MAX_VALUE + } else { + 1 + }) } } else { - node2Representation.put(element,newDescriptor) + node2Representation.put(element, newDescriptor) } } - + return representation2Amount -> node2Representation } -} \ No newline at end of file +} -- cgit v1.2.3-54-g00ecf