1 |
|
---|
2 | using System;
|
---|
3 | using System.Collections.Generic;
|
---|
4 | using HeuristicLab.Algorithms.GraphRouting.Interfaces;
|
---|
5 | using HeuristicLab.Problems.RoutePlanning.Interfaces;
|
---|
6 | namespace HeuristicLab.Algorithms.GraphRouting {
|
---|
7 | public class DijkstraAlgorithmV2 : IRouter {
|
---|
8 | private IGraph graph;
|
---|
9 |
|
---|
10 | private HashSet<long> visitedNodes;
|
---|
11 | private HashSet<long> unvisitedNodes;
|
---|
12 | private Dictionary<long, float> distances;
|
---|
13 | private Dictionary<long, long> predecessors;
|
---|
14 |
|
---|
15 | public DijkstraAlgorithmV2(IGraph graph) {
|
---|
16 | this.graph = graph;
|
---|
17 | }
|
---|
18 |
|
---|
19 | #region IRouter Members
|
---|
20 |
|
---|
21 | public long[] Calculate(long sourceNodeId, long targetNodeId) {
|
---|
22 | visitedNodes = new HashSet<long>(); // visited
|
---|
23 | unvisitedNodes = new HashSet<long>(); // unvisited
|
---|
24 | distances = new Dictionary<long, float>();
|
---|
25 | predecessors = new Dictionary<long, long>();
|
---|
26 |
|
---|
27 | List<long> resultRoute = new List<long>();
|
---|
28 | if (sourceNodeId == targetNodeId) {
|
---|
29 | resultRoute.Add(sourceNodeId);
|
---|
30 | return resultRoute.ToArray();
|
---|
31 | }
|
---|
32 |
|
---|
33 | long currentNode = sourceNodeId;
|
---|
34 | distances.Add(currentNode, 0);
|
---|
35 | unvisitedNodes.Add(currentNode);
|
---|
36 |
|
---|
37 | while (unvisitedNodes.Count > 0) {
|
---|
38 | currentNode = GetMinimumDistance(unvisitedNodes);
|
---|
39 | visitedNodes.Add(currentNode);
|
---|
40 | unvisitedNodes.Remove(currentNode);
|
---|
41 | if (currentNode == targetNodeId) {
|
---|
42 | break;
|
---|
43 | }
|
---|
44 | FindMinimalWeight(currentNode);
|
---|
45 | }
|
---|
46 |
|
---|
47 | if (currentNode != targetNodeId) {
|
---|
48 | // target was not found
|
---|
49 | // maybe throw exception
|
---|
50 | throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
|
---|
51 | }
|
---|
52 | return GetRoute(targetNodeId).ToArray();
|
---|
53 | }
|
---|
54 |
|
---|
55 | #endregion
|
---|
56 |
|
---|
57 | public long GetNodeIdWithRank(long sourceNodeId, int rank) {
|
---|
58 | visitedNodes = new HashSet<long>(); // visited
|
---|
59 | unvisitedNodes = new HashSet<long>(); // unvisited
|
---|
60 | distances = new Dictionary<long, float>();
|
---|
61 | predecessors = new Dictionary<long, long>();
|
---|
62 | int currentRank = 0;
|
---|
63 |
|
---|
64 |
|
---|
65 | long currentNode = sourceNodeId;
|
---|
66 | distances.Add(currentNode, 0);
|
---|
67 | unvisitedNodes.Add(currentNode);
|
---|
68 |
|
---|
69 | while (unvisitedNodes.Count > 0) {
|
---|
70 | currentNode = GetMinimumDistance(unvisitedNodes);
|
---|
71 | visitedNodes.Add(currentNode);
|
---|
72 | unvisitedNodes.Remove(currentNode);
|
---|
73 | currentRank++;
|
---|
74 | if (currentRank == rank) {
|
---|
75 | break;
|
---|
76 | }
|
---|
77 | FindMinimalWeight(currentNode);
|
---|
78 | }
|
---|
79 | return currentNode;
|
---|
80 | }
|
---|
81 |
|
---|
82 | private long GetMinimumDistance(HashSet<long> nodeIds) {
|
---|
83 | long minimum = -1;
|
---|
84 | foreach (long id in nodeIds) {
|
---|
85 | if (minimum == -1) minimum = id;
|
---|
86 | else {
|
---|
87 | if (GetDistance(id) < GetDistance(minimum)) {
|
---|
88 | minimum = id;
|
---|
89 | }
|
---|
90 | }
|
---|
91 | }
|
---|
92 | return minimum;
|
---|
93 | }
|
---|
94 |
|
---|
95 | private float GetDistance(long id) {
|
---|
96 | float d;
|
---|
97 | if (distances.TryGetValue(id, out d)) {
|
---|
98 | return d;
|
---|
99 | } else { return float.MaxValue; }
|
---|
100 |
|
---|
101 | }
|
---|
102 |
|
---|
103 | private void FindMinimalWeight(long nodeId) {
|
---|
104 | //if (nodeId == 274265932) {
|
---|
105 | // Console.WriteLine();
|
---|
106 | //}
|
---|
107 | Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(nodeId);
|
---|
108 | foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
|
---|
109 | // update relax
|
---|
110 | float totalWeight = GetDistance(nodeId) + neighbor.Value;
|
---|
111 | if (GetDistance(neighbor.Key) > totalWeight) {
|
---|
112 | distances[neighbor.Key] = totalWeight;
|
---|
113 | predecessors[neighbor.Key] = nodeId;
|
---|
114 | unvisitedNodes.Add(neighbor.Key);
|
---|
115 | }
|
---|
116 | }
|
---|
117 | }
|
---|
118 |
|
---|
119 | private List<long> GetRoute(long nodeId) {
|
---|
120 | List<long> route = new List<long>();
|
---|
121 | long current = nodeId;
|
---|
122 | long next;
|
---|
123 |
|
---|
124 | if (!predecessors.TryGetValue(current, out next)) {
|
---|
125 | return null;
|
---|
126 | }
|
---|
127 | route.Add(current);
|
---|
128 | while (predecessors.TryGetValue(current, out next)) {
|
---|
129 | current = predecessors[current];
|
---|
130 | route.Add(current);
|
---|
131 | }
|
---|
132 | route.Reverse();
|
---|
133 | return route;
|
---|
134 | }
|
---|
135 | }
|
---|
136 | }
|
---|