Non-sparse matrices in max-flow algorithms?

[raoanupb]

Hi,

Thank you for maintaining this package!

I just tried running some of the implemented max-flow algorithms, and I noticed that the output flow 'F' is of dense matrix type, even when the input (capacity matrix) is sparse. Is this a bug?

Thanks,
Anup

PS: Here is an example code:

edges = [1 2; 2 3; 2 4; 1 3; 3 4]
caps = 2*ones(5)
caps[2]=1
caps[3] = 1
caps[4] =1

a = sparse(edges[:,1],edges[:,2],caps,n,n)
flowGraph = DiGraph(a)

@time f, F = maximum_flow(flowGraph, 1, 4,a,algorithm=EdmondsKarpAlgorithm())
typeof(F)

[sbromberger]

This is intended. All flow algorithms accept an AbstractMatrix but for type stability will return a dense matrix.

If you'd like to make a PR that specializes on the input matrix, we'd be happy to consider it.

[jpfairbanks]

This is not strictly necessary, we could have the flow algorithms return a sparse matrix for sparse matrix inputs, without violating type stability. It would just require some effort to make sure that output types depend only on the types of the inputs.

[sbromberger]

@jpfairbanks yes - it would require specialized methods. Open to PRs.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[matbesancon]

I'll transfer this to LGFlows
@raoanupb see JuliaGraphs/LightGraphsFlows.jl#9

[sbromberger]

Cool. Thanks. Closing this out.