Package org.graph4j.coloring

Class BacktrackColoringBase

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.coloring.ExactColoringBase

org.graph4j.coloring.BacktrackColoringBase

All Implemented Interfaces:

ColoringAlgorithm

Direct Known Subclasses:

BacktrackBandwithColoring, BacktrackColoring, BacktrackEquitableColoring

public abstract class BacktrackColoringBase
extends ExactColoringBase

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 (DSatur). 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

Modifier and Type	Class	Description
protected class	BacktrackColoringBase.Worker

Field Summary

Fields

Modifier and Type	Field	Description
protected long	nodesExplored
protected List<BacktrackColoringBase.Worker>	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
BacktrackColoringBase(Graph graph)
BacktrackColoringBase(Graph graph, long timeLimit)
BacktrackColoringBase(Graph graph, Coloring initialColoring)
BacktrackColoringBase(Graph graph, Coloring initialColoring, long timeLimit)

Method Summary

Modifier and Type	Method	Description
protected Node	createNode(Node parent, int vertex, int color, Domain[] domains, Coloring coloring)
protected Node	init(int numColors)
protected boolean	prepareRootColoring(Coloring rootColoring, int numColors)
protected abstract boolean	propagateAssignment(int v, int color, Node node, int[][] assignQueue)
protected void	propagateFailure(Node node)	Deprecated.
protected boolean	propagationForcedColor(int u, int color, Node node)
protected int	removeColor(int u, int color, Node node, int[][] assignQueue, int queuePos)
protected void	solve(int numColors)

Methods inherited from class org.graph4j.coloring.ExactColoringBase

checkTime, findAllColorings, findColoring, findColoring, getInstance, 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

Field Details

workers

protected List<BacktrackColoringBase.Worker> workers

nodesExplored

protected long nodesExplored

Constructor Details

BacktrackColoringBase

public BacktrackColoringBase(Graph graph)

BacktrackColoringBase

public BacktrackColoringBase(Graph graph,
 long timeLimit)

BacktrackColoringBase

public BacktrackColoringBase(Graph graph,
 Coloring initialColoring)

BacktrackColoringBase

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

Method Details

solve

protected void solve(int numColors)

Specified by:

solve in class ExactColoringBase

prepareRootColoring

protected boolean prepareRootColoring(Coloring rootColoring,
 int numColors)

init

protected Node init(int numColors)

createNode

protected Node createNode(Node parent,
 int vertex,
 int color,
 Domain[] domains,
 Coloring coloring)

propagateAssignment

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

removeColor

protected int removeColor(int u,
 int color,
 Node node,
 int[][] assignQueue,
 int queuePos)

propagationForcedColor

protected boolean propagationForcedColor(int u,
 int color,
 Node node)

propagateFailure

@Deprecated
protected void propagateFailure(Node node)

Deprecated.