- 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.
-
-
Field Summary
Fields Modifier and Type Field Description private GraphPath<V,E>
certificate
Contains a hole or an anti-hole of the graph, if it isn't weakly chordalprivate Graph<V,E>
graph
The inspected graphprivate java.util.List<V>
indices
Inverse of the bijective mapping of vertices onto $\left[0,n-1\right]$private int
m
Edge numberprivate int
n
Vertex numberprivate java.util.Map<V,java.lang.Integer>
vertices
Bijective mapping of vertices onto $\left[0,n-1\right]$private java.lang.Boolean
weaklyChordal
Contains true if the graph is weakly chordal, otherwise false.
-
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 private Pair<java.lang.Integer,java.lang.Integer>
checkLabels(java.util.List<java.util.List<java.lang.Integer>> coConnectedComponents, java.util.List<Pair<java.lang.Integer,java.lang.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
private java.util.List<java.util.List<java.lang.Integer>>
computeCoConnectedComponents(Graph<V,E> graph, java.util.List<Pair<java.lang.Integer,java.lang.Integer>> separator)
Computes the connected components of the complement of the graph induces by the vertices of theseparator
.private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,java.lang.Integer>>,E>>
computeGlobalSeparatorList()
Computes the global separator list of thegraph
.private void
findAntiHole(V source, V targetInSeparator)
Finds an anti-hole in the inspectedgraph
.private java.util.List<V>
findCycle(java.util.Set<V> visited, Graph<V,E> graph, V tarInSep, V tar, V sour, V sourInSep)
Starts the iterative depth-first traversal fromsourInSep
vertex.private GraphPath<V,E>
findHole(Graph<V,E> graph, V sourceInSeparator, V source, V target, V targetInSeparator)
Finds a hole in the specifiedgraph
.private void
findHole(V sourceInSeparator, V source, V target, V targetInSeparator)
Finds a hole in the inspectedgraph
.private java.util.List<java.util.Set<V>>
findSeparators(Graph<V,E> graph, E edge)
Computes and returns all minimal separators in the neighborhood of theedge
in thegraph
.GraphPath<V,E>
getCertificate()
Computes and returns the certificate in the form of a hole or anti-hole in the inspectedgraph
.private java.util.List<java.lang.Integer>
getLabeling(E edge)
Computes the labeling of the neighborhood ofedge
on the verticessource
andtarget
.private java.util.Set<V>
getSeparator(Graph<V,E> graph, V startVertex, java.util.Map<V,java.lang.Byte> dfsMap)
Performs iterative depth-first search starting from thestartVertex
in thegraph
.private void
initMappings()
Initializes the mappings of the verticesboolean
isWeaklyChordal()
Check whether the inspectedgraph
is weakly chordal.private boolean
lazyComputeWeakChordality()
Lazily tests the weak chordality of thegraph
and returns the computed value.private java.util.List<V>
minimizeCycle(Graph<V,E> graph, java.util.List<V> cycle, V tar, V tarInSep, V sour, V sourInSep)
Minimizes thecycle
so that it contains a hole in thegraph
.private java.util.Set<V>
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(java.lang.Integer vertex, java.lang.Integer vertexLabel, java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel, java.util.List<java.lang.Integer> labels)
Moves thevertex
to the next bucket.private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,java.lang.Integer>>,E>>
reformatSeparatorList(java.util.List<java.util.Set<V>> separators, E edge)
Reformats the list oseparators
so that is can be conveniently used by this inspector.private void
reload(java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel, java.util.List<java.lang.Integer> labels, int minLabel)
Moves all vertices from the bucket with labelminLabel
to the bucket with label 0.private void
sortSeparatorsList(java.util.List<Pair<java.util.List<Pair<java.lang.Integer,java.lang.Integer>>,E>> separators)
Sorts theseparators
using bucket sortprivate boolean
unequalSeparators(java.util.List<Pair<java.lang.Integer,java.lang.Integer>> sep1, java.util.List<Pair<java.lang.Integer,java.lang.Integer>> sep2)
Compares two separators for inequality.
-
-
-
Field Detail
-
n
private final int n
Vertex number
-
m
private final int m
Edge number
-
vertices
private java.util.Map<V,java.lang.Integer> vertices
Bijective mapping of vertices onto $\left[0,n-1\right]$
-
indices
private java.util.List<V> indices
Inverse of the bijective mapping of vertices onto $\left[0,n-1\right]$
-
weaklyChordal
private java.lang.Boolean weaklyChordal
Contains true if the graph is weakly chordal, otherwise false. Is null before the first call to theisWeaklyChordal()
.
-
-
Method Detail
-
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
public GraphPath<V,E> 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
private java.util.List<Pair<java.util.List<Pair<java.lang.Integer,java.lang.Integer>>,E>> 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 java.util.List<Pair<java.util.List<Pair<java.lang.Integer,java.lang.Integer>>,E>> reformatSeparatorList(java.util.List<java.util.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
private java.util.List<java.lang.Integer> getLabeling(E edge)
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
private void sortSeparatorsList(java.util.List<Pair<java.util.List<Pair<java.lang.Integer,java.lang.Integer>>,E>> separators)
Sorts theseparators
using bucket sort- Parameters:
separators
- the list of separators to be sorted
-
unequalSeparators
private boolean unequalSeparators(java.util.List<Pair<java.lang.Integer,java.lang.Integer>> sep1, java.util.List<Pair<java.lang.Integer,java.lang.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 java.util.List<java.util.List<java.lang.Integer>> computeCoConnectedComponents(Graph<V,E> graph, java.util.List<Pair<java.lang.Integer,java.lang.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(java.lang.Integer vertex, java.lang.Integer vertexLabel, java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel, java.util.List<java.lang.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
private void reload(java.util.List<java.util.Set<java.lang.Integer>> bucketsByLabel, java.util.List<java.lang.Integer> labels, int minLabel)
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<java.lang.Integer,java.lang.Integer> checkLabels(java.util.List<java.util.List<java.lang.Integer>> coConnectedComponents, java.util.List<Pair<java.lang.Integer,java.lang.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
private void findHole(V sourceInSeparator, V source, V target, V targetInSeparator)
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
private void findAntiHole(V source, V targetInSeparator)
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
private java.util.List<V> findCycle(java.util.Set<V> visited, Graph<V,E> graph, V tarInSep, V tar, V sour, V sourInSep)
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 java.util.List<V> minimizeCycle(Graph<V,E> graph, java.util.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
private java.util.List<java.util.Set<V>> findSeparators(Graph<V,E> graph, E edge)
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
private java.util.Set<V> getSeparator(Graph<V,E> graph, V startVertex, java.util.Map<V,java.lang.Byte> dfsMap)
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
private java.util.Set<V> 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. 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
-
-