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

namespace DrawGraph
{
    public class Algorithm
    {
        private static int MinDistance(int[] path, bool[] includedToPath, int n)
        {
            // Initialize min value 
            int min = int.MaxValue, min_index = -1;

            for (int v = 0; v < n; v++)
                if (includedToPath[v] == false && path[v] <= min)
                {
                    min = path[v];
                    min_index = v;
                }

            return min_index;
        }

        public static int DijkstraCount(int[,] adjacencyMatrix, int startIndex, int finishIndex)
        {
            int n = adjacencyMatrix.GetLength(0);
            int[] path = new int[n];

            bool[] includedToShortestPath = new bool[n];

            for (int i = 0; i < n; i++)
            {
                path[i] = int.MaxValue;
                includedToShortestPath[i] = false;
            }

            path[startIndex] = 0;

            for (int i = 0; i < n - 1; i++)
            {
                int min = MinDistance(path, includedToShortestPath, n);

                includedToShortestPath[min] = true;

                for (int j = 0; j < n; j++)
                {
                    if (!includedToShortestPath[j] && adjacencyMatrix[min, j] != 0 &&
                        path[min] + adjacencyMatrix[min, j] < path[j])
                    {
                        path[j] = path[min] + adjacencyMatrix[min, j];
                    }
                }
            }

            return path[finishIndex];
        }
        
        public static LinkedList<Node> DepthSearch(Node[] node, Edge[] edge, int sourceIndex, int targetIndex)
        {
            var visited = new HashSet<Node>();
            var path = new LinkedList<Node>();
            Dfs(node[sourceIndex], node[targetIndex], visited, path, edge);
            if (path.Count > 0)
                path.AddFirst(node[sourceIndex]);
            return path;
        }

        private static bool Dfs(Node node, Node goal,HashSet<Node> visited, LinkedList<Node> path, Edge[] edges)
        {
            if (Node.Compare(node, goal))
                return true;

            visited.Add(node);
            foreach(var edge in edges.Where(x=>!visited.Contains(x.SourceNode) || !visited.Contains(x.TargetNode)))
            {
                if(Dfs(edge.TargetNode, goal, visited, path, edges))
                {
                    path.AddFirst(edge.TargetNode);
                    return true;
                }
            }
            return false;
        }
    }
}