BellmanFord.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 sealed class BellmanFord
    {
        public IGraph Graph { get; private set; }
        public Func<Arc, double> Cost { get; private set; }

        public IPath NegativeCycle { get; private set; }

        private const string NegativeCycleMessage = "A negative cycle was found.";
        private readonly Dictionary<Node, double> distance;
        private readonly Dictionary<Node, Arc> parentArc;

        public BellmanFord(IGraph graph, Func<Arc, double> cost, IEnumerable<Node> sources)
        {
            Graph = graph;
            Cost = cost;

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

            foreach (var n in sources)
            {
                distance[n] = 0;
                parentArc[n] = Arc.Invalid;
            }

            Run();
        }

        private void Run()
        {
            for (int i = Graph.NodeCount(); i > 0; i--)
            {
                foreach (var arc in Graph.Arcs())
                {
                    Node u = Graph.U(arc);
                    Node v = Graph.V(arc);
                    double du = GetDistance(u);
                    double dv = GetDistance(v);
                    double c = Cost(arc);

                    if (Graph.IsEdge(arc))
                    {
                        if (du > dv)
                        {
                            var t = u; u = v; v = t;
                            var dt = du; du = dv; dv = dt;
                        }

                        if (!double.IsPositiveInfinity(du) && c < 0)
                        {
                            var cycle = new Path(Graph);
                            cycle.Begin(u);
                            cycle.AddLast(arc);
                            cycle.AddLast(arc);
                            NegativeCycle = cycle;
                            return;
                        }
                    }

                    if (du + c < dv)
                    {
                        distance[v] = du + c;
                        parentArc[v] = arc;

                        if (i == 0)
                        {
                            Node p = u;
                            for (int j = Graph.NodeCount() - 1; j > 0; j--)
                                p = Graph.Other(parentArc[p], p);

                            var cycle = new Path(Graph);
                            cycle.Begin(p);
                            Node x = p;
                            while (true)
                            {
                                Arc a = parentArc[x];
                                cycle.AddFirst(a);
                                x = Graph.Other(a, x);
                                if (x == p) break;
                            }
                            NegativeCycle = cycle;
                            return;
                        }
                    }
                } // for all arcs
            } // for i
        }

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

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

        public double GetDistance(Node node)
        {
            if (NegativeCycle != null) throw new InvalidOperationException(NegativeCycleMessage);
            double result;
            return distance.TryGetValue(node, out result) ? result : double.PositiveInfinity;
        }

        public Arc GetParentArc(Node node)
        {
            if (NegativeCycle != null) throw new InvalidOperationException(NegativeCycleMessage);
            Arc result;
            return parentArc.TryGetValue(node, out result) ? result : Arc.Invalid;
        }

        public IPath GetPath(Node node)
        {
            if (NegativeCycle != null) throw new InvalidOperationException(NegativeCycleMessage);
            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;
        }
    }
}