Open gdalle opened 3 years ago
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 inruntests.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 inruntests.jl
You need to load SimpleWeightedGraphs in your tests - either with
using SimpleWeightedGraphs
orimport 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 theweights
function, even if there are no weights for a graph. The way that works is by returning aDefaultDistance
object whenever a graph does not have any weights defined - this is just a matrix that returns a1
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
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 onSimpleWeightedGraphs.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.