1 package org.simantics.db.common.utils;
3 import java.util.Collection;
4 import java.util.Collections;
5 import java.util.HashSet;
6 import java.util.Iterator;
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;
14 import gnu.trove.map.hash.TObjectIntHashMap;
15 import gnu.trove.set.hash.THashSet;
18 * <p>A utility to finds the nearest owner of a real or imaginary resource.</p>
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>
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>
29 * @see {@link #getNearestOwner(ReadGraph, Resource)}
30 * @see {@link #getNearestOwner(ReadGraph, Collection)}</p>
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;
38 private final ReadGraph graph;
39 private final Layer0 L0;
41 private final TObjectIntHashMap<Resource> resourceStatus = new TObjectIntHashMap<>();
43 private int nearestOwnerDistance; // = 0
44 private Resource nearestOwner; // = null
46 private NearestOwnerFinder(ReadGraph graph, Layer0 L0) {
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}.
56 private void browseOwnersOfInput(Collection<Resource> owners) throws DatabaseException {
57 Iterator<Resource> it = owners.iterator();
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.
64 nearestOwnerDistance = FIRST_DISTANCE;
66 // Tries to find other paths to the resource in the pilot path.
68 browseNonpilot(it.next());
75 * Tries to find a first path (=pilot path) to a root with DFS.
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.
82 Collection<Resource> owners = getDirectOwners(graph, L0, resource);
87 for(Resource owner : owners)
88 if(browsePilot(owner, distance+1)) {
89 // We found a path to a root
93 // Failed to find a path to a root
94 resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
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.
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;
116 for(Resource owner : owners)
117 browseNonpilot(owner);
119 else if(status > nearestOwnerDistance) {
120 nearestOwnerDistance = status;
121 nearestOwner = resource;
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();
131 owners = new THashSet<Resource>();
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)) {
139 if(resource.equals(statement.getObject()))
141 owners.add(statement.getObject());
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);
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>
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>
167 * @return The nearest owner or {@code null} if no roots or more than one roots are found.
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();
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;
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>
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>
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();
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;