fenfire-dev
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Fenfire-dev] Re: [ff-cvs] fenfire/org/fenfire/util/lava Traversals.java


From: Tuomas Lukka
Subject: [Fenfire-dev] Re: [ff-cvs] fenfire/org/fenfire/util/lava Traversals.java T...
Date: Mon, 25 Aug 2003 09:44:44 +0300
User-agent: Mutt/1.5.4i

Very good: I wanted to single this out to show to the others:
*This* is how you should do code and tests &c.
> +
> +    /** 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.
> +     */

1) A reasonable javadoc comment.

(it *might* be useful to expand on the "nondirected property", for
example by an example that shows it clearly, but anyway, the current comment
is far above average.)

> +    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;
>      }

2) The code is cleanly commented, at the most important points.
The really important thing is to put comments for the data,
like the "maps visited nodes to their parents". Code is MUCH easier
to follow when there's things like this

> 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
> +

3) A comprehensive test case, which also has comments about *what* it is doing,
   why it expects certain results.

Great work!

        Tuomas




reply via email to

[Prev in Thread] Current Thread [Next in Thread]