Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

com.hp.hpl.jena.graph.impl
Class GraphMatcher  view GraphMatcher download GraphMatcher.java

java.lang.Object
  extended bycom.hp.hpl.jena.graph.impl.GraphMatcher

public class GraphMatcher
extends java.lang.Object

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.

Version:
Release='$Name: $' Revision='$Revision: 1.9 $' Date='$Date: 2005/02/21 11:52:10 $'

Nested Class Summary
private  class GraphMatcher.AnonResource
           
private  class GraphMatcher.AnonStatement
           
private  class GraphMatcher.Bucket
           
private static class GraphMatcher.FixedResource
           
private static interface GraphMatcher.SomeResource
           
 
Field Summary
private  java.util.Map anonLookup
           
private  java.util.Set boundAnonResources
           
private static int col
           
private static int HASH_BAD
           
private static int HASH_OK
           
private static boolean lastDir
           
private  com.hp.hpl.jena.graph.Graph m
           
private static int MAX_HASH_DEPTH
           
private  int myHashLevel
           
private static int NOVARS
           
private static int O
           
private static int OD
           
private  GraphMatcher other
           
private static int OX
           
private static int P
           
private static int PD
           
private static int PX
           
private static int PXOX
           
private static int PXOY
           
private static java.util.Random random
           
private  boolean refinableHash
           
private static int REHASHING
           
private static int S
           
private static int SD
           
private  int state
           
private static int SX
           
private static int SXOX
           
private static int SXOY
           
private static int SXPX
           
private static int SXPXOX
           
private static int SXPXOY
           
private static int SXPY
           
private static int SXPYOX
           
private static int SXPYOY
           
private static int SXPYOZ
           
private  java.util.Map table
           
private static boolean TRACE
           
private  java.util.Set unboundAnonResources
           
 
Constructor Summary
private GraphMatcher(com.hp.hpl.jena.graph.Graph m1x)
           
 
Method Summary
private  boolean bind()
           
private  void check(int s)
           
private  GraphMatcher.SomeResource convert(com.hp.hpl.jena.graph.Node n)
           
(package private) static void count(java.util.Map bag, GraphMatcher.SomeResource r, int pos)
           
static boolean equals(com.hp.hpl.jena.graph.Graph m1, com.hp.hpl.jena.graph.Graph m2)
          Are the two models isomorphic? The isomorphism is defined as a bijection between the anonymous variables such that the statements are identical.
static int hashCode(com.hp.hpl.jena.graph.Graph g)
           
private static void impossible()
           
private  void in(int s)
           
private static boolean legalPattern(int mask)
           
static com.hp.hpl.jena.graph.Node[][] match(com.hp.hpl.jena.graph.Graph m1, com.hp.hpl.jena.graph.Graph m2)
          Return an isomorphism between the two models.
private  com.hp.hpl.jena.graph.Node[][] match(GraphMatcher oth)
           
private  GraphMatcher.Bucket matchBucket(GraphMatcher.Bucket key)
           
private  java.util.Set obligBindings()
           
private  int prepare(com.hp.hpl.jena.graph.Graph otherm)
           
private  int rehash(int lvl)
           
private  int rehash0(int level)
           
private  java.util.Iterator scanBuckets()
           
private  GraphMatcher.Bucket smallestBucket()
           
private static void trace(boolean dir, java.lang.String s)
           
private static void traceNL()
           
private  void unbindAll(java.util.Set s)
           
private static int varPosInPattern(int i, int pattern)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

random

private static java.util.Random random

TRACE

private static final boolean TRACE
See Also:
Constant Field Values

m

private com.hp.hpl.jena.graph.Graph m

other

private GraphMatcher other

myHashLevel

private int myHashLevel

MAX_HASH_DEPTH

private static final int MAX_HASH_DEPTH
See Also:
Constant Field Values

table

private java.util.Map table

state

private int state

REHASHING

private static final int REHASHING
See Also:
Constant Field Values

HASH_OK

private static final int HASH_OK
See Also:
Constant Field Values

HASH_BAD

private static final int HASH_BAD
See Also:
Constant Field Values

unboundAnonResources

private java.util.Set unboundAnonResources

boundAnonResources

private java.util.Set boundAnonResources

refinableHash

private boolean refinableHash

NOVARS

private static final int NOVARS
See Also:
Constant Field Values

SX

private static final int SX
See Also:
Constant Field Values

PX

private static final int PX
See Also:
Constant Field Values

OX

private static final int OX
See Also:
Constant Field Values

SD

private static final int SD
See Also:
Constant Field Values

PD

private static final int PD
See Also:
Constant Field Values

OD

private static final int OD
See Also:
Constant Field Values

SXPY

private static final int SXPY
See Also:
Constant Field Values

SXOY

private static final int SXOY
See Also:
Constant Field Values

PXOY

private static final int PXOY
See Also:
Constant Field Values

SXPYOZ

private static final int SXPYOZ
See Also:
Constant Field Values

SXPX

private static final int SXPX
See Also:
Constant Field Values

SXOX

private static final int SXOX
See Also:
Constant Field Values

PXOX

private static final int PXOX
See Also:
Constant Field Values

SXPXOY

private static final int SXPXOY
See Also:
Constant Field Values

SXPYOX

private static final int SXPYOX
See Also:
Constant Field Values

SXPYOY

private static final int SXPYOY
See Also:
Constant Field Values

SXPXOX

private static final int SXPXOX
See Also:
Constant Field Values

S

private static final int S
See Also:
Constant Field Values

P

private static final int P
See Also:
Constant Field Values

O

private static final int O
See Also:
Constant Field Values

anonLookup

private java.util.Map anonLookup

col

private static int col

lastDir

private static boolean lastDir
Constructor Detail

GraphMatcher

private GraphMatcher(com.hp.hpl.jena.graph.Graph m1x)
Method Detail

equals

public static boolean equals(com.hp.hpl.jena.graph.Graph m1,
                             com.hp.hpl.jena.graph.Graph m2)
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 http://www.w3.org/TR/rdf-concepts#section-Graph-syntax


hashCode

public static int hashCode(com.hp.hpl.jena.graph.Graph g)

match

public static com.hp.hpl.jena.graph.Node[][] match(com.hp.hpl.jena.graph.Graph m1,
                                                   com.hp.hpl.jena.graph.Graph m2)
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.


match

private com.hp.hpl.jena.graph.Node[][] match(GraphMatcher oth)

bind

private boolean bind()

obligBindings

private java.util.Set obligBindings()

scanBuckets

private java.util.Iterator scanBuckets()

unbindAll

private void unbindAll(java.util.Set s)

prepare

private int prepare(com.hp.hpl.jena.graph.Graph otherm)

smallestBucket

private GraphMatcher.Bucket smallestBucket()

matchBucket

private GraphMatcher.Bucket matchBucket(GraphMatcher.Bucket key)

rehash

private int rehash(int lvl)

rehash0

private int rehash0(int level)

legalPattern

private static boolean legalPattern(int mask)

varPosInPattern

private static int varPosInPattern(int i,
                                   int pattern)

count

static void count(java.util.Map bag,
                  GraphMatcher.SomeResource r,
                  int pos)

convert

private GraphMatcher.SomeResource convert(com.hp.hpl.jena.graph.Node n)

check

private void check(int s)

in

private void in(int s)

impossible

private static void impossible()

trace

private static void trace(boolean dir,
                          java.lang.String s)

traceNL

private static void traceNL()