graph.properties.splitting

Class HopcroftTarjanSplitting<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.properties.splitting.HopcroftTarjanSplitting<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class HopcroftTarjanSplitting<V extends Vertex,E extends Edge<V>>
extends java.lang.Object

Implementation based on Hopcroft and Tarjan's algorithm: J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2 (1973), no. 3, 135–158.

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
HopcroftTarjanSplitting(Graph<V,E> graph)
HopcroftTarjanSplitting(Graph<V,E> graph, boolean debug)

Method Summary

Modifier and Type	Method and Description
void	execute() Executes the algorithms and sets values of the properties which contain the results - lists of separation pair and components
java.util.List<java.util.List<E>>	getPaths()
java.util.List<SeparationPair<V>>	getSeparationPairs()
java.util.Map<SeparationPair<V>,E>	getSeparationPairVirtuelEdgeMap()
java.util.List<HopcroftTarjanSplitComponent<V,E>>	getSplitComponents()
java.util.List<E>	getVirtualEdges()

Methods inherited from class java.lang.Object

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

Constructor Detail

HopcroftTarjanSplitting

public HopcroftTarjanSplitting(Graph<V,E> graph)

HopcroftTarjanSplitting

public HopcroftTarjanSplitting(Graph<V,E> graph,
                               boolean debug)

Method Detail

execute

public void execute()
             throws AlgorithmErrorException

Executes the algorithms and sets values of the properties which contain the results - lists of separation pair and components

Throws:

AlgorithmErrorException - If an inconsistency is detected

getSeparationPairs

public java.util.List<SeparationPair<V>> getSeparationPairs()

Returns:

A list of found separation pairs

getSplitComponents

public java.util.List<HopcroftTarjanSplitComponent<V,E>> getSplitComponents()

Returns:

A list of split components

getSeparationPairVirtuelEdgeMap

public java.util.Map<SeparationPair<V>,E> getSeparationPairVirtuelEdgeMap()

getVirtualEdges

public java.util.List<E> getVirtualEdges()

Returns:

Virtual edges

getPaths

public java.util.List<java.util.List<E>> getPaths()

Returns:

Paths detected in the path searching phase