Skip to main content
summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMathieu Cartaud2016-09-30 12:01:22 -0400
committerLaurent Delaigue2016-10-13 09:14:35 -0400
commit323e2aac57794ddc61c5116728ae3179ac7c3131 (patch)
treeb229f0a71f2bb922165e06bc497d218277bf8a43
parentd2efef258ad29921c5619008d1fa1c5575d140c6 (diff)
downloadorg.eclipse.emf.compare-323e2aac57794ddc61c5116728ae3179ac7c3131.tar.gz
org.eclipse.emf.compare-323e2aac57794ddc61c5116728ae3179ac7c3131.tar.xz
org.eclipse.emf.compare-323e2aac57794ddc61c5116728ae3179ac7c3131.zip
[503035] Fix BreadthFirstIterator where some nodes may never be used
If two nodes on the same level where parent and childs of each other, the breadthFirstIterator will never iterate on them Bug: 503035 Change-Id: Ie1c542a046ace99cde5871cffcd9d00b5ac53a85 Signed-off-by: Mathieu Cartaud <mathieu.cartaud@obeo.fr>
-rw-r--r--plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java169
-rw-r--r--plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java7
2 files changed, 160 insertions, 16 deletions
diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java
index aa9981c4c..02e10f59f 100644
--- a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java
@@ -38,11 +38,19 @@ public class GraphTest {
@Test
public void testBuildSubGraph() {
IGraph<String> graph = new Graph<String>();
- // @formatter:off
- /*
- * Add the following graph: e f | | b c d \ | / \ | / --------- | a
+ /**
+ * <pre>
+ * Add the following graph:
+ * e f
+ * | |
+ * b c d
+ * \ | /
+ * \ | /
+ * ---------
+ * |
+ * a
+ * </pre>
*/
- // @formatter:on
graph.addChildren("a", ImmutableSet.of("b", "c", "d"));
graph.addChildren("c", ImmutableSet.of("e"));
graph.addChildren("d", ImmutableSet.of("f"));
@@ -58,11 +66,16 @@ public class GraphTest {
@Test
public void testPrune() {
IGraph<String> graph = new Graph<String>();
- // @formatter:off
- /*
- * Add the following graph: c-\ | | b-/ | a
+ /**
+ * <pre>
+ * Add the following graph:
+ * c-\
+ * | |
+ * b-/
+ * |
+ * a
+ * </pre>
*/
- // @formatter:on
graph.addChildren("a", ImmutableSet.of("b"));
graph.addChildren("b", ImmutableSet.of("c"));
graph.addChildren("c", ImmutableSet.of("b"));
@@ -76,13 +89,22 @@ public class GraphTest {
@Test
public void testBreadthFirstIteration() {
IGraph<String> graph = new Graph<String>();
- // @formatter:off
- /*
- * With the following Graph: A I J / \ / / \ B C G K L / / \ / \ / \ D E F H M N We expect our
- * iteration to go in the following order: three first items, in unspecified order : A, I, J next
- * five, in unspecified order : B, C, G, K, L finally, still in unspecified order : D, E, F, H, M, N
+ /**
+ * <pre>
+ * With the following Graph:
+ *
+ * A I J
+ * / \ / / \
+ * B C G K L
+ * / / \ / \ / \
+ * D E F H M N
+ *
+ * We expect our iteration to go in the following order:
+ * three first items, in unspecified order : A, I, J
+ * next five, in unspecified order : B, C, G, K, L
+ * finally, still in unspecified order : D, E, F, H, M, N
+ * </pre>
*/
- // @formatter:on
graph.addChildren("A", ImmutableSet.of("B", "C"));
graph.addChildren("B", ImmutableSet.of("D"));
graph.addChildren("C", ImmutableSet.of("E", "F"));
@@ -228,6 +250,125 @@ public class GraphTest {
}
/**
+ * Test the BreadthFirstIterator with the following cyclic graph:
+ *
+ * <pre>
+ * A
+ * / \
+ * B = C
+ * </pre>
+ */
+ @Test
+ public void testBug503035_1() {
+ IGraph<String> graph = new Graph<String>();
+
+ graph.addChildren("A", ImmutableSet.of("B", "C"));
+ graph.addChildren("B", ImmutableSet.of("C"));
+ graph.addChildren("C", ImmutableSet.of("B"));
+
+ Iterator<String> it = graph.breadthFirstIterator();
+ assertTrue(it.hasNext());
+ assertEquals("A", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("B", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("C", it.next());
+ assertFalse(it.hasNext());
+ }
+
+ /**
+ * Test the BreadthFirstIterator with the following cyclic graph:
+ *
+ * <pre>
+ * A
+ * / \
+ * B = C
+ * /
+ * D
+ * </pre>
+ */
+ @Test
+ public void testBug503035_2() {
+ IGraph<String> graph = new Graph<String>();
+
+ graph.addChildren("A", ImmutableSet.of("B", "C"));
+ graph.addChildren("B", ImmutableSet.of("D", "C"));
+ graph.addChildren("C", ImmutableSet.of("B"));
+
+ Iterator<String> it = graph.breadthFirstIterator();
+ assertTrue(it.hasNext());
+ assertEquals("A", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("B", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("C", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("D", it.next());
+ assertFalse(it.hasNext());
+ }
+
+ /**
+ * Test the BreadthFirstIterator with the following cyclic graph:
+ *
+ * <pre>
+ * A B
+ * | |
+ * C = D
+ * </pre>
+ */
+ @Test
+ public void testBug503035_3() {
+ IGraph<String> graph = new Graph<String>();
+
+ graph.addChildren("A", ImmutableSet.of("C"));
+ graph.addChildren("B", ImmutableSet.of("D"));
+ graph.addChildren("C", ImmutableSet.of("D"));
+ graph.addChildren("D", ImmutableSet.of("C"));
+
+ Iterator<String> it = graph.breadthFirstIterator();
+ assertTrue(it.hasNext());
+ assertEquals("A", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("B", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("C", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("D", it.next());
+ assertFalse(it.hasNext());
+ }
+
+ /**
+ * Test the BreadthFirstIterator with the following cyclic graph:
+ *
+ * <pre>
+ * A
+ * /|\
+ * / | \
+ * B C D
+ * \\===//
+ * </pre>
+ */
+ @Test
+ public void testBug503035_4() {
+ IGraph<String> graph = new Graph<String>();
+
+ graph.addChildren("A", ImmutableSet.of("B", "C", "D"));
+ graph.addChildren("B", ImmutableSet.of("D"));
+ graph.addChildren("D", ImmutableSet.of("B"));
+
+ Iterator<String> it = graph.breadthFirstIterator();
+ assertTrue(it.hasNext());
+ assertEquals("A", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("B", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("C", it.next());
+ assertTrue(it.hasNext());
+ assertEquals("D", it.next());
+ assertFalse(it.hasNext());
+ }
+
+ /**
* @return The following acyclic graph:
*
* <pre>
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java
index 92c61d9bc..6abebbd13 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2013, 2015 Obeo and others.
+ * Copyright (c) 2013, 2016 Obeo and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -19,6 +19,8 @@ import com.google.common.base.Predicate;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Iterators;
+import com.google.common.collect.Sets;
+import com.google.common.collect.Sets.SetView;
import java.util.Collection;
import java.util.Collections;
@@ -1081,7 +1083,8 @@ public class Graph<E> implements IGraph<E> {
}
currentIterator = Iterators.filter(difference.iterator(), new Predicate<Node<E>>() {
public boolean apply(Node<E> input) {
- return consumedNodes.containsAll(input.getParents());
+ SetView<Node<E>> trueParents = Sets.difference(input.getParents(), input.getChildren());
+ return consumedNodes.containsAll(trueParents);
}
});
nextIterable.clear();

Back to the top