Multiroute flows

Multi-route flow

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 flow_algorithm and capacity_matrix)

julia> flow_graph = lg.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
source
ExtendedMultirouteFlowAlgorithm

Used to specify the Extended Multiroute Flow algorithm.

source
KishimotoAlgorithm

Used to specify the Kishimoto algorithm.

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

source
auxiliaryPoints(flow_graph, source, target, capacity_matrix)

Output a set of (point, slope) that compose the restricted max-flow function of flow_graph from source totargetusing capacities incapacity_matrix`.

Performance

One point by possible slope is enough (hence $\mathcal{O}(λ×maximum_flow)$ complexity).

source
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`.

source
LightGraphsFlows.emrfFunction.
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

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

source
    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:

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

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

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

source
AbstractMultirouteFlowAlgorithm

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

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

source