Package org.jgrapht.alg.cycle

Class WeakChordalityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    public class WeakChordalityInspector<V,​E>
extends 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.

    Author:
    Timofey Chudakov

    • Constructor Detail

      • WeakChordalityInspector

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

    • Method Detail

      • 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