using System;
using System.Collections.Generic;
using System.Linq;
using System.Xml;
using MatrixLibrary;

namespace Graphs
{
    /// <summary>
    /// Modélise un graphe.
    /// </summary>
    public class Graph
    {

        /// <summary>
        /// Identifiant du graphe. 
        /// </summary>
        string id;

        /// <summary>
        /// Nom du graphe permettant de le décrire.
        /// </summary>
        string name;

        /// <summary>
        /// Liste des noeuds du graphe.
        /// </summary>
        List<Node> listNodes;

        /// <summary>
        /// Liste des arcs/arêtes du graphe.
        /// </summary>
        List<Edge> listEdges;

        /// <summary>
        /// Permet d'indiquer si le graphe est orienté ou non.
        /// </summary>
        /// <value>true pour un graphe orienté</value>
        /// <value>false pour un graphe non orienté</value>
        Boolean isDirected;

        /// <summary>
        /// Matrice d'adjacence du graphe. 
        /// </summary>
        Matrix adjacencyMatrix;

        //Compteur de noeud pour donner un id lorsque l'utilisateur n'en spécifie pas
        int idNode;

        /// <summary>
        /// Identifiant du graphe. 
        /// </summary>
        public string Id
        {
            get { return id; }
            set { id = value; }
        }

        /// <summary>
        /// Nom du graphe permettant de le décrire.
        /// </summary>
        public string Name
        {
            get { return name; }
            set { name = value; }
        }


        /// <summary>
        /// Liste des noeuds du graphe.
        /// </summary>
        public List<Node> ListNodes
        {
            get { return listNodes; }
            set { listNodes = value; }
        }

        /// <summary>
        /// Liste des arcs/arêtes du graphe.
        /// </summary>
        public List<Edge> ListEdges
        {
            get { return listEdges; }
            set { listEdges = value; }
        }

        /// <summary>
        /// Permet d'indiquer si le graphe est orienté ou non.
        /// </summary>
        /// <value>true pour un graphe orienté</value>
        /// <value>false pour un graphe non orienté</value>
        public Boolean IsDirected
        {
            get { return isDirected; }
            set { isDirected = value; }
        }

        /// <summary>
        /// Initialise le graphe avec les valeurs par défaut.
        /// </summary>
        /// <value>id = null</value>
        /// <value>name = null</value>
        /// <value>isDirected = false</value>
        public Graph()
        {
            id = null;
            name = null;
            isDirected = false;
            listNodes = new List<Node>();
            listEdges = new List<Edge>();
            idNode = 0;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="id">Initialise l'attribut id</param>
        /// <param name="name">Initialise l'attribut name</param>
        /// <param name="isDirected">Initialise l'attribut isDirected</param>
        public Graph(string id, String name, Boolean isDirected)
        {
            Id = id;
            Name = name;
            IsDirected = isDirected;
            ListNodes = new List<Node>();
            ListEdges = new List<Edge>();
            idNode = 0;
        }


		 /// <summary>
        /// Change le type des labels dynamiquement sans avoir à faire un LoadGXL
		/// Condition : Les attributs GXL doivent supporter le changement de type
        /// </summary>
  		public  void DynamicCastLabel (Label labelNode, Label labelEdge)
		{

			foreach (Node n in ListNodes) {
				Type typeNode = labelNode.GetType ();
				object obj = Activator.CreateInstance (typeNode);
				n.Label = (Label)obj;
				n.Label.Id = n.Id;
				n.Label.fromAttributes (n.AttributesGXL);
			}

			foreach (Edge e in ListEdges) {
				Type typeEdge = labelEdge.GetType ();
				object obj = Activator.CreateInstance (typeEdge);
				e.Label = (Label)obj;
				e.Label.Id = e.Id;
				e.Label.fromAttributes (e.AttributesGXL);
			}

		}

        public void loadGXL(string url)
        {
            IOGraph IO = new IOGraph();
            IO.loadGXL(this, url);
            IO = null;
        }


        public void saveToGXL(string url)
        {
            IOGraph IO = new IOGraph();
            IO.saveToGXL(this, url);
            IO = null;
        }

        /// <summary>
        /// Charge le graphe depuis un fichier GXL dont l'URL est donnée en paramètre. Ce fichier doit respecter les normes GXL http://www.gupro.de/GXL/. Dans le fichier GXL, les noeuds doivent être déclarés avant les arcs qui les concernent.
        /// </summary>
        /// <param name="url">Adresse complète du fichier GXL à charger</param>
        /*public void loadGXL(string url)
        {
            //Réinitialisation du graphe
            Id = null;
            Name = null;
            IsDirected = false;
            while (listNodes.Count != 0)
            {
                deleteNodeAndEdges(listNodes.ElementAt(0));
            }


            XmlDocument objXmlDoc = new XmlDocument();

            //Chargement du fichier GXL
            try
            {
                objXmlDoc.Load(url);
            }
            catch (Exception err)
            {
                Console.WriteLine("Fichier introuvable");//TODO remonter erreur d'ouverture du fichier
            }

            // Récupération du noeud racine qui est la balise GXL
            XmlNode objRootNode = objXmlDoc.DocumentElement;

            // Récupération du premier noeud enfant qui est normalement un graphe
            XmlNode objChildNode = objRootNode.FirstChild;


            // Parcourt l'ensemble des noeuds XML
            while (objChildNode != null)
            {
                //Le premier noeud XML est normalement un graphe
                if (objChildNode.Name == "graph")
                {
                    //On parcourt ses attributs id, role, edgemode
                    foreach (XmlNode item in objChildNode.Attributes)
                    {
                        if (item.Name == "id") id = item.InnerText;

                        if (item.Name == "role") name = item.InnerText;

                        if (item.Name == "edgemode")
                        {
                            if (item.InnerText == "directed") isDirected = true;
                            if (item.InnerText == "undirected") isDirected = false;
                            //Exception pour defaultdirected  et defaultundirected
                        }
                    }

                    //On passe à l'enfant de graphe qui peut être node ou edge
                    objChildNode = objChildNode.FirstChild;

                    //On parcours tous les edges et nodes
                    while (objChildNode != null)
                    {

                        if (objChildNode.Name == "node")
                        {
                            Node node = new Node();

                            //Il n'y a que id mais on parcours quand même pour le trouver si l'utilisateur à mis plusieurs attributs
                            foreach (XmlNode item in objChildNode.Attributes)
                            {
                                if (item.Name == "id")
                                {
                                    node.Id = item.InnerText;
                                    //addNode(new Node(item.InnerText));
                                }
                            }

                            // On parcourt les attributs du node
                            XmlNode objChildAttr = objChildNode.FirstChild;

                            while (objChildAttr != null)
                            {

                                if (objChildAttr.Name == "attr")
                                {
                                    AttributeGXL attribut = new AttributeGXL();

                                    //On récupère le nom de l'attribut
                                    attribut.Name = objChildAttr.Attributes[0].InnerText;


                                    //On récupère son type et sa valeur
                                    objChildAttr = objChildAttr.FirstChild;

                                    attribut.Type = objChildAttr.Name;

                                    attribut.Value = objChildAttr.InnerText;

                                    objChildAttr = objChildAttr.ParentNode;

                                    node.AttributesGXL.Add(attribut);


                                }
                                objChildAttr = objChildAttr.NextSibling;
                            }


                            addNode(node);

                        }

                        else if (objChildNode.Name == "edge")
                        {
                            Edge edge = new Edge();


                            //On parcours, ce qui permet à l'utilisateur des mettre les attributs à l'envers pas erreur
                            foreach (XmlNode item in objChildNode.Attributes)
                            {
                                if (item.Name == "id") edge.Id = item.InnerText;

                                else if (item.Name == "to") edge.NodeTarget = findNode(item.InnerText);

                                else if (item.Name == "from") edge.NodeSource = findNode(item.InnerText);
                            }

                            // On parcourt les attributs du edge
                            XmlNode objChildAttr = objChildNode.FirstChild;

                            while (objChildAttr != null)
                            {

                                if (objChildAttr.Name == "attr")
                                {
                                    AttributeGXL attribut = new AttributeGXL();

                                    //On récupère le nom de l'attribut
                                    attribut.Name = objChildAttr.Attributes[0].InnerText;


                                    //On récupère son type et sa valeur
                                    objChildAttr = objChildAttr.FirstChild;

                                    attribut.Type = objChildAttr.Name;

                                    attribut.Value = objChildAttr.InnerText;

                                    objChildAttr = objChildAttr.ParentNode;

                                    edge.AttributesGXL.Add(attribut);


                                }
                                objChildAttr = objChildAttr.NextSibling;
                            }


                            addEdge(edge);

                        }

                        // Passe au noeud XML suivant représentant un node ou un edge
                        objChildNode = objChildNode.NextSibling;
                    }
                }

            }

        }*/

        /// <summary>
        /// Permet d'enregistrer le graphe dans un fichier GXL. Si le fichier existe déjà alors la méthode efface son contenu. Les Edge.Label et Node.Label doivent être transformer avec labelToAttributes() au préalable si nécessaire.
        /// </summary>
        /// <param name="url">Adresse complète du fichier GXL à enregistrer</param>
        /*public void saveToGXL(string url)
        {
            //Il faut initialiser les attributs
            labelToAttributes();
            //Création du document et de son en-tête
            XmlDocument doc = new XmlDocument();
            doc.LoadXml("<?xml version=\"1.0\" encoding=\"UTF-8\"?>" +
                        "<gxl xmlns:xlink=\" http://www.w3.org/1999/xlink\">" +
                        "</gxl>");

            //Le noeud root est <gxl>
            XmlNode root = doc.DocumentElement;


            string edgeMode;
            if (IsDirected) edgeMode = "directed";
            else edgeMode = "undirected";

            //Ajout du graphe
            XmlElement graphXML = doc.CreateElement("graph");
            graphXML.SetAttribute("id", Id);
            graphXML.SetAttribute("role", Name);
            graphXML.SetAttribute("edgemode", edgeMode);
            root.AppendChild(graphXML);

            //Ajout des noeuds
            foreach (Node n in ListNodes)
            {
                XmlElement nodeXML = doc.CreateElement("node");
                nodeXML.SetAttribute("id", n.Id);
                graphXML.AppendChild(nodeXML);

                //On ajoute les Label du noeud
                foreach (AttributeGXL a in n.AttributesGXL)
                {
                    XmlElement attrXML = doc.CreateElement("attr");
                    attrXML.SetAttribute("name", a.Name);

                    XmlElement typeXML = doc.CreateElement(a.Type);
                    typeXML.InnerText = a.Value;
                    attrXML.AppendChild(typeXML);

                    nodeXML.AppendChild(attrXML);
                }
            }

            //Ajout des edges
            foreach (Edge e in ListEdges)
            {
                XmlElement edgeXML = doc.CreateElement("edge");

                //Edge.Id n'est pas un champs obligatoire en GXL. IL peut être null ou "".
                if (e.Id != null && e.Id != "") edgeXML.SetAttribute("id", e.Id);
                edgeXML.SetAttribute("to", e.NodeTarget.Id);
                edgeXML.SetAttribute("from", e.NodeSource.Id);
                graphXML.AppendChild(edgeXML);

                //On ajoute les Label du noeud
                foreach (AttributeGXL a in e.AttributesGXL)
                {
                    XmlElement attrXML = doc.CreateElement("attr");
                    attrXML.SetAttribute("name", a.Name);

                    XmlElement typeXML = doc.CreateElement(a.Type);
                    typeXML.InnerText = a.Value;
                    attrXML.AppendChild(typeXML);

                    edgeXML.AppendChild(attrXML);
                }
            }

            //Sauvegarde du fichier

            doc.Save(url);
        }*/

        /// <summary>
        /// Lors de l'utilisation de loadGXL, les attributs sont chargés dans Node.AttributesGXL et Edge.AttributesGXL. Pour pouvoir les transférer dans Node.Label et Edge.Label, il faut que l'utilisateur détermine les types de Label qui seront utilisés.
        /// </summary>
        /// <param name="labelNode">Objet héritant de Label initialisant tous les Node.Label au bon type</param>
        /// <param name="labelEdge">Objet héritant de Label initialisant tous les Edge.Label au bon type</param>
        /*public void attributesToLabel(Label labelNode, Label labelEdge)
        {

            foreach (Node n in listNodes)
            {
                Type typeNode = labelNode.GetType();
                object obj = Activator.CreateInstance(typeNode);
                n.Label = (Label)obj;
                if (n.AttributesGXL.Count > 0) n.Label.fromAttributes(n.AttributesGXL);
            }

            foreach (Edge e in listEdges)
            {
                Type typeEdge = labelEdge.GetType();
                object obj = Activator.CreateInstance(typeEdge);
                e.Label = (Label)obj;

                if (e.AttributesGXL.Count != 0) e.Label.fromAttributes(e.AttributesGXL);
            }

        }*/

        /// <summary>
        /// Lorsque l'utilisateur construit le graphe à la main alors doit déterminer les Node.Label et Edge.Label. Pour que ces Label puissent être écrits en GXl avec saveToGXL, les Label doivent être transformés en AttributesGXL.
        /// </summary>
        /*public void labelToAttributes()
        {
            foreach (Node n in listNodes)
            {
                if (n.Label != null) n.AttributesGXL = n.Label.toAttributes();
            }

            foreach (Edge e in listEdges)
            {
                if (e.Label != null) e.AttributesGXL = e.Label.toAttributes();
            }
        }*/

        /// <summary>
        /// Ajoute un noeud au graphe. Node.Id doit être obligatoirement renseigné dans un fichier GXL. Si l'utilisateur n'a pas renseigné le Node.Id alors cette méthode détermine un id par défaut. L'id doit être unique. 
        /// </summary>
        /// <param name="n">Noeud à ajouter au graphe</param>
        /// <returns>True si le noeud avec id unique a été ajouté, False si le noeud n'a pas été ajouté car id non unique</returns>
        public Boolean addNode (Node n)
		{
			//Si l'utilisateur n'a pas spécifié d'id pour Node alors on crée son id
			if (n.Id == null) {
				n.Id = idNode.ToString ();
				idNode++;

				while (findNode(n.Id) != null) {
					n.Id = idNode.ToString ();
					idNode++;
				}
			}
			// On vérifie que l'id est unique
			if (findNode (n.Id) != null)
				return false;

			if (n.Label == null) {
				n.Label = new GenericLabel();
			}
			n.Label.Id=n.Id;
            ListNodes.Add(n);
            return true;

        }

        /// <summary>
        /// Ajoute un Edge au graphe et aux Node Edge.NodeSource et Edge.NodeTarget. L'id de l'Edge peut être null mais lorsqu'il est renseigné il doit être unique.
        /// </summary>
        /// <param name="e">Edge à ajouter au graphe</param>
        /// <returns>True si l'id renseigné est unique (id null possible), False sinon</returns>
        public Boolean addEdge(Edge e)
        {
            // On vérifie si l'id est déjà attribué lorsqu'il est différent de null
            if (findEdge(e.Id) != null && e.Id != null) return false;

            else
            {
                
				if(e.Id == null){
					e.Id = e.NodeSource.Id+"-"+e.NodeTarget.Id+"-"+this.ListEdges.Count;
				}
				if (e.Label == null) {
					e.Label = new GenericLabel();
				}
				e.Label.Id=e.Id;
				ListEdges.Add(e);

                if (IsDirected)
                {
                    e.NodeTarget.ListEdgesIn.Add(e);
                    e.NodeSource.ListEdgesOut.Add(e);
                }
                /*Quand un graphe est non orienté alors on ajoute seulement les arcs dans la liste des edges sortant*/
                else
                {
                    e.NodeTarget.ListEdgesOut.Add(e);
                    e.NodeSource.ListEdgesOut.Add(e);
                }


                return true;
            }
        }

        /// <summary>
        /// Supprime le noeud lorsque celui-ci n'a plus d'Edge associé.
        /// </summary>
        /// <param name="node">Node à supprimer du graphe</param>
        /// <returns>True si node a été supprimé, False s'il est introuvable ou qu'il contient encore des arcs. </returns>
        public Boolean deleteNode(Node node)
        {

            // Si le noeud ne contient pas d'arête alors on peu le supprimer
            if (node.ListEdgesIn.Count == 0 && node.ListEdgesOut.Count == 0) return ListNodes.Remove(node);

            else
            {
                // Si des arêtes existent encore sur le noeud alors on ne supprime pas et on avertit
                return false;
                // TODO gestion de l'exception
            }

        }

        /// <summary>
        /// Supprime le noeud et tous ses Edge associés
        /// </summary>
        /// <param name="n">Node à supprimer</param>
        /// <returns>True si le Node et ses Edges sont trouvés et supprimés, False sinon</returns>
        public Boolean deleteNodeAndEdges(Node n)
        {
            Boolean bReturn = true;

            while (n.ListEdgesIn.Count != 0)
            {
                bReturn = bReturn && deleteEdge(n.ListEdgesIn.ElementAt(0));
            }

            while (n.ListEdgesOut.Count != 0)
            {
                bReturn = bReturn && deleteEdge(n.ListEdgesOut.ElementAt(0));
            }

            return bReturn && deleteNode(n);
        }

        /// <summary>
        /// Supprime l'Edge du graphe.
        /// </summary>
        /// <param name="edge">Edge à supprimé</param>
        /// <returns>True si edge est trouvé et supprimé, False sinon</returns>
        public Boolean deleteEdge(Edge edge)
        {
            Boolean bReturn = true;

            // On supprime ce edge des noeuds
            if (isDirected)
            {
                bReturn = bReturn && edge.NodeTarget.ListEdgesIn.Remove(edge);
                bReturn = bReturn && edge.NodeSource.ListEdgesOut.Remove(edge);
            }

            else
            {
                bReturn = bReturn && edge.NodeSource.ListEdgesOut.Remove(edge);
                bReturn = bReturn && edge.NodeTarget.ListEdgesOut.Remove(edge);

            }


            return bReturn && ListEdges.Remove(edge);
        }

        /// <summary>
        /// Calcule la matrice d'adjacence du graphe. Les indices du tableau correspondent à l'indice des noeuds dans ListNodes. 
        /// </summary>
        /// <returns>Matrice d'adjacence du graphe</returns>
        public Matrix calculateAdjacencyMatrix()
        {
            adjacencyMatrix = new Matrix(listNodes.Count, listNodes.Count);

            //initialisation de la matrice à 0
            for (int i = 0; i < adjacencyMatrix.NoRows; i++)
            {
                for (int j = 0; j < adjacencyMatrix.NoCols; j++)
                {
                    adjacencyMatrix[i, j] = 0;
                }
            }

            //Insertion des valeurs "1"
            foreach (Edge e in listEdges)
            {
                if (isDirected)
                {
                    adjacencyMatrix[listNodes.IndexOf(e.NodeSource), listNodes.IndexOf(e.NodeTarget)] = 1;
                }
                else
                {
                    adjacencyMatrix[listNodes.IndexOf(e.NodeSource), listNodes.IndexOf(e.NodeTarget)] = 1;
                    adjacencyMatrix[listNodes.IndexOf(e.NodeTarget), listNodes.IndexOf(e.NodeSource)] = 1;
                }
            }
            return adjacencyMatrix;
        }

        /// <summary>
        /// Permet de trouver un Node par son id.
        /// </summary>
        /// <param name="id">id du Node à trouver</param>
        /// <returns>Node ayant l'id passé en paramètre. Si aucun Node n'est trouvé alors la méthode retourne null.</returns>
        public Node findNode(String id)
        {
            Node n = ListNodes.Find(
                delegate
                (Node node)
                {
                    return node.Id == id;
                }
            );

            return n;
        }

        /// <summary>
        /// Permet de trouver un Node dans la liste en le passant en paramétre.
        /// </summary>
        /// <param name="node">Node à trouver</param>
        /// <returns>Recherche le Node dans la liste. Retourne le noeud s'il est trouvé, renvoit null sinon.</returns>
        public Node findNode(Node node)
        {
            Node n = ListNodes.Find(
                delegate
                (Node nod)
                {
                    return nod.Id == node.Id;
                }
            );
            return n;
        }


        /// <summary>
        /// Permet de trouver un Edge par son id. Attention toutefois, les Edges n'ont pas forcément d'id renseigné et l'id est alors null.
        /// </summary>
        /// <param name="id">id de l'Edge à trouver</param>
        /// <returns>Edge ayant l'id passé en paramètre. Si aucun Edge n'est trouvé alors la méthode retourne null.</returns>
        public Edge findEdge(String id)
        {
            Edge e = ListEdges.Find(
                delegate
                (Edge edge)
                {
                    return edge.Id == id;
                }
            );

            return e;
        }

    }
}