Popular recipes tagged "mininum_cut"http://code.activestate.com/recipes/tags/mininum_cut/2009-09-19T07:16:58-07:00ActiveState Code RecipesMinimum Cut Solver (Python)
2009-09-19T07:16:58-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/576907-minimum-cut-solver/
<p style="color: grey">
Python
recipe 576907
by <a href="/recipes/users/4168519/">Shao-chuan Wang</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/ford_fulkerson/">ford_fulkerson</a>, <a href="/recipes/tags/mininum_cut/">mininum_cut</a>, <a href="/recipes/tags/min_cut/">min_cut</a>, <a href="/recipes/tags/stoer_wagner/">stoer_wagner</a>).
</p>
<p>A Minimum Cut Solver</p>
<p>This python script is for solving the ACM problem Q2914: Minimum Cut.
<a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=2914" rel="nofollow">http://acm.pku.edu.cn/JudgeOnline/problem?id=2914</a></p>
<p>Instead of using Ford-Fulkerson method, I use Stoer and Wagner's Min cut Algorithm.
<a href="http://www.cs.dartmouth.edu/%7Eac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf" rel="nofollow">http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf</a></p>
<p>However I also include the max flow method (from wiki) for benchmark.
The code can be found at: <a href="http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm</a></p>