#include <iostream>
#include <map>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>
#include <ranges>
#include <sstream>
#include <fstream>


// making my life easier !
using dict = std::map< int, std::vector<int> >; 

// prints the graph by iterating over the map
void print_graph (const dict & graph  ) {
    for (const auto &[ vertex, edges ] : graph){
        std::cout << "Vertex " << vertex << " Edges " ;
        for ( auto element : edges )
            std::cout << " " << element;
        std::cout << std::endl; 
    }
}


std::vector<int> select_random_edge ( const dict & graph){
    // select random key from map
    // from that key select random value in the edge vector
     
    std::random_device rd; // for seed
    std::mt19937 generator(rd());
    std::uniform_int_distribution<> vertices_distrib(0,graph.size()-1);
    int randomVertexIndex = vertices_distrib(generator);
    auto it = std::begin(graph);
    std::advance(it, randomVertexIndex);
    std::uniform_int_distribution<> edges_distrib(0,it->second.size()-1);
    int randomEdgeIndex = edges_distrib(generator);
    auto vit = std::begin(it->second);
    std::advance(vit, randomEdgeIndex);
    int vertex2 = *vit;
    int vertex1 = it->first;
    std::vector<int> edge = {vertex1, vertex2};
    return edge;
}

// Merges two vertices in the graph according to the Karger's algorithm
void merge_vertex(dict & graph ) {

    auto edge = select_random_edge(graph);
    std::vector<int> merged_edges;
    std::merge(graph[edge[0]].begin(),graph[edge[0]].end(),
               graph[edge[1]].begin(),graph[edge[1]].end(),
               std::back_inserter(merged_edges)); 
    graph[edge[0]] = merged_edges;
    graph.erase(edge[1]);
    // Replace Deleted vertex with the merged one
    for ( auto &[vertex, edges] : graph){
            auto new_edges = edges | std::views::transform([&](int n) { 
                return n == edge[1] ? edge[0] : n;
             });
            
            edges = std::vector<int> (new_edges.begin(),new_edges.end());
        }
    //removing self loops
    auto new_edges = graph[edge[0]] | std::views::filter([&] (int n){
            return  n == edge[0] ? false : true;
    });

    graph[edge[0]] = std::vector<int> (new_edges.begin(),new_edges.end());

}

int min_cut(dict graph){
    // returns the minimum cut of the graph
    constexpr auto MIN_VERTEX{2};
    int count {0};
    while( graph.size() > MIN_VERTEX)
        merge_vertex(graph);
    for (auto & [key, edges] : graph){
        count += edges.size();
    }
    return static_cast<int> (count / 2);
}


// create a function that reads the file and returns the graph

dict read_file(std::ifstream & file){
    dict graph;
    std::string line;
    // the file has several rows. each row starts with the vertex and then followed by a vector for edges
    // we will read the file line by line, we read the first value of each line and create the key in the map
    // then read the rest of the line and create a vector of edges
    while (std::getline(file, line)){
        std::vector<int> edges;
        std::istringstream iss(line);
        int vertex;
        iss >> vertex;
        int edge;
        while (iss >> edge){
            edges.push_back(edge);
        }
        graph[vertex] = edges;
    }
    return graph;
}

int main(int argc, char *argv[])
{
    // read file 
    std::ifstream file(argv[1]);
    // check if file is open
    if (!file.is_open()){
        std::cout << "File not found" << std::endl;
        return 1;
    }
    // run the algorithm for multiple trials

    constexpr int TRIALS{100};

    std::vector<int> trials;
    auto min_cut_value = 0;
    const auto graph = read_file(file);

    for (int i = TRIALS; i > 0; i--)
    {   
        dict example (graph);
        trials.push_back(min_cut(example));
    }
    std::cout << "Minimum Cut " << *std::min_element(trials.begin(), trials.end()) << std::endl;
    return 0;
}