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

[Tuukka Hastrup]

CVSROOT:        /cvsroot/fenfire
Module name:    fenfire
Branch:         
Changes by:     Tuukka Hastrup <address@hidden> 03/08/27 11:52:29

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

Log message:
        added option to get component representatives from a given set

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/fenfire/fenfire/org/fenfire/util/lava/Traversals.java.diff?tr1=1.9&tr2=1.10&r1=text&r2=text

Patches:
Index: fenfire/org/fenfire/util/lava/Traversals.java
diff -u fenfire/org/fenfire/util/lava/Traversals.java:1.9 
fenfire/org/fenfire/util/lava/Traversals.java:1.10
--- fenfire/org/fenfire/util/lava/Traversals.java:1.9   Mon Aug 25 17:42:22 2003
+++ fenfire/org/fenfire/util/lava/Traversals.java       Wed Aug 27 11:52:29 2003
@@ -211,6 +211,21 @@
      */
     public static Object[] findComponents(Iterator nodes, Object property, 
                                          ConstGraph g) {
+       return findComponents(nodes, property, g, null);
+    }
+
+    /** From given nodes, finds components disconnected along a given 
+     *  non-directed property, 
+     *  and for each component returns the node of highest degree as a 
+     *  representative. Additionally, gives the representative of the 
+     *  largest component. The representatives are tried to be found
+     *  in the given candidate node set.
+     *  @return an array: 
+     *          the first element is a <code>Set</code> of representatives,
+     *          the other element is the representative of largest component
+     */
+    public static Object[] findComponents(Iterator nodes, Object property, 
+                                         ConstGraph g, Set candidates) {
        Set visited = new HashSet();
        Set components = new HashSet();
        Object largest = null;
@@ -223,13 +238,17 @@
                int visitedsize = visited.size();
                visited.add(node);
                representative = recurseDFS(node, property, g, visited, 
+                                           candidates,
                                            new DFSRet()).representative;
                int growth = visited.size() - visitedsize;
                if(growth > largestsize) {
                    largestsize = growth;
                    largest = representative;
                }
-               components.add(representative);
+               if(candidates == null || representative != null)
+                   components.add(representative);
+               else
+                   components.add(node);
            }
        }
        return new Object[] {components, largest};
@@ -242,7 +261,7 @@
      *          <code>degree</code> is the highest degree
      */
     static DFSRet recurseDFS(Object start, Object property, ConstGraph g, 
-                              Set visited, DFSRet ret) {
+                              Set visited, Set candidates, DFSRet ret) {
        Object representative = null;
        int representativeDegree = -1;
        Iterator conns = findConnected_Iter(g, start, property);
@@ -252,8 +271,9 @@
            degree++;
            if(!visited.contains(found)) {
                visited.add(found);
-               ret = recurseDFS(found, property, g, visited, ret);
-               if(ret.degree > representativeDegree) {
+               ret = recurseDFS(found, property, g, visited, candidates, ret);
+               if((candidates == null || candidates.contains(found)) 
+                  && ret.degree > representativeDegree) {
                    representativeDegree = ret.degree;
                    representative = ret.representative;
                }
@@ -262,9 +282,13 @@
        if(representativeDegree > degree) {
            ret.representative = representative;
            ret.degree = representativeDegree;
-       } else {
+       } else if (candidates == null || candidates.contains(start)) {
            ret.representative = start;
            ret.degree = degree;
+       } else {
+           // Not a single node was a candidate, so we have to return null
+           ret.representative = null;
+           ret.degree = -1;
        }
        return ret;
     }