Algorithms

GraphsOptim — Module

GraphsOptim

A package for graph optimization algorithms that rely on mathematical programming.

source

Flow

GraphsOptim.min_cost_flow — Function

min_cost_flow(
    g, vertex_demand, edge_cost, edge_min_capacity, edge_max_capacity;
    integer, optimizer
)

Compute a minimum cost flow over a directed graph.

Arguments

g::Graphs.AbstractGraph: a directed graph G = (V, E)
vertex_demand::AbstractVector: a vector in Rⱽ giving the flow requested by each vertex (should be positive for sinks, negative for sources and zero elsewhere)
edge_cost::AbstractMatrix: a vector in Rᴱ giving the cost of a unit of flow on each edge
edge_min_capacity::AbstractMatrix: a vector in Rᴱ giving the minimum flow allowed on each edge
edge_max_capacity::AbstractMatrix: a vector in Rᴱ giving the maximum flow allowed on each edge

Keyword arguments

integer::Bool: whether the flow should be integer-valued or real-valued
optimizer: JuMP-compatible solver (default is HiGHS.Optimizer)

source

GraphsOptim.min_cost_flow! — Function

min_cost_flow!(
    model,
    g, vertex_demand, edge_cost, edge_min_capacity, edge_max_capacity;
    var_name, integer
)

Modify a JuMP model by adding the variable, constraints and objective necessary to compute a minimum cost flow over a directed graph.

The flow variable will be named var_name, see min_cost_flow for details on the other arguments.

source

We denote by:

$f$ the edge flow variable
$c$ the edge cost
$a$ and $b$ the min and max edge capacity
$d$ the vertex demand

The objective function is

\[\min_{f \in \mathbb{R}^E} \sum_{(u, v) \in E} c(u, v) f(u, v)\]

The edge capacity constraint dictates that for all $(u, v) \in E$,

\[a(u, v) \leq f(u, v) \leq b(u, v)\]

The flow conservation constraint with node demand dictates that for all $v \in V$,

\[f^-(v) = d(v) + f^+(v)\]

where the incoming flow $f^-(v)$ and outgoing flow $f^+(v)$ are defined as

\[f^-(v) = \sum_{u \in N^-(v)} f(u, v) \quad \text{and} \quad f^+(v) = \sum_{w \in N^+(v)} f(v, w)\]

Shortest Path

GraphsOptim.shortest_path — Function

shortest_path(
	g, source, target, edge_cost;
    integer, optimizer
)

Compute the shortest path from a source to a target vertex over a graph. Returns a sequence of vertices from source to destination.

Arguments

g::Graphs.AbstractGraph: a directed or undirected graph G = (V, E)
source::Int: source vertex of the path
target::Int: target vertex of the path
edge_cost::AbstractMatrix: a vector in Rᴱ giving the cost of traversing the edge

Keyword arguments

integer::Bool: whether the path should be integer-valued or real-valued (default is true)
optimizer: JuMP-compatible solver (default is HiGHS.Optimizer)

source

GraphsOptim.shortest_path! — Function

shortest_path!(
	model,
	g, source, target, edge_cost;
    var_name, integer
)

Modify a JuMP model by adding the variable, constraints and objective necessary to compute the shortest path between 2 vertices over a graph.

The edge selection variable will be named var_name, see shortest_path for details on the other arguments.

source

A special case of minimum cost flow without edge capacities, and where vertex demands are $0$ everywhere except at the source ($-1$) and target ($+1$).

Assignment

Work in progress

Come back later!

GraphsOptim.min_cost_assignment — Function

min_cost_assignment(
    edge_cost;
    optimizer
)

Compute a minimum cost assignment over a bipartite graph.

Arguments

edge_cost::AbstractMatrix: a matrix in Rᵁˣⱽ giving the cost of matching u ∈ U to v ∈ V

Keyword arguments

integer::Bool: whether the flow should be integer-valued or real-valued
optimizer: JuMP-compatible solver (default is HiGHS.Optimizer)

source

GraphsOptim.min_cost_assignment! — Function

min_cost_assignment!(
    model,
    edge_cost;
    var_name, integer
)

Modify a JuMP model by adding the variable, constraints and objective necessary to compute a minimum cost assignment over a bipartite graph.

The assignment variable will be named var_name, see min_cost_assignment for details on the other arguments.

source

Minimum Vertex Cover

GraphsOptim.min_vertex_cover — Function

min_vertex_cover(
    g, optimizer
)

Compute a minimum vertex cover of an undirected graph.

Arguments

g::Graphs.AbstractGraph: an undirected graph G = (V, E)

Keyword arguments

optimizer: JuMP-compatible solver (default is HiGHS.Optimizer)

source

GraphsOptim.min_vertex_cover! — Function

min_vertex_cover!(
    model, g;
    var_name
)

Modify a JuMP model by adding the variable, constraints and objective necessary to compute a minimum vertex cove of an undirected graph.

The vertex cover indicator variable will be named var_name

source

Finds a subset $S \subset V$ of vertices of an undirected graph $G = (V,E)$ such that $\forall (u,v) \in E: u \in S \lor v \in S$

Maximum weight clique

GraphsOptim.maximum_weight_clique — Function

maximum_weight_clique(g; optimizer, binary, vertex_weights)

Computes a maximum-weighted clique of g.

source

GraphsOptim.maximum_weight_clique! — Function

maximum_weight_clique!(model, g; var_name)

Computes in-place in the JuMP model a maximum-weighted clique of g. An optional vertex_weights vector can be passed to the graph, defaulting to uniform weights (computing a maximum size clique).

source

A clique is a subset $S \subset V$ of vertices of an undirected graph $G = (V,E)$ such that $\forall (u,v) \in S: (u, v) \in E$. We search for the clique maximizing the total weight of selected vertices.

Maximum Weight Independent Set

GraphsOptim.maximum_weight_independent_set — Function

maximum_weight_independent_set(g; optimizer, binary, vertex_weights)

Computes a maximum-weighted independent set or stable set of g.

source

GraphsOptim.maximum_weight_independent_set! — Function

maximum_independent_set!(model, g; var_name)

Computes in-place in the JuMP model a maximum-weighted independent set of g. An optional vertex_weights vector can be passed to the graph, defaulting to uniform weights (computing a maximum size independent set).

source

Finds a subset $S \subset V$ of vertices of maximal weight of an undirected graph $G = (V,E)$ such that $\forall (u,v) \in E: u \notin S \lor v \notin S$.

Graph matching

Work in progress

Come back later!

GraphsOptim.graph_matching — Function

graph_matching(
    algo, A, B;
    optimizer, P_init, max_iter, tol,
    max_iter_sinkhorn, regularizer
)

Compute an approximately optimal alignment between two graphs using one of two variants of Frank-Wolfe (FAQ or GOAT)

The output is a tuple that contains:

the permutation matrix P defining the alignment;
the distance between the permuted graphs;
a boolean indicating if the algorithm converged.

Arguments

algo: allows dispatch based on the choice of algorithm, either FAQ() or GOAT()
A: the adjacency matrix of the first graph
B: the adjacency matrix of the second graph

Keyword arguments

For both algorithms:

optimizer: JuMP-compatible solver (default is HiGHS.Optimizer)
P_init: initialization matrix (default value is a flat doubly stochastic matrix).
max_iter: maximum iterations of the Frank-Wolfe method (default value is 30).
tol: tolerance for the convergence (default value is 0.1).

Only for GOAT:

regularization: penalty coefficient in the Sinkhorn algorithm (default value is 100.0).
max_iter_sinkhorn: maximum iterations of the Sinkhorn algorithm (default value is 500).

References

FAQ: Algorithm 1 of https://arxiv.org/pdf/2111.05366.pdf
GOAT: Algorithm 3 of https://arxiv.org/pdf/2111.05366.pdf

source

GraphsOptim.graph_matching_step_size — Function

graph_matching_step_size(A, B, P, Q)

Given the adjacency matrices A and B, the doubly stochastic matrix P and the direction matrix Q, return the step size of the Frank-Wolfe method for graph matching algorithms.

source

Coloring

GraphsOptim.fractional_chromatic_number — Function

fractional_chromatic_number(g; optimizer)

Compute the fractional chromatic number of a graph. Gives the same result as fractional_clique_number, though one function may run faster than the other. Beware: this can run very slowly for graphs of any substantial size.

Keyword arguments

optimizer: JuMP-compatible solver (default is HiGHS.Optimizer)

References

https://mathworld.wolfram.com/FractionalChromaticNumber.html

source

GraphsOptim.fractional_clique_number — Function

fractional_clique_number(g; optimizer)

Compute the fractional clique number of a graph. Gives the same result as fractional_chromatic_number, though one function may run faster than the other. Beware: this can run very slowly for graphs of any substantial size.

Keyword arguments