Free cookie consent management tool by TermsFeed Policy Generator

# Changeset 8640

Ignore:
Timestamp:
09/13/12 10:34:51 (12 years ago)
Message:
• Included costCalculator in a star search
• restructured and renamed Dijkstra algorithm
Location:
branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3
Files:
1 deleted
4 edited

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

 r8516 using HeuristicLab.Algorithms.GraphRouting.Interfaces; using HeuristicLab.Problems.RoutePlanning.Interfaces; using HeuristicLab.Problems.RoutePlanning.RoutingGraph; namespace HeuristicLab.Algorithms.GraphRouting { public class AStarAlgorithmV3 : IRouter { private IGraph graph; private ICostCalculator costCalculator; private Dictionary distances; private Dictionary openListLookup; public AStarAlgorithmV3(IGraph graph) { public AStarAlgorithmV3(IGraph graph) : this(graph, new TravelTimeCostCalculator()) { } public AStarAlgorithmV3(IGraph graph, ICostCalculator costCalc) { this.graph = graph; this.costCalculator = costCalc; } distances.Add(currentNode, 0); int i = 0; while (openList.Count > 0) { NodeData data = openList.Min; //Console.Write(i + ": (" + openList.Count + "/"); openList.Remove(data); //Console.Write(openList.Count + ") - (" + openListLookup.Count + "/"); openListLookup.Remove(data.Node); //Console.WriteLine(openListLookup.Count + ")"); currentNode = data.Node; if (currentNode == targetNodeId) { return ReconstructPath(currentNode).ToArray(); } //if (openList.Count != openListLookup.Count) { //  Console.WriteLine(); //} else { //  Console.Write("."); //} Dictionary currentNeighbors = graph.GetNeighborsWithWeight(currentNode); predecessors[neighbor.Key] = currentNode; float f = costsFromStart + graph.EstimatedCosts(neighbor.Key, targetNodeId); Vertex vertNeigh = graph.GetVertex(neighbor.Key); Vertex vertTarget = graph.GetVertex(targetNodeId); float f = costsFromStart + costCalculator.EstimatedCosts(vertNeigh, vertTarget); if (openListLookup.ContainsKey(neighbor.Key)) { NodeData newNode = new NodeData(neighbor.Key, f); openList.Add(newNode); openList.Add(newNode);  // wenn f bereits vorhanden -> kein add: openList.Contains(new NodeData(123, 0.2973786f)) openListLookup.Add(newNode.Node, newNode); } closedList.Add(currentNode); closedListLookup.Add(currentNode); i++; } throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
• ## branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs

 r8539 using System.Collections.Generic; using HeuristicLab.Algorithms.GraphRouting.Interfaces; using HeuristicLab.Problems.RoutePlanning.Interfaces; using HeuristicLab.Algorithms.GraphRouting.PriorityQueues; using HeuristicLab.Problems.RoutePlanning.Interfaces; namespace HeuristicLab.Algorithms.GraphRouting { public class DijkstraNoDecAlgorithm : IRouter { public long[] Calculate(long sourceNodeId, long targetNodeId) { unvisitedNodes = new BinHeap(1000000);      // unvisited unvisitedNodes = new NaivePriorityQueue(); //unvisitedNodes = new BinaryHeap(1000000);      // unvisited //unvisitedNodes = new BinomialHeap();    // unvisited //unvisitedNodes = new BinaryHeap(float.MaxValue, float.MinValue, 1000000);   // unvisited //unvisitedNodes = new BinaryHeapV2(float.MaxValue, float.MinValue, 1000000);   // unvisited //unvisitedNodes = new BinaryHeapV3(float.MaxValue, float.MinValue, 1000000);   // unvisited //unvisitedNodes = new Heap4(float.MaxValue, float.MinValue, 1000000);   // unvisited //unvisitedNodes = new FibonacciHeap();   // unvisited distances = new Dictionary(); predecessors = new Dictionary(); currentWeight = data.Key; //-------------- //Logger.LogToFile("cn = " + currentNode + " (" + currentWeight + ")"); //-------------- if (currentNode == targetNodeId) { break; RelaxNeighbors(currentNode, currentWeight); } //-------------- //Logger.LogToFile(""); //-------------- } predecessors[neighbor.Key] = nodeId; unvisitedNodes.Insert(totalWeight, neighbor.Key); //-------------- //Logger.LogToFile("    neigb:" + neighbor.Key + " (" + totalWeight + ")"); //-------------- } }
• ## branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

 r8546
• ## branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs

 r8572 min = n; } else { // concateneate the root list (becoming left sibling of root) n.Right = min; n.Left = min.Left; n.Right.Left = n; n.Left.Right = n; // update point of minimum if necessary if (n.Key.CompareTo(min.Key) < 0) { min = n; private void Link(HeapNode y, HeapNode z) { // remove y from the root list y.Left.Right = y.Right; y.Right.Left = y.Left; // make y a child of x, ... y.Parent = z; if (z.Child == null) { y.Right.Left = y; } // ... incrementing degree[x] z.Degree++; y.Mark = false; private void Consolidate() { //TODO: explain magic number HeapNode[] A = new HeapNode[45]; int dn = (int)Math.Floor(Math.Log(size) / Math.Log(2)) + 1; // log2size[Heap] HeapNode[] A = new HeapNode[dn];  // consolidation array HeapNode start = min; HeapNode w = min; // for each node w in the root list do { HeapNode x = w; min = null; for (int i = 0; i < 45; i++) { // find the new minimum key for (int i = 0; i < dn; i++) { if (A[i] != null) { HeapNode n = A[i];
Note: See TracChangeset for help on using the changeset viewer.