Class ChordalGraphMinimalVertexSeparatorFinder<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - 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 multiplicities

    In 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
    • 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 the graph and returns it.
      java.util.Map<java.util.Set<V>,​java.lang.Integer> getMinimalSeparatorsWithMultiplicities()
      Computes a mapping of all minimal vertex separators of the graph and returns it.
      private java.util.Set<V> getPredecessors​(java.util.Map<V,​java.lang.Integer> vertexInOrder, V vertex)
      Returns the predecessors of vertex in the order defined by map.
      private java.util.Map<V,​java.lang.Integer> getVertexInOrder​(java.util.List<V> vertexOrder)
      Returns a map containing vertices from the vertexOrder mapped to their indices in vertexOrder.
      private void lazyComputeMinimalSeparatorsWithMultiplicities()
      Lazy computes a set of all minimal separators and a mapping of all minimal vertex separators to their multiplicities
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private final Graph<V,​E> graph
        The graph in which minimal vertex separators to searched in
      • 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 new ChordalGraphMinimalVertexSeparatorFinder instance. The ChordalityInspector used in this implementation uses the MaximumCardinalityIterator 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 the graph and returns it. Returns null if the graph 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 the graph and returns it. Returns null if the graph 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 the vertexOrder mapped to their indices in vertexOrder.
        Parameters:
        vertexOrder - a list with vertices.
        Returns:
        a mapping of vertices from vertexOrder to their indices in vertexOrder.
      • getPredecessors

        private java.util.Set<V> getPredecessors​(java.util.Map<V,​java.lang.Integer> vertexInOrder,
                                                 V vertex)
        Returns the predecessors of vertex in the order defined by map. More precisely, returns those of vertex, whose mapped index in map is less then the index of vertex.
        Parameters:
        vertexInOrder - defines the mapping of vertices in graph to their indices in order.
        vertex - the vertex whose predecessors in order are to be returned.
        Returns:
        the predecessors of vertex in order defines by map.