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:

Wikipedia

Method Summary

All Methods Static Methods Instance Methods Abstract Methods
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 Detail
  - 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

Interface ColoringAlgo

Method Summary

Method Detail

computeColoring

isColoring

newInstance