[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 17:30:50

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

Log message:
        findShortestPath and a test

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

Patches:
Index: fenfire/org/fenfire/util/lava/Traversals.java
diff -u fenfire/org/fenfire/util/lava/Traversals.java:1.7 
fenfire/org/fenfire/util/lava/Traversals.java:1.8
--- fenfire/org/fenfire/util/lava/Traversals.java:1.7   Sun Aug 24 15:36:15 2003
+++ fenfire/org/fenfire/util/lava/Traversals.java       Sun Aug 24 17:30:50 2003
@@ -27,9 +27,14 @@
 package org.fenfire.util.lava;
 
 import org.fenfire.swamp.ConstGraph;
+import java.util.List;
+import java.util.LinkedList;
 import java.util.Set;
 import java.util.HashSet;
+import java.util.Map;
+import java.util.HashMap;
 import java.util.Iterator;
+import java.util.Collections;
 
 /** This class contains utility methods for Swamp RDF graph traversal. 
  */
@@ -76,6 +81,60 @@
                    active.remove();
                }
            };
+    }
+
+    /** Finds a shortest path between the given nodes, along the given 
+     *  nondirected property. Uses BFS.
+     *  @return a list of nodes to visit to get from origin (excluded) 
+     *          to the target (included). Or an empty list, if target 
+     *          is origin. Or null, if there is no path.
+     */
+    public static List findShortestPath(Object a, Object property, Object b, 
+                                       ConstGraph g) {
+       if(a == b)
+           return Collections.EMPTY_LIST; // No path needed to itself
+
+       Set active = new HashSet();
+       Map visited = new HashMap(); // maps visited nodes to their parents
+
+       // Initialize the search
+       active.add(a);
+
+       try {
+           while(!active.isEmpty()) {
+               // Advance the search from one active set to the next
+               Set activated = new HashSet();
+               Iterator activenodes = active.iterator();
+               while(activenodes.hasNext()) {
+                   Object node = activenodes.next();
+                   Iterator conns = findConnected_Iter(g, node, property);
+                   while(conns.hasNext()) {
+                       Object found = conns.next();
+                       if(visited.containsKey(found))
+                           continue; // Don't re-handle
+                       activated.add(found);
+                       visited.put(found, node);
+                       if(found == b) // If target reached
+                           throw new CollisionException(); 
+                   }
+               }
+               active = activated;
+           }
+       } catch(CollisionException _) {
+           // Target found, now trace path backwards
+           List path = new LinkedList();
+           Object cur = b;
+           while (cur != a) {
+               path.add(0, cur);
+               cur = visited.get(cur);
+               if(cur == null) // shouldn't happen
+                   throw new Error("Broken path!");
+           }
+           return path;
+       }
+
+       // The search died out, so there is no path
+       return null;
     }
 
     /** Tests whether a given nondirected property connects the two
Index: fenfire/org/fenfire/util/lava/Traversals.test
diff -u fenfire/org/fenfire/util/lava/Traversals.test:1.4 
fenfire/org/fenfire/util/lava/Traversals.test:1.5
--- fenfire/org/fenfire/util/lava/Traversals.test:1.4   Sun Aug 24 15:01:42 2003
+++ fenfire/org/fenfire/util/lava/Traversals.test       Sun Aug 24 17:30:50 2003
@@ -2,6 +2,39 @@
 import org.fenfire as ff
 from org.fenfire.util.lava import Traversals
 
+def testFindShortestPath():
+    def equalSeq(a, b): # sorry, can't compare with ==
+        for i in range(max(len(a),len(b))):
+            if a[i] != b[i]: return 0
+        return 1
+
+    findShortestPath = Traversals.findShortestPath
+    fen = ff.test.fen.newFen()
+    cg = fen.constgraph
+    p = ff.swamp.Nodes.N()
+
+    a = ff.swamp.Nodes.N()
+    b = ff.swamp.Nodes.N()
+    c = ff.swamp.Nodes.N()
+    d = ff.swamp.Nodes.N()
+
+    assert equalSeq(findShortestPath(a, p, a, cg), []) # empty path to itself
+    assert findShortestPath(a, p, b, cg) == None       # no path at all
+
+    fen.graph.add(a,p,b)
+
+    assert equalSeq(findShortestPath(a, p, b, cg), [b]) # simple neighbour
+    assert equalSeq(findShortestPath(b, p, a, cg), [a]) # other direction
+
+    fen.graph.add(a,p,c)
+
+    assert equalSeq(findShortestPath(b, p, c, cg), [a,c])
+
+    fen.graph.add(c,p,d) # long path
+    fen.graph.add(a,p,d) # add shortcut
+
+    assert equalSeq(findShortestPath(b, p, d, cg), [a,d]) # test shortcut use
+
 def testIsConnected():
     fen = ff.test.fen.newFen()
     p = ff.swamp.Nodes.N()
@@ -51,7 +84,7 @@
     assert Traversals.isConnected(d, p, a, fen.constgraph)
 
 
-def testfindComponents():
+def testFindComponents():
     def getNodes(fen):
         return fen.constgraph.findN_XAA_Iter() # not realistic!