Package com.jgalgo

Interface Coloring

public interface Coloring

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})$.

 
 Graph g = GraphFactory.newUndirected().newGraph();
 int v1 = g.addVertex();
 int v2 = g.addVertex();
 int v3 = g.addVertex();
 int v4 = g.addVertex();
 g.addEdge(v1, v2);
 g.addEdge(v2, v3);
 g.addEdge(v3, v1);
 g.addEdge(v3, v4);

 Coloring coloringAlg = Coloring.newBuilder().build();
 Coloring.Result colors = coloringAlg.computeColoring(g);
 System.out.println("A valid coloring with " + colors.colorsNum() + " colors was found");
 for (int u : g.vertices()) {
 	System.out.println("The color of vertex " + u + " is " + colors.colorOf(u));
 	for (EdgeIter eit = g.outEdges(u).iterator(); eit.hasNext();) {
 		eit.nextInt();
 		int v = eit.target();
 		assert colors.colorOf(u) != colors.colorOf(v);
 	}
 }
 

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	Coloring.Builder	A builder for Coloring objects.
static interface	Coloring.Result	A coloring result containing a color for each vertex.

Method Summary

Modifier and Type	Method	Description
Coloring.Result	computeColoring(Graph g)	Assign a color to each vertex of the given graph, resulting in a valid coloring.
static Coloring.Builder	newBuilder()	Create a new coloring algorithm builder.

Method Detail

computeColoring

Coloring.Result computeColoring(Graph g)

Assign a color to each vertex of the given graph, resulting in a valid coloring.

Parameters:

g - a graph

Returns:

a valid coloring with (hopefully) small number of different colors

Throws:

IllegalArgumentException - if g is directed

newBuilder

static Coloring.Builder newBuilder()

Create a new coloring algorithm builder.

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

Returns:

a new builder that can build Coloring objects