com.raffaeleconforti.automaton

Class TarjanSCC

java.lang.Object

com.raffaeleconforti.automaton.TarjanSCC

public class TarjanSCC
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
TarjanSCC(Automaton G) Computes the strong components of the digraph G.

Method Summary

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.
boolean	stronglyConnected(int v, int w) Are vertices v and w in the same strong component?

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TarjanSCC

public TarjanSCC(Automaton G)

Computes the strong components of the digraph G.

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 vertices v and w in the same strong component?

Parameters:

v - one vertex

w - the other vertex

Returns:

true if vertices v and w are in the same strong component, and false otherwise

Throws:

java.lang.IllegalArgumentException - unless 0 <= v < V

java.lang.IllegalArgumentException - unless 0 <= w < V

id

public int id(int v)

Returns the component id of the strong component containing vertex v.

Parameters:

v - the vertex

Returns:

the component id of the strong component containing vertex v

Throws:

java.lang.IllegalArgumentException - unless 0 <= v < V