com.codemelon.graph.algorithm.search

Class StronglyConnectedComponents<T extends DfsVertex & ComponentVertex,U extends OrderedDfsVertex>

java.lang.Object

com.codemelon.graph.algorithm.search.StronglyConnectedComponents<T,U>

public class StronglyConnectedComponents<T extends DfsVertex & ComponentVertex,U extends OrderedDfsVertex>
extends java.lang.Object

Identify the strongly connected components in a graph using an int value to mark the component to which each vertex belongs. Cf. CLRS, p. 617. The run() method of StronglyConnectedComponents creates a Transposer object in which the target graph has vertices of type U, which must be a subclass of OrderedDfsVertex. The vertices of the input graph must be subclasses of DfsVertex and must support component labeling but need not themselves support ordered depth-first search.

Constructor Summary

Constructors

Constructor and Description
StronglyConnectedComponents(AbstractGraph<T> graph, VertexFactory<U> vertexFactory, GraphFactory<U> graphFactory) Prepare to mark the graph for strongly connected components.

Method Summary

Methods

Modifier and Type	Method and Description
Transposer<T,U>	run() Marks the strongly connected components in the graph by setting the treeNumber field of each vertex accordingly.

Methods inherited from class java.lang.Object

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

Constructor Detail

StronglyConnectedComponents

public StronglyConnectedComponents(AbstractGraph<T> graph,
                           VertexFactory<U> vertexFactory,
                           GraphFactory<U> graphFactory)

Prepare to mark the graph for strongly connected components. No changes to the graph are made when the graph is passed into the constructor.

Parameters:

graph - graph for which strongly connected components are to be determined.

Method Detail

run

public Transposer<T,U> run()

Marks the strongly connected components in the graph by setting the treeNumber field of each vertex accordingly. Vertices in the same strongly connected component will have the same tree number, and vertices belonging to different components will have different tree numbers

Returns:

the Transposer object created when setting the vertex tree numbers. This object contains both the transpose graph that was created and a map from vertices of the original graph to the transpose graph.