Fuja

using ASD.Graphs;
using System;
using System.Collections.Generic;

namespace Lab05
{

public class PathFinder : System.MarshalByRefObject
    {

    /// <summary>
    /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
    /// Możliwe, że jej długość jest równa najkrótszej (jeśli są dwie najkrótsze ścieżki, algorytm zwróci jedną z nich).
    /// Dopuszczamy, aby na ścieżce powtarzały się wierzchołki i/lub krawędzie.
    /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
    /// </summary>
    /// <remarks>
    /// Wymagana złożoność do O(D), gdzie D jest złożonością implementacji alogorytmu Dijkstry w bibliotece Graph.
    /// </remarks>
    /// <param name="g">badany graf</param>
    /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
    /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość znalezionej ścieżki</returns>
    public double? FindSecondShortestPath(Graph g, int a, int b, out Edge[] path)
        {
            PathsInfo[] pathsInfo, pathsInfo_copy = null;       // wynik Dijkstry dla grafu g i g_copy
            path = null;
            List<Edge> shortestPath = new List<Edge>();         // najkrotsza sciezka
            List<Edge> second_shortestPath = new List<Edge>();  // druga najkrotsza sciezka
            Graph g_reversed = null;
            Graph g_copy = null;

            g_copy = g.Clone();                                 // kopia grafu g
            foreach (Edge e in g_copy.OutEdges(b))              // usuwamy wierzchołek b z grafu g_copy
                g_copy.DelEdge(e);

            if (g.Directed)
            {
                Graph g_copy_reversed = g_copy.Reverse();
                foreach (Edge e in g_copy_reversed.OutEdges(b))
                    g_copy.DelEdge(e.To, e.From);
            }

            ShortestPathsGraphExtender.DijkstraShortestPaths(g_copy, a, out pathsInfo_copy);

            if (!ShortestPathsGraphExtender.DijkstraShortestPaths(g, a, out pathsInfo))             // zwykle odleglosci
                return null;

            if (GraphHelperExtender.IsNaN(pathsInfo[b].Dist))                                       // sprawdzenie czy istnieje najkrotsza sciezka
                return null;

            int w = b;
            while (w != a)                                       // tworzymy najkrosza sciezke z a do b
            {
                shortestPath.Add((Edge)pathsInfo[w].Last);
                w = ((Edge)pathsInfo[w].Last).From;
            }

            //Edge[] shpa = PathsInfo.ConstructPath(a, b, pathsInfo);



            double weight_sum = 0;                              // chwilowa suma wag do pewnego momentu najkrotszej sciezki
            double min_weight = Double.MaxValue;                // dlugosc drugiej najkrotszej sciezki
            Edge min_neighbour = new Edge();                    // krawedz przy ktorej schodzimy z najkrotszej sciezki


            if(g.Directed)                                      // dla grafu skierowanego
            {
                g_reversed = g.Reverse();

                for (int i = 0; i < shortestPath.Count; i++)
                {
                    foreach (Edge e in g_reversed.OutEdges(shortestPath[i].To))
                    {
                        if (e.To != shortestPath[i].From)
                        {
                            double local_weight = weight_sum + e.Weight + pathsInfo_copy[e.To].Dist;
                            if (local_weight < min_weight)
                            {
                                min_weight = local_weight;
                                min_neighbour = e;

                                if (min_weight == pathsInfo[b].Dist)
                                    break;
                            }
                        }
                    }

                    if (i == shortestPath.Count - 1)
                    {
                        foreach (Edge e in g_reversed.OutEdges(shortestPath[i].From))
                        {
                            double local_weight = weight_sum + shortestPath[shortestPath.Count - 1].Weight + e.Weight + pathsInfo_copy[e.To].Dist;

                            if (local_weight < min_weight)
                            {
                                min_weight = local_weight;
                                min_neighbour = e;

                                if (min_weight == pathsInfo[b].Dist)
                                    break;
                            }
                        }
                    }

                    if (min_weight == pathsInfo[b].Dist)
                        break;
                    weight_sum += shortestPath[i].Weight;
                }
            }
            else                                                // dla grafu nieskierowanego
            {
                for (int i = 0; i < shortestPath.Count; i++)
                {
                    foreach (Edge e in g.OutEdges(shortestPath[i].To))
                    {
                        if (i == 0)
                        {
                            if (e.To != shortestPath[i].From)
                            {
                                double local_weight = weight_sum + e.Weight + pathsInfo_copy[e.To].Dist;

                                if (local_weight < min_weight)
                                {
                                    min_weight = local_weight;
                                    min_neighbour = e;
                                }
                            }
                        }
                        else if (e.To != shortestPath[i - 1].To && e.To != b)
                        {
                            double local_weight = weight_sum + e.Weight + pathsInfo_copy[e.To].Dist;
                            if (e.To == shortestPath[i].From)
                                local_weight += 2 * e.Weight;

                            if (local_weight < min_weight)
                            {
                                min_weight = local_weight;
                                min_neighbour = e;
                            }
                        }

                        if (min_weight == pathsInfo[b].Dist)
                            break;
                    }

                    if (i == shortestPath.Count - 1)
                    {
                        foreach (Edge e in g.OutEdges(shortestPath[i].From))
                        {
                            double local_weight = weight_sum + shortestPath[shortestPath.Count - 1].Weight + e.Weight + pathsInfo_copy[e.To].Dist;

                            if (local_weight < min_weight)
                            {
                                min_weight = local_weight;
                                min_neighbour = e;

                                if (min_weight == pathsInfo[b].Dist)
                                    break;
                            }
                        }
                    }

                    if (min_weight == pathsInfo[b].Dist)
                        break;

                    weight_sum += shortestPath[i].Weight;
                }
            }

           if (min_weight == Double.MaxValue)
              return null;

            w = b;
            while (w != min_neighbour.From)
            {
                second_shortestPath.Add((Edge)pathsInfo[w].Last);
                w = ((Edge)pathsInfo[w].Last).From;
            }

            second_shortestPath.Add(new Edge(min_neighbour.To, min_neighbour.From, min_neighbour.Weight));

            if(shortestPath.Contains(min_neighbour) || shortestPath.Contains(new Edge(min_neighbour.To, min_neighbour.From, min_neighbour.Weight)))
            {
                second_shortestPath.Add(min_neighbour);
                second_shortestPath.Add(new Edge(min_neighbour.To, min_neighbour.From, min_neighbour.Weight));
            }

            w = min_neighbour.To;
            while (w != a)
            {
                second_shortestPath.Add((Edge)pathsInfo_copy[w].Last);
                w = ((Edge)pathsInfo_copy[w].Last).From;
            }

            second_shortestPath.Reverse();
            path = second_shortestPath.ToArray();

            return min_weight;
        }

    /// <summary>
    /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
    /// Możliwe, że jej długość jest równa najkrótszej (jeśli są dwie najkrótsze ścieżki, algorytm zwróci jedną z nich).
    /// Wymagamy, aby na ścieżce nie było powtórzeń wierzchołków ani krawędzi.
    /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
    /// </summary>
    /// <remarks>
    /// Wymagana złożoność to O(nD), gdzie D jest złożonością implementacji algorytmu Dijkstry w bibliotece Graph.
    /// </remarks>
    /// <param name="g">badany graf</param>
    /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
    /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość tej ścieżki</returns>
    public double? FindSecondSimpleShortestPath(Graph g, int a, int b, out Edge[] path)
        {
            path = null;
            return -1;

        }

    }

}