Author: simonetripodi
Date: Thu Jul 7 21:29:43 2011
New Revision: 1144051
URL: http://svn.apache.org/viewvc?rev=1144051&view=rev
Log:
Disjoint-set implementation moved in the collections package
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
(contents, props changed)
- copied, changed from r1143237,
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
(contents, props changed)
- copied, changed from r1143237,
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
Copied:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
(from r1143237,
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java)
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java&r1=1143237&r2=1144051&rev=1144051&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java
(original)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
Thu Jul 7 21:29:43 2011
@@ -1,4 +1,4 @@
-package org.apache.commons.graph.spanning;
+package org.apache.commons.graph.collections;
/*
* Licensed to the Apache Software Foundation (ASF) under one
@@ -22,17 +22,15 @@ package org.apache.commons.graph.spannin
import java.util.HashMap;
import java.util.Map;
-import org.apache.commons.graph.Vertex;
-
/**
* Simple <a
href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure";>Disjoint-set</a>
implementation.
*
- * @param <V> the Graph vertices type.
+ * @param <E> the type of elements held in this collection.
*/
-final class DisjointSet<V extends Vertex>
+public final class DisjointSet<E>
{
- private final Map<V, DisjointSetNode<V>> disjointSets = new HashMap<V,
DisjointSetNode<V>>();
+ private final Map<E, DisjointSetNode<E>> disjointSets = new HashMap<E,
DisjointSetNode<E>>();
/**
* Performs the find applying the <i>path compression</i>.
@@ -40,9 +38,9 @@ final class DisjointSet<V extends Vertex
* @param vertex
* @return
*/
- public V find( V vertex )
+ public E find( E vertex )
{
- DisjointSetNode<V> vertexNode = find( getNode( vertex ) );
+ DisjointSetNode<E> vertexNode = find( getNode( vertex ) );
if ( vertexNode == vertexNode.getParent() )
{
@@ -60,7 +58,7 @@ final class DisjointSet<V extends Vertex
* @param node
* @return
*/
- private DisjointSetNode<V> find( DisjointSetNode<V> node )
+ private DisjointSetNode<E> find( DisjointSetNode<E> node )
{
if ( node == node.getParent() )
{
@@ -75,10 +73,10 @@ final class DisjointSet<V extends Vertex
* @param u
* @param v
*/
- public void union( V u, V v )
+ public void union( E u, E v )
{
- DisjointSetNode<V> uRoot = find( getNode( u ) );
- DisjointSetNode<V> vRoot = find( getNode( v ) );
+ DisjointSetNode<E> uRoot = find( getNode( u ) );
+ DisjointSetNode<E> vRoot = find( getNode( v ) );
if ( uRoot == vRoot )
{
@@ -101,13 +99,13 @@ final class DisjointSet<V extends Vertex
}
}
- private DisjointSetNode<V> getNode( V vertex )
+ private DisjointSetNode<E> getNode( E vertex )
{
- DisjointSetNode<V> node = disjointSets.get( vertex );
+ DisjointSetNode<E> node = disjointSets.get( vertex );
if ( node == null )
{
- node = new DisjointSetNode<V>( vertex );
+ node = new DisjointSetNode<E>( vertex );
disjointSets.put( vertex, node );
}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSet.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Copied:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
(from r1143237,
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java)
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java&r1=1143237&r2=1144051&rev=1144051&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java
(original)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
Thu Jul 7 21:29:43 2011
@@ -1,4 +1,4 @@
-package org.apache.commons.graph.spanning;
+package org.apache.commons.graph.collections;
/*
* Licensed to the Apache Software Foundation (ASF) under one
@@ -19,20 +19,18 @@ package org.apache.commons.graph.spannin
* under the License.
*/
-import org.apache.commons.graph.Vertex;
-
/**
* The {@link DisjointSet} internal node representation.
*
- * @param <V> the Graph vertices type.
+ * @param <E> the type of elements held in this node
*/
-final class DisjointSetNode<V extends Vertex>
- implements Comparable<DisjointSetNode<V>>
+final class DisjointSetNode<E>
+ implements Comparable<DisjointSetNode<E>>
{
- private final V vertex;
+ private final E vertex;
- private DisjointSetNode<V> parent = this;
+ private DisjointSetNode<E> parent = this;
private Integer rank = 0;
@@ -41,22 +39,22 @@ final class DisjointSetNode<V extends Ve
*
* @param vertex
*/
- public DisjointSetNode( V vertex )
+ public DisjointSetNode( E vertex )
{
this.vertex = vertex;
}
- public V getVertex()
+ public E getVertex()
{
return vertex;
}
- public DisjointSetNode<V> getParent()
+ public DisjointSetNode<E> getParent()
{
return parent;
}
- public void setParent( DisjointSetNode<V> parent )
+ public void setParent( DisjointSetNode<E> parent )
{
this.parent = parent;
}
@@ -79,7 +77,7 @@ final class DisjointSetNode<V extends Ve
/**
* {@inheritDoc}
*/
- public int compareTo( DisjointSetNode<V> o )
+ public int compareTo( DisjointSetNode<E> o )
{
return rank.compareTo( o.getRank() );
}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/DisjointSetNode.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java?rev=1144051&r1=1144050&r2=1144051&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
(original)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
Thu Jul 7 21:29:43 2011
@@ -28,6 +28,7 @@ import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedGraph;
+import org.apache.commons.graph.collections.DisjointSet;
import org.apache.commons.graph.model.MutableSpanningTree;
/**
