Coloring
Graphs.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.
Graphs.ColoringGraphs.degree_greedy_colorGraphs.greedy_colorGraphs.perm_greedy_colorGraphs.random_greedy_color
Graphs.Coloring — Typestruct Coloring{T}Store the number of colors used and mapping from vertex to color
Graphs.degree_greedy_color — Methoddegree_greedy_color(g)Color graph g iteratively in the descending order of the degree of the vertices.
Graphs.greedy_color — Methodgreedy_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.
Graphs.perm_greedy_color — Methodperm_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.
Graphs.random_greedy_color — Methodrandom_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.