Changeset 8640


Ignore:
Timestamp:
09/13/12 10:34:51 (10 years ago)
Author:
spimming
Message:

#1894:

  • Included costCalculator in a star search
  • restructured and renamed Dijkstra algorithm
  • Added code comments to FibonacciHeap
Location:
branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3
Files:
2 added
1 deleted
4 edited

Legend:

Unmodified
Added
Removed
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs

    r8516 r8640  
    44using HeuristicLab.Algorithms.GraphRouting.Interfaces;
    55using HeuristicLab.Problems.RoutePlanning.Interfaces;
     6using HeuristicLab.Problems.RoutePlanning.RoutingGraph;
    67namespace HeuristicLab.Algorithms.GraphRouting {
    78  public class AStarAlgorithmV3 : IRouter {
    89    private IGraph graph;
     10    private ICostCalculator costCalculator;
    911
    1012    private Dictionary<long, float> distances;
     
    1517    private Dictionary<long, NodeData> openListLookup;
    1618
    17     public AStarAlgorithmV3(IGraph graph) {
     19    public AStarAlgorithmV3(IGraph graph)
     20      : this(graph, new TravelTimeCostCalculator()) {
     21    }
     22
     23    public AStarAlgorithmV3(IGraph graph, ICostCalculator costCalc) {
    1824      this.graph = graph;
     25      this.costCalculator = costCalc;
    1926    }
    2027
     
    3643      distances.Add(currentNode, 0);
    3744
     45      int i = 0;
    3846      while (openList.Count > 0) {
     47
    3948        NodeData data = openList.Min;
     49        //Console.Write(i + ": (" + openList.Count + "/");
    4050        openList.Remove(data);
     51        //Console.Write(openList.Count + ") - (" + openListLookup.Count + "/");
    4152        openListLookup.Remove(data.Node);
     53        //Console.WriteLine(openListLookup.Count + ")");
    4254        currentNode = data.Node;
    4355        if (currentNode == targetNodeId) {
    4456          return ReconstructPath(currentNode).ToArray();
    4557        }
     58
     59        //if (openList.Count != openListLookup.Count) {
     60        //  Console.WriteLine();
     61        //} else {
     62        //  Console.Write(".");
     63        //}
    4664
    4765        Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(currentNode);
     
    5876          predecessors[neighbor.Key] = currentNode;
    5977
    60           float f = costsFromStart + graph.EstimatedCosts(neighbor.Key, targetNodeId);
     78          Vertex vertNeigh = graph.GetVertex(neighbor.Key);
     79          Vertex vertTarget = graph.GetVertex(targetNodeId);
     80          float f = costsFromStart + costCalculator.EstimatedCosts(vertNeigh, vertTarget);
    6181
    6282          if (openListLookup.ContainsKey(neighbor.Key)) {
     
    6686
    6787          NodeData newNode = new NodeData(neighbor.Key, f);
    68           openList.Add(newNode);
     88          openList.Add(newNode);  // wenn f bereits vorhanden -> kein add: openList.Contains(new NodeData(123, 0.2973786f))
    6989          openListLookup.Add(newNode.Node, newNode);
    7090        }
    7191        closedList.Add(currentNode);
    7292        closedListLookup.Add(currentNode);
     93        i++;
    7394      }
    7495      throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs

    r8539 r8640  
    33using System.Collections.Generic;
    44using HeuristicLab.Algorithms.GraphRouting.Interfaces;
     5using HeuristicLab.Problems.RoutePlanning.Interfaces;
    56using HeuristicLab.Algorithms.GraphRouting.PriorityQueues;
    6 using HeuristicLab.Problems.RoutePlanning.Interfaces;
    77namespace HeuristicLab.Algorithms.GraphRouting {
    88  public class DijkstraNoDecAlgorithm : IRouter {
     
    1919
    2020    public long[] Calculate(long sourceNodeId, long targetNodeId) {
    21       unvisitedNodes = new BinHeap<float, long>(1000000);      // unvisited
     21      unvisitedNodes = new NaivePriorityQueue<float, long>();
     22      //unvisitedNodes = new BinaryHeap<float, long>(1000000);      // unvisited
    2223      //unvisitedNodes = new BinomialHeap<float, long>();    // unvisited
    23       //unvisitedNodes = new BinaryHeap<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
     24      //unvisitedNodes = new BinaryHeapV2<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
     25      //unvisitedNodes = new BinaryHeapV3<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
     26      //unvisitedNodes = new Heap4<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
     27      //unvisitedNodes = new FibonacciHeap<float, long>();   // unvisited
    2428      distances = new Dictionary<long, float>();
    2529      predecessors = new Dictionary<long, long>();
     
    4145        currentWeight = data.Key;
    4246
     47        //--------------
     48        //Logger.LogToFile("cn = " + currentNode + " (" + currentWeight + ")");
     49        //--------------
     50
    4351        if (currentNode == targetNodeId) {
    4452          break;
     
    4957          RelaxNeighbors(currentNode, currentWeight);
    5058        }
     59
     60        //--------------
     61        //Logger.LogToFile("");
     62        //--------------
    5163      }
    5264
     
    6779          predecessors[neighbor.Key] = nodeId;
    6880          unvisitedNodes.Insert(totalWeight, neighbor.Key);
     81
     82          //--------------
     83          //Logger.LogToFile("    neigb:" + neighbor.Key + " (" + totalWeight + ")");
     84          //--------------
    6985        }
    7086      }
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

    r8546 r8640  
    6161    <Compile Include="AStarAlgorithmV4.cs" />
    6262    <Compile Include="AStarAlgorithmV5.cs" />
     63    <Compile Include="DijkstraAlgorithm.cs" />
    6364    <Compile Include="DijkstraNoDecAlgorithm.cs" />
    64     <Compile Include="DijkstraAlgorithmV2.cs" />
     65    <Compile Include="NaiveDijkstraAlgorithm.cs" />
    6566    <Compile Include="GraphRoutingAlgorithm.cs" />
    6667    <Compile Include="Interfaces\IHeap.cs" />
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs

    r8572 r8640  
    4747        min = n;
    4848      } else {
     49        // concateneate the root list (becoming left sibling of root)
    4950        n.Right = min;
    5051        n.Left = min.Left;
    5152        n.Right.Left = n;
    5253        n.Left.Right = n;
     54        // update point of minimum if necessary
    5355        if (n.Key.CompareTo(min.Key) < 0) {
    5456          min = n;
     
    103105
    104106    private void Link(HeapNode y, HeapNode z) {
     107      // remove y from the root list
    105108      y.Left.Right = y.Right;
    106109      y.Right.Left = y.Left;
    107110
     111      // make y a child of x, ...
    108112      y.Parent = z;
    109113      if (z.Child == null) {
     
    117121        y.Right.Left = y;
    118122      }
     123
     124      // ... incrementing degree[x]
    119125      z.Degree++;
    120126      y.Mark = false;
     
    122128
    123129    private void Consolidate() {
    124       //TODO: explain magic number
    125       HeapNode[] A = new HeapNode[45];
     130      int dn = (int)Math.Floor(Math.Log(size) / Math.Log(2)) + 1; // log2size[Heap]
     131      HeapNode[] A = new HeapNode[dn];  // consolidation array
    126132      HeapNode start = min;
    127133      HeapNode w = min;
    128134
     135      // for each node w in the root list
    129136      do {
    130137        HeapNode x = w;
     
    157164      min = null;
    158165
    159       for (int i = 0; i < 45; i++) {
     166      // find the new minimum key
     167      for (int i = 0; i < dn; i++) {
    160168        if (A[i] != null) {
    161169          HeapNode n = A[i];
Note: See TracChangeset for help on using the changeset viewer.