graph.properties.splitting

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

java.lang.Object

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

Type Parameters:

V - The vertex type

E - The edge type

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

An implementation of Hopcroft-Tarjan's algorithm for finding separation pairs

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
SeparationPairSplitting()

Method Summary

Modifier and Type	Method and Description
java.util.List<SplitPair<V,E>>	findSeaparationPairs(Graph<V,E> graph) Finds all separation pairs of the given graph
java.util.Map<V,java.util.List<E>>	getAdjacency()
java.util.List<E>	getFronds()
int[]	getHighpt()
int[]	getLowpt1()
java.util.Map<V,java.util.List<SplitPair<V,E>>>	getSeparationPairEndVertices()
java.util.List<SplitPair<V,E>>	getSeparationPairs()
java.util.Map<V,java.util.List<SplitPair<V,E>>>	getSeparationPairStartVertices()
DFSTree<V,E>	getTree()
java.util.List<E>	getTreeEdges()

Methods inherited from class java.lang.Object

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

Constructor Detail

SeparationPairSplitting

public SeparationPairSplitting()

Method Detail

findSeaparationPairs

public java.util.List<SplitPair<V,E>> findSeaparationPairs(Graph<V,E> graph)
                                                    throws AlgorithmErrorException

Finds all separation pairs of the given graph

Parameters:

graph - Graph

Returns:

A list of separation pairs of graph graph

Throws:

AlgorithmErrorException - If an inconsistency is detected

getSeparationPairs

public java.util.List<SplitPair<V,E>> getSeparationPairs()

Returns:

A list of found separation pair

getAdjacency

public java.util.Map<V,java.util.List<E>> getAdjacency()

Returns:

Adjacency - mapping of vertices to lists of edges which contains them

getSeparationPairStartVertices

public java.util.Map<V,java.util.List<SplitPair<V,E>>> getSeparationPairStartVertices()

Returns:

A map of vertices and all split pairs containing them as first vertices of the pair

getSeparationPairEndVertices

public java.util.Map<V,java.util.List<SplitPair<V,E>>> getSeparationPairEndVertices()

Returns:

A map of vertices and all split pairs containing them as second vertices of the pair

getTreeEdges

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

Returns:

DFS tree edges

getFronds

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

Returns:

Back edges or fronds

getLowpt1

public int[] getLowpt1()

Returns:

Lowpt1 values

getHighpt

public int[] getHighpt()

Returns:

Highpt values

getTree

public DFSTree<V,E> getTree()

Returns:

DFS tree