Changeset 1931


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

-changed data structures, should improve the performance

Location:
trunk/CrypPlugins/WorkspaceManager
Files:
2 deleted
3 edited

Legend:

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

    r1928 r1931  
    1515using WorkspaceManager.View.Container;
    1616using System.Collections;
     17using WorkspaceManager.View.VisualComponents.StackFrameDijkstra;
    1718
    1819namespace WorkspaceManager.View.VisualComponents
     
    379380        }
    380381
    381         internal class Node : StackFrameDijkstra.Node<Node>
    382         {
    383             public Point Point { get; set; }
    384             public HashSet<Node> Vertices { get; private set; }
    385             public Node()
    386             {
    387                 Vertices = new HashSet<Node>();
    388             }
    389 
    390             public double traverseCost(Node dest)
    391             {
    392                 if (!Vertices.Contains(dest))
    393                     return Double.PositiveInfinity;
    394 
    395                 if (dest.Point.X == Point.X)
    396                     return Math.Abs(dest.Point.Y - Point.Y);
    397                 return Math.Abs(dest.Point.X - Point.X);
    398             }
    399 
    400             public IEnumerable<Node> neighbors()
    401             {
    402                 return Vertices;
    403             }
    404 
    405  
    406         }
    407 
    408382        private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList, QuadTreeLib.QuadTree<FakeNode> quadTree)
    409383        {
     
    447421            nodeList.Add(endNode);
    448422
    449             QuadTreeLib.QuadTree<FakeNode> quadTree = new QuadTreeLib.QuadTree<FakeNode>(new System.Drawing.RectangleF(0,0,(float)parent.ActualWidth,(float) parent.ActualHeight));
     423            float actualWidth =(float) parent.ActualWidth, actualHeight =(float) parent.ActualWidth;
     424            //Consider zoom factor
     425            QuadTreeLib.QuadTree<FakeNode> quadTree = new QuadTreeLib.QuadTree<FakeNode>
     426                (new System.Drawing.RectangleF(-actualWidth, -actualHeight, actualWidth*5, actualHeight*5));
    450427
    451428            //foreach (var element in parent.Children)
  • 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}
  • trunk/CrypPlugins/WorkspaceManager/WorkspaceManager.csproj

    r1927 r1931  
    172172    <Compile Include="View\VisualComponents\CryptoLineView\QuadTree\QuadTreeNode.cs" />
    173173    <Compile Include="View\VisualComponents\CryptoLineView\StackFrameDijkstra\Dijkstra.cs" />
    174     <Compile Include="View\VisualComponents\CryptoLineView\StackFrameDijkstra\Node.cs" />
    175     <Compile Include="View\VisualComponents\CryptoLineView\StackFrameDijkstra\NodeState.cs" />
    176174    <Compile Include="View\VisualComponents\DataPresentation.xaml.cs">
    177175      <DependentUpon>DataPresentation.xaml</DependentUpon>
Note: See TracChangeset for help on using the changeset viewer.