Class ChordalGraphColoring<V,E>

java.lang.Object
org.jgrapht.alg.color.ChordalGraphColoring<V,E>
Type Parameters:
V - the graph vertex type.
E - the graph edge type.
All Implemented Interfaces:
VertexColoringAlgorithm<V>

public class ChordalGraphColoring<V,E> extends Object implements VertexColoringAlgorithm<V>
Calculates a minimum vertex coloring for 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 vertex coloring, this implementation relies on the ChordalityInspector to compute a perfect elimination order. The vertex coloring 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

    • lazyComputeColoring

      private void lazyComputeColoring()
      Lazily computes the coloring 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.
    • getColoring

      public VertexColoringAlgorithm.Coloring<V> getColoring()
      Returns a minimum vertex coloring of the inspected graph. If the graph isn't chordal, returns null. The number of colors used in the coloring equals the chromatic number of the input graph.
      Specified by:
      getColoring in interface VertexColoringAlgorithm<V>
      Returns:
      a coloring of the graph if it is chordal, null otherwise.
    • getPerfectEliminationOrder

      public List<V> getPerfectEliminationOrder()
      Returns the perfect elimination order used to create the coloring (if one exists). This method returns null if the graph is not chordal.
      Returns:
      the perfect elimination order used to create the coloring, or null if graph is not chordal.