# 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 <algorithm>
#include <unordered_map>
#include <random>
#include <assert.h>
void Contract(std::unordered_map <int, std::vector<int>>& 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<int, std::vector<int>>& 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 < numberOfRepetitions; i++)
{
graph = originalGraph;
std::random_device rd{};
// Use Mersenne twister engine to generate pseudo-random numbers.
std::mt19937 engine( rd () );
for (auto numberOfNodes = graph.size(); numberOfNodes > 2; numberOfNodes = graph.size())
{
std::uniform_int_distribution<int> uni1(0, numberOfNodes - 1);
auto randomInteger = uni1(engine);
auto graphElement = std::next(graph.begin(), randomInteger);
auto firstNode = graphElement->first;
randomInteger = uni2(engine);
auto secondNode = graph[firstNode][randomInteger];
Contract(graph, firstNode, secondNode);
}
auto nodeNumber = graph.begin()->second.size();
if (nodeNumber < minNodeNumber)
minNodeNumber = nodeNumber;
}
return minNodeNumber;
}


The code is run using the VisualStudio2017 CppUnitTestFramework:

TEST_METHOD(TestKargersMinimumCut)
{
std::unordered_map <int, std::vector<int>> simpleGraph
int expectedMinNodeCount = 2;
int minNodeCount = GetKargerMinCut(simpleGraph, 100);
Assert::AreEqual(expectedMinNodeCount, minNodeCount);

std::unordered_map <int, std::vector<int>> largeGraph =
expectedMinNodeCount = 17;
minNodeCount = GetKargerMinCut(largeGraph, 100);
Assert::AreEqual(expectedMinNodeCount, minNodeCount);
}


The files contain the graphs in the following representation :

1   2   3
2   1   3   4
3   1   2   4
4   2   3


Where the first column of each line contains the ID of a specific node and the following columns of each line list the IDs of nodes adjacent to the node in the first column.

I am open to any suggestions to improve my code, but I specifically want to discuss the graph representation I am using, which is an unordered map of int/vector pairs, where the integer represents the ID of a specific node and the corresponding vector contains the node IDs of all nodes connected to that specific node. Although this representation works fine for my purposes, an obvious flaw is that it contains redundant information, because each edge is represented twice. Is there a better way of doing that?

The second problem with respect to the chosen graph representation is the question of generalizability: Is it possible to represent weighted and directed edges as well, using this simple representation? One idea to represent directed graphs would be to list only those nodes in the vectors to which a specific node is pointing to, which would also solve the first problem mentioned above, because edges wouldnt be represented twice.

• It would really help if you could post a simple main() that exercises this code (the necessary header includes would be a bonus, too). Any chance of adding these before anyone answers? – Toby Speight Mar 20 '17 at 11:08
• I have updated the op accordingly. – user1934212 Mar 20 '17 at 11:22