[FEATURE REQUEST] Proposal: Add Stoer-Wagner Algorithm for Minimum Cut

[sairamsharan]

What would you like to Propose?

I would like to propose adding an implementation of the Stoer-Wagner algorithm for the global minimum cut problem.

Issue details

Description

The Stoer-Wagner algorithm is an efficient algorithm for finding the minimum cut in an undirected, weighted graph. A minimum cut is a partition of the graph's vertices into two disjoint sets with the minimum possible edge weight sum connecting the two sets.

Additional Information

Why this is useful:

This is a classic, important algorithm in graph theory with applications in network analysis, circuit design, and clustering. While the repository has many max-flow/min-cut algorithms (like Ford-Fulkerson), the Stoer-Wagner algorithm provides a different and often simpler approach for the specific case of global min-cut in undirected graphs, making it a valuable educational addition.

Proposed Implementation:

I will implement the Stoer-Wagner algorithm in Java. The implementation will:

1. Take a graph represented as an adjacency matrix as input.
2. Use a phase-based approach with a priority queue (or similar) to find the s-t min-cut for the last two vertices added.
3. Contract the vertices and repeat until the graph has only two vertices.
4. Return the minimum cut value found across all phases.
5. Include clear Javadoc documentation and comprehensive test cases.

I have searched the repository and have not found an existing implementation of this specific algorithm. I would like to work on this for Hacktoberfest.

[yonasherpa04]

Can you assign me this

[sairamsharan]

Hi @yonasherpa04 , thanks for your interest! I'm already actively working on this and have an open pull request for it here: #6752 . I appreciate you checking first!