using System;

using System.Collections.Generic;

using System.Linq;

/*

    Clase RUTA

*/

public class Ruta

{

    public Ruta(string destino, int distancia)

    {

        this.destino = destino;

        this.distancia = distancia;

    }

    public string destino { get; set; }

    public int distancia { get; set; }

}

​

/*

    Clase NODO

*/

public class Nodo

{

    public Nodo()

    {

    }

    public int Heuristica { get; set; }

    public string Datos { get; set; }

    public Nodo Padre { get; set; }

    public List<Nodo> Hijos { get; set; }

    public int Costo { get; set; }

    public void SetHijos(List<Ruta> conexiones, Dictionary<string, int> heuristica)

    {

        this.Hijos = new List<Nodo>();

        foreach (var conexion in conexiones)

        {

            var heuristicaNodo = heuristica.First(n => n.Key == conexion.destino).Value;

            this.Hijos.Add(new Nodo()

                           {

                               Datos = conexion.destino, 

                               Costo = conexion.distancia + this.Costo, 

                               Heuristica = heuristicaNodo, 

                               Padre = this

                           });

        }

    }

}

​

/* 

    PROGRAMA PRINCIPAL 

*/

public class Program

{

    public enum TipoBusqueda

        {

            Avara,

            AEstrella

​

        }

        public static Dictionary<string, List<Ruta>> conexiones;

        public static Dictionary<string, int> heuristica;

​

        public static void Main()

        {

            CargarHeuristica();

            CargarConexiones();

​

            var listaFrontera = new List<Nodo>();

            var listaVisitados = new List<Nodo>();

            var caminoSolucion = "";

            TipoBusqueda tipoBusqueda = TipoBusqueda.AEstrella;

            //TipoBusqueda tipoBusqueda = TipoBusqueda.Avara;

            bool seEncontroElObjetivo = false;

​

            // Configurar estado inicial y estado objetivo

            string estadoInicial = "D";

            string estadoObjetivo = "F";

​

            // nodo de la lista de conexiones por Clave / Valor

            KeyValuePair<string, List<Ruta>> nodoConexionActual;

​

            // Agregar nodo inicial a la frontera 

            listaFrontera.Add(new Nodo()

            {

                Datos = estadoInicial,

                Costo = 0,

                Heuristica = heuristica.First(h => h.Key == estadoInicial).Value //Obtiene la heuristica para el estado inicial.

            });

​

            while (!seEncontroElObjetivo)

            {

                // Tomar el primer nodo de la lista frontera;

                Nodo nodoActual = listaFrontera.First();

​

                nodoConexionActual = conexiones.First(conexion => conexion.Key == nodoActual.Datos);

                // Eliminar de la lista frontera el nodo actual

                listaFrontera.Remove(listaFrontera.First(nodo => nodo.Datos == nodoActual.Datos));

​

                if (nodoActual.Datos != estadoObjetivo)

                {

                    // Agregar a la lista de nodos visitados        

                    listaVisitados.Add(nodoActual);

                    // Value => lista de conexiones del nodo actual, Lista de heuristica.

                    nodoActual.SetHijos(nodoConexionActual.Value, heuristica);

​

                    foreach (var hijo in nodoActual.Hijos)

                    {

                        if (!EstaEnLista(listaVisitados, hijo))

                        {

                            var nodoEnFrontera = ObtenerNodo(listaFrontera, hijo);

                            if(nodoEnFrontera != null){

                                // MODIFICACION

                                if (SePuedeAgregarElNodo(nodoEnFrontera, hijo, tipoBusqueda)){

                                    listaFrontera.Remove(nodoEnFrontera);

                                    listaFrontera.Add(hijo);

                                }

                            }else

                            {

                                listaFrontera.Add(hijo);

                            }                            

                        }

                    }

​

                    listaFrontera = ObtenerListaOrdenada(tipoBusqueda, listaFrontera);

                }

                else

                {

                    seEncontroElObjetivo = true;

                    caminoSolucion = ObtenerCaminoSolucion(listaVisitados, nodoActual);

                }

            }

​

            Console.WriteLine("Camino solución desde " + estadoInicial + " hacia " + estadoObjetivo + ": " + caminoSolucion);

​

        }

​

    public static bool SePuedeAgregarElNodo(Nodo nodoEnFrontera, Nodo nodoActual, TipoBusqueda tipoBusqueda){

        bool sePuedeAgregar = false;

        switch(tipoBusqueda){

            case TipoBusqueda.AEstrella:

            var evaluacionEstrellaFrontera = nodoEnFrontera.Costo + nodoEnFrontera.Heuristica;

            var evaluacionEstrellaNodo = nodoActual.Costo + nodoActual.Heuristica;

            if(evaluacionEstrellaFrontera > evaluacionEstrellaNodo){

                sePuedeAgregar = true;

            }

            break;

            case TipoBusqueda.Avara:

            var evaluacionAvaraFrontera = nodoEnFrontera.Heuristica;

            var evaluacionAvaraNodo = nodoActual.Heuristica;

            if(evaluacionAvaraFrontera > evaluacionAvaraNodo){

                sePuedeAgregar = true;

            }

            break;

        }

        return sePuedeAgregar;

    }

        public static string ObtenerCaminoSolucion(List<Nodo> listaVisitados, Nodo nodoObjetivo)

        {

            List<string> camino = new List<String>();

​

            string caminoSolucion = "";

​

            Nodo nodoActual = nodoObjetivo;

​

            while (nodoActual.Padre != null)

            {

                camino.Add(nodoActual.Datos);

                nodoActual = nodoActual.Padre;

            }

​

            camino.Add(nodoActual.Datos);

​

            camino.Reverse();

​

            foreach (var paso in camino)

            {

                caminoSolucion += "[" + paso + "] ";

            }

​

            return caminoSolucion + " - Costo: " + nodoObjetivo.Costo;

        }

​

        // Evaluar si la lista pasada como parametro contiene al nodo

        public static Nodo ObtenerNodo(List<Nodo> lista, Nodo nodo)

        {

            return lista.FirstOrDefault(n => n.Datos == nodo.Datos);

        }

​

​

        // Evaluar si la lista pasada como parametro contiene al nodo

        public static bool EstaEnLista(List<Nodo> lista, Nodo nodo)

        {

            return lista.Any(n => n.Datos == nodo.Datos);

        }

​

        public static List<Nodo> ObtenerListaOrdenada(TipoBusqueda tipoBusqueda, List<Nodo> listaFrontera)

        {

            List<Nodo> nuevaListaFrontera = new List<Nodo>();

            switch (tipoBusqueda)

            {

                case TipoBusqueda.AEstrella:

                    // Ordenar la lista frontera de menor a mayor por funcion evaluacion.

                    nuevaListaFrontera = listaFrontera.OrderBy(n => { return n.Heuristica + n.Costo; }).ToList();

                    break;

                case TipoBusqueda.Avara:

                    // Ordenar la lista frontera de menor a mayor por heuristica.

                    nuevaListaFrontera = listaFrontera.OrderBy(n => n.Heuristica).ToList();

                    break;

            }

​

            return nuevaListaFrontera;

        }

​

​

        public static void CargarHeuristica()

        {

            // Cargar Heuristica para nodo objetivo. B en este caso

            heuristica = new Dictionary<string, int>();

​

            /*heuristica.Add("A", 366);

            heuristica.Add("B", 0);

            heuristica.Add("C", 160);

            heuristica.Add("D", 242);

            heuristica.Add("E", 161);

            heuristica.Add("F", 178);

            heuristica.Add("G", 77);

            heuristica.Add("H", 151);

            heuristica.Add("I", 226);

            heuristica.Add("L", 244);

            heuristica.Add("M", 241);

            heuristica.Add("N", 234);

            heuristica.Add("O", 380);

            heuristica.Add("P", 98);

            heuristica.Add("R", 193);

            heuristica.Add("S", 253);

            heuristica.Add("T", 329);

            heuristica.Add("U", 80);

            heuristica.Add("V", 199);

            heuristica.Add("Z", 374);*/

            // TP 2 - Heuristica

            heuristica.Add("A", 5);

            heuristica.Add("B", 20);

            heuristica.Add("C", 0);

            heuristica.Add("D", 0);

            heuristica.Add("E", 0);

            heuristica.Add("F", 25);

            heuristica.Add("G", 20);

            heuristica.Add("H", 5);

        }

        public static void CargarConexiones()

        {

            // Inicializar conexiones con costos y heuristicas 

            // Key del diccionario es un Objeto Clave/Valor -> contiene Datos/Heuristica

            // Value del diccionario es un Objeto Clave/Valor -> contiene Costo/Nodo destino

            conexiones = new Dictionary<string, List<Ruta>>();

            AgregarConexion("A", "B", 10);

            AgregarConexion("A", "E", 40);

            AgregarConexion("B", "E", 20);

            AgregarConexion("D", "C", 5);

            AgregarConexion("D", "E", 10);

            AgregarConexion("F", "A", 10);

            AgregarConexion("F", "B", 30);

            AgregarConexion("F", "G", 10);

            AgregarConexion("F", "H", 20);

            AgregarConexion("G", "B", 20);

            AgregarConexion("G", "D", 10);

            AgregarConexion("H", "E", 10);

            /*AgregarConexion("A", "Z", 75);

            AgregarConexion("A", "T", 118);

            AgregarConexion("A", "S", 140);

            AgregarConexion("T", "L", 111);

            AgregarConexion("L", "M", 70);

            AgregarConexion("M", "D", 75);

            AgregarConexion("D", "C", 120);

            AgregarConexion("C", "R", 146);

            AgregarConexion("C", "P", 138);

            AgregarConexion("P", "R", 97);

            AgregarConexion("P", "B", 101);

            AgregarConexion("B", "G", 90);

            AgregarConexion("B", "F", 211);

            AgregarConexion("F", "S", 99);

            AgregarConexion("S", "R", 80);

            AgregarConexion("O", "S", 151);

            AgregarConexion("Z", "O", 71);

            AgregarConexion("B", "U", 85);

            AgregarConexion("U", "H", 98);

            AgregarConexion("U", "V", 142);

            AgregarConexion("H", "E", 86);

            AgregarConexion("V", "I", 92);

            AgregarConexion("I", "N", 87);*/

​

            Console.WriteLine(ImprimirListaNodosYConexiones(conexiones));

        }

​

        public static void AgregarConexion(string origen, string destino, int distancia)

        {

            var nodoOrigen = conexiones.Where(n => n.Key == origen).FirstOrDefault();

​

            //  Cargar el camino origen - destino

            if (nodoOrigen.Key != null)

            {

                nodoOrigen.Value.Add(new Ruta(destino, distancia));

            }

            else

            {

                var listaNodos = new List<Ruta>();

                listaNodos.Add(new Ruta(destino, distancia));

                conexiones.Add(origen, listaNodos);

            }

​

            //  Cargar el camino inverso

            var nodoDestino = conexiones.Where(n => n.Key == destino).FirstOrDefault();

​

            if (nodoDestino.Key != null)

            {

                nodoDestino.Value.Add(new Ruta(origen, distancia));

            }

            else

            {

                var listaNodos = new List<Ruta>();

                listaNodos.Add(new Ruta(origen, distancia));

                conexiones.Add(destino, listaNodos);

            }

​

        }

​

        public static string ImprimirListaNodosYConexiones(Dictionary<string, List<Ruta>> conexiones)

        {

            string lista = "Caminos => ";

            foreach (var conexion in conexiones)

            {

                lista = lista + "\nDesde " + conexion.Key + ":\n";

                foreach (var ruta in conexion.Value)

                {

                    lista = lista + ruta.destino + " - " + ruta.distancia + " // ";

                }

            }

​

            return lista;

        }

}