Tutorial

Let's explore how to use the QuasiStableColors library with an example.

Installation

First, install the library. One option is to run the following code:

using Pkg
Pkg.add("QuasiStableColors")

After installing activate the library:

using QuasiStableColors

Let's use QSC as shorthand for the library name:

const QSC = QuasiStableColors

Coloring Graphs

Let's create a simple example graph.

using Graphs
n = 8
g = Graphs.SimpleGraphs.dorogovtsev_mendes(n, seed=0)

using GraphMakie, CairoMakie
graphplot(g)

Now, let's generate a quasi-stable coloring C where we allow at most one edge error (i.e. $q=1$).

C = QSC.q_color(g, q=1.0)

Quasi-stable coloring(color count=4, max q-error=1.0)

We get a four-partition coloring. How are the nodes grouped?

P = QSC.partitions(C)

4-element Vector{Vector{Int64}}:
 [5, 6, 7, 8, 1]
 [4]
 [2]
 [3]

Let's assign a unique visual color to each group:

using Colors
palette = distinguishable_colors(length(P))
color_map = Array{Colorant}(undef, nv(g))
for (i, x) in enumerate(P)
    color_map[x] .= palette[i]
end

and draw the graph again:

graphplot(g, node_color=color_map)

Summary Graphs

Let's build a summary graph using the coloring C. Each supernode represents one color:

G_super, weights = QSC.super_graph(C)

Approximation

This section on how to use the coloring for graph algorithms is upcoming–for now see the maximum-flow section of the API reference as an example.