001: /******************************************************************
002: * File: TestTransitiveGraphCacheNew.java
003: * Created by: Dave Reynolds
004: * Created on: 25-Nov-2004
005: *
006: * (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: TestTransitiveGraphCache.java,v 1.18 2008/01/02 12:08:31 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.test;
010:
011: import com.hp.hpl.jena.reasoner.transitiveReasoner.TransitiveGraphCache;
012: import com.hp.hpl.jena.reasoner.TriplePattern;
013: import com.hp.hpl.jena.graph.Node;
014: import com.hp.hpl.jena.graph.Triple;
015:
016: import junit.framework.TestCase;
017: import junit.framework.TestSuite;
018:
019: /**
020: * A purely temporary test suite just used during development and kept
021: * off the main unit test paths.
022: *
023: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
024: * @version $Revision: 1.18 $
025: */
026:
027: public class TestTransitiveGraphCache extends TestCase {
028:
029: /** The cache under test */
030: TransitiveGraphCache cache;
031:
032: // Dummy predicates and nodes for the graph
033: String NS = "urn:x-hp-test:ex/";
034: Node directP = Node.createURI(NS + "directSubProperty");
035: Node closedP = Node.createURI(NS + "subProperty");
036:
037: Node a = Node.createURI(NS + "a");
038: Node b = Node.createURI(NS + "b");
039: Node c = Node.createURI(NS + "c");
040: Node d = Node.createURI(NS + "d");
041: Node e = Node.createURI(NS + "e");
042: Node f = Node.createURI(NS + "f");
043: Node g = Node.createURI(NS + "g");
044:
045: /**
046: * Boilerplate for junit
047: */
048: public TestTransitiveGraphCache(String name) {
049: super (name);
050: }
051:
052: /**
053: * Boilerplate for junit.
054: * This is its own test suite
055: */
056: public static TestSuite suite() {
057: return new TestSuite(TestTransitiveGraphCache.class);
058: // TestSuite suite = new TestSuite();
059: // suite.addTest( new TestTransitiveGraphCache("testEquivalencesSimple"));
060: // return suite;
061: }
062:
063: /**
064: * Test the basic functioning a Transitive closure cache.
065: * Caches the graph but not the final closure.
066: */
067: public void testBasicCache() {
068: initCache();
069: cache.setCaching(false);
070: doBasicTest(cache);
071: }
072:
073: /**
074: * Test the basic functioning a Transitive closure cache.
075: * Caches the graph and any requested closures
076: */
077: public void testCachingCache() {
078: initCache();
079: cache.setCaching(true);
080: doBasicTest(cache);
081: }
082:
083: /**
084: * Test the clone operation
085: */
086: public void testCloning() {
087: initCache();
088: TransitiveGraphCache clone = cache.deepCopy();
089: // Mess with the original to check cloning
090: cache.addRelation(new Triple(a, closedP, d));
091: cache.addRelation(new Triple(g, closedP, a));
092: doBasicTest(clone);
093: }
094:
095: /**
096: * Initialize the cache with some test data
097: */
098: private void initCache() {
099: // Create a graph with reflexive references, cycles, redundant links
100: cache = new TransitiveGraphCache(directP, closedP);
101: cache.addRelation(new Triple(a, closedP, b));
102: cache.addRelation(new Triple(b, closedP, e));
103: cache.addRelation(new Triple(b, closedP, c));
104: cache.addRelation(new Triple(e, closedP, f));
105: cache.addRelation(new Triple(c, closedP, f));
106: cache.addRelation(new Triple(f, closedP, g));
107: cache.addRelation(new Triple(d, closedP, c));
108: cache.addRelation(new Triple(d, closedP, e));
109: cache.addRelation(new Triple(d, closedP, g)); // reduntant two ways
110: cache.addRelation(new Triple(a, closedP, e)); // redundant
111: cache.addRelation(new Triple(d, closedP, b)); // Makes both earlier d's redundant
112:
113: cache.addRelation(new Triple(a, closedP, a));
114: cache.addRelation(new Triple(b, closedP, b));
115: cache.addRelation(new Triple(c, closedP, c));
116: cache.addRelation(new Triple(d, closedP, d));
117: cache.addRelation(new Triple(e, closedP, e));
118: cache.addRelation(new Triple(f, closedP, f));
119: cache.addRelation(new Triple(g, closedP, g));
120: }
121:
122: public void doBasicTest(TransitiveGraphCache cache) {
123: // Test forward property patterns
124: TestUtil.assertIteratorValues(this , cache
125: .find(new TriplePattern(a, directP, null)),
126: new Object[] { new Triple(a, closedP, a),
127: new Triple(a, closedP, b) });
128: TestUtil.assertIteratorValues(this , cache
129: .find(new TriplePattern(a, closedP, null)),
130: new Object[] { new Triple(a, closedP, a),
131: new Triple(a, closedP, b),
132: new Triple(a, closedP, c),
133: new Triple(a, closedP, e),
134: new Triple(a, closedP, f),
135: new Triple(a, closedP, g) });
136: TestUtil.assertIteratorValues(this , cache
137: .find(new TriplePattern(a, closedP, g)),
138: new Object[] { new Triple(a, closedP, g), });
139:
140: // Test backward patterns
141: TestUtil.assertIteratorValues(this , cache
142: .find(new TriplePattern(null, directP, f)),
143: new Object[] { new Triple(e, closedP, f),
144: new Triple(f, closedP, f),
145: new Triple(c, closedP, f) });
146: TestUtil.assertIteratorValues(this , cache
147: .find(new TriplePattern(null, closedP, f)),
148: new Object[] { new Triple(f, closedP, f),
149: new Triple(e, closedP, f),
150: new Triple(b, closedP, f),
151: new Triple(c, closedP, f),
152: new Triple(a, closedP, f),
153: new Triple(d, closedP, f) });
154:
155: // List all cases
156: TestUtil.assertIteratorValues(this , cache
157: .find(new TriplePattern(null, directP, null)),
158: new Object[] { new Triple(a, closedP, a),
159: new Triple(a, closedP, b),
160: new Triple(d, closedP, d),
161: new Triple(d, closedP, b),
162: new Triple(b, closedP, b),
163: new Triple(b, closedP, e),
164: new Triple(b, closedP, c),
165: new Triple(e, closedP, e),
166: new Triple(e, closedP, f),
167: new Triple(c, closedP, c),
168: new Triple(c, closedP, f),
169: new Triple(f, closedP, f),
170: new Triple(f, closedP, g),
171: new Triple(g, closedP, g) });
172: TestUtil.assertIteratorValues(this , cache
173: .find(new TriplePattern(null, closedP, null)),
174: new Object[] { new Triple(a, closedP, a),
175: new Triple(a, closedP, b),
176: new Triple(a, closedP, c),
177: new Triple(a, closedP, e),
178: new Triple(a, closedP, f),
179: new Triple(a, closedP, g),
180: new Triple(d, closedP, d),
181: new Triple(d, closedP, b),
182: new Triple(d, closedP, e),
183: new Triple(d, closedP, c),
184: new Triple(d, closedP, f),
185: new Triple(d, closedP, g),
186: new Triple(b, closedP, b),
187: new Triple(b, closedP, e),
188: new Triple(b, closedP, c),
189: new Triple(b, closedP, f),
190: new Triple(b, closedP, g),
191: new Triple(e, closedP, e),
192: new Triple(e, closedP, f),
193: new Triple(e, closedP, g),
194: new Triple(c, closedP, c),
195: new Triple(c, closedP, f),
196: new Triple(c, closedP, g),
197: new Triple(f, closedP, f),
198: new Triple(f, closedP, g),
199: new Triple(g, closedP, g) });
200:
201: // Add a look in the graph and check the loop from each starting position
202: cache.addRelation(new Triple(g, closedP, e));
203:
204: TestUtil.assertIteratorValues(this , cache
205: .find(new TriplePattern(e, directP, null)),
206: new Object[] { new Triple(e, closedP, e),
207: new Triple(e, closedP, f),
208: new Triple(e, closedP, g) });
209: TestUtil.assertIteratorValues(this , cache
210: .find(new TriplePattern(f, directP, null)),
211: new Object[] { new Triple(f, closedP, f),
212: new Triple(f, closedP, g),
213: new Triple(f, closedP, e) });
214: TestUtil.assertIteratorValues(this , cache
215: .find(new TriplePattern(g, directP, null)),
216: new Object[] { new Triple(g, closedP, g),
217: new Triple(g, closedP, e),
218: new Triple(g, closedP, f) });
219: TestUtil.assertIteratorValues(this , cache
220: .find(new TriplePattern(null, directP, e)),
221: new Object[] { new Triple(e, closedP, e),
222: new Triple(f, closedP, e),
223: new Triple(b, closedP, e),
224: new Triple(c, closedP, e),
225: new Triple(g, closedP, e) });
226: TestUtil.assertIteratorValues(this , cache
227: .find(new TriplePattern(null, directP, f)),
228: new Object[] { new Triple(f, closedP, f),
229: new Triple(g, closedP, f),
230: new Triple(b, closedP, f),
231: new Triple(c, closedP, f),
232: new Triple(e, closedP, f) });
233: TestUtil.assertIteratorValues(this , cache
234: .find(new TriplePattern(null, directP, g)),
235: new Object[] { new Triple(g, closedP, g),
236: new Triple(e, closedP, g),
237: new Triple(b, closedP, g),
238: new Triple(c, closedP, g),
239: new Triple(f, closedP, g) });
240: TestUtil.assertIteratorValues(this , cache
241: .find(new TriplePattern(g, closedP, null)),
242: new Object[] { new Triple(g, closedP, g),
243: new Triple(g, closedP, e),
244: new Triple(g, closedP, f) });
245: TestUtil.assertIteratorValues(this , cache
246: .find(new TriplePattern(e, closedP, null)),
247: new Object[] { new Triple(e, closedP, g),
248: new Triple(e, closedP, e),
249: new Triple(e, closedP, f) });
250: TestUtil.assertIteratorValues(this , cache
251: .find(new TriplePattern(f, closedP, null)),
252: new Object[] { new Triple(f, closedP, g),
253: new Triple(f, closedP, e),
254: new Triple(f, closedP, f) });
255: /*
256: System.out.println("Add e-f-g-e loop");
257: cache.printAll();
258: listFind(cache, e, directP, null);
259: listFind(cache, e, closedP, null);
260: listFind(cache, f, directP, null);
261: listFind(cache, f, closedP, null);
262: listFind(cache, g, directP, null);
263: listFind(cache, g, closedP, null);
264: */
265: }
266:
267: /**
268: * Test a a case where an earlier version had a bug due to removing
269: * a link which was required rather than redundant.
270: */
271: public void testBug1() {
272: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
273: closedP);
274: cache.addRelation(new Triple(a, closedP, b));
275: cache.addRelation(new Triple(c, closedP, a));
276: cache.addRelation(new Triple(c, closedP, b));
277: cache.addRelation(new Triple(a, closedP, c));
278: TestUtil.assertIteratorValues(this , cache
279: .find(new TriplePattern(a, directP, null)),
280: new Object[] { new Triple(a, closedP, a),
281: new Triple(a, closedP, b),
282: new Triple(a, closedP, c), });
283:
284: }
285:
286: /**
287: * Test a case where the transitive reduction appears to
288: * be incomplete. The links just
289: * form a linear chain, with all closed links provided. But inserted
290: * in a particular order.
291: */
292: public void testBug2() {
293: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
294: closedP);
295: cache.addRelation(new Triple(a, closedP, b));
296: cache.addRelation(new Triple(a, closedP, c));
297: cache.addRelation(new Triple(b, closedP, c));
298: TestUtil.assertIteratorValues(this , cache
299: .find(new TriplePattern(a, directP, null)),
300: new Object[] { new Triple(a, closedP, a),
301: new Triple(a, closedP, b) });
302:
303: }
304:
305: /**
306: * Test the removeRelation functionality.
307: */
308: public void testRemove() {
309: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
310: closedP);
311: cache.addRelation(new Triple(a, closedP, b));
312: cache.addRelation(new Triple(a, closedP, c));
313: cache.addRelation(new Triple(b, closedP, d));
314: cache.addRelation(new Triple(c, closedP, d));
315: cache.addRelation(new Triple(d, closedP, e));
316: TestUtil.assertIteratorValues(this , cache
317: .find(new TriplePattern(a, closedP, null)),
318: new Object[] { new Triple(a, closedP, a),
319: new Triple(a, closedP, b),
320: new Triple(a, closedP, b),
321: new Triple(a, closedP, c),
322: new Triple(a, closedP, d),
323: new Triple(a, closedP, e) });
324: TestUtil.assertIteratorValues(this , cache
325: .find(new TriplePattern(b, closedP, null)),
326: new Object[] { new Triple(b, closedP, b),
327: new Triple(b, closedP, d),
328: new Triple(b, closedP, e) });
329: cache.removeRelation(new Triple(b, closedP, d));
330: TestUtil.assertIteratorValues(this , cache
331: .find(new TriplePattern(a, closedP, null)),
332: new Object[] { new Triple(a, closedP, a),
333: new Triple(a, closedP, b),
334: new Triple(a, closedP, b),
335: new Triple(a, closedP, c),
336: new Triple(a, closedP, d),
337: new Triple(a, closedP, e) });
338: TestUtil.assertIteratorValues(this , cache
339: .find(new TriplePattern(b, closedP, null)),
340: new Object[] { new Triple(b, closedP, b), });
341: cache.removeRelation(new Triple(a, closedP, c));
342: TestUtil.assertIteratorValues(this , cache
343: .find(new TriplePattern(a, closedP, null)),
344: new Object[] { new Triple(a, closedP, a),
345: new Triple(a, closedP, b) });
346: TestUtil.assertIteratorValues(this , cache
347: .find(new TriplePattern(b, closedP, null)),
348: new Object[] { new Triple(b, closedP, b), });
349: }
350:
351: /**
352: * Test direct link case with adverse ordering.
353: */
354: public void testDirect() {
355: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
356: closedP);
357: cache.addRelation(new Triple(a, closedP, b));
358: cache.addRelation(new Triple(c, closedP, d));
359: cache.addRelation(new Triple(a, closedP, d));
360: cache.addRelation(new Triple(b, closedP, c));
361: TestUtil.assertIteratorValues(this , cache
362: .find(new TriplePattern(a, directP, null)),
363: new Object[] { new Triple(a, closedP, a),
364: new Triple(a, closedP, b), });
365: }
366:
367: /**
368: * Test cycle detection.
369: */
370: public void testCycle() {
371: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
372: closedP);
373: cache.addRelation(new Triple(a, closedP, b));
374: cache.addRelation(new Triple(b, closedP, c));
375: cache.addRelation(new Triple(a, closedP, c));
376: cache.addRelation(new Triple(c, closedP, b));
377: TestUtil.assertIteratorValues(this , cache
378: .find(new TriplePattern(a, directP, null)),
379: new Object[] { new Triple(a, closedP, a),
380: new Triple(a, closedP, b),
381: new Triple(a, closedP, c), });
382: }
383:
384: /**
385: * A ring of three cycle
386: */
387: public void testCycle2() {
388: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
389: closedP);
390: cache.addRelation(new Triple(a, closedP, b));
391: cache.addRelation(new Triple(a, closedP, c));
392: cache.addRelation(new Triple(f, closedP, b));
393: cache.addRelation(new Triple(b, closedP, g));
394: cache.addRelation(new Triple(b, closedP, d));
395: cache.addRelation(new Triple(d, closedP, c));
396: cache.addRelation(new Triple(d, closedP, e));
397: cache.addRelation(new Triple(c, closedP, e));
398: cache.addRelation(new Triple(c, closedP, b));
399: TestUtil.assertIteratorValues(this , cache
400: .find(new TriplePattern(c, directP, null)),
401: new Object[] { new Triple(c, closedP, e),
402: new Triple(c, closedP, g),
403: new Triple(c, closedP, b),
404: new Triple(c, closedP, d),
405: new Triple(c, closedP, c), });
406: TestUtil.assertIteratorValues(this , cache
407: .find(new TriplePattern(null, directP, c)),
408: new Object[] { new Triple(a, closedP, c),
409: new Triple(b, closedP, c),
410: new Triple(d, closedP, c),
411: new Triple(f, closedP, c),
412: new Triple(c, closedP, c), });
413: TestUtil.assertIteratorValues(this , cache
414: .find(new TriplePattern(f, closedP, null)),
415: new Object[] { new Triple(f, closedP, f),
416: new Triple(f, closedP, b),
417: new Triple(f, closedP, c),
418: new Triple(f, closedP, d),
419: new Triple(f, closedP, g),
420: new Triple(f, closedP, e), });
421: }
422:
423: /**
424: * Two ring-of-three cycles joined at two points
425: */
426: public void testCycle3() {
427: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
428: closedP);
429: cache.addRelation(new Triple(a, closedP, b));
430: cache.addRelation(new Triple(b, closedP, c));
431: cache.addRelation(new Triple(c, closedP, a));
432: cache.addRelation(new Triple(d, closedP, e));
433: cache.addRelation(new Triple(e, closedP, f));
434: cache.addRelation(new Triple(f, closedP, d));
435: cache.addRelation(new Triple(b, closedP, d));
436: cache.addRelation(new Triple(f, closedP, c));
437: TestUtil.assertIteratorValues(this , cache
438: .find(new TriplePattern(a, directP, null)),
439: new Object[] { new Triple(a, closedP, a),
440: new Triple(a, closedP, b),
441: new Triple(a, closedP, c),
442: new Triple(a, closedP, d),
443: new Triple(a, closedP, e),
444: new Triple(a, closedP, f), });
445: TestUtil.assertIteratorValues(this , cache
446: .find(new TriplePattern(null, directP, a)),
447: new Object[] { new Triple(a, closedP, a),
448: new Triple(b, closedP, a),
449: new Triple(c, closedP, a),
450: new Triple(d, closedP, a),
451: new Triple(e, closedP, a),
452: new Triple(f, closedP, a), });
453: }
454:
455: /**
456: * Test simple equivalences case
457: */
458: public void testEquivalencesSimple() {
459: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
460: closedP);
461: cache.addRelation(new Triple(a, closedP, b));
462: cache.addRelation(new Triple(b, closedP, a));
463: TestUtil.assertIteratorValues(this , cache
464: .find(new TriplePattern(null, closedP, null)),
465: new Object[] { new Triple(a, closedP, b),
466: new Triple(b, closedP, a),
467: new Triple(b, closedP, b),
468: new Triple(a, closedP, a), });
469: TestUtil.assertIteratorLength(cache.find(new TriplePattern(
470: null, closedP, null)), 4);
471: }
472:
473: /**
474: * Test equivalences case
475: */
476: public void testEquivalences() {
477: TransitiveGraphCache cache = new TransitiveGraphCache(directP,
478: closedP);
479: cache.addRelation(new Triple(a, closedP, b));
480: cache.addRelation(new Triple(b, closedP, a));
481:
482: cache.addRelation(new Triple(c, closedP, d));
483: cache.addRelation(new Triple(d, closedP, c));
484:
485: cache.addRelation(new Triple(b, closedP, d));
486: cache.addRelation(new Triple(d, closedP, b));
487:
488: assertTrue("Test eq", cache.contains(new TriplePattern(a,
489: closedP, d)));
490: }
491:
492: }
493:
494: /*
495: (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
496: All rights reserved.
497:
498: Redistribution and use in source and binary forms, with or without
499: modification, are permitted provided that the following conditions
500: are met:
501:
502: 1. Redistributions of source code must retain the above copyright
503: notice, this list of conditions and the following disclaimer.
504:
505: 2. Redistributions in binary form must reproduce the above copyright
506: notice, this list of conditions and the following disclaimer in the
507: documentation and/or other materials provided with the distribution.
508:
509: 3. The name of the author may not be used to endorse or promote products
510: derived from this software without specific prior written permission.
511:
512: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
513: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
514: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
515: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
516: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
517: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
518: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
519: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
520: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
521: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
522: */
|