You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by di...@apache.org on 2005/02/26 14:24:08 UTC
svn commit: r155447 [1/4] - in jakarta/commons/sandbox/graph2/trunk: ./
src/java/org/apache/commons/graph/
src/java/org/apache/commons/graph/algorithm/dataflow/
src/java/org/apache/commons/graph/algorithm/path/
src/java/org/apache/commons/graph/algorithm/search/
src/java/org/apache/commons/graph/algorithm/spanning/
src/java/org/apache/commons/graph/algorithm/util/
src/java/org/apache/commons/graph/contract/
src/java/org/apache/commons/graph/decorator/
src/java/org/apache/commons/graph/domain/basic/
src/java/org/apache/commons/graph/domain/dependency/
src/java/org/apache/commons/graph/domain/dependency/exception/
src/java/org/apache/commons/graph/domain/jdepend/
src/java/org/apache/commons/graph/domain/statemachine/
src/java/org/apache/commons/graph/domain/statemachine/exception/
src/java/org/apache/commons/graph/exception/
src/java/org/apache/commons/graph/factory/
src/java/org/apache/commons/graph/search/
src/java/org/apache/commons/graph/visualize/
src/test/org/apache/commons/graph/
src/test/org/apache/commons/graph/algorithm/dataflow/
src/test/org/apache/commons/graph/algorithm/path/
src/test/org/apache/commons/graph/algorithm/spanning/
src/test/org/apache/commons/graph/algorithm/util/
src/test/org/apache/commons/graph/contract/
src/test/org/apache/commons/graph/decorator/
src/test/org/apache/commons/graph/domain/dependency/ xdocs/
Author: dirkv
Date: Sat Feb 26 05:21:52 2005
New Revision: 155447
URL: http://svn.apache.org/viewcvs?view=rev&rev=155447
Log:
svn:keywords correction
Modified:
jakarta/commons/sandbox/graph2/trunk/LICENSE.txt (props changed)
jakarta/commons/sandbox/graph2/trunk/NOTICE.txt (props changed)
jakarta/commons/sandbox/graph2/trunk/build.xml (props changed)
jakarta/commons/sandbox/graph2/trunk/maven.xml (props changed)
jakarta/commons/sandbox/graph2/trunk/project.xml (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/DirectedGraph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Edge.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Graph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableDirectedGraph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableGraph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Named.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Path.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/UndirectedGraph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Vertex.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedEdge.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedGraph.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedPath.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowEquations.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/PathIterator.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/PathListener.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/CostSearch.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/DFS.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/Visitor.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/VisitorAdapter.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/Label.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Acyclic.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/AcyclicContract.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Contract.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/decorator/DDirectedGraph.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/basic/DirectedGraphImpl.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/basic/DirectedGraphWrapper.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/basic/GraphWrapper.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/basic/UndirectedGraphImpl.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/basic/WeightedGraphWrapper.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/dependency/Dependency.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/dependency/DependencyGraph.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/dependency/DependencyVertex.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/dependency/DependencyVisitor.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/dependency/exception/CircularDependencyException.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/jdepend/ClassVertex.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/jdepend/ImportEdge.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/jdepend/JDependGraph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/jdepend/OwnershipEdge.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/jdepend/PackageVertex.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/statemachine/State.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/statemachine/StateMachine.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/statemachine/Transition.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/domain/statemachine/exception/StateMachineException.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/exception/ContractVerificationException.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/exception/CycleException.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/exception/GraphException.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/exception/HyperGraphException.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/exception/NegativeCycleException.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/exception/NoPathException.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/factory/GraphFactory.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/search/CostSearch.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/search/DFS.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/search/Visitor.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/visualize/Colored.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/visualize/TouchGraph.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/DirGraphTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/GraphTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/UndirGraphTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/WeightedGraphTest.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutionsTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/algorithm/dataflow/MockDataFlowEq.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/algorithm/path/AllPairsTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/algorithm/path/AllPathsTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForestTest.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/algorithm/util/LabelTest.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/contract/AcyclicContractTest.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/contract/DAGTest.java (contents, props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/decorator/ShortestPathTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/decorator/TransposeTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/src/test/org/apache/commons/graph/domain/dependency/DependencyTest.java (props changed)
jakarta/commons/sandbox/graph2/trunk/xdocs/project.xml (props changed)
Propchange: jakarta/commons/sandbox/graph2/trunk/LICENSE.txt
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/NOTICE.txt
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/build.xml
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/maven.xml
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/project.xml
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/DirectedGraph.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/DirectedGraph.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/DirectedGraph.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/DirectedGraph.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,35 +14,35 @@
* 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 java.util.Set;
-
-/**
- * Description of the Interface
- */
-public interface DirectedGraph
- extends Graph
-{
- /**
- * getInbound( Vertex ) Returns the set of edges which are inbound to the
- * Vertex.
- */
- public Set getInbound(Vertex v);
-
- /**
- * getOutbound( Vertex ) Returns the set of edges which lead away from the
- * Vertex.
- */
- public Set getOutbound(Vertex v);
-
- /**
- * getSource( Edge ) Returns the vertex which originates the edge.
- */
- public Vertex getSource(Edge e);
-
- /**
- * getTarget( Edge ) Returns the vertex which terminates the edge.
- */
- public Vertex getTarget(Edge e);
-}
+ */
+
+import java.util.Set;
+
+/**
+ * Description of the Interface
+ */
+public interface DirectedGraph
+ extends Graph
+{
+ /**
+ * getInbound( Vertex ) Returns the set of edges which are inbound to the
+ * Vertex.
+ */
+ public Set getInbound(Vertex v);
+
+ /**
+ * getOutbound( Vertex ) Returns the set of edges which lead away from the
+ * Vertex.
+ */
+ public Set getOutbound(Vertex v);
+
+ /**
+ * getSource( Edge ) Returns the vertex which originates the edge.
+ */
+ public Vertex getSource(Edge e);
+
+ /**
+ * getTarget( Edge ) Returns the vertex which terminates the edge.
+ */
+ public Vertex getTarget(Edge e);
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/DirectedGraph.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Edge.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Edge.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Edge.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Edge.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,11 +14,11 @@
* 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.
- */
-
-/**
- * Description of the Interface
- */
-public interface Edge
-{
-}
+ */
+
+/**
+ * Description of the Interface
+ */
+public interface Edge
+{
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Edge.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Graph.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Graph.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Graph.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Graph.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,40 +14,40 @@
* 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.
- */
-/**
- * Graph This is the basic interface for a graph. G = { v, e }
- * getAdjacentVertices and getAdjacentEdges helps to define the behavior of
- * Edges.
- */
-
-import java.util.Set;
-
-/**
- * Description of the Interface
- */
-public interface Graph
-{
- /**
- * getVertices - Returns the total set of Vertices in the graph.
- */
- public Set getVertices();
-
- /**
- * getEdges - Returns the total set of Edges in the graph.
- */
- public Set getEdges();
-
- /**
- * getEdges( Vertex ) - This method will return all edges which touch this
- * vertex.
- */
- public Set getEdges(Vertex v);
-
- /**
- * getVertices( Edge ) - This method will return the set of Verticies on
- * this Edge. (2 for normal edges, > 2 for HyperEdges.)
- */
- public Set getVertices(Edge e);
-}
-
+ */
+/**
+ * Graph This is the basic interface for a graph. G = { v, e }
+ * getAdjacentVertices and getAdjacentEdges helps to define the behavior of
+ * Edges.
+ */
+
+import java.util.Set;
+
+/**
+ * Description of the Interface
+ */
+public interface Graph
+{
+ /**
+ * getVertices - Returns the total set of Vertices in the graph.
+ */
+ public Set getVertices();
+
+ /**
+ * getEdges - Returns the total set of Edges in the graph.
+ */
+ public Set getEdges();
+
+ /**
+ * getEdges( Vertex ) - This method will return all edges which touch this
+ * vertex.
+ */
+ public Set getEdges(Vertex v);
+
+ /**
+ * getVertices( Edge ) - This method will return the set of Verticies on
+ * this Edge. (2 for normal edges, > 2 for HyperEdges.)
+ */
+ public Set getVertices(Edge e);
+}
+
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Graph.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableDirectedGraph.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableDirectedGraph.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableDirectedGraph.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableDirectedGraph.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,39 +14,39 @@
* 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 org.apache.commons.graph.exception.*;
-
-/**
- * Description of the Interface
- */
-public interface MutableDirectedGraph
- extends DirectedGraph
-{
- /**
- * Adds a feature to the Vertex attribute of the MutableDirectedGraph object
- */
- public void addVertex(Vertex v)
- throws GraphException;
-
- /**
- * Adds a feature to the Edge attribute of the MutableDirectedGraph object
- */
- public void addEdge(Edge e,
- Vertex source,
- Vertex target)
- throws GraphException;
-
- /**
- * Description of the Method
- */
- public void removeVertex(Vertex v)
- throws GraphException;
-
- /**
- * Description of the Method
- */
- public void removeEdge(Edge e)
- throws GraphException;
-}
+ */
+
+import org.apache.commons.graph.exception.*;
+
+/**
+ * Description of the Interface
+ */
+public interface MutableDirectedGraph
+ extends DirectedGraph
+{
+ /**
+ * Adds a feature to the Vertex attribute of the MutableDirectedGraph object
+ */
+ public void addVertex(Vertex v)
+ throws GraphException;
+
+ /**
+ * Adds a feature to the Edge attribute of the MutableDirectedGraph object
+ */
+ public void addEdge(Edge e,
+ Vertex source,
+ Vertex target)
+ throws GraphException;
+
+ /**
+ * Description of the Method
+ */
+ public void removeVertex(Vertex v)
+ throws GraphException;
+
+ /**
+ * Description of the Method
+ */
+ public void removeEdge(Edge e)
+ throws GraphException;
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableDirectedGraph.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableGraph.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableGraph.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableGraph.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableGraph.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,49 +14,49 @@
* 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 org.apache.commons.graph.exception.*;
-
-/**
- * Description of the Interface
- */
-public interface MutableGraph
- extends Graph
-{
- /**
- * Adds a feature to the Vertex attribute of the MutableGraph object
- */
- public void addVertex(Vertex v)
- throws GraphException;
-
- /**
- * Description of the Method
- */
- public void removeVertex(Vertex v)
- throws GraphException;
-
- /**
- * Adds a feature to the Edge attribute of the MutableGraph object
- */
- public void addEdge(Edge e)
- throws GraphException;
-
- /**
- * Description of the Method
- */
- public void removeEdge(Edge e)
- throws GraphException;
-
- /**
- * Description of the Method
- */
- public void connect(Edge e, Vertex v)
- throws GraphException;
-
- /**
- * Description of the Method
- */
- public void disconnect(Edge e, Vertex v)
- throws GraphException;
-}
+ */
+
+import org.apache.commons.graph.exception.*;
+
+/**
+ * Description of the Interface
+ */
+public interface MutableGraph
+ extends Graph
+{
+ /**
+ * Adds a feature to the Vertex attribute of the MutableGraph object
+ */
+ public void addVertex(Vertex v)
+ throws GraphException;
+
+ /**
+ * Description of the Method
+ */
+ public void removeVertex(Vertex v)
+ throws GraphException;
+
+ /**
+ * Adds a feature to the Edge attribute of the MutableGraph object
+ */
+ public void addEdge(Edge e)
+ throws GraphException;
+
+ /**
+ * Description of the Method
+ */
+ public void removeEdge(Edge e)
+ throws GraphException;
+
+ /**
+ * Description of the Method
+ */
+ public void connect(Edge e, Vertex v)
+ throws GraphException;
+
+ /**
+ * Description of the Method
+ */
+ public void disconnect(Edge e, Vertex v)
+ throws GraphException;
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/MutableGraph.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Named.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Named.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Named.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Named.java Sat Feb 26 05:21:52 2005
@@ -1,12 +1,12 @@
-package org.apache.commons.graph;
-
-/**
- * Description of the Interface
- */
-public interface Named
-{
- /**
- * Gets the name attribute of the Named object
- */
- public String getName();
-}
+package org.apache.commons.graph;
+
+/**
+ * Description of the Interface
+ */
+public interface Named
+{
+ /**
+ * Gets the name attribute of the Named object
+ */
+ public String getName();
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Named.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Path.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Path.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Path.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Path.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,42 +14,42 @@
* 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 java.util.List;
-
-/**
- * Description of the Interface
- */
-public interface Path
-{
- /**
- * Returns the start of the path.
- */
- public Vertex getStart();
-
- /**
- * Returns the end of the path.
- */
- public Vertex getEnd();
-
- /**
- * getVertices() - This returns a list of Vertices, in order as they go from
- * Start to End. This includes the Start and End vertex, and will have one
- * more entry than the Edges list.
- */
- public List getVertices();
-
- /**
- * getEdges() - This returns a list of Edges which comprise the path. It
- * will have one less than the list of Vertices.
- */
- public List getEdges();
-
- /**
- * size() - This returns the size of the path in terms of number of
- * verticies it visits.
- */
- public int size();
-
-}
+ */
+
+import java.util.List;
+
+/**
+ * Description of the Interface
+ */
+public interface Path
+{
+ /**
+ * Returns the start of the path.
+ */
+ public Vertex getStart();
+
+ /**
+ * Returns the end of the path.
+ */
+ public Vertex getEnd();
+
+ /**
+ * getVertices() - This returns a list of Vertices, in order as they go from
+ * Start to End. This includes the Start and End vertex, and will have one
+ * more entry than the Edges list.
+ */
+ public List getVertices();
+
+ /**
+ * getEdges() - This returns a list of Edges which comprise the path. It
+ * will have one less than the list of Vertices.
+ */
+ public List getEdges();
+
+ /**
+ * size() - This returns the size of the path in terms of number of
+ * verticies it visits.
+ */
+ public int size();
+
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Path.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/UndirectedGraph.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/UndirectedGraph.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/UndirectedGraph.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/UndirectedGraph.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,12 +14,12 @@
* 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.
- */
-
-/**
- * Description of the Interface
- */
-public interface UndirectedGraph
- extends Graph
-{
-}
+ */
+
+/**
+ * Description of the Interface
+ */
+public interface UndirectedGraph
+ extends Graph
+{
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/UndirectedGraph.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Vertex.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Vertex.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Vertex.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Vertex.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,11 +14,11 @@
* 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.
- */
-
-/**
- * Description of the Interface
- */
-public interface Vertex
-{
-}
+ */
+
+/**
+ * Description of the Interface
+ */
+public interface Vertex
+{
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/Vertex.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedEdge.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedEdge.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedEdge.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedEdge.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,16 +14,16 @@
* 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.
- */
-
-/**
- * Description of the Interface
- */
-public interface WeightedEdge
- extends Edge
-{
- /**
- * Gets the weight attribute of the WeightedEdge object
- */
- public double getWeight();
-}
+ */
+
+/**
+ * Description of the Interface
+ */
+public interface WeightedEdge
+ extends Edge
+{
+ /**
+ * Gets the weight attribute of the WeightedEdge object
+ */
+ public double getWeight();
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedEdge.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedGraph.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedPath.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedPath.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedPath.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedPath.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph;
-
+package org.apache.commons.graph;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,16 +14,16 @@
* 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.
- */
-
-/**
- * Description of the Interface
- */
-public interface WeightedPath
- extends Path
-{
- /**
- * Gets the weight attribute of the WeightedPath object
- */
- public double getWeight();
-}
+ */
+
+/**
+ * Description of the Interface
+ */
+public interface WeightedPath
+ extends Path
+{
+ /**
+ * Gets the weight attribute of the WeightedPath object
+ */
+ public double getWeight();
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/WeightedPath.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowEquations.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph.algorithm.path;
-
+package org.apache.commons.graph.algorithm.path;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,354 +14,354 @@
* 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.
- */
-
-/**
- * AllPairs solves the All Points Shortest Path problem for a DirectedGraph. (If
- * it is weighted, it will do shortest path by weight. Otherwise shortest path
- * by jumps.) Uses Floyd's Algorithm.
- */
-
-import java.util.Set;
-import java.util.Map;
-import java.util.List;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.ArrayList;
-import java.util.AbstractList;
-
-import org.apache.commons.graph.*;
-import org.apache.commons.graph.exception.*;
-
-/**
- * Description of the Class
- */
-public class AllPairsShortestPath
-{
- private int pred[][];
- private double cost[][];
- private Vertex vArray[];
- private DirectedGraph graph;
- private Map vertexIndex = new HashMap();// VERTEX X INTEGER
-
- /**
- * Description of the Class
- */
- public class EdgeList
- extends AbstractList
- {
- private DirectedGraph graph;
- private List vertices;
-
- /**
- * Constructor for the EdgeList object
- *
- * @param graph
- * @param vertices
- */
- public EdgeList(DirectedGraph graph,
- List vertices)
- {
- this.graph = graph;
- this.vertices = vertices;
- }
-
- /**
- * Description of the Method
- */
- public int size()
- {
- return vertices.size() - 1;
- }
-
- /**
- * Description of the Method
- */
- public Object get(int index)
- {
- Edge RC = null;
-
- Vertex source = (Vertex) vertices.get(index);
- Vertex target = (Vertex) vertices.get(index + 1);
-
- Set outboundSet = graph.getOutbound(source);
- if (outboundSet == null)
- {
- return null;
- }
-
- Iterator outbound = outboundSet.iterator();
- while (outbound.hasNext())
- {
- RC = (Edge) outbound.next();
- if (graph.getTarget(RC) == target)
- {
- break;
- }
- }
-
- if (graph.getTarget(RC) != target)
- {
- return null;
- }
-
- return RC;
- }
- }
-
- /**
- * Description of the Class
- */
- public class WPath
- implements WeightedPath
- {
- private Vertex start;
- private Vertex finish;
- private List vertexList = new ArrayList();
- private DirectedGraph graph;
- private double cost;
-
- /**
- * Constructor for the WPath object
- *
- * @param graph
- * @param vArray
- * @param pred
- * @param start
- * @param finish
- * @param cost
- * @exception GraphException
- */
- public WPath(DirectedGraph graph,
- Vertex vArray[], int pred[][],
- int start, int finish, double cost)
- throws GraphException
- {
- this.start = vArray[start];
- this.finish = vArray[finish];
- this.cost = cost;
- this.graph = graph;
-
- vertexList.addAll(segment(vArray, pred,
- start, finish));
- vertexList.add(vArray[finish]);
- }
-
- /**
- * Returns a List of Vectors in order. Includes the start, but not the
- * finish.
- */
- private List segment(Vertex vArray[], int pred[][],
- int start, int finish)
- throws GraphException
- {
- int mid = pred[start][finish];
- if (mid == -1)
- {
- throw new NoPathException("No SubPath Available: " +
- vArray[start] + " -> " +
- vArray[finish]);
- }
- List RC = new ArrayList();
-
- if (start == finish)
- {
- return RC;
- }
-
- if (start == mid)
- {
- RC.add(vArray[start]);
-
- }
- else
- {
- RC.addAll(segment(vArray, pred,
- start, mid));
- RC.add(vArray[mid]);
- }
-
- if (mid == pred[mid][finish])
- {
- }
- else
- {
- RC.addAll(segment(vArray, pred,
- mid, finish));
- }
- return RC;
- }
-
- /**
- * Gets the weight attribute of the WPath object
- */
- public double getWeight()
- {
- return cost;
- }
-
- /**
- * Gets the vertices attribute of the WPath object
- */
- public List getVertices()
- {
- return vertexList;
- }
-
- /**
- * Gets the edges attribute of the WPath object
- */
- public List getEdges()
- {
- return new EdgeList(graph, vertexList);
- }
-
- /**
- * Gets the start attribute of the WPath object
- */
- public Vertex getStart()
- {
- return start;
- }
-
- /**
- * Gets the end attribute of the WPath object
- */
- public Vertex getEnd()
- {
- return finish;
- }
-
- public int size() {
- return vertexList.size();
- }
- }
-
- /**
- * Constructor for the AllPairsShortestPath object
- *
- * @param graph
- * @exception NegativeCycleException
- */
- public AllPairsShortestPath(DirectedGraph graph)
- throws NegativeCycleException
- {
- update(graph);
- }
-
-
- /**
- * Description of the Method
- */
- private void initIndex(Vertex vArray[])
- {
- for (int i = 0; i < vArray.length; i++)
- {
- vertexIndex.put(vArray[i], new Integer(i));
- }
- }
-
- /**
- * Description of the Method
- */
- public void update(DirectedGraph graph)
- {
- this.graph = graph;
-
- Set vertexSet = graph.getVertices();
- vArray = (Vertex[]) vertexSet.toArray(new Vertex[vertexSet.size()]);
-
- initIndex(vArray);
-
- pred = new int[vArray.length][vArray.length];
- cost = new double[vArray.length][vArray.length];
-
- for (int i = 0; i < vArray.length; i++)
- {
- for (int j = 0; j < vArray.length; j++)
- {
- pred[i][j] = -1;
- cost[i][j] = Double.POSITIVE_INFINITY;
- }
-
- // First round values need to be in the matrix.
- Iterator edgeSet = graph.getOutbound(vArray[i]).iterator();
- while (edgeSet.hasNext())
- {
- Edge e = (Edge) edgeSet.next();
- int j = index(graph.getTarget(e));
- pred[i][j] = i;
- if (graph instanceof WeightedGraph)
- {
- cost[i][j] = ((WeightedGraph) graph).getWeight(e);
- }
- else
- {
- cost[i][j] = 1.0;
- }
- }
-
- // Cost from any node to itself is 0.0
- cost[i][i] = 0.0;
- pred[i][i] = i;
- }
-
- compute(graph, vArray);
-
- }
-
- /**
- * Description of the Method
- */
- private int index(Vertex v)
- {
- return ((Integer) vertexIndex.get(v)).intValue();
- }
-
- /**
- * Description of the Method
- */
- private void compute(DirectedGraph graph, Vertex vArray[])
- throws NegativeCycleException
- {
- for (int k = 0; k < vArray.length; k++)
- {// Mid Point
- for (int i = 0; i < vArray.length; i++)
- {// Source
- for (int j = 0; j < vArray.length; j++)
- {// Target
- if (cost[i][k] + cost[k][j] < cost[i][j])
- {
- if (i == j)
- {
- throw new NegativeCycleException();
- }
-
- // It is cheaper to go through K.
- cost[i][j] = cost[i][k] + cost[k][j];
- pred[i][j] = k;
- }
- }
- }
- }
- }
-
- /**
- * Gets the shortestPath attribute of the AllPairsShortestPath object
- */
- public WeightedPath getShortestPath(Vertex start, Vertex end)
- throws GraphException
- {
- return new WPath(graph, vArray, pred,
- index(start), index(end),
- cost[index(start)][index(end)]);
- }
-
- /**
- * Determines if a path exists or not.
- */
- public boolean hasPath( Vertex start, Vertex end )
- {
- return cost[index(start)][index(end)] < Double.POSITIVE_INFINITY;
- }
-}
+ */
+
+/**
+ * AllPairs solves the All Points Shortest Path problem for a DirectedGraph. (If
+ * it is weighted, it will do shortest path by weight. Otherwise shortest path
+ * by jumps.) Uses Floyd's Algorithm.
+ */
+
+import java.util.Set;
+import java.util.Map;
+import java.util.List;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.ArrayList;
+import java.util.AbstractList;
+
+import org.apache.commons.graph.*;
+import org.apache.commons.graph.exception.*;
+
+/**
+ * Description of the Class
+ */
+public class AllPairsShortestPath
+{
+ private int pred[][];
+ private double cost[][];
+ private Vertex vArray[];
+ private DirectedGraph graph;
+ private Map vertexIndex = new HashMap();// VERTEX X INTEGER
+
+ /**
+ * Description of the Class
+ */
+ public class EdgeList
+ extends AbstractList
+ {
+ private DirectedGraph graph;
+ private List vertices;
+
+ /**
+ * Constructor for the EdgeList object
+ *
+ * @param graph
+ * @param vertices
+ */
+ public EdgeList(DirectedGraph graph,
+ List vertices)
+ {
+ this.graph = graph;
+ this.vertices = vertices;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public int size()
+ {
+ return vertices.size() - 1;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public Object get(int index)
+ {
+ Edge RC = null;
+
+ Vertex source = (Vertex) vertices.get(index);
+ Vertex target = (Vertex) vertices.get(index + 1);
+
+ Set outboundSet = graph.getOutbound(source);
+ if (outboundSet == null)
+ {
+ return null;
+ }
+
+ Iterator outbound = outboundSet.iterator();
+ while (outbound.hasNext())
+ {
+ RC = (Edge) outbound.next();
+ if (graph.getTarget(RC) == target)
+ {
+ break;
+ }
+ }
+
+ if (graph.getTarget(RC) != target)
+ {
+ return null;
+ }
+
+ return RC;
+ }
+ }
+
+ /**
+ * Description of the Class
+ */
+ public class WPath
+ implements WeightedPath
+ {
+ private Vertex start;
+ private Vertex finish;
+ private List vertexList = new ArrayList();
+ private DirectedGraph graph;
+ private double cost;
+
+ /**
+ * Constructor for the WPath object
+ *
+ * @param graph
+ * @param vArray
+ * @param pred
+ * @param start
+ * @param finish
+ * @param cost
+ * @exception GraphException
+ */
+ public WPath(DirectedGraph graph,
+ Vertex vArray[], int pred[][],
+ int start, int finish, double cost)
+ throws GraphException
+ {
+ this.start = vArray[start];
+ this.finish = vArray[finish];
+ this.cost = cost;
+ this.graph = graph;
+
+ vertexList.addAll(segment(vArray, pred,
+ start, finish));
+ vertexList.add(vArray[finish]);
+ }
+
+ /**
+ * Returns a List of Vectors in order. Includes the start, but not the
+ * finish.
+ */
+ private List segment(Vertex vArray[], int pred[][],
+ int start, int finish)
+ throws GraphException
+ {
+ int mid = pred[start][finish];
+ if (mid == -1)
+ {
+ throw new NoPathException("No SubPath Available: " +
+ vArray[start] + " -> " +
+ vArray[finish]);
+ }
+ List RC = new ArrayList();
+
+ if (start == finish)
+ {
+ return RC;
+ }
+
+ if (start == mid)
+ {
+ RC.add(vArray[start]);
+
+ }
+ else
+ {
+ RC.addAll(segment(vArray, pred,
+ start, mid));
+ RC.add(vArray[mid]);
+ }
+
+ if (mid == pred[mid][finish])
+ {
+ }
+ else
+ {
+ RC.addAll(segment(vArray, pred,
+ mid, finish));
+ }
+ return RC;
+ }
+
+ /**
+ * Gets the weight attribute of the WPath object
+ */
+ public double getWeight()
+ {
+ return cost;
+ }
+
+ /**
+ * Gets the vertices attribute of the WPath object
+ */
+ public List getVertices()
+ {
+ return vertexList;
+ }
+
+ /**
+ * Gets the edges attribute of the WPath object
+ */
+ public List getEdges()
+ {
+ return new EdgeList(graph, vertexList);
+ }
+
+ /**
+ * Gets the start attribute of the WPath object
+ */
+ public Vertex getStart()
+ {
+ return start;
+ }
+
+ /**
+ * Gets the end attribute of the WPath object
+ */
+ public Vertex getEnd()
+ {
+ return finish;
+ }
+
+ public int size() {
+ return vertexList.size();
+ }
+ }
+
+ /**
+ * Constructor for the AllPairsShortestPath object
+ *
+ * @param graph
+ * @exception NegativeCycleException
+ */
+ public AllPairsShortestPath(DirectedGraph graph)
+ throws NegativeCycleException
+ {
+ update(graph);
+ }
+
+
+ /**
+ * Description of the Method
+ */
+ private void initIndex(Vertex vArray[])
+ {
+ for (int i = 0; i < vArray.length; i++)
+ {
+ vertexIndex.put(vArray[i], new Integer(i));
+ }
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void update(DirectedGraph graph)
+ {
+ this.graph = graph;
+
+ Set vertexSet = graph.getVertices();
+ vArray = (Vertex[]) vertexSet.toArray(new Vertex[vertexSet.size()]);
+
+ initIndex(vArray);
+
+ pred = new int[vArray.length][vArray.length];
+ cost = new double[vArray.length][vArray.length];
+
+ for (int i = 0; i < vArray.length; i++)
+ {
+ for (int j = 0; j < vArray.length; j++)
+ {
+ pred[i][j] = -1;
+ cost[i][j] = Double.POSITIVE_INFINITY;
+ }
+
+ // First round values need to be in the matrix.
+ Iterator edgeSet = graph.getOutbound(vArray[i]).iterator();
+ while (edgeSet.hasNext())
+ {
+ Edge e = (Edge) edgeSet.next();
+ int j = index(graph.getTarget(e));
+ pred[i][j] = i;
+ if (graph instanceof WeightedGraph)
+ {
+ cost[i][j] = ((WeightedGraph) graph).getWeight(e);
+ }
+ else
+ {
+ cost[i][j] = 1.0;
+ }
+ }
+
+ // Cost from any node to itself is 0.0
+ cost[i][i] = 0.0;
+ pred[i][i] = i;
+ }
+
+ compute(graph, vArray);
+
+ }
+
+ /**
+ * Description of the Method
+ */
+ private int index(Vertex v)
+ {
+ return ((Integer) vertexIndex.get(v)).intValue();
+ }
+
+ /**
+ * Description of the Method
+ */
+ private void compute(DirectedGraph graph, Vertex vArray[])
+ throws NegativeCycleException
+ {
+ for (int k = 0; k < vArray.length; k++)
+ {// Mid Point
+ for (int i = 0; i < vArray.length; i++)
+ {// Source
+ for (int j = 0; j < vArray.length; j++)
+ {// Target
+ if (cost[i][k] + cost[k][j] < cost[i][j])
+ {
+ if (i == j)
+ {
+ throw new NegativeCycleException();
+ }
+
+ // It is cheaper to go through K.
+ cost[i][j] = cost[i][k] + cost[k][j];
+ pred[i][j] = k;
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Gets the shortestPath attribute of the AllPairsShortestPath object
+ */
+ public WeightedPath getShortestPath(Vertex start, Vertex end)
+ throws GraphException
+ {
+ return new WPath(graph, vArray, pred,
+ index(start), index(end),
+ cost[index(start)][index(end)]);
+ }
+
+ /**
+ * Determines if a path exists or not.
+ */
+ public boolean hasPath( Vertex start, Vertex end )
+ {
+ return cost[index(start)][index(end)] < Double.POSITIVE_INFINITY;
+ }
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph.algorithm.path;
-
+package org.apache.commons.graph.algorithm.path;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,155 +14,155 @@
* 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.
- */
-
-/**
- * AllPaths finds for each pair of vertices, {i, j} the set of
- * all potential paths between them. (Unrolling loops by a set
- * amount.
- */
-
-import java.util.Map;
-import java.util.Set;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-
-import org.apache.commons.graph.*;
-import org.apache.commons.graph.algorithm.util.*;
-
-public class AllPaths
-{
- private Map allPaths = new HashMap(); // VERTEX PAIR X SET( PATHS )
-
- private AllPairsShortestPath apsp = null;
- private DirectedGraph graph = null;
-
- public AllPaths( DirectedGraph graph ) {
- this.graph = graph;
- try {
- apsp = new AllPairsShortestPath( graph );
- } catch (Exception ex) {
- ex.printStackTrace();
- }
- }
-
- public Iterator findPaths( final Vertex i,
- final Vertex j ) {
- final PathIterator RC = new PathIterator();
-
- Runnable run = new Runnable() {
- public void run() {
- findPaths( RC, i, j, Integer.MAX_VALUE );
- }
- };
- Thread thread = new Thread( run );
-
- RC.setThread( thread );
-
- thread.start();
-
- return RC;
- }
-
- public void findPaths( PathListener listener,
- Vertex i, Vertex j,
- int maxLength ) {
- Set workingSet = new HashSet();
- workingSet.add( new PathImpl( i ));
-
- for (int k = 0; k < maxLength; k++) {
- Iterator workingPaths = workingSet.iterator();
- if (!workingPaths.hasNext()) break;
-
- Set newWorkingSet = new HashSet();
-
- while (workingPaths.hasNext()) {
- PathImpl workingPath = (PathImpl) workingPaths.next();
-
- Iterator outbound =
- graph.getOutbound(workingPath.getEnd()).iterator();
-
- while (outbound.hasNext()) {
- Edge obEdge = (Edge) outbound.next();
- if (apsp.hasPath( graph.getTarget( obEdge ), j)) {
-
- PathImpl path =
- workingPath.append(graph.getTarget(obEdge),
- obEdge );
-
-
- newWorkingSet.add( path );
-
- if (path.getEnd() == j) {
- listener.notifyPath( path );
- }
- }
- }
- }
-
- workingSet = newWorkingSet;
- }
- }
-
- /**
- * getAllPaths will return the set of all possible ways of moving
- * from i to j using the directed graph AllPaths was initialized
- * with.
- *
- * @deprecated Use findPaths instead. Doesn't work, but code
- * may be useful in the near future.
- */
- public Set getAllPaths( Vertex i, Vertex j ) {
- Set RC = new HashSet();
- VertexPair key = new VertexPair( i, j );
-
- // If we have already started this, return what we
- // were doing. (May still be in progress.)
- //
- // If we haven't started, go ahead and start. . .
- if (allPaths.containsKey( key )) {
- return (Set) allPaths.get( key );
- } else {
- allPaths.put( key, RC );
- }
-
- Iterator outbounds = graph.getOutbound(i).iterator();
-
- while (outbounds.hasNext()) {
- Edge outbound = (Edge) outbounds.next();
- if (graph.getTarget( outbound ) == j) {
- RC.add( new PathImpl( i, j, outbound ));
- }
- }
-
- Iterator ks = graph.getVertices().iterator();
- while (ks.hasNext()) {
- Vertex k = (Vertex) ks.next();
- if (k != i && k != j) {
- appendPaths( RC,
- getAllPaths( i, k ),
- getAllPaths( k, j ));
- }
- }
-
- allPaths.put( key, RC );
- return RC;
- }
-
- public void appendPaths( Set RC, Set iks, Set kjs ) {
- Iterator ikPaths = iks.iterator();
- while (ikPaths.hasNext()) {
- PathImpl ik = (PathImpl) ikPaths.next();
-
- Iterator kjPaths = kjs.iterator();
- while (kjPaths.hasNext()) {
- PathImpl kj = (PathImpl) kjPaths.next();
- RC.add( ik.append( kj ));
- }
- }
- }
-}
-
-
-
+ */
+
+/**
+ * AllPaths finds for each pair of vertices, {i, j} the set of
+ * all potential paths between them. (Unrolling loops by a set
+ * amount.
+ */
+
+import java.util.Map;
+import java.util.Set;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+
+import org.apache.commons.graph.*;
+import org.apache.commons.graph.algorithm.util.*;
+
+public class AllPaths
+{
+ private Map allPaths = new HashMap(); // VERTEX PAIR X SET( PATHS )
+
+ private AllPairsShortestPath apsp = null;
+ private DirectedGraph graph = null;
+
+ public AllPaths( DirectedGraph graph ) {
+ this.graph = graph;
+ try {
+ apsp = new AllPairsShortestPath( graph );
+ } catch (Exception ex) {
+ ex.printStackTrace();
+ }
+ }
+
+ public Iterator findPaths( final Vertex i,
+ final Vertex j ) {
+ final PathIterator RC = new PathIterator();
+
+ Runnable run = new Runnable() {
+ public void run() {
+ findPaths( RC, i, j, Integer.MAX_VALUE );
+ }
+ };
+ Thread thread = new Thread( run );
+
+ RC.setThread( thread );
+
+ thread.start();
+
+ return RC;
+ }
+
+ public void findPaths( PathListener listener,
+ Vertex i, Vertex j,
+ int maxLength ) {
+ Set workingSet = new HashSet();
+ workingSet.add( new PathImpl( i ));
+
+ for (int k = 0; k < maxLength; k++) {
+ Iterator workingPaths = workingSet.iterator();
+ if (!workingPaths.hasNext()) break;
+
+ Set newWorkingSet = new HashSet();
+
+ while (workingPaths.hasNext()) {
+ PathImpl workingPath = (PathImpl) workingPaths.next();
+
+ Iterator outbound =
+ graph.getOutbound(workingPath.getEnd()).iterator();
+
+ while (outbound.hasNext()) {
+ Edge obEdge = (Edge) outbound.next();
+ if (apsp.hasPath( graph.getTarget( obEdge ), j)) {
+
+ PathImpl path =
+ workingPath.append(graph.getTarget(obEdge),
+ obEdge );
+
+
+ newWorkingSet.add( path );
+
+ if (path.getEnd() == j) {
+ listener.notifyPath( path );
+ }
+ }
+ }
+ }
+
+ workingSet = newWorkingSet;
+ }
+ }
+
+ /**
+ * getAllPaths will return the set of all possible ways of moving
+ * from i to j using the directed graph AllPaths was initialized
+ * with.
+ *
+ * @deprecated Use findPaths instead. Doesn't work, but code
+ * may be useful in the near future.
+ */
+ public Set getAllPaths( Vertex i, Vertex j ) {
+ Set RC = new HashSet();
+ VertexPair key = new VertexPair( i, j );
+
+ // If we have already started this, return what we
+ // were doing. (May still be in progress.)
+ //
+ // If we haven't started, go ahead and start. . .
+ if (allPaths.containsKey( key )) {
+ return (Set) allPaths.get( key );
+ } else {
+ allPaths.put( key, RC );
+ }
+
+ Iterator outbounds = graph.getOutbound(i).iterator();
+
+ while (outbounds.hasNext()) {
+ Edge outbound = (Edge) outbounds.next();
+ if (graph.getTarget( outbound ) == j) {
+ RC.add( new PathImpl( i, j, outbound ));
+ }
+ }
+
+ Iterator ks = graph.getVertices().iterator();
+ while (ks.hasNext()) {
+ Vertex k = (Vertex) ks.next();
+ if (k != i && k != j) {
+ appendPaths( RC,
+ getAllPaths( i, k ),
+ getAllPaths( k, j ));
+ }
+ }
+
+ allPaths.put( key, RC );
+ return RC;
+ }
+
+ public void appendPaths( Set RC, Set iks, Set kjs ) {
+ Iterator ikPaths = iks.iterator();
+ while (ikPaths.hasNext()) {
+ PathImpl ik = (PathImpl) ikPaths.next();
+
+ Iterator kjPaths = kjs.iterator();
+ while (kjPaths.hasNext()) {
+ PathImpl kj = (PathImpl) kjPaths.next();
+ RC.add( ik.append( kj ));
+ }
+ }
+ }
+}
+
+
+
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/PathIterator.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/path/PathListener.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/CostSearch.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/DFS.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/Visitor.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/Visitor.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/Visitor.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/Visitor.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph.algorithm.search;
-
+package org.apache.commons.graph.algorithm.search;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,42 +14,42 @@
* 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 org.apache.commons.graph.*;
-
-/**
- * Description of the Interface
- */
-public interface Visitor
-{
- /**
- * Description of the Method
- */
- public void discoverGraph(Graph graph);
-
- /**
- * Description of the Method
- */
- public void discoverVertex(Vertex vertex);
-
- /**
- * Description of the Method
- */
- public void discoverEdge(Edge edge);
-
- /**
- * Description of the Method
- */
- public void finishEdge(Edge edge);
-
- /**
- * Description of the Method
- */
- public void finishVertex(Vertex vertex);
-
- /**
- * Description of the Method
- */
- public void finishGraph(Graph graph);
-}
+ */
+
+import org.apache.commons.graph.*;
+
+/**
+ * Description of the Interface
+ */
+public interface Visitor
+{
+ /**
+ * Description of the Method
+ */
+ public void discoverGraph(Graph graph);
+
+ /**
+ * Description of the Method
+ */
+ public void discoverVertex(Vertex vertex);
+
+ /**
+ * Description of the Method
+ */
+ public void discoverEdge(Edge edge);
+
+ /**
+ * Description of the Method
+ */
+ public void finishEdge(Edge edge);
+
+ /**
+ * Description of the Method
+ */
+ public void finishVertex(Vertex vertex);
+
+ /**
+ * Description of the Method
+ */
+ public void finishGraph(Graph graph);
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/Visitor.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/search/VisitorAdapter.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java Sat Feb 26 05:21:52 2005
@@ -1,151 +1,151 @@
-package org.apache.commons.graph.algorithm.spanning;
-
-import org.apache.commons.graph.*;
-import org.apache.commons.graph.exception.*;
-import org.apache.commons.graph.decorator.*;
-import org.apache.commons.graph.domain.basic.*;
-import org.apache.commons.graph.algorithm.util.*;
-
-import org.apache.commons.collections.PriorityQueue;
-import org.apache.commons.collections.BinaryHeap;
-
-import java.util.Map;
-import java.util.Set;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.Comparator;
-
-public class MinimumSpanningForest
- extends UndirectedGraphImpl
- implements UndirectedGraph,
- WeightedGraph
-{
- private PriorityQueue queue = null;
- private Map labels = new HashMap(); // VERTEX X LABEL
- private Set chords = new HashSet(); // Edges not in MSF.
-
- private DDirectedGraph ddg = null;
-
- public class WeightedEdgeComparator
- implements Comparator
- {
- private WeightedGraph graph = null;
- public WeightedEdgeComparator( WeightedGraph graph ) {
- this.graph = graph;
- }
-
- public int compare( Object o1, Object o2 ) {
- if ((o1 instanceof Edge) &&
- (o2 instanceof Edge)) {
- double val = ( graph.getWeight( (Edge) o1 ) -
- graph.getWeight( (Edge) o2 ));
- if (val > 0) return 1;
- if (val == 0) return 0;
- if (val < 0) return -1;
- }
-
- return -1;
- }
- }
-
- public MinimumSpanningForest( WeightedGraph graph ) {
- calculateMSF( true, graph );
- }
-
- public MinimumSpanningForest( boolean isMin, WeightedGraph graph ) {
- calculateMSF( isMin, graph );
- }
-
- protected Label findLabel( Vertex v ) {
- return (Label) labels.get( v );
- }
-
- protected boolean connectsLabels( Graph graph,
- Edge e )
- {
- Label first = null;
- Label second = null;
-
- Iterator vertices = graph.getVertices( e ).iterator();
- if (vertices.hasNext()) {
- first = findLabel( (Vertex) vertices.next() );
- } else { return false; }
-
- if (vertices.hasNext()) {
- second = findLabel( (Vertex) vertices.next() );
- } else { return false; }
-
- if (vertices.hasNext()) {
- throw new HyperGraphException("Unable to compute MSF on Hypergraph.");
- }
-
- return !first.getRoot().equals( second.getRoot() );
- }
-
- protected void addEdge( WeightedGraph graph,
- Edge edge ) {
- addEdge( edge );
- chords.remove( edge );
- Iterator vertices = graph.getVertices( edge ).iterator();
- Label prime = null;
-
- if (vertices.hasNext()) {
- Vertex p = (Vertex) vertices.next();
- prime = findLabel( p );
-
- connect( edge, p );
- }
-
- while (vertices.hasNext()) {
- Vertex v = (Vertex) vertices.next();
-
- Label l = findLabel( v );
- l.setRoot( prime );
-
- connect( edge, v );
- }
-
- setWeight( edge, graph.getWeight( edge ));
- }
-
- protected void calculateMSF( boolean isMin,
- WeightedGraph graph ) {
-
- PriorityQueue queue =
- new BinaryHeap( isMin, new WeightedEdgeComparator( graph ));
-
- chords = new HashSet( graph.getEdges() );
-
- // Fill the Queue with all the edges.
- Iterator edges = graph.getEdges().iterator();
- while (edges.hasNext()) {
- queue.insert( edges.next() );
- }
-
- // Fill the graph we have with all the Vertexes.
- Iterator vertices = graph.getVertices().iterator();
- while (vertices.hasNext()) {
- Vertex v = (Vertex) vertices.next();
- labels.put( v, new Label() );
- addVertex( v );
- }
-
- // Bring the edges out in the right order.
- while (!queue.isEmpty()) {
- Edge e = (Edge) queue.pop();
-
- if ( connectsLabels( graph, e )) {
- addEdge( graph, e );
- }
- }
- }
-
- public Set getChords() {
- return chords;
- }
-}
-
-
-
-
+package org.apache.commons.graph.algorithm.spanning;
+
+import org.apache.commons.graph.*;
+import org.apache.commons.graph.exception.*;
+import org.apache.commons.graph.decorator.*;
+import org.apache.commons.graph.domain.basic.*;
+import org.apache.commons.graph.algorithm.util.*;
+
+import org.apache.commons.collections.PriorityQueue;
+import org.apache.commons.collections.BinaryHeap;
+
+import java.util.Map;
+import java.util.Set;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Comparator;
+
+public class MinimumSpanningForest
+ extends UndirectedGraphImpl
+ implements UndirectedGraph,
+ WeightedGraph
+{
+ private PriorityQueue queue = null;
+ private Map labels = new HashMap(); // VERTEX X LABEL
+ private Set chords = new HashSet(); // Edges not in MSF.
+
+ private DDirectedGraph ddg = null;
+
+ public class WeightedEdgeComparator
+ implements Comparator
+ {
+ private WeightedGraph graph = null;
+ public WeightedEdgeComparator( WeightedGraph graph ) {
+ this.graph = graph;
+ }
+
+ public int compare( Object o1, Object o2 ) {
+ if ((o1 instanceof Edge) &&
+ (o2 instanceof Edge)) {
+ double val = ( graph.getWeight( (Edge) o1 ) -
+ graph.getWeight( (Edge) o2 ));
+ if (val > 0) return 1;
+ if (val == 0) return 0;
+ if (val < 0) return -1;
+ }
+
+ return -1;
+ }
+ }
+
+ public MinimumSpanningForest( WeightedGraph graph ) {
+ calculateMSF( true, graph );
+ }
+
+ public MinimumSpanningForest( boolean isMin, WeightedGraph graph ) {
+ calculateMSF( isMin, graph );
+ }
+
+ protected Label findLabel( Vertex v ) {
+ return (Label) labels.get( v );
+ }
+
+ protected boolean connectsLabels( Graph graph,
+ Edge e )
+ {
+ Label first = null;
+ Label second = null;
+
+ Iterator vertices = graph.getVertices( e ).iterator();
+ if (vertices.hasNext()) {
+ first = findLabel( (Vertex) vertices.next() );
+ } else { return false; }
+
+ if (vertices.hasNext()) {
+ second = findLabel( (Vertex) vertices.next() );
+ } else { return false; }
+
+ if (vertices.hasNext()) {
+ throw new HyperGraphException("Unable to compute MSF on Hypergraph.");
+ }
+
+ return !first.getRoot().equals( second.getRoot() );
+ }
+
+ protected void addEdge( WeightedGraph graph,
+ Edge edge ) {
+ addEdge( edge );
+ chords.remove( edge );
+ Iterator vertices = graph.getVertices( edge ).iterator();
+ Label prime = null;
+
+ if (vertices.hasNext()) {
+ Vertex p = (Vertex) vertices.next();
+ prime = findLabel( p );
+
+ connect( edge, p );
+ }
+
+ while (vertices.hasNext()) {
+ Vertex v = (Vertex) vertices.next();
+
+ Label l = findLabel( v );
+ l.setRoot( prime );
+
+ connect( edge, v );
+ }
+
+ setWeight( edge, graph.getWeight( edge ));
+ }
+
+ protected void calculateMSF( boolean isMin,
+ WeightedGraph graph ) {
+
+ PriorityQueue queue =
+ new BinaryHeap( isMin, new WeightedEdgeComparator( graph ));
+
+ chords = new HashSet( graph.getEdges() );
+
+ // Fill the Queue with all the edges.
+ Iterator edges = graph.getEdges().iterator();
+ while (edges.hasNext()) {
+ queue.insert( edges.next() );
+ }
+
+ // Fill the graph we have with all the Vertexes.
+ Iterator vertices = graph.getVertices().iterator();
+ while (vertices.hasNext()) {
+ Vertex v = (Vertex) vertices.next();
+ labels.put( v, new Label() );
+ addVertex( v );
+ }
+
+ // Bring the edges out in the right order.
+ while (!queue.isEmpty()) {
+ Edge e = (Edge) queue.pop();
+
+ if ( connectsLabels( graph, e )) {
+ addEdge( graph, e );
+ }
+ }
+ }
+
+ public Set getChords() {
+ return chords;
+ }
+}
+
+
+
+
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/Label.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/Label.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/Label.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/Label.java Sat Feb 26 05:21:52 2005
@@ -1,39 +1,39 @@
-package org.apache.commons.graph.algorithm.util;
-
-public class Label
-{
- private Label root = null;
-
- public Label() {
- }
-
- public Label( Label root ) {
- this.root = root.getRoot();
- }
-
- public void setRoot( Label root ) {
- if (this.root == null ) {
- this.root = root.getRoot();
- } else {
- if (root != this.root) {
- this.root.setRoot( root.getRoot() );
- this.root = root.getRoot();
- }
- }
- }
-
- public Label getRoot() {
- if ((root == null) ||
- (root == this)) {
- return this;
- } else {
- root = root.getRoot();
- return root;
- }
- }
-}
-
-
-
-
-
+package org.apache.commons.graph.algorithm.util;
+
+public class Label
+{
+ private Label root = null;
+
+ public Label() {
+ }
+
+ public Label( Label root ) {
+ this.root = root.getRoot();
+ }
+
+ public void setRoot( Label root ) {
+ if (this.root == null ) {
+ this.root = root.getRoot();
+ } else {
+ if (root != this.root) {
+ this.root.setRoot( root.getRoot() );
+ this.root = root.getRoot();
+ }
+ }
+ }
+
+ public Label getRoot() {
+ if ((root == null) ||
+ (root == this)) {
+ return this;
+ } else {
+ root = root.getRoot();
+ return root;
+ }
+ }
+}
+
+
+
+
+
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/Label.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java Sat Feb 26 05:21:52 2005
@@ -1,81 +1,81 @@
-package org.apache.commons.graph.algorithm.util;
-
-import java.util.List;
-import java.util.ArrayList;
-
-import org.apache.commons.graph.*;
-
-public class PathImpl
- implements Path
-{
- protected List vertexList = new ArrayList();
- protected List edgeList = new ArrayList();
-
- public PathImpl( List vertexList,
- List edgeList ) {
- this.vertexList = vertexList;
- this.edgeList = edgeList;
- }
-
- public PathImpl( Vertex start ) {
- this.vertexList.add( start );
- }
-
- public PathImpl( Vertex start,
- Vertex end,
- Edge edge ) {
- vertexList = new ArrayList();
- vertexList.add( start );
- vertexList.add( end );
-
- edgeList = new ArrayList();
- edgeList.add( edge );
- }
-
- public PathImpl append( PathImpl impl ) {
- List newVertices = new ArrayList( vertexList );
- newVertices.remove( newVertices.size() - 1 ); // Last should be duplicated
- newVertices.addAll( impl.getVertices() );
-
- List newEdges = new ArrayList( edgeList );
- newEdges.addAll( impl.getEdges() );
-
- return new PathImpl( newVertices, newEdges );
- }
-
- public PathImpl append( Vertex v, Edge e ) {
- List newVertices = new ArrayList( vertexList );
- newVertices.add( v );
-
- List newEdges = new ArrayList( edgeList );
- newEdges.add( e );
-
- return new PathImpl( newVertices, newEdges );
- }
-
- public Vertex getStart() {
- return (Vertex) vertexList.get( 0 );
- }
-
- public Vertex getEnd() {
- return (Vertex) vertexList.get( vertexList.size() - 1 );
- }
-
- public List getVertices() {
- return vertexList;
- }
-
- public List getEdges() {
- return edgeList;
- }
-
- public int size() {
- return vertexList.size();
- }
-
- public String toString() {
- return vertexList.toString();
- }
-}
-
-
+package org.apache.commons.graph.algorithm.util;
+
+import java.util.List;
+import java.util.ArrayList;
+
+import org.apache.commons.graph.*;
+
+public class PathImpl
+ implements Path
+{
+ protected List vertexList = new ArrayList();
+ protected List edgeList = new ArrayList();
+
+ public PathImpl( List vertexList,
+ List edgeList ) {
+ this.vertexList = vertexList;
+ this.edgeList = edgeList;
+ }
+
+ public PathImpl( Vertex start ) {
+ this.vertexList.add( start );
+ }
+
+ public PathImpl( Vertex start,
+ Vertex end,
+ Edge edge ) {
+ vertexList = new ArrayList();
+ vertexList.add( start );
+ vertexList.add( end );
+
+ edgeList = new ArrayList();
+ edgeList.add( edge );
+ }
+
+ public PathImpl append( PathImpl impl ) {
+ List newVertices = new ArrayList( vertexList );
+ newVertices.remove( newVertices.size() - 1 ); // Last should be duplicated
+ newVertices.addAll( impl.getVertices() );
+
+ List newEdges = new ArrayList( edgeList );
+ newEdges.addAll( impl.getEdges() );
+
+ return new PathImpl( newVertices, newEdges );
+ }
+
+ public PathImpl append( Vertex v, Edge e ) {
+ List newVertices = new ArrayList( vertexList );
+ newVertices.add( v );
+
+ List newEdges = new ArrayList( edgeList );
+ newEdges.add( e );
+
+ return new PathImpl( newVertices, newEdges );
+ }
+
+ public Vertex getStart() {
+ return (Vertex) vertexList.get( 0 );
+ }
+
+ public Vertex getEnd() {
+ return (Vertex) vertexList.get( vertexList.size() - 1 );
+ }
+
+ public List getVertices() {
+ return vertexList;
+ }
+
+ public List getEdges() {
+ return edgeList;
+ }
+
+ public int size() {
+ return vertexList.size();
+ }
+
+ public String toString() {
+ return vertexList.toString();
+ }
+}
+
+
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java Sat Feb 26 05:21:52 2005
@@ -1,5 +1,5 @@
-package org.apache.commons.graph.algorithm.util;
-
+package org.apache.commons.graph.algorithm.util;
+
/*
* Copyright 2001,2004 The Apache Software Foundation.
*
@@ -14,37 +14,37 @@
* 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.
- */
-
-
-/**
- * VertexPair
- *
- * This is a tuple of two vertices which is capable
- * of storing things in a Hashtable.
- */
-
-import org.apache.commons.graph.*;
-
-public class VertexPair {
- public Vertex i = null;
- public Vertex j = null;
-
- public VertexPair( Vertex i, Vertex j ) {
- this.i = i;
- this.j = j;
- }
-
- public boolean equals( Object o ) {
- VertexPair vp = (VertexPair) o;
- return ( this.i == vp.i &&
- this.j == vp.j );
- }
-
- public int hashCode() {
- return (17 * i.hashCode()) + j.hashCode();
- }
-}
-
-
-
+ */
+
+
+/**
+ * VertexPair
+ *
+ * This is a tuple of two vertices which is capable
+ * of storing things in a Hashtable.
+ */
+
+import org.apache.commons.graph.*;
+
+public class VertexPair {
+ public Vertex i = null;
+ public Vertex j = null;
+
+ public VertexPair( Vertex i, Vertex j ) {
+ this.i = i;
+ this.j = j;
+ }
+
+ public boolean equals( Object o ) {
+ VertexPair vp = (VertexPair) o;
+ return ( this.i == vp.i &&
+ this.j == vp.j );
+ }
+
+ public int hashCode() {
+ return (17 * i.hashCode()) + j.hashCode();
+ }
+}
+
+
+
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
Modified: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Acyclic.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Acyclic.java?view=diff&r1=155446&r2=155447
==============================================================================
--- jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Acyclic.java (original)
+++ jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Acyclic.java Sat Feb 26 05:21:52 2005
@@ -1,8 +1,8 @@
-package org.apache.commons.graph.contract;
-
-/**
- * Description of the Interface
- */
-public interface Acyclic
-{
-}
+package org.apache.commons.graph.contract;
+
+/**
+ * Description of the Interface
+ */
+public interface Acyclic
+{
+}
Propchange: jakarta/commons/sandbox/graph2/trunk/src/java/org/apache/commons/graph/contract/Acyclic.java
------------------------------------------------------------------------------
--- svn:keywords (original)
+++ svn:keywords Sat Feb 26 05:21:52 2005
@@ -1 +1 @@
-author date id revision
+Date Author Id Revision HeadURL
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org