Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Fuja

a guest Apr 7th, 2020 152 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. using ASD.Graphs;
  3. using System;
  4. using System.Collections.Generic;
  5.  
  6. namespace Lab05
  7. {
  8.  
  9. public class PathFinder : System.MarshalByRefObject
  10.     {
  11.  
  12.     /// <summary>
  13.     /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
  14.     /// 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).
  15.     /// Dopuszczamy, aby na ścieżce powtarzały się wierzchołki i/lub krawędzie.
  16.     /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
  17.     /// </summary>
  18.     /// <remarks>
  19.     /// Wymagana złożoność do O(D), gdzie D jest złożonością implementacji alogorytmu Dijkstry w bibliotece Graph.
  20.     /// </remarks>
  21.     /// <param name="g">badany graf</param>
  22.     /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
  23.     /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość znalezionej ścieżki</returns>
  24.     public double? FindSecondShortestPath(Graph g, int a, int b, out Edge[] path)
  25.         {
  26.             PathsInfo[] pathsInfo, pathsInfo_copy = null;       // wynik Dijkstry dla grafu g i g_copy
  27.             path = null;
  28.             List<Edge> shortestPath = new List<Edge>();         // najkrotsza sciezka
  29.             List<Edge> second_shortestPath = new List<Edge>();  // druga najkrotsza sciezka
  30.             Graph g_reversed = null;
  31.             Graph g_copy = null;
  32.  
  33.             g_copy = g.Clone();                                 // kopia grafu g
  34.             foreach (Edge e in g_copy.OutEdges(b))              // usuwamy wierzchołek b z grafu g_copy
  35.                 g_copy.DelEdge(e);
  36.  
  37.             if (g.Directed)
  38.             {
  39.                 Graph g_copy_reversed = g_copy.Reverse();
  40.                 foreach (Edge e in g_copy_reversed.OutEdges(b))
  41.                     g_copy.DelEdge(e.To, e.From);
  42.             }
  43.  
  44.             ShortestPathsGraphExtender.DijkstraShortestPaths(g_copy, a, out pathsInfo_copy);
  45.  
  46.             if (!ShortestPathsGraphExtender.DijkstraShortestPaths(g, a, out pathsInfo))             // zwykle odleglosci
  47.                 return null;
  48.  
  49.             if (GraphHelperExtender.IsNaN(pathsInfo[b].Dist))                                       // sprawdzenie czy istnieje najkrotsza sciezka
  50.                 return null;
  51.  
  52.             int w = b;
  53.             while (w != a)                                       // tworzymy najkrosza sciezke z a do b
  54.             {
  55.                 shortestPath.Add((Edge)pathsInfo[w].Last);
  56.                 w = ((Edge)pathsInfo[w].Last).From;
  57.             }
  58.  
  59.             //Edge[] shpa = PathsInfo.ConstructPath(a, b, pathsInfo);
  60.  
  61.  
  62.  
  63.             double weight_sum = 0;                              // chwilowa suma wag do pewnego momentu najkrotszej sciezki
  64.             double min_weight = Double.MaxValue;                // dlugosc drugiej najkrotszej sciezki
  65.             Edge min_neighbour = new Edge();                    // krawedz przy ktorej schodzimy z najkrotszej sciezki
  66.            
  67.            
  68.             if(g.Directed)                                      // dla grafu skierowanego
  69.             {
  70.                 g_reversed = g.Reverse();
  71.  
  72.                 for (int i = 0; i < shortestPath.Count; i++)
  73.                 {
  74.                     foreach (Edge e in g_reversed.OutEdges(shortestPath[i].To))
  75.                     {
  76.                         if (e.To != shortestPath[i].From)
  77.                         {
  78.                             double local_weight = weight_sum + e.Weight + pathsInfo_copy[e.To].Dist;
  79.                             if (local_weight < min_weight)
  80.                             {
  81.                                 min_weight = local_weight;
  82.                                 min_neighbour = e;
  83.  
  84.                                 if (min_weight == pathsInfo[b].Dist)
  85.                                     break;
  86.                             }
  87.                         }
  88.                     }
  89.  
  90.                     if (i == shortestPath.Count - 1)
  91.                     {
  92.                         foreach (Edge e in g_reversed.OutEdges(shortestPath[i].From))
  93.                         {
  94.                             double local_weight = weight_sum + shortestPath[shortestPath.Count - 1].Weight + e.Weight + pathsInfo_copy[e.To].Dist;
  95.  
  96.                             if (local_weight < min_weight)
  97.                             {
  98.                                 min_weight = local_weight;
  99.                                 min_neighbour = e;
  100.  
  101.                                 if (min_weight == pathsInfo[b].Dist)
  102.                                     break;
  103.                             }
  104.                         }
  105.                     }
  106.  
  107.                     if (min_weight == pathsInfo[b].Dist)
  108.                         break;
  109.                     weight_sum += shortestPath[i].Weight;
  110.                 }
  111.             }
  112.             else                                                // dla grafu nieskierowanego
  113.             {
  114.                 for (int i = 0; i < shortestPath.Count; i++)
  115.                 {
  116.                     foreach (Edge e in g.OutEdges(shortestPath[i].To))
  117.                     {
  118.                         if (i == 0)
  119.                         {
  120.                             if (e.To != shortestPath[i].From)
  121.                             {
  122.                                 double local_weight = weight_sum + e.Weight + pathsInfo_copy[e.To].Dist;
  123.  
  124.                                 if (local_weight < min_weight)
  125.                                 {
  126.                                     min_weight = local_weight;
  127.                                     min_neighbour = e;
  128.                                 }
  129.                             }
  130.                         }
  131.                         else if (e.To != shortestPath[i - 1].To && e.To != b)
  132.                         {
  133.                             double local_weight = weight_sum + e.Weight + pathsInfo_copy[e.To].Dist;
  134.                             if (e.To == shortestPath[i].From)
  135.                                 local_weight += 2 * e.Weight;
  136.  
  137.                             if (local_weight < min_weight)
  138.                             {
  139.                                 min_weight = local_weight;
  140.                                 min_neighbour = e;
  141.                             }
  142.                         }
  143.  
  144.                         if (min_weight == pathsInfo[b].Dist)
  145.                             break;
  146.                     }
  147.  
  148.                     if (i == shortestPath.Count - 1)
  149.                     {
  150.                         foreach (Edge e in g.OutEdges(shortestPath[i].From))
  151.                         {
  152.                             double local_weight = weight_sum + shortestPath[shortestPath.Count - 1].Weight + e.Weight + pathsInfo_copy[e.To].Dist;
  153.  
  154.                             if (local_weight < min_weight)
  155.                             {
  156.                                 min_weight = local_weight;
  157.                                 min_neighbour = e;
  158.  
  159.                                 if (min_weight == pathsInfo[b].Dist)
  160.                                     break;
  161.                             }
  162.                         }
  163.                     }
  164.  
  165.                     if (min_weight == pathsInfo[b].Dist)
  166.                         break;
  167.  
  168.                     weight_sum += shortestPath[i].Weight;
  169.                 }
  170.             }
  171.  
  172.            if (min_weight == Double.MaxValue)
  173.               return null;
  174.  
  175.             w = b;
  176.             while (w != min_neighbour.From)
  177.             {
  178.                 second_shortestPath.Add((Edge)pathsInfo[w].Last);
  179.                 w = ((Edge)pathsInfo[w].Last).From;
  180.             }
  181.  
  182.             second_shortestPath.Add(new Edge(min_neighbour.To, min_neighbour.From, min_neighbour.Weight));
  183.  
  184.             if(shortestPath.Contains(min_neighbour) || shortestPath.Contains(new Edge(min_neighbour.To, min_neighbour.From, min_neighbour.Weight)))
  185.             {
  186.                 second_shortestPath.Add(min_neighbour);
  187.                 second_shortestPath.Add(new Edge(min_neighbour.To, min_neighbour.From, min_neighbour.Weight));
  188.             }
  189.  
  190.             w = min_neighbour.To;
  191.             while (w != a)
  192.             {
  193.                 second_shortestPath.Add((Edge)pathsInfo_copy[w].Last);
  194.                 w = ((Edge)pathsInfo_copy[w].Last).From;
  195.             }
  196.  
  197.             second_shortestPath.Reverse();
  198.             path = second_shortestPath.ToArray();
  199.  
  200.             return min_weight;
  201.         }
  202.  
  203.     /// <summary>
  204.     /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
  205.     /// 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).
  206.     /// Wymagamy, aby na ścieżce nie było powtórzeń wierzchołków ani krawędzi.
  207.     /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
  208.     /// </summary>
  209.     /// <remarks>
  210.     /// Wymagana złożoność to O(nD), gdzie D jest złożonością implementacji algorytmu Dijkstry w bibliotece Graph.
  211.     /// </remarks>
  212.     /// <param name="g">badany graf</param>
  213.     /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
  214.     /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość tej ścieżki</returns>
  215.     public double? FindSecondSimpleShortestPath(Graph g, int a, int b, out Edge[] path)
  216.         {
  217.             path = null;
  218.             return -1;
  219.        
  220.         }
  221.  
  222.     }
  223.  
  224. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top