Tsp.cs

Go to the documentation of this file.

#region License
/*This file is part of Satsuma Graph Library
Copyright © 2013 Balázs Szalkai

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

   1. The origin of this software must not be misrepresented; you must not
   claim that you wrote the original software. If you use this software
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.

   2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

   3. This notice may not be removed or altered from any source
   distribution.*/
#endregion

using System;
using System.Collections.Generic;
using System.Linq;

namespace Satsuma
{
    public static class TspUtils
    {
        public static double GetTourCost<TNode>(IEnumerable<TNode> tour, Func<TNode, TNode, double> cost)
        {
            double result = 0;
            if (tour.Any())
            {
                TNode prev = tour.First();
                foreach (var node in tour.Skip(1))
                {
                    result += cost(prev, node);
                    prev = node;
                }
            }
            return result;
        }
    }

    public interface ITsp<TNode>
    {
        IEnumerable<TNode> Tour { get; }
        double TourCost { get; }
    }

    public sealed class CheapestLinkTsp<TNode> : ITsp<TNode>
    {
        public IList<TNode> Nodes { get; private set; }
        public Func<TNode, TNode, double> Cost { get; private set; }

        private List<TNode> tour;
        public IEnumerable<TNode> Tour { get { return tour; } }
        public double TourCost { get; private set; }

        public CheapestLinkTsp(IList<TNode> nodes, Func<TNode, TNode, double> cost)
        {
            Nodes = nodes;
            Cost = cost;
            tour = new List<TNode>();

            Run();
        }

        private void Run()
        {
            // create a complete graph and run Kruskal with maximum degree constraint 2
            CompleteGraph graph = new CompleteGraph(Nodes.Count, Directedness.Undirected);
            Func<Arc, double> arcCost = (arc => Cost(Nodes[graph.GetNodeIndex(graph.U(arc))], 
                Nodes[graph.GetNodeIndex(graph.V(arc))]));
            Kruskal<double> kruskal = new Kruskal<double>(graph, arcCost, _ => 2);
            kruskal.Run();

            Dictionary<Node, Arc> firstArc = new Dictionary<Node, Arc>();
            Dictionary<Node, Arc> secondArc = new Dictionary<Node, Arc>();
            foreach (var arc in kruskal.Forest)
            {
                var u = graph.U(arc);
                (firstArc.ContainsKey(u) ? secondArc : firstArc)[u] = arc;
                var v = graph.V(arc);
                (firstArc.ContainsKey(v) ? secondArc : firstArc)[v] = arc;
            }

            foreach (var startNode in graph.Nodes())
            {
                if (kruskal.Degree[startNode] == 1)
                {
                    Arc prevArc = Arc.Invalid;
                    Node n = startNode;
                    while (true)
                    {
                        tour.Add(Nodes[graph.GetNodeIndex(n)]);
                        if (prevArc != Arc.Invalid && kruskal.Degree[n] == 1) break;
                        Arc arc1 = firstArc[n];
                        prevArc = (arc1 != prevArc ? arc1 : secondArc[n]);
                        n = graph.Other(prevArc, n);
                    }
                    tour.Add(Nodes[graph.GetNodeIndex(startNode)]);
                    break;
                }
            }

            TourCost = TspUtils.GetTourCost(tour, Cost);
        }
    }

    public enum TspSelectionRule
    {
        Nearest,
        Farthest
    }

    public sealed class InsertionTsp<TNode> : ITsp<TNode>
    {
        public IEnumerable<TNode> Nodes { get; private set; }
        public Func<TNode, TNode, double> Cost { get; private set; }
        public TspSelectionRule SelectionRule { get; private set; }

        private LinkedList<TNode> tour;
        private Dictionary<TNode, LinkedListNode<TNode>> tourNodes;
        private HashSet<TNode> insertableNodes;
        private PriorityQueue<TNode, double> insertableNodeQueue;

        // \copydoc ITsp<TNode>.Tour TODO this does not work in doxygen yet
        public IEnumerable<TNode> Tour { get { return tour; } }
        public double TourCost { get; private set; }

        public InsertionTsp(IEnumerable<TNode> nodes, Func<TNode, TNode, double> cost,
            TspSelectionRule selectionRule = TspSelectionRule.Farthest)
        {
            Nodes = nodes;
            Cost = cost;
            SelectionRule = selectionRule;

            tour = new LinkedList<TNode>();
            tourNodes = new Dictionary<TNode,LinkedListNode<TNode>>();
            insertableNodes = new HashSet<TNode>();
            insertableNodeQueue = new PriorityQueue<TNode, double>();

            Clear();
        }

        private double PriorityFromCost(double c)
        {
            switch (SelectionRule)
            {
                case TspSelectionRule.Farthest: return -c;
                default: return c;
            }
        }

        public void Clear()
        {
            tour.Clear();
            TourCost = 0;
            tourNodes.Clear();
            insertableNodes.Clear();
            insertableNodeQueue.Clear();

            if (Nodes.Any())
            {
                TNode startNode = Nodes.First();
                tour.AddFirst(startNode);
                tourNodes[startNode] = tour.AddFirst(startNode);
                foreach (var node in Nodes)
                    if (!node.Equals(startNode)) 
                    {
                        insertableNodes.Add(node);
                        insertableNodeQueue[node] = PriorityFromCost(Cost(startNode, node));
                    }
            }
        }

        public bool Insert(TNode node)
        {
            if (!insertableNodes.Contains(node)) return false;
            insertableNodes.Remove(node);
            insertableNodeQueue.Remove(node);

            // find the optimal insertion place
            LinkedListNode<TNode> insertAfter = null;
            double bestIncrease = double.PositiveInfinity;
            for (var llnode = tour.First; llnode != tour.Last; llnode = llnode.Next)
            {
                var llnode2 = llnode.Next;
                double increase = Cost(llnode.Value, node) + Cost(node, llnode2.Value);
                if (llnode != llnode2) increase -= Cost(llnode.Value, llnode2.Value);
                if (increase < bestIncrease)
                {
                    bestIncrease = increase;
                    insertAfter = llnode;
                }
            }
            
            LinkedListNode<TNode> llnodeNew = tourNodes[node] = tour.AddAfter(insertAfter, node);
            TourCost += bestIncrease;

            // update distances
            foreach (var n in insertableNodes)
            {
                double newPriority = PriorityFromCost(Cost(node, n));
                if (newPriority < insertableNodeQueue[n]) insertableNodeQueue[n] = newPriority;
            }

            return true;
        }

        public bool Insert()
        {
            if (insertableNodes.Count == 0) return false;
            Insert(insertableNodeQueue.Peek());
            return true;
        }

        public void Run()
        {
            while (Insert()) ;
        }
    }

    public sealed class Opt2Tsp<TNode> : ITsp<TNode>
    {
        public Func<TNode, TNode, double> Cost { get; private set; }

        private List<TNode> tour;

        public IEnumerable<TNode> Tour { get { return tour; } }
        public double TourCost { get; private set; }

        public Opt2Tsp(Func<TNode, TNode, double> cost, IEnumerable<TNode> tour, double? tourCost)
        {
            Cost = cost;
            this.tour = tour.ToList();
            TourCost = tourCost ?? TspUtils.GetTourCost(tour, cost);
        }

        public bool Step()
        {
            bool improved = false;
            for (int i = 0; i < tour.Count-3; i++) // first arc
            {
                for (int j = i + 2, jmax = tour.Count - (i == 0 ? 2 : 1); j < jmax; j++) // second arc
                {
                    double increase = Cost(tour[i], tour[j]) + Cost(tour[i+1], tour[j+1]) - 
                        (Cost(tour[i], tour[i+1]) + Cost(tour[j], tour[j+1]));
                    if (increase < 0)
                    {
                        TourCost += increase;
                        tour.Reverse(i + 1, j - i);
                        improved = true;
                    }
                }
            }
            return improved;
        }

        public void Run()
        {
            while (Step()) ;
        }
    }

    public sealed class HamiltonianCycle
    {
        public IGraph Graph { get; private set; }
        public IPath Cycle { get; private set; }

        public HamiltonianCycle(IGraph graph)
        {
            Graph = graph;
            Cycle = null;

            Run();
        }

        private void Run()
        {
            Func<Node, Node, double> cost = (u, v) => (Graph.Arcs(u, v, ArcFilter.Forward).Any() ? 1 : 10);
            IEnumerable<Node> tour = null;
            double minimumTourCost = Graph.NodeCount();

            // Use the insertion tsp combined with 2-OPT heuristic.
            InsertionTsp<Node> insertionTsp = new InsertionTsp<Node>(Graph.Nodes(), cost);
            insertionTsp.Run();
            if (insertionTsp.TourCost == minimumTourCost) tour = insertionTsp.Tour;
            else
            {
                Opt2Tsp<Node> opt2Tsp = new Opt2Tsp<Node>(cost, insertionTsp.Tour, insertionTsp.TourCost);
                opt2Tsp.Run();
                if (opt2Tsp.TourCost == minimumTourCost) tour = opt2Tsp.Tour;
            }

            // convert the tour (node sequence) into a path (arc sequence connecting two nodes)
            if (tour == null) Cycle = null;
            else 
            {
                var cycle = new Path(Graph);
                if (tour.Any())
                {
                    Node prev = Node.Invalid;
                    foreach (var n in tour)
                    {
                        if (prev == Node.Invalid) cycle.Begin(n);
                        else cycle.AddLast(Graph.Arcs(prev, n, ArcFilter.Forward).First());

                        prev = n;
                    }
                    cycle.AddLast(Graph.Arcs(prev, tour.First(), ArcFilter.Forward).First());
                } // if tour is not empty
                Cycle = cycle;
            }
        }
    }
}