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 (limited to 'subprojects') 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 From 36550e2be2146b290210cb12c76d0341e499f849 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Mon, 7 Aug 2023 16:07:09 +0200 Subject: Tests + small changes for AbstractNeighbourhoodCalculator and StateEquivalenceCheckerImpl --- .../AbstractNeighbourhoodCalculator.java | 15 +- .../statecoding/neighbourhood/ObjectCodeImpl.java | 3 +- .../StateEquivalenceCheckerImpl.java | 19 +- .../store/statecoding/EquivalenceTest.java | 178 +++++++++++++++++++ .../store/statecoding/StateCoderUnitTest.java | 195 +++++++++++++++++++++ 5 files changed, 390 insertions(+), 20 deletions(-) create mode 100644 subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java create mode 100644 subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderUnitTest.java (limited to 'subprojects') 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 index 0de76519..c3f8a586 100644 --- 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 @@ -13,10 +13,7 @@ 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; +import java.util.*; public abstract class AbstractNeighbourhoodCalculator { protected final List> nullImpactValues; @@ -56,13 +53,13 @@ public abstract class AbstractNeighbourhoodCalculator { } protected long getTupleHash1(Tuple tuple, Object value, ObjectCode objectCodeImpl) { - long result = value.hashCode(); + long result = Objects.hashCode(value); result = result * 31 + objectCodeImpl.get(tuple.get(0)); return result; } protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) { - long result = value.hashCode(); + long result = Objects.hashCode(value); result = result * 31 + objectCodeImpl.get(tuple.get(0)); result = result * 31 + objectCodeImpl.get(tuple.get(1)); if (tuple.get(0) == tuple.get(1)) { @@ -72,7 +69,7 @@ public abstract class AbstractNeighbourhoodCalculator { } protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) { - long result = value.hashCode(); + long result = Objects.hashCode(value); for (int i = 0; i < tuple.getSize(); i++) { result = result * 31 + objectCodeImpl.get(tuple.get(i)); } @@ -85,9 +82,9 @@ public abstract class AbstractNeighbourhoodCalculator { } protected long calculateModelCode(long lastSum) { - long result = 1; + long result = 0; for (var nullImpactValue : nullImpactValues) { - result = result * 31 + nullImpactValue.get(Tuple0.INSTANCE).hashCode(); + result = result * 31 + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); } result += lastSum; return result; diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java index 08e3a90b..c4d86cf1 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java @@ -50,7 +50,8 @@ public class ObjectCodeImpl implements ObjectCode { public void set(int object, long value) { ensureSize(object); - vector[object]=value; + final long valueToPut = value == 0 ? 1 : value; + vector[object]=valueToPut; } public int getSize() { 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 e58a2502..34dba34e 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 @@ -29,11 +29,8 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { List> interpretations1, ObjectCode code1, List> interpretations2, - ObjectCode code2) { - if (code1.getSize() != code2.getSize()) { - return EquivalenceResult.DIFFERENT; - } - + ObjectCode code2) + { IntIntHashMap object2PermutationGroup = new IntIntHashMap(); List> permutationsGroups = new ArrayList<>(); @@ -69,12 +66,14 @@ public class StateEquivalenceCheckerImpl implements StateEquivalenceChecker { for (int o = 0; o < code.getSize(); o++) { if(! individuals.contains(o)){ long hash = code.get(o); - var equivalenceClass = result.get(hash); - if (equivalenceClass == null) { - equivalenceClass = new IntHashSet(); - result.put(hash, equivalenceClass); + if(hash != 0) { + var equivalenceClass = result.get(hash); + if (equivalenceClass == null) { + equivalenceClass = new IntHashSet(); + result.put(hash, equivalenceClass); + } + equivalenceClass.add(o); } - equivalenceClass.add(o); } } return result; diff --git a/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java b/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java new file mode 100644 index 00000000..8a9c0e9b --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/statecoding/EquivalenceTest.java @@ -0,0 +1,178 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +import org.junit.jupiter.api.Test; +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.tuple.Tuple; + +import static org.junit.jupiter.api.Assertions.assertEquals; + +class EquivalenceTest { + Symbol person = new Symbol<>("Person", 1, Boolean.class, false); + Symbol age = new Symbol<>("age", 1, Integer.class, null); + Symbol friend = new Symbol<>("friend", 2, Boolean.class, false); + Symbol parents = new Symbol<>("parents", 3, Boolean.class, false); + Symbol population = new Symbol<>("population", 0, Integer.class, 0); + + private ModelStore createStore() { + return ModelStore.builder() + .symbols(person, age, friend, parents, population) + .with(StateCoderAdapter.builder()) + .build(); + } + + @Test + void emptyModelCode0() { + ModelStore store = createStore(); + var stateCoder = store.getAdapter(StateCoderStoreAdapter.class); + Model model = createStore().createEmptyModel(); + Version v1 = model.commit(); + Version v2 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC, stateCoder.checkEquivalence(v1, v2)); + + var personI = model.getInterpretation(person); + var friendI = model.getInterpretation(friend); + + personI.put(Tuple.of(1), true); + personI.put(Tuple.of(2), true); + friendI.put(Tuple.of(1, 2), true); + + Version v3 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v1, v3)); + } + + @Test + void nullRelationTest() { + ModelStore store = createStore(); + var stateCoder = store.getAdapter(StateCoderStoreAdapter.class); + Model model = createStore().createEmptyModel(); + + var populationI = model.getInterpretation(population); + + Version v1 = model.commit(); + + populationI.put(Tuple.of(), 1); + Version v2 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v1, v2)); + + populationI.put(Tuple.of(), 2); + Version v3 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v2, v3)); + } + + @Test + void unaryBooleanTest() { + ModelStore store = createStore(); + var stateCoder = store.getAdapter(StateCoderStoreAdapter.class); + Model model = createStore().createEmptyModel(); + + var personI = model.getInterpretation(person); + + Version v1 = model.commit(); + + personI.put(Tuple.of(1), true); + Version v2 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v1, v2)); + + personI.put(Tuple.of(2), true); + Version v3 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v2, v3)); + + personI.put(Tuple.of(1), false); + Version v4 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC, stateCoder.checkEquivalence(v2, v4)); + } + + @Test + void unaryIntTest() { + ModelStore store = createStore(); + var stateCoder = store.getAdapter(StateCoderStoreAdapter.class); + Model model = createStore().createEmptyModel(); + + var ageI = model.getInterpretation(age); + + ageI.put(Tuple.of(1), 3); + Version v1 = model.commit(); + + ageI.put(Tuple.of(1), 4); + Version v2 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v1, v2)); + + ageI.put(Tuple.of(2), 4); + Version v3 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v2, v3)); + + ageI.put(Tuple.of(1), null); + Version v4 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC, stateCoder.checkEquivalence(v2, v4)); + } + + @Test + void binaryTest() { + ModelStore store = createStore(); + var stateCoder = store.getAdapter(StateCoderStoreAdapter.class); + Model model = createStore().createEmptyModel(); + + var friendI = model.getInterpretation(friend); + + Version v1 = model.commit(); + + friendI.put(Tuple.of(1, 2), true); + Version v2 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v1, v2)); + + friendI.put(Tuple.of(2, 1), true); + Version v3 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v2, v3)); + + friendI.put(Tuple.of(1, 2), false); + Version v4 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC, stateCoder.checkEquivalence(v2, v4)); + } + + @Test + void NaryTest() { + ModelStore store = createStore(); + var stateCoder = store.getAdapter(StateCoderStoreAdapter.class); + Model model = createStore().createEmptyModel(); + + var parentsI = model.getInterpretation(parents); + + Version v1 = model.commit(); + + parentsI.put(Tuple.of(3, 1, 2), true); + Version v2 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v1, v2)); + + parentsI.put(Tuple.of(4, 1, 2), true); + Version v3 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.DIFFERENT, stateCoder.checkEquivalence(v2, v3)); + + parentsI.put(Tuple.of(3, 1, 2), false); + Version v4 = model.commit(); + + assertEquals(StateEquivalenceChecker.EquivalenceResult.ISOMORPHIC, stateCoder.checkEquivalence(v2, v4)); + } +} diff --git a/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderUnitTest.java b/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderUnitTest.java new file mode 100644 index 00000000..d94df841 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/statecoding/StateCoderUnitTest.java @@ -0,0 +1,195 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +import org.junit.jupiter.api.Test; +import tools.refinery.store.model.Model; +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.tuple.Tuple; + +import java.util.Objects; + +import static org.junit.jupiter.api.Assertions.*; + +class StateCoderUnitTest { + Symbol person = new Symbol<>("Person", 1, Boolean.class, false); + Symbol age = new Symbol<>("age", 1, Integer.class, null); + Symbol friend = new Symbol<>("friend", 2, Boolean.class, false); + Symbol parents = new Symbol<>("parents", 3, Boolean.class, false); + Symbol population = new Symbol<>("population", 0, Integer.class, 0); + + private Model createEmptyModel() { + var store = ModelStore.builder() + .symbols(person, age, friend, parents, population) + .with(StateCoderAdapter.builder()) + .build(); + + return store.createEmptyModel(); + } + + @Test + void emptyModelCode0() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + assertEquals(0, stateCoder.calculateModelCode()); + + var personI = model.getInterpretation(person); + var friendI = model.getInterpretation(friend); + + personI.put(Tuple.of(1), true); + personI.put(Tuple.of(2), true); + friendI.put(Tuple.of(1, 2), true); + + assertNotEquals(0, stateCoder.calculateModelCode()); + } + + @Test + void emptyObjectCode0() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var personI = model.getInterpretation(person); + var friendI = model.getInterpretation(friend); + + assertEquals(0, stateCoder.calculateObjectCode().get(1)); + assertEquals(0, stateCoder.calculateObjectCode().get(17)); + + personI.put(Tuple.of(1), true); + personI.put(Tuple.of(2), true); + friendI.put(Tuple.of(1, 2), true); + + assertNotEquals(0, stateCoder.calculateObjectCode().get(1)); + assertEquals(0, stateCoder.calculateObjectCode().get(17)); + } + + @Test + void nullRelationTest() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var populationI = model.getInterpretation(population); + + final int hashOf0 = Objects.hashCode(0); + + assertEquals(hashOf0, stateCoder.calculateModelCode()); + + populationI.put(Tuple.of(), 1); + int code1 = stateCoder.calculateModelCode(); + + assertNotEquals(hashOf0, stateCoder.calculateModelCode()); + + populationI.put(Tuple.of(), 2); + int code2 = stateCoder.calculateModelCode(); + + assertNotEquals(code1, code2); + + populationI.put(Tuple.of(), 1); + assertEquals(code1, stateCoder.calculateModelCode()); + } + + @Test + void unaryBooleanTest() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var personI = model.getInterpretation(person); + + assertEquals(0, stateCoder.calculateModelCode()); + + personI.put(Tuple.of(1), true); + int code1 = stateCoder.calculateModelCode(); + + assertNotEquals(0, stateCoder.calculateModelCode()); + + personI.put(Tuple.of(2), true); + int code2 = stateCoder.calculateModelCode(); + + assertNotEquals(code1, code2); + + personI.put(Tuple.of(1), false); + assertEquals(code1, stateCoder.calculateModelCode()); + } + + @Test + void unaryIntTest() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var ageI = model.getInterpretation(age); + + assertEquals(0, stateCoder.calculateModelCode()); + + ageI.put(Tuple.of(1), 4); + int code0 = stateCoder.calculateModelCode(); + + assertNotEquals(0, code0); + + ageI.put(Tuple.of(1), 5); + int code1 = stateCoder.calculateModelCode(); + + assertNotEquals(code0, code1); + + ageI.put(Tuple.of(2), 5); + int code2 = stateCoder.calculateModelCode(); + + assertNotEquals(code1, code2); + + ageI.put(Tuple.of(1), null); + assertEquals(code1, stateCoder.calculateModelCode()); + } + + @Test + void binaryTest() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var friendI = model.getInterpretation(friend); + + assertEquals(0, stateCoder.calculateModelCode()); + + friendI.put(Tuple.of(1, 2), true); + int code1 = stateCoder.calculateModelCode(); + + assertNotEquals(0, code1); + + friendI.put(Tuple.of(2, 1), true); + int code2 = stateCoder.calculateModelCode(); + + assertNotEquals(code1, code2); + + friendI.put(Tuple.of(1, 2), false); + int code3 = stateCoder.calculateModelCode(); + + assertEquals(code1, code3); + } + + @Test + void NaryTest() { + Model model = createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + var parentsI = model.getInterpretation(parents); + + assertEquals(0, stateCoder.calculateModelCode()); + + parentsI.put(Tuple.of(3, 1, 2), true); + int code1 = stateCoder.calculateModelCode(); + + assertNotEquals(0, code1); + + parentsI.put(Tuple.of(4, 1, 2), true); + int code2 = stateCoder.calculateModelCode(); + + assertNotEquals(code1, code2); + + parentsI.put(Tuple.of(3, 1, 2), false); + int code3 = stateCoder.calculateModelCode(); + + assertEquals(code1, code3); + } +} -- cgit v1.2.3-70-g09d2 From dddea012f920f922a94157c740d99a3b5a474f6e Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 8 Aug 2023 17:52:58 +0200 Subject: Non-lazy NeighbourhoodCalculator for more accurate StateCoderBuilderImpl. --- .../internal/StateCoderBuilderImpl.java | 9 +- .../AbstractNeighbourhoodCalculator.java | 19 +-- .../CollectionNeighbourhoodCalculator.java | 131 --------------------- .../neighbourhood/LazyNeighbourhoodCalculator.java | 31 +++-- .../LazyNeighbourhoodCalculatorFactory.java | 20 ---- .../neighbourhood/NeighbourhoodCalculator.java | 112 ++++++++++++++++++ .../statecoding/neighbourhood/ObjectCodeImpl.java | 11 +- 7 files changed, 152 insertions(+), 181 deletions(-) delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java (limited to 'subprojects') 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 8268a826..05b47c52 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 @@ -10,11 +10,8 @@ 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.*; +import tools.refinery.store.statecoding.neighbourhood.NeighbourhoodCalculator; import tools.refinery.store.statecoding.stateequivalence.StateEquivalenceCheckerImpl; import tools.refinery.store.tuple.Tuple1; @@ -24,7 +21,7 @@ public class StateCoderBuilderImpl implements StateCoderBuilder { Set excluded = new HashSet<>(); IntHashSet individuals = new IntHashSet(); - StateCodeCalculatorFactory calculator = new LazyNeighbourhoodCalculatorFactory(); + StateCodeCalculatorFactory calculator = NeighbourhoodCalculator::new; StateEquivalenceChecker checker = new StateEquivalenceCheckerImpl(); @Override 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 index c3f8a586..8fcf24b1 100644 --- 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 @@ -7,7 +7,6 @@ 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; @@ -20,6 +19,8 @@ public abstract class AbstractNeighbourhoodCalculator { protected final LinkedHashMap, long[]> impactValues; protected final IntLongHashMap individualHashValues; + protected static final long PRIME = 31; + protected AbstractNeighbourhoodCalculator(List> interpretations, IntSet individuals) { this.nullImpactValues = new ArrayList<>(); this.impactValues = new LinkedHashMap<>(); @@ -45,25 +46,25 @@ public abstract class AbstractNeighbourhoodCalculator { } } - protected void initializeWithIndividuals(ObjectCodeImpl previous, LongIntHashMap hash2Amount) { + protected void initializeWithIndividuals(ObjectCodeImpl previous) { 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 = Objects.hashCode(value); - result = result * 31 + objectCodeImpl.get(tuple.get(0)); + result = result * PRIME + objectCodeImpl.get(tuple.get(0)); return result; } protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) { long result = Objects.hashCode(value); - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - result = result * 31 + objectCodeImpl.get(tuple.get(1)); + result = result * PRIME + objectCodeImpl.get(tuple.get(0)); + result = result * PRIME + objectCodeImpl.get(tuple.get(1)); if (tuple.get(0) == tuple.get(1)) { - result *= 31; + result += PRIME; + result *= PRIME; } return result; } @@ -71,7 +72,7 @@ public abstract class AbstractNeighbourhoodCalculator { protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) { long result = Objects.hashCode(value); for (int i = 0; i < tuple.getSize(); i++) { - result = result * 31 + objectCodeImpl.get(tuple.get(i)); + result = result * PRIME + objectCodeImpl.get(tuple.get(i)); } return result; } @@ -84,7 +85,7 @@ public abstract class AbstractNeighbourhoodCalculator { protected long calculateModelCode(long lastSum) { long result = 0; for (var nullImpactValue : nullImpactValues) { - result = result * 31 + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); + result = result * PRIME + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); } result += lastSum; return result; diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java deleted file mode 100644 index 058750ee..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java +++ /dev/null @@ -1,131 +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 CollectionNeighbourhoodCalculator implements StateCodeCalculator { - protected final List> nullImpactValues; - protected final LinkedHashMap, long[]> impactValues; - - public CollectionNeighbourhoodCalculator(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/neighbourhood/LazyNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java index 98a75e08..2ffbef5e 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 @@ -22,34 +22,41 @@ public class LazyNeighbourhoodCalculator extends AbstractNeighbourhoodCalculator } public StateCoderResult calculateCodes() { - ObjectCodeImpl previous = new ObjectCodeImpl(); - LongIntHashMap hash2Amount = new LongIntHashMap(); - - initializeWithIndividuals(previous, hash2Amount); + ObjectCodeImpl previousObjectCode = new ObjectCodeImpl(); + LongIntHashMap prevHash2Amount = new LongIntHashMap(); long lastSum; // All hash code is 0, except to the individuals. - int lastSize = hash2Amount.size() + 1; + int lastSize = 1; + boolean first = true; boolean grows; + int rounds = 0; do { - ObjectCodeImpl next = new ObjectCodeImpl(); - constructNextObjectCodes(previous, next, hash2Amount); + final ObjectCodeImpl nextObjectCode; + if (first) { + nextObjectCode = new ObjectCodeImpl(); + initializeWithIndividuals(nextObjectCode); + } else { + nextObjectCode = new ObjectCodeImpl(previousObjectCode); + } + constructNextObjectCodes(previousObjectCode, nextObjectCode, prevHash2Amount); LongIntHashMap nextHash2Amount = new LongIntHashMap(); - lastSum = calculateLastSum(previous, next, hash2Amount, nextHash2Amount); + lastSum = calculateLastSum(previousObjectCode, nextObjectCode, prevHash2Amount, nextHash2Amount); int nextSize = nextHash2Amount.size(); grows = nextSize > lastSize; lastSize = nextSize; + first = false; - previous = next; - hash2Amount = nextHash2Amount; - } while (grows); + previousObjectCode = nextObjectCode; + prevHash2Amount = nextHash2Amount; + } while (grows && rounds++ < 4/*&& lastSize < previousObjectCode.getSize()*/); long result = calculateModelCode(lastSum); - return new StateCoderResult((int) result, previous); + return new StateCoderResult((int) result, previousObjectCode); } private long calculateLastSum(ObjectCodeImpl previous, ObjectCodeImpl next, LongIntMap hash2Amount, 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 deleted file mode 100644 index 2e499f95..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java +++ /dev/null @@ -1,20 +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.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 new file mode 100644 index 00000000..d3b3ccae --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java @@ -0,0 +1,112 @@ +/* + * 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.map.Cursor; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.statecoding.ObjectCode; +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.List; +import java.util.Objects; + +public class NeighbourhoodCalculator extends AbstractNeighbourhoodCalculator implements StateCodeCalculator { + public NeighbourhoodCalculator(List> interpretations, IntSet individuals) { + super(interpretations, individuals); + } + + public StateCoderResult calculateCodes() { + ObjectCodeImpl previousObjectCode = new ObjectCodeImpl(); + initializeWithIndividuals(previousObjectCode); + + int rounds = 0; + do { + final ObjectCodeImpl nextObjectCode = rounds == 0 ? new ObjectCodeImpl() : + new ObjectCodeImpl(previousObjectCode.getSize()); + + constructNextObjectCodes(previousObjectCode, nextObjectCode); + previousObjectCode = nextObjectCode; + rounds++; + } while (rounds <= 7 && rounds <= previousObjectCode.getSize()); + + long result = calculateLastSum(previousObjectCode); + return new StateCoderResult((int) result, previousObjectCode); + } + + private long calculateLastSum(ObjectCode codes) { + long result = 0; + for (var nullImpactValue : nullImpactValues) { + result = result * 31 + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); + } + + for (int i = 0; i < codes.getSize(); i++) { + final long hash = codes.get(i); + result += hash*PRIME; + } + + return result; + } + + private void constructNextObjectCodes(ObjectCodeImpl previous, ObjectCodeImpl next) { + for (var impactValueEntry : this.impactValues.entrySet()) { + Interpretation interpretation = impactValueEntry.getKey(); + var cursor = interpretation.getAll(); + int arity = interpretation.getSymbol().arity(); + long[] impactValue = impactValueEntry.getValue(); + + if (arity == 1) { + while (cursor.move()) { + impactCalculation1(previous, next, impactValue, cursor); + } + } else if (arity == 2) { + while (cursor.move()) { + impactCalculation2(previous, next, impactValue, cursor); + } + } else { + while (cursor.move()) { + impactCalculationN(previous, next, impactValue, cursor); + } + } + } + } + + + private void impactCalculation1(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { + + Tuple tuple = cursor.getKey(); + int o = tuple.get(0); + Object value = cursor.getValue(); + long tupleHash = getTupleHash1(tuple, value, previous); + addHash(next, o, impactValues[0], tupleHash); + } + + private void impactCalculation2(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { + final Tuple tuple = cursor.getKey(); + final int o1 = tuple.get(0); + final int o2 = tuple.get(1); + + Object value = cursor.getValue(); + long tupleHash = getTupleHash2(tuple, value, previous); + + addHash(next, o1, impactValues[0], tupleHash); + addHash(next, o2, impactValues[1], tupleHash); + } + + private void impactCalculationN(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { + final Tuple tuple = cursor.getKey(); + + Object value = cursor.getValue(); + long tupleHash = getTupleHashN(tuple, value, previous); + + for (int i = 0; i < tuple.getSize(); i++) { + addHash(next, tuple.get(i), impactValues[i], tupleHash); + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java index c4d86cf1..0d629176 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java @@ -18,9 +18,14 @@ public class ObjectCodeImpl implements ObjectCode { size = 0; } - public ObjectCodeImpl(ObjectCodeImpl sameSize) { - this.vector = new long[sameSize.size]; - this.size = sameSize.size; + public ObjectCodeImpl(int size) { + this.vector = new long[size]; + this.size = size; + } + + public ObjectCodeImpl(ObjectCodeImpl copy) { + this.vector = Arrays.copyOf(copy.vector,copy.size); + this.size = copy.size; } public void ensureSize(int object) { -- cgit v1.2.3-70-g09d2 From 52c8e89faa49988bc47a15256ed818f3b78bb56b Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 8 Aug 2023 19:07:27 +0200 Subject: Test cases for Equivalence accuracy measurements --- .../store/statecoding/ExperimentalSetupTest.java | 189 +++++++++++++++------ 1 file changed, 140 insertions(+), 49 deletions(-) (limited to 'subprojects') diff --git a/subprojects/store/src/test/java/tools/refinery/store/statecoding/ExperimentalSetupTest.java b/subprojects/store/src/test/java/tools/refinery/store/statecoding/ExperimentalSetupTest.java index 87b1623c..25b5dca1 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/statecoding/ExperimentalSetupTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/statecoding/ExperimentalSetupTest.java @@ -5,16 +5,52 @@ */ package tools.refinery.store.statecoding; +import org.eclipse.collections.impl.map.mutable.primitive.IntObjectHashMap; +import org.junit.jupiter.api.Tag; import org.junit.jupiter.api.Test; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.ValueSource; 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.tuple.Tuple; -import java.util.*; +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertTrue; + class ExperimentalSetupTest { - public static void generate(int size) { + static class ExperimentalSetupResult { + int versions = 0; + int different = 0; + int isomorphic = 0; + int unknown = 0; + + double failureRatio() { + return (different + 0.0) / versions; + } + + @Override + public String toString() { + return "ExperimentalSetupResult{" + + "versions=" + versions + + ", different=" + different + + ", isomorphic=" + isomorphic + + ", unknown=" + unknown + + ", ratio= " + failureRatio() + + '}'; + } + } + + static int MAX = 100000; + + public static ExperimentalSetupResult generate(int size, boolean permuteTypes) { Symbol person = new Symbol<>("Person", 1, Boolean.class, false); Symbol friend = new Symbol<>("friend", 2, Boolean.class, false); @@ -25,13 +61,13 @@ class ExperimentalSetupTest { .build(); Set versions = new HashSet<>(); - Map> codes = new HashMap<>(); + IntObjectHashMap> codes = new IntObjectHashMap<>(); var empty = store.createEmptyModel(); - var pI = empty.getInterpretation(person); - - for (int i = 0; i < size; i++) { - pI.put(Tuple.of(i), true); + if (!permuteTypes) { + for (int i = 0; i < size; i++) { + empty.getInterpretation(person).put(Tuple.of(i), true); + } } var emptyVersion = empty.commit(); @@ -42,12 +78,27 @@ class ExperimentalSetupTest { codes.put(emptyCode, emptyList); var storeAdapter = store.getAdapter(StateCoderStoreAdapter.class); + var result = new ExperimentalSetupResult(); - int dif = 0; - int iso = 0; - int unk = 0; + int steps = 0; - //int step = 0 + if (permuteTypes) { + for (int i = 0; i < size; i++) { + var previousVersions = new HashSet<>(versions); + for (var version : previousVersions) { + var model = store.createModelForState(version); + model.getInterpretation(person).put(Tuple.of(i), true); + + saveAsNewVersion(versions, codes, storeAdapter, result, model); + + logProgress(steps++); + if (steps > MAX) { + result.versions = versions.size(); + return result; + } + } + } + } for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { @@ -57,51 +108,91 @@ class ExperimentalSetupTest { var model = store.createModelForState(version); model.getInterpretation(friend).put(Tuple.of(i, j), true); - Version version1 = model.commit(); - var stateCode = model.getAdapter(StateCoderAdapter.class).calculateStateCode(); - int code = stateCode.modelCode(); - //System.out.println(step+++" ->" +code); - if (codes.containsKey(code)) { - Version similar = codes.get(code).get(0); - - var outcome = storeAdapter.checkEquivalence(version1, similar); - if (outcome == StateEquivalenceChecker.EquivalenceResult.DIFFERENT) { - System.out.println(); - var c = model.getInterpretation(friend).getAll(); - while (c.move()) { - System.out.println(c.getKey().toString()); - } - System.out.println("vs"); - var c2 = store.createModelForState(similar).getInterpretation(friend).getAll(); - while (c2.move()) { - System.out.println(c2.getKey().toString()); - } - - dif++; - } else if (outcome == StateEquivalenceChecker.EquivalenceResult.UNKNOWN) { - unk++; - } else { - iso++; - } - } else { - versions.add(version1); - - List newList = new ArrayList<>(); - newList.add(version1); - codes.put(code, newList); + saveAsNewVersion(versions, codes, storeAdapter, result, model); + + logProgress(steps++); + if (steps > MAX) { + result.versions = versions.size(); + return result; } } } } - System.out.printf("v=%d i=%d d=%d u=%d\n", versions.size(), iso, dif, unk); + result.versions = versions.size(); + return result; } - @Test - void runTests() { - for (int i = 0; i < 5; i++) { - System.out.println("size = " + i); - generate(i); + private static void saveAsNewVersion(Set versions, IntObjectHashMap> codes, + StateCoderStoreAdapter storeAdapter, ExperimentalSetupResult result, Model model) { + Version version1 = model.commit(); + + var stateCode = model.getAdapter(StateCoderAdapter.class).calculateStateCode(); + int code = stateCode.modelCode(); + if (codes.containsKey(code)) { + Version similar = codes.get(code).get(0); + + var outcome = storeAdapter.checkEquivalence(version1, similar); + if (outcome == StateEquivalenceChecker.EquivalenceResult.DIFFERENT) { + result.different++; + } else if (outcome == StateEquivalenceChecker.EquivalenceResult.UNKNOWN) { + result.unknown++; + } else { + result.isomorphic++; + } + } else { + versions.add(version1); + + List newList = new ArrayList<>(); + newList.add(version1); + codes.put(code, newList); + } + } + + private static void logProgress(int steps) { + if (steps % 10000 == 0) { + System.out.println("Steps: " + steps + " / " + MAX); } } + + static final double limit = 0.01; + + @Test + void test0() { + assertEquals(1, generate(0, true).versions); + } + + @ParameterizedTest + @ValueSource(ints = {1, 2, 3, 4}) + void testForSmallUntypedModels(int size) { + var res = generate(size, false); + System.out.println(res); + assertTrue(res.failureRatio() < limit); + } + + @ParameterizedTest + @ValueSource(ints = {1, 2, 3}) + void testForSmallTypedModels(int size) { + var res = generate(size, true); + System.out.println(res); + assertTrue(res.failureRatio() < limit); + } + + @Test + @Tag("fuzz") + @Tag("slow") + void testForLargeTypedModels() { + var res = generate(10, true); + System.out.println(res); + assertTrue(res.failureRatio() < limit); + } + + @Test + @Tag("fuzz") + @Tag("slow") + void testForLargeUntypedModels() { + var res = generate(10, false); + System.out.println(res); + assertTrue(res.failureRatio() < limit); + } } -- cgit v1.2.3-70-g09d2 From db7a2892def64f0d155d4fc9525be11a1833f8f8 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 8 Aug 2023 19:18:45 +0200 Subject: Added two build tests for custom coding and equivalence checking algorithms. --- .../store/statecoding/StateCoderBuildTest.java | 74 ++++++++++++++++++---- 1 file changed, 60 insertions(+), 14 deletions(-) (limited to 'subprojects') 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 a4e953ea..0b738005 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 @@ -58,14 +58,14 @@ class StateCoderBuildTest { int code = stateCoder.calculateStateCode().modelCode(); - ageI.put(Tuple.of(1),3); - assertEquals(code,stateCoder.calculateStateCode().modelCode()); + ageI.put(Tuple.of(1), 3); + assertEquals(code, stateCoder.calculateStateCode().modelCode()); - ageI.put(Tuple.of(1),null); - assertEquals(code,stateCoder.calculateStateCode().modelCode()); + ageI.put(Tuple.of(1), null); + assertEquals(code, stateCoder.calculateStateCode().modelCode()); - personI.put(Tuple.of(2),false); - assertEquals(code,stateCoder.calculateStateCode().modelCode()); + personI.put(Tuple.of(2), false); + assertEquals(code, stateCoder.calculateStateCode().modelCode()); } @Test @@ -80,14 +80,14 @@ class StateCoderBuildTest { var friendI = model.getInterpretation(friend); - friendI.put(Tuple.of(1,2),true); + 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); + friendI.put(Tuple.of(1, 2), false); + friendI.put(Tuple.of(2, 1), true); int code2 = stateCoder.calculateModelCode(); - assertEquals(code1,code2); + assertEquals(code1, code2); } @Test @@ -103,16 +103,62 @@ class StateCoderBuildTest { var friendI = model.getInterpretation(friend); - friendI.put(Tuple.of(1,2),true); + 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); + friendI.put(Tuple.of(1, 2), false); + friendI.put(Tuple.of(2, 1), true); int code2 = stateCoder.calculateModelCode(); - assertNotEquals(code1,code2); + assertNotEquals(code1, code2); } + @Test + void customStateCoderTest() { + final boolean[] called = new boolean[]{false}; + StateCodeCalculator mock = () -> { + called[0] = true; + return null; + }; + + var store = ModelStore.builder() + .symbols(friend) + .with(StateCoderAdapter.builder() + .stateCodeCalculatorFactory((interpretations, individuals) -> mock)) + .build(); + + var model = store.createEmptyModel(); + var stateCoder = model.getAdapter(StateCoderAdapter.class); + + stateCoder.calculateStateCode(); + + assertTrue(called[0]); + } + + @Test + void customEquivalenceCheckerTest() { + final boolean[] called = new boolean[]{false}; + StateEquivalenceChecker mock = (p1, p2, p3, p4, p5) -> { + called[0] = true; + return StateEquivalenceChecker.EquivalenceResult.UNKNOWN; + }; + + var store = ModelStore.builder() + .symbols(friend) + .with(StateCoderAdapter.builder() + .stateEquivalenceChecker(mock)) + .build(); + + var model = store.createEmptyModel(); + var v1 = model.commit(); + var v2 = model.commit(); + + store.getAdapter(StateCoderStoreAdapter.class).checkEquivalence(v1, v2); + + assertTrue(called[0]); + } + + 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 From 7fb2e47c13f798511b0fa6b47c34f53d42c00f34 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 8 Aug 2023 19:37:54 +0200 Subject: ObjectCodeImpl.effectiveSize introduced to correctly handle models with different indices. --- .../neighbourhood/NeighbourhoodCalculator.java | 2 +- .../statecoding/neighbourhood/ObjectCodeImpl.java | 29 ++++++++++++++-------- 2 files changed, 20 insertions(+), 11 deletions(-) (limited to 'subprojects') 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 index d3b3ccae..5b3e5ea3 100644 --- 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 @@ -34,7 +34,7 @@ public class NeighbourhoodCalculator extends AbstractNeighbourhoodCalculator imp constructNextObjectCodes(previousObjectCode, nextObjectCode); previousObjectCode = nextObjectCode; rounds++; - } while (rounds <= 7 && rounds <= previousObjectCode.getSize()); + } while (rounds <= 7 && rounds <= previousObjectCode.getEffectiveSize()); long result = calculateLastSum(previousObjectCode); return new StateCoderResult((int) result, previousObjectCode); diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java index 0d629176..0cd7ff58 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java @@ -12,31 +12,35 @@ import java.util.Arrays; public class ObjectCodeImpl implements ObjectCode { private long[] vector; private int size; + private int effectiveSize; public ObjectCodeImpl() { vector = new long[10]; size = 0; + effectiveSize = 0; } public ObjectCodeImpl(int size) { this.vector = new long[size]; this.size = size; + effectiveSize = 0; } public ObjectCodeImpl(ObjectCodeImpl copy) { - this.vector = Arrays.copyOf(copy.vector,copy.size); + this.vector = Arrays.copyOf(copy.vector, copy.size); this.size = copy.size; + effectiveSize = copy.effectiveSize; } public void ensureSize(int object) { - if(object >= size) { - size = object+1; + if (object >= size) { + size = object + 1; } - if(object >= vector.length) { - int newLength = vector.length*2; - while(object >= newLength) { - newLength*=2; + if (object >= vector.length) { + int newLength = vector.length * 2; + while (object >= newLength) { + newLength *= 2; } long[] newVector = new long[newLength]; @@ -46,7 +50,7 @@ public class ObjectCodeImpl implements ObjectCode { } public long get(int object) { - if(object < vector.length) { + if (object < vector.length) { return vector[object]; } else { return 0; @@ -56,17 +60,22 @@ public class ObjectCodeImpl implements ObjectCode { public void set(int object, long value) { ensureSize(object); final long valueToPut = value == 0 ? 1 : value; - vector[object]=valueToPut; + if (vector[object] == 0) effectiveSize++; + vector[object] = valueToPut; } public int getSize() { return this.size; } + public int getEffectiveSize() { + return this.effectiveSize; + } + @Override public String toString() { return "ObjectCodeImpl{" + - "vector=" + Arrays.toString(Arrays.copyOf(vector,this.size)) + + "vector=" + Arrays.toString(Arrays.copyOf(vector, this.size)) + '}'; } } -- cgit v1.2.3-70-g09d2