You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2011/06/27 10:56:11 UTC
svn commit: r1140058 [1/2] - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/ main/java/org/apache/commons/graph/model/
main/java/org/apache/commons/graph/shortestpath/
main/java/org/apache/commons/graph/spanning/ main/java/org/...
Author: simonetripodi
Date: Mon Jun 27 08:56:09 2011
New Revision: 1140058
URL: http://svn.apache.org/viewvc?rev=1140058&view=rev
Log:
huge Graph refactory, a big step back to the initial graph version. current APIs model the Graph in the wrong way, above all because they suggest users to insert, for Undirected graphs, the same Edge info, twice, and that's absolutely wrong, according to math definitions.
Especially, the following tense in that article[1] suggests that the current model is wrong:
"Notice that because an edge in an undirected graph is a set, {a, b}={b, a}, and since E4 is also a set, it cannot contain more than one instance of a given edge. Another consequence of Definition is that there cannot be an edge from a node to itself in an undirected graph because an edge is a set of size two and a set cannot contain duplicates"
[1] http://www.brpreiss.com/books/opus4/html/page529.html
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java (with props)
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/VertexPair.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/DirectedGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Edge.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/MutableGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/UndirectedGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedPath.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableWeightedGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableWeightedGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Boruvka.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/DirectedGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/DirectedGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/DirectedGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/DirectedGraph.java Mon Jun 27 08:56:09 2011
@@ -29,24 +29,24 @@ package org.apache.commons.graph;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public interface DirectedGraph<V extends Vertex, E extends Edge<V>>
+public interface DirectedGraph<V extends Vertex, E extends Edge>
extends Graph<V, E>
{
/**
* Returns the set of {@link Edge}s which are inbound to the {@link Vertex}.
*
- * @param v the {@link Vertex} which inbound {@link Edge}s have to be returned
- * @return the set of {@link Edge}s which are inbound to the {@link Vertex}.
+ * @param v the {@link Vertex} which inbound {@link Vertex}s have to be returned
+ * @return the set of {@link Vertex}s which are inbound to the {@link Vertex}.
*/
- Iterable<E> getInbound( V v );
+ Iterable<V> getInbound( V v );
/**
- * Returns the set of {@link Edge}s which lead away from the {@link Vertex}.
+ * Returns the set of {@link Vertex}s which lead away from the {@link Vertex}.
*
- * @param v the {@link Vertex} which outbound {@link Edge}s have to be returned
- * @return the set of {@link Edge}s which lead away from the {@link Vertex}.
+ * @param v the {@link Vertex} which outbound {@link Vertex}s have to be returned
+ * @return the set of {@link Vertex}s which lead away from the {@link Vertex}.
*/
- Iterable<E> getOutbound( V v );
+ Iterable<V> getOutbound( V v );
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Edge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Edge.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Edge.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Edge.java Mon Jun 27 08:56:09 2011
@@ -26,24 +26,8 @@ package org.apache.commons.graph;
*
* In a {@link DirectedGraph}, {@link Edge}s have orientation, so relation expressed by the {@link Edge} has to be
* intended from {@link #getHead()} to {@link #getTail()}.
- *
- * @param <V> the Graph vertices type
*/
-public interface Edge<V extends Vertex>
+public interface Edge
{
- /**
- * Return the head of this edge.
- *
- * @return the head of this edge.
- */
- V getHead();
-
- /**
- * Return the tail of this edge.
- *
- * @return the tail of this edge.
- */
- V getTail();
-
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java Mon Jun 27 08:56:09 2011
@@ -27,7 +27,7 @@ package org.apache.commons.graph;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public interface Graph<V extends Vertex, E extends Edge<V>>
+public interface Graph<V extends Vertex, E extends Edge>
{
/**
@@ -59,11 +59,11 @@ public interface Graph<V extends Vertex,
int getSize();
/**
- * Returns all edges which touch this vertex, where the input vertex is in the edge head.
+ * Returns all vertices which touch this vertex.
*
- * @return all edges which touch this vertex, where the input vertex is in the edge head.
+ * @return all vertices which touch this vertex.
*/
- Iterable<E> getEdges( V v );
+ Iterable<V> getConnectedVertices( V v );
/**
* Returns the edge with vertex source and target.
@@ -79,6 +79,6 @@ public interface Graph<V extends Vertex,
*
* @return the set of {@link Vertex} on this Edge.
*/
- Iterable<V> getVertices( E e );
+ VertexPair<V> getVertices( E e );
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/MutableGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/MutableGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/MutableGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/MutableGraph.java Mon Jun 27 08:56:09 2011
@@ -25,7 +25,7 @@ package org.apache.commons.graph;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public interface MutableGraph<V extends Vertex, E extends Edge<V>>
+public interface MutableGraph<V extends Vertex, E extends Edge>
extends Graph<V, E>
{
@@ -48,7 +48,7 @@ public interface MutableGraph<V extends
*
* @param e the {@link Edge} has to be added in this {@code MutableGraph} instance.
*/
- void addEdge( E e );
+ void addEdge( V head, E e, V tail );
/**
* Removed the {@link Edge} from the {@code MutableGraph} object.
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java Mon Jun 27 08:56:09 2011
@@ -28,7 +28,7 @@ import java.util.List;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public interface Path<V extends Vertex, E extends Edge<V>>
+public interface Path<V extends Vertex, E extends Edge>
{
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/UndirectedGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/UndirectedGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/UndirectedGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/UndirectedGraph.java Mon Jun 27 08:56:09 2011
@@ -26,7 +26,7 @@ package org.apache.commons.graph;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public interface UndirectedGraph<V extends Vertex, E extends Edge<V>>
+public interface UndirectedGraph<V extends Vertex, E extends Edge>
extends Graph<V, E>
{
}
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java?rev=1140058&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java Mon Jun 27 08:56:09 2011
@@ -0,0 +1,127 @@
+package org.apache.commons.graph;
+
+/*
+ * 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.
+ */
+
+import static java.lang.String.format;
+
+/**
+ * Indicates a {@link Vertex} pair.
+ *
+ * @param <V> the Graph vertices type
+ */
+public final class VertexPair<V extends Vertex>
+{
+
+ private final V head;
+
+ private final V tail;
+
+ /**
+ * Initializes a new {@link Vertex} pair.
+ *
+ * @param head the head Vertex
+ * @param tail the tail Vertex
+ */
+ public VertexPair( V head, V tail )
+ {
+ if ( head == null )
+ {
+ throw new IllegalArgumentException( "Impossible to construct a Vertex with a null head" );
+ }
+ if ( tail == null )
+ {
+ throw new IllegalArgumentException( "Impossible to construct a Vertex with a null tail" );
+ }
+ this.head = head;
+ this.tail = tail;
+ }
+
+ /**
+ * @return the source
+ */
+ public V getHead()
+ {
+ return head;
+ }
+
+ /**
+ * @return the target
+ */
+ public V getTail()
+ {
+ return tail;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int hashCode()
+ {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + ( ( head == null ) ? 0 : head.hashCode() );
+ result = prime * result + ( ( tail == null ) ? 0 : tail.hashCode() );
+ return result;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean equals( Object obj )
+ {
+ if ( this == obj )
+ {
+ return true;
+ }
+
+ if ( obj == null )
+ {
+ return false;
+ }
+
+ if ( getClass() != obj.getClass() )
+ {
+ return false;
+ }
+
+ @SuppressWarnings( "unchecked" ) // equals() invoked against only same VertexPair type
+ VertexPair<V> other = (VertexPair<V>) obj;
+ if ( !head.equals( other.getHead() ) )
+ {
+ return false;
+ }
+
+ if ( !tail.equals( other.getTail() ) )
+ {
+ return false;
+ }
+
+ return true;
+ }
+
+ @Override
+ public String toString()
+ {
+ return format( "[head=%s, tail=%s]", head, tail );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/VertexPair.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java Mon Jun 27 08:56:09 2011
@@ -22,11 +22,9 @@ package org.apache.commons.graph;
/**
* A WeightedEdge is an {@link Edge} where a number (weight) is assigned to represent, for example,
* costs, lengths or capacities, etc. depending on the problem.
- *
- * @param <V> the Graph vertices type
*/
-public interface WeightedEdge<V extends Vertex>
- extends Edge<V>, Comparable<WeightedEdge<V>>
+public interface WeightedEdge
+ extends Edge, Comparable<WeightedEdge>
{
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedGraph.java Mon Jun 27 08:56:09 2011
@@ -27,7 +27,7 @@ package org.apache.commons.graph;
* @param <V> the Graph vertices type.
* @param <WE> the Graph weighted edges type
*/
-public interface WeightedGraph<V extends Vertex, WE extends WeightedEdge<V>>
+public interface WeightedGraph<V extends Vertex, WE extends WeightedEdge>
extends Graph<V, WE>
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedPath.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedPath.java Mon Jun 27 08:56:09 2011
@@ -25,7 +25,7 @@ package org.apache.commons.graph;
* @param <V> the Graph vertices type
* @param <WE> the Graph weighted edges type
*/
-public interface WeightedPath<V extends Vertex, WE extends WeightedEdge<V>>
+public interface WeightedPath<V extends Vertex, WE extends WeightedEdge>
extends Path<V, WE>
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java Mon Jun 27 08:56:09 2011
@@ -23,14 +23,13 @@ import static java.util.Collections.unmo
import static java.util.Collections.unmodifiableSet;
import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
/**
* Basic abstract in-memory based of a simple read-only {@link Graph} implementation. Subclasses may load adjacency
@@ -39,14 +38,16 @@ import org.apache.commons.graph.Vertex;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public abstract class BaseGraph<V extends Vertex, E extends Edge<V>>
+public abstract class BaseGraph<V extends Vertex, E extends Edge>
implements Graph<V, E>
{
- private final Map<V, Set<E>> adjacencyList = new HashMap<V, Set<E>>();
+ private final Map<V, Set<V>> adjacencyList = new HashMap<V, Set<V>>();
private final Map<VertexPair<V>, E> indexedEdges = new HashMap<VertexPair<V>, E>();
+ private final Map<E, VertexPair<V>> indexedVertices = new HashMap<E, VertexPair<V>>();
+
/**
* {@inheritDoc}
*/
@@ -82,7 +83,7 @@ public abstract class BaseGraph<V extend
/**
* {@inheritDoc}
*/
- public final Iterable<E> getEdges( V v )
+ public final Iterable<V> getConnectedVertices( V v )
{
return unmodifiableSet( adjacencyList.get( v ) );
}
@@ -98,14 +99,9 @@ public abstract class BaseGraph<V extend
/**
* {@inheritDoc}
*/
- public final Iterable<V> getVertices( E e )
+ public final VertexPair<V> getVertices( E e )
{
- Set<V> vertices = new LinkedHashSet<V>();
-
- vertices.add( e.getHead() );
- vertices.add( e.getTail() );
-
- return unmodifiableSet( vertices );
+ return indexedVertices.get( e );
}
/**
@@ -113,22 +109,12 @@ public abstract class BaseGraph<V extend
*
* @return the adjacency list where stored vertex/edges.
*/
- protected final Map<V, Set<E>> getAdjacencyList()
+ protected final Map<V, Set<V>> getAdjacencyList()
{
return adjacencyList;
}
/**
- * Returns the set with all Graph edges.
- *
- * @return the set with all Graph edges.
- */
- private final Set<E> getAllEdges()
- {
- return unmodifiableSet( new HashSet<E>( indexedEdges.values() ) );
- }
-
- /**
* {@inheritDoc}
*/
@Override
@@ -151,15 +137,11 @@ public abstract class BaseGraph<V extend
@SuppressWarnings( "unchecked" )
// test against any Graph typed instance
- BaseGraph<Vertex, Edge<Vertex>> other = (BaseGraph<Vertex, Edge<Vertex>>) obj;
+ BaseGraph<Vertex, Edge> other = (BaseGraph<Vertex, Edge>) obj;
if ( !adjacencyList.equals( other.getAdjacencyList() ) )
{
return false;
}
- if ( !getAllEdges().equals( other.getAllEdges() ) )
- {
- return false;
- }
return true;
}
@@ -180,4 +162,12 @@ public abstract class BaseGraph<V extend
return indexedEdges;
}
+ /**
+ * @return the indexedVertices
+ */
+ protected Map<E, VertexPair<V>> getIndexedVertices()
+ {
+ return indexedVertices;
+ }
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java Mon Jun 27 08:56:09 2011
@@ -26,6 +26,7 @@ import org.apache.commons.graph.Graph;
import org.apache.commons.graph.GraphException;
import org.apache.commons.graph.MutableGraph;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
/**
* Basic abstract in-memory based of a simple mutable {@link Graph} implementation.
@@ -33,7 +34,7 @@ import org.apache.commons.graph.Vertex;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public abstract class BaseMutableGraph<V extends Vertex, E extends Edge<V>>
+public abstract class BaseMutableGraph<V extends Vertex, E extends Edge>
extends BaseGraph<V, E>
implements MutableGraph<V, E>
{
@@ -53,7 +54,7 @@ public abstract class BaseMutableGraph<V
throw new GraphException( "Vertex '%s' already present in the Graph", v );
}
- getAdjacencyList().put( v, new LinkedHashSet<E>() );
+ getAdjacencyList().put( v, new LinkedHashSet<V>() );
decorateAddVertex( v );
}
@@ -77,6 +78,10 @@ public abstract class BaseMutableGraph<V
throw new GraphException( "Vertex '%s' not present in the Graph", v );
}
+ for ( V tail : getAdjacencyList().get( v ) )
+ {
+ getIndexedEdges().remove( new VertexPair<Vertex>( v, tail ) );
+ }
getAdjacencyList().remove( v );
decorateRemoveVertex( v );
@@ -92,14 +97,46 @@ public abstract class BaseMutableGraph<V
/**
* {@inheritDoc}
*/
- public final void addEdge( E e )
+ public void addEdge( V head, E e, V tail )
{
- checkEdge( e );
+ internalAddEdge( head, e, tail );
- getAdjacencyList().get( e.getHead() ).add( e );
- getIndexedEdges().put( new VertexPair<V>( e.getHead(), e.getTail() ), e );
+ decorateAddEdge( head, e, tail );
+ }
- decorateAddEdge( e );
+ protected void internalAddEdge( V head, E e, V tail )
+ {
+ if ( head == null )
+ {
+ throw new GraphException( "Null head Vertex not admitted" );
+ }
+ if ( e == null )
+ {
+ throw new GraphException( "Impossible to add a null Edge in the Graph" );
+ }
+ if ( tail == null )
+ {
+ throw new GraphException( "Null tail Vertex not admitted" );
+ }
+
+ if ( !getAdjacencyList().containsKey( head ) )
+ {
+ throw new GraphException( "Head Vertex '%s' not present in the Graph", head );
+ }
+ if ( !getAdjacencyList().containsKey( tail ) )
+ {
+ throw new GraphException( "Tail Vertex '%s' not present in the Graph", tail );
+ }
+
+ getAdjacencyList().get( head ).add( tail );
+
+ VertexPair<V> vertexPair = new VertexPair<V>( head, tail );
+ getIndexedEdges().put( vertexPair, e );
+
+ if ( !getIndexedVertices().containsKey( e ) )
+ {
+ getIndexedVertices().put( e, vertexPair );
+ }
}
/**
@@ -107,17 +144,19 @@ public abstract class BaseMutableGraph<V
*
* @param e
*/
- protected abstract void decorateAddEdge( E e );
+ protected abstract void decorateAddEdge( V head, E e, V tail );
/**
* {@inheritDoc}
*/
public final void removeEdge( E e )
{
- checkEdge( e );
+ if ( e == null )
+ {
+ throw new GraphException( "Impossible to add a null Edge in the Graph" );
+ }
- getAdjacencyList().get( e.getHead() ).remove( e );
- getIndexedEdges().remove( new VertexPair<V>( e.getHead(), e.getTail() ) );
+ // TODO to be completed
decorateRemoveEdge( e );
}
@@ -129,34 +168,4 @@ public abstract class BaseMutableGraph<V
*/
protected abstract void decorateRemoveEdge( E e );
- /**
- * Utility method to check if Vertices in the given Edge are present in the Graph.
- *
- * @param e the Edge which Vertices have to be checked
- */
- private final void checkEdge( E e )
- {
- if ( e == null )
- {
- throw new GraphException( "Impossible to add a null Edge in the Graph" );
- }
- if ( e.getHead() == null )
- {
- throw new GraphException( "Null head Vertex not admitted" );
- }
- if ( e.getTail() == null )
- {
- throw new GraphException( "Null tail Vertex not admitted" );
- }
-
- if ( !getAdjacencyList().containsKey( e.getHead() ) )
- {
- throw new GraphException( "Head Vertex '%s' not present in the Graph", e.getHead() );
- }
- if ( !getAdjacencyList().containsKey( e.getTail() ) )
- {
- throw new GraphException( "Tail Vertex '%s' not present in the Graph", e.getTail() );
- }
- }
-
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java Mon Jun 27 08:56:09 2011
@@ -34,19 +34,19 @@ import org.apache.commons.graph.Vertex;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public class DirectedMutableGraph<V extends Vertex, E extends Edge<V>>
+public class DirectedMutableGraph<V extends Vertex, E extends Edge>
extends BaseMutableGraph<V, E>
implements DirectedGraph<V, E>
{
- private final Map<V, Set<E>> inbound = new HashMap<V, Set<E>>();
+ private final Map<V, Set<V>> inbound = new HashMap<V, Set<V>>();
- private final Map<V, Set<E>> outbound = new HashMap<V, Set<E>>();
+ private final Map<V, Set<V>> outbound = new HashMap<V, Set<V>>();
/**
* {@inheritDoc}
*/
- public Iterable<E> getInbound( V v )
+ public Iterable<V> getInbound( V v )
{
return inbound.get( v );
}
@@ -54,7 +54,7 @@ public class DirectedMutableGraph<V exte
/**
* {@inheritDoc}
*/
- public Iterable<E> getOutbound( V v )
+ public Iterable<V> getOutbound( V v )
{
return outbound.get( v );
}
@@ -65,8 +65,8 @@ public class DirectedMutableGraph<V exte
@Override
protected void decorateAddVertex( V v )
{
- inbound.put( v, new LinkedHashSet<E>() );
- outbound.put( v, new LinkedHashSet<E>() );
+ inbound.put( v, new LinkedHashSet<V>() );
+ outbound.put( v, new LinkedHashSet<V>() );
}
/**
@@ -83,10 +83,10 @@ public class DirectedMutableGraph<V exte
* {@inheritDoc}
*/
@Override
- protected void decorateAddEdge( E e )
+ protected void decorateAddEdge( V head, E e, V tail )
{
- inbound.get( e.getTail() ).add( e );
- outbound.get( e.getHead() ).add( e );
+ inbound.get( tail ).add( head );
+ outbound.get( head ).add( tail );
}
/**
@@ -95,8 +95,7 @@ public class DirectedMutableGraph<V exte
@Override
protected void decorateRemoveEdge( E e )
{
- inbound.get( e.getTail() ).remove( e );
- outbound.get( e.getHead() ).remove( e );
+ // TODO complete me
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableWeightedGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableWeightedGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableWeightedGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/DirectedMutableWeightedGraph.java Mon Jun 27 08:56:09 2011
@@ -29,7 +29,7 @@ import org.apache.commons.graph.Weighted
* @param <V> the Graph vertices type
* @param <WE> the WeightedEdge edges type
*/
-public class DirectedMutableWeightedGraph<V extends Vertex, WE extends WeightedEdge<V>>
+public class DirectedMutableWeightedGraph<V extends Vertex, WE extends WeightedEdge>
extends DirectedMutableGraph<V, WE>
implements WeightedGraph<V, WE>
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java Mon Jun 27 08:56:09 2011
@@ -36,7 +36,7 @@ import org.apache.commons.graph.Vertex;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public class InMemoryPath<V extends Vertex, E extends Edge<V>>
+public class InMemoryPath<V extends Vertex, E extends Edge>
implements Path<V, E>
{
@@ -160,7 +160,7 @@ public class InMemoryPath<V extends Vert
}
@SuppressWarnings( "unchecked" ) // test against any Path typed instance
- InMemoryPath<Vertex, Edge<Vertex>> other = (InMemoryPath<Vertex, Edge<Vertex>>) obj;
+ InMemoryPath<Vertex, Edge> other = (InMemoryPath<Vertex, Edge>) obj;
if ( !source.equals( other.getSource() ) )
{
return false;
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java Mon Jun 27 08:56:09 2011
@@ -32,7 +32,7 @@ import org.apache.commons.graph.Weighted
* @param <V> the Graph vertices type
* @param <WE> the Graph weighted edges type
*/
-public final class InMemoryWeightedPath<V extends Vertex, WE extends WeightedEdge<V>>
+public final class InMemoryWeightedPath<V extends Vertex, WE extends WeightedEdge>
extends InMemoryPath<V, WE>
implements WeightedPath<V, WE>
{
@@ -116,7 +116,7 @@ public final class InMemoryWeightedPath<
}
@SuppressWarnings( "unchecked" ) // test against any WeightedPath typed instance
- InMemoryWeightedPath<Vertex, WeightedEdge<Vertex>> other = (InMemoryWeightedPath<Vertex, WeightedEdge<Vertex>>) obj;
+ InMemoryWeightedPath<Vertex, WeightedEdge> other = (InMemoryWeightedPath<Vertex, WeightedEdge>) obj;
if ( !weigth.equals( other.getWeight() ) )
{
return false;
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java Mon Jun 27 08:56:09 2011
@@ -29,7 +29,7 @@ import org.apache.commons.graph.Vertex;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public class UndirectedMutableGraph<V extends Vertex, E extends Edge<V>>
+public class UndirectedMutableGraph<V extends Vertex, E extends Edge>
extends BaseMutableGraph<V, E>
implements UndirectedGraph<V, E>
{
@@ -56,9 +56,9 @@ public class UndirectedMutableGraph<V ex
* {@inheritDoc}
*/
@Override
- protected void decorateAddEdge( E e )
+ protected void decorateAddEdge( V head, E e, V tail )
{
- // do nothing
+ internalAddEdge( tail, e, head );
}
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableWeightedGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableWeightedGraph.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableWeightedGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/UndirectedMutableWeightedGraph.java Mon Jun 27 08:56:09 2011
@@ -29,7 +29,7 @@ import org.apache.commons.graph.Weighted
* @param <V> the Graph vertices type
* @param <WE> the WeightedEdge edges type
*/
-public class UndirectedMutableWeightedGraph<V extends Vertex, WE extends WeightedEdge<V>>
+public class UndirectedMutableWeightedGraph<V extends Vertex, WE extends WeightedEdge>
extends UndirectedMutableGraph<V, WE>
implements WeightedGraph<V, WE>
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java Mon Jun 27 08:56:09 2011
@@ -54,7 +54,7 @@ public final class AStar
* @param heuristic the <i>h(x)</i> function
* @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>> WeightedPath<V, WE> findShortestPath( WeightedGraph<V, WE> graph,
+ public static <V extends Vertex, WE extends WeightedEdge> WeightedPath<V, WE> findShortestPath( WeightedGraph<V, WE> graph,
V start,
V goal,
Heuristic<V> heuristic )
@@ -76,7 +76,7 @@ public final class AStar
openSet.add( start );
// The of navigated nodes
- final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>();
+ final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
// the current node
V current;
@@ -93,19 +93,18 @@ public final class AStar
closedSet.add( current );
@SuppressWarnings( "unchecked" )
- Iterable<WE> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, WE>) graph ).getOutbound( current )
- : graph.getEdges( current );
- for ( WE edge : edges )
+ Iterable<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, WE>) graph ).getOutbound( current )
+ : graph.getConnectedVertices( current );
+ for ( V v : connected )
{
- V v = edge.getTail();
-
if ( !closedSet.contains( v ) )
{
+ WE edge = graph.getEdge( current, v );
Double tentativeGScore = gScores.getWeight( current ) + edge.getWeight();
if ( openSet.add( v ) || tentativeGScore.compareTo( gScores.getWeight( v ) ) < 0 )
{
- predecessors.addPredecessor( v, edge );
+ predecessors.addPredecessor( v, current );
gScores.setWeight( v, tentativeGScore );
hScore = heuristic.applyHeuristic( v, goal );
fScores.setWeight( v, gScores.getWeight( v ) + hScore );
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java Mon Jun 27 08:56:09 2011
@@ -23,9 +23,9 @@ import java.util.HashMap;
import java.util.Map;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
-import org.apache.commons.graph.model.VertexPair;
/**
* Represents all shortest paths between all vertex pairs calculated by {@link FloydWarshall} algorithm.
@@ -33,7 +33,7 @@ import org.apache.commons.graph.model.Ve
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<V>>
+public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge>
{
private final Map<VertexPair<V>, WeightedPath<V, WE>> paths = new HashMap<VertexPair<V>, WeightedPath<V, WE>>();
@@ -155,4 +155,10 @@ public final class AllVertexPairsShortes
return distance;
}
+ @Override
+ public String toString()
+ {
+ return shortestDistances.toString();
+ }
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java Mon Jun 27 08:56:09 2011
@@ -2,6 +2,7 @@ package org.apache.commons.graph.shortes
import org.apache.commons.graph.DirectedGraph;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedGraph;
import org.apache.commons.graph.WeightedPath;
@@ -49,19 +50,20 @@ public final class BellmannFord
* @param target the shortest path target Vertex
* @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>, G extends WeightedGraph<V, WE> & DirectedGraph<V, WE>> WeightedPath<V, WE> findShortestPath( G graph,
+ public static <V extends Vertex, WE extends WeightedEdge, G extends WeightedGraph<V, WE> & DirectedGraph<V, WE>> WeightedPath<V, WE> findShortestPath( G graph,
V source,
V target )
{
final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
shortestDistances.setWeight( source, 0D );
- final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>();
+ final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
for ( WE edge : graph.getEdges() )
{
- V u = edge.getHead();
- V v = edge.getTail();
+ VertexPair<V> vertexPair = graph.getVertices( edge );
+ V u = vertexPair.getHead();
+ V v = vertexPair.getTail();
Double shortDist = shortestDistances.getWeight( u ) + edge.getWeight();
@@ -71,14 +73,15 @@ public final class BellmannFord
shortestDistances.setWeight( v, shortDist );
// assign predecessor in shortest path
- predecessors.addPredecessor( v, edge );
+ predecessors.addPredecessor( v, u );
}
}
for ( WE edge : graph.getEdges() )
{
- V u = edge.getHead();
- V v = edge.getTail();
+ VertexPair<V> vertexPair = graph.getVertices( edge );
+ V u = vertexPair.getHead();
+ V v = vertexPair.getTail();
Double shortDist = shortestDistances.getWeight( u ) + edge.getWeight();
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java Mon Jun 27 08:56:09 2011
@@ -54,7 +54,7 @@ public final class Dijkstra
* @return a path which describes the shortest path, if any,
* otherwise a {@link PathNotFoundException} will be thrown
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>, G extends WeightedGraph<V, WE> & DirectedGraph<V, WE>> WeightedPath<V, WE> findShortestPath( G graph,
+ public static <V extends Vertex, WE extends WeightedEdge, G extends WeightedGraph<V, WE> & DirectedGraph<V, WE>> WeightedPath<V, WE> findShortestPath( G graph,
V source,
V target )
{
@@ -66,7 +66,7 @@ public final class Dijkstra
final Set<V> settledNodes = new HashSet<V>();
- final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>();
+ final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
// the current node
V vertex;
@@ -82,13 +82,12 @@ public final class Dijkstra
settledNodes.add( vertex );
- for ( WE edge : graph.getOutbound( vertex ) )
+ for ( V v : graph.getOutbound( vertex ) )
{
- V v = edge.getTail();
-
// skip node already settled
if ( !settledNodes.contains( v ) )
{
+ WE edge = graph.getEdge( vertex, v );
Double shortDist = shortestDistances.getWeight( vertex ) + edge.getWeight();
if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
@@ -98,7 +97,7 @@ public final class Dijkstra
unsettledNodes.add( v );
// assign predecessor in shortest path
- predecessors.addPredecessor( v, edge );
+ predecessors.addPredecessor( v, vertex );
}
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java Mon Jun 27 08:56:09 2011
@@ -22,14 +22,15 @@ package org.apache.commons.graph.shortes
import java.util.HashMap;
import java.util.Map;
+import org.apache.commons.graph.UndirectedGraph;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedGraph;
import org.apache.commons.graph.WeightedPath;
-import org.apache.commons.graph.model.VertexPair;
/**
- * Contains the Floyd�Warshall's shortest paths algorithm implementation.
+ * Contains the Floyd-Warshall's shortest paths algorithm implementation.
*/
public final class FloydWarshall
{
@@ -39,17 +40,17 @@ public final class FloydWarshall
*/
private FloydWarshall()
{
- // do nothgin
+ // do nothing
}
/**
- * Applies the classical Floyd�Warshall's algorithm to find all vertex shortest path
+ * Applies the classical Floyd-Warshall's algorithm to find all vertex shortest path
*
* @param <V> the Graph vertices type.
* @param <WE> the Graph weighted edges type
* @return a data structure which contains all vertex pairs shortest path.
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>> AllVertexPairsShortestPath<V, WE> findAllVertexPairsShortestPath( WeightedGraph<V, WE> graph )
+ public static <V extends Vertex, WE extends WeightedEdge> AllVertexPairsShortestPath<V, WE> findAllVertexPairsShortestPath( WeightedGraph<V, WE> graph )
{
AllVertexPairsShortestPath<V, WE> shortesPaths = new AllVertexPairsShortestPath<V, WE>();
Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
@@ -57,11 +58,16 @@ public final class FloydWarshall
// init
for ( WE we : graph.getEdges() )
{
- shortesPaths.addShortestDistance( we.getHead(), we.getTail(), we.getWeight() );
+ VertexPair<V> vertexPair = graph.getVertices( we );
+ shortesPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), we.getWeight() );
+
+ if ( graph instanceof UndirectedGraph )
+ {
+ shortesPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), we.getWeight() );
+ }
}
// run the Floyd-Warshall algorithm.
-
for ( V k : graph.getVertices() )
{
for ( V i : graph.getVertices() )
@@ -70,7 +76,7 @@ public final class FloydWarshall
{
Double newDistance =
shortesPaths.getShortestDistance( i, k ) + shortesPaths.getShortestDistance( k, j );
- if ( newDistance < shortesPaths.getShortestDistance( i, j ) )
+ if ( newDistance.compareTo( shortesPaths.getShortestDistance( i, j ) ) < 0 )
{
shortesPaths.addShortestDistance( i, j, newDistance );
@@ -79,7 +85,6 @@ public final class FloydWarshall
}
}
}
-
}
// fills all WeightedPaths
@@ -89,7 +94,7 @@ public final class FloydWarshall
{
if ( !source.equals( target ) )
{
- PredecessorsList<V, WE> predecessorsList = new PredecessorsList<V, WE>();
+ PredecessorsList<V, WE> predecessorsList = new PredecessorsList<V, WE>( graph );
pathReconstruction( predecessorsList, source, target, next, graph );
if ( !predecessorsList.predecessors.isEmpty() )
@@ -100,7 +105,6 @@ public final class FloydWarshall
shortesPaths.addShortestPath( source, target, weightedPath );
}
}
-
}
}
}
@@ -108,10 +112,10 @@ public final class FloydWarshall
return shortesPaths;
}
- private static <V extends Vertex, WE extends WeightedEdge<V>> void pathReconstruction( PredecessorsList<V, WE> path,
- V source, V target,
- Map<VertexPair<V>, V> next,
- WeightedGraph<V, WE> graph )
+ private static <V extends Vertex, WE extends WeightedEdge> void pathReconstruction( PredecessorsList<V, WE> path,
+ V source, V target,
+ Map<VertexPair<V>, V> next,
+ WeightedGraph<V, WE> graph )
{
V k = next.get( new VertexPair<Vertex>( source, target ) );
if ( k == null )
@@ -120,7 +124,7 @@ public final class FloydWarshall
WE edge = graph.getEdge( source, target );
if ( edge != null )
{
- path.addPredecessor( target, edge );
+ path.addPredecessor( target, source );
}
}
else
@@ -128,7 +132,6 @@ public final class FloydWarshall
pathReconstruction( path, source, k, next, graph );
pathReconstruction( path, k, target, next, graph );
}
-
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java Mon Jun 27 08:56:09 2011
@@ -23,6 +23,7 @@ import java.util.HashMap;
import java.util.Map;
import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
@@ -35,20 +36,27 @@ import org.apache.commons.graph.model.In
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<V>>
+final class PredecessorsList<V extends Vertex, WE extends WeightedEdge>
{
- final Map<V, WE> predecessors = new HashMap<V, WE>();
+ final Graph<V, WE> graph;
+
+ final Map<V, V> predecessors = new HashMap<V, V>();
+
+ public PredecessorsList(Graph<V, WE> graph )
+ {
+ this.graph = graph;
+ }
/**
* Add an {@link Edge} in the predecessor list associated to the input {@link Vertex}.
*
- * @param vertex the predecessor vertex
- * @param edge the edge that succeeds to the input vertex
+ * @param tail the predecessor vertex
+ * @param head the edge that succeeds to the input vertex
*/
- public void addPredecessor( V vertex, WE edge )
+ public void addPredecessor( V tail, V head )
{
- predecessors.put( vertex, edge );
+ predecessors.put( tail, head );
}
/**
@@ -66,12 +74,13 @@ final class PredecessorsList<V extends V
V vertex = target;
while ( !source.equals( vertex ) )
{
- WE edge = predecessors.get( vertex );
+ V predecessor = predecessors.get( vertex );
+ WE edge = graph.getEdge( predecessor, vertex );
path.addEdgeInHead( edge );
path.addVertexInHead( vertex );
- vertex = edge.getHead();
+ vertex = predecessor;
}
path.addVertexInHead( source );
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Boruvka.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Boruvka.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Boruvka.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Boruvka.java Mon Jun 27 08:56:09 2011
@@ -39,7 +39,7 @@ public final class Boruvka
* @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
* @return the minimum spanning tree (or forest) of the input Graph.
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
+ public static <V extends Vertex, WE extends WeightedEdge> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
{
return null;
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java Mon Jun 27 08:56:09 2011
@@ -39,7 +39,7 @@ public final class Kruskal
* @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
* @return the minimum spanning tree (or forest) of the input Graph.
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
+ public static <V extends Vertex, WE extends WeightedEdge> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
{
return null;
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java Mon Jun 27 08:56:09 2011
@@ -38,7 +38,7 @@ public final class Prim
* @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
* @return the minimum spanning tree (or forest) of the input Graph.
*/
- public static <V extends Vertex, WE extends WeightedEdge<V>> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
+ public static <V extends Vertex, WE extends WeightedEdge> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
{
return null;
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java Mon Jun 27 08:56:09 2011
@@ -29,7 +29,7 @@ import org.apache.commons.graph.Vertex;
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
*/
-public class BaseGraphVisitHandler<V extends Vertex, E extends Edge<V>>
+public class BaseGraphVisitHandler<V extends Vertex, E extends Edge>
implements GraphVisitHandler<V, E>
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java Mon Jun 27 08:56:09 2011
@@ -26,7 +26,7 @@ import org.apache.commons.graph.Vertex;
/**
* Description of the Interface
*/
-public interface GraphVisitHandler<V extends Vertex, E extends Edge<V>>
+public interface GraphVisitHandler<V extends Vertex, E extends Edge>
{
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java Mon Jun 27 08:56:09 2011
@@ -45,7 +45,7 @@ public final class Visit
* @param source the root node the search begins from
* @return the breadth first search tree
*/
- public static final <V extends Vertex, E extends Edge<V>> Graph<V, E> breadthFirstSearch( Graph<V, E> graph, V source )
+ public static final <V extends Vertex, E extends Edge> Graph<V, E> breadthFirstSearch( Graph<V, E> graph, V source )
{
VisitGraphBuilder<V, E> visitGraphBuilder = new VisitGraphBuilder<V, E>();
breadthFirstSearch( graph, source, visitGraphBuilder );
@@ -61,7 +61,7 @@ public final class Visit
* @param source the root node the search begins from
* @param handler the handler intercepts visit actions
*/
- public static final <V extends Vertex, E extends Edge<V>> void breadthFirstSearch( Graph<V, E> graph, V source,
+ public static final <V extends Vertex, E extends Edge> void breadthFirstSearch( Graph<V, E> graph, V source,
GraphVisitHandler<V, E> handler )
{
if ( graph == null )
@@ -91,14 +91,14 @@ public final class Visit
handler.discoverVertex( v );
- Iterable<E> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
- : graph.getEdges( v );
- for ( E e : edges )
+ Iterable<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
+ : graph.getConnectedVertices( v );
+ for ( V w : connected )
{
- V w = e.getTail();
-
if ( visitedVetices.add( w ) )
{
+ E e = graph.getEdge( v, w );
+
handler.discoverEdge( e );
vertexQueue.offer( w );
@@ -122,7 +122,7 @@ public final class Visit
* @param source the root node the search begins from
* @return the depth first search tree
*/
- public static final <V extends Vertex, E extends Edge<V>> Graph<V, E> depthFirstSearch( Graph<V, E> graph, V source )
+ public static final <V extends Vertex, E extends Edge> Graph<V, E> depthFirstSearch( Graph<V, E> graph, V source )
{
VisitGraphBuilder<V, E> visitGraphBuilder = new VisitGraphBuilder<V, E>();
depthFirstSearch( graph, source, visitGraphBuilder );
@@ -138,7 +138,7 @@ public final class Visit
* @param source the root node the search begins from
* @param handler the handler intercepts visit actions
*/
- public static final <V extends Vertex, E extends Edge<V>> void depthFirstSearch( Graph<V, E> graph, V source,
+ public static final <V extends Vertex, E extends Edge> void depthFirstSearch( Graph<V, E> graph, V source,
GraphVisitHandler<V, E> handler )
{
if ( graph == null )
@@ -168,14 +168,14 @@ public final class Visit
handler.discoverVertex( v );
- Iterable<E> edges = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
- : graph.getEdges( v );
- for ( E e : edges )
+ Iterable<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
+ : graph.getConnectedVertices( v );
+ for ( V w : connected )
{
- V w = e.getTail();
-
if ( visitedVetices.add( w ) )
{
+ E e = graph.getEdge( v, w );
+
handler.discoverEdge( e );
vertexStack.push( w );
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java Mon Jun 27 08:56:09 2011
@@ -23,6 +23,7 @@ import org.apache.commons.graph.Directed
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.model.BaseMutableGraph;
import org.apache.commons.graph.model.DirectedMutableGraph;
import org.apache.commons.graph.model.UndirectedMutableGraph;
@@ -33,18 +34,22 @@ import org.apache.commons.graph.model.Un
* @param <V> the Graph vertices type.
* @param <E> the Graph edges type.
*/
-final class VisitGraphBuilder<V extends Vertex, E extends Edge<V>>
+final class VisitGraphBuilder<V extends Vertex, E extends Edge>
extends BaseGraphVisitHandler<V, E>
{
private BaseMutableGraph<V, E> visitGraph;
+ private Graph<V, E> graph;
+
/**
* {@inheritDoc}
*/
@Override
public void discoverGraph( Graph<V, E> graph )
{
+ this.graph = graph;
+
if ( graph instanceof DirectedGraph )
{
visitGraph = new DirectedMutableGraph<V, E>();
@@ -66,7 +71,17 @@ final class VisitGraphBuilder<V extends
@Override
public void discoverEdge( E edge )
{
- visitGraph.addEdge( edge );
+ VertexPair<V> vertexPair = graph.getVertices( edge );
+ visitGraph.addEdge( vertexPair.getHead(), edge, vertexPair.getTail() );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public void finishGraph( Graph<V, E> graph )
+ {
+ this.graph = null;
}
/**
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java Mon Jun 27 08:56:09 2011
@@ -25,32 +25,18 @@ import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Labeled;
public class BaseLabeledEdge
- implements Edge<BaseLabeledVertex>, Labeled
+ implements Edge, Labeled
{
private final String label;
- private final BaseLabeledVertex head;
-
- private final BaseLabeledVertex tail;
-
- public BaseLabeledEdge( String label, BaseLabeledVertex head, BaseLabeledVertex tail )
+ public BaseLabeledEdge( String label )
{
if ( label == null )
{
throw new IllegalArgumentException( "Argument 'label' must not be null" );
}
- if ( head == null )
- {
- throw new IllegalArgumentException( "Argument 'head' must not be null" );
- }
- if ( tail == null )
- {
- throw new IllegalArgumentException( "Argument 'tail' must not be null" );
- }
this.label = label;
- this.head = head;
- this.tail = tail;
}
/**
@@ -64,30 +50,12 @@ public class BaseLabeledEdge
/**
* {@inheritDoc}
*/
- public BaseLabeledVertex getHead()
- {
- return head;
- }
-
- /**
- * {@inheritDoc}
- */
- public BaseLabeledVertex getTail()
- {
- return tail;
- }
-
- /**
- * {@inheritDoc}
- */
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
- result = prime * result + ( ( head == null ) ? 0 : head.hashCode() );
result = prime * result + ( ( label == null ) ? 0 : label.hashCode() );
- result = prime * result + ( ( tail == null ) ? 0 : tail.hashCode() );
return result;
}
@@ -114,16 +82,6 @@ public class BaseLabeledEdge
BaseLabeledEdge other = (BaseLabeledEdge) obj;
- if ( !head.equals( other.getHead() ) )
- {
- return false;
- }
-
- if ( !tail.equals( other.getTail() ) )
- {
- return false;
- }
-
if ( !label.equals( other.label ) )
{
return false;
@@ -138,7 +96,7 @@ public class BaseLabeledEdge
@Override
public String toString()
{
- return format( "%s( %s ==> %s )", getLabel(), getHead(), getTail() );
+ return format( "%s()", getLabel() );
}
}
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java Mon Jun 27 08:56:09 2011
@@ -28,14 +28,14 @@ import org.apache.commons.graph.Weighted
*/
public class BaseLabeledWeightedEdge
extends BaseLabeledEdge
- implements WeightedEdge<BaseLabeledVertex>
+ implements WeightedEdge
{
private final Double weight;
- public BaseLabeledWeightedEdge( String label, BaseLabeledVertex head, BaseLabeledVertex tail, Double weight )
+ public BaseLabeledWeightedEdge( String label, Double weight )
{
- super( label, head, tail );
+ super( label );
if ( weight == null )
{
throw new IllegalArgumentException( "Argument 'weight' must not be null" );
@@ -46,7 +46,7 @@ public class BaseLabeledWeightedEdge
/**
* {@inheritDoc}
*/
- public int compareTo( WeightedEdge<BaseLabeledVertex> other )
+ public int compareTo( WeightedEdge other )
{
return weight.compareTo( other.getWeight() );
}
@@ -107,7 +107,7 @@ public class BaseLabeledWeightedEdge
@Override
public String toString()
{
- return format( "%s( %s =%s=> %s )", getLabel(), getHead(), weight, getTail() );
+ return format( "%s( %s )", getLabel(), weight );
}
}
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java Mon Jun 27 08:56:09 2011
@@ -63,22 +63,15 @@ public final class AStarTestCase
graph.addVertex( e );
graph.addVertex( goal );
- graph.addEdge( new BaseLabeledWeightedEdge( "", start, a, 1.5D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", a, start, 1.5D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", start, d, 2D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", d, start, 2D ) );
-
- graph.addEdge( new BaseLabeledWeightedEdge( "", a, b, 2D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", b, a, 2D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", b, c, 3D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", c, b, 3D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", c, goal, 3D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", goal, c, 3D ) );
-
- graph.addEdge( new BaseLabeledWeightedEdge( "", d, e, 3D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", e, d, 3D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", e, goal, 2D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", goal, e, 2D ) );
+ graph.addEdge( start, new BaseLabeledWeightedEdge( "start <-> a", 1.5D ), a );
+ graph.addEdge( start, new BaseLabeledWeightedEdge( "start <-> d", 2D ), d );
+
+ graph.addEdge( a, new BaseLabeledWeightedEdge( "a <-> b", 2D ), b );
+ graph.addEdge( b, new BaseLabeledWeightedEdge( "b <-> c", 3D ), c );
+ graph.addEdge( c, new BaseLabeledWeightedEdge( "c <-> goal", 3D ), goal );
+
+ graph.addEdge( d, new BaseLabeledWeightedEdge( "d <-> e", 3D ), e );
+ graph.addEdge( e, new BaseLabeledWeightedEdge( "e <-> goal", 2D ), goal );
// euristics
@@ -111,10 +104,10 @@ public final class AStarTestCase
expected.addVertexInTail( c );
expected.addVertexInTail( goal );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", start, a, 1.5D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", a, b, 2D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", b, c, 3D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", c, goal, 3D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "start <-> a", 1.5D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "a <-> b", 2D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "b <-> c", 3D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "c <-> goal", 3D ) );
// actual path
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java Mon Jun 27 08:56:09 2011
@@ -58,18 +58,18 @@ public final class DijkstraTestCase
graph.addVertex( five );
graph.addVertex( six );
- graph.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );
+ graph.addEdge( one, new BaseLabeledWeightedEdge( "1 -> 6", 14D ), six );
+ graph.addEdge( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
+ graph.addEdge( one, new BaseLabeledWeightedEdge( "1 -> 2", 7D ), two );
- graph.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );
+ graph.addEdge( two, new BaseLabeledWeightedEdge( "2 -> 3", 10D ), three );
+ graph.addEdge( two, new BaseLabeledWeightedEdge( "2 -> 4", 15D ), four );
- graph.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );
+ graph.addEdge( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
+ graph.addEdge( three, new BaseLabeledWeightedEdge( "3 -> 4", 11D ), four );
- graph.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
- graph.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
+ graph.addEdge( four, new BaseLabeledWeightedEdge( "4 -> 5", 6D ), five );
+ graph.addEdge( six, new BaseLabeledWeightedEdge( "6 -> 5", 9D ), five );
// expected path
@@ -81,9 +81,9 @@ public final class DijkstraTestCase
expected.addVertexInTail( six );
expected.addVertexInTail( five );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 3", 9D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "3 -> 6", 2D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "6 -> 5", 9D ) );
// actual path
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java Mon Jun 27 08:56:09 2011
@@ -19,8 +19,9 @@ package org.apache.commons.graph.shortes
* under the License.
*/
-import static org.apache.commons.graph.shortestpath.FloydWarshall.findAllVertexPairsShortestPath;
import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.fail;
+import static org.apache.commons.graph.shortestpath.FloydWarshall.findAllVertexPairsShortestPath;
import org.apache.commons.graph.MutableGraph;
import org.apache.commons.graph.UndirectedGraph;
@@ -73,35 +74,18 @@ public class FloydWarshallTestCase
mutable.addVertex( five );
mutable.addVertex( six );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );
-
- mutable.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );
+ mutable.addEdge( one, new BaseLabeledWeightedEdge( "1 -> 6", 14D ), six );
+ mutable.addEdge( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
+ mutable.addEdge( one, new BaseLabeledWeightedEdge( "1 -> 2", 7D ), two );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );
+ mutable.addEdge( two, new BaseLabeledWeightedEdge( "2 -> 3", 10D ), three );
+ mutable.addEdge( two, new BaseLabeledWeightedEdge( "2 -> 4", 15D ), four );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
+ mutable.addEdge( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
+ mutable.addEdge( three, new BaseLabeledWeightedEdge( "3 -> 4", 11D ), four );
- // reverse all edges
- if ( weighted instanceof UndirectedGraph )
- {
- mutable.addEdge( new BaseLabeledWeightedEdge( "", six, one, 14D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", three, one, 9D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", two, one, 7D ) );
-
- mutable.addEdge( new BaseLabeledWeightedEdge( "", three, two, 10D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", four, two, 15D ) );
-
- mutable.addEdge( new BaseLabeledWeightedEdge( "", six, three, 2D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", four, three, 11D ) );
-
- mutable.addEdge( new BaseLabeledWeightedEdge( "", five, four, 6D ) );
- mutable.addEdge( new BaseLabeledWeightedEdge( "", five, six, 9D ) );
- }
+ mutable.addEdge( four, new BaseLabeledWeightedEdge( "4 -> 5", 6D ), five );
+ mutable.addEdge( six, new BaseLabeledWeightedEdge( "6 -> 5", 9D ), five );
AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> p =
findAllVertexPairsShortestPath( weighted );
@@ -130,8 +114,8 @@ public class FloydWarshallTestCase
expected.addVertexInTail( three );
expected.addVertexInTail( six );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 3", 9D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "3 -> 6", 2D ) );
// Actual
assertEquals( expected, wp );
@@ -145,9 +129,16 @@ public class FloydWarshallTestCase
assertEquals( 20D, p.getShortestDistance( one, five ) );
assertEquals( Double.POSITIVE_INFINITY, p.getShortestDistance( five, one ) );
+ WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> wp;
// Verify shortest paths
- WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> wp = p.findShortestPath( five, one );
- assertEquals( null, wp );
+ try
+ {
+ wp = p.findShortestPath( five, one );
+ fail( "Path from {5} to {1} doesn't exist" );
+ }
+ catch (PathNotFoundException e) {
+ // wallow it
+ }
InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, six );
@@ -155,8 +146,8 @@ public class FloydWarshallTestCase
expected.addVertexInTail( three );
expected.addVertexInTail( six );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
- expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 3", 9D ) );
+ expected.addEdgeInTail( new BaseLabeledWeightedEdge( "3 -> 6", 2D ) );
// Actual
wp = p.findShortestPath( one, six );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java?rev=1140058&r1=1140057&r2=1140058&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java Mon Jun 27 08:56:09 2011
@@ -27,7 +27,7 @@ import java.util.List;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Vertex;
-public final class NodeSequenceVisitor<V extends Vertex, E extends Edge<V>>
+public final class NodeSequenceVisitor<V extends Vertex, E extends Edge>
extends BaseGraphVisitHandler<V, E>
{