Ignore:
Timestamp:
Sep 21, 2010, 9:04:00 PM (11 years ago)
Author:
matkovic
Message:

-changed data structures, should improve the performance

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/StackFrameDijkstra/Dijkstra.cs

    r1928 r1931  
    44using System.Text;
    55using Wintellect.PowerCollections;
     6using System.Windows;
    67
    78namespace WorkspaceManager.View.VisualComponents.StackFrameDijkstra
    89{
    9 public class Dijkstra<T>  where T : Node<T> {
     10    public class Node : IComparable<Node>
     11    {
    1012
    11     private class State : NodeState<T>, IComparable<State> {
     13        public double Dist { get; set; }
     14        public Node previous { get; set; }
    1215
    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
    1434
    1535        private static int uniqueCounter;
    1636        protected readonly int uniqueIndex;
    1737
    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>();
    2043            uniqueIndex = ++uniqueCounter;
    2144        }
    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);
    2549            //if res and other is equal then apply different CompareTo() value (OrderedSet deletes any State if
    2650
    2751            if (res == 0)
    2852                return uniqueIndex.CompareTo(other.uniqueIndex);
    29              return res;
     53            return res;
    3054        }
    3155
     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        }
    3268
    3369    }
     70
     71    public class Dijkstra<T>  where T : Node {
     72
     73        public LinkedList<Node> findPath(IEnumerable<T> graph, T start, T goal) {
    3474   
    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>();
    3976
    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);
    5583            }
    5684
     85            while (unvisitedNodes.Count!=0 ) {
     86                var visitingNode = unvisitedNodes.RemoveFirst();
     87
     88               if (visitingNode.Dist == Double.PositiveInfinity) {
     89                    break;
     90                }
     91
    5792           
    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                }
    60107            }
    61108
    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;
    73110        }
    74 
    75         return null;
    76111    }
    77 }
    78112
    79113}
Note: See TracChangeset for help on using the changeset viewer.