using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Graphs;
using Matching;


namespace Matching
{
    public unsafe class Glpk_Exact_Solve : Glpk_Solver,IGraphMatching
    {
         private string resulttext;

         public Glpk_Exact_Solve()
        {

        }
        public Glpk_Exact_Solve(Graph G1, Graph G2, string ResultText): base(G1,G2,ResultText)
        {
            ResultText+="\nExact Isomorphism\n";
            glp_set_prob_name(lp, "Exact Isomorphism");           
        }

        //override the abstract function of the abstract class Glpk_Solver
        public override void constractProblem()
        {
            //for storing the value of the constraint matrix
            List<int> iaList = new List<int>();
            List<int> jaList = new List<int>();
            List<double> arList = new List<double>();
            iaList.Add(0);
            jaList.Add(0);
            arList.Add(0);

            int rownum = 0;
            int colnum = 0;

            int numNodes1 = g1.ListNodes.Count();
            int numNodes2 = g2.ListNodes.Count();
            int numEdges1 = g1.ListEdges.Count();
            int numEdges2 = g2.ListEdges.Count();
           
            //construct the objet funcion and the contraints.
            //the objet funcion
            for (int i = 1; i <= numNodes1; i++)
            {
                for (int k = 1; k <= numNodes2; k++)
                {
                    glp_add_cols(lp, 1);
                    ++colnum;
                    glp_set_col_kind(lp, colnum, GLP_BV);
                    glp_set_col_name(lp, colnum, ("x_" + g1.ListNodes[i - 1].Id + "," + g2.ListNodes[k - 1].Id));
                    glp_set_obj_coef(lp, colnum, g1.ListNodes[i - 1].Label.dissimilarity(g2.ListNodes[k - 1].Label));

                }
            }

            for (int ij = 1; ij <= numEdges1; ij++)
                for (int kl = 1; kl <= numEdges2; kl++)
                {
                    glp_add_cols(lp, 1);
                    glp_set_col_name(lp, ++colnum, ("y_" + g1.ListEdges[ij - 1].Id + "," + g2.ListEdges[kl - 1].Id));
                    glp_set_col_kind(lp, colnum, GLP_BV);
                    glp_set_obj_coef(lp, colnum, g1.ListEdges[ij - 1].Label.dissimilarity(g2.ListEdges[kl - 1].Label));

                }

            glp_create_index(lp);


            // contraint: equation 3 ( Every vertex of g1 must be matched to a unique vertex of g2)
            for (int i = 1; i <= numNodes1; i++)
            {
                glp_add_rows(lp, 1);
                glp_set_row_name(lp, ++rownum, "equation3_" + rownum);
                glp_set_row_bnds(lp, rownum, GLP_FX, 1, 1);
                for (int k = 1; k <= numNodes2; k++)
                {
                    iaList.Add(rownum);
                    jaList.Add((i - 1) * numNodes2 + k);
                    arList.Add(1);
                }


            }


            // equation 4 ( Every edge of g1 must be matched to a unique edge of g2)
            for (int ij = 1; ij <= numEdges1; ij++)
            {
                glp_add_rows(lp, 1);
                glp_set_row_name(lp, ++rownum, "equation4_" + rownum);
                glp_set_row_bnds(lp, rownum, GLP_FX, 1, 1);
                for (int kl = 1; kl <= numEdges2; kl++)
                {

                    iaList.Add(rownum);
                    jaList.Add(numNodes1 * numNodes2 + (ij - 1) * numEdges2 + kl);
                    arList.Add(1);
                }
            }

            //equation 5 (Every vertex of g2 must be matched to at most an edge of g1 )
            for (int k = 1; k <= numNodes2; k++)
            {
                glp_add_rows(lp, 1);
                glp_set_row_name(lp, ++rownum, "equation5_" + rownum);
                glp_set_row_bnds(lp, rownum, GLP_DB, 0, 1);
                for (int i = 1; i <= numNodes1; i++)
                {
                    iaList.Add(rownum);
                    jaList.Add(numNodes2 * (i - 1) + k);
                    arList.Add(1);
                }
            }

            //equation 6 (If two vertices are matched together, 
            //an edge originating one of these two vertices must be matched with an edge originating the other vertex)
            for (int k = 1; k <= numNodes2; k++)
                for (int ij = 1; ij <= numEdges1; ij++)
                {
                    glp_add_rows(lp, 1);
                    rownum++;
                    glp_set_row_bnds(lp, rownum, GLP_FX, 0, 0);
                    glp_set_row_name(lp, rownum, "equation6_" + rownum);


                    string source = g1.ListEdges[ij - 1].NodeSource.Id;
                    string nameVar = "x_" + source + "," + g2.ListNodes[k - 1].Id;
                    int colInd = glp_find_col(lp, nameVar);
                    if (colInd == 0)
                        throw new InvalidProgramException();

                    iaList.Add(rownum);
                    jaList.Add(colInd);
                    arList.Add(1);

                    string name1 = g1.ListEdges[ij - 1].Id;
                    foreach (Edge e in g2.ListNodes[k - 1].ListEdgesOut)
                    {
                        string name2 = e.Id;
                        nameVar = "y_" + name1 + "," + name2;
                        colInd = glp_find_col(lp, nameVar);
                        if (colInd == 0)
                            throw new InvalidProgramException();

                        iaList.Add(rownum);
                        jaList.Add(colInd);
                        arList.Add(-1);
                    }
                }

            //equation 7 (If two vertices are matched together, 
            //an edge targeting one of these two vertices must be matched with an edge targeting the other vertex)
            for (int l = 1; l <= numNodes2; l++)
                for (int ij = 1; ij <= numEdges1; ij++)
                {
                    glp_add_rows(lp, 1);
                    glp_set_row_name(lp, ++rownum, "equation7_" + rownum);
                    glp_set_row_bnds(lp, rownum, GLP_FX, 0, 0);

                    string target = g1.ListEdges[ij - 1].NodeTarget.Id;
                    string nameVar = "x_" + target + "," + g2.ListNodes[l - 1].Id;
                    int colInd = glp_find_col(lp, nameVar);
                    if (colInd == 0)
                        throw new InvalidProgramException();

                    iaList.Add(rownum);
                    jaList.Add(colInd);
                    arList.Add(1);

                    string name1 = g1.ListEdges[ij - 1].Id;
                    foreach (Edge e in g2.ListNodes[l - 1].ListEdgesIn)
                    {
                        string name2 = e.Id;
                        nameVar = "y_" + name1 + "," + name2;
                        colInd = glp_find_col(lp, nameVar);
                        if (colInd == 0)
                            throw new InvalidProgramException();

                        iaList.Add(rownum);
                        jaList.Add(colInd);
                        arList.Add(-1);
                    }

                }
            //declare the contraints matrix
            ConstraintMatrix CM = new ConstraintMatrix();
            int numEle = arList.Count() - 1;
            CM.ia = iaList.ToArray();
            CM.ja = jaList.ToArray();
            CM.ar = arList.ToArray();
            glp_load_matrix(lp, numEle, CM.ia, CM.ja, CM.ar);

        }

        public Dictionary<Node, Node> getNodeMatching()
        {
            return this.NodeMatching;
        }

        public double getCost()
        {
            return this.Totalcost;
        }

        public void Compute(Graph g1, Graph g2)
        {
            
            this.init(g1, g2, this.resulttext);
            glp_set_prob_name(lp, "Exact Isomorphism");
            this.constractProblem();
            this.solve_problem();
            List<string[]> nodes = new List<string[]>();
            this.print_sol(nodes, this.resulttext);
        }

        public bool isOptimal()
        {
            return true;
        }
    }
}

