Max flow with weighted graphs

[etiennedeg]

trafficstars

It would be nice to specialize methods on weighted graphs, with weights representing the capacities. In a lot of situations, people who need flow algorithms work with weighted graphs. It also provide a sparse representation of the flow network. (without the need of an external sparse matrix).

(related : #9)

[gdalle]

You should check out SimpleWeightedGraphs.jl, you may find what you are looking for.

Adapting the code yourself shouldn't be too hard, maybe something along the lines of

function maximum_flow(
        flow_graph:: swg.AbstractSimpleWeightedGraph,          # the input graph
        source::Integer,                       # the source vertex
        target::Integer,                       # the target vertex
        algorithm::AbstractFlowAlgorithm  =    # keyword argument for algorithm
        PushRelabelAlgorithm(),
        restriction::Real = 0                  # keyword argument for restriction max-flow
    )
    capacity_matrix = weights(flow_graph)'
    if restriction > 0
        return maximum_flow(flow_graph, source, target, min.(restriction, capacity_matrix), algorithm)
    end
    return maximum_flow(flow_graph, source, target, capacity_matrix, algorithm)
end

[gdalle]

@matbesancon would this be a welcome addition to LightGraphsFlows or is the issue closable? (I warned you that I would tag you without mercy)

[matbesancon]

Yes this can be added to this package, it's ok to make it depend on SimpleWeightedGraphs

[gdalle]

I've been working on a PR but it's not as straightforward as I said above. @etienneINSA did you manage to make it work?

[simonschoelly]

Is there an advantage of writing a specalised methods for AbstractSimpleWeightedGraph? Wouldn't it be better to have a general method that uses the weights function for calculating the capacities? Then this functions would also work with other graph types that overload the weights function.

Also, we should make sure, that it is still possible to use a different capacity matrix with an AbstractSimpleWeightedGraph.

If we have to add a dependency on SimpleWeightedGraphs.jl, we might think about using Requires.jl to lazy load that extra code when needed.

[gdalle]

Sounds like a good idea! However I'm not sure it is the only change necessary in LightGraphFlows.jl, I ran into some issues to build the residual graph from a SimpleWeightedDiGraph. What is the procedure here, should I submit a buggy PR as a support for discussion?

[gdalle]

(in case I can't debug it myself after a good night's sleep)

[matbesancon]

indeed using weight makes more sense, no need to add SWG.

What is the procedure here, should I submit a buggy PR as support for discussion?

yes we can improve upon it