From: Hannu Niemistö Date: Tue, 10 Apr 2018 06:57:49 +0000 (+0300) Subject: A utility class for recursive search in cyclic graph X-Git-Tag: v1.43.0~136^2~502 X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=commitdiff_plain;h=64047d36275405b5bcae7a85e003fd4845ab80e3 A utility class for recursive search in cyclic graph refs #7859 Change-Id: Idba80d0a6a42ab06fa774da1933ffd1d636085f1 --- diff --git a/bundles/org.simantics.db.common/META-INF/MANIFEST.MF b/bundles/org.simantics.db.common/META-INF/MANIFEST.MF index 5ba6379d6..f0ac2886d 100644 --- a/bundles/org.simantics.db.common/META-INF/MANIFEST.MF +++ b/bundles/org.simantics.db.common/META-INF/MANIFEST.MF @@ -32,6 +32,7 @@ Export-Package: org.simantics.db.common, org.simantics.db.common.procedure.wrapper, org.simantics.db.common.processor, org.simantics.db.common.provider, + org.simantics.db.common.recursive, org.simantics.db.common.request, org.simantics.db.common.service, org.simantics.db.common.session, diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/CachedRecursiveSearch.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/CachedRecursiveSearch.java new file mode 100644 index 000000000..006113d42 --- /dev/null +++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/CachedRecursiveSearch.java @@ -0,0 +1,180 @@ +package org.simantics.db.common.recursive; + +import java.util.ArrayList; +import java.util.Collection; + +import org.simantics.db.Resource; +import org.simantics.db.exception.DatabaseException; + +import gnu.trove.impl.Constants; +import gnu.trove.map.hash.THashMap; +import gnu.trove.map.hash.TObjectIntHashMap; + +/** + *

A utility class that calculates the combination of all source values + * given by {@link getSourceValue} + * reachable from a given resource by {@link #children} function and caches the results. + * + *

The function {@link #combineNotNull} is assumed to be a semilattice + * operation, i.e., the following laws must hold: + * 

+ *   Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
+ *   Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
+ *   Idempotency:   combineNotNull(a, a) = a
+ *
+ * + *

If the graph of the function {link children} is acyclic, + * the function {@link get} works equally to the following + * simpler implementation: + * 

+ *  public T get(Resource resource) throws DatabaseException {
+ *      if(resultMap.contains(resource))
+ *          return resultMap.get(resource);
+ *  
+ *      T result = getSourceValue(resource);
+ *      if(result == null)
+ *          for(Resource child : children(resource))
+ *              result = combine(result, get(child));
+ *      resultMap.put(resource, result);
+ *      return result;
+ *  }
+ *
+ */ +public abstract class CachedRecursiveSearch { + /** + * Returns the source value associated with the given resource or {@code null}, + * if the resource does not have a source value. + */ + protected abstract T getSourceValue(Resource resource) throws DatabaseException; + + /** + * Returns the children of the given resource. + */ + protected abstract Collection children(Resource parent) throws DatabaseException; + + /** + * Combines the given source values. The function may assume that the values + * are not {@code null}. The function must satisfy the following laws: + * 
+     *   Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
+     *   Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
+     *   Idempotency:   combineNotNull(a, a) = a
+     *
+ */ + protected abstract T combineNotNull(T a, T b) throws DatabaseException; + + /** + * Combines the values and also checks if either of them is null or + * if the values are equal. + */ + protected T combine(T a, T b) throws DatabaseException { + if(a == null) + return b; + else if(b == null || a == b) + return a; + else + return combineNotNull(a, b); + } + + /** + * Contains the cached results + */ + private final THashMap resultMap = new THashMap(); + + /** + *

Returns the combination of all source values reachable from the given resource. + * Returns {@code null}, if no source value is reachable. + * + *

The method is not thread safe. + */ + public T get(Resource resource) throws DatabaseException { + if(resultMap.contains(resource)) + return resultMap.get(resource); + else { + curIndex = 0; + calc(resource); + return previousResult; + } + } + + private static final int NO_VALUE = -1; + private final TObjectIntHashMap indexMap = + new TObjectIntHashMap(Constants.DEFAULT_CAPACITY, Constants.DEFAULT_LOAD_FACTOR, NO_VALUE); + + private int curIndex; + private final ArrayList stack = new ArrayList(); + + /** + * This field is used to return the result from the {@code calc} + */ + private T previousResult; + + /** + *

Calculates the result for the given resource and stores it into {@code resultMap}. + * + *

The function is implemented by depth-first search where each node gets increasing + * index number. During the calculation of the result for the resource, the index + * is stored into {@code indexMap}. This information is used to detect, if the recursive + * search has encountered a resource whose calculation has not yet been finished. In this case, + * the resource must be a part of a strongly connected component of the graph of + * {@code children}. The function returns the lowest index of unfinished calculation + * it encountered. + */ + private int calc(Resource resource) throws DatabaseException { + // Check first if the resource has a source value + T result = getSourceValue(resource); + if(result != null) { + resultMap.put(resource, result); + previousResult = result; + return NO_VALUE; + } + + // Choose an index and put it into indexMpa + int index = curIndex++; + indexMap.put(resource, index); + stack.add(resource); + + // Variable lowindex maintains the lowest index + // reachable from this resource. If it is smaller than + // index, the resource is part of a bigger strongly connected + // component. + int lowindex = index; + + for(Resource child : children(resource)) { + if(resultMap.contains(child)) { + // The result for the child has already been calculated + result = combine(result, resultMap.get(child)); + } + else { + int childIndex = indexMap.get(child); + if(childIndex == NO_VALUE) { + childIndex = calc(child); + result = combine(result, previousResult); + if(childIndex == NO_VALUE) + continue; + } + lowindex = Math.min(lowindex, childIndex); + } + } + + if(lowindex == index) { + // Remove the resources of the strongly connected component from the stack and assign + // the result to all these resources. + Resource r; + do { + r = stack.remove(stack.size()-1); + indexMap.remove(r); + resultMap.put(r, result); + } while(r != resource); + previousResult = result; + return NO_VALUE; + } + else { + // This resource is a part of a bigger strongly connected component. + // Therefore the current result is still partial and will be + // combined with the other results in this component. + previousResult = result; + return lowindex; + } + } +} diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindParentsWithType.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindParentsWithType.java new file mode 100644 index 000000000..afdf7660b --- /dev/null +++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindParentsWithType.java @@ -0,0 +1,59 @@ +package org.simantics.db.common.recursive; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.Set; + +import org.simantics.db.ReadGraph; +import org.simantics.db.Resource; +import org.simantics.db.Statement; +import org.simantics.db.exception.DatabaseException; +import org.simantics.layer0.Layer0; + +public class FindParentsWithType extends FindRoots { + private final ReadGraph graph; + private final Resource rootType; + private final Layer0 L0; + + public FindParentsWithType(ReadGraph graph, Resource rootType) { + this.graph = graph; + this.rootType = rootType; + this.L0 = Layer0.getInstance(graph); + } + + @Override + protected boolean isRoot(Resource resource) throws DatabaseException { + return graph.isInstanceOf(resource, rootType); + } + + @Override + protected Collection children(Resource resource) throws DatabaseException { + Resource parent = graph.getPossibleObject(resource, L0.PartOf); + if(parent != null) + return Collections.singletonList(parent); + + ArrayList result = new ArrayList(4); + for(Statement s : graph.getStatements(resource, L0.IsWeaklyRelatedTo)) { + if(!s.getSubject().equals(resource)) + continue; + Resource inverse = graph.getPossibleInverse(s.getPredicate()); + if(inverse != null && graph.isSubrelationOf(inverse, L0.IsRelatedTo)) + result.add(s.getObject()); + } + return result; + } + + /** + * Makes a query for just one resource. If you want to make multiple queries with the same type, + * instantiate this class and call the {@code get} method. + */ + public static List findParentsWithType(ReadGraph graph, Resource r, Resource type) throws DatabaseException { + Set set = new FindParentsWithType(graph, type).get(r); + if(set == null) + return Collections.emptyList(); + else + return new ArrayList(set); + } +} diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java new file mode 100644 index 000000000..1f6b65763 --- /dev/null +++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java @@ -0,0 +1,55 @@ +package org.simantics.db.common.recursive; + +import java.util.Collections; +import java.util.Set; + +import org.simantics.db.Resource; +import org.simantics.db.exception.DatabaseException; + +import gnu.trove.set.hash.THashSet; + +/** + * Finds all roots reachable by {@code children} function + */ +public abstract class FindRoots extends CachedRecursiveSearch> { + protected abstract boolean isRoot(Resource resource) throws DatabaseException; + + protected Set getSourceValue(Resource resource) throws org.simantics.db.exception.DatabaseException { + if(isRoot(resource)) + return Collections.singleton(resource); + else + return null; + } + + private static int sharedElements(Set a, Set b) { + int count = 0; + for(Resource r : a) + if(b.contains(r)) + ++count; + return count; + } + + @Override + protected Set combineNotNull(Set a, Set b) throws DatabaseException { + int aSize = a.size(); + int bSize = b.size(); + + int shared; + if(aSize <= bSize) { + shared = sharedElements(a, b); + if(aSize == shared) + return b; + } + else { + shared = sharedElements(b, a); + if(bSize == shared) + return a; + } + + // Both set contain elements not in the other set + THashSet combined = new THashSet(aSize + bSize - shared); + combined.addAll(a); + combined.addAll(b); + return combined; + } +}