transitivegraphcache.java

Jena推理机

/******************************************************************
 * File:        TransitiveGraphCacheNew.java
 * Created by:  Dave Reynolds
 * Created on:  16-Nov-2004
 * 
 * (c) Copyright 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
 * [See end of file]
 * $Id: TransitiveGraphCache.java,v 1.23 2007/01/11 15:51:05 der Exp $
 *****************************************************************/

package com.hp.hpl.jena.reasoner.transitiveReasoner;

import com.hp.hpl.jena.graph.*;
import com.hp.hpl.jena.util.iterator.*;
import com.hp.hpl.jena.reasoner.*;

import java.util.*;

/**
 * Datastructure used to represent a closed transitive reflexive relation.
 * It (mostly) incrementally maintains a transitive reduction and transitive
 * closure of the relationship and so queries should be faster than dynamically 
 * computing the closed or reduced relations.
 * <p>
 * The implementation stores the reduced and closed relations as real graph
 * (objects linked together by pointers). For each graph node we store its direct
 * predecessors and successors and its closed successors.  A cost penalty 
 * is the storage turnover involved in turning the graph representation back into 
 * triples to answer queries. We could avoid this by optionally also storing the
 * manifested triples for the links.
 * </p><p>
 * Cycles are currently handled by collapsing strongly connected components.
 * Incremental deletes would be possible but at the price of substanially 
 * more storage and code complexity. We compromise by doing the easy cases
 * incrementally but some deletes (those that break strongly connected components)
 * will trigger a fresh rebuild.
 * </p><p>
 * TODO Combine this with interval indexes (Agrawal, Borigda and Jagadish 1989) 
 * for storing the closure of the predecessor relationship. Typical graphs
 * will be nearly tree shaped so the successor closure is modest (L^2 where
 * L is the depth of the tree branch) but the predecessor closure would be 
 * expensive. The interval index would handle predecessor closure nicely.
 * </p>
 * @author <a href="mailto:[e-mail]">Dave Reynolds</a>
 * @version $Revision: 1.23 $
 */

// Note to maintainers. The GraphNode object is treated as a record structure
// rather than an abstract datatype by the rest of the GraphCache code - which
// directly access its structure. I justify this on the flimsy grounds that it is a
// private inner class.

public class TransitiveGraphCache implements Finder {

	/** Flag controlling the whether the triples 
	 *  representing the closed relation should also be cached. */
	protected boolean cacheTriples = false;
	
    /** Map from RDF Node to the corresponding Graph node. */
    protected HashMap nodeMap = new HashMap();
    
    /** The RDF predicate representing the direct relation */
    protected Node directPredicate;
    
    /** The RDF predicate representing the closed relation */
    protected Node closedPredicate;
	
    /** A list of pending deletes which break the cycle-free normal form */
    protected Set deletesPending;
    
	/** The original triples, needed for processing delete operations
	 * because some information is lost in the SCC process */ 
	protected Set originalTriples = new HashSet();
	
    /**
     * Inner class used to represent vistors than can be applied to each
     * node in a graph walk. 
     */
    static interface Visitor {
        // The visitor must not delete and pred entries to avoid CME
        // If this is needed return a non-null result which is a list of pred nodes to kill
    	List visit(GraphNode node, GraphNode processing, Object arg1, Object arg2);
    }
    
	/**
	 * Inner class used to represent the graph node structure.
	 * Rather fat nodes (four sets)
	 */
	private static class GraphNode {
        /** The RDF Graph Node this corresponds to */
        protected Node rdfNode;
        
		/** The list of direct successor nodes to this node */
		protected Set succ = new HashSet();
		
		/** The list of direct predecessors nodes */
		protected Set pred = new HashSet();
		
		/** The set of all transitive successor nodes to this node */
		protected Set succClosed = new HashSet();
		
		/** An optional cache of the triples that represent succClosed */
		protected List succClosedTriples;
		
		/** Null for simple nodes. For the lead node in a SCC will be a list
		 * of all the nodes in the SCC. For non-lead nodes it will be a ref to the lead node. */
		protected Object aliases;

        /**
         * Constructor.
         */
        public GraphNode(Node node) {
            rdfNode = node;
        }
        
        /**
         * Return true if there is a path from this node to the argument node.
         */
        public boolean pathTo(GraphNode A) {
            if (this == A) return true;
            return succClosed.contains(A);
        }

        /**
         * Return true if there is a direct path from this node to the argument node.
         */
        public boolean directPathTo(GraphNode A) {
            if (this == A) return true;
            return succ.contains(A);
        }
		
		/**
		 * Return the lead node in the strongly connected component containing this node.
		 * It will be the node itself if it is a singleton or the lead node. 
		 */
		public GraphNode leadNode() {
			if (aliases != null && aliases instanceof GraphNode) {
				return ((GraphNode)aliases).leadNode();
			} else {
				return this;
			}
		}
		
		/**
		 * Visit each predecessor of this node applying the given visitor.
		 */
		public void visitPredecessors(Visitor visitor, Object arg1, Object arg2) {
            List kill = visitor.visit(this, null, arg1, arg2);
            if (kill != null)  pred.removeAll(kill);
			doVisitPredecessors(visitor, arg1, arg2, new HashSet());
		}
		
		/**
		 * Visit each predecessor of this node applying the given visitor.
         * Breadth first.
		 */
		private void doVisitPredecessors(Visitor visitor, Object arg1, Object arg2, Set seen) {
			if (seen.add(this)) {
                Collection allKill = null;
                for (Iterator i = pred.iterator(); i.hasNext(); ) {
                    GraphNode pred = (GraphNode)i.next();
                    List kill = visitor.visit(pred, this, arg1, arg2);
                    if (kill != null) {
                        if (allKill == null) allKill = new ArrayList();
                        allKill.addAll(kill);
                    }
                }
                if (allKill != null) pred.removeAll(allKill);
                for (Iterator i = pred.iterator(); i.hasNext(); ) {
                    GraphNode pred = (GraphNode)i.next();
                    pred.doVisitPredecessors(visitor, arg1, arg2, seen);
                }
			}
		}
		
		/**
		 * Return an iterator over all the indirect successors of this node.
         * This does NOT include aliases of successors and is used for graph maintenance.
		 */
		public Iterator iteratorOverSuccessors() {
			return succClosed.iterator();
		}
		
		/**
		 * Assert a direct link between this node and this given target.
		 * Does not update the closed successor cache
		 */
		public void assertLinkTo(GraphNode target) {
            if (this == target) return;
			succ.add(target);
			target.pred.add(this);
			clearTripleCache();
		}
		
		/**
		 * Remove a direct link currently from this node to the given target.
		 * Does not update the closed successor cache.
		 */
		public void retractLinkTo(GraphNode target) {
            if (this == target) return;
			succ.remove(target);
			target.pred.remove(this);
			clearTripleCache();
		}
		
		/**
		 * Assert an inferred indirect link from this node to the given traget
		 */
		public void assertIndirectLinkTo(GraphNode target) {
//            if (this == target) return;
			succClosed.add(target);
			clearTripleCache();
		}
		
		/**
		 * Clear the option cache of the closure triples.
		 */
		public void clearTripleCache() {
			succClosedTriples = null;
		}
        
		/**
		 * Propagate the results of adding a link from this
		 * node to the target node.
		 */
		public void propagateAdd(GraphNode target) {
            Set sc = new HashSet(target.succClosed);
            sc.add(target); 
			visitPredecessors(new Visitor() {
				public List visit(GraphNode node, GraphNode processing, Object arg1, Object target) {
					Set sc = (Set)arg1;
					// Add closure
					node.succClosed.addAll(sc);
					// Scan for redundant links
                    List kill = null;
					for (Iterator i = node.succ.iterator(); i.hasNext();) {
						GraphNode s = (GraphNode)i.next();
						if (sc.contains(s)) {
							i.remove();
                            if (s == processing) {
                                // Can't remove immediately w/o beaking the visitor loop
                                if (kill == null) kill = new ArrayList();
                                kill.add(node);
                            } else {
                                s.pred.remove(node);
                            }
						}
					}
                    return kill;
				}
		    }, sc, target);
		}
        
		/**
		 * Propagate the results of creating a new SCC with this
		 * node as lead.
		 */
		public void propagateSCC() {
			Set visited = new HashSet();
			visited.add(this);
			// Scan predecessors not including ourselves
			doVisitPredecessors(new Visitor() {
				public List visit(GraphNode node, GraphNode processing, Object arg1, Object arg2) {
					Set sc = (Set)arg1;
					// Add closure
					node.succClosed.addAll(sc);
					// Scan for redundant links
                    List kill = null;
					for (Iterator i = node.succ.iterator(); i.hasNext();) {
						GraphNode s = (GraphNode)i.next();
						if (sc.contains(s)) {
							i.remove();
//                            s.pred.remove(node);
                            if (s == processing) {
                                // Can't remove immediately w/o beaking the visitor loop
                                if (kill == null) kill = new ArrayList();
                                kill.add(node);
                            } else {
                                s.pred.remove(node);
                            }
						}
					}
                    return kill;
				}
		    }, succClosed, null, visited);
		}
		
        /**
         * Given a set of SCC nodes make this the lead member of the SCC and
         * reroute all incoming and outgoing links accordingly.
         * This eager rewrite is based on the assumption that there are few cycles
         * so it is better to rewrite once and keep the graph easy to traverse.
         */
        public void makeLeadNodeFor(Set members) {
            // Accumulate all successors
            Set newSucc = new HashSet();
            Set newSuccClosed = new HashSet();
            for (Iterator i = members.iterator(); i.hasNext(); ) {
                GraphNode n = (GraphNode)i.next();
                newSucc.addAll(n.succ);
                newSuccClosed.addAll(n.succClosed);
            }
            newSucc.removeAll(members);
            newSuccClosed.removeAll(members);
            succ = newSucc;
            succClosed = newSuccClosed;
            
            // Rewrite all direct successors to have us as predecessor
            for (Iterator i = succ.iterator(); i.hasNext();) {
                GraphNode n = (GraphNode)i.next();
                n.pred.removeAll(members);
                n.pred.add(this);
            }
            
            // Find all predecessor nodes and relink link them to point to us
            Set done = new HashSet();
            Set newAliases = new HashSet();
            for (Iterator i = members.iterator(); i.hasNext(); ) {
            	GraphNode m = (GraphNode)i.next();
            	if (m.aliases instanceof Set) {
            		newAliases.addAll((Set)m.aliases);
            	} else {
            		newAliases.add(m);
            	}
            }
            this.aliases = newAliases;
            for (Iterator i = members.iterator(); i.hasNext(); ) {
                GraphNode n = (GraphNode)i.next();
                if (n != this) {
                    pred.addAll(n.pred);
                    n.relocateAllRefTo(this, done);
                    n.aliases = this;
                }
            }
            pred.removeAll(members);
        }
		
        /**
         * This node is being absorbed into an SCC with the given node as the
         * new lead node. Trace out all predecessors to this node and relocate
         * them to point to the new lead node.
         */
        private void relocateAllRefTo(GraphNode lead, Set done) {
            visitPredecessors(new Visitor(){
                public List visit(GraphNode node, GraphNode processing, Object done, Object leadIn) {
                    if (((Set)done).add(node)) {
                        GraphNode lead = (GraphNode)leadIn;
                        Set members = (Set)lead.aliases;
                        int before = node.succ.size();
                        node.succ.removeAll(members);
                        node.succClosed.removeAll(members);
                        node.succClosed.add(lead);
                        if (node.succ.size() != before) {
                            node.succ.add(lead);
                        }