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

using System;
using System.Collections.Generic;
using HeuristicLab.Problems.RoutePlanning.Osm;
namespace HeuristicLab.Problems.RoutePlanning.Graph {
  public class Graph : IGraph {
    private IDictionary<long, Vertex> vertices;
    private IDictionary<long, List<Edge<Vertex>>> adjacencyMap;
    private IDictionary<long, List<Edge<Vertex>>> incidenceMap;

    public Graph() {
      vertices = new Dictionary<long, Vertex>();
      adjacencyMap = new Dictionary<long, List<Edge<Vertex>>>();
      incidenceMap = new Dictionary<long, List<Edge<Vertex>>>();
    }

    public void AddVertex(Vertex vertex) {
      if (!vertices.ContainsKey(vertex.Id)) {
        vertices.Add(vertex.Id, vertex);
      }
    }

    public Vertex GetVertex(long id) {
      Vertex vertex = null;
      vertices.TryGetValue(id, out vertex);
      return vertex;
    }

    public List<Vertex> GetVertices() {
      return new List<Vertex>(vertices.Values);
    }

    public void AddEdge(long startId, long endId) {
      Vertex start = GetVertex(startId);
      if (start == null) throw new ArgumentException(string.Format("Invalid vertex id {0}", startId), "startId");
      Vertex end = GetVertex(startId);
      if (end == null) throw new ArgumentException(string.Format("Invalid vertex id {0}", endId), "endId");

      Edge<Vertex> edge = new Edge<Vertex>(start, end);
      //edge.Category = -1

      AddEdge(edge);
    }

    public void AddEdge(Edge<Vertex> edge) {
      if (!adjacencyMap.ContainsKey(edge.Source.Id)) {
        adjacencyMap.Add(edge.Source.Id, new List<Edge<Vertex>>());
      }
      adjacencyMap[edge.Source.Id].Add(edge);

      if (!incidenceMap.ContainsKey(edge.Target.Id)) {
        incidenceMap.Add(edge.Target.Id, new List<Edge<Vertex>>());
      }
      incidenceMap[edge.Target.Id].Add(edge);
    }

    public void RemoveEdge(long startId, long endId) {
      Edge<Vertex> edge = GetEdge(startId, endId);
      if (edge != null) {
        adjacencyMap[startId].Remove(edge);
        incidenceMap[endId].Remove(edge);
      }
    }

    public bool HasEdge(long startId, long endId) {
      Edge<Vertex> edge = GetEdge(startId, endId);
      return (edge != null);
    }

    public Edge<Vertex> GetEdge(long startId, long endId) {
      List<Edge<Vertex>> edges = adjacencyMap[startId];
      foreach (Edge<Vertex> edge in edges) {
        if (edge.Target.Id == endId) {
          return edge;
        }
      }
      return null;
    }

    public List<Edge<Vertex>> GetInEdges(long vertexId) {
      List<Edge<Vertex>> edges;
      if (incidenceMap.TryGetValue(vertexId, out edges)) {
        return edges;
      } else {
        return new List<Edge<Vertex>>();
      }
    }

    public int GetInDegree(long vertexId) {
      return incidenceMap[vertexId].Count;
    }

    public List<Edge<Vertex>> GetOutEdges(long vertexId) {
      List<Edge<Vertex>> edges;
      if (adjacencyMap.TryGetValue(vertexId, out edges)) {
        return edges;
      } else {
        return new List<Edge<Vertex>>();
      }

    }

    public int GetOutDegree(long vertexId) {
      return adjacencyMap[vertexId].Count;
    }

    public List<Edge<Vertex>> GetEdges(long vertexId) {
      List<Edge<Vertex>> result = new List<Edge<Vertex>>();
      foreach (Edge<Vertex> edge in GetInEdges(vertexId)) {
        if (!result.Contains(edge)) {
          result.Add(edge);
        }
      }
      foreach (Edge<Vertex> edge in GetOutEdges(vertexId)) {
        if (!result.Contains(edge)) {
          result.Add(edge);
        }
      }
      return result;
    }

    public Dictionary<long, float> GetNeighborsWithWeight(long id) {
      Dictionary<long, float> neighbors = new Dictionary<long, float>();
      List<Edge<Vertex>> edges = GetOutEdges(id);
      foreach (Edge<Vertex> edge in edges) {
        // TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
        float weight = GetWeight(edge); // TODO:  edge.Weight?
        neighbors[edge.Target.Id] = weight;
      }
      return neighbors;
    }
    public Dictionary<long, float> GetNeighborsWithWeightReversed(long id) {
      Dictionary<long, float> neighbors = new Dictionary<long, float>();
      List<Edge<Vertex>> edges = GetInEdges(id);
      foreach (Edge<Vertex> edge in edges) {
        // TODO: check if edge can be traversed (eg. highway tag for car roads, ...)
        float weight = GetWeight(edge); // TODO:  edge.Weight?
        neighbors[edge.Source.Id] = weight;
      }
      return neighbors;
    }

    public float GetWeight(Edge<Vertex> edge) {
      double distance = Utils.Distance(edge.Source.Logitude, edge.Source.Latitude,
                                       edge.Target.Logitude, edge.Target.Latitude);
      //double distance = Utils.LocationDistance(source.Node.Point, target.Node.Point);
      int speed = edge.GetMaxSpeed();
      double weight = (distance / speed) * 3.6;
      //double weight = (distance / speed);
      return (float)weight;
    }

    public float EstimatedCosts(long sourceId, long targetId) {
      Vertex source = GetVertex(sourceId);
      Vertex target = GetVertex(targetId);
      return EstimatedCosts(source, target);
    }

    public float EstimatedCosts(Vertex source, Vertex target) {
      double distance = Utils.Distance(source.Logitude, source.Latitude,
                                       target.Logitude, target.Latitude);
      //double distance = Utils.LocationDistance(source.Node.Point, target.Node.Point);
      int speed = 130;
      double costs = (distance / speed) * 3.6;
      //double costs = (distance / speed);
      return (float)costs;
    }
  }
}