Push Relabel

[hcars]

Modifications:

(new algorithms, added tests or documentation)

• Created an implementation of the push-relabel algorithm
• Created tests for the algorithm and some of its helper algorithms.

Impacted submodules:

(e.g. sknetwork.topology)

• flow

This pull request:

(your PR must match these criteria before review)

• [x] targets the develop branch
• [x] does not decrease code coverage
• [x] passes the tests
• [x] is documented and the documentation build passes
• [x] has PEP8-compliant code and explicit variable naming
• [ ] has a tutorial (facultative but recommended)

I wrote this a way to familiarize myself with the push-relabel algorithm. A fast max-flow algorithm by Orlin called Enhanced Large-Medium Excess Scaling is based on this old method. I'll implement this as my next in building out the maximum flow algorithms.

[codecov[bot]]

Codecov Report

Merging #536 (f86e8c0) into develop (c90321f) will decrease coverage by 0.04%. The diff coverage is 94.02%.

@@             Coverage Diff             @@
##           develop     #536      +/-   ##
===========================================
- Coverage    98.71%   98.66%   -0.05%     
===========================================
  Files          188      196       +8     
  Lines         8122     8420     +298     
===========================================
+ Hits          8018     8308     +290     
- Misses         104      112       +8     

Impacted Files	Coverage Δ
sknetwork/classification/vote.pyx	100.00% <ø> (ø)
sknetwork/flow/utils.py	84.37% <84.37%> (ø)
sknetwork/flow/tests/test_utils.py	91.89% <91.89%> (ø)
sknetwork/__init__.py	100.00% <100.00%> (ø)
sknetwork/flow/__init__.py	100.00% <100.00%> (ø)
sknetwork/flow/push_relabel.py	100.00% <100.00%> (ø)
sknetwork/flow/push_relabel_core.pyx	100.00% <100.00%> (ø)
sknetwork/flow/tests/test_flow.py	100.00% <100.00%> (ø)
sknetwork/gnn/base.py	100.00% <0.00%> (ø)
sknetwork/gnn/utils.py	100.00% <0.00%> (ø)
... and 12 more

:mega: Codecov can now indicate which changes are the most critical in Pull Requests. Learn more

[tbonald]

Thanks for your PR! Your code seems to be much slower than that of scipy: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.maximum_flow.html

Tested on a random graph of 100 nodes.

Could you please check that?

[tbonald]

I'm closing this PR. Feel free to reopen it once the difference with Scipy is clarified.