using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using U.Graph;

namespace Algorithms.Nw.ShortestPath
{
    public abstract class ShortestPathAlgorithm : Algorithm
    {
        internal double[] d;
        internal int[] p;
        
        
        // ABSTRACT
        public abstract void run(Graph graph, SubGraph subGraph, int s, int t, bool keepTime);

        
        // GETTERS
        public double[] getDistanceVector() { return this.d; }
        public int[] getPredecessorVector() { return this.p; }
        public List<int> getShortestPathAsNodeIndices(int s, int t)
        {
            int i = t;
            List<int> nodeIndices = new List<int>() { i };
            while (i != s)
            {
                i = p[i];
                if (i == -1) { return null; }
                nodeIndices.Add(i);
            }
            nodeIndices.Reverse();
            return nodeIndices;
        }
        public List<int> getShortestPathAsArcIndices(Graph graph, int s, int t)
        {
            int[,] I = graph.getIncidenceMatrix();
            int j = t;
            List<int> edgeIndices = new List<int>();
            while (j != s)
            {
                int i = p[j];
                if (j == -1) { return null; }
                int e = I[i, j];
                edgeIndices.Add(e);
                j = i;
            }
            edgeIndices.Reverse();
            return edgeIndices;
        }

        // DISPOSE
        public void dispose()
        {
            Array.Clear(this.d, 0, this.d.Length); this.d = null;
            Array.Clear(this.p, 0, this.p.Length); this.p = null;
        }

    }
}
