Package org.graph4j.coloring

Class BacktrackColoring

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.coloring.ExactColoringBase

org.graph4j.coloring.BacktrackColoringBase

org.graph4j.coloring.BacktrackColoring

All Implemented Interfaces:

ColoringAlgorithm

public class BacktrackColoring
extends BacktrackColoringBase

Attempts at finding the optimum coloring of a graph using a systematic exploration of the search space. The backtracking is implemented in a non-recursive manner, using multiple threads.

First, a maximal clique is computed that offers a lower bound q of the chromatic number. The colors of the vertices in the maximal clique are fixed before the backtracking algorithm starts. Secondly, an initial coloring is computed using a simple heuristic. This gives an upper bound kof the chromatic number. Next, the algorithm will attemtp to color the graph using a number of colors ranging from k-1 to q, determining the optimal coloring.

A time limit may be imposed. If the algorithm stops due to the time limit, it will return the best coloring found until then.

Author:

Cristian Frăsinaru

Nested Class Summary

Nested classes/interfaces inherited from class org.graph4j.coloring.BacktrackColoringBase

BacktrackColoringBase.Worker

Field Summary

Fields inherited from class org.graph4j.coloring.BacktrackColoringBase

nodesExplored, workers

Fields inherited from class org.graph4j.coloring.ExactColoringBase

components, initialColoring, outputEnabled, solutions, solutionsLimit, startTime, timeExpired, timeLimit

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
BacktrackColoring(Graph graph)
BacktrackColoring(Graph graph, long timeLimit)
BacktrackColoring(Graph graph, Coloring initialColoring)
BacktrackColoring(Graph graph, Coloring initialColoring, long timeLimit)

Method Summary

Modifier and Type	Method	Description
protected BacktrackColoring	getInstance(Graph graph, long timeLimit)
protected boolean	propagateAssignment(int v, int color, Node node, int[][] assignQueue)

Methods inherited from class org.graph4j.coloring.BacktrackColoringBase

createNode, init, prepareRootColoring, propagateFailure, propagationForcedColor, removeColor, solve

Methods inherited from class org.graph4j.coloring.ExactColoringBase

checkTime, findAllColorings, findColoring, findColoring, getMaximalClique, getSolutionsLimit, isOutputEnabled, isTimeExpired, setOutputEnabled, solveDisconnected

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.coloring.ColoringAlgorithm

getGraph, getHeuristicColoring, getLowerBound, isOptimalityEnsured, isSolvingComponents, isStoppingOnFailure, isValid

Constructor Details

BacktrackColoring

public BacktrackColoring(Graph graph)

BacktrackColoring

public BacktrackColoring(Graph graph,
 long timeLimit)

BacktrackColoring

public BacktrackColoring(Graph graph,
 Coloring initialColoring)

BacktrackColoring

public BacktrackColoring(Graph graph,
 Coloring initialColoring,
 long timeLimit)

Method Details

getInstance

protected BacktrackColoring getInstance(Graph graph,
 long timeLimit)

Specified by:

getInstance in class ExactColoringBase

propagateAssignment

protected boolean propagateAssignment(int v,
 int color,
 Node node,
 int[][] assignQueue)

Specified by:

propagateAssignment in class BacktrackColoringBase