Module org.jgrapht.core
Package 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.

  • Field Details

    • n

      private final int n
      Vertex number

    • m

      private final int m
      Edge number

    • graph

      private Graph<V,E> graph
      The inspected graph

    • vertices

      private Map<V,Integer> vertices
      Bijective mapping of vertices onto $\left[0,n-1\right]$

    • indices

      private List<V> indices
      Inverse of the bijective mapping of vertices onto $\left[0,n-1\right]$

    • weaklyChordal

      private Boolean weaklyChordal
      Contains true if the graph is weakly chordal, otherwise false. Is null before the first call to the isWeaklyChordal().

    • certificate

      private GraphPath<V,E> certificate
      Contains a hole or an anti-hole of the graph, if it isn't weakly chordal

  • Constructor Details

    • WeakChordalityInspector

      public WeakChordalityInspector(Graph<V,E> graph)
      Creates a weak chordality inspector for the graph
      Parameters:
      graph - the inspected graph

  • Method Details

    • initMappings

      private void initMappings()
      Initializes the mappings of the vertices

    • 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

    • lazyComputeWeakChordality

      private boolean lazyComputeWeakChordality()
      Lazily tests the weak chordality of the graph and returns the computed value.
      Returns:
      true, if the inspected graph is weakly chordal, otherwise false.

    • computeGlobalSeparatorList

      private List<Pair<List<Pair<Integer,Integer>>,E>> computeGlobalSeparatorList()
      Computes the global separator list of the graph. 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>>,E>> reformatSeparatorList(List<Set<V>> separators, E edge)
      Reformats the list o separators 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 the edge substitutes all vertices for their indices in the numeration defined by vertices. Pairs every separator with the edge.
      Parameters:
      separators - the list of minimal separators in the neighborhood of the edge
      edge - the edge, which neighborhood contains minimal separators from separators
      Returns:
      the reformatted list of minimal separators

    • getLabeling

      private List<Integer> getLabeling(E edge)
      Computes the labeling of the neighborhood of edge on the vertices source and target. Vertex from the neighborhood is labeled with "1" if it sees only source, "2" is it sees only target, 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(List<Pair<List<Pair<Integer,Integer>>,E>> separators)
      Sorts the separators 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 separator
      sep2 - 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 the separator. 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 the vertex to the next bucket.
      Parameters:
      vertex - the vertex to be moved
      vertexLabel - the label of the vertex
      bucketsByLabel - the buckets, in which vertices are stored
      labels - the labels of the vertices

    • reload

      private void reload(List<Set<Integer>> bucketsByLabel, List<Integer> labels, int minLabel)
      Moves all vertices from the bucket with label minLabel to the bucket with label 0. Clears the bucket with label minLabel. Updates the labeling accordingly.
      Parameters:
      bucketsByLabel - the buckets vertices are stored in
      labels - the labels of the vertices
      minLabel - 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 the separator checks whether every vertex in it is seen by al least one vertex of the edge that is separated by the separator
      Parameters:
      coConnectedComponents - the set of the coconected components of the separator
      separator - minimal separator of some edge in the graph
      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 inspected graph. Vertices sourceInSeparator, source, target and targetInSeparator belong to the computes hole. They are used to correctly find a hole in the inspected graph.
      Parameters:
      sourceInSeparator - vertex on the hole
      source - vertex on the hole
      target - vertex on the hole
      targetInSeparator - vertex on the hole

    • findAntiHole

      private void findAntiHole(V source, V targetInSeparator)
      Finds an anti-hole in the inspected graph. Vertices source and targetInSeparator specify an edge, which belongs to the anti-hole in the complement of the graph. 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 the graph.
      Parameters:
      source - endpoint of the edge that belongs to the anti-hole
      targetInSeparator - 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 specified graph. Vertices sourceInSeparator, source, target and targetInSeparator belong to the computes hole. They are used to correctly find a hole in the specified graph.
      Parameters:
      sourceInSeparator - vertex on the hole
      source - vertex on the hole
      target - vertex on the hole
      targetInSeparator - vertex on the hole
      Returns:
      the computed hole on the graph

    • findCycle

      private List<V> findCycle(Set<V> visited, Graph<V,E> graph, V tarInSep, V tar, V sour, V sourInSep)
      Starts the iterative depth-first traversal from sourInSep vertex. Tries to build a cycle with the vertices, which aren't adjacent to the tar and sour. 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 already
      graph - the graph the search is performed on
      tarInSep - the end point of the cycle
      tar - the vertex, which can't be adjacent to the vertices in the cycle
      sour - the vertex, which can't be adjacent to the vertices in the cycle
      sourInSep - 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 the cycle so that it contains a hole in the graph. Vertices tar, tarInSep, sour and sourInSep belong to the final result.
      Parameters:
      graph - the graph, which contains vertices from cycle
      cycle - the cycle to minimize
      tar - vertex, which should belong to the final result
      tarInSep - vertex, which should belong to the final result
      sour - vertex, which should belong to the final result
      sourInSep - vertex, which should belong to the final result
      Returns:
      a list of vertices, which defines a hole in the graph

    • findSeparators

      private List<Set<V>> findSeparators(Graph<V,E> graph, E edge)
      Computes and returns all minimal separators in the neighborhood of the edge in the graph. The result may contain duplicate separators.
      Parameters:
      graph - the graph to search minimal separators in
      edge - 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 Set<V> getSeparator(Graph<V,E> graph, V startVertex, Map<V,Byte> dfsMap)
      Performs iterative depth-first search starting from the startVertex in the graph. 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 on
      startVertex - the vertex to start depth-first traversal from
      dfsMap - the depth-first vertex labeling
      Returns:
      the computed separator, which consists of all encountered red vertices

    • neighborhoodSetOf

      private 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 in
      edge - 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