Module org.jgrapht.core
Package org.jgrapht.alg.clique

Class ChordalGraphMaxCliqueFinder<V,​E>

  • Type Parameters:
    V - the graph vertex type.
    E - the graph edge type.
    All Implemented Interfaces:
    CliqueAlgorithm<V>
    public class ChordalGraphMaxCliqueFinder<V,​E>
extends java.lang.Object
implements CliqueAlgorithm<V>
    Calculates a maximum cardinality clique in a chordal graph. 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. To compute the clique, this implementation relies on the ChordalityInspector to compute a perfect elimination order. The maximum clique for a chordal graph is computed in $\mathcal{O}(|V| + |E|)$ time. All the methods in this class are invoked in a lazy fashion, meaning that computations are only started once the method gets invoked.

    • Method Detail

      • lazyComputeMaximumClique

        private void lazyComputeMaximumClique()
        Lazily computes some maximum clique of the graph.

      • 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.

      • 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.