LightGraphsFlows.jl

LightGraphsFlows.jl copied to clipboard

Hello there

As per @etienneINSA's request in #40 here is a specialization of the max-flow function for weighted graphs in which the capacities are equal to the weights. I'm not entirely confident it works well, since @simonschoelly's suggestion to simply use weights(g) instead of relying on SimpleWeightedGraphs.jl removed all the bugs without letting me understand them, but the small tests I added seem to suggest it's fine.

What do you think about the function signature? I would have used multiple dispatch instead of an additional argument but I didn't know how to detect weighted graphs without SWG.

Not entirely satisfied with this because my version of residual in maximum_flow.jl induces unnecessary copies and depends on SWG. A little help would be most welcome

Also, for some reason the tests fail because swg is unknown, even though I define the constant in runtests.jl

If you look at some functions in LightGraphs, like diameter for example: https://github.com/JuliaGraphs/LightGraphs.jl/blob/77870d4702145e2a1cfe804d0f1ec481f2e94617/src/distance.jl#L106, then they always use the weights function, even if there are no weights for a graph. The way that works is by returning a DefaultDistance object whenever a graph does not have any weights defined - this is just a matrix that returns a 1 for every entry.

Maybe we can have this here too? Then if one does not want to use any weights with a graph, they can just pass in a DefaultDistance so that we do not need the boolean parameter.

Also, for some reason the tests fail because swg is unknown, even though I define the constant in runtests.jl

You need to load SimpleWeightedGraphs in your tests - either with using SimpleWeightedGraphs or import SimpleWeightedGraphs. See: https://docs.julialang.org/en/v1/manual/modules/#Summary-of-module-usage

Also, for some reason the tests fail because swg is unknown, even though I define the constant in runtests.jl

You need to load SimpleWeightedGraphs in your tests - either with using SimpleWeightedGraphs or import SimpleWeightedGraphs. See: https://docs.julialang.org/en/v1/manual/modules/#Summary-of-module-usage

Rookie mistake ^^ The bug is fixed but I'm not sure how to include SWG only in the test deps

And i'm still not satisfied about https://github.com/gdalle/LightGraphsFlows.jl/blob/f755afa2d240292c49a3228e1e0a6fe2bb2904d5/src/maximum_flow.jl#L70, which I think a more seasoned LightGraphs practitioner could easily fix

If you look at some functions in LightGraphs, like diameter for example: https://github.com/JuliaGraphs/LightGraphs.jl/blob/77870d4702145e2a1cfe804d0f1ec481f2e94617/src/distance.jl#L106, then they always use the weights function, even if there are no weights for a graph. The way that works is by returning a DefaultDistance object whenever a graph does not have any weights defined - this is just a matrix that returns a 1 for every entry.

Maybe we can have this here too? Then if one does not want to use any weights with a graph, they can just pass in a DefaultDistance so that we do not need the boolean parameter.

Unfortunately, after taking a look, it seems that weights defaults to DefaultDistance for general graphs, but LightGraphsFlows uses DefaultCapacity instead. This seems important because making the transition from DefaultCapacity to weights breaks some tests for multiroute_flow