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/20 12:43:42 UTC
svn commit: r901145 - in
/incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src:
main/java/org/apache/clerezza/rdf/core/impl/
main/java/org/apache/clerezza/rdf/core/impl/graphmatching/
test/java/org/apache/clerezza/rdf/core/impl/ test/...
Author: reto
Date: Wed Jan 20 11:43:41 2010
New Revision: 901145
URL: http://svn.apache.org/viewvc?rev=901145&view=rev
Log:
CLEREZZA-67: proposed solution to be improved in CLEREZZA-81
Added:
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcher.java
- copied, changed from r899478, 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/graphmatching/GraphNotIsomorphicException.java
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GroupMappingIterator.java
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/HashMatching.java
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/IntHashMap.java
- copied, changed from r899478, 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/graphmatching/MappingIterator.java
- copied, changed from r899478, 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/graphmatching/PermutationIterator.java
- copied, changed from r899478, 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/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils.java
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcherTest.java
- copied, changed from r899478, 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/graphmatching/HashMatchingTest.java
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIteratorTest.java
- copied, changed from r899478, incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java
incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils4Testing.java
Removed:
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/src/main/java/org/apache/clerezza/rdf/core/impl/AbstractGraph.java
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=901145&r1=901144&r2=901145&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 Wed Jan 20 11:43:41 2010
@@ -25,6 +25,7 @@
import org.apache.clerezza.rdf.core.Graph;
import org.apache.clerezza.rdf.core.Resource;
import org.apache.clerezza.rdf.core.Triple;
+import org.apache.clerezza.rdf.core.impl.graphmatching.GraphMatcher;
/**
* <code>AbstractGraph</code> is an abstract implementation of <code>Graph</code>
Copied: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcher.java (from r899478, 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/graphmatching/GraphMatcher.java?p2=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcher.java&p1=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java&r1=899478&r2=901145&rev=901145&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/GraphMatcher.java (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcher.java Wed Jan 20 11:43:41 2010
@@ -16,22 +16,14 @@
* 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;
+package org.apache.clerezza.rdf.core.impl.graphmatching;
+
+
-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;
@@ -39,7 +31,8 @@
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.apache.clerezza.rdf.core.impl.SimpleMGraph;
+import org.apache.clerezza.rdf.core.impl.TripleImpl;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -49,7 +42,6 @@
*/
public class GraphMatcher {
- static private Random random = new Random(0);
private final static Logger log = LoggerFactory.getLogger(GraphMatcher.class);
@@ -83,215 +75,40 @@
public static Map<BNode, BNode> getValidMapping(TripleCollection og1, TripleCollection og2) {
MGraph g1 = new SimpleMGraph(og1);
MGraph g2 = new SimpleMGraph(og2);
- if (!removeGrounded(g1,g2)) {
+ if (!Utils.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();
+ final HashMatching hashMatching;
+ try {
+ hashMatching = new HashMatching(g1, g2);
+ } catch (GraphNotIsomorphicException ex) {
+ return null;
}
+ Map<BNode, BNode> matchings = hashMatching.getMatchings();
if (g1.size() > 0) {
//start trial an error matching
- Map<BNode, BNode> remainingMappings = trialAndErrorMatching(g1, g2);
+ //TODO (CLEREZZA-81) at least in the situation where one matching
+ //group is big (approx > 5) we should switch back to hash-based matching
+ //after a first guessed matching, rather than try all permutations
+ Map<BNode, BNode> remainingMappings = trialAndErrorMatching(g1, g2, hashMatching.getMatchingGroups());
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()));
+ private static Map<BNode, BNode> trialAndErrorMatching(MGraph g1, MGraph g2,
+ Map<Set<BNode>, Set<BNode>> matchingGroups) {
+ if (log.isDebugEnabled()) {
+ Set<BNode> bn1 = Utils.getBNodes(g1);
+ log.debug("doing trial and error matching for {} bnodes, " +
+ "in graphs of size: {}.", bn1.size(), g1.size());
}
- 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);
+ Iterator<Map<BNode, BNode>> mappingIter
+ = GroupMappingIterator.create(matchingGroups);
while (mappingIter.hasNext()) {
Map<BNode, BNode> map = mappingIter.next();
if (checkMapping(g1, g2, map)) {
@@ -322,70 +139,5 @@
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/graphmatching/GraphNotIsomorphicException.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/graphmatching/GraphNotIsomorphicException.java?rev=901145&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphNotIsomorphicException.java (added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphNotIsomorphicException.java Wed Jan 20 11:43:41 2010
@@ -0,0 +1,28 @@
+/*
+ * 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.graphmatching;
+
+/**
+ *
+ * @author reto
+ */
+class GraphNotIsomorphicException extends Exception {
+
+}
Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GroupMappingIterator.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/graphmatching/GroupMappingIterator.java?rev=901145&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GroupMappingIterator.java (added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/GroupMappingIterator.java Wed Jan 20 11:43:41 2010
@@ -0,0 +1,96 @@
+/*
+ * 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.graphmatching;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Iterates over all mappings from each element of every Set<T> to each
+ * elemenent of their corresponding Set<U>.
+ *
+ * @author reto
+ */
+class GroupMappingIterator<T,U> implements Iterator<Map<T, U>> {
+
+ private Iterator<Map<T, U>> firstPartIter;
+ private Map<T, U> currentFirstPart;
+ final private Map<Set<T>, Set<U>> restMap;
+ private Iterator<Map<T, U>> currentRestPartIter;
+
+ static <T,U> Iterator<Map<T, U>> create(Map<Set<T>, Set<U>> matchingGroups) {
+ if (matchingGroups.size() > 1) {
+ return new GroupMappingIterator<T, U>(matchingGroups);
+ } else {
+ if (matchingGroups.size() == 0) {
+ return new ArrayList<Map<T, U>>(0).iterator();
+ }
+ Map.Entry<Set<T>, Set<U>> entry = matchingGroups.entrySet().iterator().next();
+ return new MappingIterator<T,U>(entry.getKey(),
+ entry.getValue());
+ }
+ }
+
+ private GroupMappingIterator(Map<Set<T>, Set<U>> matchingGroups) {
+ restMap = new HashMap<Set<T>, Set<U>>();
+ boolean first = true;
+ for (Map.Entry<Set<T>, Set<U>> entry : matchingGroups.entrySet()) {
+ if (first) {
+ firstPartIter = new MappingIterator<T,U>(entry.getKey(),
+ entry.getValue());
+ first = false;
+ } else {
+ restMap.put(entry.getKey(), entry.getValue());
+ }
+ }
+ currentRestPartIter = create(restMap);
+ currentFirstPart = firstPartIter.next();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return firstPartIter.hasNext() || currentRestPartIter.hasNext();
+ }
+
+ @Override
+ public Map<T, U> next() {
+ Map<T, U> restPart = currentRestPartIter.next();
+ if (restPart == null) {
+ if (firstPartIter.hasNext()) {
+ currentFirstPart = firstPartIter.next();
+ currentRestPartIter = new GroupMappingIterator<T, U>(restMap);
+ restPart = currentRestPartIter.next();
+ } else {
+ return null;
+ }
+ }
+ Map<T, U> result = new HashMap<T, U>(restPart);
+ result.putAll(currentFirstPart);
+ 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/graphmatching/HashMatching.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/graphmatching/HashMatching.java?rev=901145&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/HashMatching.java (added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/HashMatching.java Wed Jan 20 11:43:41 2010
@@ -0,0 +1,267 @@
+/*
+ * 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.graphmatching;
+
+import it.unimi.dsi.fastutil.ints.IntIterator;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+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.Resource;
+import org.apache.clerezza.rdf.core.Triple;
+import org.apache.clerezza.rdf.core.TripleCollection;
+import org.apache.clerezza.rdf.core.UriRef;
+import org.apache.clerezza.rdf.core.impl.TripleImpl;
+
+/**
+ *
+ * @author reto
+ */
+public class HashMatching {
+
+ private Map<BNode, BNode> matchings = new HashMap<BNode, BNode>();
+ private Map<Set<BNode>, Set<BNode>> matchingGroups;
+
+ /**
+ * tc1 and tc2 will be modified: the triples containing no unmatched bnode
+ * will be removed
+ *
+ * @param tc1
+ * @param tc2
+ * @throws GraphNotIsomorphicException
+ */
+ HashMatching(MGraph tc1, MGraph tc2) throws GraphNotIsomorphicException {
+ int foundMatchings = 0;
+ int foundMatchingGroups = 0;
+ Map<BNode, Integer> bNodeHashMap = new HashMap<BNode, Integer>();
+ while (true) {
+ bNodeHashMap = matchByHashes(tc1, tc2, bNodeHashMap);
+ if (bNodeHashMap == null) {
+ throw new GraphNotIsomorphicException();
+ }
+ if (matchings.size() == foundMatchings) {
+ if (!(matchingGroups.size() > foundMatchingGroups)) {
+ break;
+ }
+ }
+ foundMatchings = matchings.size();
+ foundMatchingGroups = matchingGroups.size();
+ }
+ }
+
+ /**
+ *
+ * @return a map containing set of which each bnodes mappes one of the other set
+ */
+ public Map<Set<BNode>, Set<BNode>> getMatchingGroups() {
+ return matchingGroups;
+ }
+
+ public Map<BNode, BNode> getMatchings() {
+ return matchings;
+ }
+
+
+ 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;
+ }
+ /*
+ * 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 Map<BNode, Integer> matchByHashes(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;
+ }
+
+ matchingGroups = new HashMap<Set<BNode>, Set<BNode>>();
+ 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) {
+ matchingGroups.put(nodes1, nodes2);
+ 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 (!Utils.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, Set<Property>> getBNodePropMap(MGraph g) {
+ Set<BNode> bNodes = Utils.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 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 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;
+ }
+ }
+ }
+ 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 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);
+ }
+
+ }
+ 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 MappedNode implements NonLiteral {
+ private BNode bNode1, bNode2;
+
+ public MappedNode(BNode bNode1, BNode bNode2) {
+ this.bNode1 = bNode1;
+ this.bNode2 = bNode2;
+ }
+
+ }
+ private static interface Property {
+ public int hashCode(Map<BNode, Integer> bNodeHashMap);
+ }
+}
Copied: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/IntHashMap.java (from r899478, 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/graphmatching/IntHashMap.java?p2=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/IntHashMap.java&p1=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java&r1=899478&r2=901145&rev=901145&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/IntHashMap.java (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/IntHashMap.java Wed Jan 20 11:43:41 2010
@@ -1,5 +1,3 @@
-
-
/*
* Copyright 2002-2004 The Apache Software Foundation.
*
@@ -20,7 +18,8 @@
* 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;
+
+package org.apache.clerezza.rdf.core.impl.graphmatching;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
import it.unimi.dsi.fastutil.ints.IntSet;
Copied: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/MappingIterator.java (from r899478, 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/graphmatching/MappingIterator.java?p2=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/MappingIterator.java&p1=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java&r1=899478&r2=901145&rev=901145&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/MappintIterator.java (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/MappingIterator.java Wed Jan 20 11:43:41 2010
@@ -1,21 +1,24 @@
+package org.apache.clerezza.rdf.core.impl.graphmatching;
+
/*
- * 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.
+ * 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.ArrayList;
import java.util.HashMap;
@@ -33,13 +36,13 @@
*
* @author reto
*/
-class MappintIterator<T,U> implements Iterator<Map<T, U>> {
+class MappingIterator<T,U> implements Iterator<Map<T, U>> {
private List<T> list1;
private Iterator<List<U>> permutationList2Iterator;
- public MappintIterator(Set<T> set1, Set<U> set2) {
+ public MappingIterator(Set<T> set1, Set<U> set2) {
if (set1.size() != set2.size()) {
throw new IllegalArgumentException();
}
Copied: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIterator.java (from r899478, 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/graphmatching/PermutationIterator.java?p2=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIterator.java&p1=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java&r1=899478&r2=901145&rev=901145&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/PermutationIterator.java (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIterator.java Wed Jan 20 11:43:41 2010
@@ -1,21 +1,25 @@
/*
- * 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.
+ * 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;
+package org.apache.clerezza.rdf.core.impl.graphmatching;
+
+
import java.util.ArrayList;
import java.util.Collections;
Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils.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/graphmatching/Utils.java?rev=901145&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils.java (added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/main/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils.java Wed Jan 20 11:43:41 2010
@@ -0,0 +1,61 @@
+package org.apache.clerezza.rdf.core.impl.graphmatching;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+import org.apache.clerezza.rdf.core.BNode;
+import org.apache.clerezza.rdf.core.Triple;
+
+public class Utils {
+
+ 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
+ */
+ 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;
+ }
+
+}
Copied: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcherTest.java (from r899478, 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/graphmatching/GraphMatcherTest.java?p2=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcherTest.java&p1=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java&r1=899478&r2=901145&rev=901145&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/GraphMatcherTest.java (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/GraphMatcherTest.java Wed Jan 20 11:43:41 2010
@@ -16,7 +16,7 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.apache.clerezza.rdf.core.impl;
+package org.apache.clerezza.rdf.core.impl.graphmatching;
import java.util.Map;
import org.apache.clerezza.rdf.core.BNode;
@@ -26,6 +26,8 @@
import org.apache.clerezza.rdf.core.Triple;
import org.apache.clerezza.rdf.core.TripleCollection;
import org.apache.clerezza.rdf.core.UriRef;
+import org.apache.clerezza.rdf.core.impl.SimpleMGraph;
+import org.apache.clerezza.rdf.core.impl.TripleImpl;
import org.junit.Assert;
import org.junit.Test;
@@ -35,7 +37,7 @@
*/
public class GraphMatcherTest {
- final UriRef u1 = new UriRef("http://example.org/u1");
+ final static UriRef u1 = new UriRef("http://example.org/u1");
@Test
public void testEmpty() {
@@ -177,6 +179,32 @@
Assert.assertEquals(6, tc1.size());
final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
Assert.assertNull(mapping);
+ }
+
+ @Test
+ public void test12() {
+ NonLiteral start1 = new BNode();
+ TripleCollection tc1 = Utils4Testing.generateLine(4,start1);
+ tc1.addAll(Utils4Testing.generateLine(5,start1));
+ NonLiteral start2 = new BNode();
+ TripleCollection tc2 = Utils4Testing.generateLine(5,start2);
+ tc2.addAll(Utils4Testing.generateLine(4,start2));
+ Assert.assertEquals(9, tc1.size());
+ final Map<BNode, BNode> mapping = GraphMatcher.getValidMapping(tc1, tc2);
+ Assert.assertNotNull(mapping);
+ Assert.assertEquals(10, mapping.size());
+ }
+ @Test
+ public void test13() {
+ NonLiteral start1 = new BNode();
+ TripleCollection tc1 = Utils4Testing.generateLine(4,start1);
+ tc1.addAll(Utils4Testing.generateLine(5,start1));
+ NonLiteral start2 = new BNode();
+ TripleCollection tc2 = Utils4Testing.generateLine(3,start2);
+ tc2.addAll(Utils4Testing.generateLine(3,start2));
+ Assert.assertEquals(9, 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/graphmatching/HashMatchingTest.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/graphmatching/HashMatchingTest.java?rev=901145&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/HashMatchingTest.java (added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/HashMatchingTest.java Wed Jan 20 11:43:41 2010
@@ -0,0 +1,50 @@
+/*
+ * 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.graphmatching;
+
+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.junit.Assert;
+import org.junit.Test;
+
+/**
+ *
+ * @author reto
+ */
+public class HashMatchingTest {
+
+ @Test
+ public void twoLine() throws GraphNotIsomorphicException {
+ NonLiteral start1 = new BNode();
+ MGraph tc1 = Utils4Testing.generateLine(4,start1);
+ tc1.addAll(Utils4Testing.generateLine(5,start1));
+ NonLiteral start2 = new BNode();
+ MGraph tc2 = Utils4Testing.generateLine(5,start2);
+ tc2.addAll(Utils4Testing.generateLine(4,start2));
+ Assert.assertEquals(9, tc1.size());
+ final Map<BNode, BNode> mapping = new HashMatching(tc1, tc2).getMatchings();
+ Assert.assertNotNull(mapping);
+ Assert.assertEquals(10, mapping.size());
+ }
+
+}
Copied: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIteratorTest.java (from r899478, 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/graphmatching/PermutationIteratorTest.java?p2=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIteratorTest.java&p1=incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java&r1=899478&r2=901145&rev=901145&view=diff
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/PermutationIteratorTest.java (original)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/PermutationIteratorTest.java Wed Jan 20 11:43:41 2010
@@ -1,21 +1,23 @@
/*
- * 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.
+ * 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;
+package org.apache.clerezza.rdf.core.impl.graphmatching;
import java.util.ArrayList;
import java.util.HashSet;
Added: incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils4Testing.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/graphmatching/Utils4Testing.java?rev=901145&view=auto
==============================================================================
--- incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils4Testing.java (added)
+++ incubator/clerezza/issues/CLEREZZA-67/org.apache.clerezza.rdf.core/src/test/java/org/apache/clerezza/rdf/core/impl/graphmatching/Utils4Testing.java Wed Jan 20 11:43:41 2010
@@ -0,0 +1,51 @@
+/*
+ * 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.graphmatching;
+
+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.UriRef;
+import org.apache.clerezza.rdf.core.impl.SimpleMGraph;
+import org.apache.clerezza.rdf.core.impl.TripleImpl;
+
+/**
+ *
+ * @author reto
+ */
+public class Utils4Testing {
+
+ static MGraph generateLine(int size, final NonLiteral firstNode) {
+ if (size < 1) {
+ throw new IllegalArgumentException();
+ }
+ MGraph result = new SimpleMGraph();
+ NonLiteral lastNode = firstNode;
+ for (int i = 0; i < size; i++) {
+ final BNode newNode = new BNode();
+ result.add(new TripleImpl(lastNode, u1, newNode));
+ lastNode = newNode;
+ }
+ return result;
+ }
+
+ final static UriRef u1 = new UriRef("http://example.org/u1");
+
+}