Implementation of degree saturation algorithm for graph coloring problem. Two modes are available - greedy and branch-and-bound. Algorithm involves sets intersection operations done via bitwise-logic with custom class TenseBinArray, see tbarray.py.
color_graph function in dsatur.py
-
edges- list of tuples (int, int); represent graph's edges; -
blocksize1- (optional) int, default is 100; parameter for storing binary data associated with vertices, for more details see implementation; -
blocksize2- (optional) int, default is 100; parameter for storing binary data associated with colors, for more details see implementation; -
mode- (optional) string, available modes are"greedy"and"bnb", default is"greedy"; defines version of algorithm to run -
timeout- (optional) int or None, default is None; defines limit for algorithm's work time in seconds, when exceeded best solution found so far will be returned or None; -
improve- (optional) int or None, default is None; optional parameter forbnbmode, if passed to the function then algorithm will stop working when solution with less or equal colors thanG - improveis found whereGstands for solution found by greedy approach; if solution with this property is not found, best found solution will be returned.
- tuple (num, color) where
numis number of colors used andcoloris an array of ints so thatcolor[i]is the color assigned to i'th vertex
>>> from dsatur import color_graph
>>> color_graph([(4,3),(0,1),(1,2),(1,3)])
(2, [1, 0, 1, 1, 0])