edu.uci.ics.jung.algorithms.cluster
Class BicomponentClusterer

java.lang.Object
  edu.uci.ics.jung.algorithms.cluster.BicomponentClusterer

All Implemented Interfaces:

GraphClusterer

public class BicomponentClusterer

extends java.lang.Object

implements GraphClusterer

Finds all bicomponents (or blocks) in an undirected graph where a bicomponent is defined as s maximal set of nodes and edges such that every pair of nodes is connected by two or more independent paths

Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges

Author:

Scott White

See Also:

"Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp.", "Algorithmic Graph Theory by Alan Gibbons, 1985, Cambridge Univ. Press"

Constructor Summary

BicomponentClusterer()
Constructs a new bicomponent finder

Method Summary

ClusterSet

extract(Graph theGraph) Extracts the bicomponents from the graph

Methods inherited from class java.lang.Object

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

Constructor Detail

BicomponentClusterer

public BicomponentClusterer()

Constructs a new bicomponent finder

Method Detail

extract

public ClusterSet extract(Graph theGraph)

Extracts the bicomponents from the graph

Specified by:

extract in interface GraphClusterer

Parameters:

theGraph - the graph whose bicomponents are to be extracted

Returns:

the list of bicomponents