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

namespace Matching
{
    /// <summary>
    /// Implémentation de l'algorithme de Corneil et Gotlieb permettant de savoir
    /// si un graphe est isomorphe ou sous-graphe d'un autre. 
    /// </summary>
    public class IsomorphismCandG : IGraphMatching , IIsomorphism , ISubGraphIsomorphism
    {

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


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

        /// <summary>
        /// Constructeur.
        /// </summary>
        public IsomorphismCandG()
        {
            //nodeMatching = new List<string[]>();
            nodeMatching = new Dictionary<Node, Node>();
        }

        /// <summary>
        /// g1 in g2
        /// </summary>
        /// <param name="g1"></param>
        /// <param name="g2"></param>
        /// <returns></returns>
        public Dictionary<Node,Node> GraphMatching(Graph g1, Graph g2)
        {
            if (nodeMatching.Count == 0)
            {
                SearchTree Tree = new SearchTree(g2.Id,g2.Name);
                Tree.addGraph(g2);
                isoResult = findGraph(g1,Tree);
            }
            return nodeMatching;
        }

        
        /// <summary>
        /// 
        /// </summary>
        /// <param name="g1"></param>
        /// <param name="g2"></param>
        /// <returns></returns>
        public bool isIsomorphism(Graph g1, Graph g2)
        {
            if (isoResult == null)
            {
                SearchTree Tree = new SearchTree(g2.Id, g2.Name);
                Tree.addGraph(g2);
                isoResult = findGraph(g1, Tree);
            }
            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)
            {
                SearchTree Tree = new SearchTree(g2.Id, g2.Name);
                Tree.addGraph(g2);
                isoResult = findGraph(g1, Tree);
            }
            return isoResult.SubGraphIsomorphism;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public int resultDeep()
        {
            if (isoResult == null) return -1;
            else return isoResult.Deepest;
        }

        /// <summary>
        /// Permet de savoir si graph et isomorphe au graphe contenu dans l'arbre de recherche tree ou s'il est sous-graphe de celui-ci.
        /// </summary>
        /// <param name="graph">Graphe pour lequel on veut faire le test.</param>
        /// <param name="tree">Arbre de recherche dans lequel on va chercher graph.</param>
        /// <returns>Résultat du test d'isomorphisme.</returns>
        private ResultIsomorphism findGraph(Graph graph, SearchTree tree)
        {
            //Arbre de recherche nous permettant d'utiliser SearchTree.calculateMatrixLabel et SearchTree.calculateListLabels
            SearchTree treeTemp = new SearchTree();

            //Construction de la matrice de Label
            Label[,] matrixLabel = treeTemp.calculateMatrixLabel(graph);

            //Obtention de la liste de Labels
            List<Labels> listLabels = treeTemp.calculateListLabels(matrixLabel, graph.ListNodes.Count);

            //On se positionne sur le root
            Node noeudCourant = tree.ListNodes.ElementAt(0);

            //Permet de savoir si  le noeud qu'on cherche existe ou non
            Boolean noeudExistant;

            char[] separate = new char[] { '-' };
            //Maintenant on cherche cette liste dans l'arbre de recherche
            for (int indexLabels = 0; indexLabels < listLabels.Count; indexLabels++)
            {
                noeudExistant = false;

                //Si un fils a une dissimilarité de zéro avec notre Labels alors on se positionne sur celui-ci
                foreach (Edge edge in noeudCourant.ListEdgesOut)
                {
                    //Si dissimilarité nulle alors on continue et on se positionne sur ce noeud
                    if (edge.NodeTarget.Label.dissimilarity(listLabels.ElementAt(indexLabels)) == 0)
                    {
                        noeudCourant = edge.NodeTarget;
                        String[] tabId = noeudCourant.Id.Split(separate);
                        //nodeMatching.Add(new String[] { graph.ListNodes[indexLabels].Id, tabId[1] });
                        nodeMatching.Add(graph.ListNodes[indexLabels], tree.findNode(tabId[1])); ;
                        noeudExistant = true;
                        break;
                    }
                }

                //Si sur tous les fils aucun noeud avec dissimilarité nule n'est trouvé alors on s'arête et on retourne le résultat
                if (!noeudExistant)
                {
                    //int deepest = (listLabels.ElementAt(indexLabels).ListLabels.Count * 2) - 1;
                    int deepest = indexLabels;
                    nodeMatching.Clear();
                    return new ResultIsomorphism(false, false, deepest);
                }
            }

            //Si le noeud dans l'arbre a des fils alors il y a isomorphisme de sous graphe mais pas isomorphisme de graphe complet
            return new ResultIsomorphism(noeudCourant.ListEdgesOut.Count > 0, noeudCourant.ListEdgesOut.Count == 0, graph.ListNodes.Count);
        }

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

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

        public void Compute(Graph g1, Graph g2)
        {
            SearchTree Tree = new SearchTree(g2.Id, g2.Name);
            Tree.addGraph(g2);
            isoResult = findGraph(g1, Tree);
        }

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

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

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