edu.ksu.cis.kdd.util.graph
Class StronglyConnectedComponents

java.lang.Object
  edu.ksu.cis.kdd.util.graph.StronglyConnectedComponents

public class StronglyConnectedComponents

extends java.lang.Object

A class to compute the strongly connected components. A straight forward implementation from Cormen's textbook.

Author:

Roby Joehanes

Field Summary

protected TableSet	adjacencyListTable
protected java.util.Hashtable	clusterTable
protected TableSet	gTransform
protected java.util.LinkedList	reversePostOrderList
protected java.util.HashSet	seenAlready

Constructor Summary

StronglyConnectedComponents(Graph graph)

StronglyConnectedComponents(java.util.Set[] adjList)

StronglyConnectedComponents(TableSet adjList)

Method Summary

protected java.util.Set	dfsGetStronglyConnectedGraph(java.lang.Object curNode, java.util.HashSet set)
protected void	dfsSortByPostScore(java.lang.Object curNode) Deep first search computing post order score and the graph transform
java.util.Hashtable	getClusterTable() Get the table of node -> scc cluster
java.util.Set	getComponents() Returns the set of sets of strongly connected components
static java.util.Set	getComponents(Graph graph)
static java.util.Set	getComponents(TableSet adjList)
static void	main(java.lang.String[] args) A driver to test this strongly connected components

Methods inherited from class java.lang.Object

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

Field Detail

adjacencyListTable

protected TableSet adjacencyListTable

reversePostOrderList

protected java.util.LinkedList reversePostOrderList

seenAlready

protected java.util.HashSet seenAlready

gTransform

protected TableSet gTransform

clusterTable

protected java.util.Hashtable clusterTable

Constructor Detail

StronglyConnectedComponents

public StronglyConnectedComponents(TableSet adjList)

StronglyConnectedComponents

public StronglyConnectedComponents(java.util.Set[] adjList)

StronglyConnectedComponents

public StronglyConnectedComponents(Graph graph)

Method Detail

getComponents

public java.util.Set getComponents()

Returns the set of sets of strongly connected components

Returns:

Set

dfsSortByPostScore

protected void dfsSortByPostScore(java.lang.Object curNode)

Deep first search computing post order score and the graph transform

Parameters:

curNode -

dfsGetStronglyConnectedGraph

protected java.util.Set dfsGetStronglyConnectedGraph(java.lang.Object curNode,
                                                     java.util.HashSet set)

getComponents

public static java.util.Set getComponents(TableSet adjList)

getComponents

public static java.util.Set getComponents(Graph graph)

getClusterTable

public java.util.Hashtable getClusterTable()

Get the table of node -> scc cluster

Returns:

Hashtable

main

public static void main(java.lang.String[] args)

A driver to test this strongly connected components

Parameters:

args -