You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@clerezza.apache.org by re...@apache.org on 2010/01/15 00:46:00 UTC
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/
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());
+ }
+
+}