`ErdosExtras.minimum_weight_perfect_bmatching`

— Method`minimum_weight_perfect_bmatching(g, b[, w]; cutoff=Inf)`

Given a graph `g`

and an edgemap `w`

containing the weights associated to each edge, returns the perfect `b`

-matching with the minimum total weight.

A perfect `b`

-matching `M`

is a collection of edges in `g`

such that every vertex has exactly `b`

incident edges in `M`

.

If `w`

is not given, all edges will be considered to have weight one (results in max cardinality b-matching).

Edges `e`

with no associated value in `w`

or with `w[e] > cutoff`

will not be considered for the matching.

The algorithm uses Linear Programming to solve the linear relaxation of the problem first, then eventually refines the solution with an Integer Programming solver.

The efficiency of the algorithm depends on the input graph:

- If the graph is bipartite, then the LP relaxation is integral.
- If the graph is not bipartite, then an IP may be required to refine the solution

and the computation time may grow exponentially.

The package JuMP.jl and one of its supported solvers are required.

Returns a tuple `(status, W, match)`

containing:

- a solve
`status`

(indicating whether the problem was solved to optimality) - the tototal weight
`W`

of the matching - a vector of vectors
`match`

, where`match[v]`

contains the`b`

neighbors of`v`

in the optimal matching.

**Example**

```
julia> g = CompleteGraph(30)
julia> w = EdgeMap(g, e -> rand())
julia> status, W, match = minimum_weight_perfect_bmatching(g, 2, w)
```

`ErdosExtras.minimum_weight_perfect_matching`

— Method`minimum_weight_perfect_matching(g, weights::AEdgeMap{T}; cutoff=typemax{T}) where {T<:Real}`

Given a graph `g`

and an edgemap `weights`

containing non-negative weights associated to edges, returns a matching with the mimimum total weight among the ones containing exactly `nv(g)/2`

edges.

Edges in `g`

not present in `weights`

will not be considered for the matching. To reduce computational time, a `cutoff`

argument can be given. Only edges with weight lower than `cutoff`

will be considered for the matching.

This function relies on the BlossomV.jl package, a julia wrapper around Kolmogorov's BlossomV algorithm.

The **return value** is a `NamedTuple`

object `match`

with fields:

```
match.weight: total weight of the matching
match.mate: `mate[i] = j` if vertex `i` is matched to vertex `j`.
`mate[i] = -1` for unmatched vertices.
```

**Example**

```
g = random_regular_graph(30, 4)
w = EdgeMap(g, e -> rand())
match = minimum_weight_perfect_matching(g, w)
print(match.weight)
print(match.mate)
```

`ErdosExtras.solve_tsp`

— Method`solve_tsp(g, w; cutoff=Inf)`

Given a graph `g`

and an edgemap `w`

containing the weight associated to each edge, solves the Travelling Salesman Problem, returning the tour among all the cities with minimal total weight.

Edges `e`

with no associated value in `w`

or with `w[e] > cutoff`

will not be considered for the optimal tour.

The algorithm uses a generic Integer Programming solver combined with a lazy constraint augmentation procedure.

The package JuMP.jl and one of its supported solvers are required.

Returns a tuple `(status, W, tour)`

containing:

- a solve
`status`

(indicating whether the problem was solved to optimality) - the tototal weight
`W`

of the tour - a vector
`tour`

containing the sequence of vertices in the optimal tour.

**Example**

```
pos = rand(30, 2)
g = CompleteGraph(30)
w = EdgeMap(g, e -> norm(pos[src(e)] - pos[dst(e)]))
status, W, tour = solve_tsp(g, w)
```