Karger's min cut algorithm

Question

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;
            auto numberOfAdjacentNodes = graph[firstNode].size();
            std::uniform_int_distribution<int> uni2(0, numberOfAdjacentNodes - 1);
            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
    ReadGraphFromFile("..\\Data\\KargerMinCutSimple.txt");
    int expectedMinNodeCount = 2;
    int minNodeCount = GetKargerMinCut(simpleGraph, 100);
    Assert::AreEqual(expectedMinNodeCount, minNodeCount);

    std::unordered_map <int, std::vector<int>> largeGraph =    
    ReadGraphFromFile("..\\Data\\KargerMinCut.txt");
    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.

Answer 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.