commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject 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/
Date Tue, 31 Jan 2012 11:00:30 GMT
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



Mime
View raw message