Source code: com/hp/hpl/jena/reasoner/transitiveReasoner/TransitiveGraphCache.java
1 /******************************************************************
2 * File: TransitiveGraphCacheNew.java
3 * Created by: Dave Reynolds
4 * Created on: 16-Nov-2004
5 *
6 * (c) Copyright 2004, 2005 Hewlett-Packard Development Company, LP
7 * [See end of file]
8 * $Id: TransitiveGraphCache.java,v 1.18 2005/02/21 12:18:36 andy_seaborne Exp $
9 *****************************************************************/
10
11 package com.hp.hpl.jena.reasoner.transitiveReasoner;
12
13 import com.hp.hpl.jena.graph.*;
14 import com.hp.hpl.jena.util.iterator.*;
15 import com.hp.hpl.jena.reasoner.*;
16
17 import java.util.*;
18
19 /**
20 * Datastructure used to represent a closed transitive reflexive relation.
21 * It (mostly) incrementally maintains a transitive reduction and transitive
22 * closure of the relationship and so queries should be faster than dynamically
23 * computing the closed or reduced relations.
24 * <p>
25 * The implementation stores the reduced and closed relations as real graph
26 * (objects linked together by pointers). For each graph node we store its direct
27 * predecessors and successors and its closed successors. A cost penalty
28 * is the storage turnover involved in turning the graph representation back into
29 * triples to answer queries. We could avoid this by optionally also storing the
30 * manifested triples for the links.
31 * </p><p>
32 * Cycles are currently handled by collapsing strongly connected components.
33 * Incremental deletes would be possible but at the price of substanially
34 * more storage and code complexity. We compromise by doing the easy cases
35 * incrementally but some deletes (those that break strongly connected components)
36 * will trigger a fresh rebuild.
37 * </p><p>
38 * TODO Combine this with interval indexes (Agrawal, Borigda and Jagadish 1989)
39 * for storing the closure of the predecessor relationship. Typical graphs
40 * will be nearly tree shaped so the successor closure is modest (L^2 where
41 * L is the depth of the tree branch) but the predecessor closure would be
42 * expensive. The interval index would handle predecessor closure nicely.
43 * </p>
44 * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
45 * @version $Revision: 1.18 $
46 */
47
48 // Note to maintainers. The GraphNode object is treated as a record structure
49 // rather than an abstract datatype by the rest of the GraphCache code - which
50 // directly access its structure. I justify this on the flimsy grounds that it is a
51 // private inner class.
52
53 public class TransitiveGraphCache implements Finder {
54
55 /** Flag controlling the whether the triples
56 * representing the closed relation should also be cached. */
57 protected boolean cacheTriples = false;
58
59 /** Map from RDF Node to the corresponding Graph node. */
60 protected HashMap nodeMap = new HashMap();
61
62 /** The RDF predicate representing the direct relation */
63 protected Node directPredicate;
64
65 /** The RDF predicate representing the closed relation */
66 protected Node closedPredicate;
67
68 /** A list of pending deletes which break the cycle-free normal form */
69 protected Set deletesPending;
70
71 /** The original triples, needed for processing delete operations
72 * because some information is lost in the SCC process */
73 protected Set originalTriples = new HashSet();
74
75 /**
76 * Inner class used to represent vistors than can be applied to each
77 * node in a graph walk.
78 */
79 static interface Visitor {
80 void visit(GraphNode node, Object arg1, Object arg2);
81 }
82
83 /**
84 * Inner class used to represent the graph node structure.
85 * Rather fat nodes (four sets)
86 */
87 private static class GraphNode {
88 /** The RDF Graph Node this corresponds to */
89 protected Node rdfNode;
90
91 /** The list of direct successor nodes to this node */
92 protected Set succ = new HashSet();
93
94 /** The list of direct predecessors nodes */
95 protected Set pred = new HashSet();
96
97 /** The set of all transitive successor nodes to this node */
98 protected Set succClosed = new HashSet();
99
100 /** An optional cache of the triples that represent succClosed */
101 protected List succClosedTriples;
102
103 /** Null for simple nodes. For the lead node in a SCC will be a list
104 * of all the nodes in the SCC. For non-lead nodes it will be a ref to the lead node. */
105 protected Object aliases;
106
107 /**
108 * Constructor.
109 */
110 public GraphNode(Node node) {
111 rdfNode = node;
112 }
113
114 /**
115 * Return true if there is a path from this node to the argument node.
116 */
117 public boolean pathTo(GraphNode A) {
118 if (this == A) return true;
119 return succClosed.contains(A);
120 }
121
122 /**
123 * Return true if there is a direct path from this node to the argument node.
124 */
125 public boolean directPathTo(GraphNode A) {
126 if (this == A) return true;
127 return succ.contains(A);
128 }
129
130 /**
131 * Return the lead node in the strongly connected component containing this node.
132 * It will be the node itself if it is a singleton or the lead node.
133 */
134 public GraphNode leadNode() {
135 if (aliases != null && aliases instanceof GraphNode) {
136 return ((GraphNode)aliases).leadNode();
137 } else {
138 return this;
139 }
140 }
141
142 /**
143 * Visit each predecessor of this node applying the given visitor.
144 */
145 public void visitPredecessors(Visitor visitor, Object arg1, Object arg2) {
146 visitor.visit(this, arg1, arg2);
147 doVisitPredecessors(visitor, arg1, arg2, new HashSet());
148 }
149
150 /**
151 * Visit each predecessor of this node applying the given visitor.
152 * Breadth first.
153 */
154 private void doVisitPredecessors(Visitor visitor, Object arg1, Object arg2, Set seen) {
155 if (seen.add(this)) {
156 for (Iterator i = pred.iterator(); i.hasNext(); ) {
157 GraphNode pred = (GraphNode)i.next();
158 visitor.visit(pred, arg1, arg2);
159 }
160 for (Iterator i = pred.iterator(); i.hasNext(); ) {
161 GraphNode pred = (GraphNode)i.next();
162 pred.doVisitPredecessors(visitor, arg1, arg2, seen);
163 }
164 }
165 }
166
167 /**
168 * Return an iterator over all the indirect successors of this node.
169 * This does NOT include aliases of successors and is used for graph maintenance.
170 */
171 public Iterator iteratorOverSuccessors() {
172 return succClosed.iterator();
173 }
174
175 /**
176 * Assert a direct link between this node and this given target.
177 * Does not update the closed successor cache
178 */
179 public void assertLinkTo(GraphNode target) {
180 if (this == target) return;
181 succ.add(target);
182 target.pred.add(this);
183 clearTripleCache();
184 }
185
186 /**
187 * Remove a direct link currently from this node to the given target.
188 * Does not update the closed successor cache.
189 */
190 public void retractLinkTo(GraphNode target) {
191 if (this == target) return;
192 succ.remove(target);
193 target.pred.remove(this);
194 clearTripleCache();
195 }
196
197 /**
198 * Assert an inferred indirect link from this node to the given traget
199 */
200 public void assertIndirectLinkTo(GraphNode target) {
201 // if (this == target) return;
202 succClosed.add(target);
203 clearTripleCache();
204 }
205
206 /**
207 * Clear the option cache of the closure triples.
208 */
209 public void clearTripleCache() {
210 succClosedTriples = null;
211 }
212
213 /**
214 * Propagate the results of adding a link from this
215 * node to the target node.
216 */
217 public void propagateAdd(GraphNode target) {
218 Set sc = target.succClosed;
219 visitPredecessors(new Visitor() {
220 public void visit(GraphNode node, Object arg1, Object target) {
221 Set sc = (Set)arg1;
222 // Add closure
223 node.succClosed.addAll(sc);
224 node.succClosed.add(target);
225 // Scan for redundant links
226 for (Iterator i = node.succ.iterator(); i.hasNext();) {
227 GraphNode s = (GraphNode)i.next();
228 if (sc.contains(s)) {
229 i.remove();
230 s.pred.remove(node);
231 }
232 }
233 }
234 }, sc, target);
235 }
236
237 /**
238 * Propagate the results of creating a new SCC with this
239 * node as lead.
240 */
241 public void propagateSCC() {
242 Set visited = new HashSet();
243 visited.add(this);
244 // Scan predecessors not including ourselves
245 doVisitPredecessors(new Visitor() {
246 public void visit(GraphNode node, Object arg1, Object arg2) {
247 Set sc = (Set)arg1;
248 // Add closure
249 node.succClosed.addAll(sc);
250 // Scan for redundant links
251 for (Iterator i = node.succ.iterator(); i.hasNext();) {
252 GraphNode s = (GraphNode)i.next();
253 if (sc.contains(s)) {
254 i.remove();
255 s.pred.remove(node);
256 }
257 }
258 }
259 }, succClosed, null, visited);
260 }
261
262 /**
263 * Given a set of SCC nodes make this the lead member of the SCC and
264 * reroute all incoming and outgoing links accordingly.
265 * This eager rewrite is based on the assumption that there are few cycles
266 * so it is better to rewrite once and keep the graph easy to traverse.
267 */
268 public void makeLeadNodeFor(Set members) {
269 // Accumulate all successors
270 Set newSucc = new HashSet();
271 Set newSuccClosed = new HashSet();
272 for (Iterator i = members.iterator(); i.hasNext(); ) {
273 GraphNode n = (GraphNode)i.next();
274 newSucc.addAll(n.succ);
275 newSuccClosed.addAll(n.succClosed);
276 }
277 newSucc.removeAll(members);
278 newSuccClosed.removeAll(members);
279 succ = newSucc;
280 succClosed = newSuccClosed;
281
282 // Rewrite all direct successors to have us as predecessor
283 for (Iterator i = succ.iterator(); i.hasNext();) {
284 GraphNode n = (GraphNode)i.next();
285 n.pred.removeAll(members);
286 n.pred.add(this);
287 }
288
289 // Find all predecessor nodes and relink link them to point to us
290 Set done = new HashSet();
291 Set newAliases = new HashSet();
292 for (Iterator i = members.iterator(); i.hasNext(); ) {
293 GraphNode m = (GraphNode)i.next();
294 if (m.aliases instanceof Set) {
295 newAliases.addAll((Set)m.aliases);
296 } else {
297 newAliases.add(m);
298 }
299 }
300 this.aliases = newAliases;
301 for (Iterator i = members.iterator(); i.hasNext(); ) {
302 GraphNode n = (GraphNode)i.next();
303 if (n != this) {
304 pred.addAll(n.pred);
305 n.relocateAllRefTo(this, done);
306 n.aliases = this;
307 }
308 }
309 pred.removeAll(members);
310 }
311
312 /**
313 * This node is being absorbed into an SCC with the given node as the
314 * new lead node. Trace out all predecessors to this node and relocate
315 * them to point to the new lead node.
316 */
317 private void relocateAllRefTo(GraphNode lead, Set done) {
318 visitPredecessors(new Visitor(){
319 public void visit(GraphNode node, Object done, Object leadIn) {
320 if (((Set)done).add(node)) {
321 GraphNode lead = (GraphNode)leadIn;
322 Set members = (Set)lead.aliases;
323 int before = node.succ.size();
324 node.succ.removeAll(members);
325 node.succClosed.removeAll(members);
326 node.succClosed.add(lead);
327 if (node.succ.size() != before) {
328 node.succ.add(lead);
329 }
330 }
331 }
332 }, done, lead);
333 }
334
335 /**
336 * Return an iterator over all of the triples representing outgoing links
337 * from this node.
338 * @param closed if set to true it returns triples in the transitive closure,
339 * if set to false it returns triples in the transitive reduction
340 * @param cache the enclosing TransitiveGraphCache
341 */
342 public ExtendedIterator listTriples(boolean closed, TransitiveGraphCache tgc) {
343 if (tgc.cacheTriples) {
344 // TODO implement - for now default to non-cached
345 return WrappedIterator.create(leadNode().triplesForSuccessors(rdfNode, closed, tgc).iterator());
346 } else {
347 return WrappedIterator.create(leadNode().triplesForSuccessors(rdfNode, closed, tgc).iterator());
348 }
349 }
350
351 /**
352 * Create a list of triples for a given set of successors to this node.
353 */
354 private List triplesForSuccessors(Node base, boolean closed, TransitiveGraphCache tgc) {
355 Set successors = closed ? succClosed : succ;
356 ArrayList result = new ArrayList(successors.size() + 10);
357 result.add(new Triple(base, tgc.closedPredicate, base)); // implicit reflexive case
358 for (Iterator i = successors.iterator(); i.hasNext(); ) {
359 GraphNode s = (GraphNode)i.next();
360 result.add(new Triple(base, tgc.closedPredicate, s.rdfNode));
361 if (s.aliases instanceof Set) {
362 for (Iterator j = ((Set)s.aliases).iterator(); j.hasNext(); ) {
363 result.add(new Triple(base, tgc.closedPredicate, ((GraphNode)j.next()).rdfNode));
364 }
365 }
366 }
367 if (aliases instanceof Set) {
368 for (Iterator j = ((Set)aliases).iterator(); j.hasNext(); ) {
369 result.add(new Triple(base, tgc.closedPredicate, ((GraphNode)j.next()).rdfNode));
370 }
371 }
372 return result;
373 }
374
375 /**
376 * Return an iterator over all of the triples representing incoming links to this node.
377 * Currently no caching enabled.
378 */
379 public ExtendedIterator listPredecessorTriples(boolean closed, TransitiveGraphCache tgc) {
380 return new GraphWalker(leadNode(), rdfNode, closed, tgc.closedPredicate);
381 }
382
383 /**
384 * Print node label to assist with debug.
385 */
386 public String toString() {
387 return "[" + rdfNode.getLocalName() + "]";
388 }
389
390 /**
391 * Full dump for debugging
392 */
393 public String dump() {
394 String result = rdfNode.getLocalName();
395 if (aliases != null) {
396 if (aliases instanceof GraphNode) {
397 result = result + " leader=" + aliases + ", ";
398 } else {
399 result = result + " SCC=" + dumpSet((Set)aliases) +", ";
400 }
401 }
402 return result + " succ=" + dumpSet(succ) + ", succClose=" + dumpSet(succClosed) + ", pred=" + dumpSet(pred);
403 }
404
405 /**
406 * Dump a set to a string for debug.
407 */
408 private String dumpSet(Set s) {
409 StringBuffer sb = new StringBuffer();
410 sb.append("{");
411 boolean started = false;
412 for (Iterator i = s.iterator(); i.hasNext(); ) {
413 if (started) {
414 sb.append(", ");
415 } else {
416 started = true;
417 }
418 sb.append(i.next().toString());
419 }
420 sb.append("}");
421 return sb.toString();
422 }
423
424 } // End of GraphNode inner class
425
426 /**
427 * Inner class used to walk backward links of the graph.
428 * <p> The triples are dynamically allocated which is costly.
429 */
430 private static class GraphWalker extends NiceIterator implements ExtendedIterator {
431
432 /** Indicate if this is a shallow or deep walk */
433 boolean isDeep;
434
435 /** The current node being visited */
436 GraphNode node;
437
438 /** The root node for reconstructing triples */
439 Node root;
440
441 /** The predicate for reconstructing triples */
442 Node predicate;
443
444 /** Iterator over the predecessors to the current node bein walked */
445 Iterator iterator = null;
446
447 /** Iterator over the aliases of the current predecessor being output */
448 Iterator aliasIterator = null;
449
450 /** stack of graph nodes being walked */
451 ArrayList nodeStack = new ArrayList();
452
453 /** stack of iterators for the higher nodes in the walk */
454 ArrayList iteratorStack = new ArrayList();
455
456 /** The next value to be returned */
457 Triple next;
458
459 /** The set of junction nodes already visited */
460 HashSet visited = new HashSet();
461
462 /**
463 * Constructor. Creates an iterator which will walk
464 * the graph, returning triples.
465 * @param node the starting node for the walk
466 * @param rdfNode the rdfNode we are try to find predecessors for
467 * @param closed set to true of walking the whole transitive closure
468 * @param predicate the predicate to be walked
469 */
470 GraphWalker(GraphNode node, Node rdfNode, boolean closed, Node predicate) {
471 isDeep = closed;
472 this.node = node;
473 this.root = rdfNode;
474 this.predicate = predicate;
475 this.iterator = node.pred.iterator();
476 if (node.aliases instanceof Set) {
477 aliasIterator = ((Set)node.aliases).iterator();
478 }
479 next = new Triple(root, predicate, root); // implicit reflexive case
480 }
481
482 /** Iterator interface - test if more values available */
483 public boolean hasNext() {
484 return next != null;
485 }
486
487 /** Iterator interface - get next value */
488 public Object next() {
489 Object toReturn = next;
490 walkOne();
491 return toReturn;
492 }
493
494 /**
495 * Walk one step
496 */
497 protected void walkOne() {
498 if (aliasIterator != null) {
499 if (aliasIterator.hasNext()) {
500 GraphNode nextNode = (GraphNode)aliasIterator.next();
501 next = new Triple(nextNode.rdfNode, predicate, root);
502 return;
503 } else {
504 aliasIterator = null;
505 }
506 }
507 if (iterator.hasNext()) {
508 GraphNode nextNode = (GraphNode)iterator.next();
509 if (visited.add(nextNode)) {
510 // Set up for depth-first visit next
511 if (isDeep)
512 pushStack(nextNode);
513 next = new Triple(nextNode.rdfNode, predicate, root);
514 if (nextNode.aliases instanceof Set) {
515 aliasIterator = ((Set)nextNode.aliases).iterator();
516 }
517 } else {
518 // Already visited this junction, skip it
519 walkOne();
520 return;
521 }
522 } else {
523 // Finished this node
524 if (nodeStack.isEmpty()) {
525 next = null;
526 return;
527 }
528 popStack();
529 walkOne();
530 }
531 }
532
533 /**
534 * Push the current state onto the stack
535 */
536 protected void pushStack(GraphNode next) {
537 nodeStack.add(node);
538 iteratorStack.add(iterator);
539 iterator = next.pred.iterator();
540 node = next;
541 }
542
543 /**
544 * Pop the prior state back onto the stack
545 */
546 protected void popStack() {
547 int i = nodeStack.size()-1;
548 iterator = (Iterator) iteratorStack.remove(i);
549 node = (GraphNode) nodeStack.remove(i);
550 }
551
552 } // End of GraphWalker inner class
553
554 /**
555 * Inner class used to do a complete walk over the graph
556 */
557 private static class FullGraphWalker extends NiceIterator implements ExtendedIterator {
558
559 /** Flag whether we are walking over the closed or direct relations */
560 boolean closed;
561
562 /** Iterator over the start nodes in the node map */
563 Iterator baseNodeIt;
564
565 /** The current node being visited */
566 GraphNode node;
567
568 /** The root node for reconstructing triples */
569 Node nodeN;
570
571 /** The predicate for reconstructing triples */
572 Node predicate;
573
574 /** Iterator over the successor nodes for the baseNode */
575 Iterator succIt = null;
576
577 /** Iterator over the aliases for the current successor */
578 Iterator aliasesIt = null;
579
580 /** The next value to be returned */
581 Triple next;
582
583 /** Construct a walker for the full closed or direct graph */
584 FullGraphWalker(boolean closed, Node predicate, HashMap nodes) {
585 this.predicate = predicate;
586 this.closed = closed;
587 baseNodeIt = nodes.values().iterator();
588 walkOne();
589 }
590
591 /** Iterator interface - test if more values available */
592 public boolean hasNext() {
593 return next != null;
594 }
595
596 /** Iterator interface - get next value */
597 public Object next() {
598 Object toReturn = next;
599 walkOne();
600 return toReturn;
601 }
602
603 /**
604 * Walk one step
605 */
606 protected void walkOne() {
607 if (aliasesIt != null) {
608 if (aliasesIt.hasNext()) {
609 next = new Triple(nodeN, predicate, ((GraphNode)aliasesIt.next()).rdfNode);
610 return;
611 } else {
612 aliasesIt = null; // End of aliases
613 }
614 }
615
616 if (succIt != null) {
617 if (succIt.hasNext()) {
618 GraphNode succ = (GraphNode)succIt.next();
619 if (succ.aliases instanceof Set) {
620 aliasesIt = ((Set)succ.aliases).iterator();
621 }
622 next = new Triple(nodeN, predicate, succ.rdfNode);
623 return;
624 } else {
625 succIt = null; // End of the successors
626 }
627 }
628
629 if (baseNodeIt.hasNext()) {
630 node = (GraphNode)baseNodeIt.next();
631 nodeN = node.rdfNode;
632 succIt = (closed ? node.succClosed : node.succ).iterator();
633 next = new Triple(nodeN, predicate, nodeN); // Implicit reflexive case
634 } else {
635 next = null; // End of walk
636 }
637 }
638
639 } // End of FullGraphWalker inner class
640
641 /**
642 * Constructor - create a new cache to hold the given relation information.
643 * @param directPredicate The RDF predicate representing the direct relation
644 * @param closedPredicate The RDF predicate representing the closed relation
645 */
646 public TransitiveGraphCache(Node directPredicate, Node closedPredicate) {
647 this.directPredicate = directPredicate;
648 this.closedPredicate = closedPredicate;
649 }
650
651 /**
652 * Returns the closedPredicate.
653 * @return Node
654 */
655 public Node getClosedPredicate() {
656 return closedPredicate;
657 }
658
659 /**
660 * Returns the directPredicate.
661 * @return Node
662 */
663 public Node getDirectPredicate() {
664 return directPredicate;
665 }
666
667 /**
668 * Register a new relation instance in the cache
669 */
670 public synchronized void addRelation(Triple t) {
671 originalTriples.add(t);
672 addRelation(t.getSubject(), t.getObject());
673 }
674
675 /**
676 * Register a new relation instance in the cache
677 */
678 private void addRelation(Node start, Node end) {
679 if (start.equals(end)) return; // Reflexive case is built in
680 GraphNode startN = getLead(start);
681 GraphNode endN = getLead(end);
682
683 // Check if this link is already known about
684 if (startN.pathTo(endN)) {
685 // yes, so no work to do
686 return;
687 }
688
689 boolean needJoin = endN.pathTo(startN);
690 Set members = null;
691 if (needJoin) {
692 // Reduce graph to DAG by factoring out SCCs
693 // startN.assertLinkTo(endN);
694 // First find all the members of the new component
695 members = new HashSet();
696 members.add(endN);
697 startN.visitPredecessors(new Visitor() {
698 public void visit(GraphNode node, Object members, Object endN) {
699 if (((GraphNode)endN).pathTo(node)) ((Set)members).add(node);
700 } }, members, endN);
701 // Then create the SCC
702 startN.makeLeadNodeFor(members);
703 // Now propagate the closure in the normalized graph
704 startN.propagateSCC();
705 } else {
706 // Walk all predecessors of start retracting redundant direct links
707 // and adding missing closed links
708 startN.propagateAdd(endN);
709 startN.assertLinkTo(endN);
710 }
711
712 if (needJoin) {
713 // Create a new strongly connected component
714 }
715 }
716
717 /**
718 * Remove an instance of a relation from the cache.
719 */
720 public void removeRelation(Triple t) {
721 Node start = t.getSubject();
722 Node end = t.getObject();
723 if (start == end) {
724 return; // Reflexive case is built in
725 }
726 GraphNode startN = getLead(start);
727 GraphNode endN = getLead(end);
728 if (startN != endN && !(startN.directPathTo(endN))) {
729 // indirect link can't be removed by itself
730 return;
731 }
732 // This is a remove of a direct link possibly within an SCC
733 // Delay as long as possible and do deletes in a batch
734 if (deletesPending == null) {
735 deletesPending = new HashSet();
736 }
737 deletesPending.add(t);
738 }
739
740 /**
741 * Process outstanding delete actions
742 */
743 private void processDeletes() {
744 // The kernel is the set of start nodes of deleted links
745 Set kernel = new HashSet();
746 for (Iterator i = deletesPending.iterator(); i.hasNext(); ) {
747 Triple t = (Triple)i.next();
748 GraphNode start = (GraphNode)nodeMap.get(t.getSubject());
749 kernel.add(start);
750 }
751
752 // The predecessor set of kernel
753 Set pKernel = new HashSet();
754 pKernel.addAll(kernel);
755 for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
756 GraphNode n = (GraphNode)i.next();
757 for (Iterator j = kernel.iterator(); j.hasNext();) {
758 GraphNode target = (GraphNode)j.next();
759 if (n.pathTo(target)) {
760 pKernel.add(n); break;
761 }
762 }
763 }
764
765 // Cut the pKernel away from the finge of nodes that it connects to
766 for (Iterator i = pKernel.iterator(); i.hasNext(); ) {
767 GraphNode n = (GraphNode)i.next();
768 for (Iterator j = n.succ.iterator(); j.hasNext(); ) {
769 GraphNode fringe = (GraphNode)j.next();
770 if (! pKernel.contains(fringe)) {
771 fringe.pred.remove(n);
772 }
773 }
774 n.succ.clear();
775 n.succClosed.clear();
776 n.pred.clear();
777 }
778
779 // Delete the triples
780 originalTriples.removeAll(deletesPending);
781 deletesPending.clear();
782
783 // Reinsert the remaining links
784 for (Iterator i = originalTriples.iterator(); i.hasNext(); ) {
785 Triple t = (Triple)i.next();
786 GraphNode n = (GraphNode)nodeMap.get(t.getSubject());
787 if (pKernel.contains(n)) {
788 addRelation(t);
789 }
790 }
791 }
792
793 /**
794 * Extended find interface used in situations where the implementator
795 * may or may not be able to answer the complete query.
796 * <p>
797 * In this case any query on the direct or closed predicates will
798 * be assumed complete, any other query will pass on to the continuation.</p>
799 * @param pattern a TriplePattern to be matched against the data
800 * @param continuation either a Finder or a normal Graph which
801 * will be asked for additional match results if the implementor
802 * may not have completely satisfied the query.
803 */
804 public ExtendedIterator findWithContinuation(TriplePattern pattern, Finder continuation) {
805 Node p = pattern.getPredicate();
806
807 if (p.isVariable()) {
808 // wildcard predicate so return merge of cache and continuation
809 return find(pattern).andThen(continuation.find(pattern));
810 } else if (p.equals(directPredicate) || p.equals(closedPredicate)) {
811 // Satisfy entire query from the cache
812 return find(pattern);
813 } else {
814 // No matching triples in this cache so just search the continuation
815 return continuation.find(pattern);
816 }
817
818 }
819
820 /**
821 * Return true if the given pattern occurs somewhere in the find sequence.
822 */
823 public boolean contains(TriplePattern pattern) {
824 ClosableIterator it = find(pattern);
825 boolean result = it.hasNext();
826 it.close();
827 return result;
828 }
829 /**
830 * Return an iterator over all registered subject nodes
831 */
832 public ExtendedIterator listAllSubjects() {
833 return WrappedIterator.create(nodeMap.keySet().iterator());
834 }
835
836 /**
837 * Return true if the given Node is registered as a subject node
838 */
839 public boolean isSubject(Node node) {
840 return nodeMap.keySet().contains(node);
841 }
842
843 /**
844 * Cache all instances of the given predicate which are
845 * present in the given Graph.
846 * @param graph the searchable set of triples to cache
847 * @param predicate the predicate to cache, need not be the registered
848 * predicate due to subProperty declarations
849 * @return returns true if new information has been cached
850 */
851 public boolean cacheAll(Finder graph, Node predicate) {
852 ExtendedIterator it = graph.find(new TriplePattern(null, predicate, null));
853 boolean foundsome = it.hasNext();
854 while (it.hasNext()) {
855 Triple triple = (Triple) it.next();
856 addRelation(triple);
857 }
858 it.close();
859 return foundsome;
860 }
861
862 /**
863 * Basic pattern lookup interface.
864 * @param pattern a TriplePattern to be matched against the data
865 * @return a ExtendedIterator over all Triples in the data set
866 * that match the pattern
867 */
868 public ExtendedIterator find(TriplePattern pattern) {
869 if (deletesPending != null && deletesPending.size() > 0) {
870 processDeletes();
871 }
872
873 Node s = pattern.getSubject();
874 Node p = pattern.getPredicate();
875 Node o = pattern.getObject();
876
877 if (p.isVariable() || p.equals(directPredicate) || p.equals(closedPredicate)) {
878 boolean closed = !p.equals(directPredicate);
879 Node pred = closedPredicate; // p.isVariable() ? closedPredicate : p;
880 if (s.isVariable()) {
881 if (o.isVariable()) {
882 // list all the graph contents
883 // ExtendedIterator result = null;
884 // for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
885 // ExtendedIterator nexti = ((GraphNode)i.next()).listTriples(closed, this);
886 // if (result == null) {
887 // result = nexti;
888 // } else {
889 // result = result.andThen(nexti);
890 // }
891 // }
892 // if (result == null) {
893 // return NullIterator.instance;
894 // }
895 return new FullGraphWalker(closed, closedPredicate, nodeMap);
896 } else {
897 // list all backwards from o
898 GraphNode gn_o = (GraphNode)nodeMap.get(o);
899 if (gn_o == null) return NullIterator.instance;
900 return gn_o.listPredecessorTriples(closed, this);
901 }
902 } else {
903 GraphNode gn_s = (GraphNode)nodeMap.get(s);
904 if (gn_s == null) return NullIterator.instance;
905 if (o.isVariable()) {
906 // list forward from s
907 return gn_s.listTriples(closed, this);
908 } else {
909 // Singleton test
910 GraphNode gn_o = (GraphNode)nodeMap.get(o);
911 gn_s = gn_s.leadNode();
912 if (gn_o == null) return NullIterator.instance;
913 gn_o = gn_o.leadNode();
914 if ( closed ? gn_s.pathTo(gn_o) : gn_s.directPathTo(gn_o) ) {
915 return new SingletonIterator(new Triple(s, pred, o));
916 } else {
917 return NullIterator.instance;
918 }
919 }
920 }
921 } else {
922 // No matching triples in this cache
923 return NullIterator.instance;
924 }
925 }
926
927 /**
928 * Create a deep copy of the cache contents.
929 * Works by creating a completely new cache and just adding in the
930 * direct links.
931 */
932 public TransitiveGraphCache deepCopy() {
933 TransitiveGraphCache copy = new TransitiveGraphCache(directPredicate, closedPredicate);
934 Iterator i = find(new TriplePattern(null, directPredicate, null));
935 while (i.hasNext()) {
936 Triple t = (Triple)i.next();
937 copy.addRelation(t.getSubject(), t.getObject());
938 }
939 return copy;
940 }
941
942 /**
943 * Clear the entire cache contents.
944 */
945 public void clear() {
946 nodeMap.clear();
947 }
948
949 /**
950 * Enable/disabling caching of the Triples representing the relationships. If this is
951 * enabled then a number of triples quadratic in the graph depth will be stored. If it
952 * is disabled then all queries will turn over storage dynamically creating the result triples.
953 */
954 public void setCaching(boolean enable) {
955 if (! enable && cacheTriples) {
956 // Switching off so clear the existing cache
957 for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
958 ((GraphNode)i.next()).clearTripleCache();
959 }
960 }
961 cacheTriples = enable;
962 }
963
964 /**
965 * Dump a description of the cache to a string for debug.
966 */
967 public String dump() {
968 StringBuffer sb = new StringBuffer();
969 for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
970 GraphNode n = (GraphNode)i.next();
971 sb.append(n.dump());
972 sb.append("\n");
973 }
974 return sb.toString();
975 }
976
977 // ----------------------------------------------------------------------
978 // Internal utility methods
979 // ----------------------------------------------------------------------
980
981 /**
982 * Return the lead node of the strongly connected component corresponding
983 * to the given RDF node.
984 */
985 private GraphNode getLead(Node n) {
986 GraphNode gn = (GraphNode)nodeMap.get(n);
987 if (gn == null) {
988 gn = new GraphNode(n);
989 nodeMap.put(n, gn);
990 return gn;
991 } else {
992 return gn.leadNode();
993 }
994 }
995
996 }
997
998
999 /*
1000 (c) Copyright 2004, 2005 Hewlett-Packard Development Company, LP
1001 All rights reserved.
1002
1003 Redistribution and use in source and binary forms, with or without
1004 modification, are permitted provided that the following conditions
1005 are met:
1006
1007 1. Redistributions of source code must retain the above copyright
1008 notice, this list of conditions and the following disclaimer.
1009
1010 2. Redistributions in binary form must reproduce the above copyright
1011 notice, this list of conditions and the following disclaimer in the
1012 documentation and/or other materials provided with the distribution.
1013
1014 3. The name of the author may not be used to endorse or promote products
1015 derived from this software without specific prior written permission.
1016
1017 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1018 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1019 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1020 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1021 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1022 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1023 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1024 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1027*/