Changeset 8461

Timestamp:

08/09/12 16:17:37 (12 years ago)

Author:

spimming

Message:

#1894:

• Implemented interface IGraph in Graph
• Equals method in vertex modified
• Equals method in Edge implemented
• New algorithm version for IGraph

Location:

branches/RoutePlanning

Files:

• HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs (added)
• HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/Edge.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs (modified) (5 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/IGraph.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/Vertex.cs (modified) (1 diff)

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

@@ -60 +60 @@
     <Compile Include="AStarAlgorithmV2.cs" />
     <Compile Include="BidirectionalDijkstraAlgorithm.cs" />
+    <Compile Include="DijkstraAlgorithmV2.cs" />
     <Compile Include="DijkstraAlgorithm.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Edge.cs

@@ -32 +32 @@
       return string.Format("{0}->{1}", this.Source, this.Target);
     }
+
+    public override bool Equals(object obj) {
+      if (obj is Edge<Vertex>) {
+        Edge<Vertex> e = (obj as Edge<Vertex>);
+        return (this.source.Equals(e.source)) && (this.target.Equals(e.target));
+      }
+      return false;
+    }
+
+    public override int GetHashCode() {
+      return source.GetHashCode() ^ target.GetHashCode();
+    }
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs

@@ -3 +3 @@
 using System.Collections.Generic;
 namespace HeuristicLab.Problems.RoutePlanning.Graph {
-  public class Graph {
+  public class Graph : IGraph {
     private IDictionary<long, Vertex> vertices;
     private IDictionary<long, List<Edge<Vertex>>> adjacencyMap;
@@ -11 +11 @@
       vertices = new Dictionary<long, Vertex>();
       adjacencyMap = new Dictionary<long, List<Edge<Vertex>>>();
+      incidenceMap = new Dictionary<long, List<Edge<Vertex>>>();
     }
 
     public void AddVertex(Vertex vertex) {
-      vertices.Add(vertex.Id, vertex);
+      if (!vertices.ContainsKey(vertex.Id)) {
+        vertices.Add(vertex.Id, vertex);
+      }
     }
 
@@ -32 +35 @@
       //edge.Category = -1
 
-      if (adjacencyMap[start.Id] == null) {
-        adjacencyMap[start.Id] = new List<Edge<Vertex>>();
+      AddEdge(edge);
+    }
+
+    public void AddEdge(Edge<Vertex> edge) {
+      if (!adjacencyMap.ContainsKey(edge.Source.Id)) {
+        adjacencyMap.Add(edge.Source.Id, new List<Edge<Vertex>>());
       }
-      adjacencyMap[start.Id].Add(edge);
+      adjacencyMap[edge.Source.Id].Add(edge);
 
-      if (incidenceMap[end.Id] == null) {
-        incidenceMap[end.Id] = new List<Edge<Vertex>>();
+      if (!incidenceMap.ContainsKey(edge.Target.Id)) {
+        incidenceMap.Add(edge.Target.Id, new List<Edge<Vertex>>());
       }
-      incidenceMap[end.Id].Add(edge);
+      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);
     }
 
@@ -55 +75 @@
     public List<Edge<Vertex>> GetInEdges(long vertexId) {
       return incidenceMap[vertexId];
+    }
 
+    public int GetInDegree(long vertexId) {
+      return incidenceMap[vertexId].Count;
     }
 
@@ -61 +84 @@
       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;
+    }
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/IGraph.cs

@@ -2 +2 @@
 using System.Collections.Generic;
 namespace HeuristicLab.Problems.RoutePlanning.Graph {
-  interface IGraph {
+  public interface IGraph {
     void AddVertex(Vertex vertex);
     Vertex GetVertex(long id);
     void AddEdge(long startId, long endId);
+    void AddEdge(Edge<Vertex> edge);
     void RemoveEdge(long startId, long endId);
     bool HasEdge(long startId, long endId);

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Vertex.cs

@@ -50 +50 @@
       if (obj is Vertex) {
         Vertex v = (obj as Vertex);
-        return this.Equals(v);
+        return (this.id == v.id); //TODO:
       }
       return false;