transitivegraphcache.java

Jena推理机

                    }
                    return null;
                }
            }, done, lead);
        }
        
        /**
         * Return an iterator over all of the triples representing outgoing links
         * from this node.  
         * @param closed if set to true it returns triples in the transitive closure,
         * if set to false it returns triples in the transitive reduction
         * @param cache the enclosing TransitiveGraphCache
         */
        public ExtendedIterator listTriples(boolean closed, TransitiveGraphCache tgc) {
            if (tgc.cacheTriples) {
                // TODO implement - for now default to non-cached
                return WrappedIterator.create(leadNode().triplesForSuccessors(rdfNode, closed, tgc).iterator());
            } else {
                return WrappedIterator.create(leadNode().triplesForSuccessors(rdfNode, closed, tgc).iterator());
            }
        }
        
        /**
         * Create a list of triples for a given set of successors to this node.
         */
        private List triplesForSuccessors(Node base, boolean closed, TransitiveGraphCache tgc) {
            Set successors = closed ? succClosed : succ;
            ArrayList result = new ArrayList(successors.size() + 10);
            result.add(new Triple(base, tgc.closedPredicate, base));    // implicit reflexive case 
            for (Iterator i = successors.iterator(); i.hasNext(); ) {
                GraphNode s = (GraphNode)i.next();
                result.add(new Triple(base, tgc.closedPredicate, s.rdfNode));
                if (s.aliases instanceof Set) {
                    for (Iterator j = ((Set)s.aliases).iterator(); j.hasNext(); ) {
                        result.add(new Triple(base, tgc.closedPredicate, ((GraphNode)j.next()).rdfNode));
                    }
                }
            }
            if (aliases instanceof Set) {
                for (Iterator j = ((Set)aliases).iterator(); j.hasNext(); ) {
                    result.add(new Triple(base, tgc.closedPredicate, ((GraphNode)j.next()).rdfNode));
                }
            }
            return result;
        }
        
        /**
         * Return an iterator over all of the triples representing incoming links to this node.
         * Currently no caching enabled.
         */
        public ExtendedIterator listPredecessorTriples(boolean closed, TransitiveGraphCache tgc) {
            return new GraphWalker(leadNode(), rdfNode, closed, tgc.closedPredicate);
        }
        
        /**
         * Print node label to assist with debug.
         */
        public String toString() {
            return "[" + rdfNode.getLocalName() + "]";
        }
        
        /**
         * Full dump for debugging
         */
        public String dump() {
        	String result = rdfNode.getLocalName();
        	if (aliases != null) {
        		if (aliases instanceof GraphNode) {
        			result = result + " leader=" + aliases + ", ";
        		} else {
        			result = result + " SCC=" + dumpSet((Set)aliases) +", ";
        		}
        	}
        	return result + " succ=" + dumpSet(succ) + ", succClose=" + dumpSet(succClosed) + ", pred=" + dumpSet(pred);
        }
        
        /**
         * Dump a set to a string for debug.
         */
        private String dumpSet(Set s) {
        	StringBuffer sb = new StringBuffer();
        	sb.append("{");
        	boolean started = false;
        	for (Iterator i = s.iterator(); i.hasNext(); ) {
        		if (started) {
        			sb.append(", ");
        		} else {
        			started = true;
        		}
        		sb.append(i.next().toString());
        	}
        	sb.append("}");
        	return sb.toString();
        }
        
	} // End of GraphNode inner class
	
    /**
     * Inner class used to walk backward links of the graph.
     * <p> The triples are dynamically allocated which is costly. 
     */
    private static class GraphWalker extends NiceIterator implements ExtendedIterator {
        
        /** Indicate if this is a shallow or deep walk */
        boolean isDeep;
        
        /** The current node being visited */
        GraphNode node;
        
        /** The root node for reconstructing triples */
        Node root;
        
        /** The predicate for reconstructing triples */
        Node predicate; 
        
        /** Iterator over the predecessors to the current node bein walked */
        Iterator iterator = null;
        
        /** Iterator over the aliases of the current predecessor being output */
        Iterator aliasIterator = null;
        
        /** stack of graph nodes being walked */
        ArrayList nodeStack = new ArrayList();
        
        /** stack of iterators for the higher nodes in the walk */
        ArrayList iteratorStack = new ArrayList();
        
        /** The next value to be returned */
        Triple next;
        
        /** The set of junction nodes already visited */
        HashSet visited = new HashSet();
        
        /** 
         * Constructor. Creates an iterator which will walk
         * the graph, returning triples.
         * @param node the starting node for the walk
         * @param rdfNode the rdfNode we are try to find predecessors for
         * @param closed set to true of walking the whole transitive closure
         * @param predicate the predicate to be walked
         */
        GraphWalker(GraphNode node, Node rdfNode, boolean closed, Node predicate) {
            isDeep = closed;
            this.node = node;
            this.root = rdfNode;
            this.predicate = predicate;
            this.iterator = node.pred.iterator();
            if (node.aliases instanceof Set) {
                aliasIterator = ((Set)node.aliases).iterator();
            }
            next = new Triple(root, predicate, root);   // implicit reflexive case 
        }
        
        /** Iterator interface - test if more values available */
        public boolean hasNext() {
            return next != null;
        }
        
        /** Iterator interface - get next value */
        public Object next() {
            Object toReturn = next;
            walkOne();
            return toReturn;
        }
                
        /**
         * Walk one step
         */
        protected void walkOne() {
            if (aliasIterator != null) {
                if (aliasIterator.hasNext()) {
                    GraphNode nextNode = (GraphNode)aliasIterator.next();
                    next =  new Triple(nextNode.rdfNode, predicate, root);
                    return;
                } else {
                    aliasIterator = null;
                }
            }
            if (iterator.hasNext()) {
                GraphNode nextNode = (GraphNode)iterator.next();
                if (visited.add(nextNode)) {
                    // Set up for depth-first visit next
                    if (isDeep)
                        pushStack(nextNode);
                    next =  new Triple(nextNode.rdfNode, predicate, root);
                    if (nextNode.aliases instanceof Set) {
                        aliasIterator = ((Set)nextNode.aliases).iterator();
                    }
                } else { 
                    // Already visited this junction, skip it
                    walkOne();
                    return;
                }
            } else {
                // Finished this node
                if (nodeStack.isEmpty()) {
                    next = null;
                    return;
                }
                popStack();
                walkOne();
            }
        }
        
        /**
         * Push the current state onto the stack
         */
        protected void pushStack(GraphNode next) {
            nodeStack.add(node);
            iteratorStack.add(iterator);
            iterator = next.pred.iterator();
            node = next;
        }
        
        /**
         * Pop the prior state back onto the stack
         */
        protected void popStack() {
            int i = nodeStack.size()-1;
            iterator = (Iterator) iteratorStack.remove(i);
            node = (GraphNode) nodeStack.remove(i);
        }
        
    } // End of GraphWalker inner class    
    
    /**
     * Inner class used to do a complete walk over the graph
     */
    private static class FullGraphWalker extends NiceIterator implements ExtendedIterator {

        /** Flag whether we are walking over the closed or direct relations */
        boolean closed;
        
        /** Iterator over the start nodes in the node map */
        Iterator baseNodeIt;
        
        /** The current node being visited */
        GraphNode node;
        
        /** The root node for reconstructing triples */
        Node nodeN;
        
        /** The predicate for reconstructing triples */
        Node predicate; 
        
        /** Iterator over the successor nodes for the baseNode */
        Iterator succIt = null;
        
        /** The current successor being processed */
        GraphNode succ;
        
        /** Iterator over the aliases for the current successor */
        Iterator aliasesIt = null;
        
        /** The next value to be returned */
        Triple next;
        
        /** Construct a walker for the full closed or direct graph */
        FullGraphWalker(boolean closed, Node predicate, HashMap nodes) {
            this.predicate = predicate;
            this.closed = closed;
            baseNodeIt = nodes.values().iterator();
            walkOne();
        }
        
        /** Iterator interface - test if more values available */
        public boolean hasNext() {
            return next != null;
        }
        
        /** Iterator interface - get next value */
        public Object next() {
            Object toReturn = next;
            walkOne();
            return toReturn;
        }
                
        /**
         * Walk one step
         */
        protected void walkOne() {
            if (aliasesIt != null) {
                while (aliasesIt.hasNext()) {
                    GraphNode al = (GraphNode)aliasesIt.next();
                    if (al != succ && al != node) {
                        next = new Triple(nodeN, predicate, al.rdfNode);
                        return;
                    }
                }
                aliasesIt = null;      // End of aliases
            }
            
            if (succIt != null) {
                while (succIt.hasNext()) {
                    succ = (GraphNode)succIt.next();
                    if (succ == node) continue; // Skip accidental reflexive cases, already done
                    if (succ.aliases instanceof Set) {
                        aliasesIt = ((Set)succ.aliases).iterator();
                    }
                    next = new Triple(nodeN, predicate, succ.rdfNode);
                    return;
                }
                succIt = null;      // End of the successors
            }
            
            if (baseNodeIt.hasNext()) {
                node = (GraphNode)baseNodeIt.next();
                nodeN = node.rdfNode;
                GraphNode lead = node.leadNode();
                succIt = (closed ? lead.succClosed : lead.succ).iterator();
                if (lead.aliases instanceof Set) {
                    succIt = new ConcatenatedIterator(succIt, ((Set)lead.aliases).iterator());
                }
                next = new Triple(nodeN, predicate, nodeN); // Implicit reflexive case
            } else {
                next = null; // End of walk
            }
        }
        
    } // End of FullGraphWalker inner class
    
    /**
     * Constructor - create a new cache to hold the given relation information.
     * @param directPredicate The RDF predicate representing the direct relation
     * @param closedPredicate The RDF predicate representing the closed relation
     */
    public TransitiveGraphCache(Node directPredicate, Node closedPredicate) {
        this.directPredicate = directPredicate;
        this.closedPredicate = closedPredicate;
    }
    
    /**
     * Returns the closedPredicate.
     * @return Node
     */
    public Node getClosedPredicate() {
        return closedPredicate;
    }

    /**
     * Returns the directPredicate.
     * @return Node
     */
    public Node getDirectPredicate() {
        return directPredicate;
    }
     
    /**
     * Register a new relation instance in the cache
     */
    public synchronized void addRelation(Triple t) {
    	originalTriples.add(t);
    	addRelation(t.getSubject(), t.getObject());
    }