org.jgrapht.alg.interfaces

Interface StrongConnectivityAlgorithm<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Known Implementing Classes:

GabowStrongConnectivityInspector, GabowStrongConnectivityInspector, KosarajuStrongConnectivityInspector, KosarajuStrongConnectivityInspector

public interface StrongConnectivityAlgorithm<V,E>

A strong connectivity inspector algorithm.

Since:

September 2013

Author:

Sarah Komla-Ebri

Method Summary

Modifier and Type	Method and Description
Graph<Graph<V,E>,DefaultEdge>	getCondensation() Compute the condensation of the given graph.
Graph<V,E>	getGraph() Return the underlying graph.
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.
List<Set<V>>	stronglyConnectedSets() Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.

Method Detail

getGraph

Graph<V,E> getGraph()

Return the underlying graph.

Returns:

the underlying graph

isStronglyConnected

boolean isStronglyConnected()

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

Returns:

true if the graph is strongly connected, false otherwise

stronglyConnectedSets

List<Set<V>> stronglyConnectedSets()

Computes a List of Sets, where each set contains vertices which together form a strongly connected component within the given graph.

Returns:

List of Set s containing the strongly connected components

getStronglyConnectedComponents

List<Graph<V,E>> getStronglyConnectedComponents()

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.

Returns:

a list of subgraphs representing the strongly connected components

getCondensation

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

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.

Returns:

the condensation of the given graph