Changeset 8423

Timestamp:

08/07/12 10:52:01 (12 years ago)

Author:

spimming

Message:

#1894

• bidirectional version of Dijkstra algorithm
• method to get neighbors of a node in reversed order
• check for roundabouts in OneWay property

Location:

branches/RoutePlanning

Files:

• HeuristicLab.Algorithms.GraphRouting/3.3/BidirectionalDijkstraAlgorithm.cs (added)
• HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning.Test/Program.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm/TagConstants.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm/Way.cs (modified) (1 diff)

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

@@ -59 +59 @@
     <Compile Include="AStarAlgorithm.cs" />
     <Compile Include="AStarAlgorithmV2.cs" />
+    <Compile Include="BidirectionalDijkstraAlgorithm.cs" />
     <Compile Include="DijkstraAlgorithm.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs

@@ -26 +26 @@
       //Test(file6, 529102170, 1001363194, true, false); // inz - inz
 
-      IDataSource ds = TestLoad(file6);
-      Graph.Graph graph = new Graph.Graph(ds);
-      TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
-      TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
+      //IDataSource ds = TestLoad(file6);
+      //Graph.Graph graph = new Graph.Graph(ds);
+      //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
 
       //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
       //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 31372732, false, false); // inz - hgb
       //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 31372732, false, false); // inz - hgb
+
+      //TestLoadAndRouter(file5, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
+      //TestLoadAndRouter(file5, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, true);
+      TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 31372732, false, true); // inz - hgb
 
       System.Console.Read();

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs

@@ -35 +35 @@
         foreach (Vertex<Node> neighbor in vertices) {
           if (edge.CanBeTraversed(vertex.Node, neighbor.Node)) {
+            float weight = GetWeight(edge, vertex, neighbor);
+            neighbors[neighbor.Node.Id] = weight;
+          }
+        }
+      }
+      return neighbors;
+    }
+
+    public Dictionary<long, float> GetNeighborsReversed(long id) {
+      Vertex<Node> vertex = GetVertex(id);
+      Dictionary<long, float> neighbors = new Dictionary<long, float>();
+      List<Way> edges = GetEdges(vertex);
+      foreach (Way edge in edges) {
+        List<Vertex<Node>> vertices = GetNeighborVerticesOnEdge(edge, vertex);
+        foreach (Vertex<Node> neighbor in vertices) {
+          if (edge.CanBeTraversed(neighbor.Node, vertex.Node)) {
             float weight = GetWeight(edge, vertex, neighbor);
             neighbors[neighbor.Node.Id] = weight;

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/TagConstants.cs

@@ -3 +3 @@
   public class TagConstants {
     public const string HighwayTagKey = "highway";
+    public const string JunctionTagKey = "junction";
     public const string OneWayTag = "oneway";
+    public const string RoundaboutValue = "roundabout";
     public const string YesValue = "yes";
+    public const string TrueValue = "true";
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/Way.cs

@@ -73 +73 @@
         if (base.Tags.ContainsKey(TagConstants.OneWayTag)) {
           string value = base.Tags[TagConstants.OneWayTag];
-          return value.Equals(TagConstants.YesValue);
+          return value.Equals(TagConstants.YesValue) || value.Equals(TagConstants.TrueValue);
+        } else if (base.Tags.ContainsKey(TagConstants.JunctionTagKey)) {
+          string value = base.Tags[TagConstants.JunctionTagKey];
+          return value.Equals(TagConstants.RoundaboutValue);
         } else {
           return false;