using System.Collections.Generic;
using System.Collections;
using System;
using System.Windows.Forms;

namespace Tspform
{
    public class ACO : Algorithm
    {
        Tsp tspsolver;
        private static int M = 30;//The ant number 蚂蚁的数量
        private static int N = 30;//The city size 城市的数量 
        int inittao = 1; //The initial pheromone 信息素初始时刻值 
        private double[,] tao;//Define the pheromone matrix 信息素矩阵
        private double[,] detatao;//Define the increase of pheromone matrix 信息素增加量矩阵
        private double[,] distance; //Define the distance of cities 城市间的距离矩阵
        private double[] x;//The x_coordinate of the city 城市的横坐标
        private double[] y;//The y_coordinate of the city 城市的纵坐标    
        private int NcMax;//The maximum of the count of iteration
        private double[,] Tk;//To store the cities which has visited
        private int[,] NTk;//To choose the cities which has not visited
        private int[,] route;//Store all the cities has visited
        private int[] Lk;//Store the current route
        private double[] solution;// Store the shortest route
        private double bestSolution = 10000000000000000000;//Set the initial bestSolution is very large
        private double beta, rou;
        private int Q;//The some parameter of the algorithm     
        private double ppij;//The probability of the ant moving
        int Nc = 0;        //The current times of iternation

        public ACO(int m, int n, Tsp tspsolver, double beta, double rou, int Q, int NcMax, double[] x, double[] y, int C, ref int[] Lk)//Initialize the parameter
        {
            M = m;
            N = n;
            this.tspsolver = tspsolver;
            this.beta = beta;
            this.rou = rou;
            this.Q = Q;
            this.NcMax = NcMax;
            this.x = x;
            this.y = y;
            this.inittao = C;
            this.Lk = new int[N];
            this.distance = new double[N, N];
            this.tao = new double[N, N];
            this.detatao = new double[N, N];
            this.Tk = new double[M, N];
            this.NTk = new int[M, N];
            this.route = new int[M, N];
            this.solution = new double[M];
            
            
        }
     

        public override void ResultRoute()//Ant start move by accroding the algorithm, each ant try to find the optimal path
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    distance[i, j] = (new Wj()).Getdistance(x[i], y[i], x[j], y[j]);
                    tao[i, j] = inittao;
                    detatao[i, j] = 0.0;
                }

            }

            for (int i = 0; i < M; i++)//Set the cities are 0 if the ant has visited
            {
                for (int n = 0; n < N; n++)
                {
                    Tk[i, n] = 0;
                    route[i, i] = -1;
                }
                if (Wj.startcityNumber != -1)
                {
                    route[i, 0] = Wj.startcityNumber - 1;
                    Tk[i, route[i, 0]] = 1;
                }
                else
                {
                    for (int n = 0; n < N; n++)
                    {
                        route[i, 0] = i % N;  //set the start city of ant
                        Tk[i, route[i, 0]] = 1;
                    }
                }

            }
            while (Nc < NcMax)
            {
                int s = 1;  
                double pij = 0;
                double denominator = 0;  //the denominator of the pij
                Random drand = new Random();// set the random at the begining of ant move
                while (s < N)     //
                {
                    for (int k = 0; k < M; k++) 
                    {
                        pij = 0;  
                        denominator = 0;
                        ppij = drand.Next(3000) / 3000.0;  
                        for (int j = 0; j < N; j++)
                        {
                            if (Tk[k, j] == 0)   
                            {
                                try
                                {
                                    denominator =denominator + (tao[route[k, s - 1], j]) * Math.Pow(1/distance[route[k, s - 1], j], beta);  //the denominator of pij
                                }
                                catch (System.Exception ex) 
                                {
                                    continue ;
                                }
                            }
                        }
                        for (int j = 0; j < N; j++)
                        {
                            if (Tk[k, j] == 0)
                            {
                                try
                                {

                                    pij =pij+ (tao[route[k, s - 1], j]) * Math.Pow(1/distance[route[k, s - 1], j], beta) / denominator;  //calculate the probability of ant move
                                    if (pij > ppij)   
                                    {
                                        Tk[k, j] = 1;  
                                        route[k, s] = j; 
                                        break;
                                    }
                                }
                                catch(System .Exception ex) 
                                {
                                   continue ;
                                }
                            }
                        }
                    }
                    s++;
                }

                int shortant = 0;// update the the shortbest of current route
                for (int k = 0; k < M; k++)
                {
                    solution[k] = AllRoute(k);
                    try
                    {

                        if (solution[k] < bestSolution)
                        {
                            bestSolution = solution[k];
                            shortant = k;
                        }
                    }
                    catch (Exception ex)
                    {
                        continue;
                    }
                }           
                for (int i = 0; i < N; i++)
                {
                    Lk[i] = route[shortant, i]; 
               
                }


                //calculate the increse pheromone
                for (int k = 0; k < M; k++)
                {
                    for (int j = 0; j < N - 1; j++)
                    {
                        detatao[route[k, j], route[k, j + 1]] = Q / solution[k] + detatao[route[k, j], route[k, j + 1]];  
                    }
                    detatao[route[k, N - 1], route[k, 0]] = Q / solution[k] + detatao[route[k, N - 1], route[k, 0]];
                }

                for (int i = 0; i < N; i++)//update the pheromone
                {
                    for (int j = 0; j < N; j++)
                    {
                        tao[i, j] = (1 - rou) * tao[i, j] + detatao[i, j]; 
                    }
                  
                }
            
                for (int k = 0; k < M; k++)//update the Tk
                {
                    for (int j = 1; j < N; j++) 
                    {
                        route[k, j] = -1;
                    }
                    for (int i = 0; i < N; i++)
                    {
                        Tk[k, i] = 0;
                    }
                    Tk[k, route[k, 0]] = 1;
                
                }

                tspsolver.ShowLength(Nc + 1, bestSolution);
                tspsolver.DrawRoute(Lk);
                Nc++;
            };
        }

        public override double AllRoute(int j)//calculate the final route of the ant
        {
            double distance = 0;
            for (int i = 0; i < N - 1; i++)
            {
                distance =distance+ this.distance[this.route[j, i], this.route[j, i + 1]];              
            }
            distance = distance + this.distance[this.route[j, N - 1], this.route[j, 0]];
            return distance;
        }
    }
}