org.jgrapht.alg.cycle

Class WeakChordalityInspector<V,E>

java.lang.Object

org.jgrapht.alg.cycle.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 Summary

Constructors

Constructor and Description
WeakChordalityInspector(Graph<V,E> graph) Creates a weak chordality inspector for the graph

Method Summary

Modifier and Type	Method and Description
GraphPath<V,E>	getCertificate() Computes and returns the certificate in the form of a hole or anti-hole in the inspected graph.
boolean	isWeaklyChordal() Check whether the inspected graph is weakly chordal.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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