Class WeakChordalityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class WeakChordalityInspector<V,​E>
    extends java.lang.Object
    Tests whether a graph is weakly chordal. Weakly chordal graphs are also known as weakly triangulated graphs. Triangulated in the context of chordality has a different meaning than triangulated in the context of planarity, where it refers to a maximal planar graph, see: http://mathworld.wolfram.com/TriangulatedGraph.html

    The following definitions of are equivalent:

    1. A graph is weakly chordal (weakly triangulated) if neither it nor its complement contains a chordless cycles with five or more vertices.
    2. A 2-pair in a graph is a pair of non-adjacent vertices $x$, $y$ such that every chordless path has exactly two edges. A graph is weakly chordal if every connected induced subgraph $H$ that is not a complete graph, contains a 2-pair.
    Chordal and weakly chordal graphs are perfect.
    For more details, refer to: Hayward, R.B. Weakly triangulated graphs, Journal of Combinatorial Theory, Series B, vol 39, Issue 3, pp 200-208, 1985.

    The implementation in this class is based on: Lars Severin Skeide (2002) Recognizing weakly chordal graphs. Candidate Scientist Thesis in Informatics. Department of Informatics, University of Bergen, Norway. The terminology used in this implementation is consistent with the one used in this thesis.

    Both the runtime complexity and space complexity of the algorithm implemented in this class is $\mathcal{O}(|E|^2)$.
    The inspected graph is specified at the construction time and cannot be modified. When the graph is modified externally, the behavior of the WeakChordalityInspector is undefined.

    In the case the inspected graph in not weakly chordal, this inspector provides a certificate in the form of some hole or anti-hole. The running time of finding a hole is $\mathcal{O}(|V| + |E|)$ and of finding an anti-hole - $\mathcal{O}(|E|^2)$ in the worst case.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private GraphPath<V,​E> certificate
      Contains a hole or an anti-hole of the graph, if it isn't weakly chordal
      private Graph<V,​E> graph
      The inspected graph
      private java.util.List<V> indices
      Inverse of the bijective mapping of vertices onto $\left[0,n-1\right]$
      private int m
      Edge number
      private int n
      Vertex number
      private java.util.Map<V,​java.lang.Integer> vertices
      Bijective mapping of vertices onto $\left[0,n-1\right]$
      private java.lang.Boolean weaklyChordal
      Contains true if the graph is weakly chordal, otherwise false.
    • Constructor Summary

      Constructors 
      Constructor Description
      WeakChordalityInspector​(Graph<V,​E> graph)
      Creates a weak chordality inspector for the graph
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private Pair<java.lang.Integer,​java.lang.Integer> checkLabels​(java.util.List<java.util.List<java.lang.Integer>> coConnectedComponents, java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> separator)
      For a given coconnected component of the separator checks whether every vertex in it is seen by al least one vertex of the edge that is separated by the separator
      private java.util.List<java.util.List<java.lang.Integer>> computeCoConnectedComponents​(Graph<V,​E> graph, java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> separator)
      Computes the connected components of the complement of the graph induces by the vertices of the separator.
      private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,​java.lang.Integer>>,​E>> computeGlobalSeparatorList()
      Computes the global separator list of the graph.
      private void findAntiHole​(V source, V targetInSeparator)
      Finds an anti-hole in the inspected graph.
      private java.util.List<V> findCycle​(java.util.Set<V> visited, Graph<V,​E> graph, V tarInSep, V tar, V sour, V sourInSep)
      Starts the iterative depth-first traversal from sourInSep vertex.
      private GraphPath<V,​E> findHole​(Graph<V,​E> graph, V sourceInSeparator, V source, V target, V targetInSeparator)
      Finds a hole in the specified graph.
      private void findHole​(V sourceInSeparator, V source, V target, V targetInSeparator)
      Finds a hole in the inspected graph.
      private java.util.List<java.util.Set<V>> findSeparators​(Graph<V,​E> graph, E edge)
      Computes and returns all minimal separators in the neighborhood of the edge in the graph.
      GraphPath<V,​E> getCertificate()
      Computes and returns the certificate in the form of a hole or anti-hole in the inspected graph.
      private java.util.List<java.lang.Integer> getLabeling​(E edge)
      Computes the labeling of the neighborhood of edge on the vertices source and target.
      private java.util.Set<V> getSeparator​(Graph<V,​E> graph, V startVertex, java.util.Map<V,​java.lang.Byte> dfsMap)
      Performs iterative depth-first search starting from the startVertex in the graph.
      private void initMappings()
      Initializes the mappings of the vertices
      boolean isWeaklyChordal()
      Check whether the inspected graph is weakly chordal.
      private boolean lazyComputeWeakChordality()
      Lazily tests the weak chordality of the graph and returns the computed value.
      private java.util.List<V> minimizeCycle​(Graph<V,​E> graph, java.util.List<V> cycle, V tar, V tarInSep, V sour, V sourInSep)
      Minimizes the cycle so that it contains a hole in the graph.
      private java.util.Set<V> neighborhoodSetOf​(Graph<V,​E> g, E edge)
      Returns a set of vertices that are neighbors of the source of the specified edge or of the target of specified edge.
      private void putToNextBucket​(java.lang.Integer vertex, java.lang.Integer vertexLabel, java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel, java.util.List<java.lang.Integer> labels)
      Moves the vertex to the next bucket.
      private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,​java.lang.Integer>>,​E>> reformatSeparatorList​(java.util.List<java.util.Set<V>> separators, E edge)
      Reformats the list o separators so that is can be conveniently used by this inspector.
      private void reload​(java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel, java.util.List<java.lang.Integer> labels, int minLabel)
      Moves all vertices from the bucket with label minLabel to the bucket with label 0.
      private void sortSeparatorsList​(java.util.List<Pair<java.util.List<Pair<java.lang.Integer,​java.lang.Integer>>,​E>> separators)
      Sorts the separators using bucket sort
      private boolean unequalSeparators​(java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> sep1, java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> sep2)
      Compares two separators for inequality.
      • Methods inherited from class java.lang.Object

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

      • n

        private final int n
        Vertex number
      • m

        private final int m
        Edge number
      • graph

        private Graph<V,​E> graph
        The inspected graph
      • vertices

        private java.util.Map<V,​java.lang.Integer> vertices
        Bijective mapping of vertices onto $\left[0,n-1\right]$
      • indices

        private java.util.List<V> indices
        Inverse of the bijective mapping of vertices onto $\left[0,n-1\right]$
      • weaklyChordal

        private java.lang.Boolean weaklyChordal
        Contains true if the graph is weakly chordal, otherwise false. Is null before the first call to the isWeaklyChordal().
      • certificate

        private GraphPath<V,​E> certificate
        Contains a hole or an anti-hole of the graph, if it isn't weakly chordal
    • Constructor Detail

      • WeakChordalityInspector

        public WeakChordalityInspector​(Graph<V,​E> graph)
        Creates a weak chordality inspector for the graph
        Parameters:
        graph - the inspected graph
    • Method Detail

      • initMappings

        private void initMappings()
        Initializes the mappings of the vertices
      • isWeaklyChordal

        public boolean isWeaklyChordal()
        Check whether the inspected graph is weakly chordal. Note: this value is computed lazily.
        Returns:
        true, if the inspected graph is weakly chordal, otherwise false.
      • getCertificate

        public GraphPath<V,​E> getCertificate()
        Computes and returns the certificate in the form of a hole or anti-hole in the inspected graph. Returns null if the inspected graph is weakly chordal. Note: certificate is computed lazily.
        Returns:
        a hole or anti-hole in the inspected graph, null if the graph is weakly chordal
      • lazyComputeWeakChordality

        private boolean lazyComputeWeakChordality()
        Lazily tests the weak chordality of the graph and returns the computed value.
        Returns:
        true, if the inspected graph is weakly chordal, otherwise false.
      • computeGlobalSeparatorList

        private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,​java.lang.Integer>>,​E>> computeGlobalSeparatorList()
        Computes the global separator list of the graph. More precisely, for every edge $e$ in the $G = (V, E)$ computes list of minimal separators $S_e$ in the neighborhood of $e$ and then concatenates these lists. Note: the result may contain duplicates
        Returns:
        the list of minimal separators of every edge $e$ in the inspected graph
      • reformatSeparatorList

        private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,​java.lang.Integer>>,​E>> reformatSeparatorList​(java.util.List<java.util.Set<V>> separators,
                                                                                                                                    E edge)
        Reformats the list o separators so that is can be conveniently used by this inspector. More precisely, in every separator from the list of minimal separators in the neighborhood of the edge substitutes all vertices for their indices in the numeration defined by vertices. Pairs every separator with the edge.
        Parameters:
        separators - the list of minimal separators in the neighborhood of the edge
        edge - the edge, which neighborhood contains minimal separators from separators
        Returns:
        the reformatted list of minimal separators
      • getLabeling

        private java.util.List<java.lang.Integer> getLabeling​(E edge)
        Computes the labeling of the neighborhood of edge on the vertices source and target. Vertex from the neighborhood is labeled with "1" if it sees only source, "2" is it sees only target, and "3" if it sees both vertices.
        Parameters:
        edge - the edge, whose neighborhood is to be labeled
        Returns:
        the computed labeling with the respect to the rule described above
      • sortSeparatorsList

        private void sortSeparatorsList​(java.util.List<Pair<java.util.List<Pair<java.lang.Integer,​java.lang.Integer>>,​E>> separators)
        Sorts the separators using bucket sort
        Parameters:
        separators - the list of separators to be sorted
      • unequalSeparators

        private boolean unequalSeparators​(java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> sep1,
                                          java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> sep2)
        Compares two separators for inequality. Labeling of the vertices in the separators isn't considered
        Parameters:
        sep1 - first separator
        sep2 - second separator
        Returns:
        true, if the separators are unequal, false otherwise
      • computeCoConnectedComponents

        private java.util.List<java.util.List<java.lang.Integer>> computeCoConnectedComponents​(Graph<V,​E> graph,
                                                                                               java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> separator)
        Computes the connected components of the complement of the graph induces by the vertices of the separator. They are also called "coconnected components". The running time is $\mathcal{O}(|V| + |E|)$.
        Parameters:
        separator - the separators, whose coconnected components are computed
        Returns:
        the coconected of the separator
      • putToNextBucket

        private void putToNextBucket​(java.lang.Integer vertex,
                                     java.lang.Integer vertexLabel,
                                     java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel,
                                     java.util.List<java.lang.Integer> labels)
        Moves the vertex to the next bucket.
        Parameters:
        vertex - the vertex to be moved
        vertexLabel - the label of the vertex
        bucketsByLabel - the buckets, in which vertices are stored
        labels - the labels of the vertices
      • reload

        private void reload​(java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel,
                            java.util.List<java.lang.Integer> labels,
                            int minLabel)
        Moves all vertices from the bucket with label minLabel to the bucket with label 0. Clears the bucket with label minLabel. Updates the labeling accordingly.
        Parameters:
        bucketsByLabel - the buckets vertices are stored in
        labels - the labels of the vertices
        minLabel - the minimum value of the non-empty bucket
      • checkLabels

        private Pair<java.lang.Integer,​java.lang.Integer> checkLabels​(java.util.List<java.util.List<java.lang.Integer>> coConnectedComponents,
                                                                            java.util.List<Pair<java.lang.Integer,​java.lang.Integer>> separator)
        For a given coconnected component of the separator checks whether every vertex in it is seen by al least one vertex of the edge that is separated by the separator
        Parameters:
        coConnectedComponents - the set of the coconected components of the separator
        separator - minimal separator of some edge in the graph
        Returns:
        true if the condition described above holds, false otherwise
      • findHole

        private void findHole​(V sourceInSeparator,
                              V source,
                              V target,
                              V targetInSeparator)
        Finds a hole in the inspected graph. Vertices sourceInSeparator, source, target and targetInSeparator belong to the computes hole. They are used to correctly find a hole in the inspected graph.
        Parameters:
        sourceInSeparator - vertex on the hole
        source - vertex on the hole
        target - vertex on the hole
        targetInSeparator - vertex on the hole
      • findAntiHole

        private void findAntiHole​(V source,
                                  V targetInSeparator)
        Finds an anti-hole in the inspected graph. Vertices source and targetInSeparator specify an edge, which belongs to the anti-hole in the complement of the graph. Then the hole in the complement of the graph is computed in the graph's complement in the same way a hole is computed in the graph.
        Parameters:
        source - endpoint of the edge that belongs to the anti-hole
        targetInSeparator - endpoint of the edge that belongs to the anti-hole
      • findHole

        private GraphPath<V,​E> findHole​(Graph<V,​E> graph,
                                              V sourceInSeparator,
                                              V source,
                                              V target,
                                              V targetInSeparator)
        Finds a hole in the specified graph. Vertices sourceInSeparator, source, target and targetInSeparator belong to the computes hole. They are used to correctly find a hole in the specified graph.
        Parameters:
        sourceInSeparator - vertex on the hole
        source - vertex on the hole
        target - vertex on the hole
        targetInSeparator - vertex on the hole
        Returns:
        the computed hole on the graph
      • findCycle

        private java.util.List<V> findCycle​(java.util.Set<V> visited,
                                            Graph<V,​E> graph,
                                            V tarInSep,
                                            V tar,
                                            V sour,
                                            V sourInSep)
        Starts the iterative depth-first traversal from sourInSep vertex. Tries to build a cycle with the vertices, which aren't adjacent to the tar and sour. This condition is used in order to ensure that the cycle contains a hole, to which it is later minimized.
        Parameters:
        visited - defines which vertices have been visited already
        graph - the graph the search is performed on
        tarInSep - the end point of the cycle
        tar - the vertex, which can't be adjacent to the vertices in the cycle
        sour - the vertex, which can't be adjacent to the vertices in the cycle
        sourInSep - the vertex the search is started from
        Returns:
        the computed cycle, which contains a hole
      • minimizeCycle

        private java.util.List<V> minimizeCycle​(Graph<V,​E> graph,
                                                java.util.List<V> cycle,
                                                V tar,
                                                V tarInSep,
                                                V sour,
                                                V sourInSep)
        Minimizes the cycle so that it contains a hole in the graph. Vertices tar, tarInSep, sour and sourInSep belong to the final result.
        Parameters:
        graph - the graph, which contains vertices from cycle
        cycle - the cycle to minimize
        tar - vertex, which should belong to the final result
        tarInSep - vertex, which should belong to the final result
        sour - vertex, which should belong to the final result
        sourInSep - vertex, which should belong to the final result
        Returns:
        a list of vertices, which defines a hole in the graph
      • findSeparators

        private java.util.List<java.util.Set<V>> findSeparators​(Graph<V,​E> graph,
                                                                E edge)
        Computes and returns all minimal separators in the neighborhood of the edge in the graph. The result may contain duplicate separators.
        Parameters:
        graph - the graph to search minimal separators in
        edge - the edge, whose neighborhood is being explored
        Returns:
        the list of all minimal separators in the neighborhood of the edge. The resulted list may contain duplicates.
      • getSeparator

        private java.util.Set<V> getSeparator​(Graph<V,​E> graph,
                                              V startVertex,
                                              java.util.Map<V,​java.lang.Byte> dfsMap)
        Performs iterative depth-first search starting from the startVertex in the graph. Adds every encountered red vertex to the resulting separator. Doesn't process red vertices. Marks all white vertices with black color.
        Parameters:
        graph - the graph dfs is performed on
        startVertex - the vertex to start depth-first traversal from
        dfsMap - the depth-first vertex labeling
        Returns:
        the computed separator, which consists of all encountered red vertices
      • neighborhoodSetOf

        private java.util.Set<V> neighborhoodSetOf​(Graph<V,​E> g,
                                                   E edge)
        Returns a set of vertices that are neighbors of the source of the specified edge or of the target of specified edge. The endpoints of the specified edge aren't included in the result.
        Parameters:
        g - the graph to look for neighbors in
        edge - the edge to get the neighbors of
        Returns:
        a set of vertices that are neighbors of at least one endpoint of the specified edge. The endpoints of the specified edge aren't included in the result