Package org.jgrapht.alg.interfaces
Interface StrongConnectivityAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Known Implementing Classes:
GabowStrongConnectivityInspector
,KosarajuStrongConnectivityInspector
public interface StrongConnectivityAlgorithm<V,E>
A strong connectivity inspector algorithm.- Author:
- Sarah Komla-Ebri
-
-
Method Summary
All Methods Instance Methods Abstract 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.java.util.List<java.util.Set<V>>
stronglyConnectedSets()
Computes aList
ofSet
s, where each set contains vertices which together form a strongly connected component within the given graph.
-
-
-
Method Detail
-
isStronglyConnected
boolean isStronglyConnected()
Returns true if the graph is strongly connected, false otherwise.- Returns:
- true if the graph is strongly connected, false otherwise
-
stronglyConnectedSets
java.util.List<java.util.Set<V>> stronglyConnectedSets()
Computes aList
ofSet
s, where each set contains vertices which together form a strongly connected component within the given graph.- Returns:
List
ofSet
s containing the strongly connected components
-
getStronglyConnectedComponents
java.util.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
-
-