Package edu.princeton.cs.algs4
Class GabowSCC
 Object

 edu.princeton.cs.algs4.GabowSCC

public class GabowSCC extends Object
TheGabowSCC
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
andTarjanSCC
.For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
count()
Returns the number of strong components.int
id(int v)
Returns the component id of the strong component containing vertexv
.static void
main(String[] args)
Unit tests theGabowSCC
data type.boolean
stronglyConnected(int v, int w)
Are verticesv
andw
in the same strong component?



Constructor Detail

GabowSCC
public GabowSCC(Digraph G)
Computes the strong components of the digraphG
. Parameters:
G
 the digraph


Method Detail

count
public int count()
Returns the number of strong components. Returns:
 the number of strong components

stronglyConnected
public boolean stronglyConnected(int v, int w)
Are verticesv
andw
in the same strong component? Parameters:
v
 one vertexw
 the other vertex Returns:
true
if verticesv
andw
are in the same strong component, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V
IllegalArgumentException
 unless0 <= w < V

id
public int id(int v)
Returns the component id of the strong component containing vertexv
. Parameters:
v
 the vertex Returns:
 the component id of the strong component containing vertex
v
 Throws:
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theGabowSCC
data type. Parameters:
args
 the commandline arguments

