Karger's min cut algorithm

I have implemented a simple version of Karger's min cut algorithm. The algorithm takes a graph and repeatedly contracts randomly selected edges until only two nodes are left. By repeating this procedure n times and remembering the smallest number of edges between the remaining two nodes over the \$n\$ trials, the algorithm returns the correct number of minimum edges with a relatively high probability.

```
#include "KargerMinCut.h"
#include "stdafx.h"
#include
#include
#include
#include
void Contract(std::unordered_map >& graph, int nodeA, int nodeB)
{
assert(nodeA != nodeB);
assert(graph.size() > (size_t)2);
graph[nodeB].insert(graph[nodeB].end(), graph[nodeA].begin(), graph[nodeA].end());
auto nodesConnectedToA = graph[nodeA];
for (auto node : nodesConnectedToA)
{
auto position = graph[node].end();
while ((position = std::find(
graph[node].begin(),
graph[node].end(),
nodeA)) != graph[node].end())
{
*position = nodeB;
}
}
auto selfNodePosition = graph[nodeB].end();
while ((selfNodePosition = std::find(
graph[nodeB].begin(),
graph[nodeB].end(),
nodeB)) != graph[nodeB].end())
{
graph[nodeB].erase(selfNodePosition);
}
graph.erase(nodeA);
}

int GetKargerMinCut(std::unordered_map>& graph, int numberOfRepetitions)
{
auto n = graph.size();
int minNodeNumber = (n*(n - 1)) / 2; //initialize to maximum number of possible edges
auto originalGraph = graph;
for (int i = 0; i 2; numberOfNodes = graph.size())
{
std::uniform_int_distribution uni1(0, numberOfNodes - 1);
auto randomInteger = uni1(engine);
auto graphElement = std::next(graph.begin(), randomInteger);
auto firstNode = graphElement->first;
auto numberOfAdjacentNodes = graph[firstNode].size();
std::uniform_int_distribution uni2(0, numberOfAdjacentNodes - 1);

repeatedly contracts randomly selected edges until only two nodes are left.

Your implementation works fine. It has trouble uniformly selecting an edge because you choose by node. Consider a 10-edge linear graph (most nodes are degree two) connected to a 5-node complete graph (which also has 10 edges). You oversample the linear portion of the graph. In general, you oversample edges connected to low degree nodes.


each edge is represented twice. Is there a better way of doing that?

You also mention weights. To support uniform sampling, you might choose to represent edges as (A, B) tuples, with A numerically smaller than B's ID. This extends naturally to 3-tuples that have a weight. You would probably want to sort by weight, maintain a cumsum list, choose a random number less than total weight, and do binary search to find the corresponding edge to contract.

StackExchange Code Review Q#158263, answer score: 2