commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1240978 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning: DefaultSpanningTreeAlgorithmSelector.java SuperVertex.java
Date Mon, 06 Feb 2012 11:15:22 GMT
Author: tn
Date: Mon Feb  6 11:15:22 2012
New Revision: 1240978

URL: http://svn.apache.org/viewvc?rev=1240978&view=rev
Log:
Added more performant version of Boruvkas algorithm.
JIRA: SANDBOX-348

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
  (with props)
Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java?rev=1240978&r1=1240977&r2=1240978&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
Mon Feb  6 11:15:22 2012
@@ -19,16 +19,13 @@ package org.apache.commons.graph.spannin
  * under the License.
  */
 
-import static java.util.Collections.sort;
-import static org.apache.commons.graph.CommonsGraph.findConnectedComponent;
-import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 import static org.apache.commons.graph.utils.Assertions.checkState;
 
-import java.util.ArrayList;
-import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
-import java.util.Iterator;
+import java.util.LinkedList;
 import java.util.List;
+import java.util.Map;
 import java.util.PriorityQueue;
 import java.util.Set;
 
@@ -63,9 +60,7 @@ final class DefaultSpanningTreeAlgorithm
         this.source = source;
     }
 
-    /**
-     * {@inheritDoc}
-     */
+    /** {@inheritDoc} */
     public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm(
OM orderedMonoid )
     {
         /*
@@ -79,84 +74,77 @@ final class DefaultSpanningTreeAlgorithm
          *                 T <= T U {e}
          *             end if
          *         end for
-         * end while
-         *
+         *     end while
          * <pre>
          */
-
-        Collection<List<V>> connectedComponents =
-            findConnectedComponent( graph ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
-
-        checkNotNull( connectedComponents, "Connectivity algorithms returns a null pointer"
);
-        checkState( connectedComponents.size() == 1, "Boruvka's Algorithm cannot be calculated
on not-connected graph." );
-
-        final List<WE> sortedEdge = new ArrayList<WE>();
-
-        for ( WE we : graph.getEdges() )
-        {
-            sortedEdge.add( we );
-        }
-
-        sort( sortedEdge, new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
-
-        final MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V,
WE, W>( orderedMonoid );
+        
+        final MutableSpanningTree<V, WE, W> spanningTree =
+            new MutableSpanningTree<V, WE, W>( orderedMonoid );
+        
+        final Set<SuperVertex<V, W, WE, G, OM>> components =
+            new HashSet<SuperVertex<V, W, WE, G, OM>>( graph.getOrder() );
+        
+        final Map<V, SuperVertex<V, W, WE, G, OM>> mapping =
+            new HashMap<V, SuperVertex<V, W, WE, G, OM>>( graph.getOrder() );
 
         for ( V v : graph.getVertices() )
         {
+            // create a super vertex for each vertex
+            final SuperVertex<V, W, WE, G, OM> sv =
+                new SuperVertex<V, W, WE, G, OM>( v, graph, orderedMonoid );
+            components.add( sv );
+            // add a mapping for each vertex to its corresponding super vertex
+            mapping.put( v, sv );
+            // add each vertex to the spanning tree
             spanningTree.addVertex( v );
         }
 
-        // find connected component into spanning tree.
-        connectedComponents = findConnectedComponent( spanningTree ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
-        do
-        {
-            Iterator<WE> it = sortedEdge.iterator();
+        while ( components.size() > 1 ) {
+            List<WE> edges = new LinkedList<WE>();
+            for ( SuperVertex<V, W, WE, G, OM> v : components ) {
+                // get the minimum edge for each component to any other component
+                WE edge = v.getMinimumWeightEdge();
+                if (edge != null) {
+                    edges.add( edge );
+                }
+            }
 
-            while ( it.hasNext() )
-            {
-                WE edge = it.next();
+            // if there is no edge anymore for a component, and there is still more than
1 component,
+            // the graph is unconnected
+            checkState(!edges.isEmpty() || components.size() == 1, "unconnected graph");
+            
+            for ( WE edge : edges ) {
                 VertexPair<V> pair = graph.getVertices( edge );
-                // find the vertices into the connected component.
-                for ( List<V> list : connectedComponents )
-                {
-                    boolean listContainsHead = list.contains( pair.getHead() );
-                    boolean listContainsTail = list.contains( pair.getTail() );
-
-                    if ( listContainsHead && listContainsTail )
-                    {
-                        // this edge is included into a connected component.
-                        it.remove();
-                        break;
+                V head = pair.getHead();
+                V tail = pair.getTail();
+                
+                // find the super vertices corresponding to this edge
+                SuperVertex<V, W, WE, G, OM> headSuper = mapping.get( head );
+                SuperVertex<V, W, WE, G, OM> tailSuper = mapping.get( tail );
+                
+                // merge them, if they are not the same
+                if ( headSuper != tailSuper ) {
+                    headSuper.merge( tailSuper );
+                
+                    // update the mapping for each merged vertex
+                    for ( V v : tailSuper ) {
+                        mapping.put( v, headSuper );
                     }
-                    else if ( listContainsHead )
-                    {
-                        spanningTree.addEdge( pair.getHead(), edge, pair.getTail() );
-                        it.remove();
-
-                        for ( List<V> l : connectedComponents )
-                        {
-                            if ( l == list )
-                            {
-                                continue;
-                            }
-
-                            if ( l.contains( pair.getTail() ) )
-                            {
-                                list.addAll( l );
-                                l.clear();
-                                break;
-                            }
-                        }
-                        break;
+                
+                    // remove the merged super vertex from the components set
+                    components.remove( tailSuper );
+
+                    // add the edge to the spanning tree
+                    if ( spanningTree.getVertices( edge ) == null ) {
+                        spanningTree.addEdge( head, edge, tail );
                     }
                 }
-            }
+            }            
         }
-        while ( spanningTree.getSize() < spanningTree.getOrder() - 1 );
-
+        
         return spanningTree;
     }
-
+    
     /**
      * {@inheritDoc}
      */

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java?rev=1240978&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
Mon Feb  6 11:15:22 2012
@@ -0,0 +1,94 @@
+package org.apache.commons.graph.spanning;
+
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/**
+ * A {@link SuperVertex} is a collection of {@link Vertex} objects and is only
+ * used internally by Boruvka's algorithm to find a minimum spanning tree.
+ * 
+ * @param <V>  the Graph vertices type
+ * @param <W>  the weight type
+ * @param <WE> the Graph weighted edges type
+ * @param <G>  the input Graph type
+ * @param <OM> the Comparator for weighted edges
+ */
+class SuperVertex<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V,
WE>, OM extends OrderedMonoid<W>>
+    implements Iterable<V> {
+
+    /** The reference to the graph. */
+    private G graph;
+
+    /** The set of vertices combined in this {@link SuperVertex}. */
+    private Set<V> vertices;
+    
+    /** The ordered set of edges to other {@link SuperVertex} objects. */
+    private TreeSet<WE> orderedEdges;
+    
+    /**
+     * Create a new {@link SuperVertex} instance with <code>source</code>
+     * as start vertex.
+     * 
+     * @param source the start vertex
+     * @param graph the underlying graph
+     * @param orderedMonoid the comparator used to sort the weighted edges
+     */
+    public SuperVertex( final V source, final G graph, final OM orderedMonoid ) {
+        this.graph = graph;
+        
+        vertices = new HashSet<V>();
+        vertices.add( source );
+        
+        orderedEdges = new TreeSet<WE>( new WeightedEdgesComparator<W, WE>( orderedMonoid
) );
+        
+        // add all edges for this vertex to the sorted set
+        for ( V w : graph.getConnectedVertices( source )) {
+            WE edge = graph.getEdge( source, w );
+            orderedEdges.add( edge );
+        }
+    }
+    
+    /** {@inheritDoc} */
+    public Iterator<V> iterator() {
+        return vertices.iterator();
+    }
+
+    /**
+     * Merges another {@link SuperVertex} instance into this one.
+     * The edges from the other {@link SuperVertex} are only added in case
+     * they are not to vertices already contained in this {@link SuperVertex}. 
+     * 
+     * @param other the {@link SuperVertex} to be merged into this
+     */
+    public void merge( final SuperVertex<V, W, WE, G, OM> other ) {
+        for ( V v : other.vertices ) {
+            vertices.add(v);
+        }
+        
+        for (WE edge : other.orderedEdges) {
+            VertexPair<V> pair = graph.getVertices( edge );
+            if ( !vertices.contains(pair.getHead()) ||
+                 !vertices.contains(pair.getTail()) ) {
+                orderedEdges.add( edge );
+            }
+        }
+    }
+
+    /**
+     * Returns the edge with the minimum weight to other {@link SuperVertex}
+     * instances.
+     * 
+     * @return the minimum weight edge
+     */
+    public WE getMinimumWeightEdge() {
+        return orderedEdges.pollFirst();
+    }
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message