[ff-cvs] fenfire/org/fenfire/util/lava Traversals.java T...

[Tuukka Hastrup]

CVSROOT:        /cvsroot/fenfire
Module name:    fenfire
Branch:         
Changes by:     Tuukka Hastrup <address@hidden> 03/08/24 15:01:42

Modified files:
        org/fenfire/util/lava: Traversals.java Traversals.test 

Log message:
        findComponents gives the largest component as well

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/fenfire/fenfire/org/fenfire/util/lava/Traversals.java.diff?tr1=1.5&tr2=1.6&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/fenfire/fenfire/org/fenfire/util/lava/Traversals.test.diff?tr1=1.3&tr2=1.4&r1=text&r2=text

Patches:
Index: fenfire/org/fenfire/util/lava/Traversals.java
diff -u fenfire/org/fenfire/util/lava/Traversals.java:1.5 
fenfire/org/fenfire/util/lava/Traversals.java:1.6
--- fenfire/org/fenfire/util/lava/Traversals.java:1.5   Sun Aug 17 15:55:02 2003
+++ fenfire/org/fenfire/util/lava/Traversals.java       Sun Aug 24 15:01:41 2003
@@ -143,19 +143,30 @@
      *  representative.
      *  @return set of representatives, one for each component
      */
-    public static Set findComponents(Iterator nodes, Object property, 
-                                    ConstGraph g) {
+    public static Object[] findComponents(Iterator nodes, Object property, 
+                                         ConstGraph g) {
        Set visited = new HashSet();
        Set components = new HashSet();
+       Object largest = null;
+       int largestsize = -1;
+
        while(nodes.hasNext()) {
            Object node = nodes.next();
            if(!visited.contains(node)) { // If found a new component
+               Object representative;
+               int visitedsize = visited.size();
                visited.add(node);
-               components.add(recurseDFS(node, property, g, visited, 
-                                         new DFSRet()).representative);
+               representative = recurseDFS(node, property, g, visited, 
+                                           new DFSRet()).representative;
+               int growth = visited.size() - visitedsize;
+               if(growth > largestsize) {
+                   largestsize = growth;
+                   largest = representative;
+               }
+               components.add(representative);
            }
        }
-       return components;
+       return new Object[] {components, largest};
     }
 
     /** Recurses depth-first search from a given node, and finds the node
Index: fenfire/org/fenfire/util/lava/Traversals.test
diff -u fenfire/org/fenfire/util/lava/Traversals.test:1.3 
fenfire/org/fenfire/util/lava/Traversals.test:1.4
--- fenfire/org/fenfire/util/lava/Traversals.test:1.3   Sat Aug 16 07:45:39 2003
+++ fenfire/org/fenfire/util/lava/Traversals.test       Sun Aug 24 15:01:42 2003
@@ -72,27 +72,30 @@
     fen.graph.add(b,q,c)
     fen.graph.add(d,q,a)
 
-    result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+    reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
     for x in a, b, c, d:          # all single nodes are components
-        assert result.contains(x)
+        assert reps.contains(x)
+    assert lrep in [a, b, c, d]   # one of the components is largest
 
     fen.graph.add(a,p,b)
 
-    result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
-    assert result.contains(a) != result.contains(b) # Either is representative
+    reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+    assert reps.contains(a) != reps.contains(b) # Either is representative
+    assert lrep in [a, b]                       # [a, b] is largest component
 
     fen.graph.add(a,p,c)
 
-    result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
-    assert result.contains(a)     # a has higher degree than b or c
-    assert not result.contains(b)
-    assert not result.contains(c)
+    reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+    assert reps.contains(a)     # a has higher degree than b or c
+    assert not reps.contains(b)
+    assert not reps.contains(c)
+    assert lrep == a            # a is in the largest component
 
     fen.graph.add(c,p,b)
     fen.graph.add(d,p,b)
 
-    result = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
-    assert result.contains(b)         # b has highest degree
+    reps, lrep = Traversals.findComponents(getNodes(fen), p, fen.constgraph)
+    assert reps.contains(b)         # b has highest degree
     for x in a, c, d:
-        assert not result.contains(x)
+        assert not reps.contains(x)