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

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	ColoringAlgo.Builder	A builder for ColoringAlgo objects.

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, resulting in a valid coloring.
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.Builder	newBuilder()	Create a new coloring algorithm builder.
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, 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

newBuilder

static ColoringAlgo.Builder newBuilder()

Create a new coloring algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build ColoringAlgo objects