Package com.jgalgo.alg

Interface ColoringAlgo

  • public interface ColoringAlgo
    An algorithm that assign a color to each vertex in a graph while avoiding identical color for any pair of adjacent vertices.

    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.

    Each color is represented as an integer in range \([0, \textit{colorsNum})\).

    Use newInstance() to get a default implementation of this interface. A builder obtained via newBuilder() may support different options to obtain different implementations. 

     
 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:
    Wikipedia

    • Method Detail

      • computeColoring

        <V,​E> VertexPartition<V,​E> computeColoring​(Graph<V,​E> g)
        Assign a color to each vertex of the given graph, resulting in a valid coloring.

        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. The ColoringAlgo.Builder might support different options to obtain different implementations.

        Returns:
        a default implementation of ColoringAlgo