 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
The following definitions of are equivalent:
 A graph is weakly chordal (weakly triangulated) if neither it nor its complement contains a chordless cycles with five or more vertices.
 A 2pair in a graph is a pair of nonadjacent 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 2pair.
For more details, refer to: Hayward, R.B. Weakly triangulated graphs, Journal of Combinatorial Theory, Series B, vol 39, Issue 3, pp 200208, 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 antihole. The running time of finding a hole is $\mathcal{O}(V + E)$ and of finding an antihole  $\mathcal{O}(E^2)$ in the worst case.
 Author:
 Timofey Chudakov

Constructor Summary
ConstructorDescriptionWeakChordalityInspector
(Graph<V, E> graph) Creates a weak chordality inspector for thegraph

Method Summary
Modifier and TypeMethodDescriptionComputes and returns the certificate in the form of a hole or antihole in the inspectedgraph
.boolean
Check whether the inspectedgraph
is weakly chordal.

Constructor Details

WeakChordalityInspector
Creates a weak chordality inspector for thegraph
 Parameters:
graph
 the inspectedgraph


Method Details

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

getCertificate
Computes and returns the certificate in the form of a hole or antihole in the inspectedgraph
. Returns null if the inspected graph is weakly chordal. Note: certificate is computed lazily.
