Changeset 8308 for branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs

Timestamp:

07/19/12 19:44:56 (12 years ago)

Author:

spimming

Message:

#1894:

• get neighbors for specific node
• method to calculate weight between two nodes
• interface for router
• Dijkstra algorithm initial commit
• Utils methods added

File:

• branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs (modified) (1 diff)

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

@@ -24 +24 @@
     }
 
-    //public Dictionary<long, float> GetNeighbours(long id) {
-    //  Vertex<Node> vertex = GetVertex(id);
-    //  Dictionary<long, float> neighbors = new Dictionary<long, float>();
-    //  IList<Way> edges = GetEdges(vertex);
-    //  foreach (Way edge in edges) {
+    public Dictionary<long, float> GetNeighbors(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) {
+        //TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
 
-    //  }
-    //  return null;
-    //}
+        // get all naighbours of current vertex on this edge
+        List<Vertex<Node>> vertices = GetNeighborVerticesOnEdge(edge, vertex);
+        foreach (Vertex<Node> neighbor in vertices) {
+          float weight = GetWeight(edge, vertex, neighbor);
+          neighbors[neighbor.Id] = weight;
+        }
+      }
+      return null;
+    }
 
+    public List<Vertex<Node>> GetNeighborVerticesOnEdge(Way edge, Vertex<Node> vertex) {
+      List<Vertex<Node>> neighbors = new List<Vertex<Node>>();
+      for (int i = 0; i < edge.Nodes.Count; i++) {
+        Node node = edge.Nodes[i];
+        if (node.Id == vertex.Node.Id) {
+          if (i > 0) {
+            neighbors.Add(GetVertex(edge.Nodes[i - 1].Id));
+          }
+          if (i < edge.Nodes.Count - 1) {
+            neighbors.Add(GetVertex(edge.Nodes[i + 1].Id));
+          }
+        }
+      }
+      return neighbors;
+    }
+
+    public float GetWeight(Way edge, Vertex<Node> source, Vertex<Node> target) {
+      double distance = Utils.Distance(source.Node.Point, target.Node.Point);
+      int speed = 0;
+
+      //TODO: 
+      HighwayType highwayType = edge.HighwayTag;
+      switch (highwayType) {
+        case HighwayType.bridleway:
+        case HighwayType.bus_guideway:
+        case HighwayType.raceway:
+        case HighwayType.cycleway:
+        case HighwayType.footway:
+        case HighwayType.steps:
+        case HighwayType.null_type:
+          speed = 1;
+          break;
+
+        case HighwayType.path:
+        case HighwayType.service:
+        case HighwayType.pedestrian:
+        case HighwayType.living_street:
+          speed = 15;
+          break;
+
+        case HighwayType.road:
+        case HighwayType.track:
+          speed = 30;
+          break;
+
+        case HighwayType.tertiary:
+        case HighwayType.tertiary_link:
+        case HighwayType.secondary:
+        case HighwayType.secondary_link:
+          speed = 80;
+          break;
+
+        case HighwayType.unclassified:
+        case HighwayType.residential:
+          speed = 50;
+          break;
+
+        case HighwayType.trunk:
+        case HighwayType.trunk_link:
+        case HighwayType.primary:
+        case HighwayType.primary_link:
+          speed = 100;
+          break;
+        case HighwayType.motorway:
+        case HighwayType.motorway_link:
+          speed = 130;
+          break;
+
+        default:
+          speed = 1;
+          break;
+      }
+
+      double weight = (distance / speed) * 3.6;
+      return (float)weight;
+    }
   }
 }