# API

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

## Coloring

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

QuasiStableColors.q_colorMethod
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 undirected graph G. Typically, you should set one of:

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

Optional parameters:

• warm_start: coloring to refine. If not provided, start using trivial

(single color) partitioning assumed.

• weights: edge weights to use
source

Coloring an example graph:

using QuasiStableColors: q_color
using Graphs

# Make a chain graph
G = SimpleGraph(4)

# Color it
P = q_color(G, q=2.0)
1-element Vector{Vector{Int64}}:
[4, 2, 3, 1]

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_maxflowFunction
lifted_maxflow(
G::Graph,
s::Int,
t::Int,
q = 0.0,
n_colors = Inf,
weights::SparseMatrixCSC{<:Number,Int} = nothing,
)

Compute the approximate maximum flow 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.

source

An example of how to compute an approximate maximum flow:

using QuasiStableColors.Flow: lifted_maxflow
using Graphs

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

lifted_maxflow(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_minimizeFunction
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

A = [4 8 2; 6 5 1; 7 4 2; 3 1 22; 2 3 21]
b = [20, 20, 21, 50, 51]
c = [9, 10, 50]
z = lifted_maximize(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.