KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > transitiveReasoner > TransitiveGraphCache


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 JavaDoc arg1, Object JavaDoc 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 JavaDoc 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 JavaDoc arg1, Object JavaDoc 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 JavaDoc arg1, Object JavaDoc 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 JavaDoc arg1, Object JavaDoc 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 JavaDoc arg1, Object JavaDoc 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 JavaDoc done, Object JavaDoc 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 JavaDoc toString() {
387             return "[" + rdfNode.getLocalName() + "]";
388         }
389         
390         /**
391          * Full dump for debugging
392          */
393         public String JavaDoc dump() {
394             String JavaDoc 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 JavaDoc dumpSet(Set s) {
409             StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
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 JavaDoc next() {
489             Object JavaDoc 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 JavaDoc next() {
598             Object JavaDoc 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 JavaDoc members, Object JavaDoc 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   &nbs