From 8eb1b7a14972e52018a1bb69a53f2878e96b581e Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Mon, 7 Aug 2023 02:45:57 +0200 Subject: StateCoderBuilder improvement with individuals, and customizable calculators. --- .../statecoding/StateCodeCalculatorFactory.java | 15 +++ .../store/statecoding/StateCoderBuilder.java | 16 +++ .../store/statecoding/StateEquivalenceChecker.java | 2 + .../internal/StateCoderAdapterImpl.java | 12 +- .../internal/StateCoderBuilderImpl.java | 34 +++++- .../internal/StateCoderStoreAdapterImpl.java | 29 +++-- .../AbstractNeighbourhoodCalculator.java | 95 +++++++++++++++ .../neighbourhood/LazyNeighbourhoodCalculator.java | 100 ++++------------ .../LazyNeighbourhoodCalculatorFactory.java | 20 ++++ .../neighbourhood/NeighbourhoodCalculator.java | 132 --------------------- .../StateEquivalenceCheckerImpl.java | 42 ++++--- .../store/statecoding/StateCoderBuildTest.java | 51 +++++++- 12 files changed, 297 insertions(+), 251 deletions(-) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java new file mode 100644 index 00000000..04e17a13 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculatorFactory.java @@ -0,0 +1,15 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +import org.eclipse.collections.api.set.primitive.IntSet; +import tools.refinery.store.model.Interpretation; + +import java.util.List; + +public interface StateCodeCalculatorFactory { + StateCodeCalculator create(List> interpretations, IntSet individuals); +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java index 2f37584f..54650825 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java @@ -8,7 +8,9 @@ package tools.refinery.store.statecoding; import tools.refinery.store.adapter.ModelAdapterBuilder; import tools.refinery.store.model.ModelStore; import tools.refinery.store.representation.AnySymbol; +import tools.refinery.store.tuple.Tuple1; +import java.util.Arrays; import java.util.Collection; import java.util.List; @@ -24,6 +26,20 @@ public interface StateCoderBuilder extends ModelAdapterBuilder { return excludeAll(List.of(symbols)); } + StateCoderBuilder individual(Tuple1 tuple); + default StateCoderBuilder individual(Collection tuple1s) { + for(Tuple1 tuple : tuple1s){ + individual(tuple); + } + return this; + } + default StateCoderBuilder individuals(Tuple1... tuple1s) { + return individual(Arrays.stream(tuple1s).toList()); + } + + StateCoderBuilder stateCodeCalculatorFactory(StateCodeCalculatorFactory codeCalculatorFactory); + StateCoderBuilder stateEquivalenceChecker(StateEquivalenceChecker stateEquivalenceChecker); + @Override StateCoderStoreAdapter build(ModelStore store); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java index 6d8dc6c7..3fd8c8d8 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateEquivalenceChecker.java @@ -5,6 +5,7 @@ */ package tools.refinery.store.statecoding; +import org.eclipse.collections.api.set.primitive.IntSet; import tools.refinery.store.model.Interpretation; import java.util.List; @@ -15,6 +16,7 @@ public interface StateEquivalenceChecker { } EquivalenceResult constructMorphism( + IntSet individuals, List> interpretations1, ObjectCode code1, List> interpretations2, diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java index b66fc86d..a2471916 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java @@ -6,28 +6,20 @@ package tools.refinery.store.statecoding.internal; import tools.refinery.store.adapter.ModelStoreAdapter; -import tools.refinery.store.model.Interpretation; import tools.refinery.store.model.Model; -import tools.refinery.store.representation.Symbol; import tools.refinery.store.statecoding.StateCodeCalculator; import tools.refinery.store.statecoding.StateCoderAdapter; import tools.refinery.store.statecoding.StateCoderResult; -import tools.refinery.store.statecoding.neighbourhood.LazyNeighbourhoodCalculator; - -import java.util.Collection; -import java.util.List; public class StateCoderAdapterImpl implements StateCoderAdapter { final ModelStoreAdapter storeAdapter; final Model model; final StateCodeCalculator calculator; - StateCoderAdapterImpl(ModelStoreAdapter storeAdapter, Model model, Collection> symbols) { + StateCoderAdapterImpl(ModelStoreAdapter storeAdapter, StateCodeCalculator calculator, Model model) { this.storeAdapter = storeAdapter; this.model = model; - - List> interpretations = symbols.stream().map(model::getInterpretation).toList(); - calculator = new LazyNeighbourhoodCalculator(interpretations); + this.calculator = calculator; } @Override diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java index 700723f4..8268a826 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java @@ -5,19 +5,27 @@ */ package tools.refinery.store.statecoding.internal; +import org.eclipse.collections.impl.set.mutable.primitive.IntHashSet; import tools.refinery.store.model.ModelStore; import tools.refinery.store.model.ModelStoreBuilder; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; +import tools.refinery.store.statecoding.StateCodeCalculatorFactory; import tools.refinery.store.statecoding.StateCoderBuilder; import tools.refinery.store.statecoding.StateCoderStoreAdapter; +import tools.refinery.store.statecoding.StateEquivalenceChecker; +import tools.refinery.store.statecoding.neighbourhood.LazyNeighbourhoodCalculatorFactory; +import tools.refinery.store.statecoding.stateequivalence.StateEquivalenceCheckerImpl; +import tools.refinery.store.tuple.Tuple1; -import java.util.HashSet; -import java.util.LinkedHashSet; -import java.util.Set; +import java.util.*; public class StateCoderBuilderImpl implements StateCoderBuilder { Set excluded = new HashSet<>(); + IntHashSet individuals = new IntHashSet(); + + StateCodeCalculatorFactory calculator = new LazyNeighbourhoodCalculatorFactory(); + StateEquivalenceChecker checker = new StateEquivalenceCheckerImpl(); @Override public StateCoderBuilder exclude(AnySymbol symbol) { @@ -25,6 +33,24 @@ public class StateCoderBuilderImpl implements StateCoderBuilder { return this; } + @Override + public StateCoderBuilder individual(Tuple1 tuple) { + individuals.add(tuple.get(0)); + return this; + } + + @Override + public StateCoderBuilder stateEquivalenceChecker(StateEquivalenceChecker stateEquivalenceChecker) { + this.checker = stateEquivalenceChecker; + return this; + } + + @Override + public StateCoderBuilder stateCodeCalculatorFactory(StateCodeCalculatorFactory codeCalculatorFactory) { + this.calculator = codeCalculatorFactory; + return this; + } + @Override public boolean isConfigured() { return true; @@ -43,6 +69,6 @@ public class StateCoderBuilderImpl implements StateCoderBuilder { symbols.add(typed); } } - return new StateCoderStoreAdapterImpl(store, symbols); + return new StateCoderStoreAdapterImpl(store, calculator, checker, symbols, individuals); } } diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java index 5374755d..89586bfb 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java @@ -5,14 +5,15 @@ */ package tools.refinery.store.statecoding.internal; +import org.eclipse.collections.api.set.primitive.IntSet; import tools.refinery.store.map.Version; import tools.refinery.store.model.Model; import tools.refinery.store.model.ModelStore; import tools.refinery.store.representation.Symbol; +import tools.refinery.store.statecoding.StateCodeCalculatorFactory; import tools.refinery.store.statecoding.StateCoderAdapter; import tools.refinery.store.statecoding.StateCoderStoreAdapter; import tools.refinery.store.statecoding.StateEquivalenceChecker; -import tools.refinery.store.statecoding.stateequivalence.StateEquivalenceCheckerImpl; import java.util.Collection; import java.util.Objects; @@ -20,12 +21,22 @@ import java.util.Objects; public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter { final ModelStore store; final Collection> symbols; + final IntSet individuals; - final StateEquivalenceChecker equivalenceChecker = new StateEquivalenceCheckerImpl(); + final StateEquivalenceChecker equivalenceChecker; + final StateCodeCalculatorFactory codeCalculatorFactory; - StateCoderStoreAdapterImpl(ModelStore store, Collection> symbols) { + StateCoderStoreAdapterImpl(ModelStore store, + StateCodeCalculatorFactory codeCalculatorFactory, + StateEquivalenceChecker equivalenceChecker, + Collection> symbols, + IntSet individuals) + { + this.codeCalculatorFactory = codeCalculatorFactory; + this.equivalenceChecker = equivalenceChecker; this.store = store; this.symbols = symbols; + this.individuals = individuals; } @Override @@ -35,7 +46,7 @@ public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter { @Override public StateEquivalenceChecker.EquivalenceResult checkEquivalence(Version v1, Version v2) { - if(Objects.equals(v1,v2)) { + if (Objects.equals(v1, v2)) { return StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC; } var model1 = this.getStore().createModelForState(v1); @@ -44,20 +55,20 @@ public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter { var s1 = model1.getAdapter(StateCoderAdapter.class).calculateStateCode(); var s2 = model2.getAdapter(StateCoderAdapter.class).calculateStateCode(); - if(s1.modelCode() != s2.modelCode()) { + if (s1.modelCode() != s2.modelCode()) { return StateEquivalenceChecker.EquivalenceResult.DIFFERENT; } var i1 = symbols.stream().map(model1::getInterpretation).toList(); var i2 = symbols.stream().map(model2::getInterpretation).toList(); - return equivalenceChecker.constructMorphism(i1,s1.objectCode(),i2,s2.objectCode()); + return equivalenceChecker.constructMorphism(individuals, i1, s1.objectCode(), i2, s2.objectCode()); } @Override public StateCoderAdapter createModelAdapter(Model model) { - return new StateCoderAdapterImpl(this,model,symbols); + var interpretations = symbols.stream().map(model::getInterpretation).toList(); + var coder = codeCalculatorFactory.create(interpretations, individuals); + return new StateCoderAdapterImpl(this, coder, model); } - - } diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java new file mode 100644 index 00000000..0de76519 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java @@ -0,0 +1,95 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighbourhood; + +import org.eclipse.collections.api.set.primitive.IntSet; +import org.eclipse.collections.impl.map.mutable.primitive.IntLongHashMap; +import org.eclipse.collections.impl.map.mutable.primitive.LongIntHashMap; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.statecoding.ObjectCode; +import tools.refinery.store.tuple.Tuple; +import tools.refinery.store.tuple.Tuple0; + +import java.util.ArrayList; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Random; + +public abstract class AbstractNeighbourhoodCalculator { + protected final List> nullImpactValues; + protected final LinkedHashMap, long[]> impactValues; + protected final IntLongHashMap individualHashValues; + + protected AbstractNeighbourhoodCalculator(List> interpretations, IntSet individuals) { + this.nullImpactValues = new ArrayList<>(); + this.impactValues = new LinkedHashMap<>(); + Random random = new Random(1); + + individualHashValues = new IntLongHashMap(); + var individualsInOrder = individuals.toSortedList(Integer::compare); + for(int i = 0; i interpretation : interpretations) { + int arity = interpretation.getSymbol().arity(); + if (arity == 0) { + nullImpactValues.add(interpretation); + } else { + long[] impact = new long[arity]; + for (int i = 0; i < arity; i++) { + impact[i] = random.nextInt(); + } + impactValues.put(interpretation, impact); + } + } + } + + protected void initializeWithIndividuals(ObjectCodeImpl previous, LongIntHashMap hash2Amount) { + for (var entry : individualHashValues.keyValuesView()) { + previous.set(entry.getOne(), entry.getTwo()); + hash2Amount.put(entry.getTwo(), 1); + } + } + + protected long getTupleHash1(Tuple tuple, Object value, ObjectCode objectCodeImpl) { + long result = value.hashCode(); + result = result * 31 + objectCodeImpl.get(tuple.get(0)); + return result; + } + + protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) { + long result = value.hashCode(); + result = result * 31 + objectCodeImpl.get(tuple.get(0)); + result = result * 31 + objectCodeImpl.get(tuple.get(1)); + if (tuple.get(0) == tuple.get(1)) { + result *= 31; + } + return result; + } + + protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) { + long result = value.hashCode(); + for (int i = 0; i < tuple.getSize(); i++) { + result = result * 31 + objectCodeImpl.get(tuple.get(i)); + } + return result; + } + + protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) { + long x = tupleHash * impact; + objectCodeImpl.set(o, objectCodeImpl.get(o) + x); + } + + protected long calculateModelCode(long lastSum) { + long result = 1; + for (var nullImpactValue : nullImpactValues) { + result = result * 31 + nullImpactValue.get(Tuple0.INSTANCE).hashCode(); + } + result += lastSum; + return result; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java index 79317679..98a75e08 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java @@ -6,74 +6,48 @@ package tools.refinery.store.statecoding.neighbourhood; import org.eclipse.collections.api.map.primitive.LongIntMap; +import org.eclipse.collections.api.set.primitive.IntSet; import org.eclipse.collections.impl.map.mutable.primitive.LongIntHashMap; import tools.refinery.store.map.Cursor; import tools.refinery.store.model.Interpretation; import tools.refinery.store.statecoding.StateCodeCalculator; import tools.refinery.store.statecoding.StateCoderResult; import tools.refinery.store.tuple.Tuple; -import tools.refinery.store.tuple.Tuple0; -import java.util.ArrayList; -import java.util.LinkedHashMap; import java.util.List; -import java.util.Random; -public class LazyNeighbourhoodCalculator implements StateCodeCalculator { - protected final List> nullImpactValues; - protected final LinkedHashMap, long[]> impactValues; - - public LazyNeighbourhoodCalculator(List> interpretations) { - this.nullImpactValues = new ArrayList<>(); - this.impactValues = new LinkedHashMap<>(); - Random random = new Random(1); - - for (Interpretation interpretation : interpretations) { - int arity = interpretation.getSymbol().arity(); - if (arity == 0) { - nullImpactValues.add(interpretation); - } else { - long[] impact = new long[arity]; - for (int i = 0; i < arity; i++) { - impact[i] = random.nextInt(); - } - impactValues.put(interpretation, impact); - } - } +public class LazyNeighbourhoodCalculator extends AbstractNeighbourhoodCalculator implements StateCodeCalculator { + public LazyNeighbourhoodCalculator(List> interpretations, IntSet individuals) { + super(interpretations, individuals); } public StateCoderResult calculateCodes() { ObjectCodeImpl previous = new ObjectCodeImpl(); - ObjectCodeImpl next = new ObjectCodeImpl(); - LongIntMap hash2Amount = new LongIntHashMap(); + LongIntHashMap hash2Amount = new LongIntHashMap(); + + initializeWithIndividuals(previous, hash2Amount); long lastSum; - int lastSize = 1; - boolean grows; + // All hash code is 0, except to the individuals. + int lastSize = hash2Amount.size() + 1; + boolean grows; do { + ObjectCodeImpl next = new ObjectCodeImpl(); constructNextObjectCodes(previous, next, hash2Amount); LongIntHashMap nextHash2Amount = new LongIntHashMap(); lastSum = calculateLastSum(previous, next, hash2Amount, nextHash2Amount); - previous = next; - next = null; - int nextSize = nextHash2Amount.size(); grows = nextSize > lastSize; lastSize = nextSize; - if (grows) { - next = new ObjectCodeImpl(previous); - } + previous = next; + hash2Amount = nextHash2Amount; } while (grows); - long result = 1; - for (var nullImpactValue : nullImpactValues) { - result = result * 31 + nullImpactValue.get(Tuple0.INSTANCE).hashCode(); - } - result += lastSum; + long result = calculateModelCode(lastSum); return new StateCoderResult((int) result, previous); } @@ -96,7 +70,7 @@ public class LazyNeighbourhoodCalculator implements StateCodeCalculator { final long shifted1 = hash >>> 8; final long shifted2 = hash << 8; final long shifted3 = hash >> 2; - lastSum += shifted1*shifted3 + shifted2; + lastSum += shifted1 * shifted3 + shifted2; } return lastSum; } @@ -126,7 +100,7 @@ public class LazyNeighbourhoodCalculator implements StateCodeCalculator { private boolean isUnique(LongIntMap hash2Amount, ObjectCodeImpl objectCodeImpl, int object) { final long hash = objectCodeImpl.get(object); - if(hash == 0) { + if (hash == 0) { return false; } final int amount = hash2Amount.get(hash); @@ -149,12 +123,12 @@ public class LazyNeighbourhoodCalculator implements StateCodeCalculator { } private void lazyImpactCalculation2(LongIntMap hash2Amount, ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { - Tuple tuple = cursor.getKey(); - int o1 = tuple.get(0); - int o2 = tuple.get(1); + final Tuple tuple = cursor.getKey(); + final int o1 = tuple.get(0); + final int o2 = tuple.get(1); - boolean u1 = isUnique(hash2Amount, previous, o1); - boolean u2 = isUnique(hash2Amount, previous, o2); + final boolean u1 = isUnique(hash2Amount, previous, o1); + final boolean u2 = isUnique(hash2Amount, previous, o2); if (u1 && u2) { next.ensureSize(o1); @@ -175,9 +149,9 @@ public class LazyNeighbourhoodCalculator implements StateCodeCalculator { } private void lazyImpactCalculationN(LongIntMap hash2Amount, ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { - Tuple tuple = cursor.getKey(); + final Tuple tuple = cursor.getKey(); - boolean[] uniques = new boolean[tuple.getSize()]; + final boolean[] uniques = new boolean[tuple.getSize()]; boolean allUnique = true; for (int i = 0; i < tuple.getSize(); i++) { final boolean isUnique = isUnique(hash2Amount, previous, tuple.get(i)); @@ -204,32 +178,4 @@ public class LazyNeighbourhoodCalculator implements StateCodeCalculator { } } - private long getTupleHash1(Tuple tuple, Object value, ObjectCodeImpl objectCodeImpl) { - long result = value.hashCode(); - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - return result; - } - - private long getTupleHash2(Tuple tuple, Object value, ObjectCodeImpl objectCodeImpl) { - long result = value.hashCode(); - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - result = result * 31 + objectCodeImpl.get(tuple.get(1)); - if (tuple.get(0) == tuple.get(1)) { - result*=31; - } - return result; - } - - private long getTupleHashN(Tuple tuple, Object value, ObjectCodeImpl objectCodeImpl) { - long result = value.hashCode(); - for (int i = 0; i < tuple.getSize(); i++) { - result = result * 31 + objectCodeImpl.get(tuple.get(i)); - } - return result; - } - - protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) { - long x = tupleHash * impact; - objectCodeImpl.set(o, objectCodeImpl.get(o) + x); - } } diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java new file mode 100644 index 00000000..2e499f95 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java @@ -0,0 +1,20 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighbourhood; + +import org.eclipse.collections.api.set.primitive.IntSet; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.statecoding.StateCodeCalculator; +import tools.refinery.store.statecoding.StateCodeCalculatorFactory; + +import java.util.List; + +public class LazyNeighbourhoodCalculatorFactory implements StateCodeCalculatorFactory { + @Override + public StateCodeCalculator create(List> interpretations, IntSet individuals) { + return new LazyNeighbourhoodCalculator(interpretations,individuals); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java deleted file mode 100644 index 212291c3..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java +++ /dev/null @@ -1,132 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.statecoding.neighbourhood; - -import org.eclipse.collections.api.set.primitive.MutableLongSet; -import org.eclipse.collections.impl.set.mutable.primitive.LongHashSet; -import tools.refinery.store.model.Interpretation; -import tools.refinery.store.statecoding.StateCodeCalculator; -import tools.refinery.store.statecoding.StateCoderResult; -import tools.refinery.store.tuple.Tuple; -import tools.refinery.store.tuple.Tuple0; - -import java.util.ArrayList; -import java.util.LinkedHashMap; -import java.util.List; -import java.util.Random; - -public class NeighbourhoodCalculator implements StateCodeCalculator { - protected final List> nullImpactValues; - protected final LinkedHashMap, long[]> impactValues; - - public NeighbourhoodCalculator(List> interpretations) { - this.nullImpactValues = new ArrayList<>(); - this.impactValues = new LinkedHashMap<>(); - Random random = new Random(1); - - for (Interpretation interpretation : interpretations) { - int arity = interpretation.getSymbol().arity(); - if (arity == 0) { - nullImpactValues.add(interpretation); - } else { - long[] impact = new long[arity]; - for (int i = 0; i < arity; i++) { - impact[i] = random.nextLong(); - } - impactValues.put(interpretation, impact); - } - } - } - - @Override - public StateCoderResult calculateCodes() { - ObjectCodeImpl previous = new ObjectCodeImpl(); - ObjectCodeImpl next = new ObjectCodeImpl(); - - int previousSize = 1; - long lastSum; - boolean grows; - - do{ - for (var impactValueEntry : this.impactValues.entrySet()) { - Interpretation interpretation = impactValueEntry.getKey(); - long[] impact = impactValueEntry.getValue(); - var cursor = interpretation.getAll(); - while (cursor.move()) { - Tuple tuple = cursor.getKey(); - Object value = cursor.getValue(); - long tupleHash = getTupleHash(tuple, value, previous); - addHash(next, tuple, impact, tupleHash); - } - } - - previous = next; - next = null; - lastSum = 0; - MutableLongSet codes = new LongHashSet(); - for (int i = 0; i < previous.getSize(); i++) { - long objectHash = previous.get(i); - codes.add(objectHash); - - final long shifted1 = objectHash>>> 32; - final long shifted2 = objectHash << 32; - lastSum += shifted1 + shifted2; - } - int nextSize = codes.size(); - grows = previousSize < nextSize; - previousSize = nextSize; - - if(grows) { - next = new ObjectCodeImpl(previous); - } - } while (grows); - - long result = 1; - for (var nullImpactValue : nullImpactValues) { - result = result * 31 + nullImpactValue.get(Tuple0.INSTANCE).hashCode(); - } - result += lastSum; - - return new StateCoderResult((int) result, previous); - } - - protected long getTupleHash(Tuple tuple, Object value, ObjectCodeImpl objectCodeImpl) { - long result = value.hashCode(); - int arity = tuple.getSize(); - if (arity == 1) { - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - } else if (arity == 2) { - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - result = result * 31 + objectCodeImpl.get(tuple.get(1)); - if (tuple.get(0) == tuple.get(1)) { - result++; - } - } else if (arity > 2) { - for (int i = 0; i < arity; i++) { - result = result * 31 + objectCodeImpl.get(tuple.get(i)); - } - } - return result; - } - - protected void addHash(ObjectCodeImpl objectCodeImpl, Tuple tuple, long[] impact, long tupleHashCode) { - if (tuple.getSize() == 1) { - addHash(objectCodeImpl, tuple.get(0), impact[0], tupleHashCode); - } else if (tuple.getSize() == 2) { - addHash(objectCodeImpl, tuple.get(0), impact[0], tupleHashCode); - addHash(objectCodeImpl, tuple.get(1), impact[1], tupleHashCode); - } else if (tuple.getSize() > 2) { - for (int i = 0; i < tuple.getSize(); i++) { - addHash(objectCodeImpl, tuple.get(i), impact[i], tupleHashCode); - } - } - } - - protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) { - objectCodeImpl.set(o, objectCodeImpl.get(o) + tupleHash * impact); - } - -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java index fd704086..e58a2502 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/stateequivalence/StateEquivalenceCheckerImpl.java @@ -5,7 +5,9 @@ */ package tools.refinery.store.statecoding.stateequivalence; +import org.eclipse.collections.api.factory.primitive.IntIntMaps; import org.eclipse.collections.api.map.primitive.IntIntMap; +import org.eclipse.collections.api.set.primitive.IntSet; import org.eclipse.collections.impl.map.mutable.primitive.IntIntHashMap; import org.eclipse.collections.impl.map.mutable.primitive.LongObjectHashMap; import org.eclipse.collections.impl.set.mutable.primitive.IntHashSet; @@ -23,7 +25,8 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { public static final int LIMIT = 1000; @Override - public EquivalenceResult constructMorphism(List> interpretations1, + public EquivalenceResult constructMorphism(IntSet individuals, + List> interpretations1, ObjectCode code1, List> interpretations2, ObjectCode code2) { @@ -34,7 +37,8 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { IntIntHashMap object2PermutationGroup = new IntIntHashMap(); List> permutationsGroups = new ArrayList<>(); - final EquivalenceResult permutations = constructPermutationNavigation(indexByHash(code1), indexByHash(code2), + final EquivalenceResult permutations = constructPermutationNavigation(individuals, + indexByHash(code1, individuals), indexByHash(code2, individuals), object2PermutationGroup, permutationsGroups); if (permutations == EquivalenceResult.DIFFERENT) { @@ -60,24 +64,27 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { return EquivalenceResult.DIFFERENT; } - private LongObjectHashMap indexByHash(ObjectCode code) { + private LongObjectHashMap indexByHash(ObjectCode code, IntSet individuals) { LongObjectHashMap result = new LongObjectHashMap<>(); for (int o = 0; o < code.getSize(); o++) { - long hash = code.get(o); - var equivalenceClass = result.get(hash); - if (equivalenceClass == null) { - equivalenceClass = new IntHashSet(); - result.put(hash, equivalenceClass); + if(! individuals.contains(o)){ + long hash = code.get(o); + var equivalenceClass = result.get(hash); + if (equivalenceClass == null) { + equivalenceClass = new IntHashSet(); + result.put(hash, equivalenceClass); + } + equivalenceClass.add(o); } - equivalenceClass.add(o); } return result; } - private EquivalenceResult constructPermutationNavigation(LongObjectHashMap map1, - LongObjectHashMap map2, - IntIntHashMap emptyMapToListOfOptions, - List> emptyListOfOptions) { + private EquivalenceResult constructPermutationNavigation(IntSet individuals, + LongObjectHashMap map1, + LongObjectHashMap map2, + IntIntHashMap object2OptionIndex, + List> listOfOptions) { if (map1.size() != map2.size()) { return EquivalenceResult.DIFFERENT; } @@ -101,10 +108,13 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { allComplete &= pairing.isComplete(); - final int optionIndex = emptyListOfOptions.size(); - set1.forEach(key -> emptyMapToListOfOptions.put(key, optionIndex)); - emptyListOfOptions.add(pairing.permutations()); + final int optionIndex = listOfOptions.size(); + set1.forEach(key -> object2OptionIndex.put(key, optionIndex)); + listOfOptions.add(pairing.permutations()); } + + individuals.forEach(o -> listOfOptions.add(o,List.of(IntIntMaps.immutable.of(o,o)))); + if(allComplete) { return EquivalenceResult.ISOMORPHIC; } else { diff --git a/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderBuildTest.java b/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderBuildTest.java index b0b80af7..a4e953ea 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderBuildTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderBuildTest.java @@ -19,11 +19,10 @@ class StateCoderBuildTest { Symbol friend = new Symbol<>("friend", 2, Boolean.class, false); @Test - void simpleStateCoderTest() { + void simpleStateCoderBuildTest() { var store = ModelStore.builder() .symbols(person, age, friend) - .with(StateCoderAdapter - .builder()) + .with(StateCoderAdapter.builder()) .build(); var model = store.createEmptyModel(); @@ -33,6 +32,7 @@ class StateCoderBuildTest { var personI = model.getInterpretation(person); var friendI = model.getInterpretation(friend); var ageI = model.getInterpretation(age); + fill(personI, friendI, ageI); stateCoder.calculateStateCode(); @@ -68,6 +68,51 @@ class StateCoderBuildTest { assertEquals(code,stateCoder.calculateStateCode().modelCode()); } + @Test + void notIndividualTest() { + var store = ModelStore.builder() + .symbols(friend) + .with(StateCoderAdapter.builder()) + .build(); + + var model = store.createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var friendI = model.getInterpretation(friend); + + friendI.put(Tuple.of(1,2),true); + int code1 = stateCoder.calculateModelCode(); + + friendI.put(Tuple.of(1,2),false); + friendI.put(Tuple.of(2,1),true); + int code2 = stateCoder.calculateModelCode(); + + assertEquals(code1,code2); + } + + @Test + void individualTest() { + var store = ModelStore.builder() + .symbols(friend) + .with(StateCoderAdapter.builder() + .individual(Tuple.of(1))) + .build(); + + var model = store.createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var friendI = model.getInterpretation(friend); + + friendI.put(Tuple.of(1,2),true); + int code1 = stateCoder.calculateModelCode(); + + friendI.put(Tuple.of(1,2),false); + friendI.put(Tuple.of(2,1),true); + int code2 = stateCoder.calculateModelCode(); + + assertNotEquals(code1,code2); + } + private static void fill(Interpretation personI, Interpretation friendI, Interpretation ageI) { personI.put(Tuple.of(1), true); personI.put(Tuple.of(2), true); -- cgit v1.2.3-70-g09d2