Should we extend flow algorithm to MetaGraphs.jl?

[Azzaare]

I don't know if there is any perf benefits to use MetaGraphs with weights instead of weights matrices for current flow algorithms, but it would definitively makes sense to have those available.

[sbromberger]

They should just work as long as you've got a :weight attribute on the edges.

(:weight is the default attribute for weights, you can use weightfield!() to change it.)

[Azzaare]

@sbromberger Thanks, I was not even aware, could you point to the code part(s) that make(s) it work? I have an incoming PR for a flow-like algorithm in LG, and I would definitively love to have it work with MetaGraphs from the start.

(I will close the issue as soon as I have no more reason to bother you, sorry)

[sbromberger]

Sure. Take a look at the README.md towards the end to see how the weights work in MetaGraphs:

# using weights
julia> mg = MetaGraph(CompleteGraph(3))
{3, 3} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> enumerate_paths(dijkstra_shortest_paths(mg, 1), 3)
2-element Array{Int64,1}:
 1
 3

julia> set_prop!(mg, 1, 2, :weight, 0.2)
Dict{Symbol,Float64} with 1 entry:
  :weight => 0.2

julia> set_prop!(mg, 2, 3, :weight, 0.6)
Dict{Symbol,Float64} with 1 entry:
  :weight => 0.6

julia> enumerate_paths(dijkstra_shortest_paths(mg, 1), 3)
3-element Array{Int64,1}:
 1
 2
 3

Then, in https://github.com/JuliaGraphs/MetaGraphs.jl/blob/130f60c0fab66fa183da1cf65bfbae93f6b66cc4/src/MetaGraphs.jl#L108, we override weights(), which is used by any LightGraphs function that can handle weights (graph types can override the default "all weights = 1" structure, which is what we do here.) See https://github.com/JuliaGraphs/LightGraphs.jl/blob/f8b5589bd5bef1d71a3806082f125f8f1cb67d8b/src/centrality/closeness.jl#L14 for an example.

That said, the existing flow algorithms don't use weights, they use capacity and residual matrices. We might want to revisit that.

[Azzaare]

That said, the existing flow algorithms don't use weights, they use capacity and residual matrices. We might want to revisit that.

I think it would be really nice.

As for my incoming PR, it also uses weights on the vertices, so I will have to be creative, but I will make it compatible with MetaGraphs. Should we let the issue opened while flow algorithms are not yet using weights?

[sbromberger]

Should we let the issue opened while flow algorithms are not yet using weights?

Not here, but there should probably be an issue in LightGraphs for discussion.