Stoer–Wagner algorithm for minimum cut#606
Conversation
RaoulLuque
left a comment
RaoulLuque
left a comment
There was a problem hiding this comment.
A rebase to the current version of Petgraph is probably necessary. In particular, to comply with no-std, HashMap from the standard library should/could be replaced with the one from HashBrown and similarly with BinaryHeap.
I would also like if the private helper functions had some brief docstrings like for example in https://github.com/petgraph/petgraph/blob/master/src/algo/ford_fulkerson.rs
| /// non-negative. | ||
| /// Returns a tuple composed of a vector of `EdgeId` that represents the cut and the cut weight. | ||
| /// | ||
| /// Computes in **O(|V| |E| + |V|²*log(|V|)))** time |
There was a problem hiding this comment.
| /// Computes in **O(|V| |E| + |V|²*log(|V|)))** time | |
| /// Computes in **O(|V|³)** time |
The running time should probably be O(|V| |E| + |V|³) = O(|V|³), since we don't use Fibonacci heaps, but a binary heap.
| G::NodeId: Eq + Hash, | ||
| K: Measure + Copy, | ||
| { | ||
| let mut node_to_node = HashMap::new(); |
There was a problem hiding this comment.
std::HashMap should be replaced by the hashbrown equivalent to be no-std compliant.
| K: Measure + Copy, | ||
| EdgeId: Copy, | ||
| { | ||
| let mut queue = BinaryHeap::new(); |
There was a problem hiding this comment.
std::BinaryHeap should be replaced by the alloc::collections::BinaryHeap equivalent.
|
Hey, I wanted to check-in on whether you'd be willing to continue working on this PR, or whether I or someone else could possibly pick it up in the future :) ? |
4 participants
Hi,
I propose an implementation of Stoer–Wagner algorithm to solve the (global) minimum cut problem.
https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm
The implementation runs in O(|V| |E| + |V|²*log(|V|).
I'm fairly new to Rust and Petgraph. So I would be happy to have some advice.
The algorithm requires modifying the graph (vertex merging). So, I works on a mutable copy of the graph with the type Graph.
There may be a more elegant way to do this.
Since I need a max version of
MinScored, I created the structMaxScored.I have added tests, quickcheck tests and benchmarks.