You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2012/01/31 12:00:30 UTC
svn commit: r1238390 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/
main/java/org/apache/commons/graph/connectivity/
test/java/org/apache/commons/graph/connectivity/
Author: simonetripodi
Date: Tue Jan 31 11:00:29 2012
New Revision: 1238390
URL: http://svn.apache.org/viewvc?rev=1238390&view=rev
Log:
[SANDBOX-375] Add Connected Components algorithms - patch submitted by Marco Speranza
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java (with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java (with props)
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1238390&r1=1238389&r2=1238390&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Tue Jan 31 11:00:29 2012
@@ -23,6 +23,9 @@
</properties>
<body>
<release version="0.1" date="201?-??-??" description="First release.">
+ <action dev="simonetripodi" type="fix" issue="SANDBOX-375" due-to="Marco Speranza">
+ Add Connected Components algorithms
+ </action>
<action dev="simonetripodi" type="fix" issue="SANDBOX-374" due-to="Marco Speranza">
Kruskal's algorithm doesn't accept sparse graph
</action>
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java?rev=1238390&r1=1238389&r2=1238390&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java Tue Jan 31 11:00:29 2012
@@ -26,6 +26,8 @@ import org.apache.commons.graph.builder.
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.export.DefaultToStreamBuilder;
import org.apache.commons.graph.export.ToStreamBuilder;
import org.apache.commons.graph.flow.DefaultFromHeadBuilder;
@@ -118,11 +120,26 @@ public final class CommonsGraph<V extend
*/
public static <V extends Vertex, E extends Edge, G extends DirectedGraph<V, E>> SccAlgorithmSelector<V, E, G> findStronglyConnectedComponent( G graph )
{
- graph = checkNotNull( graph, "Strongly Connected Component cannot be calculated from a nulla graph" );
+ graph = checkNotNull( graph, "Strongly Connected Component cannot be calculated from a null graph" );
return new DefaultSccAlgorithmSelector<V, E, G>( 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 extends Vertex, E extends Edge, G extends Graph<V, E>> ConnectivityBuilder<V, E, G> findConnectedComponent( G graph )
+ {
+ graph = checkNotNull( graph, "Connected Component cannot be calculated from a null graph" );
+ return new DefaultConnectivityBuilder<V, E, G>( graph );
+ }
+
+ /**
* Allows select a series of algorithms to apply on input graph.
*
* @param <V> the Graph vertices type
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,63 @@
+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 java.util.LinkedList;
+import java.util.List;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.visit.BaseGraphVisitHandler;
+
+final class ConnectedComponentHandler<V extends Vertex, E extends Edge, G extends Graph<V, E>>
+ extends BaseGraphVisitHandler<V, E, G, List<V>>
+{
+
+ private final List<V> touchedVertices = new LinkedList<V>();
+
+ private final List<V> untouchedVertices;
+
+ public ConnectedComponentHandler( List<V> untouchedVertices )
+ {
+ this.untouchedVertices = untouchedVertices;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean finishVertex( V vertex )
+ {
+ untouchedVertices.remove( vertex );
+ touchedVertices.add( vertex );
+ return false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public List<V> onCompleted()
+ {
+ return touchedVertices;
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,45 @@
+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 java.util.Collection;
+import java.util.List;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+
+/**
+ * Builder for selecting the connectivity algorithm to perform.
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
+ * @param <G> the Graph type
+ */
+public interface ConnectivityAlgorithmsSelector <V extends Vertex, E extends Edge, G extends Graph<V, E> >
+{
+
+ /**
+ * Find all connected Component for a specific graph.
+ *
+ * @return A collection of the disjointed sub-graphes
+ */
+ Collection<List<V>> applyingMinimumSpanningTreeAlgorithm();
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityAlgorithmsSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,51 @@
+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 org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+
+/**
+ * Builder to specify the set of vertices included into a connected component.
+ *
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
+ * @param <G> the Graph type
+ */
+public interface ConnectivityBuilder<V extends Vertex, E extends Edge, G extends Graph<V, E>>
+{
+
+ /**
+ * Specifies the set of vertices included into a connected component.
+ *
+ * @param vertices the set of vertices included into a connected component.
+ * @return the connectivity algorithm selector.
+ */
+ ConnectivityAlgorithmsSelector<V, E, G> includingVertices( V... vertices );
+
+ /**
+ * Find all the connected components included into the specified graph
+ *
+ * @return the connectivity algorithm selector.
+ */
+ ConnectivityAlgorithmsSelector<V, E, G> includingAllVertices();
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectivityBuilder.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,81 @@
+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 java.util.Arrays.asList;
+import static org.apache.commons.graph.CommonsGraph.visit;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+
+/**
+ *
+ */
+final class DefaultConnectivityAlgorithmsSelector<V extends Vertex, E extends Edge, G extends Graph<V, E>>
+ implements ConnectivityAlgorithmsSelector<V, E, G>
+{
+
+ final private G graph;
+
+ final private V[] includedVertices;
+
+ public DefaultConnectivityAlgorithmsSelector( G graph, V... vertices )
+ {
+ this.graph = graph;
+ this.includedVertices = vertices;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Collection<List<V>> applyingMinimumSpanningTreeAlgorithm()
+ {
+ final List<V> untouchedVertices = new ArrayList<V>();
+
+ if ( includedVertices != null )
+ {
+ untouchedVertices.addAll( asList( includedVertices ) );
+ }
+ else
+ {
+ for ( V v : graph.getVertices() )
+ {
+ untouchedVertices.add( v );
+ }
+ }
+
+ final Collection<List<V>> connectedVertices = new LinkedList<List<V>>();
+
+ while ( untouchedVertices.size() > 0 )
+ {
+ V source = untouchedVertices.remove( 0 );
+
+ connectedVertices.add( visit( graph ).from( source ).applyingDepthFirstSearch( new ConnectedComponentHandler<V, E, G>( untouchedVertices ) ) );
+ }
+ return connectedVertices;
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityAlgorithmsSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,55 @@
+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 org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+
+/**
+ *
+ */
+public class DefaultConnectivityBuilder<V extends Vertex, E extends Edge, G extends Graph<V, E>>
+ implements ConnectivityBuilder<V, E, G>
+{
+
+ private final G graph;
+
+ public DefaultConnectivityBuilder(G graph) {
+ this.graph = graph;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public ConnectivityAlgorithmsSelector<V, E, G> includingVertices( V... vertices )
+ {
+ return new DefaultConnectivityAlgorithmsSelector<V, E, G>( graph, vertices );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public ConnectivityAlgorithmsSelector<V, E, G> includingAllVertices()
+ {
+ return new DefaultConnectivityAlgorithmsSelector<V, E, G>( graph, (V[]) null );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/DefaultConnectivityBuilder.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,23 @@
+/**
+ * Graph connectivity algorithms implementation.
+ */
+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.
+ */
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/package-info.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java?rev=1238390&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java Tue Jan 31 11:00:29 2012
@@ -0,0 +1,209 @@
+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.CommonsGraph.findConnectedComponent;
+import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+
+import java.util.Collection;
+import java.util.List;
+
+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.junit.Test;
+
+/**
+ */
+public final class FindConnectedComponetTestCase
+{
+
+ @Test
+ public void verifyConnectedComponents()
+ {
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ public void connect()
+ {
+ addVertex( a );
+ addVertex( new BaseLabeledVertex( "B" ) );
+ addVertex( new BaseLabeledVertex( "C" ) );
+ addVertex( new BaseLabeledVertex( "D" ) );
+ addVertex( new BaseLabeledVertex( "E" ) );
+ addVertex( new BaseLabeledVertex( "F" ) );
+ addVertex( new BaseLabeledVertex( "G" ) );
+ addVertex( new BaseLabeledVertex( "H" ) );
+ }
+
+ } );
+
+ Collection<List<BaseLabeledVertex>> c = findConnectedComponent( graph ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
+
+ assertNotNull( c );
+ assertFalse( c.isEmpty() );
+ assertEquals( 8, c.size() );
+ }
+
+ @Test
+ public void verifyConnectedComponents2()
+ {
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ public void connect()
+ {
+ addVertex( a );
+ BaseLabeledVertex b = addVertex( new BaseLabeledVertex( "B" ) );
+ BaseLabeledVertex c = addVertex( new BaseLabeledVertex( "C" ) );
+ BaseLabeledVertex d = addVertex( new BaseLabeledVertex( "D" ) );
+ BaseLabeledVertex e = addVertex( new BaseLabeledVertex( "E" ) );
+ BaseLabeledVertex f = addVertex( new BaseLabeledVertex( "F" ) );
+ BaseLabeledVertex g = addVertex( new BaseLabeledVertex( "G" ) );
+ BaseLabeledVertex h = addVertex( new BaseLabeledVertex( "H" ) );
+
+ addEdge( new BaseLabeledEdge( "A -> F" ) ).from( a ).to( f );
+ addEdge( new BaseLabeledEdge( "A -> B" ) ).from( a ).to( b );
+ addEdge( new BaseLabeledEdge( "B -> F" ) ).from( b ).to( f );
+ addEdge( new BaseLabeledEdge( "C -> G" ) ).from( c ).to( g );
+ addEdge( new BaseLabeledEdge( "D -> G" ) ).from( d ).to( g );
+ addEdge( new BaseLabeledEdge( "E -> F" ) ).from( e ).to( f );
+ addEdge( new BaseLabeledEdge( "H -> C" ) ).from( h ).to( c );
+ }
+
+ } );
+
+ Collection<List<BaseLabeledVertex>> c = findConnectedComponent( graph ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
+
+ assertNotNull( c );
+ assertFalse( c.isEmpty() );
+ assertEquals( 2, c.size() );
+ }
+
+ @Test
+ public void verifyConnectedComponents3()
+ {
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ public void connect()
+ {
+ addVertex( a );
+ BaseLabeledVertex b = addVertex( new BaseLabeledVertex( "B" ) );
+ BaseLabeledVertex c = addVertex( new BaseLabeledVertex( "C" ) );
+
+ addEdge( new BaseLabeledEdge( "A -> B" ) ).from( a ).to( b );
+ addEdge( new BaseLabeledEdge( "B -> C" ) ).from( b ).to( c );
+ addEdge( new BaseLabeledEdge( "C -> A" ) ).from( c ).to( a );
+ }
+
+ } );
+
+ Collection<List<BaseLabeledVertex>> c = findConnectedComponent( graph ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
+
+ assertNotNull( c );
+ assertFalse( c.isEmpty() );
+ assertEquals( 1, c.size() );
+ }
+
+ @Test
+ public void verifyConnectedComponentsIncludingVertices()
+ {
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ public void connect()
+ {
+ addVertex( a );
+ BaseLabeledVertex b = addVertex( new BaseLabeledVertex( "B" ) );
+ BaseLabeledVertex c = addVertex( new BaseLabeledVertex( "C" ) );
+ BaseLabeledVertex d = addVertex( new BaseLabeledVertex( "D" ) );
+ BaseLabeledVertex e = addVertex( new BaseLabeledVertex( "E" ) );
+ BaseLabeledVertex f = addVertex( new BaseLabeledVertex( "F" ) );
+ BaseLabeledVertex g = addVertex( new BaseLabeledVertex( "G" ) );
+ BaseLabeledVertex h = addVertex( new BaseLabeledVertex( "H" ) );
+
+ addEdge( new BaseLabeledEdge( "A -> F" ) ).from( a ).to( f );
+ addEdge( new BaseLabeledEdge( "A -> B" ) ).from( a ).to( b );
+ addEdge( new BaseLabeledEdge( "B -> F" ) ).from( b ).to( f );
+ addEdge( new BaseLabeledEdge( "C -> G" ) ).from( c ).to( g );
+ addEdge( new BaseLabeledEdge( "D -> G" ) ).from( d ).to( g );
+ addEdge( new BaseLabeledEdge( "E -> F" ) ).from( e ).to( f );
+ addEdge( new BaseLabeledEdge( "H -> C" ) ).from( h ).to( c );
+ }
+
+ } );
+
+ Collection<List<BaseLabeledVertex>> coll = findConnectedComponent( graph ).includingVertices( a ).applyingMinimumSpanningTreeAlgorithm();
+
+ assertNotNull( coll );
+ assertFalse( coll.isEmpty() );
+ assertEquals( 1, coll.size() );
+ }
+
+ @Test
+ public void verifyConnectedComponentsIncludingVertices2()
+ {
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+ final BaseLabeledVertex e = new BaseLabeledVertex( "E" );
+
+ UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
+ newUndirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+
+ public void connect()
+ {
+ addVertex( a );
+ addVertex( new BaseLabeledVertex( "B" ) );
+ addVertex( new BaseLabeledVertex( "C" ) );
+ addVertex( new BaseLabeledVertex( "D" ) );
+ addVertex( e );
+ addVertex( new BaseLabeledVertex( "F" ) );
+ addVertex( new BaseLabeledVertex( "G" ) );
+ addVertex( new BaseLabeledVertex( "H" ) );
+
+ }
+
+ } );
+
+ Collection<List<BaseLabeledVertex>> coll = findConnectedComponent( graph ).includingVertices( a, e ).applyingMinimumSpanningTreeAlgorithm();
+
+ assertNotNull( coll );
+ assertFalse( coll.isEmpty() );
+ assertEquals( 2, coll.size() );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/connectivity/FindConnectedComponetTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain