jpaul.Graphs
Class SCComponent<Vertex>

java.lang.Object
  jpaul.Graphs.SCComponent<Vertex>

All Implemented Interfaces:

java.io.Serializable, java.lang.Comparable<SCComponent<Vertex>>

public final class SCComponent<Vertex>
extends java.lang.Object
implements java.lang.Comparable<SCComponent<Vertex>>, java.io.Serializable

SCComponent models a strongly-connected component of a directed graph: a set of vertices such that there is a path between any two of them. The main way of spliting a digraph into SCComponents is using the method buildScc. Alternatively, given a DiGraph, one may construct a TopSortedCompDiGraph (using its constructor).

Version:

$Id: SCComponent.java,v 1.3 2005/08/11 21:13:24 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

DiGraph, TopSortedCompDiGraph, buildScc(jpaul.Graphs.DiGraph), Serialized Form

Method Summary

static <Vertex> java.util.Set<SCComponent<Vertex>>	buildScc(DiGraph<Vertex> diGraph) Splits a directed graph into the set of its strongly-connected components.
int	compareTo(SCComponent<Vertex> scc2)
boolean	contains(Vertex node) Checks whether node belongs to this \ strongly connected component.
java.util.List<Vertex>	entries() Returns the entry nodes of this strongly connected component.
java.util.List<Vertex>	exits() Returns the exit nodes of this strongly connected component.
int	getId() Returns the numeric ID of this SCComponent.
static <Vertex> Navigator<SCComponent<Vertex>>	getSccNavigator() Default navigator through a component graph (a diGraph of strongly-connected components).
boolean	isLoop() Checks whether this strongly connected component corresponds to a loop, ie it has at least one arc to itself.
java.util.List<SCComponent<Vertex>>	next() Returns the successors.
java.util.Collection<Vertex>	nodes() Returns the nodes of this strongly connected component (set version).
java.util.List<SCComponent<Vertex>>	prev() Returns the predecessors.
int	size() Returns the number of nodes in this strongly connected component.
java.lang.String	toString() Pretty-print method for debugging.

Methods inherited from class java.lang.Object

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

Method Detail

getSccNavigator

public static <Vertex> Navigator<SCComponent<Vertex>> getSccNavigator()

Default navigator through a component graph (a diGraph of strongly-connected components).

buildScc

public static final <Vertex> java.util.Set<SCComponent<Vertex>> buildScc(DiGraph<Vertex> diGraph)

Splits a directed graph into the set of its strongly-connected components. The complexity is linear in the size of the original digraph (nb. of vertices + nb. of arcs). We use the algorithm from the DFS-based algorithm from Cormen, Leiserson, Rivest, MIT Press, 19th Edition, 1997, Section 23.5, an efficient and simple algorithm.

Parameters:

diGraph - Directed graph

Returns:

Set of top-level strongly-connected components (ie, SCCs that are not pointed to by anybody).

getId

public int getId()

Returns the numeric ID of this SCComponent. Just for debug purposes ...

isLoop

public final boolean isLoop()

Checks whether this strongly connected component corresponds to a loop, ie it has at least one arc to itself.

compareTo

public int compareTo(SCComponent<Vertex> scc2)

Specified by:

compareTo in interface java.lang.Comparable<SCComponent<Vertex>>

next

public final java.util.List<SCComponent<Vertex>> next()

Returns the successors.

prev

public final java.util.List<SCComponent<Vertex>> prev()

Returns the predecessors.

nodes

public final java.util.Collection<Vertex> nodes()

Returns the nodes of this strongly connected component (set version).

size

public final int size()

Returns the number of nodes in this strongly connected component.

contains

public final boolean contains(Vertex node)

Checks whether node belongs to this \ strongly connected component.

entries

public final java.util.List<Vertex> entries()

Returns the entry nodes of this strongly connected component. These are the nodes that are reachable from outside the component.

exits

public final java.util.List<Vertex> exits()

Returns the exit nodes of this strongly connected component. These are the nodes that have arcs toward nodes outside the component.

toString

public final java.lang.String toString()

Pretty-print method for debugging.

Overrides:

toString in class java.lang.Object