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

using System;
using System.Collections.Generic;
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 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) {
      return incidenceMap[vertexId];
    }

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

    public List<Edge<Vertex>> GetOutEdges(long vertexId) {
      return adjacencyMap[vertexId];
    }

    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 = 1; // 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 = 1; // TODO:  edge.Weight?
        neighbors[edge.Source.Id] = weight;
      }
      return neighbors;
    }
  }
}