initial attempt of Commons-Graph modularization
diff --git a/api/pom.xml b/api/pom.xml new file mode 100644 index 0000000..c21cf89 --- /dev/null +++ b/api/pom.xml
@@ -0,0 +1,45 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-api</artifactId> + + <name>Apache Commons Graph - APIs</name> + <description>The Apache Commons Graph base APIs.</description> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/DirectedGraph.java b/api/src/main/java/org/apache/commons/graph/DirectedGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/DirectedGraph.java rename to api/src/main/java/org/apache/commons/graph/DirectedGraph.java
diff --git a/src/main/java/org/apache/commons/graph/Graph.java b/api/src/main/java/org/apache/commons/graph/Graph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/Graph.java rename to api/src/main/java/org/apache/commons/graph/Graph.java
diff --git a/src/main/java/org/apache/commons/graph/GraphException.java b/api/src/main/java/org/apache/commons/graph/GraphException.java similarity index 100% rename from src/main/java/org/apache/commons/graph/GraphException.java rename to api/src/main/java/org/apache/commons/graph/GraphException.java
diff --git a/api/src/main/java/org/apache/commons/graph/Graphs.java b/api/src/main/java/org/apache/commons/graph/Graphs.java new file mode 100644 index 0000000..a5baf37 --- /dev/null +++ b/api/src/main/java/org/apache/commons/graph/Graphs.java
@@ -0,0 +1,175 @@ +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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.builder.DefaultLinkedConnectionBuilder; +import org.apache.commons.graph.builder.LinkedConnectionBuilder; + +/** + * The Apache Commons Graph package is a toolkit for managing graphs and graph based data structures. + */ +public final class Graphs +{ + + /** + * Allows populate the given {@link MutableGraph}. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param <G> the Graph type + * @param graph the graph has to be populated + * @return the builder to configure vertices connection + */ + public static <V, E, G extends MutableGraph<V, E>> LinkedConnectionBuilder<V, E, G> populate( final G graph ) + { + G checkedGraph = checkNotNull( graph, "Impossible to configure null Graph." ); + return new DefaultLinkedConnectionBuilder<V, E, G>( checkedGraph ); + } + + /** + * Returns a synchronized (thread-safe) {@link Graph} backed by the specified Graph. + * + * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: + * <pre> + * Graph syncGraph = synchronize( graph ); + * ... + * synchronized(syncGraph) { + * for ( Vertex v : g.getVertices() ) // Must be in synchronized block + * { + * foo( v ) + * } + * } + * </pre> + * + * Failure to follow this advice may result in non-deterministic behavior. + * + * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param graph the input {@link Graph} + * @return the syncronyzed graph + */ + public static <V, E> Graph<V, E> synchronize( final Graph<V, E> graph ) + { + Graph<V, E> checkedGraph = checkNotNull( graph, "Impossible to synchronize null Graph." ); + return new SynchronizedGraph<V, E>( checkedGraph ); + } + + /** + * Returns a synchronized (thread-safe) {@link DirectedGraph} backed by the specified Graph. + * + * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: + * <pre> + * Graph syncGraph = synchronize( graph ); + * ... + * synchronized(syncGraph) { + * for ( Vertex v : g.getVertices() ) // Must be in synchronized block + * { + * foo( v ) + * } + * } + * </pre> + * + * Failure to follow this advice may result in non-deterministic behavior. + * + * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param graph the input {@link Graph} + * @return the syncronyzed graph + */ + public static <V, E> DirectedGraph<V, E> synchronize( final DirectedGraph<V, E> graph ) + { + return new SynchronizedDirectedGraph<V, E>( graph ); + } + + /** + * Returns a synchronized (thread-safe) {@link UndirectedGraph} backed by the specified Graph. + * + * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: + * <pre> + * Graph syncGraph = synchronize( graph ); + * ... + * synchronized(syncGraph) { + * for ( Vertex v : g.getVertices() ) // Must be in synchronized block + * { + * foo( v ) + * } + * } + * </pre> + * + * Failure to follow this advice may result in non-deterministic behavior. + * + * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param graph the input {@link Graph} + * @return the syncronyzed graph + */ + public static <V, E> Graph<V, E> synchronize( final UndirectedGraph<V, E> graph ) + { + UndirectedGraph<V, E> checkedGraph = checkNotNull( graph, "Impossible to synchronize null Graph." ); + return new SynchronizedUndirectedGraph<V, E>( checkedGraph ); + } + + /** + * Returns a synchronized (thread-safe) {@link MutableGraph} backed by the specified Graph. + * + * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: + * <pre> + * Graph syncGraph = synchronize( graph ); + * ... + * synchronized(syncGraph) { + * for ( Vertex v : g.getVertices() ) // Must be in synchronized block + * { + * foo( v ) + * } + * } + * </pre> + * + * Failure to follow this advice may result in non-deterministic behavior. + * + * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param graph the input {@link Graph} + * @return the synchronized graph + */ + public static <V, E> Graph<V, E> synchronize( final MutableGraph<V, E> graph ) + { + MutableGraph<V, E> checkedGraph = checkNotNull( graph, "Impossible to synchronize null Graph." ); + return new SynchronizedMutableGraph<V, E>( checkedGraph ); + } + + /** + * Hidden constructor, this class cannot be instantiated. + */ + private Graphs() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/Mapper.java b/api/src/main/java/org/apache/commons/graph/Mapper.java similarity index 100% rename from src/main/java/org/apache/commons/graph/Mapper.java rename to api/src/main/java/org/apache/commons/graph/Mapper.java
diff --git a/src/main/java/org/apache/commons/graph/MutableGraph.java b/api/src/main/java/org/apache/commons/graph/MutableGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/MutableGraph.java rename to api/src/main/java/org/apache/commons/graph/MutableGraph.java
diff --git a/src/main/java/org/apache/commons/graph/Path.java b/api/src/main/java/org/apache/commons/graph/Path.java similarity index 100% rename from src/main/java/org/apache/commons/graph/Path.java rename to api/src/main/java/org/apache/commons/graph/Path.java
diff --git a/src/main/java/org/apache/commons/graph/model/RevertedGraph.java b/api/src/main/java/org/apache/commons/graph/RevertedGraph.java similarity index 96% rename from src/main/java/org/apache/commons/graph/model/RevertedGraph.java rename to api/src/main/java/org/apache/commons/graph/RevertedGraph.java index 112d27f..e038470 100644 --- a/src/main/java/org/apache/commons/graph/model/RevertedGraph.java +++ b/api/src/main/java/org/apache/commons/graph/RevertedGraph.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.model; +package org.apache.commons.graph; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -21,8 +21,6 @@ import static org.apache.commons.graph.utils.Assertions.checkNotNull; -import org.apache.commons.graph.DirectedGraph; -import org.apache.commons.graph.VertexPair; /** * An adapted class that mirrors {@link DirectedGraph} instances,
diff --git a/src/main/java/org/apache/commons/graph/SpanningTree.java b/api/src/main/java/org/apache/commons/graph/SpanningTree.java similarity index 100% rename from src/main/java/org/apache/commons/graph/SpanningTree.java rename to api/src/main/java/org/apache/commons/graph/SpanningTree.java
diff --git a/src/main/java/org/apache/commons/graph/SynchronizedDirectedGraph.java b/api/src/main/java/org/apache/commons/graph/SynchronizedDirectedGraph.java similarity index 99% rename from src/main/java/org/apache/commons/graph/SynchronizedDirectedGraph.java rename to api/src/main/java/org/apache/commons/graph/SynchronizedDirectedGraph.java index 89c776a..f8ee5f0 100644 --- a/src/main/java/org/apache/commons/graph/SynchronizedDirectedGraph.java +++ b/api/src/main/java/org/apache/commons/graph/SynchronizedDirectedGraph.java
@@ -19,6 +19,7 @@ * under the License. */ + /** * A synchronized (thread-safe) {@link Graph} backed by the specified Graph. */
diff --git a/src/main/java/org/apache/commons/graph/SynchronizedGraph.java b/api/src/main/java/org/apache/commons/graph/SynchronizedGraph.java similarity index 99% rename from src/main/java/org/apache/commons/graph/SynchronizedGraph.java rename to api/src/main/java/org/apache/commons/graph/SynchronizedGraph.java index 8811060..ccfb983 100644 --- a/src/main/java/org/apache/commons/graph/SynchronizedGraph.java +++ b/api/src/main/java/org/apache/commons/graph/SynchronizedGraph.java
@@ -21,6 +21,7 @@ import static org.apache.commons.graph.utils.Objects.eq; + /** * A synchronized (thread-safe) {@link Graph} backed by the specified Graph. */
diff --git a/src/main/java/org/apache/commons/graph/SynchronizedMutableGraph.java b/api/src/main/java/org/apache/commons/graph/SynchronizedMutableGraph.java similarity index 99% rename from src/main/java/org/apache/commons/graph/SynchronizedMutableGraph.java rename to api/src/main/java/org/apache/commons/graph/SynchronizedMutableGraph.java index cb2a369..2e19d6e 100644 --- a/src/main/java/org/apache/commons/graph/SynchronizedMutableGraph.java +++ b/api/src/main/java/org/apache/commons/graph/SynchronizedMutableGraph.java
@@ -19,6 +19,7 @@ * under the License. */ + /** * A synchronized (thread-safe) {@link Graph} backed by the specified Graph. */
diff --git a/src/main/java/org/apache/commons/graph/SynchronizedUndirectedGraph.java b/api/src/main/java/org/apache/commons/graph/SynchronizedUndirectedGraph.java similarity index 99% rename from src/main/java/org/apache/commons/graph/SynchronizedUndirectedGraph.java rename to api/src/main/java/org/apache/commons/graph/SynchronizedUndirectedGraph.java index 2e8c3fd..9c6ee25 100644 --- a/src/main/java/org/apache/commons/graph/SynchronizedUndirectedGraph.java +++ b/api/src/main/java/org/apache/commons/graph/SynchronizedUndirectedGraph.java
@@ -19,6 +19,7 @@ * under the License. */ + /** * A synchronized (thread-safe) {@link Graph} backed by the specified Graph. */
diff --git a/src/main/java/org/apache/commons/graph/UndirectedGraph.java b/api/src/main/java/org/apache/commons/graph/UndirectedGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/UndirectedGraph.java rename to api/src/main/java/org/apache/commons/graph/UndirectedGraph.java
diff --git a/src/main/java/org/apache/commons/graph/VertexPair.java b/api/src/main/java/org/apache/commons/graph/VertexPair.java similarity index 100% rename from src/main/java/org/apache/commons/graph/VertexPair.java rename to api/src/main/java/org/apache/commons/graph/VertexPair.java
diff --git a/src/main/java/org/apache/commons/graph/Weighted.java b/api/src/main/java/org/apache/commons/graph/Weighted.java similarity index 100% rename from src/main/java/org/apache/commons/graph/Weighted.java rename to api/src/main/java/org/apache/commons/graph/Weighted.java
diff --git a/src/main/java/org/apache/commons/graph/WeightedPath.java b/api/src/main/java/org/apache/commons/graph/WeightedPath.java similarity index 100% rename from src/main/java/org/apache/commons/graph/WeightedPath.java rename to api/src/main/java/org/apache/commons/graph/WeightedPath.java
diff --git a/src/main/java/org/apache/commons/graph/builder/AbstractGraphConnection.java b/api/src/main/java/org/apache/commons/graph/builder/AbstractGraphConnection.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/AbstractGraphConnection.java rename to api/src/main/java/org/apache/commons/graph/builder/AbstractGraphConnection.java
diff --git a/src/main/java/org/apache/commons/graph/builder/DefaultGrapher.java b/api/src/main/java/org/apache/commons/graph/builder/DefaultGrapher.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/DefaultGrapher.java rename to api/src/main/java/org/apache/commons/graph/builder/DefaultGrapher.java
diff --git a/src/main/java/org/apache/commons/graph/builder/DefaultHeadVertexConnector.java b/api/src/main/java/org/apache/commons/graph/builder/DefaultHeadVertexConnector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/DefaultHeadVertexConnector.java rename to api/src/main/java/org/apache/commons/graph/builder/DefaultHeadVertexConnector.java
diff --git a/src/main/java/org/apache/commons/graph/builder/DefaultLinkedConnectionBuilder.java b/api/src/main/java/org/apache/commons/graph/builder/DefaultLinkedConnectionBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/DefaultLinkedConnectionBuilder.java rename to api/src/main/java/org/apache/commons/graph/builder/DefaultLinkedConnectionBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/builder/DefaultTailVertexConnector.java b/api/src/main/java/org/apache/commons/graph/builder/DefaultTailVertexConnector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/DefaultTailVertexConnector.java rename to api/src/main/java/org/apache/commons/graph/builder/DefaultTailVertexConnector.java
diff --git a/src/main/java/org/apache/commons/graph/builder/GraphConnection.java b/api/src/main/java/org/apache/commons/graph/builder/GraphConnection.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/GraphConnection.java rename to api/src/main/java/org/apache/commons/graph/builder/GraphConnection.java
diff --git a/src/main/java/org/apache/commons/graph/builder/GraphConnector.java b/api/src/main/java/org/apache/commons/graph/builder/GraphConnector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/GraphConnector.java rename to api/src/main/java/org/apache/commons/graph/builder/GraphConnector.java
diff --git a/src/main/java/org/apache/commons/graph/builder/HeadVertexConnector.java b/api/src/main/java/org/apache/commons/graph/builder/HeadVertexConnector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/HeadVertexConnector.java rename to api/src/main/java/org/apache/commons/graph/builder/HeadVertexConnector.java
diff --git a/src/main/java/org/apache/commons/graph/builder/LinkedConnectionBuilder.java b/api/src/main/java/org/apache/commons/graph/builder/LinkedConnectionBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/LinkedConnectionBuilder.java rename to api/src/main/java/org/apache/commons/graph/builder/LinkedConnectionBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/builder/TailVertexConnector.java b/api/src/main/java/org/apache/commons/graph/builder/TailVertexConnector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/TailVertexConnector.java rename to api/src/main/java/org/apache/commons/graph/builder/TailVertexConnector.java
diff --git a/src/main/java/org/apache/commons/graph/builder/package-info.java b/api/src/main/java/org/apache/commons/graph/builder/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/builder/package-info.java rename to api/src/main/java/org/apache/commons/graph/builder/package-info.java
diff --git a/src/main/java/org/apache/commons/graph/weight/Monoid.java b/api/src/main/java/org/apache/commons/graph/math/monoid/Monoid.java similarity index 96% rename from src/main/java/org/apache/commons/graph/weight/Monoid.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/Monoid.java index 4f99408..c01d797 100644 --- a/src/main/java/org/apache/commons/graph/weight/Monoid.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/Monoid.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight; +package org.apache.commons.graph.math.monoid; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java b/api/src/main/java/org/apache/commons/graph/math/monoid/OrderedMonoid.java similarity index 95% rename from src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/OrderedMonoid.java index fc251e4..c0ed041 100644 --- a/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/OrderedMonoid.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight; +package org.apache.commons.graph.math.monoid; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/main/java/org/apache/commons/graph/weight/package-info.java b/api/src/main/java/org/apache/commons/graph/math/monoid/package-info.java similarity index 94% rename from src/main/java/org/apache/commons/graph/weight/package-info.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/package-info.java index 88e74af..e9a8a0a 100644 --- a/src/main/java/org/apache/commons/graph/weight/package-info.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/package-info.java
@@ -1,7 +1,7 @@ /** * Interfaces that define properties and operations on weights. */ -package org.apache.commons.graph.weight; +package org.apache.commons.graph.math.monoid; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/BigDecimalWeightBaseOperations.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/BigDecimalWeightBaseOperations.java index c3ac94d..fd0d40d 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/BigDecimalWeightBaseOperations.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -23,7 +23,7 @@ import java.math.BigDecimal; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * The class {@link BigDecimalWeightBaseOperations} provides operations and properties
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/BigIntegerWeightBaseOperations.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/BigIntegerWeightBaseOperations.java index 2dc9128..5f070c6 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/BigIntegerWeightBaseOperations.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -23,7 +23,7 @@ import java.math.BigInteger; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * The class {@link BigIntegerWeightBaseOperations} provides operations and properties
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/DoubleWeightBaseOperations.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/DoubleWeightBaseOperations.java index 26c2744..cd68125 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/DoubleWeightBaseOperations.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * The class {@link DoubleWeightBaseOperations} provides operations and properties
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/FloatWeightBaseOperations.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/FloatWeightBaseOperations.java index 3418fde..dd1507a 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/FloatWeightBaseOperations.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * The class {@link FloatWeightBaseOperations} provides operations and properties
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/IntegerWeightBaseOperations.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/IntegerWeightBaseOperations.java index b0406e8..a09c5f2 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/IntegerWeightBaseOperations.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * The class {@link IntegerWeightBaseOperations} provides operations and properties
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/LongWeightBaseOperations.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/LongWeightBaseOperations.java index d730575..1f3df4e 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/LongWeightBaseOperations.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * The class {@link LongWeightBaseOperations} provides operations and properties
diff --git a/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/package-info.java similarity index 93% rename from src/main/java/org/apache/commons/graph/weight/primitive/package-info.java rename to api/src/main/java/org/apache/commons/graph/math/monoid/primitive/package-info.java index 9a70282..a32933c 100644 --- a/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java +++ b/api/src/main/java/org/apache/commons/graph/math/monoid/primitive/package-info.java
@@ -1,7 +1,7 @@ /** * Implementations of base operations on primitive types of weights. */ -package org.apache.commons.graph.weight.primitive; +package org.apache.commons.graph.math.monoid.primitive; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/main/java/org/apache/commons/graph/package-info.java b/api/src/main/java/org/apache/commons/graph/package-info.java similarity index 89% rename from src/main/java/org/apache/commons/graph/package-info.java rename to api/src/main/java/org/apache/commons/graph/package-info.java index 280a069..6aa2a36 100644 --- a/src/main/java/org/apache/commons/graph/package-info.java +++ b/api/src/main/java/org/apache/commons/graph/package-info.java
@@ -1,5 +1,5 @@ /** - * The Apache Commons Graph package is a toolkit for managing graphs and graph based data structures. + * Apache Commons Graph APIs. */ package org.apache.commons.graph;
diff --git a/src/main/java/org/apache/commons/graph/utils/Assertions.java b/api/src/main/java/org/apache/commons/graph/utils/Assertions.java similarity index 100% rename from src/main/java/org/apache/commons/graph/utils/Assertions.java rename to api/src/main/java/org/apache/commons/graph/utils/Assertions.java
diff --git a/src/main/java/org/apache/commons/graph/utils/Objects.java b/api/src/main/java/org/apache/commons/graph/utils/Objects.java similarity index 100% rename from src/main/java/org/apache/commons/graph/utils/Objects.java rename to api/src/main/java/org/apache/commons/graph/utils/Objects.java
diff --git a/src/main/java/org/apache/commons/graph/utils/package-info.java b/api/src/main/java/org/apache/commons/graph/utils/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/utils/package-info.java rename to api/src/main/java/org/apache/commons/graph/utils/package-info.java
diff --git a/base/src/main/java/org/apache/commons/graph/algorithm/dataflow/DataFlowEquations.java b/base/src/main/java/org/apache/commons/graph/algorithm/dataflow/DataFlowEquations.java deleted file mode 100644 index b26dc80..0000000 --- a/base/src/main/java/org/apache/commons/graph/algorithm/dataflow/DataFlowEquations.java +++ /dev/null
@@ -1,36 +0,0 @@ -package org.apache.commons.graph.algorithm.dataflow; - -/* - * 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 java.util.BitSet; - -import org.apache.commons.graph.*; - -public interface DataFlowEquations { - /** - * This method shows when a definition is defined. - */ - public BitSet generates( Vertex vertex ); - - /** - * This method shows when a definition is killed (or overwritten.) - */ - public BitSet kills( Vertex vertex ); -}
diff --git a/base/src/main/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java b/base/src/main/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java deleted file mode 100644 index cc744aa..0000000 --- a/base/src/main/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java +++ /dev/null
@@ -1,94 +0,0 @@ -package org.apache.commons.graph.algorithm.dataflow; - -/* - * 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 java.util.Map; -import java.util.BitSet; -import java.util.HashMap; -import java.util.Iterator; - -import org.apache.commons.graph.*; - -public class DataFlowSolutions -{ - private Map inValues = new HashMap(); // VERTEX X BITSET - private Map outValues = new HashMap(); - - public DataFlowSolutions( DirectedGraph graph, - DataFlowEquations eq ) { - calculateDataFlow( graph, eq ); - } - - private void calculateDataFlow( DirectedGraph graph, - DataFlowEquations eq ) { - Iterator vertices = graph.getVertices().iterator(); - while (vertices.hasNext()) { - Vertex v = (Vertex) vertices.next(); - inValues.put( v, new BitSet() ); // Initialize everything to - outValues.put( v, new BitSet() ); // empty - } - - boolean isOK = true; - while (isOK) { - vertices = graph.getVertices().iterator(); - isOK = false; - while (vertices.hasNext()) { - Vertex v = (Vertex) vertices.next(); - - BitSet out = new BitSet(); - out.or( (BitSet) inValues.get( v )); - out.or( eq.generates( v )); - out.andNot( eq.kills( v )); - - /* - System.err.println("Old Out: " + v + ":" + outValues.get( v )); - System.err.println("New Out: " + v + ":" + out); - */ - if (!out.equals( outValues.get( v ))) { - isOK = true; - outValues.put( v, out ); - - Iterator outbound = graph.getOutbound( v ).iterator(); - while (outbound.hasNext()) { - Vertex target = - graph.getTarget( (Edge) outbound.next() ); - - BitSet in = (BitSet) inValues.get( target ); - in.or( out ); - inValues.put( target, in ); - /* - System.err.println("Old In: " + target + ":" + - inValues.get( target )); - System.err.println("New In: " + target + ":" + in ); - */ - } - } - } - } - } - - public BitSet reaches( Vertex vertex ) { - return (BitSet) inValues.get( vertex ); - } - - public BitSet leaves( Vertex vertex ) { - return (BitSet) outValues.get( vertex ); - } -}
diff --git a/base/src/main/java/org/apache/commons/graph/contract/Acyclic.java b/base/src/main/java/org/apache/commons/graph/contract/Acyclic.java deleted file mode 100644 index bef017c..0000000 --- a/base/src/main/java/org/apache/commons/graph/contract/Acyclic.java +++ /dev/null
@@ -1,27 +0,0 @@ -package org.apache.commons.graph.contract; - -/* - * 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. - */ - -/** - * Description of the Interface - */ -public interface Acyclic -{ -}
diff --git a/base/src/main/java/org/apache/commons/graph/contract/AcyclicContract.java b/base/src/main/java/org/apache/commons/graph/contract/AcyclicContract.java deleted file mode 100644 index e47d3d4..0000000 --- a/base/src/main/java/org/apache/commons/graph/contract/AcyclicContract.java +++ /dev/null
@@ -1,171 +0,0 @@ -package org.apache.commons.graph.contract; - -/* - * 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 java.util.Iterator; - -import org.apache.commons.graph.*; -import org.apache.commons.graph.algorithm.search.*; -import org.apache.commons.graph.exception.*; -import org.apache.commons.graph.decorator.*; - -/** - * Description of the Class - */ -public class AcyclicContract<V extends Vertex, E extends Edge> - implements Contract<V, E> -{ - private DecoratedDirectedGraph graph = null; - - /** - * Description of the Class - */ - public class CycleDetector - implements Visitor - { - private DFS dfs = null; - private boolean isCyclic = false; - private DirectedGraph<V, E> graph = null; - - /** - * Constructor for the CycleDetector object - * - * @param graph - */ - public CycleDetector(DirectedGraph<V, E> graph) - { - this.dfs = new DFS(); - this.graph = graph; - Iterator<V> verts = graph.getVertices().iterator(); - - if (verts.hasNext()) - { - dfs.visit(graph, verts.next(), this); - } - } - - /** - * Description of the Method - */ - public void discoverGraph(Graph graph) { } - - /** - * Description of the Method - */ - public void discoverVertex(Vertex v) { } - - /** - * Description of the Method - */ - public void discoverEdge(Edge e) - { - if (dfs.getColor(graph.getTarget(e)) == DFS.GRAY) - { - this.isCyclic = true; - } - } - - /** - * Description of the Method - */ - public void finishEdge(Edge e) { } - - /** - * Description of the Method - */ - public void finishVertex(Vertex v) { } - - /** - * Description of the Method - */ - public void finishGraph(Graph graph) { } - - /** - * Description of the Method - */ - public boolean hasCycle() - { - return isCyclic; - } - } - - /** - * Constructor for the AcyclicContract object - */ - public AcyclicContract() { } - - /** - * Sets the impl attribute of the AcyclicContract object - */ - public void setImpl(DirectedGraph<V, E> graph) - { - this.graph = DecoratedDirectedGraph.decorateGraph(graph); - } - - /** - * Gets the interface attribute of the AcyclicContract object - */ - public Class<?> getInterface() - { - return org.apache.commons.graph.contract.Acyclic.class; - } - - /** - * Description of the Method - */ - public void verify() - throws CycleException - { - CycleDetector cd = new CycleDetector(graph); - if (cd.hasCycle()) - { - throw new CycleException("Cycle detected in Graph."); - } - } - - /** - * Adds a feature to the Vertex attribute of the AcyclicContract object - */ - public void addVertex(Vertex v) { } - - /** - * Adds a feature to the Edge attribute of the AcyclicContract object - */ - public void addEdge(Edge e, - Vertex start, - Vertex end) - throws GraphException - { - if (graph.hasConnection(end, start)) - { - throw new CycleException("Introducing edge will cause a Cycle."); - } - } - - /** - * Description of the Method - */ - public void removeVertex(Vertex v) { } - - /** - * Description of the Method - */ - public void removeEdge(Edge e) { } -}
diff --git a/base/src/main/java/org/apache/commons/graph/contract/Contract.java b/base/src/main/java/org/apache/commons/graph/contract/Contract.java deleted file mode 100644 index d4ca3e5..0000000 --- a/base/src/main/java/org/apache/commons/graph/contract/Contract.java +++ /dev/null
@@ -1,80 +0,0 @@ -package org.apache.commons.graph.contract; - -/* - * 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 org.apache.commons.graph.DirectedGraph; -import org.apache.commons.graph.Edge; -import org.apache.commons.graph.GraphException; -import org.apache.commons.graph.Vertex; - -/** - * Description of the Interface - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - */ -public interface Contract<V extends Vertex, E extends Edge> -{ - - /** - * The impl that gets passed in is read-only. This is the representation of - * the graph you should work off of. If an edge or vertex addition is - * illegal to the contract, raise a GraphException with and explanation. - */ - void setImpl( DirectedGraph<V, E> impl ); - - /** - * getInterface This returns the marker interface which is associated with - * the Contract. For instance, AcyclicContract will return AcyclicGraph - * here. - */ - Class getInterface(); - - /** - * verify - This verifies that the graph it is working on complies. - */ - void verify() - throws GraphException; - - /** - * Adds a feature to the Edge attribute of the Contract object - */ - void addEdge( Edge e, Vertex start, Vertex end ) - throws GraphException; - - /** - * Adds a feature to the Vertex attribute of the Contract object - */ - void addVertex( Vertex v ) - throws GraphException; - - /** - * Description of the Method - */ - void removeEdge( Edge e ) - throws GraphException; - - /** - * Description of the Method - */ - void removeVertex( Vertex v ) - throws GraphException; - -}
diff --git a/base/src/test/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutionsTest.java b/base/src/test/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutionsTest.java deleted file mode 100644 index 6483079..0000000 --- a/base/src/test/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutionsTest.java +++ /dev/null
@@ -1,307 +0,0 @@ -package org.apache.commons.graph.algorithm.dataflow; - -/* - * 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 org.apache.commons.graph.*; - -import java.util.BitSet; - -public class DataFlowSolutionsTest extends GraphTest { - private static BitSet BS_000 = null; - private static BitSet BS_001 = null; - private static BitSet BS_010 = null; - private static BitSet BS_011 = null; - private static BitSet BS_100 = null; - private static BitSet BS_101 = null; - private static BitSet BS_110 = null; - private static BitSet BS_111 = null; - - static { - BS_000 = new BitSet(); - BS_001 = new BitSet(); - BS_010 = new BitSet(); - BS_011 = new BitSet(); - BS_100 = new BitSet(); - BS_101 = new BitSet(); - BS_110 = new BitSet(); - BS_111 = new BitSet(); - - BS_001.set( 3 ); - BS_011.set( 3 ); - BS_101.set( 3 ); - BS_111.set( 3 ); - - BS_010.set( 2 ); - BS_011.set( 2 ); - BS_110.set( 2 ); - BS_111.set( 2 ); - - BS_100.set( 1 ); - BS_101.set( 1 ); - BS_110.set( 1 ); - BS_111.set( 1 ); - } - - public DataFlowSolutionsTest( String name ) { - super( name ); - } - - public void testBitSetEquals() throws Throwable { - BitSet one = new BitSet(); - BitSet two = new BitSet(); - - one.set( 15 ); - two.set( 15 ); - - assertTrue( one.equals( two )); - } - - /** - * Test a single Vertex. - * - * @ [ gen (1) ] --> [ leaves(1) ] - * - * @ [ gen (1) kill(1) ] --> [ ] - * - * @ [ ] --> [ ] - */ - public void testOneGraph() throws Throwable { - DirectedGraph graph = makeDirSingleVertex(); - - BitSet clear = new BitSet(); - BitSet gen = new BitSet(); - BitSet kill = new BitSet(); - BitSet leaves = new BitSet(); - - DataFlowSolutions IUT = null; - MockDataFlowEq dfe = null; - - dfe = new MockDataFlowEq(); - - dfe.addVertex( V1, BS_100, BS_000 ); - - IUT = new DataFlowSolutions( graph, dfe ); - assertEquals( "Expected nothing to reach V1.", - BS_000, IUT.reaches( V1 )); - assertEquals( "Expected 1 to leave V1.", - BS_100, IUT.leaves( V1 ) ); - - - dfe = new MockDataFlowEq(); - dfe.addVertex( V1, BS_100, BS_100 ); - - IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals( "Expected nothing to reach V1.", - BS_000, IUT.reaches( V1 )); - assertEquals( "Expected nothing to leave V1.", - BS_000, IUT.leaves( V1 ) ); - - dfe = new MockDataFlowEq(); - dfe.addVertex( V1, BS_000, BS_100 ); - - IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals( "Expected nothing to leave V1.", - BS_000, IUT.leaves( V1 ) ); - assertEquals( "Expected nothing to reach V1.", - BS_000, IUT.reaches( V1 ) ); - } - - /** - * Test two vertices - * - * gen(V1) = (1,2) - * kill(V2) = (1,2) - * leaves(V1) = (1,2) - * reaches(V1) = () - * leaves(V2) = () - * reaches(V2) = (1,2) - */ - public void testTwoVerts0() - throws Throwable - { - DirectedGraph graph = makeDirectedEdge(); - MockDataFlowEq dfe = new MockDataFlowEq(); - - BitSet genV1 = new BitSet(); - genV1.set( 1 ); - genV1.set( 2 ); - - dfe.addVertex( V1, BS_110, BS_000 ); - dfe.addVertex( V2, BS_000, BS_110 ); - - DataFlowSolutions IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals( "Expected 1 and 2 to leave V1", - BS_110, IUT.leaves( V1 )); - assertEquals( "Expected nothing to reach V1", - BS_000, IUT.reaches( V1 )); - - assertEquals( "Expected 1 and 2 to reach V2", - BS_110, IUT.reaches( V2 )); - assertEquals( "Expected nothing to leave V2", - BS_000, IUT.leaves( V2 )); - } - - /** - * Test two vertices - * - * gen(V1) = (1,2) - * kill(V2) = (1) - * leaves(V1) = (1,2) - * reaches(V1) = () - * leaves(V2) = (2) - * reaches(V2) = (1,2) - */ - public void testTwoVerts1() - throws Throwable - { - DirectedGraph graph = makeDirectedEdge(); - MockDataFlowEq dfe = new MockDataFlowEq(); - - dfe.addVertex( V1, BS_110, BS_000 ); - dfe.addVertex( V2, BS_000, BS_100 ); - - DataFlowSolutions IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals( "Expected 1 and 2 to leave V1", - BS_110, IUT.leaves( V1 )); - assertEquals( "Expected nothing to reach V1", - BS_000, IUT.reaches( V1 )); - - assertEquals( "Expected 1 and 2 to reach V2", - BS_110, IUT.reaches( V2 )); - assertEquals( "Expected 2 to leave V2", - BS_010, IUT.leaves( V2 )); - } - - /** - * Test two vertices - * - * gen(V1) = (1) - * kill(v1) = () - * - * gen(V2) = (2) - * kill(V2) = (1) - * - * leaves(V1) = (1) - * reaches(V1) = () - * - * leaves(V2) = (2) - * reaches(V2) = (1) - */ - public void testTwoVerts2() - throws Throwable - { - DirectedGraph graph = makeDirectedEdge(); - MockDataFlowEq dfe = new MockDataFlowEq(); - - BitSet genV1 = new BitSet(); - genV1.set( 1 ); - - dfe.addVertex( V1, BS_100, BS_000 ); - dfe.addVertex( V2, BS_010, BS_100 ); - - DataFlowSolutions IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals( "Expected 1 to leave V1", - BS_100, IUT.leaves( V1 )); - assertEquals( "Expected nothing to reach V1", - BS_000, IUT.reaches( V1 )); - - assertEquals( "Expected 1 to reach V2", - BS_100, IUT.reaches( V2 )); - assertEquals( "Expected 2 to leave V2", - BS_010, IUT.leaves( V2 )); - } - - /** - * Test with a Cycle: - * - * * +1 - * / \ - * +2 *---* +3 - * - * 1, 2, 3 reach all and leave all. - */ - public void testCycle0() - throws Throwable - { - DirectedGraph graph = makeDirectedCycle(); - MockDataFlowEq dfe = new MockDataFlowEq(); - - dfe.addVertex( V1, BS_100, BS_000); - dfe.addVertex( V2, BS_010, BS_000); - dfe.addVertex( V3, BS_001, BS_000); - - DataFlowSolutions IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals("Expecting all to reach V1", - BS_111, IUT.reaches( V1 )); - assertEquals("Expecting all to reach V2", - BS_111, IUT.reaches( V2 )); - assertEquals("Expecting all to reach V3", - BS_111, IUT.reaches( V3 )); - - assertEquals("Expecting all to leave V1", - BS_111, IUT.leaves( V1 )); - assertEquals("Expecting all to leave V2", - BS_111, IUT.leaves( V2 )); - assertEquals("Expecting all to leave V3", - BS_111, IUT.leaves( V3 )); - } - - /** - * Test with a Cycle: - * - * * +1 -3 - * / \ - * +2 -1 *---* +3 -2 - * - */ - public void testCycle1() - throws Throwable - { - DirectedGraph graph = makeDirectedCycle(); - MockDataFlowEq dfe = new MockDataFlowEq(); - - dfe.addVertex( V1, BS_100, BS_001); - dfe.addVertex( V2, BS_010, BS_100); - dfe.addVertex( V3, BS_001, BS_010); - - DataFlowSolutions IUT = new DataFlowSolutions( graph, dfe ); - - assertEquals("Expecting 3 to reach V1", - BS_001, IUT.reaches( V1 )); - assertEquals("Expecting 1 to reach V2", - BS_100, IUT.reaches( V2 )); - assertEquals("Expecting 2 to reach V3", - BS_010, IUT.reaches( V3 )); - - assertEquals("Expecting 1 to leave V1", - BS_100, IUT.leaves( V1 )); - assertEquals("Expecting 2 to leave V2", - BS_010, IUT.leaves( V2 )); - assertEquals("Expecting 3 to leave V3", - BS_001, IUT.leaves( V3 )); - } - -}
diff --git a/base/src/test/java/org/apache/commons/graph/algorithm/dataflow/MockDataFlowEq.java b/base/src/test/java/org/apache/commons/graph/algorithm/dataflow/MockDataFlowEq.java deleted file mode 100644 index bd908c2..0000000 --- a/base/src/test/java/org/apache/commons/graph/algorithm/dataflow/MockDataFlowEq.java +++ /dev/null
@@ -1,48 +0,0 @@ -package org.apache.commons.graph.algorithm.dataflow; - -/* - * 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 java.util.Map; -import java.util.BitSet; -import java.util.HashMap; - -import org.apache.commons.graph.*; - -public class MockDataFlowEq - implements DataFlowEquations -{ - private Map generates = new HashMap(); // VERTEX X BITSET - private Map kills = new HashMap(); // VERTEX X BITSET - - public MockDataFlowEq() { } - - public void addVertex( Vertex v, BitSet generate, BitSet kill ) { - generates.put( v, generate ); - kills.put( v, kill ); - } - - public BitSet generates( Vertex v ) { - return (BitSet) generates.get( v ); - } - - public BitSet kills( Vertex v ) { - return (BitSet) kills.get( v ); - } -}
diff --git a/base/src/test/java/org/apache/commons/graph/contract/AcyclicContractTest.java b/base/src/test/java/org/apache/commons/graph/contract/AcyclicContractTest.java deleted file mode 100644 index a27a3ed..0000000 --- a/base/src/test/java/org/apache/commons/graph/contract/AcyclicContractTest.java +++ /dev/null
@@ -1,427 +0,0 @@ -package org.apache.commons.graph.contract; - -/* - * 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 org.apache.commons.graph.*; -import org.apache.commons.graph.exception.*; - -/** - * Description of the Class - */ -public class AcyclicContractTest - extends GraphTest -{ - /** - * Constructor for the AcyclicContractTest object - * - * @param name - */ - public AcyclicContractTest(String name) - { - super(name); - } - - /** - * A unit test for JUnit - */ - public void testDirNullGraph() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDirNullGraph()); - - IUT.verify(); - } - - /** - * A unit test for JUnit - */ - public void testDirSingleVertex() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDirSingleVertex()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - } - - /** - * A unit test for JUnit - */ - public void testSelfLoop() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeSelfLoop()); - - try - { - IUT.verify(); - fail("No CycleException thrown on Verification."); - } - catch (CycleException ex) - {} - } - - /** - * A unit test for JUnit - */ - public void testDirDoubleVertex() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDirDoubleVertex()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V1_V2, V1, V2); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V1->V2"); - } - } - - - /** - * A unit test for JUnit - */ - public void testDirectedEdge() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDirectedEdge()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V1_V2_, V1, V2); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V1->V2'"); - } - - try - { - IUT.addEdge(V2_V1, V2, V1); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - } - - /** - * A unit test for JUnit - */ - public void testDirParallelEdges() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDirParallelEdges()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V1_V2__, V1, V2); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V1->V2'"); - } - - try - { - IUT.addEdge(V2_V1, V2, V1); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - } - - - /** - * A unit test for JUnit - */ - public void testTwoCycle() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeTwoCycle()); - - try - { - IUT.verify(); - fail("No CycleException thrown on Verification."); - } - catch (CycleException ex) - {} - } - - - /** - * A unit test for JUnit - */ - public void testDirectedCycle() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDirectedCycle()); - - try - { - IUT.verify(); - fail("No CycleException thrown on Verification."); - } - catch (CycleException ex) - {} - } - - /** - * A unit test for JUnit - */ - public void testPipe() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makePipe()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V1_V2_, V1, V2); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V1->V2'"); - } - - try - { - IUT.addEdge(V3_V1, V3, V1); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - - } - - /** - * A unit test for JUnit - */ - public void testDiamond() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeDiamond()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V2_V3, V2, V3); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V2->V3"); - } - - try - { - IUT.addEdge(V4_V1, V4, V1); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - } - - /** - * A unit test for JUnit - */ - public void testPipelessCycle() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makePipelessCycle()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V2_V3, V2, V3); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V2->V3"); - } - - try - { - IUT.addEdge(V3_V4, V3, V4); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - - } - - - /** - * A unit test for JUnit - */ - public void testParentTree() - throws Throwable - { - System.err.println("---- PARENT TREE ----"); - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeParentTree()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V2_V3, V2, V3); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V2->V3"); - } - - try - { - IUT.addEdge(V1_V5, V1, V5); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - } - - - /** - * A unit test for JUnit - */ - public void testChildTree() - throws Throwable - { - AcyclicContract IUT = - new AcyclicContract(); - IUT.setImpl(makeChildTree()); - IUT.verify(); - - try - { - IUT.addEdge(V1_V1, V1, V1); - fail("No GraphException thrown when Self-Cycle introduced."); - } - catch (CycleException ex) - {} - - try - { - IUT.addEdge(V2_V3, V2, V3); - } - catch (GraphException ex) - { - fail("Contract prevented adding of valid edge. V2->V3"); - } - - try - { - IUT.addEdge(V5_V1, V5, V1); - fail("Contract allowed cycle to be introduced."); - } - catch (CycleException ex) - {} - - } -}
diff --git a/base/src/test/java/org/apache/commons/graph/contract/DAGTest.java b/base/src/test/java/org/apache/commons/graph/contract/DAGTest.java deleted file mode 100644 index e6e55a9..0000000 --- a/base/src/test/java/org/apache/commons/graph/contract/DAGTest.java +++ /dev/null
@@ -1,289 +0,0 @@ -package org.apache.commons.graph.contract; - -/* - * 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 org.apache.commons.graph.*; -import org.apache.commons.graph.contract.*; -import org.apache.commons.graph.exception.*; -import org.apache.commons.graph.factory.*; - -/** - * Description of the Class - */ -public class DAGTest - extends GraphTest -{ - private Contract[] dagContracts = new Contract[1]; - private GraphFactory factory = new GraphFactory(); - private String testName = null; - - /** - * Constructor for the DAGTest object - * - * @param name - */ - public DAGTest(String name) - { - super(name); - this.testName = name; - } - - /** - * The JUnit setup method - */ - public void setUp() - { - dagContracts[0] = new AcyclicContract(); - } - - /** - * A unit test for JUnit - */ - public void testDAGSelfLoop() - throws Throwable - { - DirectedGraph dg = null; - try - { - try - { - dg = factory.makeDirectedGraph(dagContracts, - true, - makeSelfLoop()); - fail("Should not have created DAG."); - } - catch (CycleException ex) - {} - } - catch (Throwable ex) - { - printGraph(ex, dg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testDAGTwoLoop() - throws Throwable - { - DirectedGraph dg = null; - try - { - try - { - dg = factory.makeDirectedGraph(dagContracts, - true, - makeTwoCycle()); - fail("Should not have created DAG."); - } - catch (CycleException ex) - {} - } - catch (Throwable ex) - { - printGraph(ex, dg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testMakeDAGDirCycle() - throws Throwable - { - MutableDirectedGraph mdg = null; - try - { - mdg = factory.makeMutableDirectedGraph(dagContracts, - true, - null); - mdg.addVertex(V1); - mdg.addVertex(V2); - mdg.addEdge(V1_V2, V1, V2); - - mdg.addVertex(V3); - mdg.addEdge(V2_V3, V2, V3); - - try - { - mdg.addEdge(V3_V1, V3, V1); - fail("No CycleException thrown on introduction of cycle."); - } - catch (CycleException ex) - {} - } - catch (Throwable t) - { - printGraph(t, mdg); - } - } - - /** - * A unit test for JUnit - */ - public void testDAGDirCycle() - throws Throwable - { - DirectedGraph dg = null; - try - { - try - { - dg = factory.makeDirectedGraph(dagContracts, - true, - makeDirectedCycle()); - fail("Should not have created DAG."); - } - catch (CycleException ex) - {} - } - catch (Throwable ex) - { - printGraph(ex, dg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testDAGAddCycleToPipe() - throws Throwable - { - MutableDirectedGraph mdg = null; - try - { - try - { - mdg = factory.makeMutableDirectedGraph(dagContracts, - true, - makePipe()); - mdg.addEdge(V3_V1, V3, V1); - fail("No Exception thrown on adding of invalid edge."); - } - catch (CycleException e) - {} - } - catch (Throwable ex) - { - printGraph(ex, mdg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testDAGAddCycleToDirEdge() - throws Throwable - { - MutableDirectedGraph mdg = null; - try - { - try - { - mdg = factory.makeMutableDirectedGraph(dagContracts, - true, - makeDirectedEdge()); - mdg.addEdge(V2_V1, V2, V1); - fail("Failed to throw exception on introducing Cycle."); - } - catch (CycleException ex) - {} - } - catch (Throwable ex) - { - printGraph(ex, mdg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testDAGAddSelfLoop() - throws Throwable - { - MutableDirectedGraph mdg = null; - try - { - try - { - mdg = factory.makeMutableDirectedGraph(dagContracts, - true, - makeDirSingleVertex()); - mdg.addEdge(V1_V1, V1, V1); - fail("Failed to throw exception on introducing Self Loop."); - } - catch (CycleException ex) - {} - } - catch (Throwable ex) - { - printGraph(ex, mdg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testDAGValidEdge() - throws Throwable - { - MutableDirectedGraph mdg = null; - try - { - mdg = factory.makeMutableDirectedGraph(dagContracts, - true, - makeParentTree()); - mdg.addEdge(V2_V3, V2, V3); - } - catch (Throwable ex) - { - printGraph(ex, mdg); - throw ex; - } - } - - /** - * A unit test for JUnit - */ - public void testDAGValidEdge2() - throws Throwable - { - MutableDirectedGraph mdg = null; - try - { - mdg = factory.makeMutableDirectedGraph(dagContracts, - true, - makeDirDoubleVertex()); - mdg.addEdge(V1_V2, V1, V2); - } - catch (Throwable ex) - { - printGraph(ex, mdg); - throw ex; - } - } -}
diff --git a/benchmarks/pom.xml b/benchmarks/pom.xml new file mode 100644 index 0000000..8eec033 --- /dev/null +++ b/benchmarks/pom.xml
@@ -0,0 +1,115 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-benchmarks</artifactId> + + <name>Apache Commons Graph - Benchmarks</name> + <description>Benchmarks across multiple Graph algorithms.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-scc</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-shortestpath</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-spanning</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <!-- test dependencies --> + <dependency> + <groupId>com.carrotsearch</groupId> + <artifactId>junit-benchmarks</artifactId> + <classifier>jdk15</classifier> + <version>0.3.0</version> + <scope>test</scope> + </dependency> + + <dependency> + <groupId>org.slf4j</groupId> + <artifactId>slf4j-api</artifactId> + <version>1.6.1</version> + <scope>test</scope> + </dependency> + + <dependency> + <groupId>com.h2database</groupId> + <artifactId>h2</artifactId> + <version>1.3.158</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + + <plugins> + <plugin> + <artifactId>maven-surefire-plugin</artifactId> + <configuration> + <systemPropertyVariables> + <jub.consumers>CONSOLE,XML,H2</jub.consumers> + <jub.db.file>${project.parent.build.directory}/benchmarks/database</jub.db.file> + <jub.xml.file>${project.parent.build.directory}/benchmarks.xml</jub.xml.file> + <jub.charts.dir>${project.parent.build.directory}/site/benchmarks</jub.charts.dir> + </systemPropertyVariables> + <argLine>-Xmx512m -Xms512m</argLine> + </configuration> + </plugin> + </plugins> + </build> + +</project>
diff --git a/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java b/benchmarks/src/test/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java similarity index 92% rename from src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java rename to benchmarks/src/test/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java index d8aef0b..844031e 100644 --- a/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java +++ b/benchmarks/src/test/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java
@@ -21,8 +21,8 @@ import static java.lang.String.format; import static java.lang.String.valueOf; -import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; +import static org.apache.commons.graph.scc.SccSolver.findStronglyConnectedComponent; import static org.junit.Assert.assertTrue; import java.util.ArrayList; @@ -32,9 +32,9 @@ import org.apache.commons.graph.GraphException; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; import org.junit.BeforeClass; import org.junit.Rule; import org.junit.Test;
diff --git a/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java b/benchmarks/src/test/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java similarity index 92% rename from src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java rename to benchmarks/src/test/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java index f1f5ea1..25c2edb 100644 --- a/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java +++ b/benchmarks/src/test/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java
@@ -21,8 +21,8 @@ import static java.lang.String.format; import static java.lang.String.valueOf; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; import static org.junit.Assert.assertTrue; import java.util.ArrayList; @@ -30,17 +30,16 @@ import java.util.List; import java.util.Random; -import org.apache.commons.graph.builder.AbstractGraphConnection; import org.apache.commons.graph.GraphException; import org.apache.commons.graph.Mapper; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; -import org.apache.commons.graph.model.DirectedMutableGraph; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.weight.OrderedMonoid; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; - +import org.apache.commons.graph.builder.AbstractGraphConnection; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.BeforeClass; import org.junit.Rule; import org.junit.Test;
diff --git a/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java b/benchmarks/src/test/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java similarity index 92% rename from src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java rename to benchmarks/src/test/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java index 23e824e..9484ae3 100644 --- a/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java +++ b/benchmarks/src/test/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java
@@ -21,8 +21,8 @@ import static java.lang.String.format; import static java.lang.String.valueOf; -import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree; -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newUndirectedMutableGraph; +import static org.apache.commons.graph.spanning.SpanningTreeSolver.minimumSpanningTree; import static org.junit.Assert.assertTrue; import java.util.ArrayList; @@ -33,10 +33,10 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.SpanningTree; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.BeforeClass; import org.junit.Rule; import org.junit.Test;
diff --git a/collections/disjoint-set/pom.xml b/collections/disjoint-set/pom.xml new file mode 100644 index 0000000..ba532ca --- /dev/null +++ b/collections/disjoint-set/pom.xml
@@ -0,0 +1,46 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + <relativePath>../../</relativePath> + </parent> + + <artifactId>commons-graph-disjointset</artifactId> + + <name>Apache Commons Graph - Collections - Disjoint Set</name> + <description>Disjoint Set data structure implementation.</description> + + <build> + <resources> + <resource> + <directory>${basedir}/../../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/collections/DisjointSet.java b/collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/DisjointSet.java similarity index 100% rename from src/main/java/org/apache/commons/graph/collections/DisjointSet.java rename to collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
diff --git a/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java b/collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java similarity index 100% rename from src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java rename to collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
diff --git a/src/main/java/org/apache/commons/graph/collections/package-info.java b/collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/package-info.java similarity index 88% rename from src/main/java/org/apache/commons/graph/collections/package-info.java rename to collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/package-info.java index ca5e262..f81f727 100644 --- a/src/main/java/org/apache/commons/graph/collections/package-info.java +++ b/collections/disjoint-set/src/main/java/org/apache/commons/graph/collections/package-info.java
@@ -1,5 +1,5 @@ /** - * Commons collections not already implemented in any ASL2.0 licensed package. + * Simple <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint-set</a> implementation. */ package org.apache.commons.graph.collections;
diff --git a/collections/fibonacci-heap/pom.xml b/collections/fibonacci-heap/pom.xml new file mode 100644 index 0000000..38e00c9 --- /dev/null +++ b/collections/fibonacci-heap/pom.xml
@@ -0,0 +1,46 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + <relativePath>../../</relativePath> + </parent> + + <artifactId>commons-graph-fibonacciheap</artifactId> + + <name>Apache Commons Graph - Collections - Fibonacci Heap</name> + <description>Fibonacci Heap data structure implementation.</description> + + <build> + <resources> + <resource> + <directory>${basedir}/../../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java b/collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java similarity index 98% rename from src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java rename to collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java index 7040594..c14b6e3 100644 --- a/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java +++ b/collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
@@ -19,8 +19,6 @@ * under the License. */ -import static org.apache.commons.graph.utils.Assertions.checkNotNull; - import static java.lang.Math.floor; import static java.lang.Math.log; import static java.lang.Math.sqrt; @@ -127,7 +125,7 @@ // 7 concatenate the root list containing x with root list H node.getLeft().setRight( node.getRight() ); node.getRight().setLeft( node.getLeft() ); - + node.setLeft( minimumNode ); node.setRight( minimumNode.getRight() ); minimumNode.setRight( node ); @@ -159,7 +157,10 @@ */ public boolean add( E e ) { - checkNotNull( e, "Null elements not allowed in this FibonacciHeap implementation." ); + if ( e == null ) + { + throw new IllegalArgumentException( "Null elements not allowed in this FibonacciHeap implementation." ); + } // 1-6 performed in the node initialization FibonacciHeapNode<E> node = new FibonacciHeapNode<E>( e );
diff --git a/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java b/collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java similarity index 100% rename from src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java rename to collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/FibonacciHeapNode.java
diff --git a/src/main/java/org/apache/commons/graph/collections/package-info.java b/collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/package-info.java similarity index 82% copy from src/main/java/org/apache/commons/graph/collections/package-info.java copy to collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/package-info.java index ca5e262..facd579 100644 --- a/src/main/java/org/apache/commons/graph/collections/package-info.java +++ b/collections/fibonacci-heap/src/main/java/org/apache/commons/graph/collections/package-info.java
@@ -1,5 +1,7 @@ /** - * Commons collections not already implemented in any ASL2.0 licensed package. + * A Fibonacci Heap implementation based on + * <a href="http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm">University of Science and Technology of + * China</a> lesson. */ package org.apache.commons.graph.collections;
diff --git a/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java b/collections/fibonacci-heap/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java similarity index 98% rename from src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java rename to collections/fibonacci-heap/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java index fe75c3f..739f7f8 100644 --- a/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java +++ b/collections/fibonacci-heap/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java
@@ -141,7 +141,7 @@ Integer i = queue.poll(); assertThat( i, is( integer ) ); } - + assertThat( queue.isEmpty(), is( true ) ); } @@ -149,17 +149,17 @@ public void addAllAndContinsItem() { Collection<Integer> c = new ArrayList<Integer>(); - + c.add( 50 ); c.add( 100 ); c.add( 20 ); c.add( 21 ); queue.addAll( c ); - + assertThat( queue.isEmpty(), is( false ) ); assertThat( queue.containsAll( c ), is( true ) ); - + assertThat( queue.contains( 100 ), is( true ) ); assertThat( queue.contains( 21 ), is( true ) ); assertThat( queue.contains( 50 ), is( true ) ); @@ -194,10 +194,11 @@ assertThat( queue.element(), is( 20 ) ); assertThat( queue.size(), is( 4 ) ); } - + @Test( expected = NoSuchElementException.class ) public void elementThrowsException() { queue.element(); } + }
diff --git a/coloring/pom.xml b/coloring/pom.xml new file mode 100644 index 0000000..a9727dc --- /dev/null +++ b/coloring/pom.xml
@@ -0,0 +1,60 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-coloring</artifactId> + + <name>Apache Commons Graph - Coloring</name> + <description>Graph coloring problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java b/coloring/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/ColoredVertices.java
diff --git a/src/main/java/org/apache/commons/graph/coloring/ColoringAlgorithmsSelector.java b/coloring/src/main/java/org/apache/commons/graph/coloring/ColoringAlgorithmsSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/ColoringAlgorithmsSelector.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/ColoringAlgorithmsSelector.java
diff --git a/coloring/src/main/java/org/apache/commons/graph/coloring/ColoringSolver.java b/coloring/src/main/java/org/apache/commons/graph/coloring/ColoringSolver.java new file mode 100644 index 0000000..eeb166f --- /dev/null +++ b/coloring/src/main/java/org/apache/commons/graph/coloring/ColoringSolver.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.coloring; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.UndirectedGraph; + +public final class ColoringSolver +{ + + private ColoringSolver() + { + // do nothing + } + + /** + * Create a color builder. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param <G> the Graph type + * @param graph the input graph + * @return an instance of {@link ColorsBuilder} + */ + public static <V, E, G extends UndirectedGraph<V, E>> ColorsBuilder<V, E> coloring( G graph ) + { + graph = checkNotNull( graph, "Coloring can not be calculated on null graph" ); + return new DefaultColorsBuilder<V, E>( graph ); + } + +}
diff --git a/src/main/java/org/apache/commons/graph/coloring/ColorsBuilder.java b/coloring/src/main/java/org/apache/commons/graph/coloring/ColorsBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/ColorsBuilder.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/ColorsBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java b/coloring/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java
diff --git a/src/main/java/org/apache/commons/graph/coloring/DefaultColorsBuilder.java b/coloring/src/main/java/org/apache/commons/graph/coloring/DefaultColorsBuilder.java similarity index 97% rename from src/main/java/org/apache/commons/graph/coloring/DefaultColorsBuilder.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/DefaultColorsBuilder.java index 0d1a7c2..e9d0ea0 100644 --- a/src/main/java/org/apache/commons/graph/coloring/DefaultColorsBuilder.java +++ b/coloring/src/main/java/org/apache/commons/graph/coloring/DefaultColorsBuilder.java
@@ -31,7 +31,7 @@ * @param <V> the Graph vertices type * @param <E> the Graph edges type */ -public final class DefaultColorsBuilder<V, E> +final class DefaultColorsBuilder<V, E> implements ColorsBuilder<V, E> {
diff --git a/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java b/coloring/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/NotEnoughColorsException.java
diff --git a/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java b/coloring/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/UncoloredOrderedVertices.java
diff --git a/src/main/java/org/apache/commons/graph/coloring/package-info.java b/coloring/src/main/java/org/apache/commons/graph/coloring/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/coloring/package-info.java rename to coloring/src/main/java/org/apache/commons/graph/coloring/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/utils/GraphUtils.java b/coloring/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java similarity index 75% rename from src/test/java/org/apache/commons/graph/utils/GraphUtils.java rename to coloring/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java index b344ea5..5396fed 100644 --- a/src/test/java/org/apache/commons/graph/utils/GraphUtils.java +++ b/coloring/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.utils; +package org.apache.commons.graph.coloring; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -21,53 +21,78 @@ import static java.lang.String.format; import static java.lang.String.valueOf; +import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertTrue; import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; import java.util.List; +import java.util.Map; +import java.util.Random; +import java.util.Set; import org.apache.commons.graph.GraphException; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; +import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.model.BaseMutableGraph; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; /** - * Utilities graph class. + * Abstract class used for test coloring. */ -public class GraphUtils +abstract class AbstractColoringTest { /** - * Creates a complete graph with nVertices - * - * @param nVertices number of vertices - * @param g graph + * Return a random association with index and a color string in RGB. */ - public static void buildCompleteGraph( int nVertices, BaseMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) + protected static Map<Integer, String> createColorMap( int numColor ) { - // building Graph - for ( int i = 0; i < nVertices; i++ ) + Map<Integer, String> colorCodes = new HashMap<Integer, String>(); + for ( int i = 0; i < 100; i++ ) { - BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) ); - g.addVertex( v ); + Random rnd = new Random( i ); + colorCodes.put( i, String.format( "\"#%2x%2x%2x\"", rnd.nextInt( 255 ), rnd.nextInt( 255 ), rnd.nextInt( 255 ) ) ); } + return colorCodes; + } - for ( BaseLabeledVertex v1 : g.getVertices() ) + /** + * Creates a list of integer colors. + * + * @param colorNumber number of colors + * @return the list. + */ + protected static Set<Integer> createColorsList( int colorNumber ) + { + Set<Integer> colors = new HashSet<Integer>(); + for ( int j = 0; j < colorNumber; j++ ) { - for ( BaseLabeledVertex v2 : g.getVertices() ) - { - if ( !v1.equals( v2 ) ) - { - try - { - g.addEdge( v1, new BaseLabeledEdge( format( "%s -> %s", v1, v2 ) ), v2 ); - } - catch ( GraphException e ) - { - // ignore - } - } - } + colors.add( j ); + } + return colors; + } + + /** + * This method checks if all connected vertices have different colors. + * + * @param g + * @param coloredVertices + */ + protected static <V, E, C> void checkColoring( UndirectedMutableGraph<V, E> g, + ColoredVertices<V, C> coloredVertices ) + { + for ( E e : g.getEdges() ) + { + VertexPair<V> vp = g.getVertices( e ); + C h = coloredVertices.getColor( vp.getHead() ); + C t = coloredVertices.getColor( vp.getTail() ); + + assertNotNull( h ); + assertNotNull( t ); + assertTrue( !h.equals( t ) ); } } @@ -77,7 +102,7 @@ * @param nVertices number of vertices * @param g graph */ - public static void buildBipartedGraph( int nVertices, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) + protected static void buildBipartedGraph( int nVertices, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) { // building Graph for ( int i = 0; i < nVertices; i++ ) @@ -128,7 +153,7 @@ } } - public static void buildCrownGraph( int nVertices, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) + protected static void buildCrownGraph( int nVertices, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) { List<BaseLabeledVertex> tmp = new ArrayList<BaseLabeledVertex>(); @@ -163,7 +188,7 @@ * * @return */ - public static BaseLabeledVertex[][] buildSudokuGraph( UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> sudoku ) + protected static BaseLabeledVertex[][] buildSudokuGraph( UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> sudoku ) { BaseLabeledVertex[][] grid = new BaseLabeledVertex[9][9]; // build sudoku grid. @@ -271,12 +296,40 @@ return grid; } + + /** - * This class can't be instantiated + * Creates a complete graph with nVertices + * + * @param nVertices number of vertices + * @param g graph */ - private GraphUtils() + protected static void buildCompleteGraph( int nVertices, BaseMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) { - // do nothing + // building Graph + for ( int i = 0; i < nVertices; i++ ) + { + BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) ); + g.addVertex( v ); + } + + for ( BaseLabeledVertex v1 : g.getVertices() ) + { + for ( BaseLabeledVertex v2 : g.getVertices() ) + { + if ( !v1.equals( v2 ) ) + { + try + { + g.addEdge( v1, new BaseLabeledEdge( format( "%s -> %s", v1, v2 ) ), v2 ); + } + catch ( GraphException e ) + { + // ignore + } + } + } + } } }
diff --git a/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java b/coloring/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java similarity index 81% rename from src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java rename to coloring/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java index 36b81ea..4d9d430 100644 --- a/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java +++ b/coloring/src/test/java/org/apache/commons/graph/coloring/GraphColoringBackTrackingTestCase.java
@@ -19,12 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.coloring; -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildBipartedGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildCrownGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildSudokuGraph; +import static org.apache.commons.graph.Graphs.populate; +import static org.apache.commons.graph.coloring.ColoringSolver.coloring; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertNotNull; @@ -34,10 +30,10 @@ import org.apache.commons.graph.UndirectedGraph; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; /** @@ -80,22 +76,23 @@ final BaseLabeledVertex two = new BaseLabeledVertex( "2" ); UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = - newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ) + .withConnections( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + { + + @Override + public void connect() { + BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) ); + addVertex( two ); + BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) ); - @Override - public void connect() - { - BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) ); - addVertex( two ); - BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) ); + addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two ); + addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three ); + addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one ); + } - addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two ); - addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three ); - addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one ); - } - - } ); + } ); coloring( g ).withColors( createColorsList( 1 ) ).applyingBackTrackingAlgorithm(); } @@ -105,22 +102,23 @@ final BaseLabeledVertex two = new BaseLabeledVertex( "2" ); UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = - newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ) + .withConnections( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + { + + @Override + public void connect() { + BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) ); + addVertex( two ); + BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) ); - @Override - public void connect() - { - BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) ); - addVertex( two ); - BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) ); + addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two ); + addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three ); + addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one ); + } - addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two ); - addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three ); - addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one ); - } - - } ); + } ); ColoredVertices<BaseLabeledVertex, Integer> coloredVertex = new ColoredVertices<BaseLabeledVertex, Integer>(); coloredVertex.addColor( two, 2 ); @@ -265,7 +263,6 @@ sb.append( "\n" ); } Logger.getAnonymousLogger().fine( sb.toString() ); - } }
diff --git a/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java b/coloring/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java similarity index 81% rename from src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java rename to coloring/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java index e1a0be6..a394b3d 100644 --- a/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java +++ b/coloring/src/test/java/org/apache/commons/graph/coloring/GraphColoringTestCase.java
@@ -19,12 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.coloring; -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildBipartedGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildCrownGraph; -import static org.apache.commons.graph.utils.GraphUtils.buildSudokuGraph; +import static org.apache.commons.graph.Graphs.populate; +import static org.apache.commons.graph.coloring.ColoringSolver.coloring; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertNotNull; @@ -32,10 +28,10 @@ import org.apache.commons.graph.UndirectedGraph; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; /** @@ -78,22 +74,23 @@ final BaseLabeledVertex two = new BaseLabeledVertex( "2" ); UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = - newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ) + .withConnections( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + { + + @Override + public void connect() { + BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) ); + addVertex( two ); + BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) ); - @Override - public void connect() - { - BaseLabeledVertex one = addVertex( new BaseLabeledVertex( "1" ) ); - addVertex( two ); - BaseLabeledVertex three = addVertex( new BaseLabeledVertex( "3" ) ); + addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two ); + addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three ); + addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one ); + } - addEdge( new BaseLabeledEdge( "1 -> 2" ) ).from( one ).to( two ); - addEdge( new BaseLabeledEdge( "2 -> 3" ) ).from( two ).to( three ); - addEdge( new BaseLabeledEdge( "3 -> 1" ) ).from( three ).to( one ); - } - - } ); + } ); coloring( g ).withColors( createColorsList( 1 ) ).applyingGreedyAlgorithm(); } @@ -102,7 +99,8 @@ throws Exception { UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = - newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ) + .withConnections( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() { @Override
diff --git a/connectivity/pom.xml b/connectivity/pom.xml new file mode 100644 index 0000000..b305fd9 --- /dev/null +++ b/connectivity/pom.xml
@@ -0,0 +1,67 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-connectivity</artifactId> + + <name>Apache Commons Graph - Connectivity</name> + <description>Graph connectivity problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-visit</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <!-- test dependencies --> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java similarity index 100% rename from src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java rename to connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
diff --git a/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java rename to connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java
diff --git a/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java rename to connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java
diff --git a/connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivitySolver.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivitySolver.java new file mode 100644 index 0000000..c7af853 --- /dev/null +++ b/connectivity/src/main/java/org/apache/commons/graph/connectivity/ConnectivitySolver.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.connectivity; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.Graph; + +public final class ConnectivitySolver +{ + + /** + * Calculates the input graph Connected Component. + * + * @param <V> the Graph vertices type. + * @param <E> the Graph edges type. + * @param <G> the directed graph type + * @param graph the Graph which connected component has to be verified. + * @return the Connectivity algorithm builder + */ + public static <V, E, G extends Graph<V, E>> ConnectivityBuilder<V, E> findConnectedComponent( G graph ) + { + graph = checkNotNull( graph, "Connected Component cannot be calculated from a null graph" ); + return new DefaultConnectivityBuilder<V, E>( graph ); + } + + private ConnectivitySolver() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java similarity index 96% rename from src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java rename to connectivity/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java index 5934f66..e918521 100644 --- a/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java +++ b/connectivity/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java
@@ -19,7 +19,7 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.visit; +import static org.apache.commons.graph.visit.GraphVisitor.visit; import static org.apache.commons.graph.utils.Assertions.checkState; import java.util.ArrayList; @@ -31,7 +31,7 @@ /** * TODO Fill me!! - * + * * @param <V> the Graph vertices type * @param <E> the Graph edges type */ @@ -45,7 +45,7 @@ /** * Create a new instance of {@link DefaultConnectivityAlgorithmsSelector} calculated for a set of included vertices - * + * * @param graph the graph * @param includedVertices included vertices */
diff --git a/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java similarity index 97% rename from src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java rename to connectivity/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java index 5992d09..57b2687 100644 --- a/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java +++ b/connectivity/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java
@@ -26,11 +26,11 @@ /** * TODO Fill me!! - * + * * @param <V> the Graph vertices type * @param <E> the Graph edges type */ -public class DefaultConnectivityBuilder<V, E> +final class DefaultConnectivityBuilder<V, E> implements ConnectivityBuilder<V, E> {
diff --git a/src/main/java/org/apache/commons/graph/connectivity/package-info.java b/connectivity/src/main/java/org/apache/commons/graph/connectivity/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/connectivity/package-info.java rename to connectivity/src/main/java/org/apache/commons/graph/connectivity/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java b/connectivity/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java similarity index 92% rename from src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java rename to connectivity/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java index cad923f..901af35 100644 --- a/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java +++ b/connectivity/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java
@@ -19,8 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.findConnectedComponent; -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; +import static org.apache.commons.graph.Graphs.populate; +import static org.apache.commons.graph.connectivity.ConnectivitySolver.findConnectedComponent; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNotNull; @@ -30,10 +30,11 @@ import org.apache.commons.graph.Graph; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; +import org.apache.commons.graph.builder.GraphConnection; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; /** @@ -41,7 +42,7 @@ public final class FindConnectedComponetTestCase { - @Test(expected=NullPointerException.class) + @Test( expected = NullPointerException.class ) public void verifyNullGraph() { findConnectedComponent( (Graph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>) null ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm(); @@ -246,4 +247,9 @@ assertEquals( 2, coll.size() ); } + private UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> newUndirectedMutableGraph( GraphConnection<BaseLabeledVertex, BaseLabeledEdge> graphConnection ) + { + return populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ).withConnections( graphConnection ); + } + }
diff --git a/elo/pom.xml b/elo/pom.xml new file mode 100644 index 0000000..2845b58 --- /dev/null +++ b/elo/pom.xml
@@ -0,0 +1,60 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-elo</artifactId> + + <name>Apache Commons Graph - ELO</name> + <description>Graph ELO rating implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/elo/Category.java b/elo/src/main/java/org/apache/commons/graph/elo/Category.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/Category.java rename to elo/src/main/java/org/apache/commons/graph/elo/Category.java
diff --git a/src/main/java/org/apache/commons/graph/elo/DefaultKFactorBuilder.java b/elo/src/main/java/org/apache/commons/graph/elo/DefaultKFactorBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/DefaultKFactorBuilder.java rename to elo/src/main/java/org/apache/commons/graph/elo/DefaultKFactorBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/elo/DefaultRankingSelector.java b/elo/src/main/java/org/apache/commons/graph/elo/DefaultRankingSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/DefaultRankingSelector.java rename to elo/src/main/java/org/apache/commons/graph/elo/DefaultRankingSelector.java
diff --git a/elo/src/main/java/org/apache/commons/graph/elo/EloSolver.java b/elo/src/main/java/org/apache/commons/graph/elo/EloSolver.java new file mode 100644 index 0000000..fb1a67b --- /dev/null +++ b/elo/src/main/java/org/apache/commons/graph/elo/EloSolver.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.elo; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.DirectedGraph; + +public final class EloSolver +{ + + /** + * Ranks the players (vertices) that took part in a tournament (graph) depending on the game results (edges), + * applying the <a href="http://en.wikipedia.org/wiki/Elo_rating_system.">Elo Rating System</a>. + * + * @param <P> the players involved in the tournament + * @param <TG> the Tournament Graph type + * @param tournamentGraph the graph representing the tournament + * @return the builder for the functor which returns/update the players ranking + */ + public static <P, TG extends DirectedGraph<P, GameResult>> RankingSelector<P> eloRate( TG tournamentGraph ) + { + tournamentGraph = checkNotNull( tournamentGraph, "ELO ranking can not be applied on null graph!" ); + return new DefaultRankingSelector<P>( tournamentGraph ); + } + + private EloSolver() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/elo/GameResult.java b/elo/src/main/java/org/apache/commons/graph/elo/GameResult.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/GameResult.java rename to elo/src/main/java/org/apache/commons/graph/elo/GameResult.java
diff --git a/src/main/java/org/apache/commons/graph/elo/KFactorBuilder.java b/elo/src/main/java/org/apache/commons/graph/elo/KFactorBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/KFactorBuilder.java rename to elo/src/main/java/org/apache/commons/graph/elo/KFactorBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/elo/PlayersRank.java b/elo/src/main/java/org/apache/commons/graph/elo/PlayersRank.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/PlayersRank.java rename to elo/src/main/java/org/apache/commons/graph/elo/PlayersRank.java
diff --git a/src/main/java/org/apache/commons/graph/elo/RankingSelector.java b/elo/src/main/java/org/apache/commons/graph/elo/RankingSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/RankingSelector.java rename to elo/src/main/java/org/apache/commons/graph/elo/RankingSelector.java
diff --git a/src/main/java/org/apache/commons/graph/elo/package-info.java b/elo/src/main/java/org/apache/commons/graph/elo/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/elo/package-info.java rename to elo/src/main/java/org/apache/commons/graph/elo/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/elo/EloTestCase.java b/elo/src/test/java/org/apache/commons/graph/elo/EloTestCase.java similarity index 90% rename from src/test/java/org/apache/commons/graph/elo/EloTestCase.java rename to elo/src/test/java/org/apache/commons/graph/elo/EloTestCase.java index ff8deda..3c14a1b 100644 --- a/src/test/java/org/apache/commons/graph/elo/EloTestCase.java +++ b/elo/src/test/java/org/apache/commons/graph/elo/EloTestCase.java
@@ -21,11 +21,12 @@ import static org.apache.commons.graph.elo.GameResult.WIN; -import static org.apache.commons.graph.CommonsGraph.eloRate; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.elo.EloSolver.eloRate; +import static org.apache.commons.graph.Graphs.populate; import org.apache.commons.graph.DirectedGraph; import org.apache.commons.graph.builder.AbstractGraphConnection; +import org.apache.commons.graph.model.DirectedMutableGraph; import org.junit.Test; /** @@ -38,7 +39,8 @@ public void performElo() { DirectedGraph<String, GameResult> tournament = - newDirectedMutableGraph( new AbstractGraphConnection<String, GameResult>() + populate( new DirectedMutableGraph<String, GameResult>() ) + .withConnections( new AbstractGraphConnection<String, GameResult>() { @Override @@ -85,6 +87,7 @@ eloRate( tournament ).wherePlayersAreRankedIn( playersRank ).withKFactor( 80 ); + // TODO find a way to asser the rate worked System.out.println( playersRank ); }
diff --git a/src/test/java/org/apache/commons/graph/elo/SimplePlayersRank.java b/elo/src/test/java/org/apache/commons/graph/elo/SimplePlayersRank.java similarity index 100% rename from src/test/java/org/apache/commons/graph/elo/SimplePlayersRank.java rename to elo/src/test/java/org/apache/commons/graph/elo/SimplePlayersRank.java
diff --git a/export/pom.xml b/export/pom.xml new file mode 100644 index 0000000..1b0406e --- /dev/null +++ b/export/pom.xml
@@ -0,0 +1,61 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-export</artifactId> + + <name>Apache Commons Graph - Export</name> + <description>Graph exporters to different formats implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <!-- test dependencies --> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/export/AbstractExporter.java b/export/src/main/java/org/apache/commons/graph/export/AbstractExporter.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/AbstractExporter.java rename to export/src/main/java/org/apache/commons/graph/export/AbstractExporter.java
diff --git a/src/main/java/org/apache/commons/graph/export/DefaultExportSelector.java b/export/src/main/java/org/apache/commons/graph/export/DefaultExportSelector.java similarity index 97% rename from src/main/java/org/apache/commons/graph/export/DefaultExportSelector.java rename to export/src/main/java/org/apache/commons/graph/export/DefaultExportSelector.java index 0e8e3db..00a2d92 100644 --- a/src/main/java/org/apache/commons/graph/export/DefaultExportSelector.java +++ b/export/src/main/java/org/apache/commons/graph/export/DefaultExportSelector.java
@@ -25,11 +25,11 @@ /** * {@link NamedExportSelector} implementation - * + * * @param <V> the Graph vertices type. * @param <E> the Graph edges type. */ -public final class DefaultExportSelector<V, E> +final class DefaultExportSelector<V, E> implements NamedExportSelector<V, E> {
diff --git a/src/main/java/org/apache/commons/graph/export/DotExporter.java b/export/src/main/java/org/apache/commons/graph/export/DotExporter.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/DotExporter.java rename to export/src/main/java/org/apache/commons/graph/export/DotExporter.java
diff --git a/src/main/java/org/apache/commons/graph/export/ExportSelector.java b/export/src/main/java/org/apache/commons/graph/export/ExportSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/ExportSelector.java rename to export/src/main/java/org/apache/commons/graph/export/ExportSelector.java
diff --git a/src/main/java/org/apache/commons/graph/export/GraphExportException.java b/export/src/main/java/org/apache/commons/graph/export/GraphExportException.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/GraphExportException.java rename to export/src/main/java/org/apache/commons/graph/export/GraphExportException.java
diff --git a/export/src/main/java/org/apache/commons/graph/export/GraphExporter.java b/export/src/main/java/org/apache/commons/graph/export/GraphExporter.java new file mode 100644 index 0000000..401d5dd --- /dev/null +++ b/export/src/main/java/org/apache/commons/graph/export/GraphExporter.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.export; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.Graph; + +public final class GraphExporter +{ + + /** + * Export the graph in DOT or GraphML format. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param <G> the Graph type + * @param graph the input graph + * @return an instance of {@link NamedExportSelector} + */ + public static <V, E, G extends Graph<V, E>> NamedExportSelector<V, E> export( G graph ) + { + graph = checkNotNull( graph, "Null graph can not be exported" ); + return new DefaultExportSelector<V, E>( graph ); + } + + private GraphExporter() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/export/GraphMLExporter.java b/export/src/main/java/org/apache/commons/graph/export/GraphMLExporter.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/GraphMLExporter.java rename to export/src/main/java/org/apache/commons/graph/export/GraphMLExporter.java
diff --git a/src/main/java/org/apache/commons/graph/export/NamedExportSelector.java b/export/src/main/java/org/apache/commons/graph/export/NamedExportSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/NamedExportSelector.java rename to export/src/main/java/org/apache/commons/graph/export/NamedExportSelector.java
diff --git a/src/main/java/org/apache/commons/graph/export/package-info.java b/export/src/main/java/org/apache/commons/graph/export/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/export/package-info.java rename to export/src/main/java/org/apache/commons/graph/export/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/export/EdgeLabelMapper.java b/export/src/test/java/org/apache/commons/graph/export/EdgeLabelMapper.java similarity index 94% rename from src/test/java/org/apache/commons/graph/export/EdgeLabelMapper.java rename to export/src/test/java/org/apache/commons/graph/export/EdgeLabelMapper.java index 8f84bf2..535ecd1 100644 --- a/src/test/java/org/apache/commons/graph/export/EdgeLabelMapper.java +++ b/export/src/test/java/org/apache/commons/graph/export/EdgeLabelMapper.java
@@ -20,7 +20,7 @@ */ import org.apache.commons.graph.Mapper; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; public final class EdgeLabelMapper implements Mapper<BaseLabeledWeightedEdge<Double>, String>
diff --git a/src/test/java/org/apache/commons/graph/export/EdgeWeightMapper.java b/export/src/test/java/org/apache/commons/graph/export/EdgeWeightMapper.java similarity index 94% rename from src/test/java/org/apache/commons/graph/export/EdgeWeightMapper.java rename to export/src/test/java/org/apache/commons/graph/export/EdgeWeightMapper.java index c406a14..9b966a8 100644 --- a/src/test/java/org/apache/commons/graph/export/EdgeWeightMapper.java +++ b/export/src/test/java/org/apache/commons/graph/export/EdgeWeightMapper.java
@@ -20,7 +20,7 @@ */ import org.apache.commons.graph.Mapper; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; public final class EdgeWeightMapper implements Mapper<BaseLabeledWeightedEdge<Double>, Double>
diff --git a/src/test/java/org/apache/commons/graph/export/ExportTestCase.java b/export/src/test/java/org/apache/commons/graph/export/ExportTestCase.java similarity index 85% rename from src/test/java/org/apache/commons/graph/export/ExportTestCase.java rename to export/src/test/java/org/apache/commons/graph/export/ExportTestCase.java index 0750467..af0540d 100644 --- a/src/test/java/org/apache/commons/graph/export/ExportTestCase.java +++ b/export/src/test/java/org/apache/commons/graph/export/ExportTestCase.java
@@ -19,18 +19,21 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.export; -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; +import static org.apache.commons.graph.Graphs.populate; +import static org.apache.commons.graph.export.GraphExporter.export; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.After; import org.junit.Before; import org.junit.Ignore; import org.junit.Test; +/** + * TODO find a way to assert exported graphs + */ public class ExportTestCase { private UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual; @@ -39,7 +42,8 @@ public void setUp() { actual = - newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() ) + .withConnections( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() { public void connect()
diff --git a/src/test/java/org/apache/commons/graph/export/VertexLabelMapper.java b/export/src/test/java/org/apache/commons/graph/export/VertexLabelMapper.java similarity index 94% rename from src/test/java/org/apache/commons/graph/export/VertexLabelMapper.java rename to export/src/test/java/org/apache/commons/graph/export/VertexLabelMapper.java index 804de69..988f66e 100644 --- a/src/test/java/org/apache/commons/graph/export/VertexLabelMapper.java +++ b/export/src/test/java/org/apache/commons/graph/export/VertexLabelMapper.java
@@ -20,7 +20,7 @@ */ import org.apache.commons.graph.Mapper; -import org.apache.commons.graph.model.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; public final class VertexLabelMapper implements Mapper<BaseLabeledVertex, String>
diff --git a/flow/pom.xml b/flow/pom.xml new file mode 100644 index 0000000..7cd1963 --- /dev/null +++ b/flow/pom.xml
@@ -0,0 +1,65 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-flow</artifactId> + + <name>Apache Commons Graph - Flow</name> + <description>Graph flow problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-visit</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/flow/DefaultFlowWeightedEdgesBuilder.java b/flow/src/main/java/org/apache/commons/graph/flow/DefaultFlowWeightedEdgesBuilder.java similarity index 96% rename from src/main/java/org/apache/commons/graph/flow/DefaultFlowWeightedEdgesBuilder.java rename to flow/src/main/java/org/apache/commons/graph/flow/DefaultFlowWeightedEdgesBuilder.java index 4620e40..877f45d 100644 --- a/src/main/java/org/apache/commons/graph/flow/DefaultFlowWeightedEdgesBuilder.java +++ b/flow/src/main/java/org/apache/commons/graph/flow/DefaultFlowWeightedEdgesBuilder.java
@@ -26,11 +26,11 @@ /** * {@link FlowWeightedEdgesBuilder} implementation - * + * * @param <V> the Graph vertices type * @param <WE> the Graph edges type */ -public final class DefaultFlowWeightedEdgesBuilder<V, WE> +final class DefaultFlowWeightedEdgesBuilder<V, WE> implements FlowWeightedEdgesBuilder<V, WE> {
diff --git a/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java b/flow/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java rename to flow/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java b/flow/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java similarity index 94% rename from src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java rename to flow/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java index 1bdd041..ac4697e 100644 --- a/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java +++ b/flow/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java
@@ -19,15 +19,16 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; -import static org.apache.commons.graph.CommonsGraph.visit; +import static org.apache.commons.graph.Graphs.populate; import static org.apache.commons.graph.utils.Assertions.checkNotNull; +import static org.apache.commons.graph.visit.GraphVisitor.visit; import org.apache.commons.graph.DirectedGraph; import org.apache.commons.graph.Mapper; import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.DirectedMutableGraph; /** * {@link MaxFlowAlgorithmSelector} implementation. @@ -115,7 +116,8 @@ private <WO extends OrderedMonoid<W>> DirectedGraph<V, EdgeWrapper<WE>> newFlowNetwok( final DirectedGraph<V, WE> graph, final WO weightOperations ) { - return newDirectedMutableGraph( new AbstractGraphConnection<V, EdgeWrapper<WE>>() + return populate( new DirectedMutableGraph<V, EdgeWrapper<WE>>() ) + .withConnections( new AbstractGraphConnection<V, EdgeWrapper<WE>>() { @Override public void connect() @@ -125,6 +127,7 @@ { addVertex( vertex ); } + // edges for ( WE edge : graph.getEdges() ) {
diff --git a/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java b/flow/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java rename to flow/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java b/flow/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java similarity index 97% rename from src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java rename to flow/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java index b101432..d57acc6 100644 --- a/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java +++ b/flow/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
@@ -30,10 +30,10 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.shortestpath.PredecessorsList; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PredecessorsList; import org.apache.commons.graph.visit.BaseGraphVisitHandler; import org.apache.commons.graph.visit.VisitState; -import org.apache.commons.graph.weight.OrderedMonoid; /** * Provides standard operations for max-flow algorithms,
diff --git a/flow/src/main/java/org/apache/commons/graph/flow/FlowSolver.java b/flow/src/main/java/org/apache/commons/graph/flow/FlowSolver.java new file mode 100644 index 0000000..012ba0b --- /dev/null +++ b/flow/src/main/java/org/apache/commons/graph/flow/FlowSolver.java
@@ -0,0 +1,50 @@ +package org.apache.commons.graph.flow; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.DirectedGraph; +import org.apache.commons.graph.Graph; + +public final class FlowSolver +{ + + /** + * Find the maximum flow on the input {@link Graph}. + * + * @param <V> the Graph vertices type + * @param <WE> the Graph edges type + * @param <G> the Graph type + * @param graph the input edge-weighted graph + * @return an instance of {@link FlowWeightedEdgesBuilder} + */ + public static <V, WE, G extends DirectedGraph<V, WE>> FlowWeightedEdgesBuilder<V, WE> findMaxFlow( G graph ) + { + graph = checkNotNull( graph, "Max flow can not be calculated on null graph" ); + return new DefaultFlowWeightedEdgesBuilder<V, WE>( graph ); + } + + private FlowSolver() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/flow/FlowWeightedEdgesBuilder.java b/flow/src/main/java/org/apache/commons/graph/flow/FlowWeightedEdgesBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/flow/FlowWeightedEdgesBuilder.java rename to flow/src/main/java/org/apache/commons/graph/flow/FlowWeightedEdgesBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/flow/FromHeadBuilder.java b/flow/src/main/java/org/apache/commons/graph/flow/FromHeadBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/flow/FromHeadBuilder.java rename to flow/src/main/java/org/apache/commons/graph/flow/FromHeadBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java b/flow/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java similarity index 96% rename from src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java rename to flow/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java index 14e0579..2789196 100644 --- a/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java +++ b/flow/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java
@@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * Maximum Flow algorithm selector
diff --git a/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java b/flow/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java rename to flow/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/flow/package-info.java b/flow/src/main/java/org/apache/commons/graph/flow/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/flow/package-info.java rename to flow/src/main/java/org/apache/commons/graph/flow/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java b/flow/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java similarity index 93% rename from src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java rename to flow/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java index 53b6a0a..2627648 100644 --- a/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java +++ b/flow/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
@@ -19,16 +19,16 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.findMaxFlow; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.flow.FlowSolver.findMaxFlow; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; import static org.junit.Assert.assertEquals; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.IntegerWeightBaseOperations; import org.apache.commons.graph.model.DirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.IntegerWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; /**
diff --git a/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java b/flow/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java similarity index 93% rename from src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java rename to flow/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java index d4d2a56..5b2caa4 100644 --- a/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java +++ b/flow/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
@@ -19,16 +19,16 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.findMaxFlow; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.flow.FlowSolver.findMaxFlow; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; import static org.junit.Assert.assertEquals; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.IntegerWeightBaseOperations; import org.apache.commons.graph.model.DirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.IntegerWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; /**
diff --git a/model/pom.xml b/model/pom.xml new file mode 100644 index 0000000..fa09e95 --- /dev/null +++ b/model/pom.xml
@@ -0,0 +1,53 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-model</artifactId> + + <name>Apache Commons Graph - Model</name> + <description>In memory Graph data structures implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/model/BaseGraph.java b/model/src/main/java/org/apache/commons/graph/model/BaseGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/model/BaseGraph.java rename to model/src/main/java/org/apache/commons/graph/model/BaseGraph.java
diff --git a/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java b/model/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java rename to model/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
diff --git a/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java b/model/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java rename to model/src/main/java/org/apache/commons/graph/model/DirectedMutableGraph.java
diff --git a/model/src/main/java/org/apache/commons/graph/model/GraphUtils.java b/model/src/main/java/org/apache/commons/graph/model/GraphUtils.java new file mode 100644 index 0000000..ad7c79e --- /dev/null +++ b/model/src/main/java/org/apache/commons/graph/model/GraphUtils.java
@@ -0,0 +1,70 @@ +package org.apache.commons.graph.model; + +/* + * 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 org.apache.commons.graph.Graphs.populate; + +import org.apache.commons.graph.builder.GraphConnection; +import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.UndirectedMutableGraph; + +/** + * Utilities graph class. + */ +public class GraphUtils +{ + + /** + * Creates a new {@link DirectedMutableGraph} instance where vertices + * are connected as described in the input {@link GraphConnection} instance. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param graphConnection the {@link GraphConnection} instance that describes vertices + * @return a new {@link DirectedMutableGraph} instance + */ + public static <V, E> DirectedMutableGraph<V, E> newDirectedMutableGraph( GraphConnection<V, E> graphConnection ) + { + return populate( new DirectedMutableGraph<V, E>() ).withConnections( graphConnection ); + } + + /** + * Creates a new {@link UndirectedMutableGraph} instance where vertices + * are connected as described in the input {@link GraphConnection} instance. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param graphConnection the {@link GraphConnection} instance that describes vertices + * @return a new {@link UndirectedMutableGraph} instance + */ + public static <V, E> UndirectedMutableGraph<V, E> newUndirectedMutableGraph( GraphConnection<V, E> graphConnection ) + { + return populate( new UndirectedMutableGraph<V, E>() ).withConnections( graphConnection ); + } + + /** + * This class can't be instantiated + */ + private GraphUtils() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/model/InMemoryPath.java b/model/src/main/java/org/apache/commons/graph/model/InMemoryPath.java similarity index 100% rename from src/main/java/org/apache/commons/graph/model/InMemoryPath.java rename to model/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
diff --git a/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java b/model/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java similarity index 97% rename from src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java rename to model/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java index fcc8539..9fa10ec 100644 --- a/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java +++ b/model/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
@@ -24,7 +24,7 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.weight.Monoid; +import org.apache.commons.graph.math.monoid.Monoid; /** * Support {@link WeightedPath} implementation, optimized for algorithms (such Dijkstra's) that need to rebuild the path @@ -49,10 +49,10 @@ /** * Creates a new instance of {@link InMemoryWeightedPath}. - * + * * @param start the start vertex * @param target the target vertex - * @param weightOperations + * @param weightOperations * @param weightedEdges */ public InMemoryWeightedPath( V start, V target, Monoid<W> weightOperations, Mapper<WE, W> weightedEdges )
diff --git a/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java b/model/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java similarity index 96% rename from src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java rename to model/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java index 674affb..591f693 100644 --- a/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java +++ b/model/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java
@@ -21,7 +21,7 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.weight.Monoid; +import org.apache.commons.graph.math.monoid.Monoid; /** * A memory-based implementation of a mutable spanning tree. @@ -47,8 +47,8 @@ /** * Creates a new instance of {@link MutableSpanningTree} - * - * @param weightOperations + * + * @param weightOperations * @param weightedEdges */ public MutableSpanningTree( Monoid<W> weightOperations, Mapper<WE, W> weightedEdges )
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java b/model/src/main/java/org/apache/commons/graph/model/PathNotFoundException.java similarity index 95% rename from src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java rename to model/src/main/java/org/apache/commons/graph/model/PathNotFoundException.java index 10616bc..467f710 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java +++ b/model/src/main/java/org/apache/commons/graph/model/PathNotFoundException.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.shortestpath; +package org.apache.commons.graph.model; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java b/model/src/main/java/org/apache/commons/graph/model/PredecessorsList.java similarity index 97% rename from src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java rename to model/src/main/java/org/apache/commons/graph/model/PredecessorsList.java index d9ddb79..980082a 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java +++ b/model/src/main/java/org/apache/commons/graph/model/PredecessorsList.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.shortestpath; +package org.apache.commons.graph.model; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -25,8 +25,8 @@ import org.apache.commons.graph.Graph; import org.apache.commons.graph.Mapper; import org.apache.commons.graph.WeightedPath; +import org.apache.commons.graph.math.monoid.Monoid; import org.apache.commons.graph.model.InMemoryWeightedPath; -import org.apache.commons.graph.weight.Monoid; /** * The predecessor list is a list of vertex of a {@link org.apache.commons.graph.Graph}.
diff --git a/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java b/model/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java rename to model/src/main/java/org/apache/commons/graph/model/UndirectedMutableGraph.java
diff --git a/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledEdge.java similarity index 97% rename from src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java rename to model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledEdge.java index d2af19d..ced7d84 100644 --- a/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java +++ b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledEdge.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.model; +package org.apache.commons.graph.model.labeled; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/test/java/org/apache/commons/graph/model/BaseLabeledVertex.java b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledVertex.java similarity index 97% rename from src/test/java/org/apache/commons/graph/model/BaseLabeledVertex.java rename to model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledVertex.java index ded8d3a..965793b 100644 --- a/src/test/java/org/apache/commons/graph/model/BaseLabeledVertex.java +++ b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledVertex.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.model; +package org.apache.commons.graph.model.labeled; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledWeightedEdge.java similarity index 97% rename from src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java rename to model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledWeightedEdge.java index fbe8c3e..98745cd 100644 --- a/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java +++ b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseLabeledWeightedEdge.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.model; +package org.apache.commons.graph.model.labeled; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/test/java/org/apache/commons/graph/model/BaseWeightedEdge.java b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseWeightedEdge.java similarity index 95% rename from src/test/java/org/apache/commons/graph/model/BaseWeightedEdge.java rename to model/src/main/java/org/apache/commons/graph/model/labeled/BaseWeightedEdge.java index 4571d8f..74f7355 100644 --- a/src/test/java/org/apache/commons/graph/model/BaseWeightedEdge.java +++ b/model/src/main/java/org/apache/commons/graph/model/labeled/BaseWeightedEdge.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.model; +package org.apache.commons.graph.model.labeled; /* * Licensed to the Apache Software Foundation (ASF) under one
diff --git a/src/main/java/org/apache/commons/graph/model/package-info.java b/model/src/main/java/org/apache/commons/graph/model/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/model/package-info.java rename to model/src/main/java/org/apache/commons/graph/model/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/builder/GraphBuilderTestCase.java b/model/src/test/java/org/apache/commons/graph/builder/GraphBuilderTestCase.java similarity index 94% rename from src/test/java/org/apache/commons/graph/builder/GraphBuilderTestCase.java rename to model/src/test/java/org/apache/commons/graph/builder/GraphBuilderTestCase.java index cfe9cd0..f34193d 100644 --- a/src/test/java/org/apache/commons/graph/builder/GraphBuilderTestCase.java +++ b/model/src/test/java/org/apache/commons/graph/builder/GraphBuilderTestCase.java
@@ -19,12 +19,12 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newUndirectedMutableGraph; import static org.junit.Assert.assertEquals; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; public final class GraphBuilderTestCase
diff --git a/src/test/java/org/apache/commons/graph/model/BaseMutableGraphTestCase.java b/model/src/test/java/org/apache/commons/graph/model/BaseMutableGraphTestCase.java similarity index 90% rename from src/test/java/org/apache/commons/graph/model/BaseMutableGraphTestCase.java rename to model/src/test/java/org/apache/commons/graph/model/BaseMutableGraphTestCase.java index df9eff1..c5085b0 100644 --- a/src/test/java/org/apache/commons/graph/model/BaseMutableGraphTestCase.java +++ b/model/src/test/java/org/apache/commons/graph/model/BaseMutableGraphTestCase.java
@@ -19,8 +19,9 @@ * under the License. */ +import static java.lang.String.format; import static java.lang.String.valueOf; -import static org.apache.commons.graph.utils.GraphUtils.buildCompleteGraph; +import static org.apache.commons.graph.Graphs.synchronize; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNotNull; @@ -30,11 +31,10 @@ import java.util.ArrayList; import java.util.List; -import org.apache.commons.graph.CommonsGraph; import org.apache.commons.graph.GraphException; import org.apache.commons.graph.MutableGraph; -import org.apache.commons.graph.utils.MultiThreadedTestRunner; -import org.apache.commons.graph.utils.TestRunner; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; import org.junit.Test; /** @@ -377,7 +377,7 @@ throws Throwable { final MutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = - (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) CommonsGraph.synchronize( (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ); + (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) synchronize( (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ); TestRunner tr1, tr2, tr3; tr1 = new GraphInsert( g, 0, 10 ); @@ -403,7 +403,7 @@ throws Throwable { final MutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = - (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) CommonsGraph.synchronize( (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) new DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ); + (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) synchronize( (MutableGraph<BaseLabeledVertex, BaseLabeledEdge>) new DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ); TestRunner tr1, tr2, tr3; tr1 = new GraphInsert( g, 0, 10 ); @@ -472,4 +472,39 @@ } } } + + /** + * Creates a complete graph with nVertices + * + * @param nVertices number of vertices + * @param g graph + */ + private static void buildCompleteGraph( int nVertices, BaseMutableGraph<BaseLabeledVertex, BaseLabeledEdge> g ) + { + // building Graph + for ( int i = 0; i < nVertices; i++ ) + { + BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) ); + g.addVertex( v ); + } + + for ( BaseLabeledVertex v1 : g.getVertices() ) + { + for ( BaseLabeledVertex v2 : g.getVertices() ) + { + if ( !v1.equals( v2 ) ) + { + try + { + g.addEdge( v1, new BaseLabeledEdge( format( "%s -> %s", v1, v2 ) ), v2 ); + } + catch ( GraphException e ) + { + // ignore + } + } + } + } + } + }
diff --git a/src/test/java/org/apache/commons/graph/model/GraphSerializationTestCase.java b/model/src/test/java/org/apache/commons/graph/model/GraphSerializationTestCase.java similarity index 82% rename from src/test/java/org/apache/commons/graph/model/GraphSerializationTestCase.java rename to model/src/test/java/org/apache/commons/graph/model/GraphSerializationTestCase.java index 76e4e60..0fc6b09 100644 --- a/src/test/java/org/apache/commons/graph/model/GraphSerializationTestCase.java +++ b/model/src/test/java/org/apache/commons/graph/model/GraphSerializationTestCase.java
@@ -20,10 +20,8 @@ */ import static junit.framework.Assert.assertEquals; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; -import static org.apache.commons.graph.CommonsGraph.populate; -import static org.apache.commons.graph.CommonsGraph.synchronize; +import static org.apache.commons.graph.Graphs.populate; +import static org.apache.commons.graph.Graphs.synchronize; import java.io.File; import java.io.FileInputStream; @@ -38,7 +36,11 @@ import org.apache.commons.graph.MutableGraph; import org.apache.commons.graph.builder.AbstractGraphConnection; import org.apache.commons.graph.builder.GraphConnection; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.After; import org.junit.Test; @@ -64,7 +66,9 @@ public void serializeUndirectedGraph() throws Exception { - MutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = newUndirectedMutableGraph( buildGraphConnections() ); + MutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ) + .withConnections( buildGraphConnections() ); checkSerialization( g ); } @@ -73,7 +77,9 @@ public void serializeDirectedGraph() throws Exception { - MutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = newDirectedMutableGraph( buildGraphConnections() ); + MutableGraph<BaseLabeledVertex, BaseLabeledEdge> g = + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>() ) + .withConnections( buildGraphConnections() ); checkSerialization( g ); } @@ -83,7 +89,8 @@ throws Exception { MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> g = - newUndirectedMutableGraph( buildWeightedGraphConnections() ); + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() ) + .withConnections( buildWeightedGraphConnections() ); checkSerialization( g ); } @@ -93,7 +100,8 @@ throws Exception { MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> g = - newDirectedMutableGraph( buildWeightedGraphConnections() ); + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() ) + .withConnections( buildWeightedGraphConnections() ); checkSerialization( g ); } @@ -103,8 +111,7 @@ throws Exception { final MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> spanningTree = - new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( - new DoubleWeightBaseOperations(), + new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( new DoubleWeightBaseOperations(), new BaseWeightedEdge<Double>() ); populate( spanningTree ).withConnections( buildWeightedGraphConnections() ); @@ -116,10 +123,11 @@ public void serializeSyncronyzedDirectedWeightdGraph() throws Exception { - Graph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> g = - synchronize( (MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>) newDirectedMutableGraph( buildWeightedGraphConnections() ) ); + MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> g = + populate( new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>() ) + .withConnections( buildWeightedGraphConnections() ); - checkSerialization( g ); + checkSerialization( synchronize( g ) ); } @Test
diff --git a/src/test/java/org/apache/commons/graph/utils/MultiThreadedTestRunner.java b/model/src/test/java/org/apache/commons/graph/model/MultiThreadedTestRunner.java similarity index 96% rename from src/test/java/org/apache/commons/graph/utils/MultiThreadedTestRunner.java rename to model/src/test/java/org/apache/commons/graph/model/MultiThreadedTestRunner.java index 6f175d4..bb3f0c1 100644 --- a/src/test/java/org/apache/commons/graph/utils/MultiThreadedTestRunner.java +++ b/model/src/test/java/org/apache/commons/graph/model/MultiThreadedTestRunner.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.utils; +package org.apache.commons.graph.model; import java.util.ArrayList; import java.util.List; @@ -28,11 +28,13 @@ */ public class MultiThreadedTestRunner { + final private List<Thread> th; + long maxWait = 60L * 60L * 1000; + final private List<Throwable> exeptions; - - + public MultiThreadedTestRunner( TestRunner[] runnables ) { th = new ArrayList<Thread>(); @@ -50,12 +52,12 @@ { t.start(); } - + for ( Thread t : th ) { t.join( maxWait ); } - + if ( this.exeptions.size() > 0 ) { throw this.exeptions.get( 0 ); @@ -69,4 +71,5 @@ { exeptions.add( e ); } + }
diff --git a/src/test/java/org/apache/commons/graph/utils/TestRunner.java b/model/src/test/java/org/apache/commons/graph/model/TestRunner.java similarity index 96% rename from src/test/java/org/apache/commons/graph/utils/TestRunner.java rename to model/src/test/java/org/apache/commons/graph/model/TestRunner.java index 187ffa2..9364875 100644 --- a/src/test/java/org/apache/commons/graph/utils/TestRunner.java +++ b/model/src/test/java/org/apache/commons/graph/model/TestRunner.java
@@ -1,4 +1,4 @@ -package org.apache.commons.graph.utils; +package org.apache.commons.graph.model; /* * Licensed to the Apache Software Foundation (ASF) under one @@ -21,11 +21,12 @@ /** * Abstract class. It's a generic multi-thread test case - * + * */ abstract public class TestRunner implements Runnable { + private MultiThreadedTestRunner runner; abstract public void runTest(); @@ -46,4 +47,5 @@ runner.addException( e ); } } + }
diff --git a/pom.xml b/pom.xml index 22ae238..300451b 100644 --- a/pom.xml +++ b/pom.xml
@@ -27,9 +27,9 @@ <groupId>org.apache.commons</groupId> <artifactId>commons-graph</artifactId> <version>0.1-SNAPSHOT</version> - <packaging>jar</packaging> + <packaging>pom</packaging> - <name>Apache Commons Graph</name> + <name>Apache Commons Graph - Parent</name> <description> The Apache Commons Graph package is a toolkit for managing graphs and graph based data structures. </description> @@ -116,6 +116,28 @@ </site> </distributionManagement> + <modules> + <!-- foundation libs --> + <module>api</module> + <module>model</module> + <!-- aux collections --> + <module>collections/disjoint-set</module> + <module>collections/fibonacci-heap</module> + <!-- algorithms --> + <module>coloring</module> + <module>connectivity</module> + <module>elo</module> + <module>flow</module> + <module>scc</module> + <module>shortestpath</module> + <module>spanning</module> + <module>visit</module> + <!-- graph format export --> + <module>export</module> + <!-- aux tests --> + <module>benchmarks</module> + </modules> + <properties> <maven.compile.source>1.5</maven.compile.source> <maven.compile.target>1.5</maven.compile.target> @@ -133,17 +155,6 @@ </dependencies> <build> - <resources> - <resource> - <directory>${basedir}</directory> - <targetPath>META-INF</targetPath> - <includes> - <include>NOTICE.txt</include> - <include>LICENSE.txt</include> - </includes> - </resource> - </resources> - <pluginManagement> <plugins> <!--This plugin's configuration is used to store Eclipse m2e settings only. It has no influence on the Maven build itself. --> @@ -192,48 +203,13 @@ <artifactId>maven-assembly-plugin</artifactId> <configuration> <descriptors> - <descriptor>src/main/assembly/bin.xml</descriptor> - <descriptor>src/main/assembly/src.xml</descriptor> + <descriptor>${basedir}/src/main/assembly/bin.xml</descriptor> + <descriptor>${basedir}/src/main/assembly/src.xml</descriptor> </descriptors> <tarLongFileMode>gnu</tarLongFileMode> + <runOnlyAtExecutionRoot>true</runOnlyAtExecutionRoot> </configuration> </plugin> - - <plugin> - <groupId>org.sonatype.plugins</groupId> - <artifactId>jarjar-maven-plugin</artifactId> - <version>1.5</version> - <configuration> - <input>{classes}</input> - <output>${project.build.directory}/classes</output> - <overwrite>true</overwrite> - <skipManifest>true</skipManifest> - <excludes> - <exclude>*:*</exclude> - </excludes> - <rules> - <rule> - <pattern>org.apache.commons.graph.**.Default*</pattern> - <result>org.apache.commons.graph.@1.$@2</result> - </rule> - <rule> - <pattern>org.apache.commons.graph.utils.*</pattern> - <result>org.apache.commons.graph.utils.$@1</result> - </rule> - <keep> - <pattern>org.apache.commons.graph.**</pattern> - </keep> - </rules> - </configuration> - <executions> - <execution> - <phase>prepare-package</phase> - <goals> - <goal>jarjar</goal> - </goals> - </execution> - </executions> - </plugin> </plugins> </build> @@ -295,74 +271,5 @@ </site> </distributionManagement> </profile> - - <profile> - <id>benchmarks</id> - <activation> - <property> - <name>skipBenchmarks</name> - <value>!true</value> - </property> - </activation> - - <dependencies> - <dependency> - <groupId>com.carrotsearch</groupId> - <artifactId>junit-benchmarks</artifactId> - <classifier>jdk15</classifier> - <version>0.3.0</version> - <scope>test</scope> - </dependency> - <dependency> - <groupId>org.slf4j</groupId> - <artifactId>slf4j-api</artifactId> - <version>1.6.1</version> - <scope>test</scope> - </dependency> - <dependency> - <groupId>com.h2database</groupId> - <artifactId>h2</artifactId> - <version>1.3.158</version> - <scope>test</scope> - </dependency> - </dependencies> - - <build> - <plugins> - <plugin> - <groupId>org.codehaus.mojo</groupId> - <artifactId>build-helper-maven-plugin</artifactId> - <version>1.7</version> - <executions> - <execution> - <id>add-test-source</id> - <phase>generate-test-sources</phase> - <goals> - <goal>add-test-source</goal> - </goals> - <configuration> - <sources> - <source>${basedir}/src/benchmarks/java</source> - </sources> - </configuration> - </execution> - </executions> - </plugin> - - <plugin> - <artifactId>maven-surefire-plugin</artifactId> - <configuration> - <systemPropertyVariables> - <jub.consumers>CONSOLE,XML,H2</jub.consumers> - <jub.db.file>${project.build.directory}/benchmarks/database</jub.db.file> - <jub.xml.file>${project.build.directory}/benchmarks.xml</jub.xml.file> - <jub.charts.dir>${project.build.directory}/site</jub.charts.dir> - </systemPropertyVariables> - <argLine>-Xmx512m -Xms512m</argLine> - </configuration> - </plugin> - </plugins> - </build> - </profile> </profiles> </project>
diff --git a/scc/pom.xml b/scc/pom.xml new file mode 100644 index 0000000..56a31d6 --- /dev/null +++ b/scc/pom.xml
@@ -0,0 +1,61 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-scc</artifactId> + + <name>Apache Commons Graph - SCC</name> + <description>Graph strongly connected component problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <!-- test dependencies --> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + <scope>test</scope> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java b/scc/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java rename to scc/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java
diff --git a/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java b/scc/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java rename to scc/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
diff --git a/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java b/scc/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java similarity index 99% rename from src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java rename to scc/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java index e808d4a..dfda8ac 100644 --- a/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java +++ b/scc/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java
@@ -31,7 +31,7 @@ import java.util.Set; import org.apache.commons.graph.DirectedGraph; -import org.apache.commons.graph.model.RevertedGraph; +import org.apache.commons.graph.RevertedGraph; /** * Implements the classical Kosaraju's algorithm to find the strongly connected components
diff --git a/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java b/scc/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java rename to scc/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java
diff --git a/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java b/scc/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java rename to scc/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java
diff --git a/scc/src/main/java/org/apache/commons/graph/scc/SccSolver.java b/scc/src/main/java/org/apache/commons/graph/scc/SccSolver.java new file mode 100644 index 0000000..59793c1 --- /dev/null +++ b/scc/src/main/java/org/apache/commons/graph/scc/SccSolver.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.scc; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.DirectedGraph; + +public final class SccSolver +{ + + /** + * Calculates the input graph Strongly Connected Component. + * + * @param <V> the Graph vertices type. + * @param <E> the Graph edges type. + * @param <G> the directed graph type + * @param graph the Graph which strongly connected component has to be verified. + * @return the SCC algoritm selector + */ + public static <V, E, G extends DirectedGraph<V, E>> SccAlgorithmSelector<V, E> findStronglyConnectedComponent( G graph ) + { + graph = checkNotNull( graph, "Strongly Connected Component cannot be calculated from a null graph" ); + return new DefaultSccAlgorithmSelector<V, E>( graph ); + } + + private SccSolver() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java b/scc/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java rename to scc/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java
diff --git a/src/main/java/org/apache/commons/graph/scc/TarjanVertexMetaInfo.java b/scc/src/main/java/org/apache/commons/graph/scc/TarjanVertexMetaInfo.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/TarjanVertexMetaInfo.java rename to scc/src/main/java/org/apache/commons/graph/scc/TarjanVertexMetaInfo.java
diff --git a/src/main/java/org/apache/commons/graph/scc/package-info.java b/scc/src/main/java/org/apache/commons/graph/scc/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/scc/package-info.java rename to scc/src/main/java/org/apache/commons/graph/scc/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java b/scc/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java similarity index 93% rename from src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java rename to scc/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java index b031645..2612ba7 100644 --- a/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java +++ b/scc/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java
@@ -19,8 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; +import static org.apache.commons.graph.scc.SccSolver.findStronglyConnectedComponent; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; @@ -29,10 +29,10 @@ import java.util.Set; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; /**
diff --git a/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java b/scc/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java similarity index 95% rename from src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java rename to scc/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java index 08ad604..2a81cb8 100644 --- a/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java +++ b/scc/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java
@@ -19,8 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; +import static org.apache.commons.graph.scc.SccSolver.findStronglyConnectedComponent; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; @@ -29,10 +29,10 @@ import java.util.Set; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; /**
diff --git a/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java b/scc/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java similarity index 93% rename from src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java rename to scc/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java index 26edc37..d9fe121 100644 --- a/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java +++ b/scc/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
@@ -19,8 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; +import static org.apache.commons.graph.scc.SccSolver.findStronglyConnectedComponent; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; @@ -29,10 +29,10 @@ import java.util.Set; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; import org.junit.Test; /**
diff --git a/shortestpath/pom.xml b/shortestpath/pom.xml new file mode 100644 index 0000000..d275ba1 --- /dev/null +++ b/shortestpath/pom.xml
@@ -0,0 +1,52 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-shortestpath</artifactId> + + <name>Apache Commons Graph - Shortest Path</name> + <description>Graph shortest paths problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-fibonacciheap</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + </dependency> + </dependencies> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java similarity index 97% rename from src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java index 82c66c8..0fa8578 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
@@ -26,7 +26,8 @@ import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PathNotFoundException; /** * Represents all shortest paths between all vertex pairs calculated by {@link FloydWarshall} algorithm.
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java similarity index 96% rename from src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java index 9456d0c..611b252 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
@@ -30,7 +30,9 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.WeightedPath; import org.apache.commons.graph.collections.FibonacciHeap; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PathNotFoundException; +import org.apache.commons.graph.model.PredecessorsList; final class DefaultHeuristicBuilder<V, WE, W> implements HeuristicBuilder<V, WE, W>
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java similarity index 97% rename from src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java index c7acc18..986888b 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
@@ -25,11 +25,12 @@ import java.util.Map; import org.apache.commons.graph.Graph; +import org.apache.commons.graph.Mapper; import org.apache.commons.graph.UndirectedGraph; import org.apache.commons.graph.VertexPair; -import org.apache.commons.graph.Mapper; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PredecessorsList; final class DefaultPathSourceSelector<V, WE, W> implements PathSourceSelector<V, WE, W>
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java similarity index 97% rename from src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java index e21e4d9..c23ae30 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
@@ -24,13 +24,15 @@ import java.util.HashSet; import java.util.Queue; import java.util.Set; -import org.apache.commons.graph.DirectedGraph; +import org.apache.commons.graph.DirectedGraph; import org.apache.commons.graph.Graph; import org.apache.commons.graph.Mapper; import org.apache.commons.graph.WeightedPath; import org.apache.commons.graph.collections.FibonacciHeap; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PathNotFoundException; +import org.apache.commons.graph.model.PredecessorsList; final class DefaultShortestPathAlgorithmSelector<V, WE, W> implements ShortestPathAlgorithmSelector<V, WE, W>
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java similarity index 96% rename from src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java index 21fd8be..dd8b33c 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
@@ -22,10 +22,12 @@ import static org.apache.commons.graph.utils.Assertions.checkNotNull; import org.apache.commons.graph.Graph; -import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.Mapper; +import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PathNotFoundException; +import org.apache.commons.graph.model.PredecessorsList; final class DefaultTargetSourceSelector<V, WE, W> implements TargetSourceSelector<V, WE, W>
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java similarity index 100% rename from src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/NegativeWeightedCycleException.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/NegativeWeightedCycleException.java similarity index 100% rename from src/main/java/org/apache/commons/graph/shortestpath/NegativeWeightedCycleException.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/NegativeWeightedCycleException.java
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java similarity index 96% rename from src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java index 6b89908..d6486df 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java
@@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** *
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java similarity index 97% rename from src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java index dfa4abb..c67df77 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
@@ -23,7 +23,7 @@ import java.util.HashMap; import java.util.Map; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * Stores and compares Graph Vertices weights.
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java similarity index 94% rename from src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java index c84ab90..20b73b4 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java
@@ -20,7 +20,8 @@ */ import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.model.PathNotFoundException; /** *
diff --git a/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathSolver.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathSolver.java new file mode 100644 index 0000000..f686206 --- /dev/null +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathSolver.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.shortestpath; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.Graph; + +public final class ShortestPathSolver +{ + + /** + * Find the sortest on the input {@link Graph} + * + * @param <V> the Graph vertices type + * @param <WE> the Graph edges type + * @param <G> the Graph type + * @param graph the input edge-weighted graph + * @return the caluculated the sortest + */ + public static <V, WE, G extends Graph<V, WE>> PathWeightedEdgesBuilder<V, WE> findShortestPath( G graph ) + { + graph = checkNotNull( graph, "Shortest path can not be calculated on null graph" ); + return new DefaultWeightedEdgesSelector<V, WE>( graph ); + } + + private ShortestPathSolver() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java similarity index 96% rename from src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java index 6f4509b..9292107 100644 --- a/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java +++ b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java
@@ -19,7 +19,7 @@ * under the License. */ -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** *
diff --git a/src/main/java/org/apache/commons/graph/shortestpath/package-info.java b/shortestpath/src/main/java/org/apache/commons/graph/shortestpath/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/shortestpath/package-info.java rename to shortestpath/src/main/java/org/apache/commons/graph/shortestpath/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java similarity index 95% rename from src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java rename to shortestpath/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java index ed996da..6a0fd29 100644 --- a/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java +++ b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
@@ -19,8 +19,8 @@ * under the License. */ +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; import static org.junit.Assert.assertEquals; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; import static org.junit.Assert.fail; import java.util.HashMap; @@ -28,12 +28,13 @@ import org.apache.commons.graph.Graph; import org.apache.commons.graph.Path; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.InMemoryWeightedPath; +import org.apache.commons.graph.model.PathNotFoundException; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; public final class AStarTestCase
diff --git a/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java similarity index 94% rename from src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java rename to shortestpath/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java index f2d4797..db6e717 100644 --- a/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java +++ b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
@@ -19,19 +19,20 @@ * under the License. */ +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; import static org.junit.Assert.assertEquals; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; import static org.junit.Assert.fail; import org.apache.commons.graph.Graph; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.DirectedMutableGraph; import org.apache.commons.graph.model.InMemoryWeightedPath; +import org.apache.commons.graph.model.PathNotFoundException; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; public final class BellmannFordTestCase
diff --git a/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java similarity index 95% rename from src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java rename to shortestpath/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java index 662cef4..d122ade 100644 --- a/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java +++ b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java
@@ -19,40 +19,42 @@ * under the License. */ -import static org.junit.Assert.assertEquals; - -import org.apache.commons.graph.Graph; -import org.apache.commons.graph.Path; -import org.apache.commons.graph.model.InMemoryWeightedPath; - import static java.lang.String.format; import static java.lang.String.valueOf; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; -import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.apache.commons.graph.model.GraphUtils.newDirectedMutableGraph; +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; +import static org.junit.Assert.assertEquals; import java.util.ArrayList; import java.util.List; import java.util.Random; +import org.apache.commons.graph.Graph; import org.apache.commons.graph.GraphException; +import org.apache.commons.graph.Path; +import org.apache.commons.graph.WeightedPath; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; +import org.apache.commons.graph.math.monoid.OrderedMonoid; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.DirectedMutableGraph; +import org.apache.commons.graph.model.InMemoryWeightedPath; +import org.apache.commons.graph.model.PathNotFoundException; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.BeforeClass; import org.junit.Test; -import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.model.BaseWeightedEdge; -import org.apache.commons.graph.model.DirectedMutableGraph; -import org.apache.commons.graph.weight.OrderedMonoid; - public final class BidirDijkstraTestCase { + private static final int TIMES = 10; + private static final int NODES = 5000; + private static final int EDGES = 100000; + private static final double EPSILON = 1.0e-6; private static DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> graph;
diff --git a/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java similarity index 93% rename from src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java rename to shortestpath/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java index e0553fe..a81da66 100644 --- a/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java +++ b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
@@ -19,18 +19,19 @@ * under the License. */ +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; import static org.junit.Assert.assertEquals; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; import org.apache.commons.graph.Graph; import org.apache.commons.graph.Path; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.DirectedMutableGraph; import org.apache.commons.graph.model.InMemoryWeightedPath; +import org.apache.commons.graph.model.PathNotFoundException; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; public final class DijkstraTestCase
diff --git a/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java similarity index 94% rename from src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java rename to shortestpath/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java index 5d697ef..cc8f40d 100644 --- a/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java +++ b/shortestpath/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
@@ -20,21 +20,22 @@ */ import static junit.framework.Assert.assertEquals; +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; import static org.junit.Assert.assertFalse; import static org.junit.Assert.fail; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; import org.apache.commons.graph.Graph; import org.apache.commons.graph.MutableGraph; import org.apache.commons.graph.UndirectedGraph; import org.apache.commons.graph.WeightedPath; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.DirectedMutableGraph; import org.apache.commons.graph.model.InMemoryWeightedPath; +import org.apache.commons.graph.model.PathNotFoundException; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; /**
diff --git a/spanning/pom.xml b/spanning/pom.xml new file mode 100644 index 0000000..84ded87 --- /dev/null +++ b/spanning/pom.xml
@@ -0,0 +1,77 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-spanning</artifactId> + + <name>Apache Commons Graph - Spanning</name> + <description>Graph spanning tree problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-disjointset</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-fibonacciheap</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-shortestpath</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java b/spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java similarity index 99% rename from src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java index cae45cb..805c7ff 100644 --- a/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java +++ b/spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
@@ -36,8 +36,8 @@ import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.collections.DisjointSet; import org.apache.commons.graph.collections.FibonacciHeap; +import org.apache.commons.graph.math.monoid.OrderedMonoid; import org.apache.commons.graph.model.MutableSpanningTree; -import org.apache.commons.graph.weight.OrderedMonoid; /** * {@link SpanningTreeAlgorithmSelector} implementation.
diff --git a/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java b/spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java similarity index 95% rename from src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java index 82078c9..912964d 100644 --- a/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java +++ b/spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
@@ -20,7 +20,7 @@ */ import static java.util.Collections.reverseOrder; -import static org.apache.commons.graph.CommonsGraph.findShortestPath; +import static org.apache.commons.graph.shortestpath.ShortestPathSolver.findShortestPath; import static org.apache.commons.graph.utils.Assertions.checkNotNull; import static org.apache.commons.graph.utils.Assertions.checkState; @@ -33,9 +33,9 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.SpanningTree; import org.apache.commons.graph.VertexPair; +import org.apache.commons.graph.math.monoid.OrderedMonoid; import org.apache.commons.graph.model.MutableSpanningTree; -import org.apache.commons.graph.shortestpath.PathNotFoundException; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.model.PathNotFoundException; /** * {@link SpanningTreeSourceSelector} implementation. @@ -82,7 +82,6 @@ */ public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations ) { - checkNotNull( weightOperations, "The Reverse-Delete algorithm cannot be calulated with null weight operations" ); final Queue<WE> sortedEdge = new PriorityQueue<WE>( 11, reverseOrder( new WeightedEdgesComparator<W, WE>( weightOperations, weightedEdges ) ) );
diff --git a/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningWeightedEdgeMapperBuilder.java b/spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningWeightedEdgeMapperBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/spanning/DefaultSpanningWeightedEdgeMapperBuilder.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningWeightedEdgeMapperBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java b/spanning/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java similarity index 100% rename from src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
diff --git a/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java b/spanning/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java similarity index 98% rename from src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java index 3ef03a7..abbd4ed 100644 --- a/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java +++ b/spanning/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
@@ -28,8 +28,8 @@ import org.apache.commons.graph.Mapper; import org.apache.commons.graph.SpanningTree; import org.apache.commons.graph.VertexPair; +import org.apache.commons.graph.math.monoid.OrderedMonoid; import org.apache.commons.graph.model.MutableSpanningTree; -import org.apache.commons.graph.weight.OrderedMonoid; /** * The predecessor list is a list of vertex of a {@link org.apache.commons.graph.Graph}.
diff --git a/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java similarity index 97% rename from src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java index 3432313..3e8a8a6 100644 --- a/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java +++ b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java
@@ -20,7 +20,7 @@ */ import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * Spanning Tree algoritms selector.
diff --git a/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSolver.java b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSolver.java new file mode 100644 index 0000000..51338f7 --- /dev/null +++ b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSolver.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.spanning; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.Graph; + +public final class SpanningTreeSolver +{ + + /** + * Find the minimum spanning tree on the input {@link Graph} + * + * @param <V> the Graph vertices type + * @param <WE> the Graph edges type + * @param <G> the Graph type + * @param graph the input edge-weighted graph + * @return the caluculated minimun spanning tree + */ + public static <V, WE, G extends Graph<V, WE>> SpanningWeightedEdgeMapperBuilder<V, WE> minimumSpanningTree( G graph ) + { + graph = checkNotNull( graph, "Minimum spanning tree can not be calculated on null graph" ); + return new DefaultSpanningWeightedEdgeMapperBuilder<V, WE>( graph ); + } + + private SpanningTreeSolver() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java similarity index 97% rename from src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java index 1cd5468..d3fe5c6 100644 --- a/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java +++ b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java
@@ -20,7 +20,7 @@ */ import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.weight.OrderedMonoid; +import org.apache.commons.graph.math.monoid.OrderedMonoid; /** * Spanning Tree source selector.
diff --git a/src/main/java/org/apache/commons/graph/spanning/SpanningWeightedEdgeMapperBuilder.java b/spanning/src/main/java/org/apache/commons/graph/spanning/SpanningWeightedEdgeMapperBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/spanning/SpanningWeightedEdgeMapperBuilder.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/SpanningWeightedEdgeMapperBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java b/spanning/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java similarity index 100% rename from src/main/java/org/apache/commons/graph/spanning/SuperVertex.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
diff --git a/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java b/spanning/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java similarity index 100% rename from src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
diff --git a/src/main/java/org/apache/commons/graph/spanning/package-info.java b/spanning/src/main/java/org/apache/commons/graph/spanning/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/spanning/package-info.java rename to spanning/src/main/java/org/apache/commons/graph/spanning/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java b/spanning/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java similarity index 95% rename from src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java rename to spanning/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java index 433fe1f..7fc1a6b 100644 --- a/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java +++ b/spanning/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
@@ -19,18 +19,18 @@ * under the License. */ +import static org.apache.commons.graph.spanning.SpanningTreeSolver.minimumSpanningTree; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree; import org.apache.commons.graph.Graph; import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.MutableSpanningTree; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; public final class BoruvkaTestCase
diff --git a/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java b/spanning/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java similarity index 95% rename from src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java rename to spanning/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java index 4433c09..d716d5a 100644 --- a/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java +++ b/spanning/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
@@ -19,18 +19,18 @@ * under the License. */ +import static org.apache.commons.graph.spanning.SpanningTreeSolver.minimumSpanningTree; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree; import org.apache.commons.graph.Graph; import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.MutableSpanningTree; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; public final class KruskalTestCase
diff --git a/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java b/spanning/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java similarity index 96% rename from src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java rename to spanning/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java index 1cdb53f..101bf9d 100644 --- a/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java +++ b/spanning/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
@@ -19,18 +19,18 @@ * under the License. */ +import static org.apache.commons.graph.spanning.SpanningTreeSolver.minimumSpanningTree; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree; import org.apache.commons.graph.Graph; import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.MutableSpanningTree; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; public final class PrimTestCase
diff --git a/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java b/spanning/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java similarity index 96% rename from src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java rename to spanning/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java index 5f6c9b1..35a1409 100644 --- a/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java +++ b/spanning/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
@@ -19,17 +19,17 @@ * under the License. */ +import static org.apache.commons.graph.spanning.SpanningTreeSolver.minimumSpanningTree; import static org.junit.Assert.assertEquals; -import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree; import org.apache.commons.graph.Graph; import org.apache.commons.graph.SpanningTree; -import org.apache.commons.graph.model.BaseLabeledVertex; -import org.apache.commons.graph.model.BaseLabeledWeightedEdge; -import org.apache.commons.graph.model.BaseWeightedEdge; +import org.apache.commons.graph.math.monoid.primitive.DoubleWeightBaseOperations; import org.apache.commons.graph.model.MutableSpanningTree; import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; +import org.apache.commons.graph.model.labeled.BaseLabeledWeightedEdge; +import org.apache.commons.graph.model.labeled.BaseWeightedEdge; import org.junit.Test; /**
diff --git a/src/main/java/org/apache/commons/graph/CommonsGraph.java b/src/main/java/org/apache/commons/graph/CommonsGraph.java deleted file mode 100644 index ef460d8..0000000 --- a/src/main/java/org/apache/commons/graph/CommonsGraph.java +++ /dev/null
@@ -1,356 +0,0 @@ -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 org.apache.commons.graph.utils.Assertions.checkNotNull; - -import org.apache.commons.graph.builder.DefaultLinkedConnectionBuilder; -import org.apache.commons.graph.builder.GraphConnection; -import org.apache.commons.graph.builder.LinkedConnectionBuilder; -import org.apache.commons.graph.coloring.ColorsBuilder; -import org.apache.commons.graph.coloring.DefaultColorsBuilder; -import org.apache.commons.graph.connectivity.ConnectivityBuilder; -import org.apache.commons.graph.connectivity.DefaultConnectivityBuilder; -import org.apache.commons.graph.elo.DefaultRankingSelector; -import org.apache.commons.graph.elo.GameResult; -import org.apache.commons.graph.elo.RankingSelector; -import org.apache.commons.graph.export.DefaultExportSelector; -import org.apache.commons.graph.export.NamedExportSelector; -import org.apache.commons.graph.flow.DefaultFlowWeightedEdgesBuilder; -import org.apache.commons.graph.flow.FlowWeightedEdgesBuilder; -import org.apache.commons.graph.model.DirectedMutableGraph; -import org.apache.commons.graph.model.UndirectedMutableGraph; -import org.apache.commons.graph.scc.DefaultSccAlgorithmSelector; -import org.apache.commons.graph.scc.SccAlgorithmSelector; -import org.apache.commons.graph.shortestpath.DefaultWeightedEdgesSelector; -import org.apache.commons.graph.shortestpath.PathWeightedEdgesBuilder; -import org.apache.commons.graph.spanning.DefaultSpanningWeightedEdgeMapperBuilder; -import org.apache.commons.graph.spanning.SpanningWeightedEdgeMapperBuilder; -import org.apache.commons.graph.visit.DefaultVisitSourceSelector; -import org.apache.commons.graph.visit.VisitSourceSelector; - -/** - * The Apache Commons Graph package is a toolkit for managing graphs and graph based data structures. - */ -public final class CommonsGraph -{ - - /** - * Export the graph in DOT or GraphML format. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param <G> the Graph type - * @param graph the input graph - * @return an instance of {@link NamedExportSelector} - */ - public static <V, E, G extends Graph<V, E>> NamedExportSelector<V, E> export( G graph ) - { - graph = checkNotNull( graph, "Null graph can not be exported" ); - return new DefaultExportSelector<V, E>( graph ); - } - - /** - * Create a color builder. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param <G> the Graph type - * @param graph the input graph - * @return an instance of {@link ColorsBuilder} - */ - public static <V, E, G extends UndirectedGraph<V, E>> ColorsBuilder<V, E> coloring( G graph ) - { - graph = checkNotNull( graph, "Coloring can not be calculated on null graph" ); - return new DefaultColorsBuilder<V, E>( graph ); - } - - /** - * Find the maximum flow on the input {@link Graph}. - * - * @param <V> the Graph vertices type - * @param <WE> the Graph edges type - * @param <G> the Graph type - * @param graph the input edge-weighted graph - * @return an instance of {@link FlowWeightedEdgesBuilder} - */ - public static <V, WE, G extends DirectedGraph<V, WE>> FlowWeightedEdgesBuilder<V, WE> findMaxFlow( G graph ) - { - graph = checkNotNull( graph, "Max flow can not be calculated on null graph" ); - return new DefaultFlowWeightedEdgesBuilder<V, WE>( graph ); - } - - /** - * Find the minimum spanning tree on the input {@link Graph} - * - * @param <V> the Graph vertices type - * @param <WE> the Graph edges type - * @param <G> the Graph type - * @param graph the input edge-weighted graph - * @return the caluculated minimun spanning tree - */ - public static <V, WE, G extends Graph<V, WE>> SpanningWeightedEdgeMapperBuilder<V, WE> minimumSpanningTree( G graph ) - { - graph = checkNotNull( graph, "Minimum spanning tree can not be calculated on null graph" ); - return new DefaultSpanningWeightedEdgeMapperBuilder<V, WE>( graph ); - } - - /** - * Find the sortest on the input {@link Graph} - * - * @param <V> the Graph vertices type - * @param <WE> the Graph edges type - * @param <G> the Graph type - * @param graph the input edge-weighted graph - * @return the caluculated the sortest - */ - public static <V, WE, G extends Graph<V, WE>> PathWeightedEdgesBuilder<V, WE> findShortestPath( G graph ) - { - graph = checkNotNull( graph, "Shortest path can not be calculated on null graph" ); - return new DefaultWeightedEdgesSelector<V, WE>( graph ); - } - - /** - * Calculates the input graph Strongly Connected Component. - * - * @param <V> the Graph vertices type. - * @param <E> the Graph edges type. - * @param <G> the directed graph type - * @param graph the Graph which strongly connected component has to be verified. - * @return the SCC algoritm selector - */ - public static <V, E, G extends DirectedGraph<V, E>> SccAlgorithmSelector<V, E> findStronglyConnectedComponent( G graph ) - { - graph = checkNotNull( graph, "Strongly Connected Component cannot be calculated from a null graph" ); - return new DefaultSccAlgorithmSelector<V, E>( graph ); - } - - /** - * Calculates the input graph Connected Component. - * - * @param <V> the Graph vertices type. - * @param <E> the Graph edges type. - * @param <G> the directed graph type - * @param graph the Graph which connected component has to be verified. - * @return the Connectivity algorithm builder - */ - public static <V, E, G extends Graph<V, E>> ConnectivityBuilder<V, E> findConnectedComponent( G graph ) - { - graph = checkNotNull( graph, "Connected Component cannot be calculated from a null graph" ); - return new DefaultConnectivityBuilder<V, E>( graph ); - } - - /** - * Allows select a series of algorithms to apply on input graph. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param <G> the Graph type - * @param graph the Graph instance to apply graph algorithms - * @return the graph algorithms selector - */ - public static <V, E, G extends Graph<V, E>> VisitSourceSelector<V, E, G> visit( G graph ) - { - graph = checkNotNull( graph, "No algorithm can be applied on null graph!" ); - return new DefaultVisitSourceSelector<V, E, G>( graph ); - } - - /** - * Ranks the players (vertices) that took part in a tournament (graph) depending on the game results (edges), - * applying the <a href="http://en.wikipedia.org/wiki/Elo_rating_system.">Elo Rating System</a>. - * - * @param <P> the players involved in the tournament - * @param <TG> the Tournament Graph type - * @param tournamentGraph the graph representing the tournament - * @return the builder for the functor which returns/update the players ranking - */ - public static <P, TG extends DirectedGraph<P, GameResult>> RankingSelector<P> eloRate( TG tournamentGraph ) - { - tournamentGraph = checkNotNull( tournamentGraph, "ELO ranking can not be applied on null graph!" ); - return new DefaultRankingSelector<P>( tournamentGraph ); - } - - /** - * Creates a new {@link DirectedMutableGraph} instance where vertices - * are connected as described in the input {@link GraphConnection} instance. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param graphConnection the {@link GraphConnection} instance that describes vertices - * @return a new {@link DirectedMutableGraph} instance - */ - public static <V, E> DirectedMutableGraph<V, E> newDirectedMutableGraph( GraphConnection<V, E> graphConnection ) - { - return populate( new DirectedMutableGraph<V, E>() ).withConnections( graphConnection ); - } - - /** - * Creates a new {@link UndirectedMutableGraph} instance where vertices - * are connected as described in the input {@link GraphConnection} instance. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param graphConnection the {@link GraphConnection} instance that describes vertices - * @return a new {@link UndirectedMutableGraph} instance - */ - public static <V, E> UndirectedMutableGraph<V, E> newUndirectedMutableGraph( GraphConnection<V, E> graphConnection ) - { - return populate( new UndirectedMutableGraph<V, E>() ).withConnections( graphConnection ); - } - - /** - * Allows populate the given {@link MutableGraph}. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param <G> the Graph type - * @param graph the graph has to be populated - * @return the builder to configure vertices connection - */ - public static <V, E, G extends MutableGraph<V, E>> LinkedConnectionBuilder<V, E, G> populate( G graph ) - { - return new DefaultLinkedConnectionBuilder<V, E, G>( checkNotNull( graph, "Impossible to configure null graph!" ) ); - } - - /** - * Returns a synchronized (thread-safe) {@link Graph} backed by the specified Graph. - * - * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: - * <pre> - * Graph syncGraph = synchronize( graph ); - * ... - * synchronized(syncGraph) { - * for ( Vertex v : g.getVertices() ) // Must be in synchronized block - * { - * foo( v ) - * } - * } - * </pre> - * - * Failure to follow this advice may result in non-deterministic behavior. - * - * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param graph the input {@link Graph} - * @return the syncronyzed graph - */ - public static <V, E> Graph<V, E> synchronize( Graph<V, E> graph ) - { - return new SynchronizedGraph<V, E>( graph ); - } - - /** - * Returns a synchronized (thread-safe) {@link DirectedGraph} backed by the specified Graph. - * - * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: - * <pre> - * Graph syncGraph = synchronize( graph ); - * ... - * synchronized(syncGraph) { - * for ( Vertex v : g.getVertices() ) // Must be in synchronized block - * { - * foo( v ) - * } - * } - * </pre> - * - * Failure to follow this advice may result in non-deterministic behavior. - * - * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param graph the input {@link Graph} - * @return the syncronyzed graph - */ - public static <V, E> Graph<V, E> synchronize( DirectedGraph<V, E> graph ) - { - return new SynchronizedDirectedGraph<V, E>( graph ); - } - - /** - * Returns a synchronized (thread-safe) {@link UndirectedGraph} backed by the specified Graph. - * - * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: - * <pre> - * Graph syncGraph = synchronize( graph ); - * ... - * synchronized(syncGraph) { - * for ( Vertex v : g.getVertices() ) // Must be in synchronized block - * { - * foo( v ) - * } - * } - * </pre> - * - * Failure to follow this advice may result in non-deterministic behavior. - * - * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param graph the input {@link Graph} - * @return the syncronyzed graph - */ - public static <V, E> Graph<V, E> synchronize( UndirectedGraph<V, E> graph ) - { - return new SynchronizedUndirectedGraph<V, E>( graph ); - } - - /** - * Returns a synchronized (thread-safe) {@link MutableGraph} backed by the specified Graph. - * - * It is imperative that the user manually synchronize on the returned graph when iterating over iterable collections: - * <pre> - * Graph syncGraph = synchronize( graph ); - * ... - * synchronized(syncGraph) { - * for ( Vertex v : g.getVertices() ) // Must be in synchronized block - * { - * foo( v ) - * } - * } - * </pre> - * - * Failure to follow this advice may result in non-deterministic behavior. - * - * The returned {@link Graph} will be serializable if the specified {@link Graph} is serializable. - * - * @param <V> the Graph vertices type - * @param <E> the Graph edges type - * @param graph the input {@link Graph} - * @return the synchronized graph - */ - public static <V, E> Graph<V, E> synchronize( MutableGraph<V, E> graph ) - { - return new SynchronizedMutableGraph<V, E>( graph ); - } - - /** - * Hidden constructor, this class cannot be instantiated. - */ - private CommonsGraph() - { - // do nothing - } - -}
diff --git a/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java b/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java deleted file mode 100644 index 7c642ae..0000000 --- a/src/test/java/org/apache/commons/graph/coloring/AbstractColoringTest.java +++ /dev/null
@@ -1,95 +0,0 @@ -package org.apache.commons.graph.coloring; - -/* - * 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 org.junit.Assert.assertNotNull; -import static org.junit.Assert.assertTrue; - -import java.util.HashMap; -import java.util.HashSet; -import java.util.Map; -import java.util.Random; -import java.util.Set; - -import org.apache.commons.graph.VertexPair; -import org.apache.commons.graph.model.UndirectedMutableGraph; - -/** - * Abstract class used for test coloring. - */ -abstract class AbstractColoringTest -{ - - AbstractColoringTest() - { - } - - /** - * Return a random association with index and a color string in RGB. - */ - protected Map<Integer, String> createColorMap( int numColor ) - { - Map<Integer, String> colorCodes = new HashMap<Integer, String>(); - for ( int i = 0; i < 100; i++ ) - { - Random rnd = new Random( i ); - colorCodes.put( i, String.format( "\"#%2x%2x%2x\"", rnd.nextInt( 255 ), rnd.nextInt( 255 ), rnd.nextInt( 255 ) ) ); - } - return colorCodes; - } - - /** - * Creates a list of integer colors. - * - * @param colorNumber number of colors - * @return the list. - */ - protected Set<Integer> createColorsList( int colorNumber ) - { - Set<Integer> colors = new HashSet<Integer>(); - for ( int j = 0; j < colorNumber; j++ ) - { - colors.add( j ); - } - return colors; - } - - /** - * This method checks if all connected vertices have different colors. - * - * @param g - * @param coloredVertices - */ - protected <V, E, C> void checkColoring( UndirectedMutableGraph<V, E> g, - ColoredVertices<V, C> coloredVertices ) - { - for ( E e : g.getEdges() ) - { - VertexPair<V> vp = g.getVertices( e ); - C h = coloredVertices.getColor( vp.getHead() ); - C t = coloredVertices.getColor( vp.getTail() ); - - assertNotNull( h ); - assertNotNull( t ); - assertTrue( !h.equals( t ) ); - } - } - -}
diff --git a/visit/pom.xml b/visit/pom.xml new file mode 100644 index 0000000..2ef7a8d --- /dev/null +++ b/visit/pom.xml
@@ -0,0 +1,59 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + 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. +--> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <parent> + <groupId>org.apache.commons</groupId> + <artifactId>commons-graph</artifactId> + <version>0.1-SNAPSHOT</version> + </parent> + + <artifactId>commons-graph-visit</artifactId> + + <name>Apache Commons Graph - Visit</name> + <description>Graph visit problem solver implementation.</description> + + <dependencies> + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-api</artifactId> + <version>${project.parent.version}</version> + </dependency> + + <dependency> + <groupId>${project.parent.groupId}</groupId> + <artifactId>commons-graph-model</artifactId> + <version>${project.parent.version}</version> + </dependency> + </dependencies> + + <build> + <resources> + <resource> + <directory>${basedir}/../</directory> + <targetPath>META-INF</targetPath> + <includes> + <include>NOTICE.txt</include> + <include>LICENSE.txt</include> + </includes> + </resource> + </resources> + </build> + +</project>
diff --git a/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java b/visit/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java rename to visit/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java
diff --git a/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java b/visit/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java rename to visit/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
diff --git a/src/main/java/org/apache/commons/graph/visit/DefaultVisitSourceSelector.java b/visit/src/main/java/org/apache/commons/graph/visit/DefaultVisitSourceSelector.java similarity index 95% rename from src/main/java/org/apache/commons/graph/visit/DefaultVisitSourceSelector.java rename to visit/src/main/java/org/apache/commons/graph/visit/DefaultVisitSourceSelector.java index d8a34e6..96b9f56 100644 --- a/src/main/java/org/apache/commons/graph/visit/DefaultVisitSourceSelector.java +++ b/visit/src/main/java/org/apache/commons/graph/visit/DefaultVisitSourceSelector.java
@@ -31,7 +31,7 @@ * @param <E> the Graph edges type * @param <G> the Graph type */ -public final class DefaultVisitSourceSelector<V, E, G extends Graph<V, E>> +final class DefaultVisitSourceSelector<V, E, G extends Graph<V, E>> implements VisitSourceSelector<V, E, G> {
diff --git a/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java b/visit/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java rename to visit/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java
diff --git a/visit/src/main/java/org/apache/commons/graph/visit/GraphVisitor.java b/visit/src/main/java/org/apache/commons/graph/visit/GraphVisitor.java new file mode 100644 index 0000000..9ddc35f --- /dev/null +++ b/visit/src/main/java/org/apache/commons/graph/visit/GraphVisitor.java
@@ -0,0 +1,49 @@ +package org.apache.commons.graph.visit; + +/* + * 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 org.apache.commons.graph.utils.Assertions.checkNotNull; + +import org.apache.commons.graph.Graph; + +public final class GraphVisitor +{ + + /** + * Allows select a series of algorithms to apply on input graph. + * + * @param <V> the Graph vertices type + * @param <E> the Graph edges type + * @param <G> the Graph type + * @param graph the Graph instance to apply graph algorithms + * @return the graph algorithms selector + */ + public static <V, E, G extends Graph<V, E>> VisitSourceSelector<V, E, G> visit( G graph ) + { + graph = checkNotNull( graph, "No algorithm can be applied on null graph!" ); + return new DefaultVisitSourceSelector<V, E, G>( graph ); + } + + private GraphVisitor() + { + // do nothing + } + +}
diff --git a/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java b/visit/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java rename to visit/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java
diff --git a/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java b/visit/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java rename to visit/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
diff --git a/src/main/java/org/apache/commons/graph/visit/VisitSourceSelector.java b/visit/src/main/java/org/apache/commons/graph/visit/VisitSourceSelector.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/VisitSourceSelector.java rename to visit/src/main/java/org/apache/commons/graph/visit/VisitSourceSelector.java
diff --git a/src/main/java/org/apache/commons/graph/visit/VisitState.java b/visit/src/main/java/org/apache/commons/graph/visit/VisitState.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/VisitState.java rename to visit/src/main/java/org/apache/commons/graph/visit/VisitState.java
diff --git a/src/main/java/org/apache/commons/graph/visit/package-info.java b/visit/src/main/java/org/apache/commons/graph/visit/package-info.java similarity index 100% rename from src/main/java/org/apache/commons/graph/visit/package-info.java rename to visit/src/main/java/org/apache/commons/graph/visit/package-info.java
diff --git a/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java b/visit/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java similarity index 92% rename from src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java rename to visit/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java index 80ba030..99c0518 100644 --- a/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java +++ b/visit/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
@@ -24,9 +24,9 @@ import java.util.ArrayList; import java.util.List; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; public final class NodeSequenceVisitor extends BaseGraphVisitHandler<BaseLabeledVertex, BaseLabeledEdge, UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>, List<BaseLabeledVertex>>
diff --git a/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java b/visit/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java similarity index 96% rename from src/test/java/org/apache/commons/graph/visit/VisitTestCase.java rename to visit/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java index ddbda74..962c850 100644 --- a/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java +++ b/visit/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java
@@ -19,8 +19,8 @@ * under the License. */ -import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph; -import static org.apache.commons.graph.CommonsGraph.visit; +import static org.apache.commons.graph.model.GraphUtils.newUndirectedMutableGraph; +import static org.apache.commons.graph.visit.GraphVisitor.visit; import static org.junit.Assert.assertEquals; import java.util.ArrayList; @@ -28,9 +28,9 @@ import org.apache.commons.graph.Graph; import org.apache.commons.graph.builder.AbstractGraphConnection; -import org.apache.commons.graph.model.BaseLabeledEdge; -import org.apache.commons.graph.model.BaseLabeledVertex; import org.apache.commons.graph.model.UndirectedMutableGraph; +import org.apache.commons.graph.model.labeled.BaseLabeledEdge; +import org.apache.commons.graph.model.labeled.BaseLabeledVertex; import org.junit.Test; public final class VisitTestCase