- 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 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 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
FieldsModifier and TypeFieldDescriptionContains a hole or an anti-hole of the graph, if it isn't weakly chordalThe inspected graphInverse of the bijective mapping of vertices onto $\left[0,n-1\right]$private final int
Edge numberprivate final int
Vertex numberBijective mapping of vertices onto $\left[0,n-1\right]$private Boolean
Contains true if the graph is weakly chordal, otherwise false. -
Constructor Summary
ConstructorsConstructorDescriptionWeakChordalityInspector
(Graph<V, E> graph) Creates a weak chordality inspector for thegraph
-
Method Summary
Modifier and TypeMethodDescriptionFor a given coconnected component of theseparator
checks whether every vertex in it is seen by al least one vertex of the edge that is separated by theseparator
Computes the connected components of the complement of the graph induces by the vertices of theseparator
.Computes the global separator list of thegraph
.private void
findAntiHole
(V source, V targetInSeparator) Finds an anti-hole in the inspectedgraph
.Starts the iterative depth-first traversal fromsourInSep
vertex.Finds a hole in the specifiedgraph
.private void
Finds a hole in the inspectedgraph
.findSeparators
(Graph<V, E> graph, E edge) Computes and returns all minimal separators in the neighborhood of theedge
in thegraph
.Computes and returns the certificate in the form of a hole or anti-hole in the inspectedgraph
.getLabeling
(E edge) Computes the labeling of the neighborhood ofedge
on the verticessource
andtarget
.Performs iterative depth-first search starting from thestartVertex
in thegraph
.private void
Initializes the mappings of the verticesboolean
Check whether the inspectedgraph
is weakly chordal.private boolean
Lazily tests the weak chordality of thegraph
and returns the computed value.Minimizes thecycle
so that it contains a hole in thegraph
.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
(Integer vertex, Integer vertexLabel, List<Set<Integer>> bucketsByLabel, List<Integer> labels) Moves thevertex
to the next bucket.reformatSeparatorList
(List<Set<V>> separators, E edge) Reformats the list oseparators
so that is can be conveniently used by this inspector.private void
Moves all vertices from the bucket with labelminLabel
to the bucket with label 0.private void
Sorts theseparators
using bucket sortprivate boolean
Compares two separators for inequality.
-
Field Details
-
n
private final int nVertex number -
m
private final int mEdge number -
graph
The inspected graph -
vertices
Bijective mapping of vertices onto $\left[0,n-1\right]$ -
indices
Inverse of the bijective mapping of vertices onto $\left[0,n-1\right]$ -
weaklyChordal
Contains true if the graph is weakly chordal, otherwise false. Is null before the first call to theisWeaklyChordal()
. -
certificate
Contains a hole or an anti-hole of the graph, if it isn't weakly chordal
-
-
Constructor Details
-
WeakChordalityInspector
Creates a weak chordality inspector for thegraph
- Parameters:
graph
- the inspectedgraph
-
-
Method Details
-
initMappings
private void initMappings()Initializes the mappings of the vertices -
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 anti-hole in the inspectedgraph
. Returns null if the inspected graph is weakly chordal. Note: certificate is computed lazily. -
lazyComputeWeakChordality
private boolean lazyComputeWeakChordality()Lazily tests the weak chordality of thegraph
and returns the computed value.- Returns:
- true, if the inspected
graph
is weakly chordal, otherwise false.
-
computeGlobalSeparatorList
Computes the global separator list of thegraph
. 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 List<Pair<List<Pair<Integer,Integer>>, reformatSeparatorListE>> (List<Set<V>> separators, E edge) Reformats the list oseparators
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 theedge
substitutes all vertices for their indices in the numeration defined byvertices
. Pairs every separator with theedge
.- Parameters:
separators
- the list of minimal separators in the neighborhood of theedge
edge
- the edge, which neighborhood contains minimal separators fromseparators
- Returns:
- the reformatted list of minimal separators
-
getLabeling
Computes the labeling of the neighborhood ofedge
on the verticessource
andtarget
. Vertex from the neighborhood is labeled with "1" if it sees onlysource
, "2" is it sees onlytarget
, 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
Sorts theseparators
using bucket sort- Parameters:
separators
- the list of separators to be sorted
-
unequalSeparators
private boolean unequalSeparators(List<Pair<Integer, Integer>> sep1, List<Pair<Integer, Integer>> sep2) Compares two separators for inequality. Labeling of the vertices in the separators isn't considered- Parameters:
sep1
- first separatorsep2
- second separator- Returns:
- true, if the separators are unequal, false otherwise
-
computeCoConnectedComponents
private List<List<Integer>> computeCoConnectedComponents(Graph<V, E> graph, List<Pair<Integer, Integer>> separator) Computes the connected components of the complement of the graph induces by the vertices of theseparator
. 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(Integer vertex, Integer vertexLabel, List<Set<Integer>> bucketsByLabel, List<Integer> labels) Moves thevertex
to the next bucket.- Parameters:
vertex
- the vertex to be movedvertexLabel
- the label of thevertex
bucketsByLabel
- the buckets, in which vertices are storedlabels
- the labels of the vertices
-
reload
Moves all vertices from the bucket with labelminLabel
to the bucket with label 0. Clears the bucket with labelminLabel
. Updates the labeling accordingly.- Parameters:
bucketsByLabel
- the buckets vertices are stored inlabels
- the labels of the verticesminLabel
- the minimum value of the non-empty bucket
-
checkLabels
private Pair<Integer,Integer> checkLabels(List<List<Integer>> coConnectedComponents, List<Pair<Integer, Integer>> separator) For a given coconnected component of theseparator
checks whether every vertex in it is seen by al least one vertex of the edge that is separated by theseparator
- Parameters:
coConnectedComponents
- the set of the coconected components of theseparator
separator
- minimal separator of some edge in thegraph
- Returns:
- true if the condition described above holds, false otherwise
-
findHole
Finds a hole in the inspectedgraph
. VerticessourceInSeparator
,source
,target
andtargetInSeparator
belong to the computes hole. They are used to correctly find a hole in the inspected graph.- Parameters:
sourceInSeparator
- vertex on the holesource
- vertex on the holetarget
- vertex on the holetargetInSeparator
- vertex on the hole
-
findAntiHole
Finds an anti-hole in the inspectedgraph
. Verticessource
andtargetInSeparator
specify an edge, which belongs to the anti-hole in the complement of thegraph
. 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 thegraph
.- Parameters:
source
- endpoint of the edge that belongs to the anti-holetargetInSeparator
- 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 specifiedgraph
. VerticessourceInSeparator
,source
,target
andtargetInSeparator
belong to the computes hole. They are used to correctly find a hole in the specifiedgraph
.- Parameters:
sourceInSeparator
- vertex on the holesource
- vertex on the holetarget
- vertex on the holetargetInSeparator
- vertex on the hole- Returns:
- the computed hole on the
graph
-
findCycle
Starts the iterative depth-first traversal fromsourInSep
vertex. Tries to build a cycle with the vertices, which aren't adjacent to thetar
andsour
. 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 alreadygraph
- the graph the search is performed ontarInSep
- the end point of the cycletar
- the vertex, which can't be adjacent to the vertices in the cyclesour
- the vertex, which can't be adjacent to the vertices in the cyclesourInSep
- the vertex the search is started from- Returns:
- the computed cycle, which contains a hole
-
minimizeCycle
private List<V> minimizeCycle(Graph<V, E> graph, List<V> cycle, V tar, V tarInSep, V sour, V sourInSep) Minimizes thecycle
so that it contains a hole in thegraph
. Verticestar
,tarInSep
,sour
andsourInSep
belong to the final result.- Parameters:
graph
- the graph, which contains vertices fromcycle
cycle
- the cycle to minimizetar
- vertex, which should belong to the final resulttarInSep
- vertex, which should belong to the final resultsour
- vertex, which should belong to the final resultsourInSep
- vertex, which should belong to the final result- Returns:
- a list of vertices, which defines a hole in the
graph
-
findSeparators
Computes and returns all minimal separators in the neighborhood of theedge
in thegraph
. The result may contain duplicate separators.- Parameters:
graph
- the graph to search minimal separators inedge
- 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
Performs iterative depth-first search starting from thestartVertex
in thegraph
. 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 onstartVertex
- the vertex to start depth-first traversal fromdfsMap
- the depth-first vertex labeling- Returns:
- the computed separator, which consists of all encountered red vertices
-
neighborhoodSetOf
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 inedge
- 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
-