using Algorithms.Nw.ShortestPath;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using U.Graph;
using U.ListOperations;
using U.StringOperations;

namespace Algorithms.Nw.PathGeneration
{
    public class LinkElimination : PathGenerationAlgorithm
    {
        private ShortestPathAlgorithm spa;
        public LinkElimination(ShortestPathAlgorithm shortestPathAlgorithm) { this.spa = shortestPathAlgorithm; }


        public override void run(Graph graph, int oriIndex, int desIndex, int nbExistingPaths, int maxNbPaths, bool keepTime)
        {
            if (keepTime) { base.startTimer(); }
            base.lstNodeIndices = new List<List<int>>();
            if (nbExistingPaths >= maxNbPaths) { return; }
            int nbPathsToGenerate = maxNbPaths - nbExistingPaths;

            string str;
            SubGraph subGraph = new SubGraph(graph.getNbNodes());
            spa.run(graph, null, oriIndex, desIndex, false);
            List<int> sp = spa.getShortestPathAsNodeIndices(oriIndex, desIndex);
            int pathCount = 0;
            bool cs = (sp != null);
            if (cs)
            {
                subGraph.closePath(sp);
                str = Str.combine(sp, Str.Delimiter.Dash);
                if (!existingPathLabels.Contains(str))
                {
                    pathCount += 1;
                    base.lstNodeIndices.Add(UList.clone(sp));
                    addToExisting(str);
                }
            }
            while (cs && pathCount < nbPathsToGenerate)
            {
                spa.run(graph, subGraph, oriIndex, desIndex, false);
                sp = spa.getShortestPathAsNodeIndices(oriIndex, desIndex);
                cs = (sp != null);
                if (cs)
                {
                    subGraph.closePath(sp);
                    str = Str.combine(sp, Str.Delimiter.Dash);
                    if (!existingPathLabels.Contains(str))
                    {
                        pathCount += 1;
                        base.lstNodeIndices.Add(UList.clone(sp));
                        addToExisting(str);
                    }
                }
            }
            if (keepTime) { stopTimer(); }
        }
    }
}
