agape.algos

Class Separators<V,E>

java.lang.Object

agape.algos.Algorithms<V,E>

agape.algos.Separators<V,E>

Type Parameters:

V - Vertices type

E - Edges type

public class Separators<V,E>
extends Algorithms<V,E>

This class provides methods for ab-separators problem.

Author:

V. Levorato, J.-F. Lalande, P. Berthome

Constructor Summary

Constructors

Constructor and Description
Separators()

Method Summary

Methods

Modifier and Type	Method and Description
java.util.Set<java.util.Set<V>>	getABSeparators(edu.uci.ics.jung.graph.Graph<V,E> g, V a, V b) Returns the set of minimal ab-separator between vertices a and b in O(n^3) per separator.
java.util.Set<java.util.Set<V>>	getAllMinimalSeparators(edu.uci.ics.jung.graph.Graph<V,E> g) Return all the minimal separators of G.

Methods inherited from class agape.algos.Algorithms

getEdgeFactory, getGraphFactory, getVertexFactory, setEdgeFactoy, setGraphFactoy, setVertexFactoy

Methods inherited from class java.lang.Object

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

Constructor Detail

Separators

public Separators()

Method Detail

getABSeparators

public java.util.Set<java.util.Set<V>> getABSeparators(edu.uci.ics.jung.graph.Graph<V,E> g,
                                              V a,
                                              V b)

Returns the set of minimal ab-separator between vertices a and b in O(n^3) per separator. The implementation is based on an algorithm of Berry, Bordat, Cogis in ("Generating All the Minimal Separators of a Graph", 2000).

Parameters:

g - graph

a - vertex a

b - vertex b

Returns:

a set of minimal ab-separator.

getAllMinimalSeparators

public java.util.Set<java.util.Set<V>> getAllMinimalSeparators(edu.uci.ics.jung.graph.Graph<V,E> g)

Return all the minimal separators of G.

Parameters:

g - graph

Returns:

a set with all minimal separators of g.