kpeter@1201: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@1201:  *
kpeter@1201:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@1201:  *
alpar@1270:  * Copyright (C) 2003-2013
kpeter@1201:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@1201:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@1201:  *
kpeter@1201:  * Permission to use, modify and distribute this software is granted
kpeter@1201:  * provided that this copyright notice appears in all copies. For
kpeter@1201:  * precise terms see the accompanying LICENSE file.
kpeter@1201:  *
kpeter@1201:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@1201:  * express or implied, and with no claim as to its suitability for any
kpeter@1201:  * purpose.
kpeter@1201:  *
kpeter@1201:  */
kpeter@1201: 
f4c3@1199: #ifndef LEMON_GREEDY_TSP_H
f4c3@1199: #define LEMON_GREEDY_TSP_H
f4c3@1199: 
kpeter@1201: /// \ingroup tsp
kpeter@1201: /// \file
kpeter@1201: /// \brief Greedy algorithm for symmetric TSP
kpeter@1201: 
kpeter@1201: #include <vector>
kpeter@1201: #include <algorithm>
f4c3@1199: #include <lemon/full_graph.h>
f4c3@1199: #include <lemon/unionfind.h>
f4c3@1199: 
f4c3@1199: namespace lemon {
f4c3@1199: 
kpeter@1202:   /// \ingroup tsp
kpeter@1202:   ///
kpeter@1201:   /// \brief Greedy algorithm for symmetric TSP.
kpeter@1201:   ///
kpeter@1201:   /// GreedyTsp implements the greedy heuristic for solving
kpeter@1201:   /// symmetric \ref tsp "TSP".
kpeter@1201:   ///
kpeter@1201:   /// This algorithm is quite similar to the \ref NearestNeighborTsp
kpeter@1201:   /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
kpeter@1201:   /// At each step, the shortest possible edge is added to these paths
kpeter@1201:   /// as long as it does not create a cycle of less than n edges and it does
kpeter@1201:   /// not increase the degree of any node above two.
kpeter@1201:   ///
kpeter@1204:   /// This method runs in O(n<sup>2</sup>) time.
kpeter@1204:   /// It quickly finds a relatively short tour for most TSP instances,
kpeter@1204:   /// but it could also yield a really bad (or even the worst) solution
kpeter@1204:   /// in special cases.
kpeter@1201:   ///
kpeter@1201:   /// \tparam CM Type of the cost map.
kpeter@1201:   template <typename CM>
kpeter@1201:   class GreedyTsp
kpeter@1201:   {
kpeter@1201:     public:
f4c3@1199: 
kpeter@1201:       /// Type of the cost map
kpeter@1201:       typedef CM CostMap;
kpeter@1201:       /// Type of the edge costs
kpeter@1201:       typedef typename CM::Value Cost;
kpeter@1201: 
kpeter@1201:     private:
kpeter@1201: 
kpeter@1201:       GRAPH_TYPEDEFS(FullGraph);
kpeter@1201: 
kpeter@1201:       const FullGraph &_gr;
kpeter@1201:       const CostMap &_cost;
kpeter@1201:       Cost _sum;
kpeter@1201:       std::vector<Node> _path;
alpar@1270: 
kpeter@1201:     private:
alpar@1270: 
kpeter@1201:       // Functor class to compare edges by their costs
kpeter@1201:       class EdgeComp {
kpeter@1201:       private:
kpeter@1201:         const CostMap &_cost;
kpeter@1201: 
f4c3@1199:       public:
kpeter@1201:         EdgeComp(const CostMap &cost) : _cost(cost) {}
kpeter@1201: 
kpeter@1201:         bool operator()(const Edge &a, const Edge &b) const {
kpeter@1201:           return _cost[a] < _cost[b];
f4c3@1199:         }
kpeter@1201:       };
f4c3@1199: 
kpeter@1201:     public:
f4c3@1199: 
kpeter@1201:       /// \brief Constructor
kpeter@1201:       ///
kpeter@1201:       /// Constructor.
kpeter@1201:       /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
kpeter@1201:       /// \param cost The cost map.
kpeter@1201:       GreedyTsp(const FullGraph &gr, const CostMap &cost)
kpeter@1201:         : _gr(gr), _cost(cost) {}
f4c3@1199: 
kpeter@1201:       /// \name Execution Control
kpeter@1201:       /// @{
f4c3@1199: 
kpeter@1201:       /// \brief Runs the algorithm.
kpeter@1201:       ///
kpeter@1201:       /// This function runs the algorithm.
kpeter@1201:       ///
kpeter@1201:       /// \return The total cost of the found tour.
f4c3@1199:       Cost run() {
kpeter@1201:         _path.clear();
kpeter@1201: 
kpeter@1201:         if (_gr.nodeNum() == 0) return _sum = 0;
kpeter@1201:         else if (_gr.nodeNum() == 1) {
kpeter@1201:           _path.push_back(_gr(0));
kpeter@1201:           return _sum = 0;
kpeter@1201:         }
kpeter@1201: 
kpeter@1201:         std::vector<int> plist;
kpeter@1201:         plist.resize(_gr.nodeNum()*2, -1);
kpeter@1201: 
kpeter@1201:         std::vector<Edge> sorted_edges;
f4c3@1199:         sorted_edges.reserve(_gr.edgeNum());
kpeter@1201:         for (EdgeIt e(_gr); e != INVALID; ++e)
kpeter@1201:           sorted_edges.push_back(e);
kpeter@1201:         std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
f4c3@1199: 
kpeter@1201:         FullGraph::NodeMap<int> item_int_map(_gr);
kpeter@1201:         UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
kpeter@1201:         for (NodeIt n(_gr); n != INVALID; ++n)
kpeter@1201:           union_find.insert(n);
f4c3@1199: 
f4c3@1199:         FullGraph::NodeMap<int> degree(_gr, 0);
f4c3@1199: 
f4c3@1199:         int nodesNum = 0, i = 0;
kpeter@1201:         while (nodesNum != _gr.nodeNum()-1) {
kpeter@1201:           Edge e = sorted_edges[i++];
kpeter@1201:           Node u = _gr.u(e),
kpeter@1201:                v = _gr.v(e);
f4c3@1199: 
kpeter@1201:           if (degree[u] <= 1 && degree[v] <= 1) {
kpeter@1201:             if (union_find.join(u, v)) {
kpeter@1201:               const int uid = _gr.id(u),
kpeter@1201:                         vid = _gr.id(v);
kpeter@1201: 
kpeter@1201:               plist[uid*2 + degree[u]] = vid;
kpeter@1201:               plist[vid*2 + degree[v]] = uid;
kpeter@1201: 
f4c3@1199:               ++degree[u];
f4c3@1199:               ++degree[v];
f4c3@1199:               ++nodesNum;
f4c3@1199:             }
f4c3@1199:           }
f4c3@1199:         }
f4c3@1199: 
f4c3@1199:         for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
kpeter@1201:           if (plist[i] == -1) {
f4c3@1199:             if (n==-1) {
f4c3@1199:               n = i;
f4c3@1199:             } else {
kpeter@1201:               plist[n] = i/2;
kpeter@1201:               plist[i] = n/2;
f4c3@1199:               break;
f4c3@1199:             }
f4c3@1199:           }
f4c3@1199:         }
f4c3@1199: 
kpeter@1201:         for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
kpeter@1201:           _path.push_back(_gr.nodeFromId(next));
kpeter@1201:           if (plist[2*next] != last) {
kpeter@1201:             last = next;
kpeter@1201:             next = plist[2*next];
f4c3@1199:           } else {
kpeter@1201:             last = next;
kpeter@1201:             next = plist[2*next+1];
f4c3@1199:           }
f4c3@1199:         }
f4c3@1199: 
kpeter@1201:         _sum = _cost[_gr.edge(_path.back(), _path.front())];
kpeter@1201:         for (int i = 0; i < int(_path.size())-1; ++i) {
kpeter@1201:           _sum += _cost[_gr.edge(_path[i], _path[i+1])];
kpeter@1201:         }
f4c3@1199: 
f4c3@1199:         return _sum;
f4c3@1199:       }
f4c3@1199: 
kpeter@1201:       /// @}
f4c3@1199: 
kpeter@1201:       /// \name Query Functions
kpeter@1201:       /// @{
f4c3@1199: 
kpeter@1201:       /// \brief The total cost of the found tour.
kpeter@1201:       ///
kpeter@1201:       /// This function returns the total cost of the found tour.
kpeter@1201:       ///
kpeter@1201:       /// \pre run() must be called before using this function.
kpeter@1201:       Cost tourCost() const {
f4c3@1199:         return _sum;
f4c3@1199:       }
f4c3@1199: 
kpeter@1201:       /// \brief Returns a const reference to the node sequence of the
kpeter@1201:       /// found tour.
kpeter@1201:       ///
kpeter@1202:       /// This function returns a const reference to a vector
kpeter@1201:       /// that stores the node sequence of the found tour.
kpeter@1201:       ///
kpeter@1201:       /// \pre run() must be called before using this function.
kpeter@1201:       const std::vector<Node>& tourNodes() const {
kpeter@1201:         return _path;
kpeter@1201:       }
kpeter@1201: 
kpeter@1201:       /// \brief Gives back the node sequence of the found tour.
kpeter@1201:       ///
kpeter@1201:       /// This function copies the node sequence of the found tour into
kpeter@1205:       /// an STL container through the given output iterator. The
kpeter@1205:       /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
kpeter@1205:       /// For example,
kpeter@1205:       /// \code
kpeter@1205:       /// std::vector<FullGraph::Node> nodes(countNodes(graph));
kpeter@1205:       /// tsp.tourNodes(nodes.begin());
kpeter@1205:       /// \endcode
kpeter@1205:       /// or
kpeter@1205:       /// \code
kpeter@1205:       /// std::list<FullGraph::Node> nodes;
kpeter@1205:       /// tsp.tourNodes(std::back_inserter(nodes));
kpeter@1205:       /// \endcode
kpeter@1201:       ///
kpeter@1201:       /// \pre run() must be called before using this function.
kpeter@1205:       template <typename Iterator>
kpeter@1205:       void tourNodes(Iterator out) const {
kpeter@1205:         std::copy(_path.begin(), _path.end(), out);
kpeter@1201:       }
kpeter@1201: 
kpeter@1201:       /// \brief Gives back the found tour as a path.
kpeter@1201:       ///
kpeter@1201:       /// This function copies the found tour as a list of arcs/edges into
alpar@1250:       /// the given \ref lemon::concepts::Path "path structure".
kpeter@1201:       ///
kpeter@1201:       /// \pre run() must be called before using this function.
kpeter@1201:       template <typename Path>
kpeter@1201:       void tour(Path &path) const {
kpeter@1201:         path.clear();
kpeter@1201:         for (int i = 0; i < int(_path.size()) - 1; ++i) {
kpeter@1201:           path.addBack(_gr.arc(_path[i], _path[i+1]));
kpeter@1201:         }
kpeter@1201:         if (int(_path.size()) >= 2) {
kpeter@1201:           path.addBack(_gr.arc(_path.back(), _path.front()));
kpeter@1201:         }
kpeter@1201:       }
kpeter@1201: 
kpeter@1201:       /// @}
kpeter@1201: 
f4c3@1199:   };
f4c3@1199: 
f4c3@1199: }; // namespace lemon
f4c3@1199: 
f4c3@1199: #endif