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.

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 totargetusing capacities incapacity_matrix`.

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

Compute the maximum multiroute flow (for any number of routes) 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

• Extended Multiroute Flow algorithm

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).

    intersection(x1, y1, a1, x2, y2, a2)

Return the intersection of two lines defined by x and y with slopes a.

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

Requires argument:

1. • x1, y1, a1, x2, y2, a2::T<:AbstractFloat # Coordinates/slopes
2. • points::Vector{Tuple{T, T, Int}} # vector of points with T<:AbstractFloat

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

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.

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 routes is 0, return the set of breaking points of

the multiroute flow.

• When the number of routes 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 flowalgorithm and capacitymatrix)

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

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.

AbstractMultirouteFlowAlgorithm

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

ExtendedMultirouteFlowAlgorithm

Used to specify the Extended Multiroute Flow algorithm.

KishimotoAlgorithm

Used to specify the Kishimoto algorithm.

kishimoto(flow_graph, source, target, capacity_matrix, flow_algorithm, routes)

Compute the maximum multiroute flow (for an integer number of routes) 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.