[8300] | 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 |
|
---|
[8308] | 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, ...)
|
---|
[8300] | 32 |
|
---|
[8308] | 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);
|
---|
[8314] | 37 | neighbors[neighbor.Node.Id] = weight;
|
---|
[8308] | 38 | }
|
---|
| 39 | }
|
---|
[8314] | 40 | return neighbors;
|
---|
[8308] | 41 | }
|
---|
[8300] | 42 |
|
---|
[8308] | 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 | }
|
---|
[8300] | 119 | }
|
---|
| 120 | }
|
---|