Package edu.umd.cs.findbugs.graph

Class StronglyConnectedComponents<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>>

java.lang.Object

edu.umd.cs.findbugs.graph.StronglyConnectedComponents<GraphType,EdgeType,VertexType>

public class StronglyConnectedComponents<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>>
extends java.lang.Object

Algorithm to find strongly connected components in a graph. Based on algorithm in Cormen et. al., Introduction to Algorithms, p. 489.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	StronglyConnectedComponents.SCCSetIterator	Iterator for iterating over sets of vertices in strongly connected components.

Field Summary

Fields

Modifier and Type	Field	Description
private java.util.ArrayList<SearchTree<VertexType>>	m_stronglyConnectedSearchTreeList
private VertexChooser<VertexType>	m_vertexChooser

Constructor Summary

Constructors

Constructor	Description
StronglyConnectedComponents()	Constructor.

Method Summary

Modifier and Type	Method	Description
private SearchTree<VertexType>	copySearchTree(SearchTree<VertexType> tree, Transpose<GraphType,EdgeType,VertexType> t)	Make a copy of given search tree (in the transposed graph) using vertices of the original graph.
void	findStronglyConnectedComponents(GraphType g, GraphToolkit<GraphType,EdgeType,VertexType> toolkit)	Find the strongly connected components in given graph.
java.util.Iterator<SearchTree<VertexType>>	searchTreeIterator()	Returns an iterator over the search trees containing the vertices of each strongly connected component.
java.util.Iterator<java.util.Set<VertexType>>	setIterator()	Returns an iterator over the sets of vertices of each strongly connected component.
void	setVertexChooser(VertexChooser<VertexType> vertexChooser)	Specify a VertexChooser object to restrict which vertices are considered.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_stronglyConnectedSearchTreeList

private final java.util.ArrayList<SearchTree<VertexType extends GraphVertex<VertexType>>> m_stronglyConnectedSearchTreeList

m_vertexChooser

private VertexChooser<VertexType extends GraphVertex<VertexType>> m_vertexChooser

Constructor Detail

StronglyConnectedComponents

public StronglyConnectedComponents()

Constructor.

Method Detail

setVertexChooser

public void setVertexChooser(VertexChooser<VertexType> vertexChooser)

Specify a VertexChooser object to restrict which vertices are considered. This is useful if you only want to find strongly connected components among a particular category of vertices.

findStronglyConnectedComponents

public void findStronglyConnectedComponents(GraphType g,
                                            GraphToolkit<GraphType,EdgeType,VertexType> toolkit)

Find the strongly connected components in given graph.

Parameters:

g - the graph

toolkit - a GraphToolkit, used to create temporary graphs used by the algorithm

copySearchTree

private SearchTree<VertexType> copySearchTree(SearchTree<VertexType> tree,
                                              Transpose<GraphType,EdgeType,VertexType> t)

Make a copy of given search tree (in the transposed graph) using vertices of the original graph.

Parameters:

tree - a search tree in the transposed graph

t - the Transpose object which performed the transposition of the original graph

searchTreeIterator

public java.util.Iterator<SearchTree<VertexType>> searchTreeIterator()

Returns an iterator over the search trees containing the vertices of each strongly connected component.

Returns:

an Iterator over a sequence of SearchTree objects

setIterator

public java.util.Iterator<java.util.Set<VertexType>> setIterator()

Returns an iterator over the sets of vertices of each strongly connected component.

Returns:

an Iterator over a sequence of Set objects