This repository contains a Rust implementation of the "FastCut" randomized minimum cut algorithm introduced by Karger and Stein (see Figure 6 in A New Approach to the Minimum Cut Problem).
I wrote the program for an oral examination for a randomized algorithms class at university. It is probably not suitable for application to real-world problems.
(A GML file output by this program. Visualized using VANTED).
- MinCut Estimation
- Parallelized Computation
- GML Output (No Layout)
./mincut [-v] <PATH_TO_GRAPH>If the -v is specified, a visualization of the result is written to <PATH_TO_GRAPH>.gml.
This program processes undirected graphs with unit weights.
It reads plain text files that specify the edges.
The nodes are assumed to be numbered with integers from 0 to <num_nodes>.
The input format is as follows:
<num_nodes>
<num_edges>
<source1> <target1>
<source2> <target2>
...
The graph is internally represented as an adjacency matrix. Since it is undirected it is enough to store the upper triangular matrix.
Example matrix:
