Free cookie consent management tool by TermsFeed Policy Generator

source: branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs @ 8514

Last change on this file since 8514 was 8514, checked in by spimming, 10 years ago

#1894: experimented with different settings in cost and heuristic function

File size: 6.1 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using HeuristicLab.Problems.RoutePlanning.Osm;
5namespace HeuristicLab.Problems.RoutePlanning.Graph {
6  public class Graph : IGraph {
7    private IDictionary<long, Vertex> vertices;
8    private IDictionary<long, List<Edge<Vertex>>> adjacencyMap;
9    private IDictionary<long, List<Edge<Vertex>>> incidenceMap;
10
11    public Graph() {
12      vertices = new Dictionary<long, Vertex>();
13      adjacencyMap = new Dictionary<long, List<Edge<Vertex>>>();
14      incidenceMap = new Dictionary<long, List<Edge<Vertex>>>();
15    }
16
17    public void AddVertex(Vertex vertex) {
18      if (!vertices.ContainsKey(vertex.Id)) {
19        vertices.Add(vertex.Id, vertex);
20      }
21    }
22
23    public Vertex GetVertex(long id) {
24      Vertex vertex = null;
25      vertices.TryGetValue(id, out vertex);
26      return vertex;
27    }
28
29    public List<Vertex> GetVertices() {
30      return new List<Vertex>(vertices.Values);
31    }
32
33    public void AddEdge(long startId, long endId) {
34      Vertex start = GetVertex(startId);
35      if (start == null) throw new ArgumentException(string.Format("Invalid vertex id {0}", startId), "startId");
36      Vertex end = GetVertex(startId);
37      if (end == null) throw new ArgumentException(string.Format("Invalid vertex id {0}", endId), "endId");
38
39      Edge<Vertex> edge = new Edge<Vertex>(start, end);
40      //edge.Category = -1
41
42      AddEdge(edge);
43    }
44
45    public void AddEdge(Edge<Vertex> edge) {
46      if (!adjacencyMap.ContainsKey(edge.Source.Id)) {
47        adjacencyMap.Add(edge.Source.Id, new List<Edge<Vertex>>());
48      }
49      adjacencyMap[edge.Source.Id].Add(edge);
50
51      if (!incidenceMap.ContainsKey(edge.Target.Id)) {
52        incidenceMap.Add(edge.Target.Id, new List<Edge<Vertex>>());
53      }
54      incidenceMap[edge.Target.Id].Add(edge);
55    }
56
57    public void RemoveEdge(long startId, long endId) {
58      Edge<Vertex> edge = GetEdge(startId, endId);
59      if (edge != null) {
60        adjacencyMap[startId].Remove(edge);
61        incidenceMap[endId].Remove(edge);
62      }
63    }
64
65    public bool HasEdge(long startId, long endId) {
66      Edge<Vertex> edge = GetEdge(startId, endId);
67      return (edge != null);
68    }
69
70    public Edge<Vertex> GetEdge(long startId, long endId) {
71      List<Edge<Vertex>> edges = adjacencyMap[startId];
72      foreach (Edge<Vertex> edge in edges) {
73        if (edge.Target.Id == endId) {
74          return edge;
75        }
76      }
77      return null;
78    }
79
80    public List<Edge<Vertex>> GetInEdges(long vertexId) {
81      List<Edge<Vertex>> edges;
82      if (incidenceMap.TryGetValue(vertexId, out edges)) {
83        return edges;
84      } else {
85        return new List<Edge<Vertex>>();
86      }
87    }
88
89    public int GetInDegree(long vertexId) {
90      return incidenceMap[vertexId].Count;
91    }
92
93    public List<Edge<Vertex>> GetOutEdges(long vertexId) {
94      List<Edge<Vertex>> edges;
95      if (adjacencyMap.TryGetValue(vertexId, out edges)) {
96        return edges;
97      } else {
98        return new List<Edge<Vertex>>();
99      }
100
101    }
102
103    public int GetOutDegree(long vertexId) {
104      return adjacencyMap[vertexId].Count;
105    }
106
107    public List<Edge<Vertex>> GetEdges(long vertexId) {
108      List<Edge<Vertex>> result = new List<Edge<Vertex>>();
109      foreach (Edge<Vertex> edge in GetInEdges(vertexId)) {
110        if (!result.Contains(edge)) {
111          result.Add(edge);
112        }
113      }
114      foreach (Edge<Vertex> edge in GetOutEdges(vertexId)) {
115        if (!result.Contains(edge)) {
116          result.Add(edge);
117        }
118      }
119      return result;
120    }
121
122    public Dictionary<long, float> GetNeighborsWithWeight(long id) {
123      Dictionary<long, float> neighbors = new Dictionary<long, float>();
124      List<Edge<Vertex>> edges = GetOutEdges(id);
125      foreach (Edge<Vertex> edge in edges) {
126        // TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
127        float weight = GetWeight(edge); // TODO:  edge.Weight?
128        neighbors[edge.Target.Id] = weight;
129      }
130      return neighbors;
131    }
132    public Dictionary<long, float> GetNeighborsWithWeightReversed(long id) {
133      Dictionary<long, float> neighbors = new Dictionary<long, float>();
134      List<Edge<Vertex>> edges = GetInEdges(id);
135      foreach (Edge<Vertex> edge in edges) {
136        // TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
137        float weight = GetWeight(edge); // TODO:  edge.Weight?
138        neighbors[edge.Source.Id] = weight;
139      }
140      return neighbors;
141    }
142
143    public float GetWeight(Edge<Vertex> edge) {
144      //double distance = Utils.Distance(edge.Source.Logitude, edge.Source.Latitude,
145      //                                 edge.Target.Logitude, edge.Target.Latitude);
146
147      PointD s = new PointD(edge.Source.Logitude, edge.Source.Latitude);
148      PointD t = new PointD(edge.Target.Logitude, edge.Target.Latitude);
149      double distance = Utils.LocationDistance(s, t);
150
151      int speed = edge.GetMaxSpeed();
152      double weight = (distance / speed) * 60;
153      //double weight = (distance / speed) * 3.6;
154      //double weight = (distance / speed);
155      //double weight = distance;
156      return (float)weight;
157    }
158
159    public float EstimatedCosts(long sourceId, long targetId) {
160      Vertex source = GetVertex(sourceId);
161      Vertex target = GetVertex(targetId);
162      return EstimatedCosts(source, target);
163    }
164
165    public float EstimatedCosts(Vertex source, Vertex target) {
166      //double distance = Utils.Distance(source.Logitude, source.Latitude,
167      //                                 target.Logitude, target.Latitude);
168
169      PointD s = new PointD(source.Logitude, source.Latitude);
170      PointD t = new PointD(target.Logitude, target.Latitude);
171      double distance = Utils.LocationDistance(s, t);
172
173      //int speed = 130;
174      //int speed = 10;
175      int speed = 1;
176      double costs = (distance / speed) * 60;
177      //double costs = (distance / speed) * 3.6;
178      //double costs = (distance / speed);
179      //double costs = distance;
180      return (float)costs;
181    }
182  }
183}
Note: See TracBrowser for help on using the repository browser.