Edit on GitHub

API

This is a comprehensive list functions implemented in this library. For a guided introduction to these methods, check out the tutorial first.

Page contents

Coloring

These are the core methods to compute quasi-stable colorings of graphs.

QuasiStableColors.q_color — Method
q_color(
    G::AbstractGraph{T},
    q = 0.0,
    n_colors = Inf,
    weights::SparseMatrixCSC{<:Number,Int} = nothing,
    special =  Set{T}(),
    warm_start = Vector{Vector{T}}(),
)

Compute a quasi-stable coloring for the graph G. Typically, you should set one of:

  • q: maximum q-error allowed
  • n_colors: number of colors to use

Advanced, optional parameters:

  • weights: edge weights to use
  • weighting: whether to prioritize larger colors (i.e. with more members).

false to prioritize colors with the largest error, regardless of color size.

  • warm_start: coloring to refine. If not provided, starts using coarsest

(single color) partitioning.

  • special: node IDs which will always get their own colors.
source

Coloring an example graph:

using QuasiStableColors: q_color
using Graphs

# Make a chain graph
G = SimpleGraph(4)
add_edge!(G, 1, 1)
add_edge!(G, 1, 2)
add_edge!(G, 2, 3)
add_edge!(G, 3, 4)
add_edge!(G, 4, 4)

# Color it
C = q_color(G, q=2.0)
Quasi-stable coloring(color count=1, max q-error=0.0)

For the specific case of bipartite graphs, consider:

Finally, for comparison with prior work, we provide the following method.

Maximum-flow

This method for approximating maximum-flow in a flow network.

QuasiStableColors.Flow.lifted_maxflow — Function
lifted_maxflow(
    solver,
    G::Graph,
    s::Int,
    t::Int,
    q = 0.0,
    n_colors = Inf,
    weights::SparseMatrixCSC{<:Number,Int} = nothing,
)

Return an equivalent approximate maximum flow problem from s to t in flow network G. Capacities defined using weights; if none provided, unit capacities assumed. Uses a quasi-stable coloring with maximum error q or n_colors colors, whichever is smaller. Solver should be GraphsFlows.maximum_flow or similiar function.

Example of computing the approximate maximum flow: using GraphsFlows: maximumflow fapprox, _ = liftedmaxflow(maximumflow, G, s, t, C, n_colors=25)

source

An example of how to compute an approximate maximum flow:

using QuasiStableColors.Flow: lifted_maxflow
using Graphs
using GraphsFlows: maximum_flow

E = [Edge(1,2), Edge(1, 3), Edge(1, 4), Edge(2, 5), Edge(3, 5), Edge(4, 5)]
G = SimpleGraphFromIterator(E)

lifted_maxflow(maximum_flow, G, 1, 5; q=1.0)
3.0

Betweenness centrality

This method is provided for approximating betweenness centrality.

To compute the estimated betweenness centralities on a sample graph:

using Graphs
using QuasiStableColors.Centrality: approx_betweenness_centrality

# Construct example graph
E = [Edge(1, 5), Edge(2, 4), Edge(2, 5), Edge(2, 8), Edge(3, 5), Edge(3, 9),
    Edge(6, 9), Edge(7, 8), Edge(8, 9)]
G = SimpleGraphFromIterator(E)

# Compute approximate centrality
C₀ = approx_betweenness_centrality(G, q=0.0)
println("Approximate centrality: $C₀")

# Compute exact centrality for comparision
using Graphs: betweenness_centrality
C = betweenness_centrality(G, normalize=false)
println("      Exact centrality: $C")
Approximate centrality: [0.0, 11.5, 4.0, 0.0, 6.5, 0.0, 0.0, 10.5, 11.5]
      Exact centrality: [0.0, 11.0, 4.0, 0.0, 9.0, 0.0, 0.0, 11.0, 9.0]

Linear programming

This section details methods related to approximating linear optimization.

QuasiStableColors.Optimize.lifted_minimize — Function
lifted_minimize(
    A,
    b::Vector,
    c::Vector,
    q=0.0,
    n_colors=Inf,
)

Approximate the linear program $\min c^T x \text{ where } A x \geq b, x \geq 0$.

Uses a quasi-stable coloring with maximum error q or n_colors colors, whichever is smaller.

source

Consider the following example linear system from our paper:

\[\begin{align*} \text{maximize } & 9x_1+10x_2+50x_3 \\ \text{where } & 4x_1+8x_2+2x_3 \leq 20 \\ & 6x_1 + 5x_2 + x_3 \leq 20 \\ & 7x_1 + 4x_2 + 2x_3 \leq 21 \\ & 3x_1 + x_2 + 22x_3 \leq 50 \\ & 2x_1 + 3x_2 + 21x_3 \leq 51 \end{align*}\]

This system has optimum value $c^T x^\ast = 128.2$. Let's compute the approximate minimum:

using QuasiStableColors.Optimize: lifted_maximize
using Tulip

solver = Tulip.Optimizer()

A = [4.0 8 2; 6 5 1; 7 4 2; 3 1 22; 2 3 21]
b = [20.0, 20, 21, 50, 51]
c = [9.0, 10, 50]
z = lifted_maximize(solver, A, b, c; q=5.0)
"estimated value: $z"
"estimated value: 130.19901199654973"

This gives us an estimated value of $c^T x^\ast$ within $1\%$ of the true value.