Module org.jgrapht.core

Package org.jgrapht.alg.connectivity

Class AbstractStrongConnectivityInspector<V,E>

java.lang.Object

org.jgrapht.alg.connectivity.AbstractStrongConnectivityInspector<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

StrongConnectivityAlgorithm<V,E>

Direct Known Subclasses:

GabowStrongConnectivityInspector, KosarajuStrongConnectivityInspector

abstract class AbstractStrongConnectivityInspector<V,E>
extends java.lang.Object
implements StrongConnectivityAlgorithm<V,E>

Base implementation of the strongly connected components algorithm.

Field Summary

Fields

Modifier and Type	Field	Description
protected Graph<V,E>	graph
protected java.util.List<java.util.Set<V>>	stronglyConnectedSets
protected java.util.List<Graph<V,E>>	stronglyConnectedSubgraphs

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractStrongConnectivityInspector(Graph<V,E> graph)

Method Summary

Modifier and Type	Method	Description
Graph<Graph<V,E>,DefaultEdge>	getCondensation()	Compute the condensation of the given graph.
Graph<V,E>	getGraph()	Return the underlying graph.
java.util.List<Graph<V,E>>	getStronglyConnectedComponents()	Computes a list of subgraphs of the given graph.
boolean	isStronglyConnected()	Returns true if the graph is strongly connected, false otherwise.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.interfaces.StrongConnectivityAlgorithm

stronglyConnectedSets

Field Detail

graph

protected final Graph<V,E> graph

stronglyConnectedSets

protected java.util.List<java.util.Set<V>> stronglyConnectedSets

stronglyConnectedSubgraphs

protected java.util.List<Graph<V,E>> stronglyConnectedSubgraphs

Constructor Detail

AbstractStrongConnectivityInspector

protected AbstractStrongConnectivityInspector(Graph<V,E> graph)

Method Detail

getGraph

public Graph<V,E> getGraph()

Description copied from interface: StrongConnectivityAlgorithm

Return the underlying graph.

Specified by:

getGraph in interface StrongConnectivityAlgorithm<V,E>

Returns:

the underlying graph

isStronglyConnected

public boolean isStronglyConnected()

Description copied from interface: StrongConnectivityAlgorithm

Returns true if the graph is strongly connected, false otherwise.

Specified by:

isStronglyConnected in interface StrongConnectivityAlgorithm<V,E>

Returns:

true if the graph is strongly connected, false otherwise

getStronglyConnectedComponents

public java.util.List<Graph<V,E>> getStronglyConnectedComponents()

Description copied from interface: StrongConnectivityAlgorithm

Computes a list of subgraphs of the given graph. Each subgraph will represent a strongly connected component and will contain all vertices of that component. The subgraph will have an edge $(u,v)$ iff $u$ and $v$ are contained in the strongly connected component.

Specified by:

getStronglyConnectedComponents in interface StrongConnectivityAlgorithm<V,E>

Returns:

a list of subgraphs representing the strongly connected components

getCondensation

public Graph<Graph<V,E>,DefaultEdge> getCondensation()

Description copied from interface: StrongConnectivityAlgorithm

Compute the condensation of the given graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of the graph.

Specified by:

getCondensation in interface StrongConnectivityAlgorithm<V,E>

Returns:

the condensation of the given graph