### 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(); } } }