A utility class for recursive search in cyclic graph 97/1697/3
authorHannu Niemistö <hannu.niemisto@semantum.fi>
Tue, 10 Apr 2018 06:57:49 +0000 (09:57 +0300)
committerHannu Niemistö <hannu.niemisto@semantum.fi>
Tue, 10 Apr 2018 10:03:21 +0000 (13:03 +0300)
refs #7859

Change-Id: Idba80d0a6a42ab06fa774da1933ffd1d636085f1

bundles/org.simantics.db.common/META-INF/MANIFEST.MF
bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/CachedRecursiveSearch.java [new file with mode: 0644]
bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindParentsWithType.java [new file with mode: 0644]
bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java [new file with mode: 0644]

index 5ba6379d6a15a07f93d9f313320178e73acb6c8f..f0ac2886df4121bcd59921b225dd35eab588285c 100644 (file)
@@ -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 (file)
index 0000000..006113d
--- /dev/null
@@ -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;
+
+/**
+ * <p>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.
+ * 
+ * <p>The function {@link #combineNotNull} is assumed to be a semilattice
+ * operation, i.e., the following laws must hold:
+ * <pre>
+ *   Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
+ *   Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
+ *   Idempotency:   combineNotNull(a, a) = a
+ * </pre>
+ * 
+ * <p>If the graph of the function {link children} is acyclic,
+ * the function {@link get} works equally to the following
+ * simpler implementation: 
+ * <pre>
+ *  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;
+ *  }
+ * </pre>
+ */
+public abstract class CachedRecursiveSearch<T> {
+    /**
+     * 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<Resource> 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:
+     * <pre>
+     *   Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
+     *   Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
+     *   Idempotency:   combineNotNull(a, a) = a
+     * </pre>
+     */
+    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<Resource, T> resultMap = new THashMap<Resource, T>(); 
+    
+    /**
+     * <p>Returns the combination of all source values reachable from the given resource.
+     * Returns {@code null}, if no source value is reachable.
+     * 
+     * <p>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<Resource> indexMap =
+            new TObjectIntHashMap<Resource>(Constants.DEFAULT_CAPACITY, Constants.DEFAULT_LOAD_FACTOR, NO_VALUE); 
+    
+    private int curIndex;
+    private final ArrayList<Resource> stack = new ArrayList<Resource>();
+    
+    /**
+     * This field is used to return the result from the {@code calc}
+     */
+    private T previousResult;
+    
+    /**
+     * <p>Calculates the result for the given resource and stores it into {@code resultMap}.
+     * 
+     * <p>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 (file)
index 0000000..afdf766
--- /dev/null
@@ -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<Resource> children(Resource resource) throws DatabaseException {
+        Resource parent = graph.getPossibleObject(resource, L0.PartOf);
+        if(parent != null)
+            return Collections.singletonList(parent);
+        
+        ArrayList<Resource> result = new ArrayList<Resource>(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<Resource> findParentsWithType(ReadGraph graph, Resource r, Resource type) throws DatabaseException {
+        Set<Resource> set = new FindParentsWithType(graph, type).get(r);
+        if(set == null)
+            return Collections.emptyList();
+        else
+            return new ArrayList<Resource>(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 (file)
index 0000000..1f6b657
--- /dev/null
@@ -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<Set<Resource>> {
+    protected abstract boolean isRoot(Resource resource) throws DatabaseException;
+    
+    protected Set<Resource> getSourceValue(Resource resource) throws org.simantics.db.exception.DatabaseException {
+        if(isRoot(resource))
+            return Collections.singleton(resource);
+        else
+            return null;
+    }
+    
+    private static int sharedElements(Set<Resource> a, Set<Resource> b) {
+        int count = 0;
+        for(Resource r : a)
+            if(b.contains(r))
+                ++count;
+        return count;
+    }
+    
+    @Override
+    protected Set<Resource> combineNotNull(Set<Resource> a, Set<Resource> 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<Resource> combined = new THashSet<Resource>(aSize + bSize - shared);
+        combined.addAll(a);
+        combined.addAll(b);
+        return combined;
+    }
+}