From 3d44aee6069175038266c65f945147569e6343f6 Mon Sep 17 00:00:00 2001 From: RncLsn Date: Thu, 9 Jul 2015 16:01:01 +0100 Subject: Bug-fix for answer dependencies analysis: now it checks whether the endomorphism makes the first tuple identical to the second one. --- .../ac/ox/cs/pagoda/endomorph/DependencyGraph.java | 7 ++- .../ox/cs/pagoda/endomorph/EndomorphChecker.java | 1 + .../ox/cs/pagoda/endomorph/EndomorphChecker1.java | 10 ++-- .../ox/cs/pagoda/endomorph/EndomorphChecker2.java | 53 ++++++++++++++-------- .../ox/cs/pagoda/endomorph/plan/OpenEndPlan.java | 3 +- 5 files changed, 51 insertions(+), 23 deletions(-) (limited to 'src/uk/ac') diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java index 8514808..320af09 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java @@ -240,6 +240,11 @@ public class DependencyGraph { private boolean checkHomomorphism(NodeTuple u, NodeTuple v) { ++homomorphismCheckCounter; homomorphismChecker.setMapping(u, v); + + // TODO recently added, test it + if(!homomorphismChecker.isMappingTo(u, v)) + return false; + try { Node node1, node2; for (Iterator iter1 = u.getNodes().iterator(), iter2 = v.getNodes().iterator(); iter1.hasNext(); ) { @@ -251,7 +256,7 @@ public class DependencyGraph { } return true; } finally { - homomorphismChecker.clearMappings(); + homomorphismChecker.clearMappings(); } } diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java index 8f5ea07..46ddbb3 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java @@ -11,4 +11,5 @@ public interface EndomorphChecker { boolean check(Node next, Node next2); + boolean isMappingTo(NodeTuple u, NodeTuple v); } diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java index ca1256c..c2117b6 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java @@ -15,9 +15,13 @@ public class EndomorphChecker1 implements EndomorphChecker { public boolean check(Node u, Node v) { if (!u.isSubConceptOf(v)) return false; - if (!isSubsetOf(graph.getOutGoingEdges(u), graph.getOutGoingEdges(v), true)) return false; - if (!isSubsetOf(graph.getInComingEdges(u), graph.getInComingEdges(v), false)) return false; - return true; + if (!isSubsetOf(graph.getOutGoingEdges(u), graph.getOutGoingEdges(v), true)) return false; + return isSubsetOf(graph.getInComingEdges(u), graph.getInComingEdges(v), false); + } + + @Override + public boolean isMappingTo(NodeTuple u, NodeTuple v) { + throw new UnsupportedOperationException(); } private boolean isSubsetOf(Edge[] e1, Edge[] e2, boolean out) { diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java index 7ad271a..aac5f3c 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java @@ -1,17 +1,13 @@ package uk.ac.ox.cs.pagoda.endomorph; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; - import uk.ac.ox.cs.pagoda.summary.Edge; import uk.ac.ox.cs.pagoda.summary.Graph; import uk.ac.ox.cs.pagoda.summary.Node; import uk.ac.ox.cs.pagoda.summary.NodeTuple; import uk.ac.ox.cs.pagoda.util.Timer; +import java.util.*; + public class EndomorphChecker2 implements EndomorphChecker { private Graph graph; @@ -24,7 +20,8 @@ public class EndomorphChecker2 implements EndomorphChecker { private Timer timer = new Timer(); private boolean time_out = false; private static final int TIME_OUT = 60; - +// private static final int TIME_OUT = 99999999; + public boolean check(NodeTuple u, NodeTuple v) { int length = u.getNodes().size(); Edge[][] ss = new Edge[1][length], tt = new Edge[1][length]; @@ -39,15 +36,35 @@ public class EndomorphChecker2 implements EndomorphChecker { } public boolean check(Node u, Node v) { - if (!u.isSubConceptOf(v)) return false; - if (!checkSortedEdges(new Edge[][] {graph.getOutGoingEdges(u), graph.getInComingEdges(u) }, - new Edge[][] {graph.getOutGoingEdges(v), graph.getInComingEdges(v)}, 0, 0)) { - return false; - } - return true; - } + if (!u.isSubConceptOf(v)) return false; + return checkSortedEdges(new Edge[][]{graph.getOutGoingEdges(u), graph.getInComingEdges(u)}, + new Edge[][]{graph.getOutGoingEdges(v), graph.getInComingEdges(v)}, 0, 0); + } + + /*** + * Checks whether the found mapping is actually a mapping from tuple u to tuple v. + * + * @param u + * @param v + * @return + */ + @Override + public boolean isMappingTo(NodeTuple u, NodeTuple v) { + Iterator uIterator = u.getNodes().iterator(); + Iterator vIterator = v.getNodes().iterator(); + + while(uIterator.hasNext() && vIterator.hasNext()) { + Node uNode = uIterator.next(); + Node vNode = vIterator.next(); + if(mappings.containsKey(uNode) && !mappings.get(uNode).equals(vNode)) + return false; + else if(!mappings.containsKey(uNode) && !uNode.equals(vNode)) + return false; + } + return !uIterator.hasNext() && !vIterator.hasNext(); + } - Map mappings = new HashMap(); + Map mappings = new HashMap(); public void clearMappings() { mappings.clear(); @@ -100,9 +117,9 @@ public class EndomorphChecker2 implements EndomorphChecker { return true; mappings.remove(u); return false; - }; - - for (Node v: candidates) { + } + + for (Node v: candidates) { mappings.put(u, v); if (check(u, v) && checkSortedEdges(ss, st, dim, index + 1)) return true; diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java index a46da85..076427e 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java @@ -71,7 +71,8 @@ public class OpenEndPlan implements CheckPlan { else { Utility.logDebug(answerTuple.toString() + " is verified."); addProjections(clique); - flag = true; + flag = true; + validated.add(clique); } } } -- cgit v1.2.3