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

namespace Matching 
{
    /// <summary>
    /// Implémente l'algorithme VF de Cordella servant à déterminer l'isomorphisme entre deux graphes.
    /// </summary>
    public class Vf : IGraphMatching , IIsomorphism , ISubGraphIsomorphism
    {

        List<Node> inMappingA;
        List<Node> toMappingA;
        List<Node> fromMappingA;
        List<Node> disconnectedA;


        List<Node> inMappingB;
        List<Node> toMappingB;
        List<Node> fromMappingB;
        List<Node> disconnectedB;

        //List<String[]> nodeMatching;
        Dictionary<Node, Node> nodeMatching;
        ResultIsomorphism isoResult;


        /// <summary>
        /// 
        /// </summary>
        public ResultIsomorphism IsoResult
        {
            get { return isoResult; }
            set { isoResult = value; }
        }

        /// <summary>
        /// Constructeur qui initialise toutes les listes 
        /// </summary>
        public Vf()
        {
            inMappingA = new List<Node>();
            toMappingA = new List<Node>();
            fromMappingA = new List<Node>();
            disconnectedA = new List<Node>();
            inMappingB = new List<Node>();
            toMappingB = new List<Node>();
            fromMappingB = new List<Node>();
            disconnectedB = new List<Node>();
            nodeMatching = new Dictionary<Node,Node>();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="g1"></param>
        /// <param name="g2"></param>
        /// <returns></returns>
        public Dictionary<Node, Node> GraphMatching(Graph g1, Graph g2)
        {
            if (nodeMatching.Count == 0)
            {
                isoResult = matching(g1,g2);
            }
            return nodeMatching;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="g1"></param>
        /// <param name="g2"></param>
        /// <returns></returns>
        public bool isIsomorphism(Graph g1, Graph g2)
        {
            if (isoResult == null)
            {
                isoResult = matching(g1, g2);
            }
            return isoResult.GraphIsomorphism;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="g1"></param>
        /// <param name="g2"></param>
        /// <returns></returns>
        public bool isSubGraphIsomorphism(Graph g1, Graph g2)
        {
            if (isoResult == null)
            {
                isoResult = matching(g1, g2);
            }
            return isoResult.SubGraphIsomorphism;
        }

        /// <summary>
        /// Détermine si le graphe A est isomorphe au graphe B ou si le graphe A est sous graphe du graphe B
        /// </summary>
        /// <param name="graphA">Graphe ou sous graphe</param>
        /// <param name="graphB">Graphe dans lequel on cherche l'isomorphisme</param>
        /// <returns>Résultat de l'isomorphisme</returns>
        private ResultIsomorphism matching(Graph graphA, Graph graphB)
        {
            //On enleve le cas où le graphB est plus grand que le graphA
            if (graphA.ListNodes.Count > graphB.ListNodes.Count) return new ResultIsomorphism(false, false, 0);
            else
            {
                //Insertion des noeuds dans Disconnected trié
                foreach (Node n in graphA.ListNodes) disconnectedA.Add(n);
                disconnectedA.Sort(Compare);
                disconnectedA.Reverse();

                foreach (Node n in graphB.ListNodes) disconnectedB.Add(n);
                disconnectedB.Sort(Compare);
                disconnectedB.Reverse();

                Boolean isomorph = true;

                //Noeuds courants dans l'étude de l'isomorphisme
                Node nodeA = null;
                Node nodeB = null;

                //identifiant de la liste de noeuds courante
                string listOfNode = null;

                /*L'isomorphisme est terminé lorsque inMapping contient tous les
                 * noeuds ou qu'un noeud ne correspond pas à l'isomorphisme   */
                while ((inMappingA.Count != graphA.ListNodes.Count) && isomorph)
                {
                    //On étudie la liste toMapping, puis FromMappin puis disconnected
                    if (toMappingA.Count > 0)
                    {
                        nodeA = toMappingA.ElementAt(0);
                        nodeB = toMappingB.ElementAt(0);
                        listOfNode = "to";
                    }
                    else if (fromMappingA.Count > 0)
                    {
                        nodeA = fromMappingA.ElementAt(0);
                        nodeB = fromMappingB.ElementAt(0);
                        listOfNode = "from";
                    }
                    else if (disconnectedA.Count > 0)
                    {
                        nodeA = disconnectedA.ElementAt(0);
                        nodeB = disconnectedB.ElementAt(0);
                        listOfNode = "dis";
                    }

                    //Degré d'un noeud : somme de ses edges 
                    int degreeA = nodeA.ListEdgesIn.Count + nodeA.ListEdgesOut.Count;
                    int degreeB = nodeB.ListEdgesIn.Count + nodeB.ListEdgesOut.Count;

                    //Etant donné qu'on cherche si graphA est contenu dans graphB,  si degreeA>degreeB alors pas d'isomorphisme
                    if (degreeA > degreeB) isomorph = false;

                    else if (nodeA.Label.dissimilarity(nodeB.Label) == 0)
                    {
                        if (CompareList(nodeA.ListEdgesOut, nodeB.ListEdgesOut) && CompareList(nodeA.ListEdgesIn, nodeB.ListEdgesIn))
                        {
                            inMappingA.Add(nodeA);
                            inMappingB.Add(nodeB);
                        }
                        else
                        {
                            isomorph = false;
                            //break;
                        }


                        //Suppression de NodeA et NodeB dans leur liste précédente
                        deleteInList(listOfNode, nodeA, nodeB);

                        ajoutToMapping(nodeA.ListEdgesIn, inMappingA, toMappingA, fromMappingA, disconnectedA);
                        ajoutToMapping(nodeB.ListEdgesIn, inMappingB, toMappingB, fromMappingB, disconnectedB);
                        ajoutFromMapping(nodeA.ListEdgesOut, inMappingA, toMappingA, fromMappingA, disconnectedA);
                        ajoutFromMapping(nodeB.ListEdgesOut, inMappingB, toMappingB, fromMappingB, disconnectedB);

                    }

                    //Sinon ils sont différent mais peut être que le prochain dans B peut être le bon
                    else
                    {
                        //Si on trouve un isomorphisme avec un des neuds de B suivant alors on retourne au while précédent
                        bool isomorphNext = false;
                        int indexNextNode = 1;
                        while (isomorph && !isomorphNext)
                        {

                            //On récupère le prochain noeud de la listeB
                            if (listOfNode == "to")
                            {
                                if (indexNextNode < toMappingB.Count)
                                {
                                    nodeB = toMappingB.ElementAt(indexNextNode);
                                }
                                else isomorph = false;
                            }
                            else if (listOfNode == "from")
                            {
                                if (indexNextNode < fromMappingB.Count)
                                {
                                    nodeB = fromMappingB.ElementAt(indexNextNode);
                                }
                                else isomorph = false;
                            }
                            else if (listOfNode == "dis")
                            {
                                if (indexNextNode < disconnectedB.Count)
                                {
                                    nodeB = disconnectedB.ElementAt(indexNextNode);
                                }
                                else isomorph = false;
                            }

                            //On teste le degré de ce prochain noeud
                            degreeB = nodeB.ListEdgesIn.Count + nodeB.ListEdgesOut.Count;
                            if (degreeA > degreeB) isomorph = false;

                            //Si le degré est bon alors on test celui-ci
                            else if (nodeA.Label.dissimilarity(nodeB.Label) == 0)
                            {                             
                                if (CompareList(nodeA.ListEdgesOut, nodeB.ListEdgesOut) && CompareList(nodeA.ListEdgesIn, nodeB.ListEdgesIn))
                                {
                                    inMappingA.Add(nodeA);
                                    inMappingB.Add(nodeB);
                                    isomorphNext = true;
                                }
                                else
                                {
                                    isomorph = false;
                                    //break;
                                }

                                //Suppression de NodeA et NodeB dans leur liste précédente
                                deleteInList(listOfNode, nodeA, nodeB);

                                ajoutToMapping(nodeA.ListEdgesIn, inMappingA, toMappingA, fromMappingA, disconnectedA);
                                ajoutToMapping(nodeB.ListEdgesIn, inMappingB, toMappingB, fromMappingB, disconnectedB);
                                ajoutFromMapping(nodeA.ListEdgesOut, inMappingA, toMappingA, fromMappingA, disconnectedA);
                                ajoutFromMapping(nodeB.ListEdgesOut, inMappingB, toMappingB, fromMappingB, disconnectedB);
                            }
                            indexNextNode++;
                        }
                    }
                }

                bool graphIsomorph = false;
                bool subGraphIsomorph = false;


                //Si tous les noeuds de graphA sont dans inMappingA alors forcément isomorphisme de graphe ou sous graphe
                if (inMappingA.Count == graphA.ListNodes.Count)
                {
                    subGraphIsomorph = true;

                    for (int i = 0; i < graphA.ListNodes.Count; i++)
                    {
                        //nodeMatching.Add(new String[] { inMappingA[i].Id, inMappingB[i].Id });
                        nodeMatching.Add(inMappingA[i], inMappingB[i]);
                    }

                    //Si en plus c'est idem sur B alors isomorphisme de graphe
                    if (inMappingB.Count == graphB.ListNodes.Count)
                    {
                        graphIsomorph = true;
                        subGraphIsomorph = false;
                    }
                }
                return new ResultIsomorphism(subGraphIsomorph, graphIsomorph, inMappingA.Count);
            }
        }


        /// <summary>
        /// Fonction de comparaison permettant de trier une liste de noeud en fonction de leur degré
        /// </summary>
        /// <returns>Retourne 0 si les degrés sont égaux, 1 si le noeud n1 a un degré plus élevé et -1 sinon</returns>
        private int Compare(Node n1, Node n2)
        {
            return n1.compareDegree(n2);
        }

        /// <summary>
        /// Fonction de comparaison de liste
        /// </summary>
        /// <param name="ListA"></param>
        /// <param name="ListB"></param>
        /// <returns></returns>
        private bool CompareList(List<Edge> ListA, List<Edge> ListB)
        {
            List<int> indexEdgeMatching = new List<int>();

            //ON vérifie si chaque arête de nodeA est bien égale à une unique de nodeB
            foreach (Edge e in ListA)
            {
                Boolean edgeMatching = false;

                for (int indexB = 0; indexB < ListB.Count; indexB++)
                {
                    //Une arête de B ne doit correspondre qu'une fois avec une arête de A, donc on vérifie avec contains 
                    if (e.Label.dissimilarity(ListB.ElementAt(indexB).Label) == 0 && !indexEdgeMatching.Contains(indexB))
                    {
                        indexEdgeMatching.Add(indexB);
                        edgeMatching = true;
                        break;
                    }
                }
                if (!edgeMatching)
                {
                    return false;
                }
            }
            return true;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="listAjout"></param>
        /// <param name="inM"></param>
        /// <param name="toM"></param>
        /// <param name="frM"></param>
        /// <param name="dis"></param>
        private void ajoutToMapping(List<Edge> listAjout, List<Node> inM, List<Node> toM, List<Node> frM, List<Node> dis)
        {
            //On ajoute les noeuds qui pointent vers node dans toMapping
            for (int indexNode = 0; indexNode < listAjout.Count; indexNode++)
            {
                Node toN = listAjout.ElementAt(indexNode).NodeSource;

                //Pour ajouter le noeud à toMapping il faut qu'il ne soit pas présent dans inMapping
                if (!inM.Contains(toN) && !toM.Contains(toN))
                {
                    toM.Add(toN);
                    toM.Sort(Compare);
                    toM.Reverse();
                }

                //On supprime le noeud (s'il existe) de son ancienne liste
                frM.Remove(toN);
                dis.Remove(toN);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="listAjout"></param>
        /// <param name="inM"></param>
        /// <param name="toM"></param>
        /// <param name="frM"></param>
        /// <param name="dis"></param>
        private void ajoutFromMapping(List<Edge> listAjout, List<Node> inM, List<Node> toM, List<Node> frM, List<Node> dis)
        {
            foreach (Edge edge in listAjout)
            {
                Node fromN = edge.NodeTarget;

                //Il faut que fromN n'appartienne pas à inMapping et toMapping pour l'ajouter à fromMapping
                if (!inM.Contains(fromN) && !toM.Contains(fromN) && !frM.Contains(fromN))
                {
                    frM.Add(fromN);
                    frM.Sort(Compare);
                    frM.Reverse();
                }

                //Si ce noeud était dans disconnected alors il faut le supprimer
                dis.Remove(fromN);
            }
        }

        private void deleteInList(String indexList, Node nodeA, Node nodeB)
        {
            if (indexList == "to")
            {
                toMappingA.Remove(nodeA);
                toMappingB.Remove(nodeB);
            }
            else if (indexList == "from")
            {
                fromMappingA.Remove(nodeA);
                fromMappingB.Remove(nodeB);
            }
            else if (indexList == "dis")
            {
                disconnectedA.Remove(nodeA);
                disconnectedB.Remove(nodeB);
            }
        }


        /// <summary>
        /// Fonction de test permettant d'afficher l'état des listes
        /// </summary>
        public void printLists()
        {

            System.IO.File.AppendAllText("./test.txt", "\n\n\n\n\n\ninMappingA : ");
            foreach (Node n in inMappingA)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }

            System.IO.File.AppendAllText("./test.txt", "\ninMappingB : ");
            foreach (Node n in inMappingB)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }

            System.IO.File.AppendAllText("./test.txt", "\ntoMappingA : ");
            foreach (Node n in toMappingA)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }

            System.IO.File.AppendAllText("./test.txt", "\toMappingB : ");
            foreach (Node n in toMappingB)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }

            System.IO.File.AppendAllText("./test.txt", "\nfromMappingA : ");
            foreach (Node n in fromMappingA)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }

            System.IO.File.AppendAllText("./test.txt", "\fromMappingB : ");
            foreach (Node n in fromMappingB)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }



            System.IO.File.AppendAllText("./test.txt", "\ndisconnectedA : ");
            foreach (Node n in disconnectedA)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }

            System.IO.File.AppendAllText("./test.txt", "\ndisconnectedB : ");
            foreach (Node n in disconnectedB)
            {
                System.IO.File.AppendAllText("./test.txt", n.Label.toString() + " ; ");
            }
        }


        public Dictionary<Node, Node> getNodeMatching()
        {
            throw new NotImplementedException();
        }

        public double getCost()
        {
            if (this.getIsGraphIsomorphism() || this.getIsSubGraphIsomorphism())
            {
                return 1;
            }
            return 0;
        }

        public void Compute(Graph g1, Graph g2)
        {
            isoResult = matching(g1, g2);
        }

        public bool getIsGraphIsomorphism()
        {
            //throw new NotImplementedException();
            return this.isoResult.GraphIsomorphism;
        }

        public bool getIsSubGraphIsomorphism()
        {
            return this.isoResult.SubGraphIsomorphism;
        }

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