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 typeE
- 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
All Methods Instance Methods Concrete Methods 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
-
-
-
-
Method Detail
-
getGraph
public Graph<V,E> getGraph()
Description copied from interface:StrongConnectivityAlgorithm
Return the underlying graph.- Specified by:
getGraph
in interfaceStrongConnectivityAlgorithm<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 interfaceStrongConnectivityAlgorithm<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 interfaceStrongConnectivityAlgorithm<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 interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- the condensation of the given graph
-
-