You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/02/06 12:15:22 UTC
svn commit: r1240978 - in
/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning:
DefaultSpanningTreeAlgorithmSelector.java SuperVertex.java
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