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/03/02 09:46:49 UTC
svn commit: r1296088 -
/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
Author: simonetripodi
Date: Fri Mar 2 08:46:49 2012
New Revision: 1296088
URL: http://svn.apache.org/viewvc?rev=1296088&view=rev
Log:
trailing spaces NO FUNCTIONAL CHANGES
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java?rev=1296088&r1=1296087&r2=1296088&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java Fri Mar 2 08:46:49 2012
@@ -66,18 +66,18 @@ public final class DefaultSccAlgorithmSe
{
checkNotNull( source, "Kosaraju Sharir algorithm cannot be calculated without expressing the source vertex" );
checkState( graph.containsVertex( source ), "Vertex %s does not exist in the Graph", source );
-
+
final Set<V> visitedVertices = new HashSet<V>();
final List<V> expandedVertexList = getExpandedVertexList( source, visitedVertices );
final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
-
+
// remove the last element from the expanded vertices list
final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
final Set<V> sccSet = new HashSet<V>();
searchRecursive( reverted, v, sccSet, visitedVertices, false );
return sccSet;
}
-
+
/**
* {@inheritDoc}
*/
@@ -95,20 +95,20 @@ public final class DefaultSccAlgorithmSe
final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
final Set<V> sccSet = new HashSet<V>();
searchRecursive( reverted, v, sccSet, visitedVertices, false );
-
- // remove all strongly connected components from the expanded list
+
+ // remove all strongly connected components from the expanded list
expandedVertexList.removeAll( sccSet );
sccs.add( sccSet );
}
-
+
return sccs;
}
-
+
private List<V> getExpandedVertexList( final V source, final Set<V> visitedVertices )
{
final int size = (source != null) ? 13 : graph.getOrder();
final Set<V> vertices = new HashSet<V>( size );
-
+
if ( source != null )
{
vertices.add( source );
@@ -120,7 +120,7 @@ public final class DefaultSccAlgorithmSe
vertices.add( vertex );
}
}
-
+
// use an ArrayList so that subList is fast
final ArrayList<V> expandedVertexList = new ArrayList<V>();
@@ -128,7 +128,7 @@ public final class DefaultSccAlgorithmSe
while ( ! vertices.isEmpty() )
{
// get the next vertex that has not yet been added to the expanded list
- final V v = vertices.iterator().next();
+ final V v = vertices.iterator().next();
searchRecursive( graph, v, expandedVertexList, visitedVertices, true );
// remove all expanded vertices from the list of vertices that have to be
// still processed. To improve performance, only the items that have been
@@ -136,15 +136,15 @@ public final class DefaultSccAlgorithmSe
vertices.removeAll( expandedVertexList.subList( idx, expandedVertexList.size() ) );
idx = expandedVertexList.size();
}
-
+
return expandedVertexList;
}
/**
* Searches a directed graph in iterative depth-first order, while adding the visited
- * vertices in a recursive manner, i.e. a vertex is added to the result list only
+ * vertices in a recursive manner, i.e. a vertex is added to the result list only
* when the search has finished expanding the vertex (and its subsequent childs).
- *
+ *
* <p><b>Implementation Note:</b> in the first step we look for vertices that have not
* been visited yet, while in the second step we search for vertices that have already
* been visited.</p>
@@ -161,7 +161,7 @@ public final class DefaultSccAlgorithmSe
{
final LinkedList<V> stack = new LinkedList<V>();
stack.addLast( source );
-
+
while ( !stack.isEmpty() )
{
final V v = stack.removeLast();
@@ -174,7 +174,7 @@ public final class DefaultSccAlgorithmSe
if ( ! ( forward ^ visited.contains( v ) ) )
{
coll.add( v );
- continue;
+ continue;
}
// add the current vertex to the stack, so it is visited again
@@ -200,7 +200,7 @@ public final class DefaultSccAlgorithmSe
}
}
}
-
+
/**
* {@inheritDoc}
*/