| 1 |
|
|---|
| 2 | using System.Collections.Generic;
|
|---|
| 3 | using HeuristicLab.Problems.RoutePlanning.Osm;
|
|---|
| 4 | namespace HeuristicLab.Problems.RoutePlanning.Graph {
|
|---|
| 5 | public class Graph {
|
|---|
| 6 | private IDataSource dataSource;
|
|---|
| 7 | private Dictionary<Node, List<Node>> vertexEdges;
|
|---|
| 8 | private Dictionary<long, Vertex<Node>> vertices;
|
|---|
| 9 | private Dictionary<Way, Dictionary<long, List<Vertex<Node>>>> resolvedList;
|
|---|
| 10 |
|
|---|
| 11 | public Graph(IDataSource ds) {
|
|---|
| 12 | dataSource = ds;
|
|---|
| 13 | vertexEdges = new Dictionary<Node, List<Node>>();
|
|---|
| 14 | vertices = new Dictionary<long, Vertex<Node>>();
|
|---|
| 15 | resolvedList = new Dictionary<Way, Dictionary<long, List<Vertex<Node>>>>();
|
|---|
| 16 | }
|
|---|
| 17 |
|
|---|
| 18 | public Vertex<Node> GetVertex(long id) {
|
|---|
| 19 | return new Vertex<Node>(dataSource.GetNode(id));
|
|---|
| 20 | }
|
|---|
| 21 |
|
|---|
| 22 | public List<Way> GetEdges(Vertex<Node> vertex) {
|
|---|
| 23 | return dataSource.GetWays(vertex.Node);
|
|---|
| 24 | }
|
|---|
| 25 |
|
|---|
| 26 | public Dictionary<long, float> GetNeighbors(long id) {
|
|---|
| 27 | Vertex<Node> vertex = GetVertex(id);
|
|---|
| 28 | Dictionary<long, float> neighbors = new Dictionary<long, float>();
|
|---|
| 29 | List<Way> edges = GetEdges(vertex);
|
|---|
| 30 | foreach (Way edge in edges) {
|
|---|
| 31 | //TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
|
|---|
| 32 |
|
|---|
| 33 | // get all naighbours of current vertex on this edge
|
|---|
| 34 | List<Vertex<Node>> vertices = GetNeighborVerticesOnEdge(edge, vertex);
|
|---|
| 35 | foreach (Vertex<Node> neighbor in vertices) {
|
|---|
| 36 | float weight = GetWeight(edge, vertex, neighbor);
|
|---|
| 37 | neighbors[neighbor.Node.Id] = weight;
|
|---|
| 38 | }
|
|---|
| 39 | }
|
|---|
| 40 | return neighbors;
|
|---|
| 41 | }
|
|---|
| 42 |
|
|---|
| 43 | public List<Vertex<Node>> GetNeighborVerticesOnEdge(Way edge, Vertex<Node> vertex) {
|
|---|
| 44 | List<Vertex<Node>> neighbors = new List<Vertex<Node>>();
|
|---|
| 45 | for (int i = 0; i < edge.Nodes.Count; i++) {
|
|---|
| 46 | Node node = edge.Nodes[i];
|
|---|
| 47 | if (node.Id == vertex.Node.Id) {
|
|---|
| 48 | if (i > 0) {
|
|---|
| 49 | neighbors.Add(GetVertex(edge.Nodes[i - 1].Id));
|
|---|
| 50 | }
|
|---|
| 51 | if (i < edge.Nodes.Count - 1) {
|
|---|
| 52 | neighbors.Add(GetVertex(edge.Nodes[i + 1].Id));
|
|---|
| 53 | }
|
|---|
| 54 | }
|
|---|
| 55 | }
|
|---|
| 56 | return neighbors;
|
|---|
| 57 | }
|
|---|
| 58 |
|
|---|
| 59 | public float GetWeight(Way edge, Vertex<Node> source, Vertex<Node> target) {
|
|---|
| 60 | double distance = Utils.Distance(source.Node.Point, target.Node.Point);
|
|---|
| 61 | int speed = 0;
|
|---|
| 62 |
|
|---|
| 63 | //TODO:
|
|---|
| 64 | HighwayType highwayType = edge.HighwayTag;
|
|---|
| 65 | switch (highwayType) {
|
|---|
| 66 | case HighwayType.bridleway:
|
|---|
| 67 | case HighwayType.bus_guideway:
|
|---|
| 68 | case HighwayType.raceway:
|
|---|
| 69 | case HighwayType.cycleway:
|
|---|
| 70 | case HighwayType.footway:
|
|---|
| 71 | case HighwayType.steps:
|
|---|
| 72 | case HighwayType.null_type:
|
|---|
| 73 | speed = 1;
|
|---|
| 74 | break;
|
|---|
| 75 |
|
|---|
| 76 | case HighwayType.path:
|
|---|
| 77 | case HighwayType.service:
|
|---|
| 78 | case HighwayType.pedestrian:
|
|---|
| 79 | case HighwayType.living_street:
|
|---|
| 80 | speed = 15;
|
|---|
| 81 | break;
|
|---|
| 82 |
|
|---|
| 83 | case HighwayType.road:
|
|---|
| 84 | case HighwayType.track:
|
|---|
| 85 | speed = 30;
|
|---|
| 86 | break;
|
|---|
| 87 |
|
|---|
| 88 | case HighwayType.tertiary:
|
|---|
| 89 | case HighwayType.tertiary_link:
|
|---|
| 90 | case HighwayType.secondary:
|
|---|
| 91 | case HighwayType.secondary_link:
|
|---|
| 92 | speed = 80;
|
|---|
| 93 | break;
|
|---|
| 94 |
|
|---|
| 95 | case HighwayType.unclassified:
|
|---|
| 96 | case HighwayType.residential:
|
|---|
| 97 | speed = 50;
|
|---|
| 98 | break;
|
|---|
| 99 |
|
|---|
| 100 | case HighwayType.trunk:
|
|---|
| 101 | case HighwayType.trunk_link:
|
|---|
| 102 | case HighwayType.primary:
|
|---|
| 103 | case HighwayType.primary_link:
|
|---|
| 104 | speed = 100;
|
|---|
| 105 | break;
|
|---|
| 106 | case HighwayType.motorway:
|
|---|
| 107 | case HighwayType.motorway_link:
|
|---|
| 108 | speed = 130;
|
|---|
| 109 | break;
|
|---|
| 110 |
|
|---|
| 111 | default:
|
|---|
| 112 | speed = 1;
|
|---|
| 113 | break;
|
|---|
| 114 | }
|
|---|
| 115 |
|
|---|
| 116 | double weight = (distance / speed) * 3.6;
|
|---|
| 117 | return (float)weight;
|
|---|
| 118 | }
|
|---|
| 119 |
|
|---|
| 120 | public float EstimatedCosts(long sourceId, long targetId) {
|
|---|
| 121 | Vertex<Node> source = GetVertex(sourceId);
|
|---|
| 122 | Vertex<Node> target = GetVertex(targetId);
|
|---|
| 123 | return EstimatedCosts(source, target);
|
|---|
| 124 | }
|
|---|
| 125 |
|
|---|
| 126 | public float EstimatedCosts(Vertex<Node> source, Vertex<Node> target) {
|
|---|
| 127 | double distance = Utils.Distance(source.Node.Point, target.Node.Point);
|
|---|
| 128 | int speed = 130;
|
|---|
| 129 | double costs = (distance / speed) * 3.6;
|
|---|
| 130 | return (float)costs;
|
|---|
| 131 | }
|
|---|
| 132 | }
|
|---|
| 133 | }
|
|---|
