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.13 2006/03/14 02:55:23 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.Set<Vertex>	entryVertices() Returns the entry vertices of this strongly connected component.
java.util.Set<Vertex>	exitVertices() Returns the exit vertices of this strongly connected component.
int	getId() Returns the numeric ID of this SCComponent.
static <Vertex> BiDiNavigator<SCComponent<Vertex>>	getSccBiDiNavigator() 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 SCCs that this SCC points to in the component digraph.
java.util.List<SCComponent<Vertex>>	prev() Returns the SCCs that point to this SCC in the component digraph.
int	size() Returns the number of vertices in this strongly connected component.
java.lang.String	toString() Pretty-print method for debugging.
java.util.Set<Vertex>	vertices() Returns the vertices of this strongly connected component.

Methods inherited from class java.lang.Object

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

Method Detail

getSccBiDiNavigator

public static <Vertex> BiDiNavigator<SCComponent<Vertex>> getSccBiDiNavigator()

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). The client may mutate this set, with no effect on the original digraph diGraph.

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 SCCs that this SCC points to in the component digraph. Returns an unmodifiable list. Returns a list (instead of a set), in order to be consistent with the navigator methods.

prev

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

Returns the SCCs that point to this SCC in the component digraph. Returns an unmodifiable list. Returns a list (instead of a set), in order to be consistent with the navigator methods.

vertices

public final java.util.Set<Vertex> vertices()

Returns the vertices of this strongly connected component. Returns an umodifiable set.

size

public final int size()

Returns the number of vertices in this strongly connected component.

contains

public final boolean contains(Vertex node)

Checks whether node belongs to this \ strongly connected component.

entryVertices

public final java.util.Set<Vertex> entryVertices()

Returns the entry vertices of this strongly connected component. These are the vertices that are reachable from outside the component. Returns an unmodifiable set.

exitVertices

public final java.util.Set<Vertex> exitVertices()

Returns the exit vertices of this strongly connected component. These are the vertices that have arcs toward vertices outside the component. Returns an unmodifiable set.

toString

public final java.lang.String toString()

Pretty-print method for debugging.

Overrides:

toString in class java.lang.Object