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 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 ClassesModifier and TypeClassDescriptionprivate class
Iterator for iterating over sets of vertices in strongly connected components. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final ArrayList
<SearchTree<VertexType>> private VertexChooser
<VertexType> -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate SearchTree
<VertexType> Make a copy of given search tree (in the transposed graph) using vertices of the original graph.void
Find the strongly connected components in given graph.Returns an iterator over the search trees containing the vertices of each strongly connected component.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.
-
Field Details
-
m_stronglyConnectedSearchTreeList
private final ArrayList<SearchTree<VertexType extends GraphVertex<VertexType>>> m_stronglyConnectedSearchTreeList -
m_vertexChooser
-
-
Constructor Details
-
StronglyConnectedComponents
public StronglyConnectedComponents()Constructor.
-
-
Method Details
-
setVertexChooser
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 graphtoolkit
- 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 grapht
- the Transpose object which performed the transposition of the original graph
-
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
Returns an iterator over the sets of vertices of each strongly connected component.- Returns:
- an Iterator over a sequence of Set objects
-