| | | 1 | | using MoreStructures.PriorityQueues; |
| | | 2 | | using MoreStructures.PriorityQueues.BinaryHeap; |
| | | 3 | | using MoreStructures.PriorityQueues.Extensions; |
| | | 4 | | |
| | | 5 | | namespace MoreStructures.Graphs.MinimumSpanningTree; |
| | | 6 | | |
| | | 7 | | /// <summary> |
| | | 8 | | /// A <see cref="IMstFinder"/> implementing Prim's algorithm. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="algorithm"> |
| | | 12 | | /// ALGORITHM |
| | | 13 | | /// <br/> |
| | | 14 | | /// - The algorithm closely resembles Dijkstra's algorithm for shortest distance finding. It is a gready algorithm |
| | | 15 | | /// selecting a vertex and the corresponding edge at each iteration, and doing that efficiently thanks to the use |
| | | 16 | | /// of a priority queue and a dictionary of mappings from vertices to edges of shortest distance. |
| | | 17 | | /// <br/> |
| | | 18 | | /// - The core idea is to split the vertices of the graph into two sets: the set A of vertices already added to the |
| | | 19 | | /// Minimum Spanning Tree MST, and the set NA of vertices which haven't been added yet to the MST. |
| | | 20 | | /// <br/> |
| | | 21 | | /// - At the beginning an arbitrary vertex (id = 0), is included in A and set as last added vertex LA, to bootstrap |
| | | 22 | | /// the process. The set of edges representing the Minimum Spanning Tree, MST, is set to an empty set. The |
| | | 23 | | /// dictionary mapping vertices to shortest distance edges BP is set to an empty dictionary. A min priority queue |
| | | 24 | | /// of vertices, PQ, is also instantiated. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - After that the main loop of the algorithm is executed, adding a single vertex LA to A and a single edge to |
| | | 27 | | /// MST at each iteration, and stopping only when A contains v vertices (i.e. when MST is spanning the entire |
| | | 28 | | /// graph). |
| | | 29 | | /// <br/> |
| | | 30 | | /// - At each iteration, all edges e, outgoing from and incoming into LA, and connecting LA to a vertex V not yet |
| | | 31 | | /// in A are checked. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - If the distance of e, d(e), is strictly smaller than the smallest known edge for V, BP[V], BP is updated and |
| | | 34 | | /// pushed or updated in PQ. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - After all edges of LA are checked, the vertex V' connected to A via an edge E' of shortest distance is |
| | | 37 | | /// extracted from PQ, assigned to LA and added to A. E' is added to MST. |
| | | 38 | | /// <br/> |
| | | 39 | | /// - After v - 1 iterations, MST is returned as result. |
| | | 40 | | /// </para> |
| | | 41 | | /// <para id="complexity"> |
| | | 42 | | /// COMPLEXITY |
| | | 43 | | /// <br/> |
| | | 44 | | /// - All data structures initialization (A, NA, PQ, BP, MST) takes constant amount of time. |
| | | 45 | | /// <br/> |
| | | 46 | | /// - During the v - 1 iterations, all edges are visited at most twice: once from the source side and once from the |
| | | 47 | | /// target side. |
| | | 48 | | /// <br/> |
| | | 49 | | /// - While checking and updating BP and A take a constant amount of time, pushing or updating the priority in PQ |
| | | 50 | | /// has a runtime which depends on the specific implementation of <see cref="IUpdatablePriorityQueue{T}"/> used. |
| | | 51 | | /// <br/> |
| | | 52 | | /// - The analysis of the impact of the priority queue on the overall performance of the algorithm is similar to |
| | | 53 | | /// the one done in <see cref="ShortestDistance.DijkstraShortestDistanceFinder"/>. Check that analysis for |
| | | 54 | | /// further details. |
| | | 55 | | /// <br/> |
| | | 56 | | /// - In conclusion, Time Complexity is O(e + v * log(v)) with the best available implementation of an |
| | | 57 | | /// <see cref="IUpdatablePriorityQueue{T}"/> and O((v + e) * e) with a naive implementation. |
| | | 58 | | /// <br/> |
| | | 59 | | /// - Space Complexity is O(v), since all data structures contains O(v) items, all of constant size. |
| | | 60 | | /// </para> |
| | | 61 | | /// </remarks> |
| | | 62 | | public class PrimMstFinder : IMstFinder |
| | | 63 | | { |
| | 13 | 64 | | private Func<IUpdatablePriorityQueue<int>> PriorityQueueBuilder { get; } |
| | | 65 | | |
| | | 66 | | /// <inheritdoc cref="PrimMstFinder"/>. |
| | | 67 | | /// <param name="priorityQueueBuilder"> |
| | | 68 | | /// A builder of a <see cref="IUpdatablePriorityQueue{T}"/> of <see cref="int"/> values, used by the algorithm to |
| | | 69 | | /// store edges with priority from the closest to any of the vertices of the MST, to the farthest. |
| | | 70 | | /// </param> |
| | 14 | 71 | | public PrimMstFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder) |
| | 14 | 72 | | { |
| | 14 | 73 | | PriorityQueueBuilder = priorityQueueBuilder; |
| | 14 | 74 | | } |
| | | 75 | | |
| | | 76 | | /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/> |
| | | 77 | | /// <summary> |
| | | 78 | | /// Finds the Minimum Spanning Tree (MST) of the provided <paramref name="graph"/> using the Prim's algorithm. |
| | | 79 | | /// </summary> |
| | | 80 | | /// <remarks> |
| | | 81 | | /// <inheritdoc cref="PrimMstFinder"/> |
| | | 82 | | /// </remarks> |
| | | 83 | | public ISet<(int, int)> Find(IGraph graph, IGraphDistances distances) |
| | 14 | 84 | | { |
| | 14 | 85 | | var numberOfVertices = graph.GetNumberOfVertices(); |
| | 14 | 86 | | if (numberOfVertices == 0) |
| | 1 | 87 | | return new HashSet<(int, int)>(); |
| | | 88 | | |
| | 13 | 89 | | var mst = new HashSet<(int, int)> { }; |
| | | 90 | | |
| | 13 | 91 | | var start = 0; |
| | 13 | 92 | | var bestPreviouses = new Dictionary<int, (int edgeDistance, int edgeStart, int edgeEnd)>(); |
| | | 93 | | |
| | 13 | 94 | | var added = new HashSet<int> { start }; |
| | 13 | 95 | | var vertexes = PriorityQueueBuilder(); |
| | 13 | 96 | | var lastAdded = start; |
| | 42 | 97 | | while (added.Count < numberOfVertices) |
| | 33 | 98 | | { |
| | 259 | 99 | | foreach (var (vertex, edgeStart, edgeEnd) in graph.GetAdjacentVerticesAndEdges(lastAdded, false)) |
| | 80 | 100 | | { |
| | 80 | 101 | | if (added.Contains(vertex)) |
| | 33 | 102 | | continue; |
| | | 103 | | |
| | 47 | 104 | | var newDistance = distances[(edgeStart, edgeEnd)]; |
| | 47 | 105 | | if (!bestPreviouses.TryGetValue(vertex, out var bestPrevious) || |
| | 47 | 106 | | bestPrevious.edgeDistance > newDistance) |
| | 41 | 107 | | { |
| | 41 | 108 | | bestPreviouses[vertex] = (newDistance, edgeStart, edgeEnd); |
| | 41 | 109 | | vertexes.PushOrUpdate(vertex, -newDistance); |
| | 41 | 110 | | } |
| | 47 | 111 | | } |
| | | 112 | | |
| | 33 | 113 | | if (vertexes.Count == 0) |
| | 4 | 114 | | throw new InvalidOperationException("The graph is not connected."); |
| | | 115 | | |
| | 29 | 116 | | lastAdded = vertexes.Pop().Item; |
| | 29 | 117 | | added.Add(lastAdded); |
| | 29 | 118 | | mst.Add((bestPreviouses[lastAdded].edgeStart, bestPreviouses[lastAdded].edgeEnd)); |
| | 29 | 119 | | } |
| | | 120 | | |
| | 9 | 121 | | return mst; |
| | 10 | 122 | | } |
| | | 123 | | } |