graph.properties.splitting

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

java.lang.Object

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

Type Parameters:

V - The vertex type

E - The edge type

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

A class containing methods regarding graph splitting, such as finding cut vertices Some methods need to be rewritten due to being slow

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
Splitting()

Method Summary

Modifier and Type	Method and Description
java.util.List<V>	findAllCutVertices(Graph<V,E> graph) Finds a list of graph's cut vertices A cut vertex is a vertex whose removal would disconnect the remaining graph
java.util.List<SplitComponent<V,E>>	findAllSplitComponents(Graph<V,E> graph, SplitPair<V,E> splitPair)
java.util.List<SplitPair<V,E>>	findAllSplitPairs(Graph<V,E> graph) Deprecated.
java.util.List<SplitPair<V,E>>	maximalSplitPairs(Graph<V,E> graph, E edge) Finds a list of maximal split pair with respect to some edge A maximal split pair with respect to some edge is a split pair not dominated by any other split pair with respect to that edge There may several such pairs
Graph<V,E>	splitGraph(java.util.List<SplitComponent<V,E>> splitComponents, E edge) A split graph of a split pair with respect of some edge is the union of all split components which don't contain that edge
Graph<V,E>	splitGraph(SplitPair<V,E> splitPair, E edge, Graph<V,E> graph) Finds a split graph with respect to the given split pair and edge
boolean	splitPairIsDominantedBy(Graph<V,E> graph, SplitPair<V,E> dominanted, SplitPair<V,E> dominant, E edge) Checks if one split pair is dominated by another given an edge A split pair {u,v} is dominated by another split pair {x,y} if
boolean	testSplitComponents(java.util.List<SplitComponent<V,E>> components, SplitPair<V,E> splitPair) All components should have two vertices in common: split pair vertices and no edges

Methods inherited from class java.lang.Object

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

Constructor Detail

Splitting

public Splitting()

Method Detail

findAllCutVertices

public java.util.List<V> findAllCutVertices(Graph<V,E> graph)

Finds a list of graph's cut vertices A cut vertex is a vertex whose removal would disconnect the remaining graph

Parameters:

graph - The graph

Returns:

A list of cut vertices

findAllSplitPairs

public java.util.List<SplitPair<V,E>> findAllSplitPairs(Graph<V,E> graph)

Deprecated.

Finds graph's split pairs A pair {u,v} of vertices is a split pair if it is an edge in the graph or if it is a separation pair (it increases the number of connected components) in the graph (graph is no longer connected if it is removed)

Parameters:

graph - The graph

Returns:

A list of split pairs

findAllSplitComponents

public java.util.List<SplitComponent<V,E>> findAllSplitComponents(Graph<V,E> graph,
                                                                  SplitPair<V,E> splitPair)

testSplitComponents

public boolean testSplitComponents(java.util.List<SplitComponent<V,E>> components,
                                   SplitPair<V,E> splitPair)

All components should have two vertices in common: split pair vertices and no edges

Parameters:

components - Split components

splitPair - Split pair

Returns:

true if the test shows that everything is in order, false otherwise

splitGraph

public Graph<V,E> splitGraph(java.util.List<SplitComponent<V,E>> splitComponents,
                             E edge)

A split graph of a split pair with respect of some edge is the union of all split components which don't contain that edge

Parameters:

splitComponents - All split components

edge - Edge

Returns:

Split graph

splitGraph

public Graph<V,E> splitGraph(SplitPair<V,E> splitPair,
                             E edge,
                             Graph<V,E> graph)

Finds a split graph with respect to the given split pair and edge

Parameters:

splitPair - Split pair

edge - Edge

graph - Graph

Returns:

Split graph

splitPairIsDominantedBy

public boolean splitPairIsDominantedBy(Graph<V,E> graph,
                                       SplitPair<V,E> dominanted,
                                       SplitPair<V,E> dominant,
                                       E edge)

Checks if one split pair is dominated by another given an edge A split pair {u,v} is dominated by another split pair {x,y} if

Parameters:

graph - The graph

dominanted - Potentially dominated split pair

dominant - Potentially dominant split pair

edge - Edge

Returns:

true if dominated is dominated by @{code other}

maximalSplitPairs

public java.util.List<SplitPair<V,E>> maximalSplitPairs(Graph<V,E> graph,
                                                        E edge)

Finds a list of maximal split pair with respect to some edge A maximal split pair with respect to some edge is a split pair not dominated by any other split pair with respect to that edge There may several such pairs

Parameters:

graph - The graph

edge - The edge with respect to which the pairs are being examined

Returns:

A list of maximal split pairs