Source Code Cross Referenced for TransitiveGraphCache.java in  » RSS-RDF » Jena-2.5.5 » com » hp » hpl » jena » reasoner » transitiveReasoner » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » RSS RDF » Jena 2.5.5 » com.hp.hpl.jena.reasoner.transitiveReasoner 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


0001:        /******************************************************************
0002:         * File:        TransitiveGraphCacheNew.java
0003:         * Created by:  Dave Reynolds
0004:         * Created on:  16-Nov-2004
0005:         * 
0006:         * (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
0007:         * [See end of file]
0008:         * $Id: TransitiveGraphCache.java,v 1.24 2008/01/02 12:07:50 andy_seaborne Exp $
0009:         *****************************************************************/package com.hp.hpl.jena.reasoner.transitiveReasoner;
0010:
0011:        import com.hp.hpl.jena.graph.*;
0012:        import com.hp.hpl.jena.util.iterator.*;
0013:        import com.hp.hpl.jena.reasoner.*;
0014:
0015:        import java.util.*;
0016:
0017:        /**
0018:         * Datastructure used to represent a closed transitive reflexive relation.
0019:         * It (mostly) incrementally maintains a transitive reduction and transitive
0020:         * closure of the relationship and so queries should be faster than dynamically 
0021:         * computing the closed or reduced relations.
0022:         * <p>
0023:         * The implementation stores the reduced and closed relations as real graph
0024:         * (objects linked together by pointers). For each graph node we store its direct
0025:         * predecessors and successors and its closed successors.  A cost penalty 
0026:         * is the storage turnover involved in turning the graph representation back into 
0027:         * triples to answer queries. We could avoid this by optionally also storing the
0028:         * manifested triples for the links.
0029:         * </p><p>
0030:         * Cycles are currently handled by collapsing strongly connected components.
0031:         * Incremental deletes would be possible but at the price of substanially 
0032:         * more storage and code complexity. We compromise by doing the easy cases
0033:         * incrementally but some deletes (those that break strongly connected components)
0034:         * will trigger a fresh rebuild.
0035:         * </p><p>
0036:         * TODO Combine this with interval indexes (Agrawal, Borigda and Jagadish 1989) 
0037:         * for storing the closure of the predecessor relationship. Typical graphs
0038:         * will be nearly tree shaped so the successor closure is modest (L^2 where
0039:         * L is the depth of the tree branch) but the predecessor closure would be 
0040:         * expensive. The interval index would handle predecessor closure nicely.
0041:         * </p>
0042:         * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
0043:         * @version $Revision: 1.24 $
0044:         */
0045:
0046:        // Note to maintainers. The GraphNode object is treated as a record structure
0047:        // rather than an abstract datatype by the rest of the GraphCache code - which
0048:        // directly access its structure. I justify this on the flimsy grounds that it is a
0049:        // private inner class.
0050:        public class TransitiveGraphCache implements  Finder {
0051:
0052:            /** Flag controlling the whether the triples 
0053:             *  representing the closed relation should also be cached. */
0054:            protected boolean cacheTriples = false;
0055:
0056:            /** Map from RDF Node to the corresponding Graph node. */
0057:            protected HashMap nodeMap = new HashMap();
0058:
0059:            /** The RDF predicate representing the direct relation */
0060:            protected Node directPredicate;
0061:
0062:            /** The RDF predicate representing the closed relation */
0063:            protected Node closedPredicate;
0064:
0065:            /** A list of pending deletes which break the cycle-free normal form */
0066:            protected Set deletesPending;
0067:
0068:            /** The original triples, needed for processing delete operations
0069:             * because some information is lost in the SCC process */
0070:            protected Set originalTriples = new HashSet();
0071:
0072:            /**
0073:             * Inner class used to represent vistors than can be applied to each
0074:             * node in a graph walk. 
0075:             */
0076:            static interface Visitor {
0077:                // The visitor must not delete and pred entries to avoid CME
0078:                // If this is needed return a non-null result which is a list of pred nodes to kill
0079:                List visit(GraphNode node, GraphNode processing, Object arg1,
0080:                        Object arg2);
0081:            }
0082:
0083:            /**
0084:             * Inner class used to represent the graph node structure.
0085:             * Rather fat nodes (four sets)
0086:             */
0087:            private static class GraphNode {
0088:                /** The RDF Graph Node this corresponds to */
0089:                protected Node rdfNode;
0090:
0091:                /** The list of direct successor nodes to this node */
0092:                protected Set succ = new HashSet();
0093:
0094:                /** The list of direct predecessors nodes */
0095:                protected Set pred = new HashSet();
0096:
0097:                /** The set of all transitive successor nodes to this node */
0098:                protected Set succClosed = new HashSet();
0099:
0100:                /** An optional cache of the triples that represent succClosed */
0101:                protected List succClosedTriples;
0102:
0103:                /** Null for simple nodes. For the lead node in a SCC will be a list
0104:                 * of all the nodes in the SCC. For non-lead nodes it will be a ref to the lead node. */
0105:                protected Object aliases;
0106:
0107:                /**
0108:                 * Constructor.
0109:                 */
0110:                public GraphNode(Node node) {
0111:                    rdfNode = node;
0112:                }
0113:
0114:                /**
0115:                 * Return true if there is a path from this node to the argument node.
0116:                 */
0117:                public boolean pathTo(GraphNode A) {
0118:                    if (this  == A)
0119:                        return true;
0120:                    return succClosed.contains(A);
0121:                }
0122:
0123:                /**
0124:                 * Return true if there is a direct path from this node to the argument node.
0125:                 */
0126:                public boolean directPathTo(GraphNode A) {
0127:                    if (this  == A)
0128:                        return true;
0129:                    return succ.contains(A);
0130:                }
0131:
0132:                /**
0133:                 * Return the lead node in the strongly connected component containing this node.
0134:                 * It will be the node itself if it is a singleton or the lead node. 
0135:                 */
0136:                public GraphNode leadNode() {
0137:                    if (aliases != null && aliases instanceof  GraphNode) {
0138:                        return ((GraphNode) aliases).leadNode();
0139:                    } else {
0140:                        return this ;
0141:                    }
0142:                }
0143:
0144:                /**
0145:                 * Visit each predecessor of this node applying the given visitor.
0146:                 */
0147:                public void visitPredecessors(Visitor visitor, Object arg1,
0148:                        Object arg2) {
0149:                    List kill = visitor.visit(this , null, arg1, arg2);
0150:                    if (kill != null)
0151:                        pred.removeAll(kill);
0152:                    doVisitPredecessors(visitor, arg1, arg2, new HashSet());
0153:                }
0154:
0155:                /**
0156:                 * Visit each predecessor of this node applying the given visitor.
0157:                 * Breadth first.
0158:                 */
0159:                private void doVisitPredecessors(Visitor visitor, Object arg1,
0160:                        Object arg2, Set seen) {
0161:                    if (seen.add(this )) {
0162:                        Collection allKill = null;
0163:                        for (Iterator i = pred.iterator(); i.hasNext();) {
0164:                            GraphNode pred = (GraphNode) i.next();
0165:                            List kill = visitor.visit(pred, this , arg1, arg2);
0166:                            if (kill != null) {
0167:                                if (allKill == null)
0168:                                    allKill = new ArrayList();
0169:                                allKill.addAll(kill);
0170:                            }
0171:                        }
0172:                        if (allKill != null)
0173:                            pred.removeAll(allKill);
0174:                        for (Iterator i = pred.iterator(); i.hasNext();) {
0175:                            GraphNode pred = (GraphNode) i.next();
0176:                            pred.doVisitPredecessors(visitor, arg1, arg2, seen);
0177:                        }
0178:                    }
0179:                }
0180:
0181:                /**
0182:                 * Return an iterator over all the indirect successors of this node.
0183:                 * This does NOT include aliases of successors and is used for graph maintenance.
0184:                 */
0185:                public Iterator iteratorOverSuccessors() {
0186:                    return succClosed.iterator();
0187:                }
0188:
0189:                /**
0190:                 * Assert a direct link between this node and this given target.
0191:                 * Does not update the closed successor cache
0192:                 */
0193:                public void assertLinkTo(GraphNode target) {
0194:                    if (this  == target)
0195:                        return;
0196:                    succ.add(target);
0197:                    target.pred.add(this );
0198:                    clearTripleCache();
0199:                }
0200:
0201:                /**
0202:                 * Remove a direct link currently from this node to the given target.
0203:                 * Does not update the closed successor cache.
0204:                 */
0205:                public void retractLinkTo(GraphNode target) {
0206:                    if (this  == target)
0207:                        return;
0208:                    succ.remove(target);
0209:                    target.pred.remove(this );
0210:                    clearTripleCache();
0211:                }
0212:
0213:                /**
0214:                 * Assert an inferred indirect link from this node to the given traget
0215:                 */
0216:                public void assertIndirectLinkTo(GraphNode target) {
0217:                    //            if (this == target) return;
0218:                    succClosed.add(target);
0219:                    clearTripleCache();
0220:                }
0221:
0222:                /**
0223:                 * Clear the option cache of the closure triples.
0224:                 */
0225:                public void clearTripleCache() {
0226:                    succClosedTriples = null;
0227:                }
0228:
0229:                /**
0230:                 * Propagate the results of adding a link from this
0231:                 * node to the target node.
0232:                 */
0233:                public void propagateAdd(GraphNode target) {
0234:                    Set sc = new HashSet(target.succClosed);
0235:                    sc.add(target);
0236:                    visitPredecessors(new Visitor() {
0237:                        public List visit(GraphNode node, GraphNode processing,
0238:                                Object arg1, Object target) {
0239:                            Set sc = (Set) arg1;
0240:                            // Add closure
0241:                            node.succClosed.addAll(sc);
0242:                            // Scan for redundant links
0243:                            List kill = null;
0244:                            for (Iterator i = node.succ.iterator(); i.hasNext();) {
0245:                                GraphNode s = (GraphNode) i.next();
0246:                                if (sc.contains(s)) {
0247:                                    i.remove();
0248:                                    if (s == processing) {
0249:                                        // Can't remove immediately w/o beaking the visitor loop
0250:                                        if (kill == null)
0251:                                            kill = new ArrayList();
0252:                                        kill.add(node);
0253:                                    } else {
0254:                                        s.pred.remove(node);
0255:                                    }
0256:                                }
0257:                            }
0258:                            return kill;
0259:                        }
0260:                    }, sc, target);
0261:                }
0262:
0263:                /**
0264:                 * Propagate the results of creating a new SCC with this
0265:                 * node as lead.
0266:                 */
0267:                public void propagateSCC() {
0268:                    Set visited = new HashSet();
0269:                    visited.add(this );
0270:                    // Scan predecessors not including ourselves
0271:                    doVisitPredecessors(new Visitor() {
0272:                        public List visit(GraphNode node, GraphNode processing,
0273:                                Object arg1, Object arg2) {
0274:                            Set sc = (Set) arg1;
0275:                            // Add closure
0276:                            node.succClosed.addAll(sc);
0277:                            // Scan for redundant links
0278:                            List kill = null;
0279:                            for (Iterator i = node.succ.iterator(); i.hasNext();) {
0280:                                GraphNode s = (GraphNode) i.next();
0281:                                if (sc.contains(s)) {
0282:                                    i.remove();
0283:                                    //                            s.pred.remove(node);
0284:                                    if (s == processing) {
0285:                                        // Can't remove immediately w/o beaking the visitor loop
0286:                                        if (kill == null)
0287:                                            kill = new ArrayList();
0288:                                        kill.add(node);
0289:                                    } else {
0290:                                        s.pred.remove(node);
0291:                                    }
0292:                                }
0293:                            }
0294:                            return kill;
0295:                        }
0296:                    }, succClosed, null, visited);
0297:                }
0298:
0299:                /**
0300:                 * Given a set of SCC nodes make this the lead member of the SCC and
0301:                 * reroute all incoming and outgoing links accordingly.
0302:                 * This eager rewrite is based on the assumption that there are few cycles
0303:                 * so it is better to rewrite once and keep the graph easy to traverse.
0304:                 */
0305:                public void makeLeadNodeFor(Set members) {
0306:                    // Accumulate all successors
0307:                    Set newSucc = new HashSet();
0308:                    Set newSuccClosed = new HashSet();
0309:                    for (Iterator i = members.iterator(); i.hasNext();) {
0310:                        GraphNode n = (GraphNode) i.next();
0311:                        newSucc.addAll(n.succ);
0312:                        newSuccClosed.addAll(n.succClosed);
0313:                    }
0314:                    newSucc.removeAll(members);
0315:                    newSuccClosed.removeAll(members);
0316:                    succ = newSucc;
0317:                    succClosed = newSuccClosed;
0318:
0319:                    // Rewrite all direct successors to have us as predecessor
0320:                    for (Iterator i = succ.iterator(); i.hasNext();) {
0321:                        GraphNode n = (GraphNode) i.next();
0322:                        n.pred.removeAll(members);
0323:                        n.pred.add(this );
0324:                    }
0325:
0326:                    // Find all predecessor nodes and relink link them to point to us
0327:                    Set done = new HashSet();
0328:                    Set newAliases = new HashSet();
0329:                    for (Iterator i = members.iterator(); i.hasNext();) {
0330:                        GraphNode m = (GraphNode) i.next();
0331:                        if (m.aliases instanceof  Set) {
0332:                            newAliases.addAll((Set) m.aliases);
0333:                        } else {
0334:                            newAliases.add(m);
0335:                        }
0336:                    }
0337:                    this .aliases = newAliases;
0338:                    for (Iterator i = members.iterator(); i.hasNext();) {
0339:                        GraphNode n = (GraphNode) i.next();
0340:                        if (n != this ) {
0341:                            pred.addAll(n.pred);
0342:                            n.relocateAllRefTo(this , done);
0343:                            n.aliases = this ;
0344:                        }
0345:                    }
0346:                    pred.removeAll(members);
0347:                }
0348:
0349:                /**
0350:                 * This node is being absorbed into an SCC with the given node as the
0351:                 * new lead node. Trace out all predecessors to this node and relocate
0352:                 * them to point to the new lead node.
0353:                 */
0354:                private void relocateAllRefTo(GraphNode lead, Set done) {
0355:                    visitPredecessors(new Visitor() {
0356:                        public List visit(GraphNode node, GraphNode processing,
0357:                                Object done, Object leadIn) {
0358:                            if (((Set) done).add(node)) {
0359:                                GraphNode lead = (GraphNode) leadIn;
0360:                                Set members = (Set) lead.aliases;
0361:                                int before = node.succ.size();
0362:                                node.succ.removeAll(members);
0363:                                node.succClosed.removeAll(members);
0364:                                node.succClosed.add(lead);
0365:                                if (node.succ.size() != before) {
0366:                                    node.succ.add(lead);
0367:                                }
0368:                            }
0369:                            return null;
0370:                        }
0371:                    }, done, lead);
0372:                }
0373:
0374:                /**
0375:                 * Return an iterator over all of the triples representing outgoing links
0376:                 * from this node.  
0377:                 * @param closed if set to true it returns triples in the transitive closure,
0378:                 * if set to false it returns triples in the transitive reduction
0379:                 * @param cache the enclosing TransitiveGraphCache
0380:                 */
0381:                public ExtendedIterator listTriples(boolean closed,
0382:                        TransitiveGraphCache tgc) {
0383:                    if (tgc.cacheTriples) {
0384:                        // TODO implement - for now default to non-cached
0385:                        return WrappedIterator.create(leadNode()
0386:                                .triplesForSuccessors(rdfNode, closed, tgc)
0387:                                .iterator());
0388:                    } else {
0389:                        return WrappedIterator.create(leadNode()
0390:                                .triplesForSuccessors(rdfNode, closed, tgc)
0391:                                .iterator());
0392:                    }
0393:                }
0394:
0395:                /**
0396:                 * Create a list of triples for a given set of successors to this node.
0397:                 */
0398:                private List triplesForSuccessors(Node base, boolean closed,
0399:                        TransitiveGraphCache tgc) {
0400:                    Set successors = closed ? succClosed : succ;
0401:                    ArrayList result = new ArrayList(successors.size() + 10);
0402:                    result.add(new Triple(base, tgc.closedPredicate, base)); // implicit reflexive case 
0403:                    for (Iterator i = successors.iterator(); i.hasNext();) {
0404:                        GraphNode s = (GraphNode) i.next();
0405:                        result.add(new Triple(base, tgc.closedPredicate,
0406:                                s.rdfNode));
0407:                        if (s.aliases instanceof  Set) {
0408:                            for (Iterator j = ((Set) s.aliases).iterator(); j
0409:                                    .hasNext();) {
0410:                                result.add(new Triple(base,
0411:                                        tgc.closedPredicate, ((GraphNode) j
0412:                                                .next()).rdfNode));
0413:                            }
0414:                        }
0415:                    }
0416:                    if (aliases instanceof  Set) {
0417:                        for (Iterator j = ((Set) aliases).iterator(); j
0418:                                .hasNext();) {
0419:                            result.add(new Triple(base, tgc.closedPredicate,
0420:                                    ((GraphNode) j.next()).rdfNode));
0421:                        }
0422:                    }
0423:                    return result;
0424:                }
0425:
0426:                /**
0427:                 * Return an iterator over all of the triples representing incoming links to this node.
0428:                 * Currently no caching enabled.
0429:                 */
0430:                public ExtendedIterator listPredecessorTriples(boolean closed,
0431:                        TransitiveGraphCache tgc) {
0432:                    return new GraphWalker(leadNode(), rdfNode, closed,
0433:                            tgc.closedPredicate);
0434:                }
0435:
0436:                /**
0437:                 * Print node label to assist with debug.
0438:                 */
0439:                public String toString() {
0440:                    return "[" + rdfNode.getLocalName() + "]";
0441:                }
0442:
0443:                /**
0444:                 * Full dump for debugging
0445:                 */
0446:                public String dump() {
0447:                    String result = rdfNode.getLocalName();
0448:                    if (aliases != null) {
0449:                        if (aliases instanceof  GraphNode) {
0450:                            result = result + " leader=" + aliases + ", ";
0451:                        } else {
0452:                            result = result + " SCC=" + dumpSet((Set) aliases)
0453:                                    + ", ";
0454:                        }
0455:                    }
0456:                    return result + " succ=" + dumpSet(succ) + ", succClose="
0457:                            + dumpSet(succClosed) + ", pred=" + dumpSet(pred);
0458:                }
0459:
0460:                /**
0461:                 * Dump a set to a string for debug.
0462:                 */
0463:                private String dumpSet(Set s) {
0464:                    StringBuffer sb = new StringBuffer();
0465:                    sb.append("{");
0466:                    boolean started = false;
0467:                    for (Iterator i = s.iterator(); i.hasNext();) {
0468:                        if (started) {
0469:                            sb.append(", ");
0470:                        } else {
0471:                            started = true;
0472:                        }
0473:                        sb.append(i.next().toString());
0474:                    }
0475:                    sb.append("}");
0476:                    return sb.toString();
0477:                }
0478:
0479:            } // End of GraphNode inner class
0480:
0481:            /**
0482:             * Inner class used to walk backward links of the graph.
0483:             * <p> The triples are dynamically allocated which is costly. 
0484:             */
0485:            private static class GraphWalker extends NiceIterator implements 
0486:                    ExtendedIterator {
0487:
0488:                /** Indicate if this is a shallow or deep walk */
0489:                boolean isDeep;
0490:
0491:                /** The current node being visited */
0492:                GraphNode node;
0493:
0494:                /** The root node for reconstructing triples */
0495:                Node root;
0496:
0497:                /** The predicate for reconstructing triples */
0498:                Node predicate;
0499:
0500:                /** Iterator over the predecessors to the current node bein walked */
0501:                Iterator iterator = null;
0502:
0503:                /** Iterator over the aliases of the current predecessor being output */
0504:                Iterator aliasIterator = null;
0505:
0506:                /** stack of graph nodes being walked */
0507:                ArrayList nodeStack = new ArrayList();
0508:
0509:                /** stack of iterators for the higher nodes in the walk */
0510:                ArrayList iteratorStack = new ArrayList();
0511:
0512:                /** The next value to be returned */
0513:                Triple next;
0514:
0515:                /** The set of junction nodes already visited */
0516:                HashSet visited = new HashSet();
0517:
0518:                /** 
0519:                 * Constructor. Creates an iterator which will walk
0520:                 * the graph, returning triples.
0521:                 * @param node the starting node for the walk
0522:                 * @param rdfNode the rdfNode we are try to find predecessors for
0523:                 * @param closed set to true of walking the whole transitive closure
0524:                 * @param predicate the predicate to be walked
0525:                 */
0526:                GraphWalker(GraphNode node, Node rdfNode, boolean closed,
0527:                        Node predicate) {
0528:                    isDeep = closed;
0529:                    this .node = node;
0530:                    this .root = rdfNode;
0531:                    this .predicate = predicate;
0532:                    this .iterator = node.pred.iterator();
0533:                    if (node.aliases instanceof  Set) {
0534:                        aliasIterator = ((Set) node.aliases).iterator();
0535:                    }
0536:                    next = new Triple(root, predicate, root); // implicit reflexive case 
0537:                }
0538:
0539:                /** Iterator interface - test if more values available */
0540:                public boolean hasNext() {
0541:                    return next != null;
0542:                }
0543:
0544:                /** Iterator interface - get next value */
0545:                public Object next() {
0546:                    Object toReturn = next;
0547:                    walkOne();
0548:                    return toReturn;
0549:                }
0550:
0551:                /**
0552:                 * Walk one step
0553:                 */
0554:                protected void walkOne() {
0555:                    if (aliasIterator != null) {
0556:                        if (aliasIterator.hasNext()) {
0557:                            GraphNode nextNode = (GraphNode) aliasIterator
0558:                                    .next();
0559:                            next = new Triple(nextNode.rdfNode, predicate, root);
0560:                            return;
0561:                        } else {
0562:                            aliasIterator = null;
0563:                        }
0564:                    }
0565:                    if (iterator.hasNext()) {
0566:                        GraphNode nextNode = (GraphNode) iterator.next();
0567:                        if (visited.add(nextNode)) {
0568:                            // Set up for depth-first visit next
0569:                            if (isDeep)
0570:                                pushStack(nextNode);
0571:                            next = new Triple(nextNode.rdfNode, predicate, root);
0572:                            if (nextNode.aliases instanceof  Set) {
0573:                                aliasIterator = ((Set) nextNode.aliases)
0574:                                        .iterator();
0575:                            }
0576:                        } else {
0577:                            // Already visited this junction, skip it
0578:                            walkOne();
0579:                            return;
0580:                        }
0581:                    } else {
0582:                        // Finished this node
0583:                        if (nodeStack.isEmpty()) {
0584:                            next = null;
0585:                            return;
0586:                        }
0587:                        popStack();
0588:                        walkOne();
0589:                    }
0590:                }
0591:
0592:                /**
0593:                 * Push the current state onto the stack
0594:                 */
0595:                protected void pushStack(GraphNode next) {
0596:                    nodeStack.add(node);
0597:                    iteratorStack.add(iterator);
0598:                    iterator = next.pred.iterator();
0599:                    node = next;
0600:                }
0601:
0602:                /**
0603:                 * Pop the prior state back onto the stack
0604:                 */
0605:                protected void popStack() {
0606:                    int i = nodeStack.size() - 1;
0607:                    iterator = (Iterator) iteratorStack.remove(i);
0608:                    node = (GraphNode) nodeStack.remove(i);
0609:                }
0610:
0611:            } // End of GraphWalker inner class    
0612:
0613:            /**
0614:             * Inner class used to do a complete walk over the graph
0615:             */
0616:            private static class FullGraphWalker extends NiceIterator implements 
0617:                    ExtendedIterator {
0618:
0619:                /** Flag whether we are walking over the closed or direct relations */
0620:                boolean closed;
0621:
0622:                /** Iterator over the start nodes in the node map */
0623:                Iterator baseNodeIt;
0624:
0625:                /** The current node being visited */
0626:                GraphNode node;
0627:
0628:                /** The root node for reconstructing triples */
0629:                Node nodeN;
0630:
0631:                /** The predicate for reconstructing triples */
0632:                Node predicate;
0633:
0634:                /** Iterator over the successor nodes for the baseNode */
0635:                Iterator succIt = null;
0636:
0637:                /** The current successor being processed */
0638:                GraphNode succ;
0639:
0640:                /** Iterator over the aliases for the current successor */
0641:                Iterator aliasesIt = null;
0642:
0643:                /** The next value to be returned */
0644:                Triple next;
0645:
0646:                /** Construct a walker for the full closed or direct graph */
0647:                FullGraphWalker(boolean closed, Node predicate, HashMap nodes) {
0648:                    this .predicate = predicate;
0649:                    this .closed = closed;
0650:                    baseNodeIt = nodes.values().iterator();
0651:                    walkOne();
0652:                }
0653:
0654:                /** Iterator interface - test if more values available */
0655:                public boolean hasNext() {
0656:                    return next != null;
0657:                }
0658:
0659:                /** Iterator interface - get next value */
0660:                public Object next() {
0661:                    Object toReturn = next;
0662:                    walkOne();
0663:                    return toReturn;
0664:                }
0665:
0666:                /**
0667:                 * Walk one step
0668:                 */
0669:                protected void walkOne() {
0670:                    if (aliasesIt != null) {
0671:                        while (aliasesIt.hasNext()) {
0672:                            GraphNode al = (GraphNode) aliasesIt.next();
0673:                            if (al != succ && al != node) {
0674:                                next = new Triple(nodeN, predicate, al.rdfNode);
0675:                                return;
0676:                            }
0677:                        }
0678:                        aliasesIt = null; // End of aliases
0679:                    }
0680:
0681:                    if (succIt != null) {
0682:                        while (succIt.hasNext()) {
0683:                            succ = (GraphNode) succIt.next();
0684:                            if (succ == node)
0685:                                continue; // Skip accidental reflexive cases, already done
0686:                            if (succ.aliases instanceof  Set) {
0687:                                aliasesIt = ((Set) succ.aliases).iterator();
0688:                            }
0689:                            next = new Triple(nodeN, predicate, succ.rdfNode);
0690:                            return;
0691:                        }
0692:                        succIt = null; // End of the successors
0693:                    }
0694:
0695:                    if (baseNodeIt.hasNext()) {
0696:                        node = (GraphNode) baseNodeIt.next();
0697:                        nodeN = node.rdfNode;
0698:                        GraphNode lead = node.leadNode();
0699:                        succIt = (closed ? lead.succClosed : lead.succ)
0700:                                .iterator();
0701:                        if (lead.aliases instanceof  Set) {
0702:                            succIt = new ConcatenatedIterator(succIt,
0703:                                    ((Set) lead.aliases).iterator());
0704:                        }
0705:                        next = new Triple(nodeN, predicate, nodeN); // Implicit reflexive case
0706:                    } else {
0707:                        next = null; // End of walk
0708:                    }
0709:                }
0710:
0711:            } // End of FullGraphWalker inner class
0712:
0713:            /**
0714:             * Constructor - create a new cache to hold the given relation information.
0715:             * @param directPredicate The RDF predicate representing the direct relation
0716:             * @param closedPredicate The RDF predicate representing the closed relation
0717:             */
0718:            public TransitiveGraphCache(Node directPredicate,
0719:                    Node closedPredicate) {
0720:                this .directPredicate = directPredicate;
0721:                this .closedPredicate = closedPredicate;
0722:            }
0723:
0724:            /**
0725:             * Returns the closedPredicate.
0726:             * @return Node
0727:             */
0728:            public Node getClosedPredicate() {
0729:                return closedPredicate;
0730:            }
0731:
0732:            /**
0733:             * Returns the directPredicate.
0734:             * @return Node
0735:             */
0736:            public Node getDirectPredicate() {
0737:                return directPredicate;
0738:            }
0739:
0740:            /**
0741:             * Register a new relation instance in the cache
0742:             */
0743:            public synchronized void addRelation(Triple t) {
0744:                originalTriples.add(t);
0745:                addRelation(t.getSubject(), t.getObject());
0746:            }
0747:
0748:            /**
0749:             * Register a new relation instance in the cache
0750:             */
0751:            private void addRelation(Node start, Node end) {
0752:                if (start.equals(end))
0753:                    return; // Reflexive case is built in
0754:                GraphNode startN = getLead(start);
0755:                GraphNode endN = getLead(end);
0756:
0757:                // Check if this link is already known about
0758:                if (startN.pathTo(endN)) {
0759:                    // yes, so no work to do
0760:                    return;
0761:                }
0762:
0763:                boolean needJoin = endN.pathTo(startN);
0764:                Set members = null;
0765:                if (needJoin) {
0766:                    // Reduce graph to DAG by factoring out SCCs
0767:                    //	        startN.assertLinkTo(endN);
0768:                    // First find all the members of the new component
0769:                    members = new HashSet();
0770:                    members.add(endN);
0771:                    startN.visitPredecessors(new Visitor() {
0772:                        public List visit(GraphNode node, GraphNode processing,
0773:                                Object members, Object endN) {
0774:                            if (((GraphNode) endN).pathTo(node))
0775:                                ((Set) members).add(node);
0776:                            return null;
0777:                        }
0778:                    }, members, endN);
0779:                    // Then create the SCC
0780:                    startN.makeLeadNodeFor(members);
0781:                    // Now propagate the closure in the normalized graph
0782:                    startN.propagateSCC();
0783:                } else {
0784:                    // Walk all predecessors of start retracting redundant direct links
0785:                    // and adding missing closed links
0786:                    startN.propagateAdd(endN);
0787:                    startN.assertLinkTo(endN);
0788:                }
0789:
0790:                if (needJoin) {
0791:                    // Create a new strongly connected component
0792:                }
0793:            }
0794:
0795:            /**
0796:             * Remove an instance of a relation from the cache.
0797:             */
0798:            public void removeRelation(Triple t) {
0799:                Node start = t.getSubject();
0800:                Node end = t.getObject();
0801:                if (start == end) {
0802:                    return; // Reflexive case is built in
0803:                }
0804:                GraphNode startN = getLead(start);
0805:                GraphNode endN = getLead(end);
0806:                if (startN != endN && !(startN.directPathTo(endN))) {
0807:                    // indirect link can't be removed by itself
0808:                    return;
0809:                }
0810:                // This is a remove of a direct link possibly within an SCC
0811:                // Delay as long as possible and do deletes in a batch
0812:                if (deletesPending == null) {
0813:                    deletesPending = new HashSet();
0814:                }
0815:                deletesPending.add(t);
0816:            }
0817:
0818:            /**
0819:             * Process outstanding delete actions
0820:             */
0821:            private void processDeletes() {
0822:                // The kernel is the set of start nodes of deleted links
0823:                Set kernel = new HashSet();
0824:                for (Iterator i = deletesPending.iterator(); i.hasNext();) {
0825:                    Triple t = (Triple) i.next();
0826:                    GraphNode start = (GraphNode) nodeMap.get(t.getSubject());
0827:                    kernel.add(start);
0828:                }
0829:
0830:                // The predecessor set of kernel
0831:                Set pKernel = new HashSet();
0832:                pKernel.addAll(kernel);
0833:                for (Iterator i = nodeMap.values().iterator(); i.hasNext();) {
0834:                    GraphNode n = (GraphNode) i.next();
0835:                    for (Iterator j = kernel.iterator(); j.hasNext();) {
0836:                        GraphNode target = (GraphNode) j.next();
0837:                        if (n.pathTo(target)) {
0838:                            pKernel.add(n);
0839:                            break;
0840:                        }
0841:                    }
0842:                }
0843:
0844:                // Cut the pKernel away from the finge of nodes that it connects to
0845:                for (Iterator i = pKernel.iterator(); i.hasNext();) {
0846:                    GraphNode n = (GraphNode) i.next();
0847:                    for (Iterator j = n.succ.iterator(); j.hasNext();) {
0848:                        GraphNode fringe = (GraphNode) j.next();
0849:                        if (!pKernel.contains(fringe)) {
0850:                            fringe.pred.remove(n);
0851:                        }
0852:                    }
0853:                    n.succ.clear();
0854:                    n.succClosed.clear();
0855:                    n.pred.clear();
0856:                }
0857:
0858:                // Delete the triples
0859:                originalTriples.removeAll(deletesPending);
0860:                deletesPending.clear();
0861:
0862:                // Reinsert the remaining links
0863:                for (Iterator i = originalTriples.iterator(); i.hasNext();) {
0864:                    Triple t = (Triple) i.next();
0865:                    GraphNode n = (GraphNode) nodeMap.get(t.getSubject());
0866:                    if (pKernel.contains(n)) {
0867:                        addRelation(t);
0868:                    }
0869:                }
0870:            }
0871:
0872:            /**
0873:             * Extended find interface used in situations where the implementator
0874:             * may or may not be able to answer the complete query. 
0875:             * <p>
0876:             * In this case any query on the direct or closed predicates will
0877:             * be assumed complete, any other query will pass on to the continuation.</p>
0878:             * @param pattern a TriplePattern to be matched against the data
0879:             * @param continuation either a Finder or a normal Graph which
0880:             * will be asked for additional match results if the implementor
0881:             * may not have completely satisfied the query.
0882:             */
0883:            public ExtendedIterator findWithContinuation(TriplePattern pattern,
0884:                    Finder continuation) {
0885:                Node p = pattern.getPredicate();
0886:
0887:                if (p.isVariable()) {
0888:                    // wildcard predicate so return merge of cache and continuation
0889:                    return find(pattern).andThen(continuation.find(pattern));
0890:                } else if (p.equals(directPredicate)
0891:                        || p.equals(closedPredicate)) {
0892:                    // Satisfy entire query from the cache
0893:                    return find(pattern);
0894:                } else {
0895:                    // No matching triples in this cache so just search the continuation
0896:                    return continuation.find(pattern);
0897:                }
0898:
0899:            }
0900:
0901:            /**
0902:             * Return true if the given pattern occurs somewhere in the find sequence.
0903:             */
0904:            public boolean contains(TriplePattern pattern) {
0905:                ClosableIterator it = find(pattern);
0906:                boolean result = it.hasNext();
0907:                it.close();
0908:                return result;
0909:            }
0910:
0911:            /**
0912:             * Return an iterator over all registered subject nodes
0913:             */
0914:            public ExtendedIterator listAllSubjects() {
0915:                return WrappedIterator.create(nodeMap.keySet().iterator());
0916:            }
0917:
0918:            /**
0919:             * Return true if the given Node is registered as a subject node
0920:             */
0921:            public boolean isSubject(Node node) {
0922:                return nodeMap.keySet().contains(node);
0923:            }
0924:
0925:            /**
0926:             * Cache all instances of the given predicate which are
0927:             * present in the given Graph.
0928:             * @param graph the searchable set of triples to cache
0929:             * @param predicate the predicate to cache, need not be the registered
0930:             * predicate due to subProperty declarations
0931:             * @return returns true if new information has been cached
0932:             */
0933:            public boolean cacheAll(Finder graph, Node predicate) {
0934:                ExtendedIterator it = graph.find(new TriplePattern(null,
0935:                        predicate, null));
0936:                boolean foundsome = it.hasNext();
0937:                while (it.hasNext()) {
0938:                    Triple triple = (Triple) it.next();
0939:                    addRelation(triple);
0940:                }
0941:                it.close();
0942:                return foundsome;
0943:            }
0944:
0945:            /**
0946:             * Basic pattern lookup interface.
0947:             * @param pattern a TriplePattern to be matched against the data
0948:             * @return a ExtendedIterator over all Triples in the data set
0949:             *  that match the pattern
0950:             */
0951:            public ExtendedIterator find(TriplePattern pattern) {
0952:                if (deletesPending != null && deletesPending.size() > 0) {
0953:                    processDeletes();
0954:                }
0955:
0956:                Node s = pattern.getSubject();
0957:                Node p = pattern.getPredicate();
0958:                Node o = pattern.getObject();
0959:
0960:                if (p.isVariable() || p.equals(directPredicate)
0961:                        || p.equals(closedPredicate)) {
0962:                    boolean closed = !p.equals(directPredicate);
0963:                    Node pred = closedPredicate; // p.isVariable() ? closedPredicate : p;
0964:                    if (s.isVariable()) {
0965:                        if (o.isVariable()) {
0966:                            // list all the graph contents
0967:                            //                    ExtendedIterator result = null;
0968:                            //                    for (Iterator i = nodeMap.values().iterator(); i.hasNext(); ) {
0969:                            //                        ExtendedIterator nexti = ((GraphNode)i.next()).listTriples(closed, this);
0970:                            //                        if (result == null) {
0971:                            //                            result = nexti;
0972:                            //                        } else {
0973:                            //                            result = result.andThen(nexti);
0974:                            //                        }
0975:                            //                    }
0976:                            //                    if (result == null) {
0977:                            //                        return NullIterator.instance;
0978:                            //                    }
0979:                            return new FullGraphWalker(closed, closedPredicate,
0980:                                    nodeMap);
0981:                        } else {
0982:                            // list all backwards from o
0983:                            GraphNode gn_o = (GraphNode) nodeMap.get(o);
0984:                            if (gn_o == null)
0985:                                return NullIterator.instance;
0986:                            return gn_o.listPredecessorTriples(closed, this );
0987:                        }
0988:                    } else {
0989:                        GraphNode gn_s = (GraphNode) nodeMap.get(s);
0990:                        if (gn_s == null)
0991:                            return NullIterator.instance;
0992:                        if (o.isVariable()) {
0993:                            // list forward from s
0994:                            return gn_s.listTriples(closed, this );
0995:                        } else {
0996:                            // Singleton test
0997:                            GraphNode gn_o = (GraphNode) nodeMap.get(o);
0998:                            gn_s = gn_s.leadNode();
0999:                            if (gn_o == null)
1000:                                return NullIterator.instance;
1001:                            gn_o = gn_o.leadNode();
1002:                            if (closed ? gn_s.pathTo(gn_o) : gn_s
1003:                                    .directPathTo(gn_o)) {
1004:                                return new SingletonIterator(new Triple(s,
1005:                                        pred, o));
1006:                            } else {
1007:                                return NullIterator.instance;
1008:                            }
1009:                        }
1010:                    }
1011:                } else {
1012:                    // No matching triples in this cache
1013:                    return NullIterator.instance;
1014:                }
1015:            }
1016:
1017:            /**
1018:             * Create a deep copy of the cache contents.
1019:             * Works by creating a completely new cache and just adding in the
1020:             * direct links.
1021:             */
1022:            public TransitiveGraphCache deepCopy() {
1023:                TransitiveGraphCache copy = new TransitiveGraphCache(
1024:                        directPredicate, closedPredicate);
1025:                Iterator i = find(new TriplePattern(null, directPredicate, null));
1026:                while (i.hasNext()) {
1027:                    Triple t = (Triple) i.next();
1028:                    copy.addRelation(t.getSubject(), t.getObject());
1029:                }
1030:                return copy;
1031:            }
1032:
1033:            /**
1034:             * Clear the entire cache contents. 
1035:             */
1036:            public void clear() {
1037:                nodeMap.clear();
1038:            }
1039:
1040:            /**
1041:             * Enable/disabling caching of the Triples representing the relationships. If this is
1042:             * enabled then a number of triples quadratic in the graph depth will be stored. If it
1043:             * is disabled then all queries will turn over storage dynamically creating the result triples.
1044:             */
1045:            public void setCaching(boolean enable) {
1046:                if (!enable && cacheTriples) {
1047:                    // Switching off so clear the existing cache
1048:                    for (Iterator i = nodeMap.values().iterator(); i.hasNext();) {
1049:                        ((GraphNode) i.next()).clearTripleCache();
1050:                    }
1051:                }
1052:                cacheTriples = enable;
1053:            }
1054:
1055:            /**
1056:             * Dump a description of the cache to a string for debug.
1057:             */
1058:            public String dump() {
1059:                StringBuffer sb = new StringBuffer();
1060:                for (Iterator i = nodeMap.values().iterator(); i.hasNext();) {
1061:                    GraphNode n = (GraphNode) i.next();
1062:                    sb.append(n.dump());
1063:                    sb.append("\n");
1064:                }
1065:                return sb.toString();
1066:            }
1067:
1068:            //  ----------------------------------------------------------------------
1069:            //  Internal utility methods    
1070:            //  ----------------------------------------------------------------------
1071:
1072:            /**
1073:             * Return the lead node of the strongly connected component corresponding
1074:             * to the given RDF node. 
1075:             */
1076:            private GraphNode getLead(Node n) {
1077:                GraphNode gn = (GraphNode) nodeMap.get(n);
1078:                if (gn == null) {
1079:                    gn = new GraphNode(n);
1080:                    nodeMap.put(n, gn);
1081:                    return gn;
1082:                } else {
1083:                    return gn.leadNode();
1084:                }
1085:            }
1086:
1087:        }
1088:
1089:        /*
1090:         (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
1091:         All rights reserved.
1092:
1093:         Redistribution and use in source and binary forms, with or without
1094:         modification, are permitted provided that the following conditions
1095:         are met:
1096:
1097:         1. Redistributions of source code must retain the above copyright
1098:         notice, this list of conditions and the following disclaimer.
1099:
1100:         2. Redistributions in binary form must reproduce the above copyright
1101:         notice, this list of conditions and the following disclaimer in the
1102:         documentation and/or other materials provided with the distribution.
1103:
1104:         3. The name of the author may not be used to endorse or promote products
1105:         derived from this software without specific prior written permission.
1106:
1107:         THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1108:         IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1109:         OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1110:         IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1111:         INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1112:         NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1113:         DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1114:         THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1115:         (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1116:         THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1117:         */
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.