Changeset 1931 for trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/StackFrameDijkstra/Dijkstra.cs
 Timestamp:
 Sep 21, 2010, 9:04:00 PM (11 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/StackFrameDijkstra/Dijkstra.cs
r1928 r1931 4 4 using System.Text; 5 5 using Wintellect.PowerCollections; 6 using System.Windows; 6 7 7 8 namespace WorkspaceManager.View.VisualComponents.StackFrameDijkstra 8 9 { 9 public class Dijkstra<T> where T : Node<T> { 10 public class Node : IComparable<Node> 11 { 10 12 11 private class State : NodeState<T>, IComparable<State> { 13 public double Dist { get; set; } 14 public Node previous { get; set; } 12 15 13 public double Dist {get;set;} 16 public Point Point { get; set; } 17 public HashSet<Node> Vertices { get; private set; } 18 19 public double traverseCost(Node dest) 20 { 21 if (!Vertices.Contains(dest)) 22 return Double.PositiveInfinity; 23 24 if (dest.Point.X == Point.X) 25 return Math.Abs(dest.Point.Y  Point.Y); 26 return Math.Abs(dest.Point.X  Point.X); 27 } 28 29 public IEnumerable<Node> neighbors() 30 { 31 return Vertices; 32 } 33 14 34 15 35 private static int uniqueCounter; 16 36 protected readonly int uniqueIndex; 17 37 18 public State(T node, State parent, double dist) : base(node, parent) { 19 this.Dist = dist; 38 public Node() 39 { 40 this.Dist = Double.PositiveInfinity; 41 this.previous = null; 42 this.Vertices = new HashSet<Node>(); 20 43 uniqueIndex = ++uniqueCounter; 21 44 } 22 23 public int CompareTo(State other) { 24 int res = Dist.CompareTo(other.Dist); 45 46 public int CompareTo(Node other) 47 { 48 int res = Dist.CompareTo(other.Dist); 25 49 //if res and other is equal then apply different CompareTo() value (OrderedSet deletes any State if 26 50 27 51 if (res == 0) 28 52 return uniqueIndex.CompareTo(other.uniqueIndex); 29 53 return res; 30 54 } 31 55 56 public LinkedList<Node> makePath() 57 { 58 LinkedList<Node> result = new LinkedList<Node>(); 59 Node s = this; 60 while (s != null) 61 { 62 result.AddFirst(s); 63 s = s.previous; 64 } 65 66 return result; 67 } 32 68 33 69 } 70 71 public class Dijkstra<T> where T : Node { 72 73 public LinkedList<Node> findPath(IEnumerable<T> graph, T start, T goal) { 34 74 35 public LinkedList<T> findPath(IEnumerable<T> graph, T start, T goal) { 36 37 Dictionary<T, State> states = new Dictionary<T, State>(); 38 OrderedSet<State> unvisitedNodes = new OrderedSet<State>(); 75 OrderedSet<T> unvisitedNodes = new OrderedSet<T>(); 39 76 40 foreach(T n in graph) { 41 var state = new State(n, null, Double.PositiveInfinity); 42 if(n.Equals(start)) 43 { 44 state.Dist = 0; 45 } 46 states.Add(n, state); 47 unvisitedNodes.Add(state); 48 } 49 50 while (unvisitedNodes.Count!=0 ) { 51 var visitingNode = unvisitedNodes.RemoveFirst(); 52 53 if (visitingNode.Dist == Double.PositiveInfinity) { 54 break; 77 foreach(T n in graph) { 78 if(n.Equals(start)) 79 { 80 n.Dist = 0; 81 } 82 unvisitedNodes.Add(n); 55 83 } 56 84 85 while (unvisitedNodes.Count!=0 ) { 86 var visitingNode = unvisitedNodes.RemoveFirst(); 87 88 if (visitingNode.Dist == Double.PositiveInfinity) { 89 break; 90 } 91 57 92 58 if (goal.Equals(visitingNode.Node)) { 59 return visitingNode.makePath(); 93 if (goal.Equals(visitingNode)) { 94 return visitingNode.makePath(); 95 } 96 97 foreach (T v in visitingNode.neighbors()) { 98 double altPathCost = visitingNode.Dist + visitingNode.traverseCost(v); 99 100 if (altPathCost < v.Dist) { 101 unvisitedNodes.Remove(v); 102 v.Dist = altPathCost; 103 v.previous = visitingNode; 104 unvisitedNodes.Add(v); 105 } 106 } 60 107 } 61 108 62 foreach (T v in visitingNode.Node.neighbors()) { 63 State vState = states[v]; 64 double altPathCost = visitingNode.Dist + visitingNode.Node.traverseCost(v); 65 66 if (altPathCost < vState.Dist) { 67 unvisitedNodes.Remove(vState); 68 vState.Dist = altPathCost; 69 vState.previous = visitingNode; 70 unvisitedNodes.Add(vState); 71 } 72 } 109 return null; 73 110 } 74 75 return null;76 111 } 77 }78 112 79 113 }
Note: See TracChangeset
for help on using the changeset viewer.