1 


2  using System;


3  using System.Collections.Generic;


4  using HeuristicLab.Problems.RoutePlanning.Osm;


5  namespace 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  }

