//========================================================================
// Copyright(C): RFAI France
//
// CLR Version : 4.0.30319.18052
// NameSpace : Matching
// FileName : ResearchGraph.cs
//
// Created by : JC (jiangchar@gamil.com) at 1/1/2014 10:04:19 PM
//
//========================================================================

#region Using directives

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Graphs;
using System.Collections;
using System.IO;
using Accord.MachineLearning;
using System.Xml.Linq;
using MatrixLibrary;

#endregion

namespace Matching
{
    public class ResearchGraph
    {
        /***************************************************************/
        /*************************Attributs*****************************/
        /***************************************************************/
        #region Attributs

        /// <summary>
        /// la méthode de plus court chemin pour calculer la distance entre graphe
        /// </summary>
        public const int PCC = 1;
        /// <summary>
        /// la méthode de matrice d'adjacent chemin pour calculer la distance entre graphe
        /// </summary>
        public const int MATRIX = 0;
        /// <summary>
        /// la méthode de beam research pour calculer la distance entre graphe
        /// </summary>
        public const int BEAMSEARCH = -1;

        //La signature pour le graphe de recherche
        FMGESignature signature;
        //Le graphe de recherche
        Graph QueryGraph;
        //les noms et les répértoires du graphes lu dans le fichier ClusterInfo.xml
        Dictionary<String, String> nameAndDirectory;
        //Une liste de résultat(nom + score dans l'objet ResultMatching)
        List<ResultMatching> resultMatchingSet;

        #endregion

        /***************************************************************/
        /*************************Accesseurs****************************/
        /***************************************************************/

        #region Accesseurs

        public List<ResultMatching> ResultMatchingSet
        {
            get { return resultMatchingSet; }
            set { resultMatchingSet = value; }
        }

        #endregion

        /***************************************************************/
        /************************Constructeurs**************************/
        /***************************************************************/

        #region Constructeurs

        public ResearchGraph()
        {
            QueryGraph = new Graph();
            signature = new FMGESignature();
        }

        #endregion

        /***************************************************************/
        /*********************Méthodes publics**************************/
        /***************************************************************/

        #region Méthodes publics

        /// <summary>
        /// La méthode principale de recherche de graphe 
        /// </summary>
        /// <param name="DirGraph">graphe de recherche</param>
        /// <param name="DirClusterXML">ClusterInfo.XML</param>
        /// <param name="DirCompleteXML">Indexation.XML</param>
        /// <param name="DirBinsData">La répértoire du fichier bins</param>
        /// <param name="levelGraph">S'il contient le graph level information</param>
        /// <param name="levelStructure">S'il contient le structure level information</param>
        /// <param name="levelComponent">S'il contient le elementary level information</param>
        /// <param name="Knn_k">Le nombre de K plus proche voisin</param>
        /// <param name="Knn_nbClass">Le nombre de classe de clustering</param>
        /// <param name="shortestPathMode">S'il utilise la méthode de plus court chemin, le beam research et la matrice d'adjacente</param>
        public void Run(string DirGraph, string DirClusterXML, string DirCompleteXML, string DirBinsData,
            bool levelGraph = true, bool levelStructure = true, bool levelComponent = true,
            int Knn_k = 1, int Knn_nbClass = 3, int shortestPathMode = ResearchGraph.MATRIX)
        {
            //lire les infos de clustering dans un objet de clusterinfomation.
            ClusterInformation clusterInfo = new ClusterInformation();

            //mettre la graphe de recherche dans une signature.
            FMGESignature FGMRunRes = new FMGESignature();
            XElement xmlDoc;

            //pour un graphe de recherche, on compte, sur chaque groupe, le nombre de clique.
            //int:numero groupe
            //int:nombre de fois
            Dictionary<int, int> AppearTimes = new Dictionary<int, int>();

            //pour chaque clique d'un graphe de recherche, le numero de groupe et le nom de clique
            //int: groupe de clique
            //string:nom de graphe+nom de clique
            List<KeyValuePair<int, string>> QueryLabels = new List<KeyValuePair<int, string>>();

            //les infos de la fichier ClusterInfo.xml en forme InvertedIndexTable[nom_graphe, numero_groupe]=liste de tout les arcs.
            //KeyValuePair<String, int>:nom_graphe,numero_groupe
            //List<String>:liste d'arc
            Dictionary<KeyValuePair<String, int>, List<String>> InvertedIndexTable =
                new Dictionary<KeyValuePair<String, int>, List<String>>();

            //Pour une groupe, tout les graphes dans lequels il existe au moins une clique dans ce groupe.
            //int:numero de groupe, List<String>: liste de nom de graphes
            Dictionary<int, List<String>> ResultSetXML = new Dictionary<int, List<String>>();

            //resultat de matching
            resultMatchingSet = new List<ResultMatching>();

            try
            {
                clusterInfo.ReadFromXML(DirClusterXML);
                if(clusterInfo.ListCenter.Count != Knn_nbClass)
                    throw new Exception("The class number is not match, please" +
                " do the index again with the new class number. \n");
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("Fail to read cluster XML. \n" + e.Message);
            }
            try
            {
                QueryGraph.loadGXL(DirGraph);
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("fail to read the graph file. \n", e);
            }
            try
            {
                FGMRunRes.ExtractClique(QueryGraph, Path.GetFileName(DirGraph), false);
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("fail to extract cliques", e);
            }
            try
            {
                //il faut utiliser des fichiers bins existants
                FGMRunRes.FillTable(levelGraph, levelStructure, levelComponent, FMGESignature.LoadBins, DirBinsData);
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("fail to get FGME vectors", e);
            }

            //---------------------------------------------------------------------------------------
            try
            {
                QueryLabels = Classification(Knn_k, Knn_nbClass, clusterInfo.ListCenter,
                    clusterInfo.ListClusterLabel, FGMRunRes.ListVectorFGME);
               // testClassification(1, 3, clusterInfo.ListCenter,
                 //   clusterInfo.ListClusterLabel, FGMRunRes.ListVectorFGME, QueryLabels);
                //trouver les labels differents et il existe combien de fois
                foreach (KeyValuePair<int, String> kvp in QueryLabels)
                {
                    if (AppearTimes.ContainsKey(kvp.Key))
                        AppearTimes[kvp.Key] += 1;
                    else
                        AppearTimes.Add(kvp.Key, 1);
                }
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("fail to make the classification", e);
            }
            //---------------------------------------------------------------------------------------
            try
            {
                xmlDoc = XElement.Load(DirClusterXML + "\\ClusterInfo.xml");
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("fail to load the complete clustering file", e);
            }
            //---------------------------------------------------------------------------------------

            //pour chaque label de chaque clique du graphe de recherche, on tourve une liste de graphs qui
            //ont des cliques qui sont dans le meme groupe avec des cliques du graphe de recherche
            foreach (KeyValuePair<int,int> i in AppearTimes)
            {
                var Result = (from e in xmlDoc.Elements("Cluster_label")
                             where e.Attribute("Label").Value == i.Key.ToString()
                             select e.Element("List_cliques")).SingleOrDefault().Value;
                //ResultSet contient tout les cliques dans les memes groupes avec les cliques dans le graphe de recherche. 
                ResultSetXML.Add(i.Key, Result.ToString().Split(' ').ToList());
            }
            if (ResultSetXML.Count == 0)
                return;
            //------------------------------------------organiser les infos------------------------------------

            // initialisation InvertedIndexTable, lire les infos de la tableau ResultSetXML et les remplir dans InvertedIndexTable
            foreach (int i in ResultSetXML.Keys)
            {
                GetClusterTable(InvertedIndexTable, ResultSetXML[i], i);
            }
            //retirer $ dans le nom
            List<List<String>> names = FilterName(ResultSetXML);

            //calcule les graphs communs
            List<String> Intersection = new List<String>(names[0].Distinct());

            Intersection = new List<String>(Intersection.Distinct());

            foreach (List<String> listString in names)
            {
                Intersection =  new List<String>(Intersection.Intersect(listString.Distinct()));
            }
            //******************************Resultat**************************************************************

            Intersection = IntersectGraphsFilter(Intersection, InvertedIndexTable, AppearTimes);

            //Intersection contient tout les graphs dans lequels chaque clique a le meme label que des cliques dans le
            //graphe de recherche en respectant le nombre de fois d'existance.


            //---------------------------------calcule score-------------------------------------------
            //interesction:tout les graphes contient tout les labels
            //DirCompleteXML:la répértoire du fichier indexation.xml
            //InvertedIndexTable: tableau d'indexation
            //QueryLabels:le resultat de classification du graphe de recherche

            resultMatchingSet = GetResult(Intersection, DirCompleteXML, InvertedIndexTable, QueryLabels, AppearTimes, shortestPathMode);

            //mettre en ordre par le score
            resultMatchingSet = resultMatchingSet.OrderBy(s => s.Score).ToList();
            
        }

        //-------------------------------fin de Run----------------------------------------------------------------

        /// <summary>
        /// fonction de classification
        /// </summary>
        /// <param name="nbPPV">nb de plus proche voisin</param>
        /// <param name="nbClass">nb de classe de K means</param>
        /// <param name="vectorsAfterCluster">les vecteurs qu'on a utilisé pour clustering</param>
        /// <param name="labels">les numero de label apres clustering</param>
        /// <param name="vectorsWaitClassification">un vecteur pour être classifier</param>
        /// <returns>résultat avec le noméro de groupe et le nom de vecteur</returns>
        public List<KeyValuePair<int, string>> Classification(int nbPPV, int nbClass,
            List<VectorFMGE> vectorsAfterCluster, List<int> labels,
            List<VectorFMGE> vectorsWaitClassification)
        {
            //---------------------------------------------------------------------------------------
            //--------------------------------Convertir pour classification---------------------------
            //---------------------------------------------------------------------------------------
            List<double[]> LisCluInd_WaitForConvert = new List<double[]>();

            foreach (VectorFMGE vector in vectorsAfterCluster)
            {
                LisCluInd_WaitForConvert.Add(vector.GetMatrix());
            }
            List<int> LisRunRes_WaitForConvert = labels;
            //recharger les labels
            int[] IntClaRes_outputs = LisRunRes_WaitForConvert.ToArray<int>();
            //recharger les vecteurs
            double[][] LisCluInd_WaitForclassification = LisCluInd_WaitForConvert.ToArray();
            //---------------------------------------------------------------------------------------
            //----------------------------------------------classification---------------------------
            //---------------------------------------------------------------------------------------
            //donner le nombre de ppv, nombre de classe existante, vecteurs existants, et les labels qu'on calcule par clustering
            KNearestNeighbors knn = new KNearestNeighbors(nbPPV, nbClass,
                LisCluInd_WaitForclassification, IntClaRes_outputs);
            //on aura un résultat(numéro de classe et nom de clique correspondant)
            List<KeyValuePair<int, string>> LisClaRes_result = new List<KeyValuePair<int, string>>();
            foreach (VectorFMGE v in vectorsWaitClassification)
            {
                int answer = knn.Compute(v.GetMatrix());
                LisClaRes_result.Add(new KeyValuePair<int, string>(answer, v.Name));
            }
            return LisClaRes_result;
        }

        //-------------------------------fin de Classification----------------------------------------------------------------

        /// <summary>
        /// créer un fichier de test de classification
        /// </summary>
        /// <param name="nbPPV">nb de plus proche voisin</param>
        /// <param name="nbClass">nb de classe de K means</param>
        /// <param name="vectorsAfterCluster">les vecteurs qu'on a utilisé pour clustering</param>
        /// <param name="labels">les numero de label apres clustering</param>
        /// <param name="vectorsWaitClassification">un vecteur pour être classifier</param>
        /// <param name="groupe"></param>
        public void testClassification(int nbPPV, int nbClass, List<VectorFMGE> vectorsAfterCluster, List<int> labels,
            List<VectorFMGE> vectorsAfterClassification, List<KeyValuePair<int, string>> groupe)
        {
            System.IO.StreamWriter writer = new System.IO.StreamWriter(@"testClassification.txt");
            String outer = "**********************************************************************************-- " +
                "\n " + "dimension" + vectorsAfterClassification[0].FSMFV.Count + "---nombre de plus proche voisin: " +
                nbPPV + "  nombre cluster: " + nbClass + 
                "--- \n ********************************************************************************** ";
            writer.WriteLine(outer);
            outer = "";
            foreach (VectorFMGE v in vectorsAfterCluster)
            {
                outer += "centre vecteur <" + v.GetString() + "> \n";
            }
            writer.WriteLine(outer);
            outer = "";
            for (int i = 0; i<vectorsAfterClassification.Count; i++)
            {
                outer = "vecteur de classification <" + vectorsAfterClassification[i].GetString() +
                    "> groupe attributé (" + groupe[i].Key +") Clique id ( " + groupe[i].Value + ") (dimension" +
                    vectorsAfterClassification[i].FSMFV.Count + ") \n";
                writer.WriteLine(outer);
            }
            writer.Close();
        }

        //-------------------------------fin de testClassification----------------------------------------------------------------

        #endregion

        /***************************************************************/
        /*********************Méthodes privées**************************/
        /***************************************************************/

        #region Méthodes privées

        /// <summary>
        /// Assurer les arcs dans graphe de rechercher sont tous existé au moins une fois dans le graphe courrant
        /// </summary>
        /// <param name="Intersection">une liste de graphe</param>
        /// <param name="clusterTable">inverted index tableau</param>
        /// <param name="appearTimes">les labels et pour chaque label, le nombre de fois qu'il existe</param>
        /// <returns>une liste de graphe qui satisfait ce condition</returns>
        private List<String> IntersectGraphsFilter(List<String> Intersection, 
            Dictionary<KeyValuePair<String, int>, List<String>> clusterTable, Dictionary<int, int> appearTimes)
        {
            List<String> Res = new List<String>();
            foreach (String name in Intersection)
            {
                bool insert = true;
                foreach (KeyValuePair<int, int> kvp in appearTimes)
                {
                    KeyValuePair<String, int> cell = new KeyValuePair<string,int>(name, kvp.Key);
                    if (clusterTable[cell].Count < kvp.Value)
                        insert = false;
                }
                if (insert)
                    Res.Add(name);
            }
            return Res;
        }

        //-------------------------------fin de IntersectGraphsFilter----------------------------------------------------------------

        /// <summary>
        /// Retirer le nom d'arc dans le nom entier.
        /// </summary>
        /// <param name="listName">liste de nom entier</param>
        /// <returns>liste de nom traité</returns>
        private List<List<String>> FilterName(Dictionary<int, List<String>> listName)
        {
            List<List<String>> ResListStr = new List<List<String>>();
            foreach (KeyValuePair<int, List<String>> listStr in listName)
            {
                List<String> ResStr = new List<String>();
                foreach(String str in listStr.Value)
                {
                    if (str.IndexOf('$') == -1)
                        throw new Exception("File name malformed");
                   ResStr.Add(str.Substring(0, str.IndexOf('$')));
                }
                ResListStr.Add(ResStr);
            }
            return ResListStr;
        }

        //-------------------------------fin de FilterName----------------------------------------------------------------

        /// <summary>
        /// Calculer un score pour chaque graphe résultat
        /// </summary>
        /// <param name="intersectionsIn">les noms de graphe</param>
        /// <param name="directory">la répértoire de fichier indexation</param>
        /// <param name="InvertedIndexTableIn">l'inverted tableau</param>
        /// <param name="QueryLabels">les labels et les noms d'arc pour le graphe de recherche</param>
        /// <param name="appearsTimes">les labels et le nombre de fois qu'il existe</param>
        /// <param name="ShortestPathMode">si on utilise la méthode Shortest path ou le beam research ou la matrice d'adjacent</param>
        /// <returns>une list de ResultMatching avec un score</returns>
        private List<ResultMatching> GetResult(List<String> intersectionsIn, String directory,
    Dictionary<KeyValuePair<String, int>, List<String>> InvertedIndexTableIn, List<KeyValuePair<int, string>> QueryLabels,
            Dictionary<int, int> appearsTimes, int ShortestPathMode)
        {
            //-----------------------chercher la répértoire d'un graphe---------------------------------
            nameAndDirectory = new Dictionary<string, string>();

            List<ResultMatching> resultMatchingSet = new List<ResultMatching>();

            XElement xmlDoc;
            try
            {
                xmlDoc = XElement.Load(directory + "\\indexation.xml");
            }
            catch (Exception e)
            {
                Console.Write(e.Message);
                throw new Exception("cannot load graph file", e);
            }
            foreach (String str in intersectionsIn)
            {
                List<String> result = (from e in xmlDoc.Elements("Clique")
                                       where Path.GetFileName(e.Attribute("Directory").Value).Equals(str)
                                       select e.Attribute("Directory").Value.ToString()).ToList();

                if (result.Distinct().Count() != 1) throw new Exception("error");

                nameAndDirectory.Add(str, result[0].ToString());
            }
            //---------------------------calcul la matrice-------------------------------------------
            foreach (KeyValuePair<String, String> kvp in nameAndDirectory)
            {
                ResultMatching resultMatching = new ResultMatching();

                Graph graph = new Graph(kvp.Key, "", false);
                try
                {
                    graph.loadGXL(kvp.Value);
                }
                catch (Exception e)
                {
                    Console.Write(e.Message);
                    throw new Exception("fail to load graph", e);
                }
                resultMatching.Graph = graph;
                if (ShortestPathMode == MATRIX)
                    resultMatching.Score = ComputeScore(kvp.Key, graph, appearsTimes, InvertedIndexTableIn);
                else if (ShortestPathMode == BEAMSEARCH)
                {
                    BeamSearchGraphEditDistanceAC be = new BeamSearchGraphEditDistanceAC(3);

                    resultMatching.Score = be.GraphDistance(QueryGraph, graph);
                }
                else
                    resultMatching.Score = ComputeScoreSPF(kvp.Key, graph, QueryLabels, InvertedIndexTableIn);

                resultMatchingSet.Add(resultMatching);
            }
            return resultMatchingSet;
        }

        //-------------------------------fin de GetResult----------------------------------------------------------------

        /// <summary>
        /// Pour un graphe, on calcule un score utilisant la méthode matrice d'adjacent
        /// </summary>
        /// <param name="graphId">id de graphe dans la base de graphe</param>
        /// <param name="graphInBD">graphe dans la base de graphe</param>
        /// <param name="appearsTimes">les labels et le nombre de fois qu'il existe</param>
        /// <param name="InvertedIndexTableIn">l'inverted tableau</param>
        /// <returns>le score d'un graphe dans la liste de résultat</returns>
        private double ComputeScore(String graphId, Graph graphInBD, Dictionary<int, int> appearsTimes,
            Dictionary<KeyValuePair<String, int>, List<String>> InvertedIndexTableIn)
        {
            double score = 0.0;

            int edgeNb = graphInBD.ListEdges.Count;

            Matrix matrix = graphInBD.calculateAdjacencyMatrix();

            foreach (KeyValuePair<int, int> kvpLabel in appearsTimes)
            {
                KeyValuePair<String, int> cell = new KeyValuePair<string, int>(graphId, kvpLabel.Key);
                //chercher tous les arcs qui ont le meme label que ce arc dans le graphe de recherche.
                List<String> Edges = InvertedIndexTableIn[cell];
                //chercher l'arc courant dans un graphe
                foreach (String edgeId in Edges)
                {
                    Edge edge;
                    try
                    {
                        edge = graphInBD.findEdge(edgeId);
                    }
                    catch (Exception e)
                    {
                        Console.Write(e.Message);
                        throw new Exception("cannot find edge", e);
                    }
                    matrix[graphInBD.ListNodes.IndexOf(edge.NodeSource), graphInBD.ListNodes.IndexOf(edge.NodeTarget)] += 1;
                    if (graphInBD.ListNodes.IndexOf(edge.NodeSource) - 1 >= 0)
                        matrix[graphInBD.ListNodes.IndexOf(edge.NodeSource) - 1, graphInBD.ListNodes.IndexOf(edge.NodeTarget)] += 1;
                    if (graphInBD.ListNodes.IndexOf(edge.NodeTarget) - 1 >= 0)
                        matrix[graphInBD.ListNodes.IndexOf(edge.NodeSource), graphInBD.ListNodes.IndexOf(edge.NodeTarget) - 1] += 1;
                    if (graphInBD.ListNodes.IndexOf(edge.NodeSource) + 1 < matrix.NoCols)
                        matrix[graphInBD.ListNodes.IndexOf(edge.NodeSource) + 1, graphInBD.ListNodes.IndexOf(edge.NodeTarget)] += 1;
                    if (graphInBD.ListNodes.IndexOf(edge.NodeTarget) + 1 < matrix.NoRows)
                        matrix[graphInBD.ListNodes.IndexOf(edge.NodeSource), graphInBD.ListNodes.IndexOf(edge.NodeTarget) + 1] += 1;
                }
            }
            //------------------------calcule soure---------------------------------------------------------------------------
            for (int i = 0; i < matrix.NoRows; i++)
            {
                for (int j = 0; j < matrix.NoCols; j++)
                {
                    //on compte les valeurs egale le nombre d'arc mulitplie 2 moins 1.
                    if (2 == matrix[i, j])
                        score += 1;
                    //if (matrix[i, j] > score) score = matrix[i, j];
                }
            }
            return Math.Abs(edgeNb * 3 - 2 - score);
        }

        //-------------------------------fin de GetScore----------------------------------------------------------------

        /// <summary>
        /// Pour un graphe, on calcule un score utilisant la méthode le plus court chemin
        /// </summary>
        /// <param name="fileNameOfGraphInBD">id de graphe dans la base de graphe</param>
        /// <param name="graphInBD">graphe dans la base de graphe</param>
        /// <param name="researchGraphWithLabel">les labels et les noms d'arc dans le graphe de recherche</param>
        /// <param name="invertedIndexTableIn">l'inverted tableau</param>
        /// <returns>le score d'un graphe dans la liste de résultat</returns>
        private int ComputeScoreSPF(String fileNameOfGraphInBD, Graph graphInBD,
            List<KeyValuePair<int, string>> researchGraphWithLabel,
            Dictionary<KeyValuePair<String, int>, List<String>> invertedIndexTableIn)
        {
            List<SPF_Node> firstLayer = new List<SPF_Node>();
            List<SPF_Node> secondLayer = new List<SPF_Node>();
            bool found;

            //construire les deux couches
            foreach (KeyValuePair<int, string> kvp in researchGraphWithLabel)
            {
                //pour les noms d'arcs, ils sont comme graph.gxl$nom_arc. 
                //il faut le retraiter avant de l'utiliser.
                SPF_Node firstLayer_NewNode;
                try
                {
                    firstLayer_NewNode =
                        new SPF_Node(kvp.Value.Substring(kvp.Value.IndexOf('$') + 1), kvp.Key.ToString());
                }
                catch (Exception ex)
                {
                    throw new Exception("node name not correct" + ex);
                }
                firstLayer.Add(firstLayer_NewNode);
            }
            //cherche les labels differents et puis pour chaque label, on le cherche dans le graphInBD
            List<KeyValuePair<int, string>> distinctResearchGraphWithLabel =
                researchGraphWithLabel.Distinct(new researchGraphWithLabel_Comparer()).ToList();
            foreach (Edge e in graphInBD.ListEdges)
            {
                found = false;
                foreach (KeyValuePair<int, String> kvp in researchGraphWithLabel)
                {
                    //si pour un arc e, il a le meme label qui est dans le graphe de recherche.
                    if (invertedIndexTableIn[new KeyValuePair<String, int>(fileNameOfGraphInBD,
                        Convert.ToInt32(kvp.Key))].Contains(e.Id))
                    {
                        SPF_Node secondLayer_NewNode = new SPF_Node(e.Id, kvp.Key.ToString());
                        secondLayer.Add(secondLayer_NewNode);
                        found = true;
                        break;
                    }
                }
                // si un arc de graphe graphInBD avec aucun label
                if (found == false)
                {
                    SPF_Node secondLayer_NewNode = new SPF_Node(e.Id, "-1");
                    secondLayer.Add(secondLayer_NewNode);
                }
            }
            //construire les arcs du graphe
            foreach (SPF_Node spf_Node_1 in firstLayer)
            {
                foreach (SPF_Node spf_Node_2 in secondLayer)
                {
                    //arc entre couche 1 et couche 2
                    if (spf_Node_1.Label.Equals(spf_Node_2.Label))
                    {
                        spf_Node_1.NodesTarget.Add(spf_Node_2);
                    }
                }
            }

            foreach (SPF_Node spf_Node_2 in secondLayer)
            {
                Edge edge;
                //arc entre les noeuds de couche 2
                edge = graphInBD.findEdge(spf_Node_2.Id);
                //pour les arcs connectés avec le noeud d'entrée
                //pour les graphes non orienté, les arcs sont dans ListEdgesOut
                foreach (Edge e in edge.NodeSource.ListEdgesOut)
                {
                    string id = e.Id;
                    //chercher l'arc e dans secondLayer
                    SPF_Node nodeTarget = secondLayer.Find(
                        delegate(SPF_Node s)
                        {
                            return s.Id == id;
                        }
                        );
                    if (!spf_Node_2.NodesTarget.Contains(nodeTarget) && spf_Node_2.Id != nodeTarget.Id)
                        spf_Node_2.NodesTarget.Add(nodeTarget);
                }
                //pour les arcs connectés avec le noeud de sortie
                //pour les graphes non orienté, les arcs sont dans ListEdgesOut
                foreach (Edge e in edge.NodeTarget.ListEdgesOut)
                {
                    string id = e.Id;
                    //chercher l'arc e dans secondLayer
                    SPF_Node nodeTarget = secondLayer.Find(
                        delegate(SPF_Node s)
                        {
                            return s.Id == id;
                        }
                        );
                    if (!spf_Node_2.NodesTarget.Contains(nodeTarget) && spf_Node_2.Id != nodeTarget.Id)
                        spf_Node_2.NodesTarget.Add(nodeTarget);
                }
            }
            //-----------------------------calculer le plus court chemin-----------------------------

            //le tableau pour calculer le plus court chemin pour secondLayer
            int[,] table = new int[secondLayer.Count, secondLayer.Count];

            for (int i = 0; i < secondLayer.Count; i++)
            {
                for (int j = 0; j < secondLayer.Count; j++)
                {
                    if (secondLayer[i].NodesTarget.Contains(secondLayer[j]))
                        table[i, j] = 1;
                    else
                        table[i, j] = int.MaxValue;
                }
            }

            //calcule le plus court chemin pour secondLayer utilisant algo Floyd
            table = FloydWarshall(table);

            int[] values = new int[firstLayer.Count];
            int miniDistance = int.MaxValue;
            values[0] = 0;

            Parallel.For(0, firstLayer.Count - 1, i =>
            //for (int i = 0; i < firstLayer.Count; i++)
            {
                Parallel.For(i + 1, firstLayer.Count - 1, j =>
                //for (int j = i + 1; j < firstLayer.Count; j++)
                {
                    miniDistance = int.MaxValue;
                    Parallel.ForEach(firstLayer[i].NodesTarget, node1 =>
                    //foreach (SPF_Node node1 in firstLayer[i].NodesTarget)
                    {
                        Parallel.ForEach(firstLayer[j].NodesTarget, node2 =>
                        //foreach (SPF_Node node2 in firstLayer[j].NodesTarget)
                        {
                            int begin = secondLayer.FindIndex(item => item.Id == node1.Id);
                            int end = secondLayer.FindIndex(item => item.Id == node2.Id);
                            if (begin != end && table[begin, end] < miniDistance) miniDistance =
                                values[i] + table[begin, end];
                        });
                    });
                    values[j] = miniDistance;
                });
            });
            return Math.Abs(graphInBD.ListEdges.Count - values[firstLayer.Count - 1]);
        }
        //-------------------------------fin de ComputeScoreSPF----------------------------------------------------------------

        /// <summary>
        /// l'algorithme de Floyd pour calculer le plus court chemin
        /// </summary>
        /// <param name="table">tableau de poids d'un graphe</param>
        /// <returns>tableau de poids d'un graphe, chaque poids est le plus court distance entre i et j</returns>
        private int[,] FloydWarshall(int[,] table)
        {
            for (int k = 0; k < table.GetLength(0); k++)
            {
                for (int i = 0; i < table.GetLength(0); i++)
                {
                    for (int j = 0; j < table.GetLength(0); j++)
                    {
                        if(table[i, k] != int.MaxValue &&
                            table[k, j] != int.MaxValue &&
                            table[i, j] > table[i, k] + table[k, j] && i != j)
                            table[i, j] = table[i, k] + table[k, j];
                    }
                }
            }
            return table;
        }

        //-------------------------------fin de FloydWarshall----------------------------------------------------------------

        /// <summary>
        /// Construire la inverted index tableau
        /// </summary>
        /// <param name="clusterTable">outputs</param>
        /// <param name="namePlusEdge">les nomGraph$nomArc dans un groupe</param>
        /// <param name="group">numéro de groupe</param>
        private void GetClusterTable(Dictionary<KeyValuePair<String, int>, List<String>> clusterTable,
            List<String> namePlusEdge, int group)
        {
            foreach (String str in namePlusEdge)
            {
                //si dans la liste, il n'existe pas de $, afficher un erreur
                if (str.IndexOf('$') == -1)
                    throw new Exception("File name Malformed");
                String nameGraph = str.Substring(0, str.IndexOf('$'));
                String nameEdge = str.Substring(str.IndexOf('$') + 1);
                //verifier si le couple [nameGraph, group] existe
                KeyValuePair<String, int> cell = new KeyValuePair<String, int>(nameGraph, group);
                if (clusterTable.ContainsKey(cell))
                {
                    //declarer une reference de la liste d'arc
                    List<String> edges = clusterTable[cell];
                    edges.Add(nameEdge);
                }
                else
                {
                    List<String> edges = new List<String>();
                    edges.Add(nameEdge);
                    clusterTable.Add(cell, edges);
                }
            }
        }

        //-------------------------------fin de GetClusterTable----------------------------------------------------------------

        #endregion
    }

}

public class SPF_Node
{
    private string id;
    private string label;
    List<SPF_Node> nodesTarget;

    public String Id
    {
        get { return id; }
        set { id = value; }
    }
    public List<SPF_Node> NodesTarget
    {
        get { return nodesTarget; }
        set { nodesTarget = value; }
    }
    public String Label
    {
        set { label = value; }
        get { return label; }
    }
    public SPF_Node()
    {
        id = "";
        label = "";
        nodesTarget = new List<SPF_Node>();
    }
    public SPF_Node(String id, String label)
    {
        this.id = id;
        this.label = label;
        nodesTarget = new List<SPF_Node>();
    }
    public void addTarget(SPF_Node target)
    {
        nodesTarget.Add(target);
    }
    
}

public class researchGraphWithLabel_Comparer : IEqualityComparer<KeyValuePair<int, string>>
{
    public bool Equals(KeyValuePair<int, string> kvp1, KeyValuePair<int, string> kvp2)
    {
        return kvp1.Key == kvp2.Key;
    }
    public int GetHashCode(KeyValuePair<int, string> kvp)
    {
        return 1;
    }
}