0001: /*
0002: * (c) Copyright 2002, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
0003: *
0004: * All rights reserved.
0005: *
0006: * See end of file.
0007: */
0008:
0009: package com.hp.hpl.jena.graph.impl;
0010:
0011: import java.util.*;
0012:
0013: import com.hp.hpl.jena.graph.*;
0014: import com.hp.hpl.jena.util.CollectionFactory;
0015: import com.hp.hpl.jena.util.iterator.*;
0016: import com.hp.hpl.jena.shared.*;
0017:
0018: // Purely syntactic: Uses .equals, not .sameVAlueAs (see the one note at "PURE SYNTAX" below)
0019:
0020: /**
0021: * An implemantation of graph isomorphism for Graph equality.
0022: * The underlying algorithm is exponential but will only enter
0023: * a non-deterministic polynomial part when there are a lot of difficult to
0024: * distinguish anonymous nodes
0025: * connected to each other by statements with the same property(s).
0026: * Non-pathological examples, where most nodes have some properties that
0027: * help distinguish them from other nodes, will experience nearly linear
0028: * performance.
0029: *<p>
0030: * @author jjc
0031: * @version Release='$Name: $' Revision='$Revision: 1.18 $' Date='$Date: 2008/01/02 12:05:16 $'
0032: */
0033: public class GraphMatcher extends java.lang.Object {
0034: static private Random random = new Random(0);
0035:
0036: /**
0037: * Are the two models isomorphic?
0038: * The isomorphism is defined as a bijection between the anonymous
0039: * variables such that the statements are identical.
0040: * This is
0041: * described in
0042: * <a href="http://www.w3.org/TR/rdf-concepts#section-Graph-syntax">
0043: * http://www.w3.org/TR/rdf-concepts#section-Graph-syntax
0044: * </a>
0045: */
0046: static public boolean equals(Graph m1, Graph m2) {
0047: if (m1 == m2)
0048: return true;
0049: return match(m1, m2) != null;
0050: }
0051:
0052: static public int hashCode(Graph g) {
0053: ClosableIterator ci = GraphUtil.findAll(g);
0054: int hash = 0;
0055: GraphMatcher gm = new GraphMatcher(g);
0056: while (ci.hasNext()) {
0057: Triple t = (Triple) ci.next();
0058: hash += gm.new AnonStatement(t).myHashCode(null);
0059: }
0060: return hash;
0061: }
0062:
0063: /**
0064: * Return an isomorphism between the two models.
0065: * This function is nondeterministic in that it may return a
0066: * different bijection on each call, in cases where there are
0067: * multiple isomorphisms between the models.
0068: * @return <code>null</code> on failure or an array of related pairs
0069: (arrays of length 2) of anonymous nodes.
0070: <code>match(m1,m2)[i][0]</code> is from <code>m1</code>,
0071: and <code>match(m1,m2)[i][1]</code> is the corresponding node in
0072: <code>m2</code>.
0073: */
0074: static public Node[][] match(Graph m1, Graph m2) {
0075: return new GraphMatcher(m1).match(new GraphMatcher(m2));
0076: }
0077:
0078: /* NOTE: inner classes
0079: * We use a number of non-static inner classes, these all
0080: * refer to the GraphMatcher for context.
0081: *
0082: * NOTE: the built-in hashCode() is not modified, so that Set's etc
0083: * still work.
0084: * This algorithm depends on a hash function, which I call myHashCode()
0085: * This has the somewhat perplexing property of changing as we do
0086: * the binding.
0087: * obj.myHashCode() depends on:
0088: * - obj and it's non anonymous subcomponents
0089: * - ModelMatcher.myHashLevel (in the enclosing ModelMatcher)
0090: * - for a bound AnonResource b in obj, it depends on a
0091: * random value generated at the time that b got bound
0092: * - for an unbound AnonResource, if myHashLevel>0, then
0093: * it depends on the value of myHashCode() at myHashLevel-1
0094: *
0095: *
0096: *
0097: */
0098: static final private boolean TRACE = false;
0099: private Graph m;
0100: private GraphMatcher other;
0101: private int myHashLevel = 0; // This is usually 0, but can be any value
0102: // less than MAX_HASH_DEPTH
0103:
0104: static final private int MAX_HASH_DEPTH = 3;
0105: // I don't think there's much
0106: // mileage in a huge number here
0107: // A large number is likely to be unhelpful in typical
0108: // cases, but helps in pathological cases.
0109: // The pathological cases are the slowest, so perhaps it
0110: // is best to optimise for them.!
0111:
0112: // The rehashable - hash table
0113: // A Map from Integer => Bucket
0114: // Most of the time the table is a mess,
0115: // this is reflected in state=BAD
0116: private Map table;
0117:
0118: // This variable is mainly for sanity checking and
0119: // documentation. It has one logical impact in
0120: // AnonResource.myHashCodeFromStatement() and
0121: // AnonResource.wrapStatements()
0122: // AnonResource.myHashCodeFromStatement() requires
0123: // either state != HASH_BAD or myHashLevel = 0,
0124: // we ensure that one or other is the case in
0125: // AnonResource.wrapStatements().
0126: private int state;
0127: static final private int REHASHING = 1;
0128: static final private int HASH_OK = 2;
0129: static final private int HASH_BAD = 4;
0130:
0131: // As the algorithm proceeds we move resources
0132: // from one to the other.
0133: // At completion unBoundAnonResources is empty.
0134: private Set unboundAnonResources = CollectionFactory
0135: .createHashedSet();
0136: private Set boundAnonResources = CollectionFactory
0137: .createHashedSet();
0138:
0139: private GraphMatcher(Graph m1x) {
0140: m = m1x;
0141: }
0142:
0143: private Node[][] match(GraphMatcher oth) {
0144: other = oth;
0145: oth.other = this ;
0146: in(HASH_BAD);
0147:
0148: // check that the size's are the same.
0149: // If the size is not accurate then it is a lower bound
0150:
0151: if (m.getCapabilities().sizeAccurate()
0152: && m.size() < other.m.size())
0153: return null;
0154: if (other.m.getCapabilities().sizeAccurate()
0155: && m.size() > other.m.size())
0156: return null;
0157: int myPrep = prepare(other.m);
0158: if (myPrep == -1 || myPrep != other.prepare(m)) {
0159: return null;
0160: }
0161: if (bind()) {
0162: if (!unboundAnonResources.isEmpty())
0163: impossible();
0164: Node rslt[][] = new Node[boundAnonResources.size()][];
0165: int ix = 0;
0166: Iterator it = boundAnonResources.iterator();
0167: while (it.hasNext()) {
0168: AnonResource r = (AnonResource) it.next();
0169: rslt[ix++] = new Node[] { r.r, r.bound.r };
0170: }
0171: return rslt;
0172: } else {
0173: return null;
0174: }
0175: }
0176:
0177: // bind returns true if we have a binding,
0178: // false if not, in either case table is screwed.
0179: private boolean bind() {
0180: Set locallyBound = obligBindings();
0181: if (locallyBound == null) // Contradiction reached - fail.
0182: return false;
0183: check(HASH_OK);
0184: Bucket bkt = smallestBucket();
0185: if (bkt == null)
0186: return true; // No smallest bucket - we are finished.
0187: Bucket otherBkt = other.matchBucket(bkt);
0188: if (otherBkt != null) {
0189: AnonResource v = bkt.aMember();
0190: Iterator candidates = otherBkt.members();
0191: // System.out.println("Guessing");
0192: while (candidates.hasNext()) {
0193: check(HASH_OK | HASH_BAD);
0194: AnonResource otherV = (AnonResource) candidates.next();
0195: trace(true, "Guess: ");
0196: if (!bkt.bind(v, otherBkt, otherV))
0197: continue;
0198: if (bind())
0199: return true;
0200: v.unbind();
0201: }
0202: }
0203: unbindAll(locallyBound);
0204: return false;
0205: }
0206:
0207: /*
0208: * Called with hashing incorrect.
0209: * Returns null if situation is unworkable.
0210: * Returns non-null with no outstanding obvious bindings,
0211: * and with the hashing correct.
0212: * The set of obligatorily bound resources is returned.
0213: *
0214: */
0215: private Set obligBindings() {
0216: int hashLevel = 0;
0217: boolean newBinding;
0218: Set rslt = CollectionFactory.createHashedSet();
0219: check(HASH_OK | HASH_BAD);
0220: do {
0221: if (rehash(hashLevel) != other.rehash(hashLevel)) {
0222: unbindAll(rslt);
0223: return null;
0224: }
0225: refinableHash = false;
0226: newBinding = false;
0227: Iterator singles = scanBuckets();
0228: while (singles.hasNext()) {
0229: newBinding = true;
0230: Bucket bkt = (Bucket) singles.next();
0231: Bucket otherBkt = other.matchBucket(bkt);
0232: if (otherBkt == null) {
0233: unbindAll(rslt);
0234: return null;
0235: }
0236: AnonResource bindMe = bkt.aMember();
0237: if (!bkt.bind(otherBkt)) {
0238: unbindAll(rslt);
0239: return null;
0240: }
0241: rslt.add(bindMe);
0242: }
0243: if (newBinding)
0244: hashLevel = 0;
0245: else
0246: hashLevel++;
0247: } while (hashLevel < MAX_HASH_DEPTH
0248: && (refinableHash || newBinding));
0249: return rslt;
0250: }
0251:
0252: // Communication between obligBindings and scanBuckets
0253: private boolean refinableHash;
0254:
0255: private Iterator scanBuckets() {
0256: // Looks through buckets,
0257: // if has single member then return in iterator.
0258: // Otherwise if some member of the bucket has friends
0259: // we can refine the hash, and we set refinableHash.
0260: check(HASH_OK);
0261: return new FilterIterator(new Filter() {
0262: public boolean accept(Object o) {
0263: Bucket b = (Bucket) o;
0264: if (b.size() == 1)
0265: return true;
0266: if (!refinableHash) {
0267: Iterator it = b.members();
0268: while (it.hasNext())
0269: if (!((AnonResource) it.next()).friends
0270: .isEmpty()) {
0271: refinableHash = true;
0272: break;
0273: }
0274: }
0275: return false;
0276: }
0277: }, table.values().iterator());
0278:
0279: }
0280:
0281: private void unbindAll(Set s) {
0282: Iterator rs = s.iterator();
0283: while (rs.hasNext())
0284: ((AnonResource) rs.next()).unbind();
0285: in(HASH_BAD);
0286: }
0287:
0288: private int prepare(Graph otherm) {
0289: ClosableIterator ss = GraphUtil.findAll(m);
0290: myHashLevel = 0;
0291: int hash = 0;
0292: try {
0293: while (ss.hasNext()) {
0294: Triple s = (Triple) ss.next();
0295: AnonStatement ass = new AnonStatement(s);
0296: if (ass.pattern == NOVARS) {
0297: if (!otherm.contains(s))
0298: return -1;
0299: } else {
0300: hash += ass.myHashCode(ass.vars[0]);
0301: for (int i = 0; i < ass.vars.length; i++) {
0302: ass.vars[i].occursIn.add(ass);
0303: for (int j = i + 1; j < ass.vars.length; j++) {
0304: ass.vars[i].friends.add(ass.vars[j]);
0305: ass.vars[j].friends.add(ass.vars[i]);
0306: }
0307: }
0308: }
0309: }
0310: return hash == -1 ? 1 : hash;
0311: } finally {
0312: ss.close();
0313: }
0314: }
0315:
0316: private Bucket smallestBucket() {
0317: check(HASH_OK);
0318: Iterator bit = table.values().iterator();
0319: Bucket smallB = null;
0320: int smallest = Integer.MAX_VALUE;
0321: while (bit.hasNext()) {
0322: Bucket b = (Bucket) bit.next();
0323: int sz = b.size();
0324: if (sz < smallest) {
0325: smallB = b;
0326: smallest = sz;
0327: }
0328: }
0329: return smallB;
0330: }
0331:
0332: private Bucket matchBucket(Bucket key) {
0333: check(HASH_OK);
0334: Integer hash = new Integer(key.aMember().myHash);
0335: Bucket rslt = (Bucket) table.get(hash);
0336: if (rslt != null) {
0337: if (key.size() != rslt.size())
0338: return null;
0339: }
0340: return rslt;
0341: }
0342:
0343: /* rehash performance notes:
0344: *Uncommenting below gives an easy way of measuring
0345: *rehash performance.
0346: *On a 480ms job the rehash appeared to take over 200ms.
0347: *(Since with the code below uncommented the same
0348: *problem took about 1300ms).
0349: *
0350: */
0351: private int rehash(int lvl) {
0352: /*
0353: rehash0(lvl);
0354: rehash0(lvl);
0355: rehash0(lvl);
0356: rehash0(lvl);
0357: **/
0358: return rehash0(lvl);
0359: }
0360:
0361: private int rehash0(int level) {
0362: in(REHASHING);
0363: this .table = CollectionFactory.createHashedMap();
0364: // Set a global to define the hash of an AnonResource
0365: // level = 0 ==> AnonResource.myHashCode() = 0
0366: // level = n+1 ==> AnonResource.myHashCode() = hash[n]
0367: myHashLevel = level;
0368:
0369: // Now compute all hashes and stick things in the
0370: // right buckets.
0371: Iterator anons = unboundAnonResources.iterator();
0372: while (anons.hasNext()) {
0373: AnonResource a = (AnonResource) anons.next();
0374: Integer hash = new Integer(a.myHashCode());
0375: Bucket bkt = (Bucket) table.get(hash);
0376: if (bkt == null) {
0377: bkt = new Bucket();
0378: table.put(hash, bkt);
0379: }
0380: bkt.add(a);
0381: }
0382:
0383: // Produce a checksum for the table.
0384: int rslt = 0;
0385: Iterator tit = table.entrySet().iterator();
0386:
0387: while (tit.hasNext()) {
0388: Map.Entry pair = (Map.Entry) tit.next();
0389: int hash = ((Integer) pair.getKey()).intValue();
0390: Bucket bkt = (Bucket) pair.getValue();
0391: int sz = bkt.size();
0392: rslt += sz * 0x10001 ^ hash;
0393: }
0394:
0395: in(HASH_OK);
0396: return rslt;
0397:
0398: }
0399:
0400: /* subjects identified by bits 0 and 1,
0401: * predicate by bits 2 and 3,
0402: * object by 4 and 5
0403: * If neither bit set then role is bound.
0404: * If lower bit is set then role is unbound to
0405: * singleton variable in triple.
0406: * If higher bit is set then role is unbound
0407: * with anonymous variable that is also
0408: * unbound to a different role.
0409: * It is an error if both bits are set.
0410: *
0411: *
0412: * These funny things are read like this: e.g.
0413: *
0414: * SXPYOX - the subject is a variable X,
0415: * the predicate is another var Y
0416: * the object is the same var X
0417: *
0418: */
0419: static final private int NOVARS = 0;
0420: static final private int SX = 1;
0421: static final private int PX = 4;
0422: static final private int OX = 16;
0423: // SD, PD and OD are illegal values
0424: // by themselves, should only
0425: // be found in combination with
0426: // each other.
0427: // D for duplicate.
0428: static final private int SD = 2;
0429: static final private int PD = 8;
0430: static final private int OD = 32;
0431: static final private int SXPY = SX | PX;
0432: static final private int SXOY = SX | OX;
0433: static final private int PXOY = PX | OX;
0434: static final private int SXPYOZ = SX | PX | OX;
0435: static final private int SXPX = SD | PD;
0436: static final private int SXOX = SD | OD;
0437: static final private int PXOX = PD | OD;
0438: static final private int SXPXOY = SD | PD | OX;
0439: static final private int SXPYOX = SD | OD | PX;
0440: static final private int SXPYOY = SX | PD | OD;
0441: static final private int SXPXOX = SD | PD | OD;
0442: static final private int S = SX | SD;
0443: static final private int P = PX | PD;
0444: static final private int O = OX | OD;
0445:
0446: static private boolean legalPattern(int mask) {
0447: switch (mask) {
0448: case NOVARS:
0449: case SX:
0450: case OX:
0451: case PX:
0452: case SXPY:
0453: case SXOY:
0454: case PXOY:
0455: case SXPYOZ:
0456: case SXPX:
0457: case SXOX:
0458: case PXOX:
0459: case SXPXOY:
0460: case SXPYOX:
0461: case SXPYOY:
0462: case SXPXOX:
0463: return true;
0464: default:
0465: return false;
0466: }
0467: }
0468:
0469: // if i = 0 return the X component of pattern
0470: // if i = 1 return the Y component of pattern
0471: // if i = 2 return the Z component of pattern
0472: static private int varPosInPattern(int i, int pattern) {
0473: switch (pattern) {
0474: case NOVARS:
0475: break;
0476: case SX:
0477: if (i == 0)
0478: return SX;
0479: break;
0480: case OX:
0481: if (i == 0)
0482: return OX;
0483: break;
0484: case PX:
0485: if (i == 0)
0486: return PX;
0487: break;
0488: case SXPY:
0489: switch (i) {
0490: case 0:
0491: return SX;
0492: case 1:
0493: return PX;
0494: }
0495: break;
0496: case SXOY:
0497: switch (i) {
0498: case 0:
0499: return SX;
0500: case 1:
0501: return OX;
0502: }
0503: break;
0504: case PXOY:
0505: switch (i) {
0506: case 0:
0507: return PX;
0508: case 1:
0509: return OX;
0510: }
0511: break;
0512: case SXPYOZ:
0513: switch (i) {
0514: case 0:
0515: return SX;
0516: case 1:
0517: return PX;
0518: case 2:
0519: return OX;
0520: }
0521: break;
0522: case SXPX:
0523: if (i == 0)
0524: return SXPX;
0525: break;
0526: case SXOX:
0527: if (i == 0)
0528: return SXOX;
0529: break;
0530: case PXOX:
0531: if (i == 0)
0532: return PXOX;
0533: break;
0534: case SXPXOY:
0535: switch (i) {
0536: case 0:
0537: return SXPX;
0538: case 1:
0539: return OX;
0540: }
0541: break;
0542: case SXPYOX:
0543: switch (i) {
0544: case 0:
0545: return SXOX;
0546: case 1:
0547: return PX;
0548: }
0549: break;
0550: case SXPYOY:
0551: switch (i) {
0552: case 0:
0553: return SX;
0554: case 1:
0555: return PXOX;
0556: }
0557: break;
0558: case SXPXOX:
0559: if (i == 0)
0560: return SXPXOX;
0561: break;
0562: }
0563: System.out.println("Bad: " + i + " " + pattern);
0564: impossible();
0565: return 0;
0566: }
0567:
0568: static private interface SomeResource {
0569: int myHashCodeFromStatement();
0570:
0571: boolean mightBeEqual(SomeResource r);
0572: }
0573:
0574: static private class FixedResource implements SomeResource {
0575: int hash;
0576: Node node;
0577:
0578: public String toString() {
0579: return "f" + hash;
0580: }
0581:
0582: public int myHashCodeFromStatement() {
0583: return hash;
0584: }
0585:
0586: FixedResource(Node n) {
0587: hash = n.hashCode();
0588: node = n;
0589: }
0590:
0591: public boolean mightBeEqual(SomeResource r) {
0592: if (r != null && (r instanceof FixedResource)) {
0593: FixedResource f = (FixedResource) r;
0594: return hash == f.hash && node.equals(f.node); // PURE SYNTAX
0595: } else {
0596: return false;
0597: }
0598: }
0599: }
0600:
0601: // Record the occurence of variable r in bag.
0602: static void count(Map bag, SomeResource r, int pos) {
0603: if (r instanceof AnonResource) {
0604: int v[] = (int[]) bag.get(r);
0605: if (v == null) {
0606: v = new int[] { -1, -1, -1 };
0607: bag.put(r, v);
0608: }
0609: for (int i = 0; i < 3; i++)
0610: if (v[i] == -1) {
0611: v[i] = pos;
0612: return;
0613: }
0614: }
0615: }
0616:
0617: private class AnonStatement {
0618: int varCount;
0619: AnonResource vars[];
0620: SomeResource subj;
0621: SomeResource pred;
0622: SomeResource obj;
0623: int pattern;
0624:
0625: AnonStatement(Triple s) {
0626: Map bag = CollectionFactory.createHashedMap();
0627: pattern = NOVARS;
0628: subj = convert(s.getSubject());
0629: pred = convert(s.getPredicate());
0630: obj = convert(s.getObject());
0631: count(bag, subj, 0);
0632: count(bag, pred, 2);
0633: count(bag, obj, 4);
0634: varCount = bag.size();
0635: vars = new AnonResource[varCount];
0636: add(subj);
0637: add(pred);
0638: add(obj);
0639: Iterator it = bag.values().iterator();
0640: while (it.hasNext()) {
0641: int v[] = (int[]) it.next();
0642: int last = 2;
0643: int p;
0644: while (v[last] == -1)
0645: last--;
0646: if (last == 0)
0647: p = SX;
0648: else
0649: p = SD;
0650: for (int i = 0; i <= last; i++)
0651: pattern |= p << v[i];
0652: }
0653: if (!legalPattern(pattern)) {
0654: System.out.println("s: " + subj + " p: " + pred
0655: + " o: " + obj + " pattern: " + pattern);
0656: impossible();
0657: }
0658: }
0659:
0660: private void add(SomeResource r) {
0661: if (r instanceof AnonResource) {
0662: for (int i = 0; i < vars.length; i++)
0663: if (vars[i] == null || vars[i] == r) {
0664: vars[i] = (AnonResource) r;
0665: return;
0666: }
0667: impossible();
0668: }
0669: }
0670:
0671: // returns the location of v in this statement.
0672: // e.g. PXOX to say that v is both the predicate and object.
0673: int varPos(AnonResource v) {
0674: if (v == null)
0675: return 0;
0676: for (int i = 0; i < vars.length; i++)
0677: if (vars[i] == v)
0678: return varPosInPattern(i, pattern);
0679: impossible();
0680: return 0;
0681: }
0682:
0683: int myHashCode(AnonResource v) {
0684: int vX = varPos(v);
0685: int hash = vX;
0686: // The multipliers are chosen to be 2 bit numbers.
0687: // These muddle up the bits; should be quick in an optimised
0688: // compilation or JIT (a shift and an add); and ensure
0689: // that positional information (SPO) is encoded in the hash.
0690: if ((vX & S) == 0) {
0691: hash ^= subj.myHashCodeFromStatement() * 0x101;
0692: }
0693: if ((vX & P) == 0) {
0694: hash ^= pred.myHashCodeFromStatement() * 0x3f;
0695: }
0696: if ((vX & O) == 0) {
0697: hash ^= obj.myHashCodeFromStatement() * 0x41;
0698: }
0699: return hash;
0700: }
0701:
0702: boolean contextualEquals(AnonResource v, AnonStatement sB,
0703: AnonResource vB) {
0704: int vX = varPos(v);
0705: if (vX != sB.varPos(vB))
0706: return false;
0707: return ((vX & S) != 0 || subj.mightBeEqual(sB.subj))
0708: && ((vX & P) != 0 || pred.mightBeEqual(sB.pred))
0709: && ((vX & O) != 0 || obj.mightBeEqual(sB.obj));
0710:
0711: }
0712: }
0713:
0714: // Bucket's live longer than the table that they sit in.
0715: // If a bucket is matched before the main bind() loop then
0716: // we are iterating over it's members while the rest of the
0717: // algorithm is proceeding.
0718: private class Bucket {
0719: Set anonRes = CollectionFactory.createHashedSet();
0720: int hash[] = new int[MAX_HASH_DEPTH];
0721:
0722: boolean bind(Bucket singleton) {
0723: return bind(aMember(), singleton, singleton.aMember());
0724: }
0725:
0726: boolean bind(AnonResource mine, Bucket other,
0727: AnonResource binding) {
0728: if (mine.checkBinding(binding)) {
0729: mine.bind(binding);
0730: return true;
0731: } else {
0732: return false;
0733: }
0734: }
0735:
0736: void add(AnonResource r) {
0737: anonRes.add(r);
0738: }
0739:
0740: AnonResource aMember() {
0741: return (AnonResource) anonRes.iterator().next();
0742: }
0743:
0744: Iterator members() {
0745: return anonRes.iterator();
0746: }
0747:
0748: int size() {
0749: return anonRes.size();
0750: }
0751: }
0752:
0753: private class AnonResource implements SomeResource {
0754: AnonResource bound;
0755: Node r;
0756: Set occursIn = CollectionFactory.createHashedSet(); // The AnonStatements containing me.
0757: int hash[] = new int[MAX_HASH_DEPTH];
0758: int boundHash;
0759: Set friends = CollectionFactory.createHashedSet(); // Other vars in AnonStatements containing me.
0760: int myHash;
0761:
0762: public String toString() {
0763: String rslt = r.toString();
0764: if (bound != null)
0765: rslt += "[" + bound.r.toString() + "]";
0766: return rslt;
0767: }
0768:
0769: AnonResource(Node r) {
0770: unboundAnonResources.add(this );
0771: this .r = r;
0772: }
0773:
0774: public int myHashCodeFromStatement() {
0775: if (bound != null)
0776: return boundHash;
0777: if (myHashLevel == 0) {
0778: return 0xcafebabe;
0779: }
0780: check(REHASHING | HASH_OK);
0781: return hash[myHashLevel - 1];
0782: }
0783:
0784: // MUST NOT BE CALLED FROM WITHIN THE LOOP
0785: // OF OBLIG BINDINGS, use myHash
0786: // ONLY INTENDED TO BE CALLED FROM WITHIN rehash
0787: int myHashCode() {
0788: check(REHASHING);
0789: if (bound != null)
0790: impossible();
0791: myHash = 0;
0792: Iterator ss = occursIn.iterator();
0793: while (ss.hasNext()) {
0794: AnonStatement ass = (AnonStatement) ss.next();
0795: myHash += ass.myHashCode(this );
0796: }
0797: hash[myHashLevel] = myHash;
0798: return myHash;
0799: }
0800:
0801: void bind(AnonResource pair) {
0802: bound = pair;
0803:
0804: if (!unboundAnonResources.remove(this ))
0805: impossible();
0806: boundAnonResources.add(this );
0807:
0808: if (pair.bound == null) {
0809: trace(true, r.getBlankNodeId() + "="
0810: + pair.r.getBlankNodeId() + ", ");
0811: pair.bind(this );
0812: // choice any arbitary number here
0813: // helps spread the bits.
0814: bound.boundHash = boundHash = random.nextInt();
0815: // if ( myHash != bound.myHash )
0816: // impossible();
0817: // Sometimes they are different, after we have
0818: // guessed badly, changed bound.myHash and then
0819: // backtracked.
0820: }
0821:
0822: if (bound.bound != this )
0823: impossible();
0824: }
0825:
0826: void unbind() {
0827: AnonResource pair = bound;
0828: bound = null;
0829:
0830: if (!boundAnonResources.remove(this ))
0831: impossible();
0832:
0833: unboundAnonResources.add(this );
0834:
0835: if (pair.bound != null) {
0836: trace(false, r.getBlankNodeId() + "!="
0837: + pair.r.getBlankNodeId() + ", ");
0838: if (pair.bound != this )
0839: impossible();
0840:
0841: pair.unbind();
0842: }
0843:
0844: in(HASH_BAD);
0845: }
0846:
0847: boolean checkBinding(AnonResource pair) {
0848:
0849: if (occursIn.size() != pair.occursIn.size())
0850: return false;
0851:
0852: Set ourStatements = wrapStatements();
0853: Set otherStatements = pair.wrapStatements();
0854:
0855: return ourStatements.removeAll(otherStatements)
0856: && ourStatements.isEmpty();
0857:
0858: }
0859:
0860: private Set wrapStatements() {
0861: if (state == HASH_BAD) {
0862: // We are already in(HASH_BAD).
0863: // We need to use AnonResource.myHashCodeFromStatement().
0864: // That is OK as long as myHashLevel is 0
0865: myHashLevel = 0;
0866: }
0867: Set statements = CollectionFactory.createHashedSet();
0868: // Add all our statements to the set.
0869: Iterator it = occursIn.iterator();
0870: while (it.hasNext())
0871: statements
0872: .add(wrapStatement((AnonStatement) it.next()));
0873: return statements;
0874: }
0875:
0876: public boolean mightBeEqual(SomeResource r) {
0877: if (r != null && (r instanceof AnonResource)) {
0878: AnonResource a = (AnonResource) r;
0879: return a == this || bound == a
0880: || (bound == null && a.bound == null);
0881: } else {
0882: return false;
0883: }
0884: }
0885:
0886: StatementWrapper wrapStatement(AnonStatement s) {
0887: return new StatementWrapper(s);
0888: }
0889:
0890: // inner inner class -- ouch!
0891: private class StatementWrapper {
0892: int hash;
0893: AnonStatement statement;
0894:
0895: public boolean equals(Object o) {
0896: if (o == null || (!(o instanceof StatementWrapper)))
0897: return false;
0898: StatementWrapper w = (StatementWrapper) o;
0899: return hash == w.hash
0900: && statement.contextualEquals(
0901: AnonResource.this , w.statement, w
0902: .asAnonR());
0903: }
0904:
0905: public int hashCode() {
0906: return hash;
0907: }
0908:
0909: StatementWrapper(AnonStatement s) {
0910: hash = s.myHashCode(AnonResource.this );
0911: statement = s;
0912: }
0913:
0914: AnonResource asAnonR() {
0915: return AnonResource.this ;
0916: }
0917: }
0918: }
0919:
0920: private Map anonLookup = CollectionFactory.createHashedMap();
0921:
0922: private SomeResource convert(Node n) {
0923: if (n.isBlank()) {
0924: SomeResource anon = (SomeResource) anonLookup.get(n);
0925: if (anon == null) {
0926: anon = new AnonResource(n);
0927: anonLookup.put(n, anon);
0928: }
0929: return anon;
0930: } else {
0931: return new FixedResource(n);
0932: }
0933: }
0934:
0935: private void check(int s) {
0936: if ((state & s) == 0)
0937: impossible();
0938: }
0939:
0940: private void in(int s) {
0941: state = s;
0942: other.state = s;
0943: }
0944:
0945: static private void impossible() {
0946: throw new JenaException("Cannot happen!");
0947: }
0948:
0949: static private int col = 0;
0950: static private boolean lastDir = false;
0951:
0952: static private void trace(boolean dir, String s) {
0953: if (TRACE) {
0954: if (dir != lastDir) {
0955: traceNL();
0956: lastDir = dir;
0957: }
0958: int nCol = col + s.length();
0959: if (col != 0 && nCol > 70) {
0960: traceNL();
0961: nCol = s.length();
0962: }
0963: System.out.print(s);
0964: System.out.flush();
0965: col = nCol;
0966: }
0967: }
0968:
0969: static private void traceNL() {
0970: if (TRACE) {
0971: System.out.println();
0972: col = 0;
0973: }
0974: }
0975:
0976: }
0977: /*
0978: * (c) Copyright 2002, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
0979: *
0980: * All rights reserved.
0981: *
0982: *
0983: * Redistribution and use in source and binary forms, with or without
0984: * modification, are permitted provided that the following conditions
0985: * are met:
0986: * 1. Redistributions of source code must retain the above copyright
0987: * notice, this list of conditions and the following disclaimer.
0988: * 2. Redistributions in binary form must reproduce the above copyright
0989: * notice, this list of conditions and the following disclaimer in the
0990: * documentation and/or other materials provided with the distribution.
0991: * 3. The name of the author may not be used to endorse or promote products
0992: * derived from this software without specific prior written permission.
0993:
0994: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
0995: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
0996: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
0997: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
0998: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
0999: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1000: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1001: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1002: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1003: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1004: *
1005: * $Id: GraphMatcher.java,v 1.18 2008/01/02 12:05:16 andy_seaborne Exp $
1006: */
|