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 | if (edge.CanBeTraversed(vertex.Node, neighbor.Node)) {
|
---|
37 | float weight = GetWeight(edge, vertex, neighbor);
|
---|
38 | neighbors[neighbor.Node.Id] = weight;
|
---|
39 | }
|
---|
40 | }
|
---|
41 | }
|
---|
42 | return neighbors;
|
---|
43 | }
|
---|
44 |
|
---|
45 | public List<Vertex<Node>> GetNeighborVerticesOnEdge(Way edge, Vertex<Node> vertex) {
|
---|
46 | List<Vertex<Node>> neighbors = new List<Vertex<Node>>();
|
---|
47 | for (int i = 0; i < edge.Nodes.Count; i++) {
|
---|
48 | Node node = edge.Nodes[i];
|
---|
49 | if (node.Id == vertex.Node.Id) {
|
---|
50 | if (i > 0) {
|
---|
51 | neighbors.Add(GetVertex(edge.Nodes[i - 1].Id));
|
---|
52 | }
|
---|
53 | if (i < edge.Nodes.Count - 1) {
|
---|
54 | neighbors.Add(GetVertex(edge.Nodes[i + 1].Id));
|
---|
55 | }
|
---|
56 | }
|
---|
57 | }
|
---|
58 | return neighbors;
|
---|
59 | }
|
---|
60 |
|
---|
61 | public float GetWeight(Way edge, Vertex<Node> source, Vertex<Node> target) {
|
---|
62 | double distance = Utils.Distance(source.Node.Point, target.Node.Point);
|
---|
63 | int speed = edge.GetMaxSpeed();
|
---|
64 | double weight = (distance / speed) * 3.6;
|
---|
65 | return (float)weight;
|
---|
66 | }
|
---|
67 |
|
---|
68 | public float EstimatedCosts(long sourceId, long targetId) {
|
---|
69 | Vertex<Node> source = GetVertex(sourceId);
|
---|
70 | Vertex<Node> target = GetVertex(targetId);
|
---|
71 | return EstimatedCosts(source, target);
|
---|
72 | }
|
---|
73 |
|
---|
74 | public float EstimatedCosts(Vertex<Node> source, Vertex<Node> target) {
|
---|
75 | double distance = Utils.Distance(source.Node.Point, target.Node.Point);
|
---|
76 | int speed = 130;
|
---|
77 | double costs = (distance / speed) * 3.6;
|
---|
78 | return (float)costs;
|
---|
79 | }
|
---|
80 | }
|
---|
81 | }
|
---|