using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;
using TSP;

namespace TSP_Solver
{
    public delegate void optimumRouteChangeDelegate();

    public delegate void progressReportDelegate(double progress);

    public delegate void statusReportDelegate(String message);


    public abstract class TSPSolver
    {
        private TSPGrid grid;
        private City[] cities;
        private  int gridSize;
        private City[] optimumRoute;
        private double optimumRouteLength;
        private event optimumRouteChangeDelegate optimumRouteChangeEvent;
        private event progressReportDelegate progressReportEvent;
        private event statusReportDelegate statusReportEvent;


        public TSPSolver(TSPGrid g)
        {
            grid = g;

            gridSize = grid.GridSize;

            optimumRoute = new City[gridSize];

            cities = grid.Cities;
        }

        public TSPGrid Grid
        {
            get { return grid; }
        }

        public City[] Cities
        {
            get { return cities; }
        }

        public int GridSize
        {
            get { return gridSize; }
        }

        public City[] OptimumRoute
        {
            get { return optimumRoute; }

            set { optimumRoute = value;}
        }

        public double OptimumRouteLength
        {
            get { return optimumRouteLength; }

            set { optimumRouteLength = value; }
        }

        public void fireOptimumRouteChangeEvent()
        {
            // Fire sensor state change event
            optimumRouteChangeEvent();
        }

        public void fireProgressReportEvent(double progress)
        {
            // Fire sensor state change event
            progressReportEvent(progress);
        }

        public void fireStatusReportEvent(String message)
        {
            // Fire sensor state change event
            statusReportEvent(message);
        }

        public event optimumRouteChangeDelegate OptimumRouteChangeEvent
        {
            add
            {
                optimumRouteChangeEvent += value;
            }

            remove
            {
                optimumRouteChangeEvent -= value;
            }
        }

        public event progressReportDelegate ProgressReportEvent
        {
            add
            {
                progressReportEvent += value;
            }

            remove
            {
                progressReportEvent -= value;
            }
        }

        public event statusReportDelegate StatusReportEvent
        {
            add
            {
                statusReportEvent += value;
            }

            remove
            {
                statusReportEvent -= value;
            }
        } 

        public abstract void solve();
    }

    public class TSPGreedySolver:TSPSolver
    {
        public TSPGreedySolver(TSPGrid g):base(g) {}
      
        public override void solve()
        {
             City[] route = new City[GridSize];

            OptimumRouteLength = Double.MaxValue;

            foreach (City c in Cities)
                c.Visited = false;

            // Iterate from each starting city
            int progress = 0;
            foreach (City c in Cities)
            {
                progress++;

                fireProgressReportEvent(100.0 * progress/GridSize);

                c.Visited = true; 

                int routeCount = 0;

                route[routeCount++] = c;

                City c1 = c;

                double routeLength=0;

                do
                {
     
                    int cityIndex = c1.Index;

                    EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                    // Find the first unvisited city in the list of adjoining cities
                    int edgeCount = 0;

                    EdgeStruct e = edgeList[edgeCount++];

                    c1 = Cities[e.RightCity];

                    while (c1.Visited)
                    {
                        e = edgeList[edgeCount++];

                        c1 = Cities[e.RightCity];
                    }

                    c1.Visited = true;

                    route[routeCount++] = c1;

                    routeLength += e.CityDistance;

                } while (routeCount < GridSize);

                // Add length back to starting city
                routeLength += (new EdgeStruct(c1, c)).CityDistance;

                // Copy route into the optimum route if it has a smaller route length
                if (routeLength < OptimumRouteLength)
                {
                    OptimumRouteLength = routeLength;

                    Array.Copy(route, OptimumRoute, GridSize);

                    // Fire route change event
                    fireOptimumRouteChangeEvent();
                }

                // Reset city visiting status
                foreach (City c2 in Cities)               
                    c2.Visited = false; 
            }

            return;
        }
    }

    class ACOEdgeLabels
    {
        private double pheromoneLevel;

        public double PheromoneLevel
        {
            get { return pheromoneLevel; }

            set { pheromoneLevel = value; }
        }
    }

    public class TSPACOSolver : TSPSolver
    {
        protected double pheromoneInfluence, evaporationRate;

        protected const double initialPheromoneLevel = 1.0e-5;

        protected double pheremoneConstant = 0.0;

        protected int numberOfAnts, maxIterations;

        protected int neighbourhoodSize;

        public TSPACOSolver(TSPGrid g)
            : base(g)
        {
            // Give default parameter values
            numberOfAnts = GridSize;
            pheromoneInfluence = 7.0;
            evaporationRate = 0.5;
            maxIterations = 3000;
            neighbourhoodSize = 10;   // Consider all possible cities in the neighbourhood
        }

        public TSPACOSolver(TSPGrid g, int _numberOfAnts, int _maxIterations, double _pheromoneInfluence, double _evaporationRate, int _neighbourhoodSize)
            : base(g)
        {
            numberOfAnts = _numberOfAnts;
            pheromoneInfluence = _pheromoneInfluence;
            evaporationRate = _evaporationRate;
            maxIterations = _maxIterations;
            neighbourhoodSize = _neighbourhoodSize;
        }

        public override void solve()
        {
            Random rand = new Random();

            OptimumRouteLength = Double.MaxValue;

            EdgeStruct[][] route = new EdgeStruct[numberOfAnts][];

            for (int i = 0; i < numberOfAnts; i++)
                route[i] = new EdgeStruct[GridSize - 1];

            double[] routeLength = new double[numberOfAnts];

            double[] decisionMatrixRowTotals = new double[GridSize];       // For normalizing the decision matrix probabilities

            for (int i = 0; i < GridSize; i++)
                decisionMatrixRowTotals[i] = 0.0;

            // Initialize the ACO edge label information on each edge 
            foreach (City c in Cities)
            {
                c.Visited = false;
                int cityIndex = c.Index;

                EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                // Normalize the decision matrix probality totals
                for (int i = 0; i < (GridSize - 1); i++)
                {
                    edgeList[i].EdgeValues = new ACOEdgeLabels();
                    ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                    el.PheromoneLevel = initialPheromoneLevel;
                    double distance = edgeList[i].CityDistance;
                    distance = Math.Max(1.0, distance);
                    decisionMatrixRowTotals[cityIndex] += (initialPheromoneLevel * Math.Pow(distance, -pheromoneInfluence));
                }
            }


            // Iterate a fixed number of times and return the best solution
            for (int t = 0; t < maxIterations; t++)
            {
                fireProgressReportEvent(100.0 * t / maxIterations);

                // For each ant, perform a random tour and deposit pheromone
                double totalRouteLength = 0.0;
                for (int antID = 0; antID < numberOfAnts; antID++)
                {
                    int cityStartIndex = antID;

                    City c = Cities[cityStartIndex];

                    c.Visited = true;

                    int routeCount = 0;

                    routeLength[antID] = 0.0;

                    City c1 = c;

                    do
                    {

                        int cityIndex = c1.Index;

                        EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                        // Re-normalize the decision matrix row probality totals
                        decisionMatrixRowTotals[cityIndex] = 0.0;
                        int neighbourCount = 0;
                        int i = 0;
                        do
                        {
                            if (!Cities[edgeList[i].RightCity].Visited)
                            {
                                neighbourCount++;
                                ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                                double distance = edgeList[i].CityDistance;
                                distance = Math.Max(distance, 1.0);     // Distance can't be zero
                                decisionMatrixRowTotals[cityIndex] += Math.Abs((el.PheromoneLevel * Math.Pow(distance, -pheromoneInfluence)));
                            }
                            i++;
                        } while ((neighbourCount < neighbourhoodSize) && (i < (GridSize - 1)));

                        // Determine next city to visit according to the decision matrix
                        double decisionSum = 0.0;
                        double randVal = rand.NextDouble();
                        int edgeCount = 0;
                        while ((randVal > decisionSum) && (edgeCount < (GridSize - 1)))
                        {

                            ACOEdgeLabels el = (ACOEdgeLabels)edgeList[edgeCount].EdgeValues;

                            if (!(Cities[edgeList[edgeCount].RightCity].Visited))
                            {
                                double distance = edgeList[edgeCount].CityDistance;

                                distance = Math.Max(distance, 1.0);     // Distance can't be zero

                                double decisionProb = Math.Abs((el.PheromoneLevel * Math.Pow(distance, -pheromoneInfluence)));

                                decisionProb /= decisionMatrixRowTotals[cityIndex];

                                decisionSum += decisionProb;

                                if (randVal <= decisionSum)
                                {
                                    c1 = Cities[edgeList[edgeCount].RightCity];

                                    cityIndex = c1.Index;

                                    c1.Visited = true;

                                    route[antID][routeCount++] = edgeList[edgeCount];

                                    routeLength[antID] += edgeList[edgeCount].CityDistance;
                                }
                            }

                            edgeCount++;
                        }

                    } while (routeCount < (GridSize - 1));

                    // Add length back to starting city
                    routeLength[antID] += (new EdgeStruct(c1, c)).CityDistance;

                    totalRouteLength += routeLength[antID];

                    // Copy route into the optimum route if it has a smaller route length
                    if (routeLength[antID] < OptimumRouteLength)
                    {
                        OptimumRouteLength = routeLength[antID];

                        OptimumRoute[0] = Cities[route[antID][0].LeftCity];
                        for (int i = 1; i < GridSize; i++)
                            OptimumRoute[i] = Cities[route[antID][i - 1].RightCity];

                        // Fire route change event
                        fireOptimumRouteChangeEvent();
                    }


                    foreach (City c2 in Cities)
                        c2.Visited = false;
                }

                // Evaporate the pheremone for every edge
                foreach (City c in Cities)
                {
                    int cityIndex = c.Index;
                    EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                    for (int i = 0; i < (GridSize - 1); i++)
                    {
                        ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                        el.PheromoneLevel *= (1.0 - evaporationRate);

                        if (el.PheromoneLevel<initialPheromoneLevel)
                            el.PheromoneLevel = initialPheromoneLevel;
                    }
                }

                // Evaluate the pheremone constant for the first iteration
                if (t == 0)
                {
                    double averageRouteLength = totalRouteLength / numberOfAnts;       // Average route length for evaluating pheremone normalizing constant

                    pheremoneConstant = GridSize * GridSize * averageRouteLength * initialPheromoneLevel * 50.0 / maxIterations;

                }

                // Udate the pheromone levels on each edge for each ant
                for (int antID = 0; antID < numberOfAnts; antID++)
                {
                    EdgeStruct[] antsRoute = route[antID];

                    for (int i = 0; i < (GridSize - 1); i++)
                    {
                        ACOEdgeLabels el = (ACOEdgeLabels)antsRoute[i].EdgeValues;
                        el.PheromoneLevel += pheremoneConstant / routeLength[antID];
                    }
                }

            }   // Next iteration

            return;
        }
    }

   
    public class TSPACOSolverV2 : TSPACOSolver
    {

        protected void resetPheromone()
        {
            foreach (City c in Cities)
            {
                c.Visited = false;
                int cityIndex = c.Index;

                EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                for (int i = 0; i < (GridSize - 1); i++)
                {
                    edgeList[i].EdgeValues = new ACOEdgeLabels();
                    ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                    el.PheromoneLevel = initialPheromoneLevel;
                }
            }
        }

        public TSPACOSolverV2(TSPGrid g)
            : base(g)
        {
            // Give default parameter values
            numberOfAnts = GridSize;
            pheromoneInfluence = 7.0;
            evaporationRate = 0.5;
            maxIterations = 3000;
            neighbourhoodSize = 10;   // Consider all possible cities in the neighbourhood
        }

        public TSPACOSolverV2(TSPGrid g, int _numberOfAnts, int _maxIterations, double _pheromoneInfluence, double _evaporationRate,
            int _neighbourhoodSize)
            : base(g, _numberOfAnts, _maxIterations, _pheromoneInfluence, _evaporationRate, _neighbourhoodSize)
        { }

        public override void solve()
        {
            Random rand = new Random();

            OptimumRouteLength = Double.MaxValue;

            EdgeStruct[][] route = new EdgeStruct[numberOfAnts][];

            for (int i = 0; i < numberOfAnts; i++)
                route[i] = new EdgeStruct[GridSize - 1];

            double[] routeLength = new double[numberOfAnts];

            double[] decisionMatrixRowTotals = new double[GridSize];       // For normalizing the decision matrix probabilities

            for (int i = 0; i < GridSize; i++)
                decisionMatrixRowTotals[i] = 0.0;

            // Initialize the ACO edge label information on each edge 
            foreach (City c in Cities)
            {
                c.Visited = false;
                int cityIndex = c.Index;

                EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                // Normalize the decision matrix probality totals
                for (int i = 0; i < (GridSize - 1); i++)
                {
                    edgeList[i].EdgeValues = new ACOEdgeLabels();
                    ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                    el.PheromoneLevel = initialPheromoneLevel;
                    double distance = edgeList[i].CityDistance;
                    distance = Math.Max(1.0, distance);
                    decisionMatrixRowTotals[cityIndex] += (initialPheromoneLevel * Math.Pow(distance, -pheromoneInfluence));
                }
            }


            // Iterate a fixed number of times and return the best solution
            EdgeStruct[] optimumRouteRefs = new EdgeStruct[GridSize - 1];   // References adjacency list EdgeStruct elements
            double decisionProbabilityThreshold;
            for (int t = 0; t < maxIterations; t++)
            {
                
                fireProgressReportEvent(100.0 * t / maxIterations);

                decisionProbabilityThreshold = (double)t / (double)maxIterations;

                // For each ant, perform a random tour and deposit pheromone
                double totalRouteLength = 0.0;
                for (int antID = 0; antID < numberOfAnts; antID++)
                {
                    int cityStartIndex = antID;

                    City c = Cities[cityStartIndex];

                    c.Visited = true;

                    int routeCount = 0;

                    routeLength[antID] = 0.0;

                    City c1 = c;

                    do
                    {

                        int cityIndex = c1.Index;

                        EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                        // Re-normalize the decision matrix row probality totals
                        decisionMatrixRowTotals[cityIndex] = 0.0;
                        int neighbourCount = 0;
                        int i = 0;
                        int imax = 0;
                        double maxDecisionProb = Double.MinValue;
                        do
                        {
                            if (!Cities[edgeList[i].RightCity].Visited)
                            {
                                neighbourCount++;
                                ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                                double distance = edgeList[i].CityDistance;
                                distance = Math.Max(distance, 1.0);     // Distance can't be zero
                                double prob = Math.Abs((el.PheromoneLevel * Math.Pow(distance, -pheromoneInfluence)));
                                decisionMatrixRowTotals[cityIndex] += prob;
                                if (prob > maxDecisionProb)
                                {
                                    imax = i;
                                    maxDecisionProb = prob;
                                }
                            }
                            i++;
                        } while ((neighbourCount < neighbourhoodSize) && (i < (GridSize - 1)));

                        // Determine next city to visit according to the decision matrix
                        double randVal = rand.NextDouble();

                        if (randVal <= decisionProbabilityThreshold)
                        {
                            // Deterministic decision
                            c1 = Cities[edgeList[imax].RightCity];

                            cityIndex = c1.Index;

                            c1.Visited = true;

                            route[antID][routeCount++] = edgeList[imax];

                            routeLength[antID] += edgeList[imax].CityDistance;

                        }
                        else
                        {
                            double decisionSum = 0.0;
                            randVal = rand.NextDouble();
                            int edgeCount = 0;
                            while ((randVal > decisionSum) && (edgeCount < (GridSize - 1)))
                            {

                                ACOEdgeLabels el = (ACOEdgeLabels)edgeList[edgeCount].EdgeValues;

                                if (!(Cities[edgeList[edgeCount].RightCity].Visited))
                                {
                                    double distance = edgeList[edgeCount].CityDistance;

                                    distance = Math.Max(distance, 1.0);     // Distance can't be zero

                                    double decisionProb = Math.Abs((el.PheromoneLevel * Math.Pow(distance, -pheromoneInfluence)));

                                    decisionProb /= decisionMatrixRowTotals[cityIndex];

                                    decisionSum += decisionProb;

                                    if (randVal <= decisionSum)
                                    {
                                        c1 = Cities[edgeList[edgeCount].RightCity];

                                        cityIndex = c1.Index;

                                        c1.Visited = true;

                                        route[antID][routeCount++] = edgeList[edgeCount];

                                        routeLength[antID] += edgeList[edgeCount].CityDistance;
                                    }
                                }

                                edgeCount++;
                            }
                        }

                    } while (routeCount < (GridSize - 1));

                    // Add length back to starting city
                    routeLength[antID] += (new EdgeStruct(c1, c)).CityDistance;

                    totalRouteLength += routeLength[antID];

                    // Copy route into the optimum route if it has a smaller route length
                    if (routeLength[antID] < OptimumRouteLength)
                    {
                        OptimumRouteLength = routeLength[antID];

                        // Update references into the adjacency list
                        for (int i = 0; i < GridSize - 1; i++)
                            optimumRouteRefs[i] = route[antID][i];

                        OptimumRoute[0] = Cities[route[antID][0].LeftCity];
                        for (int i = 1; i < GridSize; i++)
                            OptimumRoute[i] = Cities[route[antID][i - 1].RightCity];

                        // Fire route change event
                        fireOptimumRouteChangeEvent();
                    }
                    
                    foreach (City c2 in Cities)
                        c2.Visited = false;

                }

                // Evaporate the pheremone for every edge
                foreach (City c in Cities)
                {
                    int cityIndex = c.Index;
                    EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                    for (int i = 0; i < (GridSize - 1); i++)
                    {
                        ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                        el.PheromoneLevel *= (1.0 - evaporationRate);

                        if (el.PheromoneLevel < initialPheromoneLevel)
                            el.PheromoneLevel = initialPheromoneLevel;
                    }
                }

                // Evaluate the pheremone constant for the first iteration
                if (t == 0)
                {
                    double averageRouteLength = totalRouteLength / numberOfAnts;       // Average route length for evaluating pheremone normalizing constant

                    // Pheremone normalizing constant
                    pheremoneConstant = GridSize * GridSize * averageRouteLength * initialPheromoneLevel * 50.0 / maxIterations;

                }

                // Update the pheremonelevels on the optimum route
                for (int i = 0; i < (GridSize - 1); i++)
                {
                    ACOEdgeLabels el = (ACOEdgeLabels)optimumRouteRefs[i].EdgeValues;
                    el.PheromoneLevel += (pheremoneConstant / OptimumRouteLength);
                }

            }   // Next iteration
        }
    }

    public class TSPACOSolverV3 : TSPACOSolverV2
    {
        private Boolean triangleInequalitySearch(City[] optimumRoute, ref double optimumRouteLength)
        {
            // Local optimisation based on triangle inequality
            List<int> indexList=new List<int>{};

            for (int j = 0; j < GridSize; j++)
                indexList.Add(j);

            City[] route = new City[GridSize];
         
            for (int i = 1; i < GridSize - 1; i++)
            {
                // Consider the removing city at index i and re-inserting
                
                // Compute change to route length 
                double routeLengthChange = (new EdgeStruct(optimumRoute[i - 1], optimumRoute[i+1])).CityDistance;
                routeLengthChange -= (new EdgeStruct(optimumRoute[i], optimumRoute[i - 1])).CityDistance;
                routeLengthChange -= (new EdgeStruct(optimumRoute[i+1], optimumRoute[i])).CityDistance;

                if (routeLengthChange > 0)
                {
                    // Triangle inequality not valid
                    return false;
                }

                for (int j = 0; j < GridSize -1 ; j++)
                {
                    if ((j != (i - 1)) && (j != i))
                    {
                        double newRouteLengthChange = (new EdgeStruct(optimumRoute[j], optimumRoute[i])).CityDistance;
                        newRouteLengthChange += (new EdgeStruct(optimumRoute[i], optimumRoute[j+1])).CityDistance;
                        newRouteLengthChange -= (new EdgeStruct(optimumRoute[j], optimumRoute[j + 1])).CityDistance;

                        if (newRouteLengthChange < 0)
                        {
                            // Triangle inequality not valid
                            return false;
                        }

                        if ((routeLengthChange+newRouteLengthChange)<0)
                        {
                            optimumRouteLength += (routeLengthChange + newRouteLengthChange);

                            if (i > j)
                            {
                                indexList.Remove(i);
                                indexList.Insert(j+1, i);
                            }
                            else if (i < j)
                            {
                                indexList.Remove(i);
                                indexList.Insert(j, i);
                            }

                            for (int k = 0; k < GridSize; k++)
                                route[k] = optimumRoute[indexList[k]];

                            for (int k = 0; k < GridSize; k++)
                                optimumRoute[k] = route[k];

                           return true;

                        }
                    }

                }
            }

            return false;

        }


        private Boolean opt3Search(City[] optimumRoute, ref double optimumRouteLength)
        {
           
            // Consider all permutations of the 3 cities starting from index i
            int []targetIndices = new int[3];
            Boolean routeChanged = false;
            for (int i0 = 1; i0 < GridSize - 5; i0++)
                for (int i1 = i0 + 2; i1 < GridSize - 3; i1++)
                    if (i1 > i0 + 1)    
                        for (int i2 = i1 + 2; i2 < GridSize - 1; i2++)
                            if (i2 > i1 + 1)
                            {
                                targetIndices[0] = i0; targetIndices[1] = i1; targetIndices[2] = i2;
                                for (int ip0 = 0; ip0 < 3; ip0++)
                                    for (int ip1 = 0; ip1 < 3; ip1++)
                                        if (ip0 != ip1)
                                            for (int ip2 = 0; ip2 < 3; ip2++)
                                            {
                                                if ((ip2 != ip0) && (ip2 != ip1))
                                                {
                                                    // Compute partial route length for the 3 cities starting from index i
                                                    double routeLength = (new EdgeStruct(optimumRoute[i0 - 1], optimumRoute[i0])).CityDistance;
                                                    routeLength += (new EdgeStruct(optimumRoute[i0], optimumRoute[i0 + 1])).CityDistance;

                                                    routeLength += (new EdgeStruct(optimumRoute[i1 - 1], optimumRoute[i1])).CityDistance;
                                                    routeLength += (new EdgeStruct(optimumRoute[i1], optimumRoute[i1 + 1])).CityDistance;

                                                    routeLength += (new EdgeStruct(optimumRoute[i2 - 1], optimumRoute[i2])).CityDistance;
                                                    routeLength += (new EdgeStruct(optimumRoute[i2], optimumRoute[i2 + 1])).CityDistance;


                                                    // Compute partial route length for permutation
                                                    int ii0 = targetIndices[ip0];
                                                    int ii1 = targetIndices[ip1];
                                                    int ii2 = targetIndices[ip2];

                                                    double permutedRouteLength = (new EdgeStruct(optimumRoute[i0 - 1], optimumRoute[ii0])).CityDistance;
                                                    permutedRouteLength += (new EdgeStruct(optimumRoute[ii0], optimumRoute[i0 + 1])).CityDistance;

                                                    permutedRouteLength += (new EdgeStruct(optimumRoute[i1 - 1], optimumRoute[ii1])).CityDistance;
                                                    permutedRouteLength += (new EdgeStruct(optimumRoute[ii1], optimumRoute[i1 + 1])).CityDistance;

                                                    permutedRouteLength += (new EdgeStruct(optimumRoute[i2 - 1], optimumRoute[ii2])).CityDistance;
                                                    permutedRouteLength += (new EdgeStruct(optimumRoute[ii2], optimumRoute[i2 + 1])).CityDistance;

                                                    if (permutedRouteLength < routeLength)
                                                    {
                                                        // Update the optimum route
                                                        City c1 = optimumRoute[ii0];
                                                        City c2 = optimumRoute[ii1];
                                                        City c3 = optimumRoute[ii2];
                                                        optimumRoute[i0] = c1;
                                                        optimumRoute[i1] = c2;
                                                        optimumRoute[i2] = c3;

                                                        optimumRouteLength += (permutedRouteLength - routeLength);

                                                        routeChanged = true;

                                                    }
                                                }

                                            }
                            }

            return routeChanged;

        }


        public TSPACOSolverV3(TSPGrid g)
            : base(g)
        {
            // Give default parameter values
            numberOfAnts = GridSize;
            pheromoneInfluence = 7.0;
            evaporationRate = 0.5;
            maxIterations = 3000;
            neighbourhoodSize = 10;   // Consider all possible cities in the neighbourhood
        }

        public TSPACOSolverV3(TSPGrid g, int _numberOfAnts, int _maxIterations, double _pheromoneInfluence, double _evaporationRate,
            int _neighbourhoodSize)
            : base(g, _numberOfAnts, _maxIterations, _pheromoneInfluence, _evaporationRate, _neighbourhoodSize)
        {}

        public override void solve()
        {
            Random rand = new Random();

            OptimumRouteLength = Double.MaxValue;

            EdgeStruct[][] route = new EdgeStruct[numberOfAnts][];

            for (int i = 0; i < numberOfAnts; i++)
                route[i] = new EdgeStruct[GridSize - 1];

            double[] routeLength = new double[numberOfAnts];

            double[] decisionMatrixRowTotals = new double[GridSize];       // For normalizing the decision matrix probabilities

            for (int i = 0; i < GridSize; i++)
                decisionMatrixRowTotals[i] = 0.0;

            // Initialize the ACO edge label information on each edge 
            foreach (City c in Cities)
            {
                c.Visited = false;
                int cityIndex = c.Index;

                EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                // Normalize the decision matrix probality totals
                for (int i = 0; i < (GridSize - 1); i++)
                {
                    edgeList[i].EdgeValues = new ACOEdgeLabels();
                    ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                    el.PheromoneLevel = initialPheromoneLevel;
                    double distance = edgeList[i].CityDistance;
                    distance = Math.Max(1.0, distance);
                    decisionMatrixRowTotals[cityIndex] += (initialPheromoneLevel * Math.Pow(distance, -pheromoneInfluence));
                }
            }


            // Iterate a fixed number of times and return the best solution
            EdgeStruct[] optimumRouteRefs = new EdgeStruct[GridSize - 1];   // References adjacency list EdgeStruct elements
            double decisionProbabilityThreshold;
            Boolean routeUpdate;
            Boolean locSearch = false;
            int localOptRoutelengthReduction = 0;
            int t0 = maxIterations/2; // Time to initiate local search
            for (int t = 0; t < maxIterations; t++)
            {
                fireProgressReportEvent(100.0 * t / maxIterations);

                decisionProbabilityThreshold = (double)t / (double)maxIterations;

                // For each ant, perform a random tour and deposit pheromone
                double totalRouteLength = 0.0;
                routeUpdate = false;
                for (int antID = 0; antID < numberOfAnts; antID++)
                {
                    int cityStartIndex = antID;

                    City c = Cities[cityStartIndex];

                    c.Visited = true;

                    int routeCount = 0;

                    routeLength[antID] = 0.0;

                    City c1 = c;

                    do
                    {

                        int cityIndex = c1.Index;

                        EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                        // Re-normalize the decision matrix row probality totals
                        decisionMatrixRowTotals[cityIndex] = 0.0;
                        int neighbourCount = 0;
                        int i = 0;
                        int imax = 0;
                        double maxDecisionProb = Double.MinValue;
                        do
                        {
                            if (!Cities[edgeList[i].RightCity].Visited)
                            {
                                neighbourCount++;
                                ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                                double distance = edgeList[i].CityDistance;

                                distance = Math.Max(distance, 1.0);     // Distance can't be zero

                                double prob = Math.Abs((el.PheromoneLevel * Math.Pow(distance, -pheromoneInfluence)));
                          
                                decisionMatrixRowTotals[cityIndex] += prob;

                                
                                if (prob > maxDecisionProb)
                                {
                                    imax = i;
                                    maxDecisionProb = prob;
                                }
                            }
                            i++;
                        } while ((neighbourCount < neighbourhoodSize) && (i < (GridSize - 1)));

 
                        // Determine next city to visit according to the decision matrix
                        double randVal = rand.NextDouble();

                        if (randVal <= decisionProbabilityThreshold)
                        {
                            // Deterministic decision
                            c1 = Cities[edgeList[imax].RightCity];

                            cityIndex = c1.Index;

                            c1.Visited = true;

                            route[antID][routeCount++] = edgeList[imax];

                            routeLength[antID] += edgeList[imax].CityDistance;

                        }
                        else
                        {
                            double decisionSum = 0.0;
                            randVal = rand.NextDouble();

                            int edgeCount = 0;

  
                            while ((randVal > decisionSum) && (edgeCount < (GridSize - 1)))
                            {

                                ACOEdgeLabels el = (ACOEdgeLabels)edgeList[edgeCount].EdgeValues;

                                if (!(Cities[edgeList[edgeCount].RightCity].Visited))
                                {
                                    double distance = edgeList[edgeCount].CityDistance;

                                    distance = Math.Max(distance, 1.0);     // Distance can't be zero

                                    double decisionProb = Math.Abs((el.PheromoneLevel * Math.Pow(distance, -pheromoneInfluence)));
                                                                        
                                    decisionProb /= decisionMatrixRowTotals[cityIndex];
                                    
                                    decisionSum += decisionProb;

                                    if (randVal <= decisionSum)
                                    {
                                        c1 = Cities[edgeList[edgeCount].RightCity];

                                        cityIndex = c1.Index;

                                        c1.Visited = true;

                                        route[antID][routeCount++] = edgeList[edgeCount];

                                        routeLength[antID] += edgeList[edgeCount].CityDistance;
                                    }
                                }

                                edgeCount++;
                            }
   
                        }

                    } while (routeCount < (GridSize - 1));

                    // Add length back to starting city
                    routeLength[antID] += (new EdgeStruct(c1, c)).CityDistance;

                    totalRouteLength += routeLength[antID];

                    // Copy route into the optimum route if it has a smaller route length
                    if (routeLength[antID] < OptimumRouteLength)
                    {
                        OptimumRouteLength = routeLength[antID];

                        // Update references into the adjacency list
                        for (int i = 0; i < GridSize - 1; i++)
                            optimumRouteRefs[i] = route[antID][i];

                        OptimumRoute[0] = Cities[route[antID][0].LeftCity];
                        for (int i = 1; i < GridSize; i++)
                            OptimumRoute[i] = Cities[route[antID][i - 1].RightCity];

                        // Fire route change event
                        fireOptimumRouteChangeEvent();
                        routeUpdate = true;
                    }

                    foreach (City c2 in Cities)
                        c2.Visited = false;
                }

                // Evaporate the pheremone for every edge
                foreach (City c in Cities)
                {
                    int cityIndex = c.Index;
                    EdgeStruct[] edgeList = Grid.AdjacencyArray[cityIndex];

                    for (int i = 0; i < (GridSize - 1); i++)
                    {
                        ACOEdgeLabels el = (ACOEdgeLabels)edgeList[i].EdgeValues;
                        el.PheromoneLevel *= (1.0 - evaporationRate);

                        if (el.PheromoneLevel < initialPheromoneLevel)
                            el.PheromoneLevel = initialPheromoneLevel;
                    }
                }

                // Evaluate the pheremone constant for the first iteration
                if (t == 0)
                {
                    double averageRouteLength = totalRouteLength / numberOfAnts;       // Average route length for evaluating pheremone normalizing constant

                    pheremoneConstant = GridSize * GridSize * averageRouteLength * initialPheromoneLevel * 50.0 / maxIterations;

                }


                // Implement local search on the optimum route at t=t0 and after that following a route update
                if (t == t0)
                    locSearch = true;
                else if ((t > t0) && (!locSearch))
                    locSearch = routeUpdate;

                if (locSearch)
                {
                    double oldOptRouteLength = OptimumRouteLength;
                    double optRouteLength = OptimumRouteLength;
                    locSearch = triangleInequalitySearch(OptimumRoute, ref optRouteLength);
                    OptimumRouteLength = optRouteLength;

                    if (locSearch)
                    {
                        localOptRoutelengthReduction += (int)(oldOptRouteLength - OptimumRouteLength);
                        
                        fireStatusReportEvent("(t= " + t + "),  " + localOptRoutelengthReduction);
                        
                        fireOptimumRouteChangeEvent();

                        // Update the pheremone levels on the optimum route
                        int cityIndexL, cityIndexR;
                        EdgeStruct[] edgeList1;
                        for (int i = 0; i < GridSize - 2; i++)
                        {
                            cityIndexL = OptimumRoute[i].Index;
                            cityIndexR = OptimumRoute[i + 1].Index;
                            edgeList1 = Grid.AdjacencyArray[cityIndexL];
                            for (int j = 0; j < GridSize - 1; j++)
                            {
                                if ((edgeList1[j].LeftCity == cityIndexL) && (edgeList1[j].RightCity == cityIndexR))
                                {
                                    optimumRouteRefs[i] = edgeList1[j];
                                }
                            }
                        }

                        cityIndexL = OptimumRoute[GridSize - 1].Index;
                        cityIndexR = OptimumRoute[0].Index;
                        edgeList1 = Grid.AdjacencyArray[cityIndexL];
                        for (int j = 0; j < GridSize - 1; j++)
                        {
                            if ((edgeList1[j].LeftCity == cityIndexL) && (edgeList1[j].RightCity == cityIndexR))
                            {
                                optimumRouteRefs[GridSize - 2] = edgeList1[j];
                            }
                        }   
                    }
                }

                // Update the pheremonelevels on the optimum route
                for (int i = 0; i < (GridSize - 1); i++)
                {
                    ACOEdgeLabels el = (ACOEdgeLabels)optimumRouteRefs[i].EdgeValues;
                    el.PheromoneLevel += (pheremoneConstant / OptimumRouteLength);
                }

            }   // Next iteration

            return;
        }
    }
 }