| | | 1 | | namespace MoreStructures.Graphs.ShortestDistance; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An <see cref="IPotentialBasedShortestDistanceFinder"/> implementation, wrapping a |
| | | 5 | | /// <see cref="IShortestDistanceFinder"/> algorithm and using a potential function as a heuristic to enhance graph |
| | | 6 | | /// exploration. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <remarks> |
| | | 9 | | /// Common ground for all A* variants, such as <see cref="AStarShortestDistanceFinder"/> and |
| | | 10 | | /// <see cref="BidirectionalAStarShortestDistanceFinder"/>. |
| | | 11 | | /// <br/> |
| | | 12 | | /// Check <see cref="IPotentialBasedShortestDistanceFinder"/> general documentation for the requirements and desired |
| | | 13 | | /// properties for the heuristic. |
| | | 14 | | /// </remarks> |
| | | 15 | | public abstract class PotentialBasedShortestDistanceFinder : IPotentialBasedShortestDistanceFinder |
| | | 16 | | { |
| | | 17 | | /// <summary> |
| | | 18 | | /// A <see cref="IShortestDistanceFinder"/> instance, used to run the shortest distance algorithm on the provided |
| | | 19 | | /// graph. |
| | | 20 | | /// </summary> |
| | 1038 | 21 | | protected IShortestDistanceFinder Finder { get; } |
| | | 22 | | |
| | | 23 | | /// <inheritdoc cref="PotentialBasedShortestDistanceFinder"/> |
| | | 24 | | /// <param name="finder"> |
| | | 25 | | /// <inheritdoc cref="Finder" path="*"/> |
| | | 26 | | /// </param> |
| | 60 | 27 | | protected PotentialBasedShortestDistanceFinder(IShortestDistanceFinder finder) |
| | 60 | 28 | | { |
| | 60 | 29 | | Finder = finder; |
| | 60 | 30 | | } |
| | | 31 | | |
| | | 32 | | /// <inheritdoc/> |
| | | 33 | | public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end) => |
| | 4256 | 34 | | Find(graph, distances, v => 0, start, end); |
| | | 35 | | |
| | | 36 | | /// <inheritdoc/> |
| | | 37 | | public (int, IList<int>) Find( |
| | | 38 | | IGraph graph, IGraphDistances distances, Func<int, int> potentials, int start, int end) |
| | 1038 | 39 | | { |
| | 1038 | 40 | | var alteredDistances = new PotentialFunctionAlteredGraphDistances(distances, potentials); |
| | 1038 | 41 | | var (alteredDistance, shortestDistancePath) = Finder.Find(graph, alteredDistances, start, end); |
| | 1024 | 42 | | var actualDistance = alteredDistance == int.MaxValue || alteredDistance == int.MinValue |
| | 1024 | 43 | | ? alteredDistance |
| | 1024 | 44 | | : alteredDistance + potentials(start) - potentials(end); |
| | 1024 | 45 | | return (actualDistance, shortestDistancePath); |
| | 1024 | 46 | | } |
| | | 47 | | |
| | | 48 | | private sealed class PotentialFunctionAlteredGraphDistances : IGraphDistances |
| | | 49 | | { |
| | 2811 | 50 | | private IGraphDistances OriginalDistances { get; } |
| | 5622 | 51 | | private Func<int, int> Potentials { get; } |
| | | 52 | | |
| | 1038 | 53 | | public PotentialFunctionAlteredGraphDistances( |
| | 1038 | 54 | | IGraphDistances originalDistances, Func<int, int> potentials) |
| | 1038 | 55 | | { |
| | 1038 | 56 | | OriginalDistances = originalDistances; |
| | 1038 | 57 | | Potentials = potentials; |
| | 1038 | 58 | | } |
| | | 59 | | |
| | | 60 | | public int this[(int edgeStart, int edgeEnd) edge] => |
| | 2811 | 61 | | OriginalDistances[edge] - Potentials(edge.edgeStart) + Potentials(edge.edgeEnd); |
| | | 62 | | } |
| | | 63 | | |
| | | 64 | | } |