Coloring
LightGraphs.jl defines a structure and basic interface for coloring algorithms. Since coloring is a hard problem in the general case, users can extend the behavior and define their own function taking a graph as input and returning the Coloring structure.
#
LightGraphs.Coloring — Type
struct Coloring{T}Store the number of colors used and mapping from vertex to color
#
LightGraphs.degree_greedy_color — Method
degree_greedy_color(g)Color graph g iteratively in the descending order of the degree of the vertices.
#
LightGraphs.greedy_color — Method
greedy_color(g; sort_degree=false, reps = 1)Color graph g based on Greedy Coloring Heuristics
The heuristics can be described as choosing a permutation of the vertices and assigning the lowest color index available iteratively in that order.
If sort_degree is true then the permutation is chosen in reverse sorted order of the degree of the vertices. parallel and reps are irrelevant in this case.
If sort_degree is false then reps colorings are obtained based on random permutations and the one using least colors is chosen.
#
LightGraphs.perm_greedy_color — Method
perm_greedy_color(g, seq)Color graph g according to an order specified by seq using a greedy heuristic. seq[i] = v implies that vertex v is the vertex to be colored.
#
LightGraphs.random_greedy_color — Method
random_greedy_color(g, reps)Color the graph g iteratively in a random order using a greedy heuristic and choose the best coloring out of reps such random colorings.