[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/15 20:11:30

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

Log message:
        findComponents using DFS

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

Patches:
Index: fenfire/org/fenfire/util/lava/Traversals.java
diff -u fenfire/org/fenfire/util/lava/Traversals.java:1.2 
fenfire/org/fenfire/util/lava/Traversals.java:1.3
--- fenfire/org/fenfire/util/lava/Traversals.java:1.2   Fri Aug 15 19:04:03 2003
+++ fenfire/org/fenfire/util/lava/Traversals.java       Fri Aug 15 20:11:30 2003
@@ -1,3 +1,4 @@
+//(c): Tuukka Hastrup
 
 package org.fenfire.util.lava;
 
@@ -14,6 +15,13 @@
     static class CollisionException extends Exception {
     }
 
+    /** Return type for recurseDFS. 
+     */
+    static class DFSRet {
+       public Object representative;
+       public int degree;
+    }
+
     /** Returns an iterator of nodes directly connected to a given node
      *  along a given non-directional property.
      */
@@ -105,4 +113,57 @@
        }
     }
 
+    /** Finds components disconnected along a given non-directed property, 
+     *  and for each component returns the node of highest degree as a 
+     *  representative.
+     *  @return set of representatives, one for each component
+     */
+    public static Set findComponents(Object property, ConstGraph g) {
+       // XXX "Iterator nodes" could be a parameter
+       Iterator nodes = g.findN_XAA_Iter(); // FIXME doesn't find objects
+       Set visited = new HashSet();
+       Set components = new HashSet();
+       while(nodes.hasNext()) {
+           Object node = nodes.next();
+           if(!visited.contains(node)) { // If found a new component
+               visited.add(node);
+               components.add(recurseDFS(node, property, g, visited, 
+                                         new DFSRet()).representative);
+           }
+       }
+       return components;
+    }
+
+    /** Recurses depth-first search from a given node, and finds the node
+     *  of highest degree (with most connections).
+     *  @return an array: the first element is the node of highest degree
+     *                    the second element is the highest degree as Integer
+     */
+    static DFSRet recurseDFS(Object start, Object property, ConstGraph g, 
+                              Set visited, DFSRet ret) {
+       Object representative = null;
+       int representativeDegree = -1;
+       Iterator conns = findConnected_Iter(g, start, property);
+       int degree = 0;
+       while(conns.hasNext()) {
+           Object found = conns.next();
+           degree++;
+           if(!visited.contains(found)) {
+               visited.add(found);
+               ret = recurseDFS(found, property, g, visited, ret);
+               if(ret.degree > representativeDegree) {
+                   representativeDegree = ret.degree;
+                   representative = ret.representative;
+               }
+           }
+       }
+       if(representativeDegree > degree) {
+           ret.representative = representative;
+           ret.degree = representativeDegree;
+       } else {
+           ret.representative = start;
+           ret.degree = degree;
+       }
+       return ret;
+    }
 }
Index: fenfire/org/fenfire/util/lava/Traversals.test
diff -u fenfire/org/fenfire/util/lava/Traversals.test:1.1 
fenfire/org/fenfire/util/lava/Traversals.test:1.2
--- fenfire/org/fenfire/util/lava/Traversals.test:1.1   Fri Aug 15 17:49:50 2003
+++ fenfire/org/fenfire/util/lava/Traversals.test       Fri Aug 15 20:11:30 2003
@@ -49,3 +49,52 @@
 
     assert Traversals.isConnected(a, p, d, fen.constgraph)
     assert Traversals.isConnected(d, p, a, fen.constgraph)
+
+
+def testfindComponents():
+    fen = ff.test.fen.newFen()
+    p = ff.swamp.Nodes.N()
+    q = ff.swamp.Nodes.N()
+
+    a = ff.swamp.Nodes.N()
+    b = ff.swamp.Nodes.N()
+    c = ff.swamp.Nodes.N()
+    d = ff.swamp.Nodes.N()
+
+    # Introduce the nodes into graph
+    fen.graph.add(a,q,b)
+    fen.graph.add(c,q,d)
+
+    ## no XAA problem if all nodes are subjects
+    # fen.graph.add(b,q,c)
+    # fen.graph.add(d,q,a)
+
+    result = Traversals.findComponents(p, fen.constgraph)
+    nodes = fen.constgraph.findN_XAA_Iter()
+    print "XAA doesn't find objects:"
+    while nodes.hasNext():
+        print nodes.next()
+    print result
+    for x in a, b, c, d:          # all single nodes are components
+        assert result.contains(x)
+
+    fen.graph.add(a,p,b)
+
+    result = Traversals.findComponents(p, fen.constgraph)
+    assert result.contains(a) != result.contains(b) # Either is representative
+
+    fen.graph.add(a,p,c)
+
+    result = Traversals.findComponents(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)
+
+    fen.graph.add(c,p,b)
+    fen.graph.add(d,p,b)
+
+    result = Traversals.findComponents(p, fen.constgraph)
+    assert result.contains(b)         # b has highest degree
+    for x in a, c, d:
+        assert not result.contains(x)
+