Package org.jgrapht.alg
Class GabowStrongConnectivityInspector<V,E>
- java.lang.Object
-
- org.jgrapht.alg.GabowStrongConnectivityInspector<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
StrongConnectivityAlgorithm<V,E>
public class GabowStrongConnectivityInspector<V,E> extends java.lang.Object implements StrongConnectivityAlgorithm<V,E>
Allows obtaining the strongly connected components of a directed graph. The implemented algorithm follows Cheriyan-Mehlhorn/Gabow's algorithm Presented in Path-based depth-first search for strong and biconnected components by Gabow (2000). The running time is order of O(|V|+|E|)- Since:
- September, 2013
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
GabowStrongConnectivityInspector.VertexNumber<V>
-
Field Summary
Fields Modifier and Type Field Description private java.util.Deque<java.lang.Integer>
B
private int
c
private DirectedGraph<V,E>
graph
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>>
stack
private java.util.List<java.util.Set<V>>
stronglyConnectedSets
private java.util.List<DirectedSubgraph<V,E>>
stronglyConnectedSubgraphs
private java.util.Map<V,GabowStrongConnectivityInspector.VertexNumber<V>>
vertexToVertexNumber
-
Constructor Summary
Constructors Constructor Description GabowStrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
The constructor of GabowStrongConnectivityInspector class.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
createVertexNumber()
private void
dfsVisit(DirectedGraph<V,E> visitedGraph, GabowStrongConnectivityInspector.VertexNumber<V> v)
DirectedGraph<V,E>
getGraph()
Returns the graph inspectedboolean
isStronglyConnected()
Returns true if the graph instance is strongly connected.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.java.util.List<DirectedSubgraph<V,E>>
stronglyConnectedSubgraphs()
Computes a list ofDirectedSubgraph
s of the given graph.
-
-
-
Field Detail
-
graph
private final DirectedGraph<V,E> graph
-
stack
private java.util.Deque<GabowStrongConnectivityInspector.VertexNumber<V>> stack
-
stronglyConnectedSets
private java.util.List<java.util.Set<V>> stronglyConnectedSets
-
stronglyConnectedSubgraphs
private java.util.List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs
-
vertexToVertexNumber
private java.util.Map<V,GabowStrongConnectivityInspector.VertexNumber<V>> vertexToVertexNumber
-
B
private java.util.Deque<java.lang.Integer> B
-
c
private int c
-
-
Constructor Detail
-
GabowStrongConnectivityInspector
public GabowStrongConnectivityInspector(DirectedGraph<V,E> directedGraph)
The constructor of GabowStrongConnectivityInspector class.- Parameters:
directedGraph
- the graph to inspect- Throws:
java.lang.IllegalArgumentException
- in case the graph is null
-
-
Method Detail
-
getGraph
public DirectedGraph<V,E> getGraph()
Returns the graph inspected- Specified by:
getGraph
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- the graph inspected
-
isStronglyConnected
public boolean isStronglyConnected()
Returns true if the graph instance is strongly connected.- Specified by:
isStronglyConnected
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- true if the graph is strongly connected, false otherwise
-
stronglyConnectedSets
public 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.- Specified by:
stronglyConnectedSets
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
List
ofSet
s containing the strongly connected components
-
stronglyConnectedSubgraphs
public java.util.List<DirectedSubgraph<V,E>> stronglyConnectedSubgraphs()
Computes a list of
DirectedSubgraph
s 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.NOTE: Calling this method will first execute
stronglyConnectedSets()
. If you don't need subgraphs, use that method.- Specified by:
stronglyConnectedSubgraphs
in interfaceStrongConnectivityAlgorithm<V,E>
- Returns:
- a list of subgraphs representing the strongly connected components
-
createVertexNumber
private void createVertexNumber()
-
dfsVisit
private void dfsVisit(DirectedGraph<V,E> visitedGraph, GabowStrongConnectivityInspector.VertexNumber<V> v)
-
-