Commits

Anonymous committed f61093b

don't treat an edge from one cycle to itself as a cycle for topological sort

Comments (0)

Files changed (2)

src/main/java/org/nrg/util/GraphUtils.java

         final Set<X> resolved = Sets.newLinkedHashSet();
         for (final Iterator<Map.Entry<X,Collection<X>>> mei = graph.entrySet().iterator(); mei.hasNext(); ) {
             final Map.Entry<X,Collection<X>> me = mei.next();
-            if (me.getValue().isEmpty()) {
-                resolved.add(me.getKey());
+            final X node = me.getKey();
+            final Collection<X> edges = me.getValue();
+            edges.remove(node); // ignore edges from a node to itself
+            if (edges.isEmpty()) {
+                resolved.add(node);
                 mei.remove();
             }
         }
-
+        
         final List<X> sorted = new ArrayList<X>(graph.size());
         while (!resolved.isEmpty()) {
             // Move one element (x) from the resolved bin to the final sorted list.

src/test/java/org/nrg/util/GraphUtilsTest.java

 
 import org.nrg.util.GraphUtils.CyclicGraphException;
 
+import com.google.common.collect.Iterables;
+
 import junit.framework.TestCase;
 
 /**
 @SuppressWarnings({ "rawtypes", "unchecked" })
 public class GraphUtilsTest extends TestCase {
     private final List asMutableList(final Object[] a) {
-	return new ArrayList(Arrays.asList(a));
+        return new ArrayList(Arrays.asList(a));
     }
-    
+
     /**
      * Test method for {@link org.nrg.util.GraphUtils#topologicalSort(java.util.Map)}.
      */
     public void testTopologicalSort() {
-	final Map m1 = new LinkedHashMap();
-	m1.put("A", Collections.EMPTY_LIST);
-	m1.put("B", Collections.EMPTY_LIST);
-	m1.put("C", Collections.EMPTY_LIST);
-	final List s1 = GraphUtils.topologicalSort(m1);
-	assertEquals(3, s1.size());
-	assertTrue(s1.contains("A"));
-	assertTrue(s1.contains("B"));
-	assertTrue(s1.contains("C"));
-	
-	final Map m2 = new LinkedHashMap();
-	m2.put("A", Collections.EMPTY_LIST);
-	m2.put("B", asMutableList(new String[]{"A"}));
-	m2.put("C", asMutableList(new String[]{"B"}));
-	final List s2 = GraphUtils.topologicalSort(m2);
-	assertEquals(3, s2.size());
-	assertEquals("A", s2.get(0));
-	assertEquals("B", s2.get(1));
-	assertEquals("C", s2.get(2));
-	
-	final Map m3 = new LinkedHashMap();
-	m3.put("A", Collections.EMPTY_LIST);
-	m3.put("B", Collections.EMPTY_LIST);
-	m3.put("C", asMutableList(new String[]{"A", "B"}));
-	m3.put("D", asMutableList(new String[]{"C"}));
-	final List s3 = GraphUtils.topologicalSort(m3);
-	assertEquals(4, s3.size());
-	assertTrue("A".equals(s3.get(0)) || "B".equals(s3.get(0)));
-	assertTrue("B".equals(s3.get(1)) || "A".equals(s3.get(1)));
-	assertEquals("C", s3.get(2));
-	assertEquals("D", s3.get(3));
-	
-	final Map m4 = new LinkedHashMap();
-	m4.put("A", Collections.EMPTY_LIST);
-	m4.put("B", asMutableList(new String[]{"A"}));
-	m4.put("C", asMutableList(new String[]{"B", "D"}));
-	m4.put("D", asMutableList(new String[]{"C"}));
-	try {
-	    GraphUtils.topologicalSort(m4);
-	    fail("Expected CyclicGraphException");
-	} catch (CyclicGraphException e) {
-	    final List sorted = (List)e.getPartialResult();
-	    assertEquals(2, sorted.size());
-	    assertEquals("A", sorted.get(0));
-	    assertEquals("B", sorted.get(1));
-	}
+        final Map m1 = new LinkedHashMap();
+        m1.put("A", Collections.EMPTY_LIST);
+        m1.put("B", Collections.EMPTY_LIST);
+        m1.put("C", Collections.EMPTY_LIST);
+        final List s1 = GraphUtils.topologicalSort(m1);
+        assertEquals(3, s1.size());
+        assertTrue(s1.contains("A"));
+        assertTrue(s1.contains("B"));
+        assertTrue(s1.contains("C"));
+
+        final Map m2 = new LinkedHashMap();
+        m2.put("A", Collections.EMPTY_LIST);
+        m2.put("B", asMutableList(new String[]{"A"}));
+        m2.put("C", asMutableList(new String[]{"B"}));
+        final List s2 = GraphUtils.topologicalSort(m2);
+        assertEquals(3, s2.size());
+        assertEquals("A", s2.get(0));
+        assertEquals("B", s2.get(1));
+        assertEquals("C", s2.get(2));
+
+        final Map m3 = new LinkedHashMap();
+        m3.put("A", Collections.EMPTY_LIST);
+        m3.put("B", Collections.EMPTY_LIST);
+        m3.put("C", asMutableList(new String[]{"A", "B"}));
+        m3.put("D", asMutableList(new String[]{"C"}));
+        final List s3 = GraphUtils.topologicalSort(m3);
+        assertEquals(4, s3.size());
+        assertTrue("A".equals(s3.get(0)) || "B".equals(s3.get(0)));
+        assertTrue("B".equals(s3.get(1)) || "A".equals(s3.get(1)));
+        assertEquals("C", s3.get(2));
+        assertEquals("D", s3.get(3));
+
+        final Map m4 = new LinkedHashMap();
+        m4.put("A", Collections.EMPTY_LIST);
+        m4.put("B", asMutableList(new String[]{"A"}));
+        m4.put("C", asMutableList(new String[]{"B", "D"}));
+        m4.put("D", asMutableList(new String[]{"C"}));
+        try {
+            GraphUtils.topologicalSort(m4);
+            fail("Expected CyclicGraphException");
+        } catch (CyclicGraphException e) {
+            final List sorted = (List)e.getPartialResult();
+            assertEquals(2, sorted.size());
+            assertEquals("A", sorted.get(0));
+            assertEquals("B", sorted.get(1));
+        }
+    }
+
+    /**
+     * Test method for {@link org.nrg.util.GraphUtils#topologicalSort(java.util.Map)}.
+     */
+    public void testTopologicalSortSelfEdge() {
+        final Map m = new LinkedHashMap();
+        m.put("A", asMutableList(new String[]{"A"}));
+        final List s = GraphUtils.topologicalSort(m);
+        assertEquals("A", Iterables.getOnlyElement(s));
     }
 }