Class ChordalityInspector<V,​E>

  • Type Parameters:
    V - the graph vertex type.
    E - the graph edge type.

    public class ChordalityInspector<V,​E>
    extends java.lang.Object
    Tests whether a graph is chordal. A chordal graph is a simple graph in which all cycles of four or more vertices have a chord. A chord is an edge that is not part of the cycle but connects two vertices of the cycle. A graph is chordal if and only if it has a perfect elimination order. A perfect elimination order in a graph is an ordering of the vertices of the graph such that, for each vertex $v$, $v$ and the neighbors of $v$ that occur after $v$ in the order form a clique. This implementation uses either MaximumCardinalityIterator or LexBreadthFirstIterator to compute a perfect elimination order. The desired method is specified during construction time.

    Chordal graphs are a subset of the perfect graphs. They may be recognized in polynomial time, and several problems that are hard on other classes of graphs such as minimum vertex coloring or determining maximum cardinality cliques and independent set can be performed in polynomial time when the input is chordal.

    All methods in this class run in $\mathcal{O}(|V| + |E|)$ time. Determining whether a graph is chordal, as well as computing a perfect elimination order takes $\mathcal{O}(|V| + |E|)$ time, independent of the algorithm (MaximumCardinalityIterator or LexBreadthFirstIterator) used to compute the perfect elimination order.

    All the methods in this class are invoked in a lazy fashion, meaning that computations are only started once the method gets invoked.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void dfsVisit​(java.util.List<V> cycle, java.util.Map<V,​java.lang.Boolean> visited, V finish, V middle, V current)
      Computes some cycle in the graph on the vertices from the domain of the map visited.
      private void findHole​(V a, V b, V c)
      Computes a hole from the vertices of subgraph of the inspected graph with vertices a, b and c on this cycle (there must be no edge between a and c.
      GraphPath<V,​E> getHole()
      A graph which is not chordal, must contain a hole (chordless cycle on 4 or more vertices).
      ChordalityInspector.IterationOrder getIterationOrder()
      Returns the type of iterator used in this ChordalityInspector
      java.util.List<V> getPerfectEliminationOrder()
      Returns a perfect elimination order if one exists.
      private java.util.Set<V> getPredecessors​(java.util.Map<V,​java.lang.Integer> vertexInOrder, V vertex)
      Returns the predecessors of vertex in the order defined by map.
      private java.util.Map<V,​java.lang.Integer> getVertexInOrder​(java.util.List<V> vertexOrder)
      Returns a map containing vertices from the vertexOrder mapped to their indices in vertexOrder.
      boolean isChordal()
      Checks whether the inspected graph is chordal.
      boolean isPerfectEliminationOrder​(java.util.List<V> vertexOrder)
      Checks whether the vertices in the vertexOrder form a perfect elimination order with respect to the inspected graph.
      private boolean isPerfectEliminationOrder​(java.util.List<V> vertexOrder, boolean computeHole)
      Checks whether the vertices in the vertexOrder form a perfect elimination order with respect to the inspected graph.
      private java.util.List<V> lazyComputeOrder()
      Computes vertex order via orderIterator.
      private java.util.List<V> minimizeCycle​(java.util.List<V> cycle)
      Minimizes the cycle represented by the list cycle.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • orderIterator

        private final GraphIterator<V,​E> orderIterator
        Iterator used for producing perfect elimination order.
      • graph

        private final Graph<V,​E> graph
        The inspected graph.
      • chordal

        private boolean chordal
        Contains true if the graph is chordal, otherwise false.
      • order

        private java.util.List<V> order
        Order produced by orderIterator.
      • hole

        private GraphPath<V,​E> hole
        A hole contained in the inspected graph.
    • Constructor Detail

      • ChordalityInspector

        public ChordalityInspector​(Graph<V,​E> graph)
        Creates a chordality inspector for graph, which uses MaximumCardinalityIterator as a default iterator.
        Parameters:
        graph - the graph for which a chordality inspector to be created.
      • ChordalityInspector

        public ChordalityInspector​(Graph<V,​E> graph,
                                   ChordalityInspector.IterationOrder iterationOrder)
        Creates a chordality inspector for graph, which uses an iterator defined by the second parameter as an internal iterator.
        Parameters:
        graph - the graph for which a chordality inspector is to be created.
        iterationOrder - the constant, which defines iterator to be used by this ChordalityInspector.
    • Method Detail

      • isChordal

        public boolean isChordal()
        Checks whether the inspected graph is chordal.
        Returns:
        true if this graph is chordal, otherwise false.
      • getPerfectEliminationOrder

        public java.util.List<V> getPerfectEliminationOrder()
        Returns a perfect elimination order if one exists. The existence of a perfect elimination order certifies that the graph is chordal. This method returns null if the graph is not chordal.
        Returns:
        a perfect elimination order of a graph or null if graph is not chordal.
      • getHole

        public GraphPath<V,​E> getHole()
        A graph which is not chordal, must contain a hole (chordless cycle on 4 or more vertices). The existence of a hole certifies that the graph is not chordal. This method returns a chordless cycle if the graph is not chordal, or null if the graph is chordal.
        Returns:
        a hole if the graph is not chordal, or null if the graph is chordal.
      • isPerfectEliminationOrder

        public boolean isPerfectEliminationOrder​(java.util.List<V> vertexOrder)
        Checks whether the vertices in the vertexOrder form a perfect elimination order with respect to the inspected graph. Returns false otherwise.
        Parameters:
        vertexOrder - the sequence of vertices of the graph.
        Returns:
        true if the graph is chordal and the vertices in vertexOrder are in perfect elimination order, otherwise false.
      • lazyComputeOrder

        private java.util.List<V> lazyComputeOrder()
        Computes vertex order via orderIterator.
        Returns:
        computed order.
      • isPerfectEliminationOrder

        private boolean isPerfectEliminationOrder​(java.util.List<V> vertexOrder,
                                                  boolean computeHole)
        Checks whether the vertices in the vertexOrder form a perfect elimination order with respect to the inspected graph. Returns false otherwise. Computes a hole if the computeHole is true.
        Parameters:
        vertexOrder - the sequence of vertices of graph.
        computeHole - tells whether to compute the hole if the graph isn't chordal.
        Returns:
        true if the graph is chordal and the vertices in vertexOrder are in perfect elimination order.
      • getVertexInOrder

        private java.util.Map<V,​java.lang.Integer> getVertexInOrder​(java.util.List<V> vertexOrder)
        Returns a map containing vertices from the vertexOrder mapped to their indices in vertexOrder.
        Parameters:
        vertexOrder - a list with vertices.
        Returns:
        a mapping of vertices from vertexOrder to their indices in vertexOrder.
      • findHole

        private void findHole​(V a,
                              V b,
                              V c)
        Computes a hole from the vertices of subgraph of the inspected graph with vertices a, b and c on this cycle (there must be no edge between a and c.
        Parameters:
        a - vertex that belongs to the cycle
        b - vertex that belongs to the cycle
        c - vertex that belongs to the cycle
      • dfsVisit

        private void dfsVisit​(java.util.List<V> cycle,
                              java.util.Map<V,​java.lang.Boolean> visited,
                              V finish,
                              V middle,
                              V current)
        Computes some cycle in the graph on the vertices from the domain of the map visited. More precisely, finds some path from middle to finish. The vertex middle isn't the endpoint of any chord in this cycle.
        Parameters:
        cycle - already computed part of the cycle
        visited - the map that defines which vertex has been visited by this method
        finish - the last vertex in the cycle.
        middle - the vertex, which must be adjacent onl
        current - currently examined vertex.
      • minimizeCycle

        private java.util.List<V> minimizeCycle​(java.util.List<V> cycle)
        Minimizes the cycle represented by the list cycle. More precisely it retains first 2 vertices and finds a chordless cycle starting from the third vertex.
        Parameters:
        cycle - vertices of the graph that represent the cycle.
        Returns:
        a chordless cycle
      • getPredecessors

        private java.util.Set<V> getPredecessors​(java.util.Map<V,​java.lang.Integer> vertexInOrder,
                                                 V vertex)
        Returns the predecessors of vertex in the order defined by map. More precisely, returns those of vertex, whose mapped index in map is less then the index of vertex.
        Parameters:
        vertexInOrder - defines the mapping of vertices in graph to their indices in order.
        vertex - the vertex whose predecessors in order are to be returned.
        Returns:
        the predecessors of vertex in order defines by map.
      • getIterationOrder

        public ChordalityInspector.IterationOrder getIterationOrder()
        Returns the type of iterator used in this ChordalityInspector
        Returns:
        the type of iterator used in this ChordalityInspector