<commit_before>/**
 * \file min_cut_graph.cpp
 *
 * Contains implementation of min_cut_graph function
 */
#include <random>
#include "min_cut_graph.hpp"
#include <stdio.h> 
#include <stdlib.h>
#include <vector>
#include <structures/union_find.hpp>
#include "../contracting_graph.hpp"
//#define debug

namespace vg {
    namespace algorithms {

        using namespace std;

        #ifdef debug
                cerr << "some debug statement" << endl; 
        #endif


        structures::UnionFind kargers_min_cut(Graph graph, const int n_iterations, const int seed, int V) {
 
     
            minstd_rand0 random_engine(seed);
            structures::UnionFind uf(V, true);
            
            

            ContractingGraph cg(graph,uf); 
            unordered_map<size_t, size_t> cgraph_total_edge_weights;
            
            while(V > 2){
                

                // get nodes will return the heads of all the nodes
                // at first call all nodes will be heads
                vector<size_t> super_nodes = cg.get_nodes();
                V = super_nodes.size();

                //get the total edge weights for super_nodes in contracted graph
                unordered_map<size_t, unordered_map<size_t, size_t>> contracted_graph;
                for (int i =0; i < super_nodes.size(); i++){
                    //get total edge weights for each super node
                    unordered_map<size_t, size_t> supernode_edge_weights = cg.get_edges(super_nodes[i]);
                    contracted_graph[super_nodes[i]] = supernode_edge_weights; 
                    size_t total_weight = 0;
                    for_each(supernode_edge_weights.begin(), supernode_edge_weights.end() , [&](pair<size_t, size_t > element){
                        total_weight += element.second;
                    });
                    //add total edge weight for each super node
                    //ex: 2: {1:1, 4:14}, sum up 1+14 and put that in the total edge weight list for node #2
                    cgraph_total_edge_weights[super_nodes[i]] = total_weight;

                }

                // create a vector with the node weights 
                vector<int> node_weights;
                int node_num;
                for (int i =0; i <V; i++){
                    node_num = super_nodes[i];
                    node_weights.push_back(cgraph_total_edge_weights[node_num]);
                }
                // create a discrete distrbution with node weights 
                discrete_distribution<int> nodes_distribution(begin(node_weights), end(node_weights));
                
                //pick an node proportional to its total weight from incident edges
                //will choose the weight first and will get the node that maps to it after
                size_t incident_edge_totweight = nodes_distribution(random_engine);

                //check if there is more than one node with equal chosen weight
                vector <int> dup_nodes = find_dups(cgraph_total_edge_weights, incident_edge_totweight);
     
                int random_node;
                if(dup_nodes.size()>1){
                    //pick nodes with duplicate weights with equal likelihood 
                    random_node = sample_dups_uniformly(dup_nodes,random_engine);
                }else{
                    random_node = dup_nodes[0];
                }
                

                //get the edge weights of random node
                vector <int> rand_ew; 
                unordered_map<size_t, size_t> rand_node_edges = contracted_graph[random_node];
                for_each(rand_node_edges.begin(), rand_node_edges.end() , [&](pair<size_t, size_t > element){
                        //push back the weights 
                         rand_ew.push_back(element.second);
                });

                // create a discrete distrbution with edge weights 
                discrete_distribution<int> edges_distribution(begin(rand_ew), end(rand_ew));

                //pick a random edge weight proportional to its value
                size_t random_edge_weight = edges_distribution(random_engine);

                vector<int> dup_edges = find_dups(rand_node_edges, random_edge_weight);

                //if there are edges with duplicate total weights, sample from them uniformly
                int other_node;
                if(dup_edges.size()>1){
                    other_node = sample_dups_uniformly(dup_edges,random_engine);
                }else{
                    other_node = dup_edges[0];
                }

                //contract edge between random node and other node 
                uf.union_groups(random_node, other_node);

                
                // check the new size of super nodes after contraction
                // if we have only two we can break out of the while loop
                vector<size_t> super_nodes = cg.get_nodes();
                if(super_nodes.size() == 2){
                    break;
                }

                // will hold most up-to-date contracted graphs weights
                cgraph_total_edge_weights.clear();

            }
        // or send back a pair containing min_cut_of_cgraph and uf objects so we can get the disjoint sets
        // can also send back the disjoint set instead of the object
        return uf;    
        } 

        vector<vector<int>> compute_min_cut(Graph graph, const int n_iterations, const int seed, int V){

            // compute min-cut twice and choose the min-cut with least total graph weights
            //the minimum total edge weight of graph will give us the min-cut
            structures::UnionFind uf1 = kargers_min_cut(graph, n_iterations, seed, V);
            structures::UnionFind uf1 = kargers_min_cut(graph, n_iterations, seed, V);

            //two dijoint sets are nodes contracted in each of supernodes
            //we will use these sets to get out of local optima
            //might need to send back a pair <int graph_min_cut, vector<vector<int>> disjoint_sets> for unit testing





        }

        size_t sample_dups_uniformly(vector<int> to_check, minstd_rand0 random_engine){
            int size = to_check.size();
            uniform_int_distribution<int> distribution(0,size-1);
            int node_index = distribution(random_engine);

            size_t random_node = to_check[node_index];

            return random_node;

        }

        vector<int> find_dups(unordered_map<size_t, size_t> to_search, size_t num_to_find){
            vector<int> to_return;
            for_each(to_search.begin(), to_search.end() , [&](pair<size_t, size_t > element){
                    if(element.second == num_to_find){
                        to_return.push_back(element.first);
                    }
                    
            });
            return to_return;


        }
         
    }
}<commit_msg>fixed sampling using indices from generator<commit_after>/**
 * \file min_cut_graph.cpp
 *
 * Contains implementation of min_cut_graph function
 */
#include <random>
#include "min_cut_graph.hpp"
#include <stdio.h> 
#include <stdlib.h>
#include <vector>
#include <structures/union_find.hpp>
#include "../contracting_graph.hpp"
#include <random>
//#define debug

namespace vg {
    namespace algorithms {

        using namespace std;

        #ifdef debug
                cerr << "some debug statement" << endl; 
        #endif


        structures::UnionFind kargers_min_cut(Graph graph, const int n_iterations, const int seed, int V) {
 
     
            minstd_rand0 random_engine(seed);
            structures::UnionFind uf(V, true);
            
            

            ContractingGraph cg(graph,uf); 
            unordered_map<size_t, size_t> cgraph_total_edge_weights;
            pair<vector<vector<size_t>>, size_t> to_return;
            
            while(V > 2){
                

                // get nodes will return the heads of all the nodes
                // at first call all nodes will be heads
                vector<size_t> super_nodes = cg.get_nodes();
                V = super_nodes.size();

                //get the total edge weights for super_nodes in contracted graph
                unordered_map<size_t, unordered_map<size_t, size_t>> contracted_graph;
                for (int i =0; i < super_nodes.size(); i++){
                    //get total edge weights for each super node
                    unordered_map<size_t, size_t> supernode_edge_weights = cg.get_edges(super_nodes[i]);
                    contracted_graph[super_nodes[i]] = supernode_edge_weights; 

                    // tally up the total weights of incident edges
                    size_t total_weight = 0;
                    for(pair<size_t, size_t >& element: supernode_edge_weights){
                        total_weight += element.second;
                    }
                
                    //add total edge weight for each super node
                    //ex: 2: {1:1, 4:14}, sum up 1+14 and put that in the total edge weight list for node #2
                    cgraph_total_edge_weights[super_nodes[i]] = total_weight;

                }

                // create a vector with the node weights 
                vector<int> node_weights;
                int node_num;
                for (int i =0; i <V; i++){
                    node_num = super_nodes[i];
                    node_weights.push_back(cgraph_total_edge_weights[node_num]);
                }
                // create a discrete distrbution with node weights 
                discrete_distribution<int> nodes_distribution(begin(node_weights), end(node_weights));
                
                //pick an node proportional to its total weight from incident edges
                //and chooses uniformly from duplicates
                //discrete distribution returns an index
                size_t random_weight_idx = nodes_distribution(random_engine);
                size_t random_node = super_nodes[random_weight_idx];
          

                //get the edge weights of random node
                vector <int> rand_ew; 
                unordered_map<size_t, size_t> rand_node_edges = contracted_graph[random_node];
                for_each(rand_node_edges.begin(), rand_node_edges.end() , [&](pair<size_t, size_t > element){
                        //push back the weights 
                         rand_ew.push_back(element.second);
                });
                //{edge:}

                // create a discrete distrbution with edge weights 
                discrete_distribution<int> edges_distribution(begin(rand_ew), end(rand_ew));

                //pick a random edge weight proportional to its value
                int other_node;
                size_t random_edge_weight_idx = edges_distribution(random_engine);
                int count = 0;
                for (pair<size_t, size_t>& element : rand_node_edges){
                    //iterate through the unordered_map rand_node:{other_node: edge_weight} 
                    //use the idx to access other node
                    if (count==random_edge_weight_idx){
                        other_node = element.first;
                        break;
                    }
                    count++;

                }
 
                //contract edge between random node and other node 
                uf.union_groups(random_node, other_node);

                
                // check the new size of super nodes after contraction
                // if we have only two we can break out of the while loop
                // vector<size_t> super_nodes = cg.get_nodes();
                if(cg.get_nodes().size() == 2){
                    //compute the min cut of graph which is equal to the total edge weights of two supernodes 
                    size_t min_cut;
                    for (pair<size_t, size_t>& element: cgraph_total_edge_weights){
                        min_cut += element.second;
                    }

                    vector<vector<size_t>> disjoint_sets;
                    vector<size_t> d1, d2;
                    for(int i = 0; i<cg.get_nodes().size(); i++){
                        vector<int> d_set;
                        for(pair<size_t, size_t>& element: contracted_graph[i]){
                            d_set.push_back(element.first);
                        }
                        disjoint_sets.push_back(d_set);

                    }
                    to_return = make_pair(disjoint_sets, min_cut);
                    break;
                }

                // will hold most up-to-date contracted graphs weights
                cgraph_total_edge_weights.clear();

            }
            
            
        // or send back a pair containing contracted_graph, cgraph_total_edge_weights
        return to_return;    
        } 

        pair<vector<vector<size_t>>, size_t> compute_min_cut(Graph graph, const int n_iterations, const int seed, int V){

            // compute min-cut twice and choose the min-cut with least total graph weights
            //the minimum total edge weight of graph will give us the min-cut
            pair<vector<vector<size_t>>, size_t> to_return;
            pair<vector<vector<size_t>>, size_t> min_cut1 = kargers_min_cut(graph, n_iterations, seed, V);
            pair<vector<vector<size_t>>, size_t> min_cut2 = kargers_min_cut(graph, n_iterations, seed, V);

            if (min_cut1.second < min_cut2.second){
                to_return = min_cut1;

            }else{
                to_return = min_cut2;

            }

            return to_return;

        }
         
    }
}
{'fraction_non_alphanumeric': 0.07713175452745802, 'fraction_numerical': 0.003739277073099201, 'mean_word_length': 1.6185448262622384, 'pattern_counts': {'":': 0, '<': 89, '<?xml version=': 0, '>': 79, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2248125', 'n_tokens_mistral': 3762, 'n_tokens_neox': 3449, 'n_words': 992}