/*****************************************************************//**
 * \file   SubsetRowPadberg.h
 * \brief  Finds and adds odd holes to the node on the conflicting columns containing at least two subjects in common.
 * This heuristic avoids the limitation of Groetschel Method that is the non elementary odd cycles.
 *
 * \author talmefta
 * \date   January 2023
 *********************************************************************/
#ifndef SUBSETROWPADBERG_H
#define SUBSETROWPADBERG_H

#include "Header.h"
#include "CutGeneratorAbstract.h"
#include "RestrictedMasterProblem.h"
#include "PricingProblem.h"
#include "ColumnGeneration.h"
#include "lemon/dijkstra.h"
#include "lemon/smart_graph.h"
using namespace lemon;
using SptSolver = Dijkstra<SmartGraph, SmartGraph::EdgeMap<double>>;

 /**
  * \class SubsetRowPadberg.
     Finds and adds odd holes to the node on the conflicting columns containing at least two subjects in common.
 * This heuristic avoids the limitation of Groetschel Method that is the non elementary odd cycles.
 */


//struct lifting_node {
//    int node = -1;
//    int lifting_coefficient = 0;
//    bool deleted = false;
//    lifting_node* parent = nullptr;
//    vector<lifting_node*> descendants = vector<lifting_node*>();
//};

class SubsetRowPadberg : public CutGeneratorAbstract<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>
{

protected:

    /*GRBEnv* env;
    GRBModel* model;*/
    GRBLinExpr		 objective;
    vector<GRBConstr> node_packing_constraints;
    const vector<Vertex>& vertices;
    int maxNumberPerIteration;
    bool isSRNotFound;

public:


    /**
     * Constructor with pricing problem.
     *
     * \param instance: Instance&
     */
    SubsetRowPadberg(const vector<Vertex>& vertices, const int& maxNumberPerIteration) : CutGeneratorAbstract(), vertices(vertices) {
        //env = new GRBEnv();
        ////env->set("LogFile", "OddHolePadberg.log");
        //env->start();

        //model = new GRBModel(*env);
        //model->set(GRB_IntParam_LogToConsole, 0);
        /*this->min_violation = ::OMEGA;
        this->max_violation = ::EPSILON;*/
        this->maxNumberPerIteration = maxNumberPerIteration;
        this->isSRNotFound = false;
        //this->isOHnotFound = false;
    }

    void reset_found_inequality() override {
        this->isSRNotFound = false;
    }

    /**
     * \brief Destructor.
     *
     */
    virtual ~SubsetRowPadberg()
    {
        /*delete model;
        delete env;*/
        
    }


    /**
    * \brief Evaluates if the handler (the algorithm) can handle (solve) the cutting procedure based on the code of request.
    *
    * \param request : string
    * \return True if the concrete algorithm can find the cuts, false otherwise.
    */
    bool can_cut(const string& request) const override
    {
        return request == "SUBSETROWPADBERG" || request == "WHATEVER";
    }

    /**
     * Tries to find odd holes to add to the node. Stores the new cuts if any in the node's cut_constraints.
     * See https://doi.org/10.1287/mnsc.39.6.657
     *
     * \param node: Node<class RestrictedMasterProblem, class PricingSubProblem, class ColumnGeneration>&
     */
    bool cut(Node<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>& node) override {


        if (can_cut(node.get_restricted_master_problem()->get_cut_request()) && node.get_depth() <= ::MAXLEVELTREESEPARATION && node.get_depth() >= ::MINLEVELTREESEPARATION &&
            cut_counter < ::MAXCUTSNUMBER && separation_time < ::MAXCUTSTIME) {
            clock_t start = clock();
            ////Consider the conflict_graph induced by the solution variables (having y_k > 0)
           ////Construct the induced conflict graph restricted to nodes with 0 < y_k < 1

           ///TO DO LATER///////////////////////////////////////////////////////////////////////////////////////////////
           /// Construct the conflict graph once and pass it as a parameter to the other cut generators if necessary
           /// Each cut generator takes the conflict graph if it is needed (Only clique and odd holes need conflict graph)
           /// Then checks if it is empty then may be it has to construct it
           /// Otherwise it is already done and the procedure of the cut generator can start immediately :)
           ////////////////////////////////////////////////////////////////////////////////////////////////// 

            //node.get_restricted_master_problem()->fake_solution();

            //node.get_restricted_master_problem()->write_solution_value_into_text(0);
           // node.get_restricted_master_problem()->write_solution_info_into_text(0);

           //We have here the indes set of the fractional variables (0 < y_k < 1)
            vector<int> indexes_restricted_conflict_graph;
            for (int k = 0; k < node.get_restricted_master_problem()->get_columns().size(); k++)
                if (node.get_restricted_master_problem()->get_solution()[k] > 0)
                {
                    if (node.get_restricted_master_problem()->get_solution()[k] < 1)
                        indexes_restricted_conflict_graph.push_back(k);
                }

            //We have here for each fractional variable, its the neighbors (the variables that conflict with it)
            map<int, vector<int>> restricted_conflicting_for_each_variable;
            int edgeNumb = 0;
            for (int k = 0; k < indexes_restricted_conflict_graph.size(); k++)
            {
                restricted_conflicting_for_each_variable[indexes_restricted_conflict_graph[k]] = {};
                for (int l = 0/*k + 1*/; l < indexes_restricted_conflict_graph.size(); l++)
                    if (l != k && node.get_restricted_master_problem()->get_columns()[indexes_restricted_conflict_graph[k]].conflicts_with(node.get_restricted_master_problem()->get_columns()[indexes_restricted_conflict_graph[l]]))
                        restricted_conflicting_for_each_variable[indexes_restricted_conflict_graph[k]].push_back(indexes_restricted_conflict_graph[l]);
                edgeNumb += restricted_conflicting_for_each_variable[indexes_restricted_conflict_graph[k]].size();
            }


            //Pick random set of root nodes R (The set can be limited to MAXROOT (Padberg 20-50% of conflict graph nodes)
            vector<unsigned int> indices(indexes_restricted_conflict_graph.size());
            iota(indices.begin(), indices.end(), 0);
            
            shuffle(indices.begin(), indices.end(), ::generator );
            int i = 0;
            int nb_max_root_nodes = MAXROOTS * indexes_restricted_conflict_graph.size();
            vector<unsigned int>::iterator it = indices.begin();
            while (i < nb_max_root_nodes)
            {
                i++;
                it++;
            }
            while (it != indices.end())
                it = indices.erase(it);

            vector<int> root_nodes(indices.size());
            for (int j = 0; j < root_nodes.size(); j++)
                root_nodes[j] = indexes_restricted_conflict_graph[indices[j]];



            //The set of odd holes 
            set<pair<vector<int>, double>> odd_holes;
            double minimal_violation = 1e5;
            double maximal_violation = 0;

            bool at_least_one_violated_odd_hole_inequality_found = false;
            int number_violated_odd_hole_inequality_found = 0;
            for (int& root : root_nodes) {

                //Construct the layered graph rooted at root
                //Use lemon to store the graph and compute the shortest path with dijkstra
                SmartGraph layered_graph;
                map<int, SmartGraph::Node> nodes;
                map<pair<int, int>, SmartGraph::Edge> edges;
                
               //cout << "root\t" << root << endl;
               

                map<int, vector<int>> level_graph;
                map<int, vector<SmartGraph::Edge>> edges_per_level;

                map<int, bool> node_already_put_in_level;
                for (auto& node : indexes_restricted_conflict_graph)
                    node_already_put_in_level[node] = false;

                //Initialize the layerd graph with root
                nodes[root] = layered_graph.addNode();
                SmartGraph::NodeMap<int> node_map(layered_graph);
                node_map[nodes[root]] = root;
                level_graph[0].push_back(root);
                node_already_put_in_level[root] = true;
                edges_per_level[0] = {};

                //Create new levels until no more nodes for a new level
                bool success;
                int current_level = 0;

                do {
                    //Create current level and assign each edge (u,v) the value 1 - x_i - x_j
                    success = false;
                    for (auto& node_i : level_graph[current_level])
                    {
                        for (auto& neighbor : restricted_conflicting_for_each_variable[node_i])
                        {
                            if (!node_already_put_in_level[neighbor])
                            {
                                nodes[neighbor] = layered_graph.addNode();
                                node_map[nodes[neighbor]] = neighbor;
                                level_graph[current_level + 1].push_back(neighbor);
                                node_already_put_in_level[neighbor] = true;
                                edges[{node_i, neighbor}] = layered_graph.addEdge(nodes[node_i], nodes[neighbor]);

                                success = true;
                            }
                            else
                            {
                                if (edges.count({ node_i, neighbor }) == 1 || edges.count({ neighbor,node_i }) == 1)
                                    ;
                                else {
                                    int min = min(node_i, neighbor);
                                    int max = max(node_i, neighbor);
                                    edges[{min, max}] = layered_graph.addEdge(nodes[min], nodes[max]);
                                }
                            }
                        }
                    }

                    //If next level empty then stop
                    if (!success)
                        continue;

                    current_level++;

                    //Call Bellman-Ford from the root with max length equal to current level
                    /*****************************************PREPARING DATA BELLMAN-FORD*****************************************************************************/
                    unordered_map<int, int> vectorNodesLinker;
                    vector<int> nodes_vector(nodes.size(), -1);
                    vector<vector<int>> incident_edges(nodes.size(), vector<int>());
                    int counter = 0;
                    for (map<int, SmartGraph::Node>::const_iterator it = nodes.begin(); it != nodes.end(); it++) {
                        nodes_vector.at(counter) = it->first;
                        vectorNodesLinker.insert(make_pair(it->first, counter));
                        counter++;
                    }
                    for (int l = 0; l < nodes_vector.size(); l++) {
                        int var_id = nodes_vector.at(l);
                        for (int j = 0; j < restricted_conflicting_for_each_variable.at(var_id).size(); j++) {
                            int dest = restricted_conflicting_for_each_variable.at(var_id).at(j);
                            if (node_already_put_in_level.at(dest)) {
                                int dest_pos = vectorNodesLinker.at(dest);
                                incident_edges.at(l).push_back(dest_pos);
                            }
                        }
                    }

                    //SmartGraph::EdgeMap<double> edge_map(layered_graph);
                    vector<vector<double>> edge_weights(nodes_vector.size(), vector<double>(nodes_vector.size(), 0.0));
                    for (auto& edge : edges) {
                        int u_pos = vectorNodesLinker.at(edge.first.first);
                        int v_pos = vectorNodesLinker.at(edge.first.second);
                        edge_weights.at(u_pos).at(v_pos) = 1 - node.get_restricted_master_problem()->get_solution()[edge.first.first] -
                            node.get_restricted_master_problem()->get_solution()[edge.first.second];
                        edge_weights.at(v_pos).at(u_pos) = 1 - node.get_restricted_master_problem()->get_solution()[edge.first.first] -
                            node.get_restricted_master_problem()->get_solution()[edge.first.second];
                        /*edge_map[edge.second] = 1 - node.get_restricted_master_problem()->get_solution()[edge.first.first] -
                            node.get_restricted_master_problem()->get_solution()[edge.first.second];*/
                    }
                    for (vector<int>::iterator node_i = level_graph[current_level].begin(); node_i != level_graph[current_level].end(); node_i++) {
                        int i_pos = vectorNodesLinker.at(*node_i);
                        for (vector<int>::iterator node_j = node_i + 1; node_j != level_graph[current_level].end(); node_j++) {
                            if (find(restricted_conflicting_for_each_variable[*node_i].begin(),
                                restricted_conflicting_for_each_variable[*node_i].end(), *node_j) != restricted_conflicting_for_each_variable[*node_i].end()) {
                                int j_pos = vectorNodesLinker.at(*node_j);
                                edges[{*node_i, * node_j}] = layered_graph.addEdge(nodes[*node_i], nodes[*node_j]);
                                edge_weights.at(i_pos).at(j_pos) = 1 - node.get_restricted_master_problem()->get_solution()[*node_i] -
                                    node.get_restricted_master_problem()->get_solution()[*node_j];
                                edge_weights.at(j_pos).at(i_pos) = 1 - node.get_restricted_master_problem()->get_solution()[*node_i] -
                                    node.get_restricted_master_problem()->get_solution()[*node_j];
                                
                                
                                /*edge_map[edges[{*node_i, * node_j}]] = 1 - node.get_restricted_master_problem()->get_solution()[*node_i] -
                                    node.get_restricted_master_problem()->get_solution()[*node_j];*/
                                edges_per_level[current_level].push_back(edges[{*node_i, * node_j}]);
                            }
                        }
                    }


                    int root_pos = vectorNodesLinker.at(root);
                    unordered_map<int, vector<int>> first_paths = bellmanFordSPP(true, root_pos, current_level, root_pos, nodes_vector, incident_edges, edges, edge_weights);

                    //Search for odd holes 
                    //for each edge (u,v) in current level
                    for (auto edge : edges_per_level[current_level]) {

                        for (auto edge1 : edges_per_level[current_level]) {
                            if (edge1 != edge) {
                                int u_pos = vectorNodesLinker.at(node_map[layered_graph.u(edge1)]);
                                int v_pos = vectorNodesLinker.at(node_map[layered_graph.v(edge1)]);
                                edge_weights.at(u_pos).at(v_pos) = BIGM;
                                edge_weights.at(v_pos).at(u_pos) = BIGM;
                            }
                        }

                        //find shortest path between u and root
                        
                        /*SptSolver spt(layered_graph, edge_map);
                        spt.run(layered_graph.u(edge), nodes[root]);
                        double path_value = spt.dist(nodes[root]);*/
                        int id_var_u = node_map[layered_graph.u(edge)];
                        unordered_map<int, vector<int>>::const_iterator path_finder = first_paths.find(id_var_u);
                        if (path_finder != first_paths.end()) {
                            //vector<SmartGraph::Node> path;
                            //for (SmartGraph::Node v = nodes[root]; v != layered_graph.u(edge); v = spt.predNode(v))
                            //    if (v != INVALID && spt.reached(v)) //special LEMON node constant
                            //        path.push_back(v);

                            //path.push_back(layered_graph.u(edge));

                                  //Store the indices of the corresponding variables from this first shortest path 
                            //vector<int> first_path;
                           /* cout << "fitst path ";
                            for (auto p = path_finder->second.begin(); p != path_finder->second.end(); ++p) {
                                cout << *p << " ";
                            }
                            cout << "\n";
                           
                           cout << "\nBLOCK\n";*/
                            //block the all the nodes that are adjacent to nodes of this path by assigning the corresponding edges the weight bigM
                            for (auto& node : path_finder->second) {
                                if (node != root) {
                                    int node_pos = vectorNodesLinker.at(node);
                                    //cout << "node " << node << "\n";
                                    for (auto& neighbor : restricted_conflicting_for_each_variable[node]) {
                                        //cout << "neigh " << neighbor << "\n";
                                        if (node_already_put_in_level[neighbor]) {
                                            int neighbour_pos = vectorNodesLinker.at(neighbor);
                                            if (edges.count({ node, neighbor }) == 1) {
                                                edge_weights.at(node_pos).at(neighbour_pos) = BIGM;
                                                edge_weights.at(neighbour_pos).at(node_pos) = BIGM;
                                                //edge_map[edges[{node, neighbor}]] = BIGM;
                                                //cout << "block " << BIGM << endl;
                                            }
                                            else if (edges.count({ neighbor, node }) == 1) {
                                                edge_weights.at(node_pos).at(neighbour_pos) = BIGM;
                                                edge_weights.at(neighbour_pos).at(node_pos) = BIGM;
                                                //edge_map[edges[{neighbor, node}]] = BIGM;
                                                //cout << "block " << BIGM << endl;
                                            }
                                            else
                                                cout << "ERROR" << endl;
                                            //Then To be sure that this neighbor is blocked, we assign to the edges incident to neighbor
                                            //the wight BigM
                                            if (neighbor != root && neighbor != node_map[layered_graph.v(edge)])
                                                for (auto& neighbor_neighbor : restricted_conflicting_for_each_variable[neighbor]) {
                                                    //cout << "neighOFneigh " << neighbor_neighbor << "\n";
                                                    if (neighbor_neighbor != root)
                                                        if (node_already_put_in_level[neighbor_neighbor]) {
                                                            int neighbour_neighbour_pos = vectorNodesLinker.at(neighbor_neighbor);
                                                            if (edges.count({ neighbor, neighbor_neighbor }) == 1) {
                                                                //edge_map[edges[{neighbor, neighbor_neighbor}]] = BIGM;
                                                                edge_weights.at(neighbour_neighbour_pos).at(neighbour_pos) = BIGM;
                                                                edge_weights.at(neighbour_pos).at(neighbour_neighbour_pos) = BIGM;
                                                                //cout << "block " << BIGM << endl;
                                                            }
                                                            else if (edges.count({ neighbor_neighbor, neighbor }) == 1) {
                                                                //edge_map[edges[{neighbor_neighbor, neighbor}]] = BIGM;
                                                                //cout << "block " << BIGM << endl;
                                                                edge_weights.at(neighbour_neighbour_pos).at(neighbour_pos) = BIGM;
                                                                edge_weights.at(neighbour_pos).at(neighbour_neighbour_pos) = BIGM;
                                                            }
                                                            else
                                                                cout << "ERROR" << endl;
                                                        }

                                                }
                                        }

                                    }
                                }
                                //cout << "\n\n";
                            }

                            //Find shortest path between v and root
                            //Call Bellman-Ford from the root with max length equal to current level
                            int id_var_v = node_map[layered_graph.v(edge)];
                            int v_pos = vectorNodesLinker.at(id_var_v);
                            unordered_map<int, vector<int>> second_path = bellmanFordSPP(false, root_pos, current_level, v_pos, nodes_vector, incident_edges, edges, edge_weights);
                            unordered_map<int, vector<int>>::const_iterator path_finder_root = second_path.find(root);
                            /*SptSolver spt_2(layered_graph, edge_map);
                            spt_2.run(layered_graph.v(edge), nodes[root]);
                            path_value = spt_2.dist(nodes[root]);*/

                            //If value shortest path v to root < bigM
                            if (path_finder_root != second_path.end()) {
                                //Odd cycle containing root, u and v
                                //Construct the odd cycle and Check if this odd cycle implies a violated odd hole
                                //vector<SmartGraph::Node> path;
                                //for (SmartGraph::Node v = nodes[root]; v != layered_graph.v(edge); v = spt_2.predNode(v))
                                //    if (v != INVALID && spt_2.reached(v)) //special LEMON node constant
                                //        path.push_back(v);

                                //path.push_back(layered_graph.v(edge));

                                //Store the indices of the corresponding variables from this first shortest path 
                                //vector<int> second_path;
                                //cout << "second path ";
                                //for (auto p = path_finder_root->second.begin(); p != path_finder_root->second.end(); ++p) {
                                //    //second_path.push_back(node_map[*p]);
                                //    cout << *p << " ";
                                //}
                                //cout << "\n";

                                //check if the conctenation of the two paths form a cycle
                                vector<int> odd_hole;
                                for (auto& node : path_finder->second)
                                    odd_hole.push_back(node);
                                for (auto& node : path_finder_root->second)
                                    if (node != root)
                                        odd_hole.push_back(node);

                                sort(odd_hole.begin(), odd_hole.end());

                                /*cout << "OH ";
                                for (int k = 0; k < odd_hole.size(); k++) {
                                    cout << odd_hole.at(k) << " ";
                                }
                                cout << "\n";*/
                                double value_odd_cycle = 0;
                                for (auto& variable : odd_hole)
                                    value_odd_cycle += node.get_restricted_master_problem()->get_solution()[variable];

                                //cout << "VALUE " << value_odd_cycle << "\t" << ceil((odd_hole.size() - 1) / 2.0) + VIOLATIONEPSILON << endl;

                                if (value_odd_cycle > ceil((odd_hole.size() - 1) / 2.0) + VIOLATIONEPSILON) {

                                    int old_size_odd_holes = odd_holes.size();
                                    odd_holes.insert({ odd_hole, value_odd_cycle - ceil((odd_hole.size() - 1) / 2.0) });
                                    if (odd_holes.size() > old_size_odd_holes)
                                    {
                                        if (value_odd_cycle - ceil((odd_hole.size() - 1) / 2.0) < minimal_violation)
                                            minimal_violation = value_odd_cycle - ceil((odd_hole.size() - 1) / 2.0);

                                        if (value_odd_cycle - ceil((odd_hole.size() - 1) / 2.0) > maximal_violation)
                                            maximal_violation = value_odd_cycle - ceil((odd_hole.size() - 1) / 2.0);

                                        at_least_one_violated_odd_hole_inequality_found = true;
                                    }
                                }



                            }

                            //Unbock the neighbors of the forst path
                            for (auto& edge : edges) {
                                int u_pos = vectorNodesLinker.at(edge.first.first);
                                int v_pos = vectorNodesLinker.at(edge.first.second);
                                if (edge_weights.at(u_pos).at(v_pos) >= BIGM) {
                                    edge_weights.at(u_pos).at(v_pos) = 1 - node.get_restricted_master_problem()->get_solution()[edge.first.first] -
                                        node.get_restricted_master_problem()->get_solution()[edge.first.second];
                                    edge_weights.at(v_pos).at(u_pos) = 1 - node.get_restricted_master_problem()->get_solution()[edge.first.first] -
                                        node.get_restricted_master_problem()->get_solution()[edge.first.second];
                                }
                                /*if (edge_map[edge.second] >= BIGM) {
                                    edge_map[edge.second] = edge_map[edge.second] = 1 - node.get_restricted_master_problem()->get_solution()[edge.first.first] -
                                        node.get_restricted_master_problem()->get_solution()[edge.first.second];
                                }*/
                            }


                        }

                        for (auto edge1 : edges_per_level[current_level]) {
                            int u_pos = vectorNodesLinker.at(node_map[layered_graph.u(edge1)]);
                            int v_pos = vectorNodesLinker.at(node_map[layered_graph.v(edge1)]);
                            if (edge_weights.at(u_pos).at(v_pos) >= BIGM) {
                                edge_weights.at(u_pos).at(v_pos) = 1 - node.get_restricted_master_problem()->get_solution()[node_map[layered_graph.u(edge1)]] -
                                    node.get_restricted_master_problem()->get_solution()[node_map[layered_graph.v(edge1)]];
                                edge_weights.at(v_pos).at(u_pos) = 1 - node.get_restricted_master_problem()->get_solution()[node_map[layered_graph.u(edge1)]] -
                                    node.get_restricted_master_problem()->get_solution()[node_map[layered_graph.v(edge1)]];
                            }
                           /* if (edge_map[edge1] >= BIGM) {
                                edge_map[edge1] = edge_map[edge1] = 1 - node.get_restricted_master_problem()->get_solution()[node_map[layered_graph.u(edge1)]] -
                                    node.get_restricted_master_problem()->get_solution()[node_map[layered_graph.v(edge1)]];
                            }*/
                        }

                    }

                    break;

                } while (success);

                if (odd_holes.size() >= this->maxNumberPerIteration) {
                    break;
                }

                clock_t end1 = clock();
                double duration = (float)(end1 - start) / CLOCKS_PER_SEC;
                if (duration > ::MAXTIMESEPARATIONROUND) {
                    break;
                }

            }

            /***************************************************************FROM ODDHOLE TO SUBSETROW***************************************************************************/
            ofstream oddHole_violated;
            string file_name = ::solutionPath + ::instanceName + "_subsetRow_violated.txt";
            oddHole_violated.open(file_name, ios::app);
            int number_per_it = 0;
            oddHole_violated << "BaB node " << node.get_id() << " LEVEL " << node.get_depth() << "\n";
            oddHole_violated << "VERT " << restricted_conflicting_for_each_variable.size() << " EDGE " << edgeNumb << "\n";
            oddHole_violated << "MIN VIOL " << minimal_violation << " MAX VIOL " << maximal_violation << "\n";

            vector<vector<int>> violated_subset_row;
            for (auto odd_hole : odd_holes) {
                vector<int> subset;
                //cout << "ODDHOLE\n";
                for (int i = 0; i < odd_hole.first.size() - 1; i++) {
                    const Exchange* e = &node.get_restricted_master_problem()->get_columns().at(odd_hole.first.at(i));
                    for (int j = i + 1; j < odd_hole.first.size(); j++) {
                        int id = e->first_vertex_in_common(node.get_restricted_master_problem()->get_columns().at(odd_hole.first.at(j)));
                        if (id != -1) {
                            /*cout << "FRIST\n" << e->toString() << endl;
                            cout << "SECOND\n" << node.get_restricted_master_problem()->get_columns().at(odd_hole.first.at(j)).toString() << endl;
                            cout << "ID\t" << id << endl;*/
                            subset.push_back(id);
                        }
                    }
                }

                for (auto& node_odd_hole : odd_hole.first) {
                    const Exchange* e = &node.get_restricted_master_problem()->get_columns().at(node_odd_hole);
                    //cout << e->toString() << endl;
                    oddHole_violated << node_odd_hole << " ";
                }
                oddHole_violated << "ssi subset ";
                //cout << "subset ";
                for (int i = 0; i < subset.size(); i++) {
                    oddHole_violated << subset.at(i) << " ";
                    //cout << subset.at(i) << "\t";
                }
                //cout << "\n";
                /*if (count(subset.begin(), subset.end(), 9) > 1) {
                    cout << "stop\n";
                }*/
                oddHole_violated << "\n";
                violated_subset_row.push_back(subset);
            }

            int gcd = 2;
            int wordsNumber = this->vertices.at(1).getNgSet().size();
            for (int i = 0; i < violated_subset_row.size(); i++) {
                vector<int> subset_bit(wordsNumber, 0);
                vector<int> multipliers;
                double rhs = 0.0;
                string subsetToString;
                for (int j = 0; j < violated_subset_row.at(i).size(); j++) {
                    int id = violated_subset_row.at(i).at(j);
                    subsetToString += "_" + to_string(id);
                    multipliers.push_back(1); 
                    rhs += 1.0;
                    const Vertex* v = &this->vertices.at(id);
                    subset_bit.at(v->getWord()) += v->getBitKey();
                }
                rhs /= static_cast<double>(gcd);
                rhs += ::EPSILON;
                rhs = floor(rhs);
                node.add_cut_constraint(new SubsetRowConstraint<GRBConstr>(rhs, "<=", violated_subset_row.at(i), subset_bit, multipliers, gcd, subsetToString, "SUBSETROW"));
                node.get_cut_constraints().back()->set_birth(node.get_restricted_master_problem()->get_solving_rmp_iteration());
                node.get_cut_constraints().back()->set_become_effective(node.get_restricted_master_problem()->get_solving_rmp_iteration());
                node.get_restricted_master_problem()->add_cut_constraint(node.get_cut_constraints().back(), node.get_cut_constraints().size() - 1, true);
                number_per_it++;
            }

            
            cut_counter += number_per_it;

            if (number_per_it == 0) {
                this->isSRNotFound = true;
            }
           // number_per_it = violated_subset_row.size();

           // //Lifting an odd hole by Nemhauser and Sigismondi https://doi.org/10.1057/jors.1992.71
           // /*Initialization step*/
           // //Let H be the odd hole we want to lift
           // //Construct V_H the set of nodes in V\H which have at least three links with the odd hole H

           // set<vector<int>> lifted_odd_holes;
           //// node.get_restricted_master_problem()->write_solution_value();

           // number_violated_odd_hole_inequality_found = odd_holes.size();
           // for (auto& odd_hole : odd_holes)
           // {
           //     bool is_lifted = false;
           //     vector<int> candidate_nodes;
           //     for (auto& node : indexes_restricted_conflict_graph)
           //     {
           //         if (find(odd_hole.first.begin(), odd_hole.first.end(), node) == odd_hole.first.end())
           //         {
           //             int number_links = 0;
           //             for (auto& node_odd_hole : odd_hole.first)
           //             {
           //                 if (find(restricted_conflicting_for_each_variable[node_odd_hole].begin(),
           //                     restricted_conflicting_for_each_variable[node_odd_hole].end(), node) !=
           //                     restricted_conflicting_for_each_variable[node_odd_hole].end())
           //                     number_links++;
           //             }
           //             if (number_links >= 3)
           //                 candidate_nodes.push_back(node);

           //         }
           //     }

           //     //for each candidate node in V_H, compute its lifting coefficient when lifted first by solving the node packing problem


           //     //For each candidate node,
           //     //  construct the corresponding decision variable
           //     //  construct the induced graph H \union {v_1, v_2, ..., v_{j-1}}) \ N(v_j)
           //     //  construct the node packig constraints
           //     //  solve he problem
           //     //  lifting coefficient alpha_{v_j} = k - beta_{v_j} where v_j is the candidate node,
           //     //  k = (|H| - 1 )/2, beta_{v_j} = optimal value of the node packing problem.
           //     map<int, int> lifting_coeffcients;
           //     for (auto& node_vj : candidate_nodes)
           //     {
           //         vector<int> induced_nodes = odd_hole.first;
           //         vector<int>::iterator node = induced_nodes.begin();
           //         while (node != induced_nodes.end())
           //         {
           //             if (find(restricted_conflicting_for_each_variable[*node].begin(),
           //                 restricted_conflicting_for_each_variable[*node].end(), node_vj)
           //                 != restricted_conflicting_for_each_variable[*node].end())
           //                 node = induced_nodes.erase(node);
           //             else
           //                 node++;
           //         }

           //         //Construct the node packing problem
           //         //Max beta_{v_j} = SUM_{v in H} x_v + SUM_{i = 1; i = j -1} alpha_{v_i} x_{v_i}
           //         //Subject to
           //         //              x_u + x_v <= 1 foreach (u,v) in induced graph (H \union {v_1, v_2, ..., v_{j-1}}) \ N(v_j)
           //         //              x_v in {0,1} foreach v in induced graph (H \union {v_1, v_2, ..., v_{j-1}}) \ N(v_j)
           //         //For each variable v in the the induced graph, construct the corresponding decision variable x_v and add it to the objective function
           //         objective = 0;
           //         map<int, GRBVar> x_v;
           //         for (auto& node : induced_nodes)
           //         {
           //             string name = "x_" + to_string(node);
           //             x_v[node] = model->addVar(0.0, 1.0, 0.0, GRB_BINARY, name);
           //             objective += x_v[node];
           //         }
           //         model->setObjective(objective, GRB_MAXIMIZE);


           //         for (auto& constraint : node_packing_constraints)
           //             model->remove(constraint);

           //         node_packing_constraints.clear();
           //         for (vector<int>::iterator node_i = induced_nodes.begin(); node_i != induced_nodes.end(); node_i++)
           //             for (vector<int>::iterator node_j = node_i + 1; node_j != induced_nodes.end(); node_j++)
           //             {
           //                 if (find(restricted_conflicting_for_each_variable[*node_i].begin(),
           //                     restricted_conflicting_for_each_variable[*node_i].end(), *node_j)
           //                     != restricted_conflicting_for_each_variable[*node_i].end())
           //                 {
           //                     node_packing_constraints.push_back(model->addConstr(x_v[*node_i] + x_v[*node_j] <= 1, "node_packing"));
           //                 }
           //             }
           //         model->optimize();
           //         int beta_vj = model->get(GRB_DoubleAttr_ObjVal);
           //         if (beta_vj > (odd_hole.first.size() - 1) / 2)
           //             lifting_coeffcients[node_vj] = (odd_hole.first.size() - 1) / 2;
           //         else
           //             lifting_coeffcients[node_vj] = (odd_hole.first.size() - 1) / 2 - beta_vj;
           //     }

           //     //compute degrees of candidate nodes in the induced graph of V_H 
           //     map<int, int> degrees_of_candidate_nodes_in_Vh;
           //     for (map<int, int>::iterator node_i = lifting_coeffcients.begin(); node_i != lifting_coeffcients.end(); node_i++)
           //     {
           //         int degree = 0;
           //         for (map<int, int>::iterator node_j = next(node_i); node_j != lifting_coeffcients.end(); node_j++)
           //         {
           //             if (find(restricted_conflicting_for_each_variable[node_i->first].begin(),
           //                 restricted_conflicting_for_each_variable[node_i->first].end(), node_j->first)
           //                 != restricted_conflicting_for_each_variable[node_i->first].end())
           //                 degree++;
           //         }
           //         degrees_of_candidate_nodes_in_Vh[node_i->first] = degree;
           //     }

           //     //Delete from V_H those nodes whose lifting coefficient equals zero.
           //     for (auto& pair : lifting_coeffcients)
           //         if (pair.second == 0)
           //             lifting_coeffcients.erase(pair.first);

           //     //There is at least one node for which the lifting coefficient is strictly positif when lifted first
           //     //That means that the odd hole is at least lifted once 
           //     if (!lifting_coeffcients.empty())
           //         is_lifted = true;
           //     
           //     //Ordering the remaining candidate nodes first by increasing order of lifting coeffs, and then by decreasing order of degrees in the induced graph V_H
           //     vector<int> ordered_candidate_nodes;
           //     for (auto& node_vj : lifting_coeffcients)
           //     {
           //         if (ordered_candidate_nodes.empty())
           //             ordered_candidate_nodes.push_back(node_vj.first);
           //         else if (lifting_coeffcients[node_vj.first] < lifting_coeffcients[ordered_candidate_nodes.front()])
           //             ordered_candidate_nodes.insert(ordered_candidate_nodes.begin(), node_vj.first);
           //         else
           //         {
           //             vector<int>::iterator node_iterator = ordered_candidate_nodes.begin();
           //             while (node_iterator != ordered_candidate_nodes.end() && degrees_of_candidate_nodes_in_Vh[node_vj.first] < degrees_of_candidate_nodes_in_Vh[*node_iterator])
           //                 node_iterator++;
           //             ordered_candidate_nodes.insert(node_iterator, node_vj.first);
           //         }
           //     }

           //     //Construct the lifting tree
           //     map<int, vector<lifting_node*>> lifting_tree;
           //     lifting_tree[0].push_back(new lifting_node());
           //     map<int, vector<int>> lifting_tree_levels;
           //     //Put in the level 1 of the tree the sorted candidate nodes. The leftmost node is on the top of the list
           //     for (auto& node_vj : ordered_candidate_nodes)
           //     {
           //         lifting_tree[0].back()->descendants.push_back(new lifting_node);
           //         lifting_tree[0].back()->descendants.back()->node = node_vj;
           //         lifting_tree[0].back()->descendants.back()->lifting_coefficient = lifting_coeffcients[node_vj];
           //         lifting_tree[0].back()->descendants.back()->parent = lifting_tree[0].back();
           //         lifting_tree[1].push_back(lifting_tree[0].back()->descendants.back());
           //     }

           //     lifting_tree_levels[1] = ordered_candidate_nodes;

           //   
           //     //Iterative step
           //     //I need to parse the tree and not the lifting_tree_levels!!!!
           //     for (auto& level : lifting_tree)
           //     {
           //         if (level.first >= 1)
           //         {
           //             for (auto& node_i : level.second)
           //             {
           //                 if (!node_i->deleted)
           //                 {
           //                     vector<lifting_node*> L_i, R_i; //L_i nodes in the same level as node_i that are located in the left and right of node_i
           //                     int l_i = 0;
           //                     while (level.second[l_i] != node_i)
           //                     {
           //                         if (!level.second[l_i]->deleted && level.second[l_i]->parent->node == node_i->parent->node)
           //                             L_i.push_back(level.second[l_i]);
           //                         l_i++;
           //                     }
           //                     int r_i = l_i + 1;
           //                     while (r_i != level.second.size())
           //                     {
           //                         if (!level.second[r_i]->deleted && level.second[r_i]->parent->node == node_i->parent->node)
           //                             R_i.push_back(level.second[r_i]);
           //                         r_i++;
           //                     }

           //                     bool adjacent = false;
           //                     for (auto& node_j : L_i)
           //                     {
           //                         //Here he uses the proposition 3 I think?! can leed to redundant constraints if we did not do this?!
           //                         if (find(restricted_conflicting_for_each_variable[node_i->node].begin(),
           //                             restricted_conflicting_for_each_variable[node_i->node].end(), node_j->node)
           //                             != restricted_conflicting_for_each_variable[node_i->node].end())
           //                         {
           //                             adjacent = true;
           //                             break;
           //                         }
           //                     }
           //                     if (adjacent)
           //                     {
           //                         //Delete  node_i from the tree
           //                         //Mark it as deleted for the moment, I will think to remove it physically later
           //                         node_i->deleted = true;
           //                     }
           //                     else
           //                     {
           //                         for (auto& node_j : L_i)
           //                         {
           //                             //If the lifting coefficient of $i$ at level $q$ and the lifting coefficient of $i$  as a descendant of $j$ at level  $q+1$  are different then
           //                             //use Proposition 3 to compute the lifting coefficient of  $j$
           //                             //and if it is positive, add  $j$  as a descendant of  $i$ at level  $q + 1$;
           //                             int alpha_node_i_q = node_i->lifting_coefficient;
           //                             int alpha_node_j_q = node_j->lifting_coefficient;
           //                             int alpha_node_i_q_plus_1 = 0;
           //                             for (auto& descendant : node_j->descendants)
           //                                 if (descendant->node == node_i->node)
           //                                     alpha_node_i_q_plus_1 = descendant->lifting_coefficient;
           //                             if (alpha_node_i_q != alpha_node_i_q_plus_1)
           //                             {
           //                                 //Use proposition 2 to compute lifting coefficient of node_j
           //                                 int alpha_node_j_q_plus_1 = alpha_node_j_q + alpha_node_i_q_plus_1 - alpha_node_i_q;
           //                                 if (alpha_node_j_q_plus_1 > 0)
           //                                 {
           //                                     //add node_j as a descendant of node_i
           //                                     lifting_tree[level.first + 1].push_back(new lifting_node);
           //                                     lifting_tree[level.first + 1].back()->node = node_j->node;
           //                                     lifting_tree[level.first + 1].back()->lifting_coefficient = alpha_node_j_q_plus_1;
           //                                     lifting_tree[level.first + 1].back()->parent = node_i;
           //                                     node_i->descendants.push_back(lifting_tree[level.first + 1].back());
           //                                     is_lifted = true;
           //                                 }
           //                             }

           //                         }
           //                         for (auto& node_j : R_i)
           //                         {
           //                             //if $j$ is adjacent to  $i$  then
           //                                 //the lifting coefficient of $j$ at level  $q + 1$ is the same as the lifting coefficient of $j$ at level  $q$;
           //                             int lifting_node_j;
           //                             if (find(restricted_conflicting_for_each_variable[node_i->node].begin(),
           //                                 restricted_conflicting_for_each_variable[node_i->node].end(),
           //                                 node_j->node) != restricted_conflicting_for_each_variable[node_i->node].end())
           //                             {
           //                                 lifting_node_j = node_j->lifting_coefficient;
           //                                 is_lifted = true;
           //                             }
           //                             else
           //                                 //else
           //                                     //compute the lifting coefficient of $j$ by solving a node packing problem;
           //                                 //if the lifting coefficient is greater than 0 then
           //                                     //add $j$ as a descendant of  $i$  at level  $q + 1$;
           //                             {
           //                                 //Construct the node packing problem with the corresponding induced graph of the odd_hole H and all the parents of node_j minus the neighbors of node_j
           //                                 map<int, int> induced_graph_node_j_with_lifting_coeff;
           //                                 for (auto parent = node_i; parent != nullptr; parent = parent->parent)
           //                                 {
           //                                     if (parent->parent != nullptr)
           //                                         if (find(restricted_conflicting_for_each_variable[node_j->node].begin(),
           //                                             restricted_conflicting_for_each_variable[node_j->node].end(),
           //                                             parent->node) == restricted_conflicting_for_each_variable[node_j->node].end())
           //                                         {
           //                                             induced_graph_node_j_with_lifting_coeff[parent->node] = parent->lifting_coefficient;
           //                                         }
           //                                     if (parent->parent == nullptr)
           //                                     {
           //                                         for (auto& _node : odd_hole.first)
           //                                         {
           //                                             if (find(restricted_conflicting_for_each_variable[node_j->node].begin(),
           //                                                 restricted_conflicting_for_each_variable[node_j->node].end(),
           //                                                 _node) == restricted_conflicting_for_each_variable[node_j->node].end())
           //                                                 induced_graph_node_j_with_lifting_coeff[_node] = 1;
           //                                         }
           //                                     }
           //                                 }
           //                                 //construct decision variables and objective
           //                                 map<int, GRBVar> x_v;
           //                                 objective = 0;
           //                                 for (auto& pair : induced_graph_node_j_with_lifting_coeff)
           //                                 {
           //                                     string name = "x_" + to_string(pair.first);
           //                                     x_v[pair.first] = model->addVar(0.0, 1.0, 0.0, GRB_BINARY, name);
           //                                     objective += pair.second * x_v[pair.first];
           //                                 }
           //                                 model->setObjective(objective, GRB_MAXIMIZE);


           //                                 for (auto& constraint : node_packing_constraints)
           //                                     model->remove(constraint);

           //                                 //construct the node packing constraints
           //                                 node_packing_constraints.clear();
           //                                 for (map<int, int>::iterator node_i = induced_graph_node_j_with_lifting_coeff.begin(); node_i != induced_graph_node_j_with_lifting_coeff.end(); node_i++)
           //                                     for (map<int, int>::iterator node_j = next(node_i); node_j != induced_graph_node_j_with_lifting_coeff.end(); node_j++)
           //                                     {
           //                                         if (find(restricted_conflicting_for_each_variable[node_i->first].begin(),
           //                                             restricted_conflicting_for_each_variable[node_i->first].end(), node_j->first)
           //                                             != restricted_conflicting_for_each_variable[node_i->first].end())
           //                                         {
           //                                             node_packing_constraints.push_back(model->addConstr(x_v[node_i->first] + x_v[node_j->first] <= 1, "node_packing"));
           //                                         }
           //                                     }
           //                                 //solve the model and extract the objective function
           //                                 model->optimize();
           //                                 int beta_vj = model->get(GRB_DoubleAttr_ObjVal);

           //                                 //Compute the lifting coefficient
           //                                 if (beta_vj > (odd_hole.first.size() - 1) / 2)
           //                                     lifting_node_j = (odd_hole.first.size() - 1) / 2;
           //                                 else
           //                                     lifting_node_j = (odd_hole.first.size() - 1) / 2 - beta_vj;

           //                             }
           //                             if (lifting_node_j > 0)
           //                             {
           //                                 //add node_j as a descendant of node_i
           //                                 lifting_tree[level.first + 1].push_back(new lifting_node);
           //                                 lifting_tree[level.first + 1].back()->node = node_j->node;
           //                                 lifting_tree[level.first + 1].back()->lifting_coefficient = lifting_node_j;
           //                                 lifting_tree[level.first + 1].back()->parent = node_i;
           //                                 node_i->descendants.push_back(lifting_tree[level.first + 1].back());
           //                                 is_lifted = true;
           //                             }
           //                         }
           //                     }
           //                 }
           //             }
           //         }
           //     }
           //     
           //     //Now I need to reconstitute the lifted odd holes
           //     // //each path from a leaf in the lifting tree to the root that is the original odd hole is a lifted odd hole
           //     if (!is_lifted)
           //     {
           //         map<int, int> odd_hole_coeff;
           //         for (auto& element : odd_hole.first)
           //             odd_hole_coeff.insert({ element, 1 });
           //         node.add_cut_constraint(new Constraint<GRBConstr>(odd_hole_coeff, map<pair<int, int>, int>(), ceil((odd_hole.first.size() - 1) / 2.0), "<=", "ODDHOLE", odd_hole.second));
           //         node.get_cut_constraints().back()->set_birth(node.get_restricted_master_problem()->get_solving_rmp_iteration());
           //         node.get_cut_constraints().back()->set_become_effective(node.get_restricted_master_problem()->get_solving_rmp_iteration());
           //         node.get_restricted_master_problem()->add_cut_constraint(node.get_cut_constraints().back());
           //     }
           //     else
           //     {
           //         for (auto& level : lifting_tree)
           //         {
           //            
           //             if (level.first >= 1)
           //                 for (auto& leaf : level.second)
           //                 {
           //                     if (leaf->descendants.empty())
           //                     {//construct the path from the leaf to the root
           //                         map<int, int> path;
           //                         for (auto node = leaf; node != nullptr; node = node->parent)
           //                         {
           //                             if (node->parent != nullptr)
           //                                 path[node->node] = node->lifting_coefficient;
           //                         }
           //                         vector<int> lifted_odd_hole = odd_hole.first;
           //                         map<int, int> lifted_odd_hole_coeff;
           //                         for (auto& element : lifted_odd_hole)
           //                         {
           //                             lifted_odd_hole_coeff.insert({ element, 1 });
           //                         }
           //                         for (auto& pair : path)
           //                         {
           //                             for (int i = 0; i < pair.second; i++)
           //                                 lifted_odd_hole.push_back(pair.first);
           //                            
           //                             lifted_odd_hole_coeff.insert(pair);
           //                             
           //                         }
           //                         sort(lifted_odd_hole.begin(), lifted_odd_hole.end());
           //                         int old_size_lifted_odd_holes = lifted_odd_holes.size();
           //                         lifted_odd_holes.insert(lifted_odd_hole);
           //                         //Store only non duplicate lifted odd holes in case there are some odd holes that take part of a maximal clique,
           //                         //They can produce duplicate lifted odd holes
           //                         if (old_size_lifted_odd_holes < lifted_odd_holes.size())
           //                         {
           //                             double value_odd_cycle = 0;
           //                             for (auto& variable : lifted_odd_hole_coeff)
           //                                 value_odd_cycle += variable.second * node.get_restricted_master_problem()->get_solution()[variable.first];

           //                             number_violated_odd_hole_inequality_found++;
           //                             node.add_cut_constraint(new Constraint<GRBConstr>(lifted_odd_hole_coeff, map<pair<int, int>, int>(), ceil((odd_hole.first.size() - 1) / 2.0), "<=", "LIFTEDODDHOLE", value_odd_cycle - ceil((odd_hole.first.size() - 1) / 2.0)));
           //                             node.get_cut_constraints().back()->set_birth(node.get_restricted_master_problem()->get_solving_rmp_iteration());
           //                             node.get_cut_constraints().back()->set_become_effective(node.get_restricted_master_problem()->get_solving_rmp_iteration());
           //                             node.get_restricted_master_problem()->add_cut_constraint(node.get_cut_constraints().back());
           //                         }
           //                     }
           //                 }
           //         }
           //     }



           //     //Free memory
           //     for (auto& level : lifting_tree)
           //     {
           //         for (auto& node : level.second)
           //             delete node;
           //     }
           // }

            clock_t end = clock();
            double duration = (float)(end - start) / CLOCKS_PER_SEC;
            separation_time += duration;
            node.set_cut_generation_time_spent(node.get_cut_generation_time_spent() + duration);
            node.set_nb_cuts_added(static_cast<int>(node.get_nb_cuts_added() + number_per_it));
            oddHole_violated << "TIME SEPARATION ROUND\t" << duration << "\n\n";
            oddHole_violated.close();
            

            //stats collection
            information.push_back(new CutFamilyInformation("CliqueInequalities", node.get_id(), cut_iteration, number_per_it, node.get_dual_bound(), duration, minimal_violation, maximal_violation));
            node.get_restricted_master_problem()->attach(information.back());

            if (number_per_it != 0) {
                return (number_per_it != 0);
            }
            else
                return CutGeneratorAbstract<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>::cut(node);
        }
        else
            return CutGeneratorAbstract<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>::cut(node);
    }
    
    unordered_map<int, vector<int>> bellmanFordSPP(const bool& isFirst, const int& root, const int& maxLength, const int& source, 
        const vector<int>& nodes_vector, const vector<vector<int>>& incident_edges, map<pair<int, int>, SmartGraph::Edge>& edges, const vector<vector<double>>& edge_weights) {

        //initialisation
        int maxLengthBF = maxLength + 1;
        vector<vector<double>> weights(maxLengthBF, vector<double>(nodes_vector.size(), ::OMEGA));
        weights.at(0).at(source) = 0.0;
        vector<vector<bool>> vertexLists(maxLengthBF, vector<bool>(nodes_vector.size(), false));
        vertexLists.at(0).at(source) = true;
        vector<vector<int>> walks(maxLengthBF, vector<int>(nodes_vector.size(), -1));
        int source_var = nodes_vector.at(source);
        walks.at(0).at(source) = 0;

        //iterations
        for (int k = 1; k < maxLengthBF; k++) {
            /*if (::isToPrint) {
                cout << "CURRENT LENGTH " << k << endl;
            }*/
            int previous = k - 1;
            for (int j = 0; j < nodes_vector.size(); j++) {
                if (vertexLists.at(previous).at(j)) {
                    int pos = j;
                    //int var = nodes_vector.at(pos);
                    /*if (::isToPrint) {
                        cout << "CURRENT NODE " << id << "\tBEST LABEL " << currentWeight << "\tBD " <<best_dual_price<<" edge "<< (this->cyclesLength - k) <<" CB "<<
                            currentWeight + (maxLength - k) * best_dual_price<<"\n";
                        cout << "Current path ";
                        for (int p = 0; p < walks.at(previous).at(id).size(); p++) {
                            cout << walks.at(previous).at(id).at(p) << " ";
                        }
                        cout << "\n";
                    }*/

                    for (int j = 0; j < incident_edges.at(pos).size(); j++) {
                        int dest_pos = incident_edges.at(pos).at(j);
                        int dest_var = nodes_vector.at(dest_pos);

                        double newCost = weights.at(previous).at(pos) + edge_weights.at(pos).at(dest_pos);

                        /*if (::isToPrint) {
                            cout << "DEST " << dest <<"\t"<<newCost << endl;
                        }*/

                        if (::strictly_less(newCost, weights.at(k).at(dest_pos))) {

                            weights.at(k).at(dest_pos) = newCost;
                            vertexLists.at(k).at(dest_pos) = true;
                            walks.at(k).at(dest_pos) = pos;
                            /*walks.at(k).at(dest_pos) = walks.at(k - 1).at(pos);
                            walks.at(k).at(dest_pos).push_back(dest_var);*/


                        }
                    }

                }

            }

        }

        unordered_map<int, vector<int>> paths;
        if (isFirst) {
            for (int i = 0; i < walks.at(maxLength).size(); i++) {
                if (weights.at(maxLength).at(i) < BIGM) {
                    int current = i;
                    vector<int> path(maxLength + 1, -1);
                    path.at(maxLength) = nodes_vector.at(current);
                    int lentgth = maxLength;
                    while (lentgth > 0) {
                        int previous = walks.at(lentgth).at(current);
                        current = previous;
                        lentgth--;
                        path.at(lentgth) = nodes_vector.at(current);
                    }
                    paths.insert(make_pair(nodes_vector.at(i), path));
                }
            }
        }
        else {
            if (weights.at(maxLength).at(root) < BIGM) {
                int current = root;
                vector<int> path(maxLength + 1, -1);
                path.at(maxLength) = nodes_vector.at(current);
                int lentgth = maxLength;
                while (lentgth > 0) {
                    int previous = walks.at(lentgth).at(current);
                    current = previous;
                    lentgth--;
                    path.at(lentgth) = nodes_vector.at(current);
                }
                paths.insert(make_pair(nodes_vector.at(root), path));
            }
        }

       return paths;

    }

};

#endif //SUBSETROWPADBERG_H