Class WeakChordalityInspector<V,E>
- java.lang.Object
-
- org.jgrapht.alg.cycle.WeakChordalityInspector<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.htmlThe 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 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.
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 inspectedgraph
is specified at the construction time and cannot be modified. When the graph is modified externally, the behavior of theWeakChordalityInspector
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 Summary
Constructors Constructor Description WeakChordalityInspector(Graph<V,E> graph)
Creates a weak chordality inspector for thegraph
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description GraphPath<V,E>
getCertificate()
Computes and returns the certificate in the form of a hole or anti-hole in the inspectedgraph
.boolean
isWeaklyChordal()
Check whether the inspectedgraph
is weakly chordal.
-
-
-
Method Detail
-
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.
-
-