source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/StackFrameDijkstra/Dijkstra.cs @ 1928

Last change on this file since 1928 was 1928, checked in by matkovic, 11 years ago

-Fixed some Collections issues

File size: 2.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using Wintellect.PowerCollections;
6
7namespace WorkspaceManager.View.VisualComponents.StackFrameDijkstra
8{
9public class Dijkstra<T>  where T : Node<T> {
10
11    private class State : NodeState<T>, IComparable<State> {
12
13        public double Dist {get;set;}
14
15        private static int uniqueCounter;
16        protected readonly int uniqueIndex;
17
18        public State(T node, State parent, double dist) : base(node, parent) {
19            this.Dist = dist;
20            uniqueIndex = ++uniqueCounter;
21        }
22       
23        public int CompareTo(State other) {
24            int res =  Dist.CompareTo(other.Dist);
25            //if res and other is equal then apply different CompareTo() value (OrderedSet deletes any State if
26
27            if (res == 0)
28                return uniqueIndex.CompareTo(other.uniqueIndex);
29             return res;
30        }
31
32
33    }
34   
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>();
39
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;
55            }
56
57           
58            if (goal.Equals(visitingNode.Node)) {
59                return visitingNode.makePath();
60            }
61
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            }
73        }
74
75        return null;
76    }
77}
78
79}
Note: See TracBrowser for help on using the repository browser.