public class GabowSCC extends Object
GabowSCC
class represents a data type for
determining the strong components in a digraph.
The id operation determines in which strong component
a given vertex lies; the areStronglyConnected operation
determines whether two vertices are in the same strong component;
and the count operation determines the number of strong
components.
The component identifier of a component is one of the
vertices in the strong component: two vertices have the same component
identifier if and only if they are in the same strong component.
This implementation uses the Gabow's algorithm.
The constructor takes Θ(V + E) time,
where V is the number of vertices and E is
the number of edges.
Each instance method takes Θ(1) time.
It uses Θ(V) extra space (not including the digraph).
For alternative implementations of the same API, see
KosarajuSharirSCC
and TarjanSCC
.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
GabowSCC(Digraph G)
Computes the strong components of the digraph
G . |
Modifier and Type | Method and Description |
---|---|
int |
count()
Returns the number of strong components.
|
int |
id(int v)
Returns the component id of the strong component containing vertex
v . |
static void |
main(String[] args)
Unit tests the
GabowSCC data type. |
boolean |
stronglyConnected(int v,
int w)
Are vertices
v and w in the same strong component? |
public GabowSCC(Digraph G)
G
.G
- the digraphpublic int count()
public boolean stronglyConnected(int v, int w)
v
and w
in the same strong component?v
- one vertexw
- the other vertextrue
if vertices v
and w
are in the same
strong component, and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
IllegalArgumentException
- unless 0 <= w < V
public int id(int v)
v
.v
- the vertexv
IllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
GabowSCC
data type.args
- the command-line arguments