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