C# Dijkstra

Implementation

Uses the HeapPriorityQueue.
Code on Github

//
//  Copyright 2012  Patrick Uhlmann
//
//    Licensed under the Apache License, Version 2.0 (the "License");
//    you may not use this file except in compliance with the License.
//    You may obtain a copy of the License at
//
//        http://www.apache.org/licenses/LICENSE-2.0
//
//    Unless required by applicable law or agreed to in writing, software
//    distributed under the License is distributed on an "AS IS" BASIS,
//    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//    See the License for the specific language governing permissions and
//    limitations under the License.
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;
using System.Linq;

namespace Uhlme
{
    /// <summary>
    /// Dijkstra
    /// Some operations are implemented using a Dictionary. In order for them to run fast T should have a good hash
    /// </summary>
    public class Dijkstra<T>
    {
        public AdjacencyNode<T> Source {
            get;
            private set;
        }
        
        private Dictionary<AdjacencyNode<T>, AdjacencyNode<T>> PreviousNode {
            get;
            set ;
        }
        
        /// <summary>
        /// Runs the Dijkstra algorithm which calculates the shortest paths from the source to any other node
        /// which is reachable from there.
        /// 
        /// If this method is called multiple times with the same source it does only calculate the paths the first time
        /// 
        /// Exceptions:
        /// ArgumentException if the nodes Enumerable is null, the source is null or the source is not part of the graph (the nodes)
        /// </summary>
        public void Run (IEnumerable<AdjacencyNode<T>> nodes, AdjacencyNode<T> source)
        {
            if (nodes == null || source == null) {
                throw new ArgumentException ("Nodes Enumerable or Source is null");
            }
            
            if (Source != null && Source.Equals(source)) {
                return;
            }
            
            /**
             * Initialize the Algorithm
             */
            Source = source;
            
            // Holds the shortest distance between the source and the node
            Dictionary<AdjacencyNode<T>, int> Distance = new Dictionary<AdjacencyNode<T>, int> ();
            // Holds the node from which we need to go to the current node if we are taking the shortest path
            PreviousNode = new Dictionary<AdjacencyNode<T>, AdjacencyNode<T>> ();
            // Fast Access to the Node (of the Nodes to inspect) which has the shortest distance and thus needs to be processed next
            // if we processed all nodes in that queue or the remaining ones are not reachable the algorithm is finished
            HeapPriorityQueue<AdjacencyNode<T>> DistanceQueue = new HeapPriorityQueue<AdjacencyNode<T>> ();
            
            foreach (AdjacencyNode<T> n in nodes) {
                // previous nodes are unknown at the start
                PreviousNode.Add (n, null);
                // distance is assumed to be the maximum possible value. Therefore it can be improved if we find a shorter one
                Distance.Add (n, int.MaxValue);
                DistanceQueue.Enqueue (n, int.MaxValue);
            }
            
            if (!DistanceQueue.Contains (source)) {
                throw new ArgumentException("The source is not part of the graph (nodes)");
            }
            
            /**
             * Execute the Algorithm
             */
            Distance [Source] = 0;
            DistanceQueue.UpdatePriority(Source, 0);
            
            while (!DistanceQueue.IsEmpty()) {
                // The nearest node is a node which has never been reached (otherwise its path would have been improved)
                // This means all other nodes can also not be reached and our algorithm is finished...
                if (DistanceQueue.PeekPriority() == int.MaxValue) {
                    break;
                }
                
                AdjacencyNode<T> nearestNode = DistanceQueue.Dequeue();
                
                // Check all neighbours that still need to be inspected
                foreach (AdjacencyNode<T> neighbour in nearestNode.AdjacentNodes) {
                    if (!DistanceQueue.Contains (neighbour)) {
                        continue;
                    }
                    
                    // calculate distance with the currently inspected neighbour
                    int NeighbourDist = Distance [nearestNode] + 1;
                    
                    // set the neighbour as shortest if it is better than the currently known shortest distance
                    if (NeighbourDist < Distance [neighbour]) {
                        Distance [neighbour] = NeighbourDist;
                        DistanceQueue.UpdatePriority(neighbour, NeighbourDist);
                        PreviousNode [neighbour] = nearestNode;
                    }
                }
            }
        }
        
        /// <summary>
        /// Gets the path from the source to the destination. It does include the destination as its last point. The first point
        /// is not the source but the first neighbour of it.
        /// 
        /// Operation executes in O(n)
        /// 
        /// Note: before we can get a path we need to run the algorithm
        /// </summary>
        public LinkedList<T> GetShortestPathTo (T destination)
        {
            if (Source == null) {
                throw new InvalidOperationException("You need to Run the algorithm first before calculating paths...");
            }
            
            AdjacencyNode<T> destinationNode = new AdjacencyNode<T> (destination);
            
            // building path going back from the destination to the source always taking the nearest node
            LinkedList<T> path = new LinkedList<T> ();
            path.AddFirst (destinationNode.Value);
            
            while (PreviousNode[destinationNode] != null) {
                destinationNode = PreviousNode [destinationNode];
                path.AddFirst (destinationNode.Value);
            }
            
            path.RemoveFirst ();
            
            return path;
        }
    }
}

Graph Classes

//
//  Copyright 2012  Patrick Uhlmann
//
//    Licensed under the Apache License, Version 2.0 (the "License");
//    you may not use this file except in compliance with the License.
//    You may obtain a copy of the License at
//
//        http://www.apache.org/licenses/LICENSE-2.0
//
//    Unless required by applicable law or agreed to in writing, software
//    distributed under the License is distributed on an "AS IS" BASIS,
//    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//    See the License for the specific language governing permissions and
//    limitations under the License.
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;

namespace Uhlme
{
    /// <summary>
    /// Undirected, unweightened graph.
    /// Each node and edge can only be added once. 
    /// If it gets added a second time it does just get ignored.
    /// 
    /// Some operations are implemented using a Dictionary. In order for them to run fast T should have a good hash
    /// </summary>
    public class AdjacencyGraph<T>
    {
        private Dictionary<T, AdjacencyNode<T>> nodes = new Dictionary<T, AdjacencyNode<T>> ();

        public int NodeCount {
            get {
                return nodes.Count;
            }
        }

        public IEnumerable<AdjacencyNode<T>> Nodes {
            get {
                return nodes.Values;
            }
        }

        /// <summary>
        /// If we add an edge it checks if the node as already there, otherwise it adds the node.
        /// 
        /// Operation: O(1)
        /// </summary>
        public void AddEdge (T node1, T node2)
        {
            var startNode = nodes.ContainsKey(node1) ? nodes[node1] : null;
            if (startNode == null) {
                startNode = new AdjacencyNode<T>(node1);
                AddNodeIfNotAlreadyContained (startNode);
            }

            var endNode = nodes.ContainsKey(node2) ? nodes[node2] : null;
            if (endNode == null) {
                endNode = new AdjacencyNode<T>(node2);
                AddNodeIfNotAlreadyContained(endNode);
            }

            startNode.AddEdgeTo(endNode);
            endNode.AddEdgeTo(startNode);
        }

        private void AddNodeIfNotAlreadyContained (AdjacencyNode<T> node)
        {
            if (!nodes.ContainsKey(node.Value)) {
                nodes.Add (node.Value, node);
            }
        }
                
        /// <summary>
        /// Removes the edge from nodes that are already part of the graph
        /// If the very last edge of a node to another one is removed the node is removed as well
        /// 
        /// Operation: O(1)
        /// </summary>
        public bool RemoveEdge (T start, T end)
        {
            var startNode = nodes.ContainsKey(start) ? nodes[start] : null;
            var endNode = nodes.ContainsKey(end) ? nodes[end] : null;

            if (startNode == null || endNode == null) {
                return false;
            }

            startNode.RemoveEdgeTo (endNode);

            if (startNode.EdgeCount == 0) {
                nodes.Remove(start);
            }

            endNode.RemoveEdgeTo (startNode);
            if (endNode.EdgeCount == 0) {
                nodes.Remove(end);
            }

            return true;
        }
        
        /// <summary>
        /// If we remove a node the associated edges are removed as well
        /// 
        /// Operation: O(m) where m is the number of edges
        /// </summary>
        public bool RemoveNode (T node)
        {
            var nodeToRemove = nodes.ContainsKey(node) ? nodes[node] : null;
            if (nodeToRemove == null) {
                return false;
            }

            foreach (AdjacencyNode<T> n in nodeToRemove.AdjacentNodes) {
                n.RemoveEdgeTo(nodeToRemove);
            }

            nodes.Remove (node);

            return true;
        }

        /// <summary>
        /// Operation: O(1)
        /// </summary>
        public bool ContainsNode (T node)
        {
            return nodes.ContainsKey(node);
        }

        /// <summary>
        /// Operation: O(1)
        /// </summary>
        public bool AreDirectlyConnected (T node1, T node2)
        {
            var startNode = nodes.ContainsKey(node1) ? nodes[node1] : null;
            var endNode = nodes.ContainsKey(node2) ? nodes[node2] : null;

            if (startNode == null || endNode == null) {
                return false;
            }

            return startNode.HasEdgeTo(endNode);
        }
    }
}

//
//  Copyright 2012  Patrick Uhlmann
//
//    Licensed under the Apache License, Version 2.0 (the "License");
//    you may not use this file except in compliance with the License.
//    You may obtain a copy of the License at
//
//        http://www.apache.org/licenses/LICENSE-2.0
//
//    Unless required by applicable law or agreed to in writing, software
//    distributed under the License is distributed on an "AS IS" BASIS,
//    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//    See the License for the specific language governing permissions and
//    limitations under the License.
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections.ObjectModel;
using System.Linq;

namespace Uhlme
{
    /// <summary>
    /// Adjacency node
    /// Some operations are implemented using a Dictionary. In order for them to run fast T should have a good hash
    /// </summary>
    public class AdjacencyNode<T>
    {
        private Dictionary<T, AdjacencyNode<T>> adjacentNodes = new Dictionary<T, AdjacencyNode<T>> ();

        public AdjacencyNode (T value)
        {
            Value = value;
        }
        
        public T Value {
            get;
            private set;
        }

        public int EdgeCount {
            get {
                return adjacentNodes.Count;
            }
        }

        public IEnumerable<AdjacencyNode<T>> AdjacentNodes {
            get {
                return adjacentNodes.Values;
            }
        }

        /// <summary>
        /// Operation: O(1)
        /// </summary>
        public void AddEdgeTo (AdjacencyNode<T> node)
        {
            if (!HasEdgeTo(node)) {
                adjacentNodes.Add(node.Value, node);
            }
        }

        /// <summary>
        /// Operation: O(1)
        /// </summary>
        public void RemoveEdgeTo (AdjacencyNode<T> node)
        {
            adjacentNodes.Remove(node.Value);
        }

        /// <summary>
        /// Operation: O(1)
        /// </summary>
        public bool HasEdgeTo (AdjacencyNode<T> node)
        {
            return adjacentNodes.ContainsKey(node.Value);
        }
        
        public override bool Equals (System.Object obj)
        {
            if (obj == null) {
                return false;
            }
            
            AdjacencyNode<T> f = obj as AdjacencyNode<T>;
            if (f == null) {
                return false;
            }
            
            return Equals (f);
        }
        
        public bool Equals (AdjacencyNode<T> f)
        {
            if (f == null) {
                return false;
            }
            
            return (Value.Equals (f.Value));
        }
        
        public override int GetHashCode ()
        {
            return Value.GetHashCode ();
        }

        public override string ToString ()
        {
            return Value.ToString();
        }
    }
}