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 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*/
1028

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags