## Multi-route flow

`GraphsFlows.approximately_equal`

— Method`approximately_equal(a, b)`

Return true if each element in the tuple is approximately equal to its counterpart.

**Implementation Notes:**

This is a separate function because we don't want to hijack isapprox for tuples.

`GraphsFlows.breakingPoints`

— Function`breakingPoints(flow_graph::::IsDirected, source, target, capacity_matrix)`

Calculates the breaking of the restricted max-flow from a set of auxiliary points for `flow_graph`

from `source to`

target`using capacities in`

capacity_matrix`.

`GraphsFlows.emrf`

— Function`emrf(flow_graph, source, target, capacity_matrix, flow_algorithm, routes=0)`

Compute the maximum multiroute flow (for any number of `route`

s) between `source`

and `target`

in `flow_graph`

via flow algorithm `flow_algorithm`

.

If a number of routes is given, return the value of the multiroute flow as well as the final flow matrix, along with a multiroute cut if the Boykov-Kolmogorov max-flow algorithm is used as a subroutine. Otherwise, return the vector of breaking points of the parametric multiroute flow function.

**References**

`GraphsFlows.intersection`

— Method`intersection(points, k)`

Return the intersection of a set of line segments and a line of slope `k`

passing by the origin. Segments are defined as a triple (x, y, slope).

`GraphsFlows.intersection`

— Method` intersection(x1, y1, a1, x2, y2, a2)`

Return the intersection of two lines defined by `x`

and `y`

with slopes `a`

.

- A set of segments and a linear function of slope k passing by the origin.

Requires argument:

- x1, y1, a1, x2, y2, a2::T<:AbstractFloat # Coordinates/slopes

- points::Vector{Tuple{T, T, Int}} # vector of points with T<:AbstractFloat

- k::R<:Real # number of routes (slope of the line)

`GraphsFlows.minmaxCapacity`

— Method`minmaxCapacity(capacity_matrix)`

Return the nonzero min and max function of `capacity_matrix`

.

Note: this is more efficient than maximum() / minimum() / extrema() since we have to ignore zero values.

`GraphsFlows.multiroute_flow`

— Method`multiroute_flow(flow_graph, source, target[, DefaultCapacity][, flow_algorithm][, mrf_algorithm][, routes])`

The generic multiroute_flow function.

The output will vary depending on the input:

- When the number of
`route`

s is`0`

, return the set of breaking points of

the multiroute flow.

- When the number of
`route`

s is`1`

, return a flow with a set of 1-disjoint paths

(this is the classical max-flow implementation).

- When the input is limited to a set of breaking points and a route value
`k`

,

return only the k-route flow.

- Otherwise, a tuple with 1) the maximum flow and 2) the flow matrix. When the

max-flow subroutine is the Boykov-Kolmogorov algorithm, the associated mincut is returned as a third output.

When the input is a network, it requires the following arguments:

`flow_graph`

: the input graph`source`

: the source vertex`target`

: the target vertex`capacity_matrix`

: matrix of edge flow capacities`flow_algorithm`

: keyword argument for flow algorithm`mrf_algorithm`

: keyword argument for multiroute flow algorithm`routes`

: keyword argument for the number of routes

When the input is only the set of (breaking) points and the number of route, it requires the following arguments:

`breakingpoints`

: vector of breaking points`routes`

: number of routes

When the input is the set of (breaking) points, the number of routes, and the network descriptors, it requires the following arguments:

`breakingpoints`

: vector of breaking points`routes`

: number of routes`flow_graph`

: the input graph`source`

: the source vertex`target`

: the target vertex`capacity_matrix`

: matrix of edge flow capacities`flow_algorithm`

: keyword argument for flow algorithm

The function defaults to the Push-relabel (classical flow) and Kishimoto (multiroute) algorithms. Alternatively, the algorithms to be used can also be specified through keyword arguments. A default capacity of `1`

is assumed for each link if no capacity matrix is provided.

The `mrf_algorithm`

keyword is inforced to Extended Multiroute Flow in the following cases:

- The number of routes is non-integer
- The number of routes is 0 or non-specified

**Usage Example :**

(please consult the `maximum_flow`

section for options about flow*algorithm and capacity*matrix)

```
julia> flow_graph = Graphs.DiGraph(8) # Create a flow graph
julia> flow_edges = [
(1, 2, 10), (1, 3, 5), (1, 4, 15), (2, 3, 4), (2, 5, 9),
(2, 6, 15), (3, 4, 4), (3, 6, 8), (4, 7, 16), (5, 6, 15),
(5, 8, 10), (6, 7, 15), (6, 8, 10), (7, 3, 6), (7, 8, 10)
]
julia> capacity_matrix = zeros(Int, 8, 8) # Create a capacity matrix
julia> for e in flow_edges
u, v, f = e
add_edge!(flow_graph, u, v)
capacity_matrix[u, v] = f
end
julia> f, F = multiroute_flow(flow_graph, 1, 8, capacity_matrix, routes = 2) # Run default multiroute_flow with an integer number of routes = 2
julia> f, F = multiroute_flow(flow_graph, 1, 8, capacity_matrix, routes = 1.5) # Run default multiroute_flow with a noninteger number of routes = 1.5
julia> points = multiroute_flow(flow_graph, 1, 8, capacity_matrix) # Run default multiroute_flow for all the breaking points values
julia> f, F = multiroute_flow(points, 1.5) # Then run multiroute flow algorithm for any positive number of routes
julia> f = multiroute_flow(points, 1.5, valueonly = true)
julia> f, F, labels = multiroute_flow(flow_graph, 1, 8, capacity_matrix, algorithm = BoykovKolmogorovAlgorithm(), routes = 2) # Run multiroute flow algorithm using Boykov-Kolmogorov algorithm as maximum_flow routine
```

`GraphsFlows.slope`

— Function`slope(flow_graph, capacity_matrix, cut, restriction)`

Return the slope of `flow_graph`

using capacities in `capacity_matrix`

and a cut vector `cut`

. The slope is initialized at 0 and is incremented for each edge whose capacity does not exceed `restriction`

.

`GraphsFlows.AbstractMultirouteFlowAlgorithm`

— Type`AbstractMultirouteFlowAlgorithm`

Abstract type that allows users to pass in their preferred algorithm.

`GraphsFlows.ExtendedMultirouteFlowAlgorithm`

— Type`ExtendedMultirouteFlowAlgorithm`

Used to specify the Extended Multiroute Flow algorithm.

`GraphsFlows.KishimotoAlgorithm`

— Type`KishimotoAlgorithm`

Used to specify the Kishimoto algorithm.

`GraphsFlows.kishimoto`

— Function`kishimoto(flow_graph, source, target, capacity_matrix, flow_algorithm, routes)`

Compute the maximum multiroute flow (for an integer number of `route`

s) between `source`

and `target`

in `flow_graph`

with capacities in `capacity_matrix`

using the Kishimoto algorithm. Return the value of the multiroute flow as well as the final flow matrix, along with a multiroute cut if Boykov-Kolmogorov is used as a subroutine.