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.ColoringLightGraphs.degree_greedy_colorLightGraphs.greedy_colorLightGraphs.perm_greedy_colorLightGraphs.random_greedy_color
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.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.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 $i^{th}$ 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.