Feature request: minimum cut function

[MrRaghav]

Hello, I know that NetworkX has a direct function to implement min cut max flow algorithm minimum_cut(). It works well with small graphs but fails for large graphs.

I checked graph-theory and found that it has test_flow_problem.py but I couldn't find a direct minimum_cut() function like NetworkX.

This is a feature request to add this functionality in graph-theory.

[root-11]

Challenge accepted.

[root-11]

Given the Graph g we can determine the edges for the minimum cut using g.maximum_flow which returns the flow as a value and the graph of flows at maximum flow (maximum flow graph : mfg). g.maximum_flow likes large graphs. No issue here as far as I'm aware.

Conceptually we can now declare the candidate edges for the minimum cut by deducing the flow in mfg from the edge capacity in g to determine which edges which will have a value of zero. This can be done in two lines of code:

_, mfg = g.maximum_flow(start,end)
min_cut_edges = [(start, end) for start, end, flow in mfg.edges() if g.edge(start, end) - flow == 0]

This is where the "problem" starts as the combinations of candidate solutions for the minimum cut will appear.

Example 1

Which solution should we return as "the solution"? Should it be edges [('+', 'a'), ('+', 'c')] or [('b','-')] ?

Example 2

How about this case?

We can now present 4 unique solutions.

We can settle with Ford-Fulkersons view that it should always be the left-most (nearest the source) cut. By using the Ford-Fulkerson algorithm on mfg that should be pretty quick despite that the original g might be very very large..

references:

1. https://stackoverflow.com/questions/29418244/which-min-cut-does-the-ford-fulkerson-algorithm-find
2. https://cs.stackexchange.com/questions/42960/does-ford-fulkerson-always-produce-the-left-most-min-cut?noredirect=1&lq=1

[root-11]

1st Implementation available in commit bac8d633ee0

[root-11]

@MrRaghav please add your own tests and leave a pull request to include the tests into the test suite.

[MrRaghav]

@root-11 , I'm really thankful for your quick response. I'm nobody to challenge you :)

I used Jupyter notebook to run my code but when I run g.maximum_flow_min_cut(source,sink) , it gives me following error:

AttributeError                            Traceback (most recent call last)
<ipython-input-36-972037cd63ff> in <module>
----> 1 g.maximum_flow_min_cut(source,sink)

AttributeError: 'Graph' object has no attribute 'maximum_flow_min_cut'

I checked that I have installed latest released version:

(base) C:\Users\>pip install --upgrade graph-theory
Requirement already up-to-date: graph-theory in c:\users\anaconda3\lib\site-packages (2020.9.23.63516)

Please spare some time to suggest me here so that I can create a pull request.

[root-11]

@MrRaghav - The pypi package 2020.9.23 doesn't contain the maximum_flow_min_cut as I thought you would like to test it before release. So It's only github in master. Are you familiar with cloning a branch adding your own tests and creating a pull request?

[MrRaghav]

I got your point now and I'm aware of this process. I'll test it and will let you know.

[root-11]

@MrRaghav Did you run into any problems?

[MrRaghav]

Hello, I apologize for late. My Linux access was revoked so I had to use windows. I'm facing some import related issues but didn't want to bother you regarding this trivial thing. I've following code:

from graph_theory.graph.__init__.py import *

G = Graph()

source_list = [0.11, 0.11, 0.11, 0.89, 0.11, 0.89, 0.11, 0.11, 0.11, 0.11]

# to create edges for source
x = 10

for i in range(0, x):
    G.add_edge('source', str(i), source_list[i])
    G.add_edge(str(i), 'source', source_list[i])

sink_list = [0.89, 0.89, 0.89, 0.01, 0.89, 0.01, 0.89, 0.89, 0.89, 0.89]

# to create edges for sink
x = 10

for i in range(0, x):
    G.add_edge('sink', str(i), sink_list[i])
    G.add_edge(str(i), 'sink', sink_list[i])

import pandas as pd

dfTestCsv = pd.read_excel("../../min_cut_using_graph_theory_library.xlsx", header=None)

# to create edges for each node

z = 10

for i in range(0, z):
    for j in range(0, z):
        IterList = dfTestCsv.iloc[i].tolist()
        G.add_edge(str(i), str(j), IterList[j])

G.maximum_flow_min_cut(source, sink)

But, PyCharm IDE gives me following error:

C:\Users\PycharmProjects\min_cut\venv\Scripts\python.exe C:/Users/.PyCharmCE2019.2/config/scratches/scratch.py
Traceback (most recent call last):
  File "C:/Users/.PyCharmCE2019.2/config/scratches/scratch.py", line 6, in <module>
    from graph_theory.graph.__init__.py import *
ModuleNotFoundError: No module named 'graph_theory.graph.__init__.py'; 'graph_theory.graph.__init__' is not a package

Process finished with exit code 1

I'm not that expert with Python, therefore its taking time for me to fix these issues.

[root-11]

Try this import instead:

from graph import *

[root-11]

This should work for you

from graph.random import random_xy_graph
from graph.visuals import plot_2d
from random import choice

g = random_xy_graph(nodes=20, x_max=200, y_max=200, edges=35)
for s,e,d in g.edges():
    g.add_edge(s,e,1)

plt = plot_2d(g)
plt.show()

a,b = choice(g.nodes()), choice(g.nodes())

print(g.maximum_flow_min_cut(a,b))

Note that the nodes have (x,y) coordinates.

[MrRaghav]

Hello, I tried above mentioned ways but they don't work in my environment of PyCharm. Also, I tried other ways with my understanding and I feel that I need to gain more knowledge of python programming (not data science) to handle such situations in future.

I'm really thankful that you helped a junior but I can't waste your time due to my less knowledge. I will close this issue by today.

[root-11]

Try to run your pip install --upgrade graph-theory The function is packaged as of yesterday.

[MrRaghav]

Thank a million :pray: . However, I've done a comparative experiment of my approach with graph-theory and NetworkX. Basically my approach is:

_randomly assign weights to the edges (including those of source and sink) and run mincut() functions.

I've attached PNGs[1][2] of my IPYNB file (because Github doesn't allows me to attach an IPYNB) where G.maximum_flow_min_cut('source','sink') of graph-theory gives following output:

[('source', '3'), ('source', '5'), ('source', '2'), ('source', '6'), ('source', '7'), ('source', '9'), ('source', '4'), ('source', '0'), ('source', '1'), ('source', '8')]

Whereas, nx.minimum_cut(Gnx, 'source', 'sink') gives following output:

({'source'}, {'8', '4', '6', '3', '2', '9', '5', '7', '0', '1', 'sink'})

For NetworkX, I've followed this tutorial.

I'm not sure why graph-theory considers all the nodes with the sub-graph of source while NetworkX does vice-versa. Except this, I think this functionality works in graph-theory.

[root-11]

Well done!

[MrRaghav]

Thank you 🙏 . I'm closing it now.