graphmatcher.java

Jena推理机

/*
 *  (c) Copyright 2002, 2002, 2003, 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
 *  
 *  All rights reserved.
 * 
 * See end of file.
 */
 

package com.hp.hpl.jena.graph.impl;
import java.util.*;

import com.hp.hpl.jena.graph.*;
import com.hp.hpl.jena.util.CollectionFactory;
import com.hp.hpl.jena.util.iterator.*;
import com.hp.hpl.jena.shared.*;

/**
 * An implemantation of graph isomorphism for Graph equality.
 * The underlying algorithm is exponential but will only enter
 * a non-deterministic polynomial part when there are a lot of difficult to
 * distinguish anonymous nodes
 * connected to each other by statements with the same property(s).
 * Non-pathological examples, where most nodes have some properties that
 * help distinguish them from other nodes, will experience nearly linear
 * performance.
 *<p>
 * @author  jjc
 * @version  Release='$Name:  $' Revision='$Revision: 1.15 $' Date='$Date: 2007/01/02 11:48:28 $'
 */
public class GraphMatcher extends java.lang.Object {
    static private Random random = new Random(0);
 /**
 * Are the two models isomorphic?
 * The isomorphism is defined as a bijection between the anonymous
 * variables such that the statements are identical. 
 * This is
	 * described in 
	 * <a href="http://www.w3.org/TR/rdf-concepts#section-Graph-syntax">
     * http://www.w3.org/TR/rdf-concepts#section-Graph-syntax
     * </a>
 */
    static public boolean equals(Graph m1,Graph m2)   {
        if ( m1 == m2 )
            return true;
        return match(m1,m2) != null;
    }  
    
    static public int hashCode(Graph g) {
    	ClosableIterator ci = GraphUtil.findAll( g );
    	int hash = 0;
    	GraphMatcher gm = new GraphMatcher(g);
    	while ( ci.hasNext() ) {
    		Triple t = (Triple)ci.next();
    		hash += gm.new AnonStatement(t).myHashCode(null);
    	}
    	return hash;
    }
/**
 * Return an isomorphism between the two models.
 * This function is nondeterministic in that it may return a 
 * different bijection on each call, in cases where there are 
 * multiple isomorphisms between the models.
 * @return <code>null</code> on failure or an array of related pairs 
           (arrays of length 2) of anonymous nodes.
            <code>match(m1,m2)[i][0]</code>  is from <code>m1</code>, 
            and <code>match(m1,m2)[i][1]</code> is the corresponding node in
            <code>m2</code>.
 */
    static public Node[][] match(Graph m1,Graph m2)  {
            return new GraphMatcher(m1).match(new GraphMatcher(m2));
    }
    /* NOTE: inner classes
     *    We use a number of non-static inner classes, these all
     *    refer to the GraphMatcher for context.
     *
     * NOTE: the built-in hashCode() is not modified, so that Set's etc
     * still work.
     * This algorithm depends on a hash function, which I call myHashCode()
     * This has the somewhat perplexing property of changing as we do
     * the binding.
     * obj.myHashCode() depends on:
     *    -  obj and it's non anonymous subcomponents
     *    - ModelMatcher.myHashLevel (in the enclosing ModelMatcher)
     *    - for a bound AnonResource b in obj, it depends on a
     *      random value generated at the time that b got bound
     *    - for an unbound AnonResource, if myHashLevel>0, then
     *      it depends on the value of myHashCode() at myHashLevel-1
     *
     *
     *
     */
    static final private boolean TRACE = false;
    private Graph m;
    private GraphMatcher other;
    private int myHashLevel = 0; // This is usually 0, but can be any value
    // less than MAX_HASH_DEPTH
    
    
    static final private int MAX_HASH_DEPTH = 3;
    // I don't think there's much
    // mileage in a huge number here
    // A large number is likely to be unhelpful in typical
    // cases, but helps in pathological cases.
    // The pathological cases are the slowest, so perhaps it
    // is best to optimise for them.!
    
    // The rehashable - hash table
    // A Map from Integer => Bucket
    // Most of the time the table is a mess,
    // this is reflected in state=BAD
    private Map table;
    
    // This variable is mainly for sanity checking and
    // documentation. It has one logical impact in
    // AnonResource.myHashCodeFromStatement() and
    // AnonResource.wrapStatements()
    // AnonResource.myHashCodeFromStatement() requires
    // either state != HASH_BAD or myHashLevel = 0,
    // we ensure that one or other is the case in
    // AnonResource.wrapStatements().
    private int state;
    static final private int REHASHING = 1;
    static final private int HASH_OK = 2;
    static final private int HASH_BAD = 4;
    
    // As the algorithm proceeds we move resources
    // from one to the other.
    // At completion unBoundAnonResources is empty.
    private Set unboundAnonResources = CollectionFactory.createHashedSet();
    private Set boundAnonResources = CollectionFactory.createHashedSet();
    
    
    
    private GraphMatcher(Graph m1x) {
        m = m1x;
    }
    private Node[][] match(GraphMatcher oth) {
        other = oth;
        oth.other = this;
        in(HASH_BAD);
        
        // check that the size's are the same.
        // If the size is not accurate then it is a lower bound
        
        if (m.getCapabilities().sizeAccurate()
                && m.size() < other.m.size() )
            return null;
        if (other.m.getCapabilities().sizeAccurate()
                && m.size() > other.m.size() )
            return null;
        int myPrep = prepare(other.m);
        if ( myPrep == -1 || myPrep != other.prepare(m) ) {
            return null;
        }
        if ( bind() ) {
            if ( !unboundAnonResources.isEmpty() )
                impossible();
            Node rslt[][] = new Node[boundAnonResources.size()][];
            int ix = 0;
            Iterator it = boundAnonResources.iterator();
            while ( it.hasNext() ) {
                AnonResource r = (AnonResource)it.next();
                rslt[ix++] = new Node[]{r.r,r.bound.r};
            }
            return rslt;
        }
        else {
            return null;
        }
    }
    // bind returns true if we have a binding,
    // false if not, in either case table is screwed.
    private boolean bind()   {
        Set locallyBound = obligBindings();
        if (locallyBound==null)  // Contradiction reached - fail.
            return false;
        check(HASH_OK);
        Bucket bkt = smallestBucket();
        if ( bkt == null )
            return true;  // No smallest bucket - we are finished.
        Bucket otherBkt = other.matchBucket(bkt);
        if ( otherBkt != null ) {
            AnonResource v = bkt.aMember();
            Iterator candidates = otherBkt.members();
            // System.out.println("Guessing");
            while ( candidates.hasNext() ) {
                check(HASH_OK|HASH_BAD);
                AnonResource otherV = (AnonResource)candidates.next();
                trace(true,"Guess: ");
                if (!bkt.bind(v,otherBkt,otherV))
                    continue;
                if (bind())
                    return true;
                v.unbind();
            }
        }
        unbindAll(locallyBound);
        return false;
    }
    /*
     * Called with hashing incorrect.
     * Returns null if situation is unworkable.
     * Returns non-null with no outstanding obvious bindings,
     * and with the hashing correct.
     * The set of obligatorily bound resources is returned.
     *
     */
    private Set obligBindings() {
        int hashLevel = 0;
        boolean newBinding;
        Set rslt = CollectionFactory.createHashedSet();
        check(HASH_OK|HASH_BAD);
        do {
            if ( rehash(hashLevel) != other.rehash(hashLevel) ){
                unbindAll(rslt);
                return null;
            }
            refinableHash = false;
            newBinding = false;
            Iterator singles = scanBuckets();
            while ( singles.hasNext() ) {
                newBinding = true;
                Bucket bkt = (Bucket)singles.next();
                Bucket otherBkt = other.matchBucket(bkt);
                if ( otherBkt == null ) {
                    unbindAll(rslt);
                    return null;
                }
                AnonResource bindMe = bkt.aMember();
                if (!bkt.bind(otherBkt)) {
                    unbindAll(rslt);
                    return null;
                }
                rslt.add(bindMe);
            }
            if ( newBinding )
                hashLevel = 0;
            else
                hashLevel++;
        } while (hashLevel<MAX_HASH_DEPTH && (refinableHash||newBinding));
        return rslt;
    }
    // Communication between obligBindings and scanBuckets
    private boolean refinableHash;
    private Iterator scanBuckets() {
        // Looks through buckets,
        // if has single member then return in iterator.
        // Otherwise if some member of the bucket has friends
        // we can refine the hash, and we set refinableHash.
        check(HASH_OK);
        return new FilterIterator(
        new Filter() {
            public boolean accept(Object o) {
                Bucket b = (Bucket)o;
                if (b.size()==1)
                    return true;
                if (!refinableHash) {
                    Iterator it = b.members();
                    while ( it.hasNext() )
                        if (!((AnonResource)it.next())
                        .friends.isEmpty()) {
                            refinableHash = true;
                            break;
                        }
                }
                return false;
            }
        },table.values().iterator());
        
    }
    private void unbindAll(Set s)  {
        Iterator rs = s.iterator();
        while (rs.hasNext())
            ((AnonResource)rs.next()).unbind();
        in(HASH_BAD);
    }
    private int prepare(Graph otherm)  {
        ClosableIterator ss = GraphUtil.findAll( m );
        myHashLevel = 0;
        int hash = 0;
        try {
            while ( ss.hasNext() ) {
                Triple s = (Triple)ss.next();
                AnonStatement ass = new AnonStatement(s);
                if ( ass.pattern == NOVARS ) {
                    if ( !otherm.contains( s ) ) return -1;
                } else {
                    hash += ass.myHashCode(ass.vars[0]);
                    for (int i=0;i<ass.vars.length;i++) {
                        ass.vars[i].occursIn.add(ass);
                        for (int j=i+1;j<ass.vars.length;j++) {
                            ass.vars[i].friends.add(ass.vars[j]);
                            ass.vars[j].friends.add(ass.vars[i]);
                        }
                    }
                }
            }
            return hash==-1?1:hash;
        }
        finally {
            ss.close();
        }
    }
    private Bucket smallestBucket() {
        check(HASH_OK);
        Iterator bit = table.values().iterator();
        Bucket smallB = null;
        int smallest = Integer.MAX_VALUE;
        while ( bit.hasNext() ) {
            Bucket b = (Bucket)bit.next();
            int sz = b.size();
            if ( sz < smallest ) {
                smallB = b;
                smallest = sz;
            }