Dijsktra.cs

Go to the documentation of this file.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Satsuma
{
    public enum DijkstraMode
    {
        Sum,

        Maximum
    }

    public sealed class Dijkstra
    {
        public IGraph Graph { get; private set; }
        public Func<Arc, double> Cost { get; private set; }

        public DijkstraMode Mode { get; private set; }
        public double NullCost { get; private set; }

        private readonly Dictionary<Node, double> distance;
        private readonly Dictionary<Node, Arc> parentArc;
        private readonly PriorityQueue<Node, double> priorityQueue;

        public Dijkstra(IGraph graph, Func<Arc, double> cost, DijkstraMode mode)
        {
            Graph = graph;
            Cost = cost;
            Mode = mode;
            NullCost = (mode == DijkstraMode.Sum ? 0 : double.NegativeInfinity);

            distance = new Dictionary<Node, double>();
            parentArc = new Dictionary<Node, Arc>();
            priorityQueue = new PriorityQueue<Node, double>();
        }

        private void ValidateCost(double c)
        {
            if (Mode == DijkstraMode.Sum && c < 0)
                throw new InvalidOperationException("Invalid cost: " + c);
        }

        public void AddSource(Node node)
        {
            AddSource(node, NullCost);
        }

        public void AddSource(Node node, double nodeCost)
        {
            if (Reached(node)) throw new InvalidOperationException("Cannot add a reached node as a source.");
            ValidateCost(nodeCost);

            parentArc[node] = Arc.Invalid;
            priorityQueue[node] = nodeCost;
        }

        public Node Step()
        {
            if (priorityQueue.Count == 0) return Node.Invalid;

            // find the closest reached but unfixed node
            double minDist;
            Node min = priorityQueue.Peek(out minDist);
            priorityQueue.Pop();

            if (double.IsPositiveInfinity(minDist)) return Node.Invalid;
            distance[min] = minDist; // fix the node

            // modify keys for neighboring nodes in the priority queue
            foreach (var arc in Graph.Arcs(min, ArcFilter.Forward))
            {
                Node other = Graph.Other(arc, min);
                if (Fixed(other)) continue; // already processed

                double arcCost = Cost(arc);
                ValidateCost(arcCost);
                double newDist = (Mode == DijkstraMode.Sum ? minDist + arcCost : Math.Max(minDist, arcCost));

                double oldDist;
                if (!priorityQueue.TryGetPriority(other, out oldDist)) oldDist = double.PositiveInfinity;

                if (newDist < oldDist)
                {
                    priorityQueue[other] = newDist;
                    parentArc[other] = arc;
                }
            }

            return min;
        }

        public void Run()
        {
            while (Step() != Node.Invalid) ;
        }

        public Node RunUntilFixed(Node target)
        {
            if (Fixed(target)) return target; // already fixed
            while (true)
            {
                Node fixedNode = Step();
                if (fixedNode == Node.Invalid || fixedNode == target) return fixedNode;
            }
        }

        public Node RunUntilFixed(Func<Node, bool> isTarget)
        {
            Node fixedNode = FixedNodes.FirstOrDefault(isTarget);
            if (fixedNode != Node.Invalid) return fixedNode; // already fixed
            while (true)
            {
                fixedNode = Step();
                if (fixedNode == Node.Invalid || isTarget(fixedNode)) return fixedNode;
            }
        }

        public bool Reached(Node node)
        {
            return parentArc.ContainsKey(node);
        }

        public IEnumerable<Node> ReachedNodes { get { return parentArc.Keys; } }

        public bool Fixed(Node node)
        {
            return distance.ContainsKey(node);
        }

        public IEnumerable<Node> FixedNodes { get { return distance.Keys; } }

        public double GetDistance(Node node)
        {
            double result;
            return distance.TryGetValue(node, out result) ? result : double.PositiveInfinity;
        }

        public Arc GetParentArc(Node node)
        {
            Arc result;
            return parentArc.TryGetValue(node, out result) ? result : Arc.Invalid;
        }

        public IPath GetPath(Node node)
        {
            if (!Reached(node)) return null;

            var result = new Path(Graph);
            result.Begin(node);
            while (true)
            {
                Arc arc = GetParentArc(node);
                if (arc == Arc.Invalid) break;
                result.AddFirst(arc);
                node = Graph.Other(arc, node);
            }
            return result;
        }
    }
}