clerezza-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From r...@apache.org
Subject svn commit: r899478 - in /incubator/clerezza/issues/CLEREZZA-67: ./ org.apache.clerezza.rdf.core/ org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/ org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/
Date Thu, 14 Jan 2010 23:46:00 GMT
Author: reto
Date: Thu Jan 14 23:45:59 2010
New Revision: 899478

URL: http://svn.apache.org/viewvc?rev=899478&view=rev
Log:
CLEREZZA-67: a first and quite inefficient implementation

Added:
    incubator/clerezza/issues/CLEREZZA-67/
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/
      - copied from r897462, incubator/clerezza/trunk/org.apache.clerezza.parent/org.apache.clerezza.rdf.core/
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java
Modified:
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/pom.xml
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/AbstractGraph.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleMGraph.java
    incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleTripleCollection.java

Modified: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/pom.xml
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/pom.xml?rev=899478&r1=897462&r2=899478&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/pom.xml (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/pom.xml Thu Jan 14
23:45:59 2010
@@ -29,6 +29,12 @@
 			<artifactId>junit</artifactId>
 			<scope>test</scope>
 		</dependency>
+	 <dependency>
+	  <groupId>fastutil</groupId>
+	  <artifactId>fastutil</artifactId>
+	  <version>5.0.9</version>
+	  <type>jar</type>
+	 </dependency>
 	</dependencies>
 	<build>
 		<plugins>
@@ -76,3 +82,4 @@
 		</plugins>
 	</build>
 </project>
+

Modified: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/AbstractGraph.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/AbstractGraph.java?rev=899478&r1=897462&r2=899478&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/AbstractGraph.java
(original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/AbstractGraph.java
Thu Jan 14 23:45:59 2010
@@ -91,6 +91,15 @@
 
 	@Override
 	public boolean equals(Object obj) {
-		throw new UnsupportedOperationException("Not supported yet.");
+		if (this == obj) {
+			return true;
+		}
+		if (!(obj instanceof Graph)) {
+			return false;
+		}
+		if (hashCode() != obj.hashCode()) {
+			return false;
+		}
+		return GraphMatcher.getValidMapping(this, (Graph) obj) != null;
 	}
 }

Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java?rev=899478&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java
(added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java
Thu Jan 14 23:45:59 2010
@@ -0,0 +1,391 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.clerezza.rdf.core.impl;
+
+import it.unimi.dsi.fastutil.ints.IntIterator;
+import it.unimi.dsi.fastutil.ints.IntSet;
+
+import java.io.StringReader;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+
+
+import java.util.Set;
+import org.apache.clerezza.rdf.core.BNode;
+import org.apache.clerezza.rdf.core.MGraph;
+import org.apache.clerezza.rdf.core.NonLiteral;
+import org.apache.clerezza.rdf.core.TripleCollection;
+import org.apache.clerezza.rdf.core.Resource;
+import org.apache.clerezza.rdf.core.Triple;
+import org.apache.clerezza.rdf.core.UriRef;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * @author reto
+ * 
+ */
+public class GraphMatcher {
+
+	static private Random random = new Random(0);
+
+	private final static Logger log = LoggerFactory.getLogger(GraphMatcher.class);
+
+	/**
+	 * get a mapping from g1 to g2 or null if the graphs are not isomorphic. The
+	 * returned map maps each <code>BNode</code>s from g1 to one
+	 * of g2. If the graphs are ground graphs the method return an empty map if
+	 * the graph are equals and null otherwise.
+	 * <p/>
+	 * NOTE: This method does not returned mapping from blank nodes to grounded
+	 * nodes, a bnode in g1 is not a vraiable that may match any node, but must
+	 * match a bnode in g2.
+	 * <p/>
+	 *
+	 * On the algorithm:<br/>
+	 * - In a first step it checked if every grounded triple in g1 matches one
+	 * in g2<br/>
+	 * - [optional] blank node blind matching</br>
+	 * - in a map mbng1 bnode of g1 is mapped to a set of of its
+	 * properties and inverse properties, this is the predicate and the object
+	 * or subject respectively, analoguosly in mbgn2 every bnode of g2<br/>
+	 * - based on the incoming and outgoing properties a hash is calculated for
+	 * each bnode, in the first step when calculating the hash  aconstant value
+	 * is taken for the bnodes that might be subject or object in the (inverse properties)
+	 * - hash-classes:
+	 * 
+	 * @param g1
+	 * @param g2
+	 * @return a Set of NodePairs
+	 */
+	public static Map<BNode, BNode> getValidMapping(TripleCollection og1, TripleCollection
og2) {
+		MGraph g1 = new SimpleMGraph(og1);
+		MGraph g2 = new SimpleMGraph(og2);
+		if (!removeGrounded(g1,g2)) {
+			return null;
+		}
+		Map<BNode, BNode> matchings = new HashMap<BNode, BNode>();
+		int foundMatchings = 0;
+		//start with an empty map
+		Map<BNode, Integer> bNodeHashMap = new HashMap<BNode, Integer>();
+		while (true) {
+			bNodeHashMap = matchByHashes(matchings, g1, g2, bNodeHashMap);
+			if (bNodeHashMap == null) {
+				return null;
+			}
+			if (matchings.size() == foundMatchings) {
+				break;
+			}
+			foundMatchings = matchings.size();
+		}
+		if (g1.size() > 0) {
+			//start trial an error matching
+			Map<BNode, BNode> remainingMappings = trialAndErrorMatching(g1, g2);
+			if (remainingMappings == null) {
+				return null;
+			} else {
+				matchings.putAll(remainingMappings);
+			}
+		}
+		
+
+		return matchings;
+	}
+
+	private static Map<BNode, Set<Property>> getBNodePropMap(MGraph g) {
+		Set<BNode> bNodes = getBNodes(g);
+		Map<BNode, Set<Property>> result = new HashMap<BNode, Set<Property>>();
+		for (BNode bNode : bNodes) {
+			result.put(bNode, getProperties(bNode, g));
+		}
+		return result;
+	}
+
+	private static Set<Property> getProperties(BNode bNode, MGraph g) {
+		Set<Property> result = new HashSet<Property>();
+		Iterator<Triple> ti = g.filter(bNode, null, null);
+		while (ti.hasNext()) {
+			Triple triple = ti.next();
+			result.add(new ForwardProperty(triple.getPredicate(), triple.getObject()));
+		}
+		ti = g.filter(null, null, bNode);
+		while (ti.hasNext()) {
+			Triple triple = ti.next();
+			result.add(new BackwardProperty(triple.getSubject(), triple.getPredicate()));
+		}
+		return result;
+	}
+
+
+	private static Set<BNode> getBNodes(Collection<Triple> s) {
+		Set<BNode> result = new HashSet<BNode>();
+		for (Triple triple : s) {
+			if (triple.getSubject() instanceof BNode) {
+				result.add((BNode) triple.getSubject());
+			}
+			if (triple.getObject() instanceof BNode) {
+				result.add((BNode) triple.getObject());
+			}
+		}
+		return result;
+	}
+
+	
+	/**
+	 * removes the common grounded triples from s1 and s2. returns false if
+	 * a grounded triple is not in both sets, true otherwise
+	 */
+	private static boolean removeGrounded(Collection<Triple> s1, Collection<Triple>
s2) {
+		Iterator<Triple> triplesIter = s1.iterator();
+		while (triplesIter.hasNext()) {
+			Triple triple = triplesIter.next();
+			if (!isGrounded(triple)) {
+				continue;
+			}
+			if (!s2.remove(triple)) {
+				return false;
+			}
+			triplesIter.remove();
+		}
+		//for efficiency we might skip this (redefine method)
+		for (Triple triple : s2) {
+			if (isGrounded(triple)) {
+				return false;
+			}
+		}
+		return true;
+	}
+
+	private static boolean isGrounded(Triple triple) {
+		if (triple.getSubject() instanceof BNode) {
+			return false;
+		}
+		if (triple.getObject() instanceof BNode) {
+			return false;
+		}
+		return true;
+	}
+
+	private static IntHashMap<Set<BNode>> getHashNodes(Map<BNode,
+			Set<Property>> bNodePropMap, Map<BNode, Integer> bNodeHashMap) {
+		IntHashMap<Set<BNode>> result = new IntHashMap<Set<BNode>>();
+		for (Map.Entry<BNode, Set<Property>> entry : bNodePropMap.entrySet()) {
+			int hash = computeHash(entry.getValue(), bNodeHashMap);
+			Set<BNode> bNodeSet = result.get(hash);
+			if (bNodeSet == null) {
+				bNodeSet = new HashSet<BNode>();
+				result.put(hash,bNodeSet);
+			}
+			bNodeSet.add(entry.getKey());
+		}
+		return result;
+	}
+
+	private static void replaceNode(MGraph mGraph, BNode bNode, NonLiteral replacementNode)
{
+		Set<Triple> triplesToRemove = new HashSet<Triple>();
+		for (Triple triple : mGraph) {
+			Triple replacementTriple = getReplacement(triple, bNode, replacementNode);
+			if (replacementTriple != null) {
+				triplesToRemove.add(triple);
+				mGraph.add(replacementTriple);
+			}
+		}
+		mGraph.removeAll(triplesToRemove);
+	}
+
+	private static Triple getReplacement(Triple triple, BNode bNode, NonLiteral replacementNode)
{
+		if (triple.getSubject().equals(bNode)) {
+			if (triple.getObject().equals(bNode)) {
+				return new TripleImpl(replacementNode, triple.getPredicate(), replacementNode);
+			} else {
+				return new TripleImpl(replacementNode, triple.getPredicate(), triple.getObject());
+			}
+		} else {
+			if (triple.getObject().equals(bNode)) {
+				return new TripleImpl(triple.getSubject(), triple.getPredicate(), replacementNode);
+			} else {
+				return null;
+			}
+		}
+	}
+
+
+	/*
+	 * returns a Map from bnodes to hash that can be used for future
+	 * refinements, this could be separate for each graph.
+	 *
+	 * triples no longer containing an unmatched bnodes ae removed.
+	 *
+	 * Note that the matched node are not guaranteed to be equals, but only to
+	 * be the correct if the graphs are isomorphic.
+	 */
+	private static Map<BNode, Integer> matchByHashes(Map<BNode, BNode> matchings,
+			MGraph g1, MGraph g2, Map<BNode, Integer> bNodeHashMap) {
+		Map<BNode, Set<Property>> bNodePropMap1  = getBNodePropMap(g1);
+		Map<BNode, Set<Property>> bNodePropMap2  = getBNodePropMap(g2);
+		IntHashMap<Set<BNode>> hashNodeMap1 = getHashNodes(bNodePropMap1, bNodeHashMap);
+		IntHashMap<Set<BNode>> hashNodeMap2 = getHashNodes(bNodePropMap2, bNodeHashMap);
+		if (!hashNodeMap1.keySet().equals(hashNodeMap2.keySet())) {
+			return null;
+		}
+
+		IntIterator hashIter = hashNodeMap1.keySet().iterator();
+		while (hashIter.hasNext()) {
+			int hash = hashIter.next();
+			Set<BNode> nodes1 = hashNodeMap1.get(hash);
+			Set<BNode> nodes2 = hashNodeMap2.get(hash);
+			if (nodes1.size() != nodes2.size()) {
+				return null;
+			}
+			if (nodes1.size() != 1) {
+				continue;
+			}
+			final BNode bNode1 = nodes1.iterator().next();
+			final BNode bNode2 = nodes2.iterator().next();
+			matchings.put(bNode1,bNode2);
+			//in the graphs replace node occurences with grounded node,
+			NonLiteral mappedNode = new MappedNode(bNode1, bNode2);
+			replaceNode(g1,bNode1, mappedNode);
+			replaceNode(g2, bNode2, mappedNode);
+			//remove grounded triples
+			if (!removeGrounded(g1,g2)) {
+				return null;
+			}
+		}
+		Map<BNode, Integer> result = new HashMap<BNode, Integer>();
+		addInverted(result, hashNodeMap1);
+		addInverted(result, hashNodeMap2);
+		return result;
+	}
+
+	private static int computeHash(Set<Property> propertySet, Map<BNode, Integer>
bNodeHashMap) {
+		int result = 0;
+		for (Property property : propertySet) {
+			result += property.hashCode(bNodeHashMap);
+		}
+		return result;
+	}
+
+	private static Map<BNode, BNode> trialAndErrorMatching(MGraph g1, MGraph g2) {
+		Set<BNode> bn1  = getBNodes(g1);
+		Set<BNode> bn2  = getBNodes(g2);
+		Iterator<Map<BNode, BNode>> mappingIter = new MappintIterator(bn1,bn2);
+		while (mappingIter.hasNext()) {
+			Map<BNode, BNode> map = mappingIter.next();
+			if (checkMapping(g1, g2, map)) {
+				return map;
+			}
+		}
+		return null;
+	}
+
+	private static boolean checkMapping(MGraph g1, MGraph g2, Map<BNode, BNode> map) {
+		for (Triple triple : g1) {
+			if (!g2.contains(map(triple, map))) {
+				return false;
+			}
+		}
+		return true;
+	}
+
+	private static Triple map(Triple triple, Map<BNode, BNode> map) {
+		final NonLiteral oSubject = triple.getSubject();
+
+		NonLiteral subject = oSubject instanceof BNode ?
+			map.get((BNode)oSubject) : oSubject;
+
+		Resource oObject = triple.getObject();
+		Resource object = oObject instanceof BNode ?
+			map.get((BNode)oObject) : oObject;
+		return new TripleImpl(subject, triple.getPredicate(), object);
+	}
+
+	private static void addInverted(Map<BNode, Integer> result, IntHashMap<Set<BNode>>
hashNodeMap) {
+		for (int hash : hashNodeMap.keySet()) {
+			Set<BNode> bNodes = hashNodeMap.get(hash);
+			for (BNode bNode : bNodes) {
+				result.put(bNode, hash);
+			}
+		}
+	}
+
+	private static class MappedNode implements NonLiteral {
+		private BNode bNode1, bNode2;
+
+		public MappedNode(BNode bNode1, BNode bNode2) {
+			this.bNode1 = bNode1;
+			this.bNode2 = bNode2;
+		}
+		
+	}
+
+	private static int nodeHash(Resource resource, Map<BNode, Integer> bNodeHashMap) {
+		if (resource instanceof BNode) {
+			Integer mapValue = bNodeHashMap.get((BNode)resource);
+			if (mapValue == null) {
+				return 0;
+			} else {
+				return mapValue;
+			}
+		} else {
+			return resource.hashCode();
+		}
+	}
+
+	private static interface Property {
+		public int hashCode(Map<BNode, Integer> bNodeHashMap);
+	}
+
+	private static class ForwardProperty implements Property {
+		private UriRef predicate;
+		private Resource object;
+
+		public ForwardProperty(UriRef predicate, Resource object) {
+			this.predicate = predicate;
+			this.object = object;
+		}
+
+		@Override
+		public int hashCode(Map<BNode, Integer> bNodeHashMap) {
+			return predicate.hashCode() ^ nodeHash(object, bNodeHashMap);
+		}
+	}
+
+	private static class BackwardProperty implements Property {
+		private NonLiteral subject;
+		private UriRef predicate;
+
+		public BackwardProperty(NonLiteral subject, UriRef predicate) {
+			this.subject = subject;
+			this.predicate = predicate;
+		}
+
+		@Override
+		public int hashCode(Map<BNode, Integer> bNodeHashMap) {
+			return  0xFF ^ predicate.hashCode() ^ nodeHash(subject, bNodeHashMap);
+		}
+
+	}
+}

Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java?rev=899478&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java
(added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java
Thu Jan 14 23:45:59 2010
@@ -0,0 +1,378 @@
+
+
+/*
+ * Copyright 2002-2004 The Apache Software Foundation.
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * Note: originally released under the GNU LGPL v2.1, 
+ * but rereleased by the original author under the ASF license (above).
+ */
+package org.apache.clerezza.rdf.core.impl;
+
+import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntSet;
+
+/**
+ * <p>A hash map that uses primitive ints for the key rather than objects.</p>
+ *
+ * <p>Note that this class is for internal optimization purposes only, and may
+ * not be supported in future releases of Jakarta Commons Lang.  Utilities of
+ * this sort may be included in future releases of Jakarta Commons Collections.</p>
+ *
+ * @author Justin Couch
+ * @author Alex Chaffee (alex@apache.org)
+ * @author Stephen Colebourne
+ * @since 2.0
+ * @version $Revision: 1.2 $
+ * @see java.util.HashMap
+ */
+class  IntHashMap<T> {
+	
+	private IntSet keySet = new IntOpenHashSet();
+
+    /**
+     * The hash table data.
+     */
+    private transient Entry<T> table[];
+
+    /**
+     * The total number of entries in the hash table.
+     */
+    private transient int count;
+
+    /**
+     * The table is rehashed when its size exceeds this threshold.  (The
+     * value of this field is (int)(capacity * loadFactor).)
+     *
+     * @serial
+     */
+    private int threshold;
+
+    /**
+     * The load factor for the hashtable.
+     *
+     * @serial
+     */
+    private float loadFactor;
+
+    /**
+     * <p>Innerclass that acts as a datastructure to create a new entry in the
+     * table.</p>
+     */
+    private static class Entry<T> {
+        int hash;
+        int key;
+        T value;
+        Entry<T> next;
+
+        /**
+         * <p>Create a new entry with the given values.</p>
+         *
+         * @param hash The code used to hash the object with
+         * @param key The key used to enter this in the table
+         * @param value The value for this key
+         * @param next A reference to the next entry in the table
+         */
+        protected Entry(int hash, int key, T value, Entry<T> next) {
+            this.hash = hash;
+            this.key = key;
+            this.value = value;
+            this.next = next;
+        }
+    }
+
+    /**
+     * <p>Constructs a new, empty hashtable with a default capacity and load
+     * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
+     */
+    public IntHashMap() {
+        this(20, 0.75f);
+    }
+
+    /**
+     * <p>Constructs a new, empty hashtable with the specified initial capacity
+     * and default load factor, which is <code>0.75</code>.</p>
+     *
+     * @param  initialCapacity the initial capacity of the hashtable.
+     * @throws IllegalArgumentException if the initial capacity is less
+     *   than zero.
+     */
+    public IntHashMap(int initialCapacity) {
+        this(initialCapacity, 0.75f);
+    }
+
+    /**
+     * <p>Constructs a new, empty hashtable with the specified initial
+     * capacity and the specified load factor.</p>
+     *
+     * @param initialCapacity the initial capacity of the hashtable.
+     * @param loadFactor the load factor of the hashtable.
+     * @throws IllegalArgumentException  if the initial capacity is less
+     *             than zero, or if the load factor is nonpositive.
+     */
+    public IntHashMap(int initialCapacity, float loadFactor) {
+        super();
+        if (initialCapacity < 0) {
+            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
+        }
+        if (loadFactor <= 0) {
+            throw new IllegalArgumentException("Illegal Load: " + loadFactor);
+        }
+        if (initialCapacity == 0) {
+            initialCapacity = 1;
+        }
+
+        this.loadFactor = loadFactor;
+        table = new Entry[initialCapacity];
+        threshold = (int) (initialCapacity * loadFactor);
+    }
+
+    /**
+     * <p>Returns the number of keys in this hashtable.</p>
+     *
+     * @return  the number of keys in this hashtable.
+     */
+    public int size() {
+        return count;
+    }
+
+    /**
+     * <p>Tests if this hashtable maps no keys to values.</p>
+     *
+     * @return  <code>true</code> if this hashtable maps no keys to values;
+     *          <code>false</code> otherwise.
+     */
+    public boolean isEmpty() {
+        return count == 0;
+    }
+
+    /**
+     * <p>Tests if some key maps into the specified value in this hashtable.
+     * This operation is more expensive than the <code>containsKey</code>
+     * method.</p>
+     *
+     * <p>Note that this method is identical in functionality to containsValue,
+     * (which is part of the Map interface in the collections framework).</p>
+     *
+     * @param      value   a value to search for.
+     * @return     <code>true</code> if and only if some key maps to the
+     *             <code>value</code> argument in this hashtable as
+     *             determined by the <tt>equals</tt> method;
+     *             <code>false</code> otherwise.
+     * @throws  NullPointerException  if the value is <code>null</code>.
+     * @see        #containsKey(int)
+     * @see        #containsValue(Object)
+     * @see        java.util.Map
+     */
+    public boolean contains(Object value) {
+        if (value == null) {
+            throw new NullPointerException();
+        }
+
+        Entry tab[] = table;
+        for (int i = tab.length; i-- > 0;) {
+            for (Entry e = tab[i]; e != null; e = e.next) {
+                if (e.value.equals(value)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    /**
+     * <p>Returns <code>true</code> if this HashMap maps one or more keys
+     * to this value.</p>
+     *
+     * <p>Note that this method is identical in functionality to contains
+     * (which predates the Map interface).</p>
+     *
+     * @param value value whose presence in this HashMap is to be tested.
+     * @see    java.util.Map
+     * @since JDK1.2
+     */
+    public boolean containsValue(Object value) {
+        return contains(value);
+    }
+
+    /**
+     * <p>Tests if the specified object is a key in this hashtable.</p>
+     *
+     * @param  key  possible key.
+     * @return <code>true</code> if and only if the specified object is a
+     *    key in this hashtable, as determined by the <tt>equals</tt>
+     *    method; <code>false</code> otherwise.
+     * @see #contains(Object)
+     */
+    public boolean containsKey(int key) {
+        Entry tab[] = table;
+        int hash = key;
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+        for (Entry e = tab[index]; e != null; e = e.next) {
+            if (e.hash == hash) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * <p>Returns the value to which the specified key is mapped in this map.</p>
+     *
+     * @param   key   a key in the hashtable.
+     * @return  the value to which the key is mapped in this hashtable;
+     *          <code>null</code> if the key is not mapped to any value in
+     *          this hashtable.
+     * @see     #put(int, Object)
+     */
+    public T get(int key) {
+        Entry<T> tab[] = table;
+        int hash = key;
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+        for (Entry<T> e = tab[index]; e != null; e = e.next) {
+            if (e.hash == hash) {
+                return e.value;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * <p>Increases the capacity of and internally reorganizes this
+     * hashtable, in order to accommodate and access its entries more
+     * efficiently.</p>
+     *
+     * <p>This method is called automatically when the number of keys
+     * in the hashtable exceeds this hashtable's capacity and load
+     * factor.</p>
+     */
+    protected void rehash() {
+        int oldCapacity = table.length;
+        Entry<T> oldMap[] = table;
+
+        int newCapacity = oldCapacity * 2 + 1;
+        Entry<T> newMap[] = new Entry[newCapacity];
+
+        threshold = (int) (newCapacity * loadFactor);
+        table = newMap;
+
+        for (int i = oldCapacity; i-- > 0;) {
+            for (Entry<T> old = oldMap[i]; old != null;) {
+                Entry<T> e = old;
+                old = old.next;
+
+                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
+                e.next = newMap[index];
+                newMap[index] = e;
+            }
+        }
+    }
+
+    /**
+     * <p>Maps the specified <code>key</code> to the specified
+     * <code>value</code> in this hashtable. The key cannot be
+     * <code>null</code>. </p>
+     *
+     * <p>The value can be retrieved by calling the <code>get</code> method
+     * with a key that is equal to the original key.</p>
+     *
+     * @param key     the hashtable key.
+     * @param value   the value.
+     * @return the previous value of the specified key in this hashtable,
+     *         or <code>null</code> if it did not have one.
+     * @throws  NullPointerException  if the key is <code>null</code>.
+     * @see     #get(int)
+     */
+    public Object put(int key, T value) {
+    		keySet.add(key);
+        // Makes sure the key is not already in the hashtable.
+        Entry<T> tab[] = table;
+        int hash = key;
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+        for (Entry<T> e = tab[index]; e != null; e = e.next) {
+            if (e.hash == hash) {
+                T old = e.value;
+                e.value = value;
+                return old;
+            }
+        }
+
+        if (count >= threshold) {
+            // Rehash the table if the threshold is exceeded
+            rehash();
+
+            tab = table;
+            index = (hash & 0x7FFFFFFF) % tab.length;
+        }
+
+        // Creates the new entry.
+        Entry<T> e = new Entry<T>(hash, key, value, tab[index]);
+        tab[index] = e;
+        count++;
+        return null;
+    }
+
+    /**
+     * <p>Removes the key (and its corresponding value) from this
+     * hashtable.</p>
+     *
+     * <p>This method does nothing if the key is not present in the
+     * hashtable.</p>
+     *
+     * @param   key   the key that needs to be removed.
+     * @return  the value to which the key had been mapped in this hashtable,
+     *          or <code>null</code> if the key did not have a mapping.
+     */
+    /*public Object remove(int key) {
+        Entry tab[] = table;
+        int hash = key;
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+        for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
+            if (e.hash == hash) {
+                if (prev != null) {
+                    prev.next = e.next;
+                } else {
+                    tab[index] = e.next;
+                }
+                count--;
+                Object oldValue = e.value;
+                e.value = null;
+                return oldValue;
+            }
+        }
+        return null;
+    }*/
+
+    /**
+     * <p>Clears this hashtable so that it contains no keys.</p>
+     */
+    public synchronized void clear() {
+    		keySet.clear();
+        Entry tab[] = table;
+        for (int index = tab.length; --index >= 0;) {
+            tab[index] = null;
+        }
+        count = 0;
+    }
+    
+    public IntSet keySet() {
+    		return keySet;
+    }
+    
+    
+    
+}
+

Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java?rev=899478&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java
(added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java
Thu Jan 14 23:45:59 2010
@@ -0,0 +1,73 @@
+/*
+ *  Copyright 2010 reto.
+ * 
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ *  under the License.
+ */
+
+package org.apache.clerezza.rdf.core.impl;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * An iterator over all possible mapping beetween the elemnets of two sets of
+ * the same size, each mapping maps each element from set1 to a disctinct one of
+ * set2.
+ *
+ *
+ *
+ * @author reto
+ */
+class MappintIterator<T,U> implements Iterator<Map<T, U>> {
+
+	private List<T> list1;
+	private Iterator<List<U>> permutationList2Iterator;
+
+
+	public MappintIterator(Set<T> set1, Set<U> set2) {
+		if (set1.size() != set2.size()) {
+			throw new IllegalArgumentException();
+		}
+		this.list1 = new ArrayList<T>(set1);
+		permutationList2Iterator = new PermutationIterator<U>(
+				new ArrayList<U>(set2));
+	}
+
+	@Override
+	public boolean hasNext() {
+		return permutationList2Iterator.hasNext();
+	}
+
+	@Override
+	public Map<T, U> next() {
+		List<U> list2 = permutationList2Iterator.next();
+		Map<T, U> result = new HashMap<T, U>(list1.size());
+		for (int i = 0; i < list1.size(); i++) {
+			result.put(list1.get(i), list2.get(i));
+		}
+		return result;
+	}
+
+	@Override
+	public void remove() {
+		throw new UnsupportedOperationException("Not supported.");
+	}
+
+
+
+}

Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java?rev=899478&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java
(added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java
Thu Jan 14 23:45:59 2010
@@ -0,0 +1,99 @@
+/*
+ *  Copyright 2010 reto.
+ * 
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ *  under the License.
+ */
+
+package org.apache.clerezza.rdf.core.impl;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ *
+ * An Iterator over all permuations of a list.
+ *
+ * @author reto
+ */
+class PermutationIterator<T> implements Iterator<List<T>> {
+
+	private Iterator<List<T>> restIterator;
+	private List<T> list;
+	private List<T> next;
+	int posInList = 0; //the position of the last element of next returned list
+	//with list, this is the one excluded from restIterator
+
+	PermutationIterator(List<T> list) {
+		this.list = Collections.unmodifiableList(list);
+		if (list.size() > 1) {
+			createRestList();
+		}
+		prepareNext();
+	}
+
+	@Override
+	public boolean hasNext() {
+		return next != null;
+	}
+
+	@Override
+	public List<T> next() {
+		List<T> result = next;
+		prepareNext();
+		return result;
+	}
+
+	@Override
+	public void remove() {
+		throw new UnsupportedOperationException("Not supported");
+	}
+
+	private void createRestList() {
+		List<T> restList = new ArrayList<T>(list);
+		restList.remove(posInList);
+		restIterator = new PermutationIterator<T>(restList);
+	}
+
+	private void prepareNext() {
+		next = getNext();
+		
+	}
+	private List<T> getNext() {
+		if (list.size() == 0) {
+			return null;
+		}
+		if (list.size() == 1) {
+			if (posInList++ == 0) {
+				return new ArrayList<T>(list);
+			} else {
+				return null;
+			}
+		} else {
+			if (!restIterator.hasNext()) {
+				if (posInList < (list.size()-1)) {
+					posInList++;
+					createRestList();
+				} else {
+					return null;
+				}
+			}
+			List<T> result = restIterator.next();
+			result.add(list.get(posInList));
+			return result;
+		}
+	}
+
+}

Modified: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleMGraph.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleMGraph.java?rev=899478&r1=897462&r2=899478&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleMGraph.java
(original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleMGraph.java
Thu Jan 14 23:45:59 2010
@@ -18,6 +18,7 @@
  */
 package org.apache.clerezza.rdf.core.impl;
 
+import java.util.Collection;
 import java.util.Iterator;
 import java.util.Set;
 
@@ -41,6 +42,10 @@
 		super(baseSet);
 	}
 
+	public SimpleMGraph(Collection<Triple> baseCollection) {
+		super(baseCollection);
+	}
+
 	public SimpleMGraph(Iterator<Triple> iterator) {
 		super(iterator);
 	}

Modified: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleTripleCollection.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleTripleCollection.java?rev=899478&r1=897462&r2=899478&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleTripleCollection.java
(original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/SimpleTripleCollection.java
Thu Jan 14 23:45:59 2010
@@ -19,6 +19,7 @@
 package org.apache.clerezza.rdf.core.impl;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
@@ -73,6 +74,16 @@
 		this.triples = baseSet;
 	}
 
+	/**
+	 * Creates a SimpleTripleCollection for the specified collection of triples,
+	 * subsequent modification of baseSet do not affect the created instance.
+	 *
+	 * @param baseSet
+	 */
+	public SimpleTripleCollection(Collection<Triple> baseCollection) {
+		this.triples = new HashSet<Triple>(baseCollection);
+	}
+
 	@Override
 	public int size() {
 		return triples.size();

Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java?rev=899478&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java
(added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java
Thu Jan 14 23:45:59 2010
@@ -0,0 +1,182 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.clerezza.rdf.core.impl;
+
+import java.util.Map;
+import org.apache.clerezza.rdf.core.BNode;
+import org.apache.clerezza.rdf.core.MGraph;
+import org.apache.clerezza.rdf.core.NonLiteral;
+import org.apache.clerezza.rdf.core.Resource;
+import org.apache.clerezza.rdf.core.Triple;
+import org.apache.clerezza.rdf.core.TripleCollection;
+import org.apache.clerezza.rdf.core.UriRef;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ *
+ * @author reto
+ */
+public class GraphMatcherTest {
+
+	final UriRef u1 = new UriRef("http://example.org/u1");
+
+	@Test
+	public void testEmpty() {
+		TripleCollection tc1 = new SimpleMGraph();
+		TripleCollection tc2 = new SimpleMGraph();
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		Assert.assertEquals(0, mapping.size());
+	}
+
+	@Test
+	public void test2() {
+		TripleCollection tc1 = new SimpleMGraph();
+		tc1.add(new TripleImpl(u1, u1, u1));
+		TripleCollection tc2 = new SimpleMGraph();
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNull(mapping);
+	}
+
+	@Test
+	public void test3() {
+		TripleCollection tc1 = new SimpleMGraph();
+		tc1.add(new TripleImpl(u1, u1, u1));
+		TripleCollection tc2 = new SimpleMGraph();
+		tc2.add(new TripleImpl(u1, u1, u1));
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		Assert.assertEquals(0, mapping.size());
+	}
+
+	@Test
+	public void test4() {
+		TripleCollection tc1 = new SimpleMGraph();
+		tc1.add(new TripleImpl(u1, u1, new BNode()));
+		TripleCollection tc2 = new SimpleMGraph();
+		tc2.add(new TripleImpl(u1, u1, new BNode()));
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		Assert.assertEquals(1, mapping.size());
+	}
+
+	@Test
+	public void test5() {
+		TripleCollection tc1 = new SimpleMGraph();
+		tc1.add(new TripleImpl(new BNode(), u1, new BNode()));
+		TripleCollection tc2 = new SimpleMGraph();
+		tc2.add(new TripleImpl(new BNode(), u1, new BNode()));
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		Assert.assertEquals(2, mapping.size());
+	}
+
+	@Test
+	public void test6() {
+		TripleCollection tc1 = new SimpleMGraph();
+		final BNode b11 = new BNode();
+		tc1.add(new TripleImpl(new BNode(), u1,b11));
+		tc1.add(new TripleImpl(new BNode(), u1,b11));
+		TripleCollection tc2 = new SimpleMGraph();
+		tc2.add(new TripleImpl(new BNode(), u1, new BNode()));
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNull(mapping);
+	}
+
+	private MGraph generateCircle(int size) {
+		return generateCircle(size, new BNode());
+	}
+
+	private MGraph generateCircle(int size, final NonLiteral firstNode) {
+		if (size < 1) {
+			throw new IllegalArgumentException();
+		}
+		MGraph result = new SimpleMGraph();
+		NonLiteral lastNode = firstNode;
+		for (int i = 0; i < (size-1); i++) {
+			final BNode newNode = new BNode();
+			result.add(new TripleImpl(lastNode, u1, newNode));
+			lastNode = newNode;
+		}
+		result.add(new TripleImpl(lastNode, u1, firstNode));
+		return result;
+	}
+
+	@Test
+	public void test7() {
+		TripleCollection tc1 = generateCircle(2);
+		TripleCollection tc2 = generateCircle(2);
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		Assert.assertEquals(2, mapping.size());
+	}
+
+	@Test
+	public void test8() {
+		TripleCollection tc1 = generateCircle(5);
+		TripleCollection tc2 = generateCircle(5);
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		Assert.assertEquals(5, mapping.size());
+	}
+
+	@Test
+	public void test9() {
+		NonLiteral crossing = new UriRef("http://example.org/");
+		TripleCollection tc1 = generateCircle(2,crossing);
+		tc1.addAll(generateCircle(3,crossing));
+		TripleCollection tc2 = generateCircle(2,crossing);
+		tc2.addAll(generateCircle(3,crossing));
+		Assert.assertEquals(5, tc1.size());
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		//a circle of 2 with 1 bnode and one of 2 bnodes
+		Assert.assertEquals(3, mapping.size());
+	}
+
+	@Test
+	public void test10() {
+		NonLiteral crossing1 = new BNode();
+		TripleCollection tc1 = generateCircle(2,crossing1);
+		tc1.addAll(generateCircle(3,crossing1));
+		NonLiteral crossing2 = new BNode();
+		TripleCollection tc2 = generateCircle(2,crossing2);
+		tc2.addAll(generateCircle(3,crossing2));
+		Assert.assertEquals(5, tc1.size());
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNotNull(mapping);
+		//a circle of 2 and one of 3 with one common node
+		Assert.assertEquals(4, mapping.size());
+	}
+
+	@Test
+	public void test11() {
+		NonLiteral crossing1 = new BNode();
+		TripleCollection tc1 = generateCircle(2,crossing1);
+		tc1.addAll(generateCircle(4,crossing1));
+		NonLiteral crossing2 = new BNode();
+		TripleCollection tc2 = generateCircle(3,crossing2);
+		tc2.addAll(generateCircle(3,crossing2));
+		Assert.assertEquals(6, tc1.size());
+		final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+		Assert.assertNull(mapping);
+
+	}
+}

Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java
URL: http://svn.apache.org/viewvc/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java?rev=899478&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java
(added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java
Thu Jan 14 23:45:59 2010
@@ -0,0 +1,75 @@
+/*
+ *  Copyright 2010 reto.
+ * 
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ *  under the License.
+ */
+
+package org.apache.clerezza.rdf.core.impl;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ *
+ * @author reto
+ */
+public class PermutationIteratorTest {
+
+	@Test
+	public void simple() {
+		List<String> list = new ArrayList<String>();
+		PermutationIterator<String> pi = new PermutationIterator<String>(list);
+		Assert.assertFalse(pi.hasNext());
+	}
+
+	@Test
+	public void lessSimple() {
+		List<String> list = new ArrayList<String>();
+		list.add("Hasan");
+		PermutationIterator<String> pi = new PermutationIterator<String>(list);
+		Assert.assertTrue(pi.hasNext());
+	}
+
+	@Test
+	public void regular() {
+		List<String> list = new ArrayList<String>();
+		list.add("Hasan");
+		list.add("Tsuy");
+		PermutationIterator<String> pi = new PermutationIterator<String>(list);
+		Set<List<String>> permutations = new HashSet<List<String>>();
+		while (pi.hasNext()) {
+			permutations.add(pi.next());
+		}
+		Assert.assertEquals(2, permutations.size());
+	}
+
+	@Test
+	public void extended() {
+		List<String> list = new ArrayList<String>();
+		list.add("Hasan");
+		list.add("Tsuy");
+		list.add("Llena");
+		PermutationIterator<String> pi = new PermutationIterator<String>(list);
+		Set<List<String>> permutations = new HashSet<List<String>>();
+		while (pi.hasNext()) {
+			permutations.add(pi.next());
+		}
+		Assert.assertEquals(6, permutations.size());
+	}
+
+}



Mime
View raw message