xmlgraphics-fop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jerem...@apache.org
Subject svn commit: r594560 - in /xmlgraphics/fop/branches/Temp_ImagePackageRedesign: src/java/org/apache/fop/util/dijkstra/ test/java/org/apache/fop/util/dijkstra/
Date Tue, 13 Nov 2007 15:10:36 GMT
Author: jeremias
Date: Tue Nov 13 07:10:35 2007
New Revision: 594560

URL: http://svn.apache.org/viewvc?rev=594560&view=rev
Log:
Implementation of Dijkstra's algorithm for finding the shortest path. Used in the new image
package to find the best combination of image loaders and image converters to provide an image
in the optimal form for a renderer.

Added:
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java
  (with props)
    xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java
  (with props)

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.Map;
+
+/**
+ * Default implementation of an edge directory for the {@link DijkstraAlgorithm}.
+ */
+public class DefaultEdgeDirectory implements EdgeDirectory {
+
+    /** The directory of edges */
+    private Map edges = new java.util.HashMap();
+    //Map<Vertex,Map<Vertex,Edge>>
+    
+    /**
+     * Adds a new edge between two vertices.
+     * @param edge the new edge
+     */
+    public void addEdge(Edge edge) {
+        Map directEdges = (Map)edges.get(edge.getStart());
+        if (directEdges == null) {
+            directEdges = new java.util.HashMap();
+            edges.put(edge.getStart(), directEdges);
+        }
+        directEdges.put(edge.getEnd(), edge);
+    }
+
+    /** {@inheritDoc} */
+    public int getPenalty(Vertex start, Vertex end) {
+        Map edgeMap = (Map)edges.get(start);
+        if (edgeMap != null) {
+            Edge route = (Edge)edgeMap.get(end);
+            if (route != null) {
+                int penalty = route.getPenalty();
+                if (penalty < 0) {
+                    throw new IllegalStateException("Penalty must not be negative");
+                }
+                return penalty;
+            }
+        }
+        return 0;
+    }
+
+    /** {@inheritDoc} */
+    public Iterator getDestinations(Vertex origin) {
+        Map directRoutes = (Map)edges.get(origin);
+        if (directRoutes != null) {
+            Iterator iter = directRoutes.keySet().iterator();
+            return iter;
+        }
+        return Collections.EMPTY_LIST.iterator();
+    }
+
+    /**
+     * Returns an iterator over all edges with the given origin.
+     * @param origin the origin
+     * @return an iterator over Edge instances
+     */
+    public Iterator getEdges(Vertex origin) {
+        Map directRoutes = (Map)edges.get(origin);
+        if (directRoutes != null) {
+            Iterator iter = directRoutes.values().iterator();
+            return iter;
+        }
+        return Collections.EMPTY_LIST.iterator();
+    }
+
+    /**
+     * Returns the best edge (the edge with the lowest penalty) between two given vertices.
+     * @param start the start vertex
+     * @param end the end vertex
+     * @return the best vertex or null if none is found
+     */
+    public Edge getBestEdge(Vertex start, Vertex end) {
+        Edge best = null;
+        Iterator iter = getEdges(start);
+        while (iter.hasNext()) {
+            Edge edge = (Edge)iter.next();
+            if (edge.getEnd().equals(end)) {
+                if (best == null || edge.getPenalty() < best.getPenalty()) {
+                    best = edge;
+                }
+            }
+        }
+        return best;
+    }
+
+    
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DefaultEdgeDirectory.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,215 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeSet;
+
+/**
+ * This is an implementation of Dijkstra's algorithm to find the shortest path for a directed
+ * graph with non-negative edge weights.
+ * @see <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">WikiPedia on
Dijkstra's 
+ *      Algorithm</a>
+ */
+public class DijkstraAlgorithm {
+    
+    /** Infinity value for distances. */
+    public static final int INFINITE = Integer.MAX_VALUE;
+
+    /** Compares penalties between two possible destinations. */
+    private final Comparator penaltyComparator = new Comparator() {
+        public int compare(Object left, Object right) {
+            int leftPenalty = getLowestPenalty((Vertex)left);
+            int rightPenalty = getLowestPenalty((Vertex)right);
+            if (leftPenalty < rightPenalty) {
+                return -1;
+            } else if (leftPenalty == rightPenalty) {
+                return ((Comparable)left).compareTo(right);
+            } else {
+                return 1;
+            }
+        }
+    };
+
+    /** The directory of edges */
+    private EdgeDirectory edgeDirectory;
+
+    /** The priority queue for all vertices under inspection, ordered by penalties/distances.
*/
+    private TreeSet priorityQueue = new TreeSet(penaltyComparator);
+    //Set<Vertex>
+
+    /** The set of vertices for which the lowest penalty has been found. */
+    private Set finishedVertices = new java.util.HashSet();
+    //Set<Vertex>
+
+    /** The currently known lowest penalties for all vertices. */
+    private Map lowestPenalties = new java.util.HashMap();
+    //Map<Vertex,Integer>
+
+    /** Map of all predecessors in the spanning tree of best routes. */
+    private Map predecessors = new java.util.HashMap();
+    //Map<Vertex,Vertex>
+
+    /**
+     * Main Constructor.
+     * @param edgeDirectory the edge directory this instance should work on
+     */
+    public DijkstraAlgorithm(EdgeDirectory edgeDirectory) {
+        this.edgeDirectory = edgeDirectory;
+    }
+
+    /**
+     * Returns the penalty between two vertices.
+     * @param start the start vertex
+     * @param end the end vertex
+     * @return the penalty between two vertices, or 0 if no single edge between the two vertices
+     *                  exists.
+     */
+    protected int getPenalty(Vertex start, Vertex end) {
+        return this.edgeDirectory.getPenalty(start, end);
+    }
+
+    /**
+     * Returns an iterator over all valid destinations for a given vertex.
+     * @param origin the origin from which to search for destinations
+     * @return the iterator over all valid destinations for a given vertex
+     */
+    protected Iterator getDestinations(Vertex origin) {
+        return this.edgeDirectory.getDestinations(origin);
+    }
+
+    private void reset() {
+        finishedVertices.clear();
+        priorityQueue.clear();
+
+        lowestPenalties.clear();
+        predecessors.clear();
+    }
+
+    /**
+     * Run Dijkstra's shortest path algorithm. After this method is finished you can use
+     * {@link #getPredecessor(Vertex)} to reconstruct the best/shortest path starting from
the
+     * destination backwards.
+     * @param start the starting vertex
+     * @param destination the destination vertex.
+     */
+    public void execute(Vertex start, Vertex destination) {
+        if (start == null || destination == null) {
+            throw new NullPointerException("start and destination may not be null");
+        }
+        
+        reset();
+        setShortestDistance(start, 0);
+        priorityQueue.add(start);
+
+        // the current node
+        Vertex u;
+
+        // extract the vertex with the shortest distance
+        while (priorityQueue.size() > 0) {
+            u = (Vertex)priorityQueue.first();
+            priorityQueue.remove(u);
+            
+            if (destination.equals(u)) {
+                //Destination reached
+                break;
+            }
+
+            finishedVertices.add(u);
+            relax(u);
+        }
+    }
+
+    /**
+     * Compute new lowest penalties for neighboring vertices. Update the lowest penalties
and the
+     * predecessor map if a better solution is found.
+     * @param u the vertex to process
+     */
+    private void relax(Vertex u) {
+        Iterator iter = getDestinations(u);
+        while (iter.hasNext()) {
+            Vertex v = (Vertex)iter.next();
+            // skip node already settled
+            if (isFinished(v)) {
+                continue;
+            }
+
+            int shortDist = getLowestPenalty(u) + getPenalty(u, v);
+
+            if (shortDist < getLowestPenalty(v)) {
+                // assign new shortest distance and mark unsettled
+                setShortestDistance(v, shortDist);
+
+                // assign predecessor in shortest path
+                setPredecessor(v, u);
+            }
+        }
+    }
+
+    private void setPredecessor(Vertex a, Vertex b) {
+        predecessors.put(a, b);
+    }
+
+    /**
+     * Indicates whether a shortest route to a vertex has been found.
+     * @param v the vertex
+     * @return true if the shortest route to this vertex has been found.
+     */
+    private boolean isFinished(Vertex v) {
+        return finishedVertices.contains(v);
+    }
+
+    private void setShortestDistance(Vertex vertex, int distance) {
+        //Remove so it is inserted at the right position after the lowest penalty changes
for this
+        //vertex.
+        priorityQueue.remove(vertex);
+
+        //Update the lowest penalty.
+        lowestPenalties.put(vertex, new Integer(distance));
+
+        //Insert the vertex again at the new position based on the lowest penalty
+        priorityQueue.add(vertex);
+    }
+
+    /**
+     * Returns the lowest penalty from the start point to a given vertex.
+     * @param vertex the vertex
+     * @return the lowest penalty or {@link DijkstraAlgorithm#INFINITE} if there is no route
to
+     *         the destination.
+     */
+    public int getLowestPenalty(Vertex vertex) {
+        Integer d = ((Integer)lowestPenalties.get(vertex));
+        return (d == null) ? INFINITE : d.intValue();
+    }
+
+    /**
+     * Returns the vertex's predecessor on the shortest path.
+     * @param vertex the vertex for which to find the predecessor
+     * @return the vertex's predecessor on the shortest path, or
+     *         <code>null</code> if there is no route to the destination.
+     */
+    public Vertex getPredecessor(Vertex vertex) {
+        return (Vertex)predecessors.get(vertex);
+    }
+
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/DijkstraAlgorithm.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+/**
+ * Represents an edge (or direct route between two points) for the {@link DijkstraAlgorithm}.
+ * Implement this class to hold the start and end vertex for an edge and implement the
+ * <code>getPenalty()</code> method.
+ */
+public interface Edge {
+
+    /**
+     * Returns the start vertex of the edge.
+     * @return the start vertex
+     */
+    Vertex getStart();
+
+    /**
+     * Returns the end vertex of the edge.
+     * @return the end vertex
+     */
+    Vertex getEnd();
+    
+    /**
+     * Returns the penalty (or distance) for this edge.
+     * @return the penalty value (must be non-negative)
+     */
+    int getPenalty();
+    
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Edge.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,45 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+import java.util.Iterator;
+
+/**
+ * Represents a directory of edges for use by the {@link DijkstraAlgorithm}.
+ */
+public interface EdgeDirectory {
+
+    /**
+     * Returns the penalty between two vertices.
+     * @param start the start vertex
+     * @param end the end vertex
+     * @return the penalty between two vertices, or 0 if no single edge between the two vertices
+     *                  exists.
+     */
+    int getPenalty(Vertex start, Vertex end);
+
+    /**
+     * Returns an iterator over all valid destinations for a given vertex.
+     * @param origin the origin from which to search for destinations
+     * @return the iterator over all valid destinations for a given vertex
+     */
+    Iterator getDestinations(Vertex origin);
+
+}
\ No newline at end of file

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/EdgeDirectory.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,32 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+/**
+ * Represents a vertex to be used by {@link DijkstraAlgorithm}. If you want to represent
a city,
+ * you can do "public class City implements Vertex". The purpose of this interface is to
make
+ * sure the Vertex implementation implements the Comparable interface so the sorting order
is
+ * well-defined even when two vertices have the same penalty/distance from an origin point.
+ * Therefore, make sure you implement the <code>compareTo(Object)</code> and
+ * <code>equals(Object)</code> methods. 
+ */
+public interface Vertex extends Comparable {
+
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/src/java/org/apache/fop/util/dijkstra/Vertex.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,57 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+/**
+ * Represents a city.
+ */
+public class City implements Vertex {
+
+    private String name;
+    
+    /**
+     * Main constructor
+     * @param name the city's name
+     */
+    public City(String name) {
+        this.name = name;
+    }
+    
+    /** {@inheritDoc} */
+    public boolean equals(Object obj) {
+        return this.name.equals(((City)obj).name);
+    }
+
+    /** {@inheritDoc} */
+    public int hashCode() {
+        return this.name.hashCode();
+    }
+
+    /** {@inheritDoc} */
+    public int compareTo(Object obj) {
+        return this.name.compareTo(((City)obj).name);
+    }
+    
+    /** {@inheritDoc} */
+    public String toString() {
+        return this.name;
+    }
+    
+}
\ No newline at end of file

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/City.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,139 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+
+import junit.framework.TestCase;
+
+/**
+ * Tests the Dijkstra algorithm implementation. We're comparing best solutions with focus
on
+ * time or distance getting from St. Gallen to Lucerne on Switzerland's railroads.
+ */
+public class DijkstraTestCase extends TestCase {
+
+    private static final boolean DEBUG = false;
+    
+    private static final City ROMANSHORN = new City("Romanshorn");
+    private static final City ST_GALLEN = new City("St. Gallen");
+    private static final City WINTERTHUR = new City("Winterthur");
+    private static final City ZURICH = new City("Zurich");
+    private static final City ZUG = new City("Zug");
+    private static final City RAPPERSWIL = new City("Rapperswil");
+    private static final City ARTH_GOLDAU = new City("Arth-Goldau");
+    private static final City LUCERNE = new City("Lucerne");
+
+    private static final City NOWHERE = new City("nowhere");
+    
+    private DijkstraAlgorithm algo;
+    private DefaultEdgeDirectory edges;
+    private Mode mode;
+    
+    /** {@inheritDoc} */
+    protected void setUp() throws Exception {
+        super.setUp();
+        
+        edges = new DefaultEdgeDirectory();
+        algo = new DijkstraAlgorithm(edges);
+        mode = new Mode();
+        
+        //St.Gallen - Winterthur - Zurich - Zug - Lucerne: 161 km, 2h 01min
+        edges.addEdge(new TrainRoute(mode, ST_GALLEN, WINTERTHUR, 61, 39));
+        edges.addEdge(new TrainRoute(mode, WINTERTHUR, ZURICH, 31, 31));
+        edges.addEdge(new TrainRoute(mode, ZURICH, ZUG, 39, 31));
+        edges.addEdge(new TrainRoute(mode, ZUG, LUCERNE, 30, 20));
+        
+        //St.Gallen - Rapperswil - Arth-Goldau - Lucerne: 158km, 2h 18min
+        edges.addEdge(new TrainRoute(mode, ST_GALLEN, RAPPERSWIL, 72, 57));
+        edges.addEdge(new TrainRoute(mode, RAPPERSWIL, ARTH_GOLDAU, 55, 48));
+        edges.addEdge(new TrainRoute(mode, ARTH_GOLDAU, LUCERNE, 31, 33));
+        
+        //A detour to make it interesting (St.Gallen - Romanshorn - Winterthur): 89km, 1h
23min
+        edges.addEdge(new TrainRoute(mode, ST_GALLEN, ROMANSHORN, 30, 32));
+        edges.addEdge(new TrainRoute(mode, ROMANSHORN, WINTERTHUR, 59, 51));
+    }
+
+    public void testAlgorithmWithDistance() throws Exception {
+        mode.useDistance();
+        City origin = ST_GALLEN;
+        City destination = LUCERNE;
+        String route = executeAlgorithm(origin, destination);
+        
+        int distance = algo.getLowestPenalty(destination);
+        
+        if (DEBUG) {
+            System.out.println(route + " " + distance + " km");
+        }
+        
+        assertEquals(158, distance);
+        assertEquals("St. Gallen - Rapperswil - Arth-Goldau - Lucerne", route);
+    }
+
+    public void testAlgorithmWithDuration() throws Exception {
+        mode.useDuration();
+        City origin = ST_GALLEN;
+        City destination = LUCERNE;
+        String route = executeAlgorithm(origin, destination);
+        
+        int duration = algo.getLowestPenalty(destination);
+        
+        if (DEBUG) {
+            System.out.println(route + " " + duration + " minutes");
+        }
+        
+        assertEquals(121, duration);
+        assertEquals("St. Gallen - Winterthur - Zurich - Zug - Lucerne", route);
+    }
+    
+    public void testAlgorithmWithNonExistentRoute() throws Exception {
+        City origin = ST_GALLEN;
+        City destination = NOWHERE;
+        algo.execute(origin, destination);
+        Vertex pred = algo.getPredecessor(destination);
+        assertNull(pred);
+    }
+    
+    private String executeAlgorithm(City origin, City destination) {
+        algo.execute(origin, destination);
+        Vertex prev = destination;
+        Vertex pred = algo.getPredecessor(destination);
+        if (pred == null) {
+            fail("No route found!");
+        }
+        LinkedList stops = new LinkedList();
+        stops.addLast(destination);
+        while ((pred = algo.getPredecessor(prev)) != null) {
+            stops.addFirst(pred);
+            prev = pred;
+        }
+        StringBuffer sb = new StringBuffer();
+        Iterator iter = stops.iterator();
+        while (iter.hasNext()) {
+            if (sb.length() > 0) {
+                sb.append(" - ");
+            }
+            sb.append(iter.next());
+        }
+        String route = sb.toString();
+        return route;
+    }
+    
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/DijkstraTestCase.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,51 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+/**
+ * Class to allow easy switching between duration and distance mode.
+ */
+public class Mode {
+
+    private boolean duration = true;
+    
+    /**
+     * Switch to duration mode.
+     */
+    public void useDuration() {
+        this.duration = true;
+    }
+    
+    /**
+     * Switch to distance mode.
+     */
+    public void useDistance() {
+        this.duration = false;
+    }
+    
+    /**
+     * Indicates whether to use duration mode or distance mode.
+     * @return true if duration mode is active, otherwise it's the distance mode.
+     */
+    public boolean isDuration() {
+        return this.duration;
+    }
+    
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/Mode.java
------------------------------------------------------------------------------
    svn:keywords = Id

Added: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java
URL: http://svn.apache.org/viewvc/xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java?rev=594560&view=auto
==============================================================================
--- xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java
(added)
+++ xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java
Tue Nov 13 07:10:35 2007
@@ -0,0 +1,67 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ * 
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util.dijkstra;
+
+/**
+ * Represents a train route with both distance and duration.
+ */
+public class TrainRoute implements Edge {
+
+    private Mode mode;
+    private Vertex start;
+    private Vertex end;
+    private int distance;
+    private int minutes;
+
+    /**
+     * Main constructor.
+     * @param origin the start city
+     * @param dest the destination city
+     * @param distance the distance between the two cities
+     * @param minutes the duration for the route
+     */
+    public TrainRoute(Mode mode, City origin, City dest, int distance, int minutes) {
+        this.mode = mode;
+        this.start = origin;
+        this.end = dest;
+        this.distance = distance;
+        this.minutes = minutes;
+    }
+    
+    /** {@inheritDoc} */
+    public int getPenalty() {
+        if (mode.isDuration()) {
+            return this.minutes;
+        } else {
+            return this.distance;
+        }
+    }
+
+    /** {@inheritDoc} */
+    public Vertex getEnd() {
+        return this.end;
+    }
+
+    /** {@inheritDoc} */
+    public Vertex getStart() {
+        return this.start;
+    }
+
+}

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: xmlgraphics/fop/branches/Temp_ImagePackageRedesign/test/java/org/apache/fop/util/dijkstra/TrainRoute.java
------------------------------------------------------------------------------
    svn:keywords = Id



---------------------------------------------------------------------
To unsubscribe, e-mail: fop-commits-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: fop-commits-help@xmlgraphics.apache.org


Mime
View raw message