search

JuliaGraphs / LightGraphsFlows.jl

Flow algorithms on LightGraphs
Other
36 stars 11 forks source link

Max flow with weighted graphs #40

Open etiennedeg opened 3 years ago

etiennedeg commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

@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 commented 3 years ago

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

gdalle commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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

matbesancon commented 3 years ago

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