/*****************************************************************//**
 * \file   OddHole.h
 * \brief  Finds and adds vilated odd hole inequalities if any to the node on the conflicting columns containing at least two subjects in common.
 *
 * \author talmefta
 * \date   June 2022
 *********************************************************************/
#ifndef ODDHOLE_H
#define ODDHOLE_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 OddHole.
 * \brief  Finds and adds vilated odd hole inequalities if any to the node on the conflicting columns containing at least two subjects in common.
  */
class OddHole : public CutGeneratorAbstract<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>
{


public:
    /**
     * Constructor by default.
     */
    OddHole() : CutGeneratorAbstract() {}

    /**
     * \brief Destructor.
     *
     */
    virtual ~OddHole() {}


    /**
    * \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 == "ODDHOLE" || request == "WHATEVER";
    }

    /**
     * Tries to find clique inequality cuts to add to the node. Stores the new cuts if any in the node's cut_constraints.
     *
     * \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()))
        {
            //Construct conflict graph of fractional variables
            ////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
            clock_t start = clock();
          
            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);
                }

            map<int, vector<int>> restricted_conflicting_for_each_variable;
            for (int k = 0; k < indexes_restricted_conflict_graph.size(); k++)
            {
                restricted_conflicting_for_each_variable[indexes_restricted_conflict_graph[k]] = {};
                for (int l = k + 1; l < indexes_restricted_conflict_graph.size(); l++)
                    if (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]);
            }
           
           // node.get_restricted_master_problem()->write_solution_value();
            bool at_least_one_violated_odd_hole_inequality_found = false;
            //The set of odd holes 
            set<vector<int>> odd_holes;
            double minimal_violation = 1e5;
            double maximal_violation = 0;

            cout << "LEMON " << endl;
            if (!indexes_restricted_conflict_graph.empty())
            {
                //Duplicate each vertex i in the conflict graph into i'
                //Construct the bipartite graph with vertices i and i', 
                //and each edge [i,j] in the conflict graph yields the two edges [i, j'] and [i', j]
                // Having each the weight 1 - y*_i - y*_j >= 0

                SmartGraph bipartite_graph;
                map<int, SmartGraph::Node> nodes;
                //nodes first
                SmartGraph::Node current_node;
                for (auto y_k = indexes_restricted_conflict_graph.begin(); y_k != indexes_restricted_conflict_graph.end(); ++y_k)
                {
                    //Real node i
                    current_node = bipartite_graph.addNode();
                    nodes[*y_k] = current_node;

                    //Duplicate node i' with id' = i + last_node.id
                    current_node = bipartite_graph.addNode();
                    nodes[*y_k + indexes_restricted_conflict_graph.back() + 1] = current_node;
                }

                SmartGraph::NodeMap<int> node_map(bipartite_graph);
                for (auto& node : nodes)
                {
                    node_map[node.second] = node.first;
                }

                //then the edges with the weights through the weight_map
                SmartGraph::Edge current_edge;
                map<SmartGraph::Edge, double> edges_weights;



                for (auto y_k = restricted_conflicting_for_each_variable.begin(); y_k != restricted_conflicting_for_each_variable.end(); ++y_k)
                {
                    for (auto y_l = y_k->second.begin(); y_l != y_k->second.end(); y_l++)
                    {
                        SmartGraph::Node i = nodes[y_k->first];
                        SmartGraph::Node i_prime = nodes[y_k->first + indexes_restricted_conflict_graph.back() + 1];

                        SmartGraph::Node j = nodes[*y_l];
                        SmartGraph::Node j_prime = nodes[*y_l + indexes_restricted_conflict_graph.back() + 1];

                        double value_y_k = node.get_restricted_master_problem()->get_solution()[y_k->first];
                        double value_y_l = node.get_restricted_master_problem()->get_solution()[*y_l];

                        current_edge = bipartite_graph.addEdge(i, j_prime);
                        edges_weights[current_edge] = 1 - value_y_k - value_y_l; //do I have to be sure that this quantity is always greater than 0 or it is not mandatory???
                        current_edge = bipartite_graph.addEdge(i_prime, j);
                        edges_weights[current_edge] = 1 - value_y_k - value_y_l; //do I have to be sure that this quantity is always greater than 0 or it is not mandatory???
                    }
                }

                SmartGraph::EdgeMap<double> weight_map(bipartite_graph);
                for (auto& edge : edges_weights)
                {
                    weight_map[edge.first] = edge.second;
                }

                //For each vertex i in conflict graph, search the shortest path from i to i' SP(i,i') in the bipartite graph with Dijkstra algorithm
                //If the value of SP(i,i') < 1, then we have and odd cycle passign through i and violated by the fractional solution y*
                //Then in this case, construct the odd hole resulted inequality and add it to the node \sum y_i in SP(i,i') <= ceil(|SP(i,i')|/2)
                at_least_one_violated_odd_hole_inequality_found = false;
                SptSolver spt(bipartite_graph, weight_map);
                for (auto y_k : indexes_restricted_conflict_graph)
                {
                    //Search a shortest path from i to i_prime with Dijkstra
                    SmartGraph::Node       i = nodes[y_k];
                    SmartGraph::Node i_prime = nodes[y_k + indexes_restricted_conflict_graph.back() + 1];

                    spt.run(i, i_prime);
                    double path_value = spt.dist(i_prime);
                    if (!spt.path(i_prime).empty() && path_value + EPSILON < 1)
                    {
                        at_least_one_violated_odd_hole_inequality_found = true;
                        //We found a violated odd hole inequality passing through y_k
                        vector<SmartGraph::Node> path;
                        for (SmartGraph::Node v = i_prime; v != i; v = spt.predNode(v))
                        {
                            if (v != INVALID && spt.reached(v)) //special LEMON node constant
                            {
                                path.push_back(v);
                            }
                        }
                        path.push_back(i);

                        //Construct the variables from this inequality with the ids that are i_prime converted to i
                        vector<int> odd_hole;
                        for (auto p = path.rbegin(); p != path.rend() - 1; ++p)
                        {
                            if (node_map[*p] <= indexes_restricted_conflict_graph.back())
                                odd_hole.push_back(node_map[*p]);
                            else if (node_map[*p] >= indexes_restricted_conflict_graph.back() + 1)
                                odd_hole.push_back(node_map[*p] - indexes_restricted_conflict_graph.back() - 1);
                        }

                        if (!odd_hole.empty())
                        {
                            sort(odd_hole.begin(), odd_hole.end());
                            odd_holes.insert(odd_hole);
                        }
                    }
                }

              

                //Add the cut constraint (odd hole inequliaty) to the node as well as to the RMP
                for (auto& odd_hole : odd_holes)
                {
                 /*   node.add_cut_constraint(new Constraint<GRBConstr>(ceil((odd_hole.size() - 1) / 2.0), "<=", "ODDHOLE"));
                    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);*/
                  /*  double sum_value_odd_hole = 0;
                    for (auto& element : odd_hole)
                        sum_value_odd_hole += node.get_restricted_master_problem()->get_solution()[element];

                    if (sum_value_odd_hole - node.get_cut_constraints().back()->get_rhs() < minimal_violation)
                        minimal_violation = sum_value_odd_hole - node.get_cut_constraints().back()->get_rhs();

                    if (sum_value_odd_hole - node.get_cut_constraints().back()->get_rhs() > maximal_violation)
                        maximal_violation = sum_value_odd_hole - node.get_cut_constraints().back()->get_rhs();*/
                }
            }

            clock_t end = clock();
            double duration = (float)(end - start) / CLOCKS_PER_SEC;
            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() + odd_holes.size()));

           
            if (/*at_least_one_violated_odd_hole_inequality_found*/false)
            {
                //Add new CutFamilyInromation object and initilize it with already known info before finding violated cuts
                information.push_back(new CutFamilyInformation);
                information.back()->set_name_cutter("OddHole");
                information.back()->set_cut_iteration(cut_iteration);
                information.back()->set_lower_bound_before_adding_cuts(rounderToNDecimals(node.get_restricted_master_problem()->get_objective_value(), 10));
                information.back()->set_number_columns_before_adding_cuts(node.get_nb_columns_added());
                //Update nb violated cuts found in information
                information.back()->set_number_violated_cuts(odd_holes.size());
                information.back()->set_time(duration);
                information.back()->set_minimum_violation(rounderToNDecimals(minimal_violation, 3));
                information.back()->set_maximum_violation(rounderToNDecimals(maximal_violation, 3));
                node.get_restricted_master_problem()->attach(information.back());

                return at_least_one_violated_odd_hole_inequality_found;
            }
            else
                return CutGeneratorAbstract<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>::cut(node);
        }
        else
            return CutGeneratorAbstract<RestrictedMasterProblem, PricingProblem, ColumnGeneration<RestrictedMasterProblem, PricingProblem>, GRBConstr>::cut(node);
    }

};

#endif //ODDHOLE_H