G2A Many GEOs
SHARE
TWEET

Untitled

a guest Apr 7th, 2020 174 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Collections.Immutable;
  4. using System.Linq;
  5. using ASD.Graphs;
  6.  
  7. namespace Lab05
  8. {
  9.     public class PathFinder : System.MarshalByRefObject
  10.     {
  11.         private class DijkstraK
  12.         {
  13.             public Int32 LastVertex { get; set; }
  14.             public Double Cost { get; set; }
  15.             public LinkedListNode<Edge> History { get; set; }
  16.         }
  17.  
  18.         private class LinkedListNode<T>
  19.         {
  20.             public T Element { get; set; }
  21.             public LinkedListNode<T> Previous { get; set; }
  22.         }
  23.  
  24.         public (Edge[] edges, Double? sum) KShortestPathDijkstra(Graph g, int start, int end, int k)
  25.         {
  26.             var paths = new List<(LinkedListNode<Edge>, Double)>();
  27.             var pathCounts = new Int32[g.VerticesCount];
  28.  
  29.             var priorityQueue = new PriorityQueue<DijkstraK, Double>((x1, x2) => x1.Value < x2.Value);
  30.             priorityQueue.Put(new DijkstraK
  31.             {
  32.                 LastVertex = start,
  33.                 History = null
  34.             }, 0);
  35.  
  36.             while (!priorityQueue.Empty && pathCounts[end] < k)
  37.             {
  38.                 var puCost = priorityQueue.BestPriority();
  39.                 var pu = priorityQueue.Get();
  40.                 var u = pu.LastVertex;
  41.                 pathCounts[u] += 1;
  42.  
  43.                 if (u == end)
  44.                 {
  45.                     paths.Add((pu.History, pu.Cost));
  46.                     continue;
  47.                 }
  48.  
  49.                 if (pathCounts[u] <= k)
  50.                 {
  51.                     foreach (var edge in g.OutEdges(u))
  52.                     {
  53.                         var pvCost = puCost + edge.Weight;
  54.                         priorityQueue.Put(new DijkstraK
  55.                         {
  56.                             LastVertex = edge.To,
  57.                             Cost = pvCost,
  58.                             History = new LinkedListNode<Edge>
  59.                             {
  60.                                 Element = edge,
  61.                                 Previous = pu.History
  62.                             }
  63.                         }, pvCost);
  64.                     }
  65.                 }
  66.             }
  67.  
  68.             if (paths.Count < k)
  69.             {
  70.                 return (null, null);
  71.             }
  72.  
  73.             var (pointer, cost) = paths[k - 1];
  74.             var tmp = new LinkedList<Edge>();
  75.             while (pointer != null)
  76.             {
  77.                 tmp.AddFirst(pointer.Element);
  78.                 pointer = pointer.Previous;
  79.             }
  80.             var path = tmp.ToArray();
  81.             return (path, cost);
  82.         }
  83.  
  84.         public (Edge[] edges, Double? sum) ShortestPathDijkstra(Graph g, int start, int end) =>
  85.             KShortestPathDijkstra(g, start, end, 1);
  86.  
  87.         /// <summary>
  88.         /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
  89.         /// 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).
  90.         /// Dopuszczamy, aby na ścieżce powtarzały się wierzchołki i/lub krawędzie.
  91.         /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
  92.         /// </summary>
  93.         /// <remarks>
  94.         /// Wymagana złożoność do O(D), gdzie D jest złożonością implementacji alogorytmu Dijkstry w bibliotece Graph.
  95.         /// </remarks>
  96.         /// <param name="g">badany graf</param>
  97.         /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
  98.         /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość znalezionej ścieżki</returns>
  99.         public double? FindSecondShortestPath(Graph g, int a, int b, out Edge[] path)
  100.         {
  101.             var (shortestPath, cost) = KShortestPathDijkstra(g, a, b, 2);
  102.             path = shortestPath;
  103.             return cost;
  104.         }
  105.  
  106.         /// <summary>
  107.         /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
  108.         /// 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).
  109.         /// Wymagamy, aby na ścieżce nie było powtórzeń wierzchołków ani krawędzi.
  110.         /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
  111.         /// </summary>
  112.         /// <remarks>
  113.         /// Wymagana złożoność to O(nD), gdzie D jest złożonością implementacji algorytmu Dijkstry w bibliotece Graph.
  114.         /// </remarks>
  115.         /// <param name="g">badany graf</param>
  116.         /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
  117.         /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość tej ścieżki</returns>
  118.         public double? FindSecondSimpleShortestPath(Graph g, int a, int b, out Edge[] path)
  119.         {
  120.             Edge[] bestCandidate = null;
  121.             Double? bestCanditateCost = Double.PositiveInfinity;
  122.  
  123.             var (shortestPath, cost) = ShortestPathDijkstra(g, a, b);
  124.             if (shortestPath == null)
  125.             {
  126.                 path = null;
  127.                 return null;
  128.             }
  129.  
  130.             Double commonPathCost = 0;
  131.             for (var i = 0; i < shortestPath.Length; i++)
  132.             {
  133.                 var edge = shortestPath[i];
  134.                 var rootNode = edge.From;
  135.                 g.DelEdge(edge.From, edge.To);
  136.                 var (pathProposition, pathPropositionCost) = ShortestPathDijkstra(g, rootNode, b); // Ścieżka od {rootNode} do {b}
  137.                 if (pathProposition != null && commonPathCost + pathPropositionCost < bestCanditateCost)
  138.                 {
  139.                     bestCanditateCost = commonPathCost + pathPropositionCost;
  140.                     bestCandidate = new Edge[i + pathProposition.Length];
  141.                     Array.Copy(shortestPath, bestCandidate, i);
  142.                     pathProposition.CopyTo(bestCandidate, i);
  143.                 }
  144.                 g.AddEdge(edge.From, edge.To, edge.Weight);
  145.  
  146.                 commonPathCost += edge.Weight;
  147.             }
  148.  
  149.             path = bestCandidate;
  150.             return bestCanditateCost == Double.PositiveInfinity ? null : bestCanditateCost;
  151.         }
  152.     }
  153. }
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