org.ginsim.johnsonCycles

Class StrongConnectedComponents

java.lang.Object

org.ginsim.johnsonCycles.StrongConnectedComponents

public class StrongConnectedComponents
extends Object

This is a helpclass for the search of all elementary cycles in a graph with the algorithm of Johnson. For this it searches for strong connected components, using the algorithm of Tarjan. The constructor gets an adjacency-list of a graph. Based on this graph, it gets a nodenumber s, for which it calculates the subgraph, containing all nodes {s, s + 1, ..., n}, where n is the highest nodenumber in the original graph (e.g. it builds a subgraph with all nodes with higher or same nodenumbers like the given node s). It returns the strong connected component of this subgraph which contains the lowest nodenumber of all nodes in the subgraph.

For a description of the algorithm for calculating the strong connected components see:
Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Volume 1, Nr. 2 (1972), pp. 146-160.
For a description of the algorithm for searching all elementary cycles in a directed graph see:
Donald B. Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing. Volumne 4, Nr. 1 (1975), pp. 77-84.

Version:

1.1, 22.03.2009

Author:

Frank Meyer, web_at_normalisiert_dot_de

Constructor Summary

Constructors

Constructor and Description
StrongConnectedComponents(int[][] adjList) Constructor.

Method Summary

Modifier and Type	Method and Description
SCCResult	getAdjacencyList(int node) This method returns the adjacency-structure of the strong connected component with the least vertex in a subgraph of the original graph induced by the nodes {s, s + 1, ..., n}, where s is a given node.
static void	main(String[] args)

Methods inherited from class java.lang.Object

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

Constructor Detail

StrongConnectedComponents

public StrongConnectedComponents(int[][] adjList)

Constructor.

Parameters:

adjList - adjacency-list of the graph

Method Detail

getAdjacencyList

public SCCResult getAdjacencyList(int node)

This method returns the adjacency-structure of the strong connected component with the least vertex in a subgraph of the original graph induced by the nodes {s, s + 1, ..., n}, where s is a given node. Note that trivial strong connected components with just one node will not be returned.

Parameters:

node - node s

Returns:

SCCResult with adjacency-structure of the strong connected component; null, if no such component exists

main

public static void main(String[] args)