Package com.jgalgo.alg.color

Interface ColoringAlgo

All Known Implementing Classes:
ColoringAlgoAbstract, ColoringDSatur, ColoringGreedy, ColoringRecursiveLargestFirst
public interface ColoringAlgo
An algorithm that assign a color to each vertex in a graph such that the endpoints of each edge have different colors.

Given a graph \(G=(V,E)\) a valid coloring is a function \(C:v \rightarrow c\) for any vertex \(v\) in \(V\) where each edge \((u,v)\) in \(E\) satisfy \(C(u) \neq C(v)\). The objective is to minimize the total number of different colors. The problem is NP-hard, but various heuristics exists which give decent results for general graphs and optimal results for special cases.

There is not special result object for this interface, rather the result is a VertexPartition. Each 'block' in the partition is a color, and the vertices in the block are the vertices that have the same color. The number of blocks is the number of different colors used in the coloring.

Use newInstance() to get a default implementation of this interface. 

 
 Graph<String, Integer> g = Graph.newUndirected();
 g.addVertex("Alice");
 g.addVertex("Bob");
 g.addVertex("Charlie");
 g.addVertex("David");
 g.addEdge("Alice", "Bob");
 g.addEdge("Bob", "Charlie");
 g.addEdge("Charlie", "Alice");
 g.addEdge("Charlie", "David");

 Coloring coloringAlg = Coloring.newInstance();
 VertexPartition<String, Integer> colors = coloringAlg.computeColoring(g);
 System.out.println("A valid coloring with " + colors.numberOfBlocks() + " colors was found");
 for (String u : g.vertices()) {
 	System.out.println("The color of vertex " + u + " is " + colors.vertexBlock(u));
 	for (EdgeIter<String, Integer> eit = g.outEdges(u).iterator(); eit.hasNext();) {
 		eit.next();
 		String v = eit.target();
 		assert colors.vertexBlock(u) != colors.vertexBlock(v);
 	}
 }
Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    <V, E> VertexPartition<V,E>
    computeColoring(Graph<V,E> g)
    Assign a color to each vertex of the given graph, while minimizing the number of different colors.
    static <V, E> boolean
    isColoring(Graph<V,E> g, ToIntFunction<V> mapping)
    Check whether a given mapping is a valid coloring of a graph.
    static ColoringAlgo
    newInstance()
    Create a new coloring algorithm object.

  • Method Details

    • computeColoring

      <V, E> VertexPartition<V,E> computeColoring(Graph<V,E> g)
      Assign a color to each vertex of the given graph, while minimizing the number of different colors.

      If g is IntGraph, the returned object is IVertexPartition.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      a valid coloring with (hopefully) small number of different colors
      Throws:
      IllegalArgumentException - if g is directed

    • isColoring

      static <V, E> boolean isColoring(Graph<V,E> g, ToIntFunction<V> mapping)
      Check whether a given mapping is a valid coloring of a graph.

      A valid coloring is first of all a valid VertexPartition, but also for each edge \((u,v)\) in the graph the color of \(u\) is different than the color of \(v\).

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      mapping - a mapping from the vertices of g to colors in range \([0, \textit{colorsNum})\)
      Returns:
      true if mapping is a valid coloring of g, false otherwise

    • newInstance

      static ColoringAlgo newInstance()
      Create a new coloring algorithm object.

      This is the recommended way to instantiate a new ColoringAlgo object.

      Returns:
      a default implementation of ColoringAlgo