1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  7. namespace BLL
  8. {
  9. public class PathFinder
  10. {
  11. Dictionary<BatteryCenter, double> listDistance = new Dictionary<BatteryCenter, double>();
  12. Dictionary<BatteryCenter, BatteryCenter> listPrevious = new Dictionary<BatteryCenter, BatteryCenter>();
  14. public List<BatteryCenterDistance> FindPathFromCityToCity(Map map, BatteryCenter from, BatteryCenter to, double range)
  15. {
  17. using (System.IO.StreamWriter file = new System.IO.StreamWriter(@"C:\log\map.txt", true))
  18. {
  19. file.WriteLine("COUNT: {0} - RANGE {1}", map.Stations.Count, range);
  20. file.WriteLine("FROM: {0} - TO: {1}", from.name, to.name);
  22. foreach (var m in map.Stations)
  23. {
  24. file.WriteLine("C: {0} - E: {1} - T: {2}", m.name, m.Edgelist.Count, m.GetType());
  25. }
  26. }
  28. List<BatteryCenterDistance> list = new List<BatteryCenterDistance>();
  30. if (map.IsAdjacent(from, to))
  31. {
  32. list.Add(new BatteryCenterDistance() { BatteryCenter = from, Distance = 0 });
  33. list.Add(new BatteryCenterDistance() { BatteryCenter = to, Distance = map.FindEdge(from, to).distance });
  34. }
  35. else
  36. {
  37. CalculateDistance(map, from, range);
  39. while (listPrevious[to] != null)
  40. {
  41. var b = map.FindEdge(to, listPrevious[to]);
  43. list.Add(new BatteryCenterDistance() { BatteryCenter = to, Distance = (b != null ? b.distance : 0) });
  44. to = listPrevious[to];
  45. }
  47. list.Add(new BatteryCenterDistance() { BatteryCenter = from, Distance = 0 });
  48. list.Reverse();
  50. double covered = 0.0;
  52. BatteryCenterDistance bcd = new BatteryCenterDistance();
  54. foreach (var b in list)
  55. {
  56. if ((covered + b.Distance >= range))
  57. {
  58. if (b.Distance > range)
  59. b.Possible = false;
  60. else
  61. {
  62. bcd.Stop = true;
  63. covered = b.Distance;
  64. }
  65. }
  66. else
  67. covered += b.Distance;
  69. bcd = b;
  70. }
  71. }
  73. return list;
  74. }
  76. private void CalculateDistance(Map map, BatteryCenter from, double range)
  77. {
  78. List<BatteryCenter> listTemp = new List<BatteryCenter>();
  80. foreach (BatteryCenter b in map.Stations)
  81. {
  82. listDistance[b] = Double.PositiveInfinity;
  83. listPrevious[b] = null;
  84. b.Mark = false;
  85. }
  87. listDistance[from] = 0;
  88. listTemp.Add(from);
  90. while (listTemp.Count > 0)
  91. {
  92. BatteryCenter current = null;
  94. double distance = Double.PositiveInfinity;
  96. foreach (BatteryCenter v in listTemp)
  97. {
  98. if (listDistance[v] < distance)
  99. {
  100. current = v;
  101. distance = listDistance[v];
  102. }
  103. }
  105. listTemp.Remove(current);
  106. current.Mark = true;
  108. foreach (var _edge in current.Edgelist)
  109. {
  110. BatteryCenter b = map.Stations.FirstOrDefault(x => x.name.Equals(_edge.BatteryStation1.name));
  112. if (((listDistance[current] + _edge.distance) < listDistance[b]) && !b.Mark && (_edge.distance <= range))
  113. {
  114. listDistance[b] = listDistance[current] + _edge.distance;
  115. listPrevious[b] = current;
  117. listTemp.Add(b);
  118. }
  119. }
  120. }
  121. }
  122. }
  123. }