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