| | | 1 | | using MoreStructures.PriorityQueues; |
| | | 2 | | using MoreStructures.PriorityQueues.Extensions; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.Graphs.ShortestDistance; |
| | | 5 | | |
| | | 6 | | internal static class ShortestDistanceFinderHelper |
| | | 7 | | { |
| | | 8 | | public static void ValidateParameters(IGraph graph, int start, int? end = null) |
| | 2207 | 9 | | { |
| | 2207 | 10 | | var numberOfVertices = graph.GetNumberOfVertices(); |
| | 2207 | 11 | | if (start < 0 || start >= numberOfVertices) |
| | 18 | 12 | | throw new ArgumentException( |
| | 18 | 13 | | "Must be non-negative and smaller than the total number of vertices in the graph.", nameof(start)); |
| | 2189 | 14 | | if (end != null && (end < 0 || end >= numberOfVertices)) |
| | 18 | 15 | | throw new ArgumentException( |
| | 18 | 16 | | "Must be non-negative and smaller than the total number of vertices in the graph.", nameof(end)); |
| | 2171 | 17 | | } |
| | | 18 | | |
| | | 19 | | public static IList<int> BuildShortestPath(int end, BestPreviouses bestPreviouses, bool reverse = true) |
| | 1316 | 20 | | { |
| | 1316 | 21 | | var shortestPath = new List<int> { end }; |
| | | 22 | | |
| | 1316 | 23 | | int current = end; |
| | 3538 | 24 | | while (bestPreviouses.Values.TryGetValue(current, out var bestPrevious)) |
| | 3538 | 25 | | { |
| | 3538 | 26 | | current = bestPrevious.PreviousVertex; |
| | 3538 | 27 | | if (current < 0) |
| | 1316 | 28 | | break; |
| | | 29 | | |
| | 2222 | 30 | | shortestPath.Add(current); |
| | 2222 | 31 | | } |
| | | 32 | | |
| | 1316 | 33 | | if (reverse) |
| | 998 | 34 | | shortestPath.Reverse(); |
| | 1316 | 35 | | return shortestPath; |
| | 1316 | 36 | | } |
| | | 37 | | |
| | | 38 | | public static void RelaxOutgoingEdgesOfVertex( |
| | | 39 | | IGraph graph, |
| | | 40 | | Func<int, int, int> distancesFunc, |
| | | 41 | | BestPreviouses bestPreviouses, |
| | | 42 | | HashSet<int> added, IUpdatablePriorityQueue<int> vertexes, int lastAdded) |
| | 4317 | 43 | | { |
| | 21671 | 44 | | foreach (var (vertex, edgeStart, edgeEnd) in graph.GetAdjacentVerticesAndEdges(lastAdded, true)) |
| | 4372 | 45 | | { |
| | 4372 | 46 | | if (added.Contains(vertex)) |
| | 22 | 47 | | continue; |
| | | 48 | | |
| | 4350 | 49 | | var edgeDistance = distancesFunc(edgeStart, edgeEnd); |
| | 4350 | 50 | | if (edgeDistance < 0) |
| | 24 | 51 | | throw new InvalidOperationException( |
| | 24 | 52 | | $"Negative edges are not supported: distance of ({edgeStart}, {edgeEnd}) = {edgeDistance}."); |
| | | 53 | | |
| | 4326 | 54 | | var newDistance = bestPreviouses.Values[lastAdded].DistanceFromStart + edgeDistance; |
| | 4326 | 55 | | if (!bestPreviouses.Values.TryGetValue(vertex, out var bestPrevious) || |
| | 4326 | 56 | | bestPrevious.DistanceFromStart > newDistance) |
| | 4280 | 57 | | { |
| | 4280 | 58 | | bestPreviouses.Values[vertex] = new(newDistance, lastAdded); |
| | 4280 | 59 | | vertexes.PushOrUpdate(vertex, -newDistance); |
| | 4280 | 60 | | } |
| | 4326 | 61 | | } |
| | 4293 | 62 | | } |
| | | 63 | | } |