bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java

   1 package org.simantics.db.common.utils;
   2
   3 import java.util.Collection;
   4 import java.util.Collections;
   5 import java.util.HashSet;
   6 import java.util.Iterator;
   7
   8 import org.simantics.db.ReadGraph;
   9 import org.simantics.db.Resource;
  10 import org.simantics.db.Statement;
  11 import org.simantics.db.exception.DatabaseException;
  12 import org.simantics.layer0.Layer0;
  13
  14 import gnu.trove.map.hash.TObjectIntHashMap;
  15 import gnu.trove.set.hash.THashSet;
  16
  17 /**
  18  * <p>A utility to finds the nearest owner of a real or imaginary resource.</p>
  19  *
  20  * <p>The nearest owner
  21  * is found by first finding a path (pilot path) from the input to a root resource and then
  22  * trying to find other paths to the resources in the pilot path such that the other
  23  * paths don't visit other resources of the pilot path. The farthest resource so found
  24  * is then the nearest common owner. See the methods for the exact specification.</p>
  25  *
  26  * <p>The time and space complexity of the algorithm is O(m),
  27  * where m is the number of resources reachable by direct-owners relation from the input.</p>
  28  *
  29  * @see {@link #getNearestOwner(ReadGraph, Resource)}
  30  * @see {@link #getNearestOwner(ReadGraph, Collection)}</p>
  31  *
  32  */
  33 public class NearestOwnerFinder {
  34     private static final int FIRST_DISTANCE = 1;
  35     private static final int UNVISITED = 0;
  36     private static final int NOT_INTERESTING_ANYMORE = -1;
  37
  38     private final ReadGraph graph;
  39     private final Layer0 L0;
  40
  41     private final TObjectIntHashMap<Resource> resourceStatus = new TObjectIntHashMap<>();
  42
  43     private int nearestOwnerDistance; // = 0
  44     private Resource nearestOwner; // = null
  45
  46     private NearestOwnerFinder(ReadGraph graph, Layer0 L0) {
  47         this.graph = graph;
  48         this.L0 = L0;
  49     }
  50
  51     /**
  52      * Iterates the owners of the input resource. It first
  53      * tries to find the pilot path and when it has been found,
  54      * it browses other owners with {@link #browseNonpilot}.
  55      */
  56     private void browseOwnersOfInput(Collection<Resource> owners) throws DatabaseException {
  57         Iterator<Resource> it = owners.iterator();
  58         while(it.hasNext()) {
  59             Resource owner = it.next();
  60             if(browsePilot(owner, FIRST_DISTANCE)) {
  61                 // Because we found a path to root, {@code owner}
  62                 // becomes our first candidate for nearestOwner.
  63                 nearestOwner = owner;
  64                 nearestOwnerDistance = FIRST_DISTANCE;
  65
  66                 // Tries to find other paths to the resource in the pilot path.
  67                 while(it.hasNext())
  68                     browseNonpilot(it.next());
  69                 return;
  70             }
  71         }
  72     }
  73
  74     /**
  75      * Tries to find a first path (=pilot path) to a root with DFS.
  76      */
  77     private boolean browsePilot(Resource resource, int distance) throws DatabaseException {
  78         if(resourceStatus.putIfAbsent(resource, distance) != UNVISITED)
  79             // We recursed back to the current path or encountered previously failed path.
  80             return false;
  81
  82         Collection<Resource> owners = getDirectOwners(graph, L0, resource);
  83         if(owners.isEmpty())
  84             // We found a root
  85             return true;
  86
  87         for(Resource owner : owners)
  88             if(browsePilot(owner, distance+1)) {
  89                 // We found a path to a root
  90                 return true;
  91             }
  92
  93         // Failed to find a path to a root
  94         resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
  95         return false;
  96     }
  97
  98     /**
  99      * Tries to find some path to a resource on a pilot path using DFS.
 100      * Marks all visited resource by {@code NOT_INTERESTING_ANYMORE}
 101      * to prevent visiting the same resources more than once.
 102      */
 103     private void browseNonpilot(Resource resource) throws DatabaseException {
 104         // In the next statement, we may overwrite also information about resource being on pilot path,
 105         // but that is ok, because we don't care resources that are nearer than nearestOwnerDistance.
 106         int status = resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
 107         if(status == UNVISITED) {
 108             Collection<Resource> owners = getDirectOwners(graph, L0, resource);
 109             if(owners.isEmpty()) {
 110                 // This is a root that differs from the root at the end of the pilot path.
 111                 // Therefore there cannot be a nearest owner.
 112                 nearestOwnerDistance = Integer.MAX_VALUE;
 113                 nearestOwner = null;
 114                 return;
 115             }
 116             for(Resource owner : owners)
 117                 browseNonpilot(owner);
 118         }
 119         else if(status > nearestOwnerDistance) {
 120             nearestOwnerDistance = status;
 121             nearestOwner = resource;
 122         }
 123     }
 124
 125     private static Collection<Resource> getDirectOwners(ReadGraph graph, Layer0 L0, Resource resource) throws DatabaseException {
 126         Collection<Resource> owners = graph.getObjects(resource, L0.IsOwnedBy);
 127         if(owners.isEmpty()) {
 128             if(resource.equals(graph.getRootLibrary()))
 129                 return Collections.emptyList();
 130
 131             owners = new THashSet<Resource>();
 132
 133             // If there are no owners, collect resources referring to this resource by IsRelatedTo
 134             for(Statement statement : graph.getStatements(resource, L0.IsWeaklyRelatedTo)) {
 135                 Resource inverse = graph.getPossibleInverse(statement.getPredicate());
 136                 if(inverse != null) {
 137                     if(graph.isSubrelationOf(inverse, L0.IsRelatedTo)) {
 138                         // Filter away tags
 139                         if(resource.equals(statement.getObject()))
 140                             continue;
 141                         owners.add(statement.getObject());
 142                     }
 143                 }
 144             }
 145         }
 146         else if(owners.size() > 1) {
 147             // TODO: getObjects returns duplicate entries (https://www.simantics.org/redmine/issues/4885) and therefore direct is Set<Resource>.
 148             // Fix getObjects to not return duplicate entries
 149             owners = new HashSet<Resource>(owners);
 150         }
 151
 152         return owners;
 153     }
 154
 155     /**
 156      * <p>Finds the nearest owner of a resource. Nearest owner is the
 157      * <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">immediate dominator</a>
 158      * of the resource in a graph defined in the following way:
 159      * Each IsComposedOf statement is an edge of the graph.
 160      * Additionally an IsRelatedTo statement in an edge of graph if
 161      * no IsComposedOf statement points to its object.</p>
 162      *
 163      * <p>The root of the graph is any resource without owners or the root resource
 164      * of the database. If the search encounters two distinct roots, there
 165      * cannot be a nearest owner.</p>
 166      *
 167      * @return The nearest owner or {@code null} if no roots or more than one roots are found.
 168      */
 169     public static Resource getNearestOwner(ReadGraph graph, Resource resource) throws DatabaseException {
 170         // Handle cases of one or zero direct owners
 171         Layer0 L0 = Layer0.getInstance(graph);
 172         Collection<Resource> owners = getDirectOwners(graph, L0, resource);
 173         if(owners.size() == 1)
 174             return owners.iterator().next();
 175         if(owners.isEmpty())
 176             return null;
 177
 178         // There are two or more direct owners
 179         NearestOwnerFinder finder = new NearestOwnerFinder(graph, L0);
 180         finder.resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
 181         finder.browseOwnersOfInput(owners);
 182         return finder.nearestOwner;
 183     }
 184
 185     /**
 186      * <p>Finds the nearest owner of a real or imaginary resource whose direct owners are known. This works in the same
 187      * way as the method for one resource {@link #getNearestOwner(ReadGraph, Resource)}
 188      * but we add one extra node to the graph that has the input resources as direct owners and
 189      * find the immediate dominator of that extra node.</p>
 190      *
 191      * <p>Note that this method may return one of the input resources if it is dominator of all other
 192      * resources in the collection. Returns {@code null} if the input collection is empty.</p>
 193      */
 194     public static Resource getNearestOwnerFromDirectOwners(ReadGraph graph, Collection<Resource> owners) throws DatabaseException {
 195         // Handle the cases of one or zero direct owners
 196         if(owners.size() == 1)
 197             return owners.iterator().next();
 198         if(owners.isEmpty())
 199             return null;
 200
 201         // There are two or more direct owners
 202         Layer0 L0 = Layer0.getInstance(graph);
 203         NearestOwnerFinder finder = new NearestOwnerFinder(graph, L0);
 204         finder.browseOwnersOfInput(owners);
 205         return finder.nearestOwner;
 206     }
 207 }