Class ChordalGraphMinimalVertexSeparatorFinder<V,E>
- java.lang.Object
-
- org.jgrapht.alg.cycle.ChordalGraphMinimalVertexSeparatorFinder<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
public class ChordalGraphMinimalVertexSeparatorFinder<V,E> extends java.lang.Object
Allows obtaining a mapping of all minimal vertex separators of a graph to their multiplicitiesIn the context of this implementation following definitions are used:
- A set of vertices $S$ of a graph $G=(V, E)$ is called a u-v separator, if vertices $u$ and $v$ in the induced graph on vertices $V(G) - S$ are in different connected components.
- A set $S$ is called a minimal u-v separator if it is a u-v separator and no proper subset of $S$ is a u-v separator.
- A set $S$ is called a minimal vertex separator if it is minimal u-v separator for some vertices $u$ and $v$ of the graph $G$.
- A set of vertices $S$ is called a minimal separator if no proper subset of $S$ is a separator of the graph $G$.
Let $\sigma = (v_1, v_2, \dots, v_n)$ be some perfect elimination order (peo) of the graph $G = (V, E)$. The induced graph on vertices $(v_1, v_2, \dots, v_i)$ with respect to peo $\sigma$ is denoted as $G_i$. The predecessors set of vertex $v$ with respect to peo $\sigma$ is denoted as $N(v, \sigma)$. A set $B$ is called a base set with respect to $\sigma$, is there exist some vertex $v$ with $t = \sigma(v)$ such that $N(v, \sigma) = B$ and B is not a maximal clique in $G_{t-1}$. The vertices which satisfy conditions described above are called dependent vertices with respect to $\sigma$. The cardinality of the set of dependent vertices is called a multiplicity of the base set $B$. The multiplicity of a minimal vertex separator indicates the number of different pairs of vertices separated by it.The definitions of a base set and a minimal vertex separator in the context of chordal graphs are equivalent.
For more information on the topic see: Kumar, P. Sreenivasa & Madhavan, C. E. Veni. (1998). Minimal vertex separators of chordal graphs. Discrete Applied Mathematics. 89. 155-168. 10.1016/S0166-218X(98)00123-1.
The running time of the algorithm is $\mathcal{O}(\omega(G)(|V| + |E|))$, where $\omega(G)$ is the size of a maximum clique of the graph $G$.
- See Also:
ChordalityInspector
-
-
Field Summary
Fields Modifier and Type Field Description private ChordalityInspector<V,E>
chordalityInspector
ChordalityInspector
for testing chordality of thegraph
private Graph<V,E>
graph
The graph in which minimal vertex separators to searched inprivate java.util.Map<java.util.Set<V>,java.lang.Integer>
minimalSeparatorsWithMultiplicities
A mapping of minimal separators to their multiplicities
-
Constructor Summary
Constructors Constructor Description ChordalGraphMinimalVertexSeparatorFinder(Graph<V,E> graph)
Creates newChordalGraphMinimalVertexSeparatorFinder
instance.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.Set<java.util.Set<V>>
getMinimalSeparators()
Computes a set of all minimal separators of thegraph
and returns it.java.util.Map<java.util.Set<V>,java.lang.Integer>
getMinimalSeparatorsWithMultiplicities()
Computes a mapping of all minimal vertex separators of thegraph
and returns it.private java.util.Set<V>
getPredecessors(java.util.Map<V,java.lang.Integer> vertexInOrder, V vertex)
Returns the predecessors ofvertex
in the order defined bymap
.private java.util.Map<V,java.lang.Integer>
getVertexInOrder(java.util.List<V> vertexOrder)
Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.private void
lazyComputeMinimalSeparatorsWithMultiplicities()
Lazy computes a set of all minimal separators and a mapping of all minimal vertex separators to their multiplicities
-
-
-
Field Detail
-
chordalityInspector
private final ChordalityInspector<V,E> chordalityInspector
ChordalityInspector
for testing chordality of thegraph
-
minimalSeparatorsWithMultiplicities
private java.util.Map<java.util.Set<V>,java.lang.Integer> minimalSeparatorsWithMultiplicities
A mapping of minimal separators to their multiplicities
-
-
Constructor Detail
-
ChordalGraphMinimalVertexSeparatorFinder
public ChordalGraphMinimalVertexSeparatorFinder(Graph<V,E> graph)
Creates newChordalGraphMinimalVertexSeparatorFinder
instance. TheChordalityInspector
used in this implementation uses theMaximumCardinalityIterator
iterator- Parameters:
graph
- the graph minimal separators to search in
-
-
Method Detail
-
getMinimalSeparators
public java.util.Set<java.util.Set<V>> getMinimalSeparators()
Computes a set of all minimal separators of thegraph
and returns it. Returns null if thegraph
isn't chordal.- Returns:
- computed set of all minimal separators, or null if the
graph
isn't chordal
-
getMinimalSeparatorsWithMultiplicities
public java.util.Map<java.util.Set<V>,java.lang.Integer> getMinimalSeparatorsWithMultiplicities()
Computes a mapping of all minimal vertex separators of thegraph
and returns it. Returns null if thegraph
isn't chordal.- Returns:
- computed mapping of all minimal separators to their multiplicities, or null if the
graph
isn't chordal
-
lazyComputeMinimalSeparatorsWithMultiplicities
private void lazyComputeMinimalSeparatorsWithMultiplicities()
Lazy computes a set of all minimal separators and a mapping of all minimal vertex separators to their multiplicities
-
getVertexInOrder
private java.util.Map<V,java.lang.Integer> getVertexInOrder(java.util.List<V> vertexOrder)
Returns a map containing vertices from thevertexOrder
mapped to their indices invertexOrder
.- Parameters:
vertexOrder
- a list with vertices.- Returns:
- a mapping of vertices from
vertexOrder
to their indices invertexOrder
.
-
getPredecessors
private java.util.Set<V> getPredecessors(java.util.Map<V,java.lang.Integer> vertexInOrder, V vertex)
Returns the predecessors ofvertex
in the order defined bymap
. More precisely, returns those ofvertex
, whose mapped index inmap
is less then the index ofvertex
.- Parameters:
vertexInOrder
- defines the mapping of vertices ingraph
to their indices in order.vertex
- the vertex whose predecessors in order are to be returned.- Returns:
- the predecessors of
vertex
in order defines bymap
.
-
-