Class ChordalGraphMaxCliqueFinder<V,E>

java.lang.Object
org.jgrapht.alg.clique.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 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.
  • Field Details

  • Constructor Details

  • Method Details

    • lazyComputeMaximumClique

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

      private Map<V,Integer> getVertexInOrder(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 Set<V> getPredecessors(Map<V,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.
    • getClique

      public CliqueAlgorithm.Clique<V> getClique()
      Returns a maximum cardinality clique of the inspected graph. If the graph isn't chordal, returns null.
      Specified by:
      getClique in interface CliqueAlgorithm<V>
      Returns:
      a maximum clique of the graph if it is chordal, null otherwise.