Document and greatly improve TSP algorithms (#386)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sat, 08 Jan 2011 22:51:16 +0100
changeset 12019a51db038228
parent 1200 62ba43576f85
child 1202 ef200e268af2
Document and greatly improve TSP algorithms (#386)

- Add LEMON headers.
- Add Doxygen doc for all classes and their members.
- Clarify and unify the public API of the algorithms.
- Various small improvements in the implementations to make
them clearer and faster.
- Avoid using adaptors in ChristofidesTsp.
lemon/christofides_tsp.h
lemon/greedy_tsp.h
lemon/insertion_tsp.h
lemon/nearest_neighbor_tsp.h
lemon/opt2_tsp.h
     1.1 --- a/lemon/christofides_tsp.h	Sat Jan 08 22:49:09 2011 +0100
     1.2 +++ b/lemon/christofides_tsp.h	Sat Jan 08 22:51:16 2011 +0100
     1.3 @@ -1,129 +1,240 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2010
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22  #ifndef LEMON_CHRISTOFIDES_TSP_H
    1.23  #define LEMON_CHRISTOFIDES_TSP_H
    1.24  
    1.25 +/// \ingroup tsp
    1.26 +/// \file
    1.27 +/// \brief Christofides algorithm for symmetric TSP
    1.28 +
    1.29  #include <lemon/full_graph.h>
    1.30  #include <lemon/smart_graph.h>
    1.31 -#include <lemon/path.h>
    1.32  #include <lemon/kruskal.h>
    1.33  #include <lemon/matching.h>
    1.34 -#include <lemon/adaptors.h>
    1.35 -#include <lemon/maps.h>
    1.36  #include <lemon/euler.h>
    1.37  
    1.38  namespace lemon {
    1.39    
    1.40 -  namespace christofides_helper {
    1.41 -    template <class L>
    1.42 -    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    1.43 -      return L(_path.begin(), _path.end());
    1.44 -    }
    1.45 -  
    1.46 -    template <>
    1.47 -    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    1.48 -      return _path;
    1.49 -    }
    1.50 -  }
    1.51 -  
    1.52 +  /// \brief Christofides algorithm for symmetric TSP.
    1.53 +  ///
    1.54 +  /// ChristofidesTsp implements Christofides' heuristic for solving
    1.55 +  /// symmetric \ref tsp "TSP".
    1.56 +  ///
    1.57 +  /// This a well-known approximation method for the TSP problem with
    1.58 +  /// \ref checkMetricCost() "metric cost function".
    1.59 +  /// It yields a tour whose total cost is at most 3/2 of the optimum,
    1.60 +  /// but it is usually much better.
    1.61 +  /// This implementation runs in O(n<sup>3</sup>log(n)) time.
    1.62 +  ///
    1.63 +  /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
    1.64 +  /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
    1.65 +  /// in the subgraph induced by the nodes that have odd degree in the
    1.66 +  /// spanning tree.
    1.67 +  /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
    1.68 +  /// of the union of the spanning tree and the matching.
    1.69 +  /// During this last step, the algorithm simply skips the visited nodes
    1.70 +  /// (i.e. creates shortcuts) assuming that the triangle inequality holds
    1.71 +  /// for the cost function.
    1.72 +  ///
    1.73 +  /// \tparam CM Type of the cost map.
    1.74 +  ///
    1.75 +  /// \warning \& CM::Value must be signed type.
    1.76    template <typename CM>
    1.77 -  class ChristofidesTsp {
    1.78 +  class ChristofidesTsp
    1.79 +  {
    1.80 +    public:
    1.81 +
    1.82 +      /// Type of the cost map
    1.83 +      typedef CM CostMap;
    1.84 +      /// Type of the edge costs
    1.85 +      typedef typename CM::Value Cost;
    1.86 +
    1.87      private:
    1.88 -      GRAPH_TYPEDEFS(SmartGraph);
    1.89 +
    1.90 +      GRAPH_TYPEDEFS(FullGraph);
    1.91 +
    1.92 +      const FullGraph &_gr;
    1.93 +      const CostMap &_cost;
    1.94 +      std::vector<Node> _path;
    1.95 +      Cost _sum;
    1.96  
    1.97      public:
    1.98 -      typedef typename CM::Value Cost;
    1.99 -      typedef SmartGraph::EdgeMap<Cost> CostMap;
   1.100 -    
   1.101 -      ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
   1.102 -        graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
   1.103 -      }
   1.104  
   1.105 +      /// \brief Constructor
   1.106 +      ///
   1.107 +      /// Constructor.
   1.108 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
   1.109 +      /// \param cost The cost map.
   1.110 +      ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
   1.111 +        : _gr(gr), _cost(cost) {}
   1.112 +
   1.113 +      /// \name Execution Control
   1.114 +      /// @{
   1.115 +
   1.116 +      /// \brief Runs the algorithm.
   1.117 +      ///
   1.118 +      /// This function runs the algorithm.
   1.119 +      ///
   1.120 +      /// \return The total cost of the found tour.
   1.121        Cost run() {
   1.122          _path.clear();
   1.123 +
   1.124 +        if (_gr.nodeNum() == 0) return _sum = 0;
   1.125 +        else if (_gr.nodeNum() == 1) {
   1.126 +          _path.push_back(_gr(0));
   1.127 +          return _sum = 0;
   1.128 +        }
   1.129 +        else if (_gr.nodeNum() == 2) {
   1.130 +          _path.push_back(_gr(0));
   1.131 +          _path.push_back(_gr(1));
   1.132 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   1.133 +        }
   1.134          
   1.135 -        SmartGraph::EdgeMap<bool> tree(_gr);
   1.136 -        kruskal(_gr, _cost, tree);
   1.137 +        // Compute min. cost spanning tree
   1.138 +        std::vector<Edge> tree;
   1.139 +        kruskal(_gr, _cost, std::back_inserter(tree));
   1.140          
   1.141 -        FilterEdges<SmartGraph> treefiltered(_gr, tree);
   1.142 -        InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
   1.143 -        
   1.144 -        SmartGraph::NodeMap<bool> oddfilter(_gr, false);
   1.145 -        FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
   1.146 -        
   1.147 -        for (NodeIt n(_gr); n!=INVALID; ++n) {
   1.148 -          if (deg[n]%2 == 1) {
   1.149 -            oddNodes.enable(n);
   1.150 +        FullGraph::NodeMap<int> deg(_gr, 0);
   1.151 +        for (int i = 0; i != int(tree.size()); ++i) {
   1.152 +          Edge e = tree[i];
   1.153 +          ++deg[_gr.u(e)];
   1.154 +          ++deg[_gr.v(e)];
   1.155 +        }
   1.156 +
   1.157 +        // Copy the induced subgraph of odd nodes
   1.158 +        std::vector<Node> odd_nodes;
   1.159 +        for (NodeIt u(_gr); u != INVALID; ++u) {
   1.160 +          if (deg[u] % 2 == 1) odd_nodes.push_back(u);
   1.161 +        }
   1.162 +  
   1.163 +        SmartGraph sgr;
   1.164 +        SmartGraph::EdgeMap<Cost> scost(sgr);
   1.165 +        for (int i = 0; i != int(odd_nodes.size()); ++i) {
   1.166 +          sgr.addNode();
   1.167 +        }
   1.168 +        for (int i = 0; i != int(odd_nodes.size()); ++i) {
   1.169 +          for (int j = 0; j != int(odd_nodes.size()); ++j) {
   1.170 +            if (j == i) continue;
   1.171 +            SmartGraph::Edge e =
   1.172 +              sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
   1.173 +            scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
   1.174            }
   1.175          }
   1.176          
   1.177 -        NegMap<CostMap> negmap(_cost);
   1.178 -        MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
   1.179 -                  NegMap<CostMap> > perfmatch(oddNodes, negmap);
   1.180 -        perfmatch.run();
   1.181 +        // Compute min. cost perfect matching
   1.182 +        MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
   1.183 +          mwpm(sgr, scost);
   1.184 +        mwpm.run();
   1.185          
   1.186 -        for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
   1.187 -          if (perfmatch.matching(e)) {
   1.188 -            treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
   1.189 +        for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
   1.190 +          if (mwpm.matching(e)) {
   1.191 +            tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
   1.192 +                                     odd_nodes[sgr.id(sgr.v(e))]) );
   1.193            }
   1.194          }
   1.195          
   1.196 -        FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
   1.197 -        for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
   1.198 -          if (seen[treefiltered.target(e)]==false) {
   1.199 -            _path.push_back(nr[treefiltered.target(e)]);
   1.200 -            seen[treefiltered.target(e)] = true;
   1.201 +        // Join the spanning tree and the matching        
   1.202 +        sgr.clear();
   1.203 +        for (int i = 0; i != _gr.nodeNum(); ++i) {
   1.204 +          sgr.addNode();
   1.205 +        }
   1.206 +        for (int i = 0; i != int(tree.size()); ++i) {
   1.207 +          int ui = _gr.id(_gr.u(tree[i])),
   1.208 +              vi = _gr.id(_gr.v(tree[i]));
   1.209 +          sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
   1.210 +        }
   1.211 +
   1.212 +        // Compute the tour from the Euler traversal
   1.213 +        SmartGraph::NodeMap<bool> visited(sgr, false);
   1.214 +        for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
   1.215 +          SmartGraph::Node n = sgr.target(e);
   1.216 +          if (!visited[n]) {
   1.217 +            _path.push_back(_gr(sgr.id(n)));
   1.218 +            visited[n] = true;
   1.219            }
   1.220          }
   1.221  
   1.222 -        _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
   1.223 -        for (unsigned int i=0; i<_path.size()-1; ++i)
   1.224 -          _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
   1.225 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   1.226 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   1.227 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   1.228 +        }
   1.229  
   1.230          return _sum;
   1.231        }
   1.232  
   1.233 -      template <typename L>
   1.234 -      void tourNodes(L &container) {
   1.235 -        container(christofides_helper::vectorConvert<L>(_path));
   1.236 -      }
   1.237 +      /// @}
   1.238        
   1.239 -      template <template <typename> class L>
   1.240 -      L<FullGraph::Node> tourNodes() {
   1.241 -        return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
   1.242 -      }
   1.243 -
   1.244 -      const std::vector<Node>& tourNodes() {
   1.245 -        return _path;
   1.246 -      }
   1.247 +      /// \name Query Functions
   1.248 +      /// @{
   1.249        
   1.250 -      Path<FullGraph> tour() {
   1.251 -        Path<FullGraph> p;
   1.252 -        if (_path.size()<2)
   1.253 -          return p;
   1.254 -
   1.255 -        for (unsigned int i=0; i<_path.size()-1; ++i) {
   1.256 -          p.addBack(fullg.arc(_path[i], _path[i+1]));
   1.257 -        }
   1.258 -        p.addBack(fullg.arc(_path.back(), _path.front()));
   1.259 -        
   1.260 -        return p;
   1.261 -      }
   1.262 -      
   1.263 -      Cost tourCost() {
   1.264 +      /// \brief The total cost of the found tour.
   1.265 +      ///
   1.266 +      /// This function returns the total cost of the found tour.
   1.267 +      ///
   1.268 +      /// \pre run() must be called before using this function.
   1.269 +      Cost tourCost() const {
   1.270          return _sum;
   1.271        }
   1.272        
   1.273 +      /// \brief Returns a const reference to the node sequence of the
   1.274 +      /// found tour.
   1.275 +      ///
   1.276 +      /// This function returns a const reference to the internal structure
   1.277 +      /// that stores the node sequence of the found tour.
   1.278 +      ///
   1.279 +      /// \pre run() must be called before using this function.
   1.280 +      const std::vector<Node>& tourNodes() const {
   1.281 +        return _path;
   1.282 +      }
   1.283  
   1.284 -  private:
   1.285 -    SmartGraph _gr;
   1.286 -    CostMap _cost;
   1.287 -    Cost _sum;
   1.288 -    const FullGraph &fullg;
   1.289 -    const CM &fullcost;
   1.290 -    std::vector<FullGraph::Node> _path;
   1.291 -    SmartGraph::NodeMap<FullGraph::Node> nr;
   1.292 +      /// \brief Gives back the node sequence of the found tour.
   1.293 +      ///
   1.294 +      /// This function copies the node sequence of the found tour into
   1.295 +      /// the given standard container.
   1.296 +      ///
   1.297 +      /// \pre run() must be called before using this function.
   1.298 +      template <typename Container>
   1.299 +      void tourNodes(Container &container) const {
   1.300 +        container.assign(_path.begin(), _path.end());
   1.301 +      }
   1.302 +      
   1.303 +      /// \brief Gives back the found tour as a path.
   1.304 +      ///
   1.305 +      /// This function copies the found tour as a list of arcs/edges into
   1.306 +      /// the given \ref concept::Path "path structure".
   1.307 +      ///
   1.308 +      /// \pre run() must be called before using this function.
   1.309 +      template <typename Path>
   1.310 +      void tour(Path &path) const {
   1.311 +        path.clear();
   1.312 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   1.313 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   1.314 +        }
   1.315 +        if (int(_path.size()) >= 2) {
   1.316 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   1.317 +        }
   1.318 +      }
   1.319 +      
   1.320 +      /// @}
   1.321 +      
   1.322    };
   1.323  
   1.324 -
   1.325  }; // namespace lemon
   1.326  
   1.327  #endif
     2.1 --- a/lemon/greedy_tsp.h	Sat Jan 08 22:49:09 2011 +0100
     2.2 +++ b/lemon/greedy_tsp.h	Sat Jan 08 22:51:16 2011 +0100
     2.3 @@ -1,174 +1,236 @@
     2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library.
     2.7 + *
     2.8 + * Copyright (C) 2003-2010
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22  #ifndef LEMON_GREEDY_TSP_H
    2.23  #define LEMON_GREEDY_TSP_H
    2.24  
    2.25 -#include <lemon/path.h>
    2.26 +/// \ingroup tsp
    2.27 +/// \file
    2.28 +/// \brief Greedy algorithm for symmetric TSP
    2.29 +
    2.30 +#include <vector>
    2.31 +#include <algorithm>
    2.32  #include <lemon/full_graph.h>
    2.33  #include <lemon/unionfind.h>
    2.34 -#include <algorithm>
    2.35  
    2.36  namespace lemon {
    2.37  
    2.38 -  namespace greedy_tsp_helper {
    2.39 +  /// \brief Greedy algorithm for symmetric TSP.
    2.40 +  ///
    2.41 +  /// GreedyTsp implements the greedy heuristic for solving
    2.42 +  /// symmetric \ref tsp "TSP".
    2.43 +  ///
    2.44 +  /// This algorithm is quite similar to the \ref NearestNeighborTsp
    2.45 +  /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
    2.46 +  /// At each step, the shortest possible edge is added to these paths
    2.47 +  /// as long as it does not create a cycle of less than n edges and it does
    2.48 +  /// not increase the degree of any node above two.
    2.49 +  ///
    2.50 +  /// This method runs in O(n<sup>2</sup>log(n)) time.
    2.51 +  /// It quickly finds an effectively short tour for most TSP
    2.52 +  /// instances, but in special cases, it could yield a really bad
    2.53 +  /// (or even the worst) solution.
    2.54 +  ///
    2.55 +  /// \tparam CM Type of the cost map.
    2.56 +  template <typename CM>
    2.57 +  class GreedyTsp
    2.58 +  {
    2.59 +    public:
    2.60  
    2.61 -    template <typename CostMap>
    2.62 -    class KeyComp {
    2.63 -      typedef typename CostMap::Key Key;
    2.64 -      const CostMap &cost;
    2.65 +      /// Type of the cost map
    2.66 +      typedef CM CostMap;
    2.67 +      /// Type of the edge costs
    2.68 +      typedef typename CM::Value Cost;
    2.69 +
    2.70 +    private:
    2.71 +
    2.72 +      GRAPH_TYPEDEFS(FullGraph);
    2.73 +
    2.74 +      const FullGraph &_gr;
    2.75 +      const CostMap &_cost;
    2.76 +      Cost _sum;
    2.77 +      std::vector<Node> _path;
    2.78        
    2.79 +    private:
    2.80 +    
    2.81 +      // Functor class to compare edges by their costs
    2.82 +      class EdgeComp {
    2.83 +      private:
    2.84 +        const CostMap &_cost;
    2.85 +
    2.86        public:
    2.87 -        KeyComp(const CostMap &_cost) : cost(_cost) {}
    2.88 -      
    2.89 -        bool operator() (const Key &a, const Key &b) const {
    2.90 -          return cost[a] < cost[b];
    2.91 +        EdgeComp(const CostMap &cost) : _cost(cost) {}
    2.92 +
    2.93 +        bool operator()(const Edge &a, const Edge &b) const {
    2.94 +          return _cost[a] < _cost[b];
    2.95          }
    2.96 -    };
    2.97 +      };
    2.98  
    2.99 -  
   2.100 -    template <class L>
   2.101 -    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
   2.102 -      return L(_path.begin(), _path.end());
   2.103 -    }
   2.104 -  
   2.105 -    template <>
   2.106 -    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
   2.107 -      return _path;
   2.108 -    }
   2.109 -    
   2.110 -  }
   2.111 +    public:
   2.112  
   2.113 +      /// \brief Constructor
   2.114 +      ///
   2.115 +      /// Constructor.
   2.116 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
   2.117 +      /// \param cost The cost map.
   2.118 +      GreedyTsp(const FullGraph &gr, const CostMap &cost)
   2.119 +        : _gr(gr), _cost(cost) {}
   2.120  
   2.121 -  template <typename CM>
   2.122 -  class GreedyTsp {
   2.123 -    private:
   2.124 -      GRAPH_TYPEDEFS(FullGraph);
   2.125 -    
   2.126 -    public:
   2.127 -      typedef CM CostMap;
   2.128 -      typedef typename CM::Value Cost;
   2.129 -      
   2.130 -      GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}  
   2.131 +      /// \name Execution Control
   2.132 +      /// @{
   2.133  
   2.134 +      /// \brief Runs the algorithm.
   2.135 +      ///
   2.136 +      /// This function runs the algorithm.
   2.137 +      ///
   2.138 +      /// \return The total cost of the found tour.
   2.139        Cost run() {
   2.140 -        typedef UnionFind<FullGraph::NodeMap<int> > Union;
   2.141 -        _nodes.clear();
   2.142 -        
   2.143 -        std::vector<int> path;
   2.144 -        path.resize(_gr.nodeNum()*2, -1);
   2.145 -        
   2.146 -        std::vector<typename CostMap::Key> sorted_edges;
   2.147 +        _path.clear();
   2.148 +
   2.149 +        if (_gr.nodeNum() == 0) return _sum = 0;
   2.150 +        else if (_gr.nodeNum() == 1) {
   2.151 +          _path.push_back(_gr(0));
   2.152 +          return _sum = 0;
   2.153 +        }
   2.154 +
   2.155 +        std::vector<int> plist;
   2.156 +        plist.resize(_gr.nodeNum()*2, -1);
   2.157 +
   2.158 +        std::vector<Edge> sorted_edges;
   2.159          sorted_edges.reserve(_gr.edgeNum());
   2.160 -        for (EdgeIt n(_gr); n != INVALID; ++n)
   2.161 -          sorted_edges.push_back(n);
   2.162 +        for (EdgeIt e(_gr); e != INVALID; ++e)
   2.163 +          sorted_edges.push_back(e);
   2.164 +        std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
   2.165  
   2.166 -        std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
   2.167 +        FullGraph::NodeMap<int> item_int_map(_gr);
   2.168 +        UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
   2.169 +        for (NodeIt n(_gr); n != INVALID; ++n)
   2.170 +          union_find.insert(n);
   2.171  
   2.172 -        FullGraph::NodeMap<int> nodemap(_gr);
   2.173 -        Union unionfind(nodemap);
   2.174 -
   2.175 -        for (NodeIt n(_gr); n != INVALID; ++n)
   2.176 -          unionfind.insert(n);
   2.177 -        
   2.178          FullGraph::NodeMap<int> degree(_gr, 0);
   2.179  
   2.180          int nodesNum = 0, i = 0;
   2.181 +        while (nodesNum != _gr.nodeNum()-1) {
   2.182 +          Edge e = sorted_edges[i++];
   2.183 +          Node u = _gr.u(e),
   2.184 +               v = _gr.v(e);
   2.185  
   2.186 -        while ( nodesNum != _gr.nodeNum()-1 ) {
   2.187 -          const Edge &e = sorted_edges[i];
   2.188 -          
   2.189 -          const Node u = _gr.u(e),
   2.190 -                     v = _gr.v(e);
   2.191 -          
   2.192 -          if (degree[u]<=1 && degree[v]<=1) {
   2.193 -            if (unionfind.join(u, v)) {
   2.194 +          if (degree[u] <= 1 && degree[v] <= 1) {
   2.195 +            if (union_find.join(u, v)) {
   2.196 +              const int uid = _gr.id(u),
   2.197 +                        vid = _gr.id(v);
   2.198 +
   2.199 +              plist[uid*2 + degree[u]] = vid;
   2.200 +              plist[vid*2 + degree[v]] = uid;
   2.201 +
   2.202                ++degree[u];
   2.203                ++degree[v];
   2.204                ++nodesNum;
   2.205 -              
   2.206 -              const int uid = _gr.id(u),
   2.207 -                        vid = _gr.id(v);
   2.208 -              
   2.209 -              
   2.210 -              path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
   2.211 -              path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
   2.212              }
   2.213            }
   2.214 -
   2.215 -          ++i;
   2.216          }
   2.217  
   2.218 -
   2.219          for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
   2.220 -          if (path[i] == -1) {
   2.221 +          if (plist[i] == -1) {
   2.222              if (n==-1) {
   2.223                n = i;
   2.224              } else {
   2.225 -              path[n] = i/2;
   2.226 -              path[i] = n/2;
   2.227 +              plist[n] = i/2;
   2.228 +              plist[i] = n/2;
   2.229                break;
   2.230              }
   2.231            }
   2.232          }
   2.233  
   2.234 -
   2.235 -        for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
   2.236 -          _nodes.push_back(_gr.nodeFromId(j));
   2.237 -          
   2.238 -          if (path[2*j] != last) {
   2.239 -            last = j;
   2.240 -            j = path[2*j];
   2.241 +        for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
   2.242 +          _path.push_back(_gr.nodeFromId(next));
   2.243 +          if (plist[2*next] != last) {
   2.244 +            last = next;
   2.245 +            next = plist[2*next];
   2.246            } else {
   2.247 -            last = j;
   2.248 -            j = path[2*j+1];
   2.249 +            last = next;
   2.250 +            next = plist[2*next+1];
   2.251            }
   2.252          }
   2.253  
   2.254 -        _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
   2.255 -        for (unsigned int i=0; i<_nodes.size()-1; ++i)
   2.256 -          _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
   2.257 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   2.258 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   2.259 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   2.260 +        }
   2.261  
   2.262          return _sum;
   2.263        }
   2.264  
   2.265 +      /// @}
   2.266  
   2.267 +      /// \name Query Functions
   2.268 +      /// @{
   2.269  
   2.270 -      template <typename L>
   2.271 -      void tourNodes(L &container) {
   2.272 -        container(greedy_tsp_helper::vectorConvert<L>(_nodes));
   2.273 -      }
   2.274 -      
   2.275 -      template <template <typename> class L>
   2.276 -      L<Node> tourNodes() {
   2.277 -        return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
   2.278 -      }
   2.279 -      
   2.280 -      const std::vector<Node>& tourNodes() {
   2.281 -        return _nodes;
   2.282 -      }
   2.283 -      
   2.284 -      Path<FullGraph> tour() {
   2.285 -        Path<FullGraph> p;
   2.286 -        if (_nodes.size()<2)
   2.287 -          return p;
   2.288 -        
   2.289 -        for (unsigned int i=0; i<_nodes.size()-1; ++i) {
   2.290 -          p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
   2.291 -        }
   2.292 -        
   2.293 -        p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
   2.294 -        
   2.295 -        return p;
   2.296 -      }
   2.297 -      
   2.298 -      Cost tourCost() {
   2.299 +      /// \brief The total cost of the found tour.
   2.300 +      ///
   2.301 +      /// This function returns the total cost of the found tour.
   2.302 +      ///
   2.303 +      /// \pre run() must be called before using this function.
   2.304 +      Cost tourCost() const {
   2.305          return _sum;
   2.306        }
   2.307 -      
   2.308  
   2.309 -    private:
   2.310 -      const FullGraph &_gr;
   2.311 -      const CostMap &_cost;
   2.312 -      Cost _sum;
   2.313 -      std::vector<Node> _nodes;
   2.314 +      /// \brief Returns a const reference to the node sequence of the
   2.315 +      /// found tour.
   2.316 +      ///
   2.317 +      /// This function returns a const reference to the internal structure
   2.318 +      /// that stores the node sequence of the found tour.
   2.319 +      ///
   2.320 +      /// \pre run() must be called before using this function.
   2.321 +      const std::vector<Node>& tourNodes() const {
   2.322 +        return _path;
   2.323 +      }
   2.324 +
   2.325 +      /// \brief Gives back the node sequence of the found tour.
   2.326 +      ///
   2.327 +      /// This function copies the node sequence of the found tour into
   2.328 +      /// the given standard container.
   2.329 +      ///
   2.330 +      /// \pre run() must be called before using this function.
   2.331 +      template <typename Container>
   2.332 +      void tourNodes(Container &container) const {
   2.333 +        container.assign(_path.begin(), _path.end());
   2.334 +      }
   2.335 +
   2.336 +      /// \brief Gives back the found tour as a path.
   2.337 +      ///
   2.338 +      /// This function copies the found tour as a list of arcs/edges into
   2.339 +      /// the given \ref concept::Path "path structure".
   2.340 +      ///
   2.341 +      /// \pre run() must be called before using this function.
   2.342 +      template <typename Path>
   2.343 +      void tour(Path &path) const {
   2.344 +        path.clear();
   2.345 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   2.346 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   2.347 +        }
   2.348 +        if (int(_path.size()) >= 2) {
   2.349 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   2.350 +        }
   2.351 +      }
   2.352 +
   2.353 +      /// @}
   2.354 +
   2.355    };
   2.356  
   2.357  }; // namespace lemon
     3.1 --- a/lemon/insertion_tsp.h	Sat Jan 08 22:49:09 2011 +0100
     3.2 +++ b/lemon/insertion_tsp.h	Sat Jan 08 22:51:16 2011 +0100
     3.3 @@ -1,225 +1,349 @@
     3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library.
     3.7 + *
     3.8 + * Copyright (C) 2003-2010
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22  #ifndef LEMON_INSERTION_TSP_H
    3.23  #define LEMON_INSERTION_TSP_H
    3.24  
    3.25 +/// \ingroup tsp
    3.26 +/// \file
    3.27 +/// \brief Insertion algorithm for symmetric TSP
    3.28 +
    3.29 +#include <vector>
    3.30  #include <lemon/full_graph.h>
    3.31 -#include <lemon/path.h>
    3.32  #include <lemon/maps.h>
    3.33  #include <lemon/random.h>
    3.34 -#include <vector>
    3.35  
    3.36  namespace lemon {
    3.37  
    3.38 -  namespace insertion_tsp_helper {
    3.39 -  
    3.40 -    template <class L>
    3.41 -    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    3.42 -      return L(_path.begin(), _path.end());
    3.43 -    };
    3.44 -  
    3.45 -    template <>
    3.46 -    std::vector<FullGraph::Node> vectorConvert(
    3.47 -        const std::vector<FullGraph::Node> &_path) {
    3.48 -      return _path;
    3.49 -    };
    3.50 -    
    3.51 -  };
    3.52 +  /// \brief Insertion algorithm for symmetric TSP.
    3.53 +  ///
    3.54 +  /// InsertionTsp implements the insertion heuristic for solving
    3.55 +  /// symmetric \ref tsp "TSP".
    3.56 +  ///
    3.57 +  /// This is a basic TSP heuristic that has many variants.
    3.58 +  /// It starts with a subtour containing a few nodes of the graph and it
    3.59 +  /// iteratively inserts the other nodes into this subtour according to a
    3.60 +  /// certain node selection rule.
    3.61 +  ///
    3.62 +  /// This implementation provides four different node selection rules,
    3.63 +  /// from which the most powerful one is used by default.
    3.64 +  /// For more information, see \ref SelectionRule.
    3.65 +  ///
    3.66 +  /// \tparam CM Type of the cost map.
    3.67 +  template <typename CM>
    3.68 +  class InsertionTsp
    3.69 +  {
    3.70 +    public:
    3.71  
    3.72 -  template <typename CM>
    3.73 -  class InsertionTsp {
    3.74 -    private:
    3.75 -      GRAPH_TYPEDEFS(FullGraph);
    3.76 -
    3.77 -    public:      
    3.78 +      /// Type of the cost map
    3.79        typedef CM CostMap;
    3.80 +      /// Type of the edge costs
    3.81        typedef typename CM::Value Cost;
    3.82 -      
    3.83 -      InsertionTsp(const FullGraph &gr, const CostMap &cost) : 
    3.84 -            _gr(gr), _cost(cost) {}
    3.85 -      
    3.86 -      enum InsertionMethod {
    3.87 -        INSERT_NEAREST,
    3.88 -        INSERT_FARTHEST,
    3.89 -        INSERT_CHEAPEST,
    3.90 -        INSERT_RANDOM
    3.91 -      };     
    3.92 -      
    3.93 -      Cost run(InsertionMethod method = INSERT_FARTHEST) {
    3.94 -        switch (method) {
    3.95 -          case INSERT_NEAREST:
    3.96 -            start<InitTour<true>, NearestSelection, DefaultInsert>();
    3.97 -            break;
    3.98 -          case INSERT_FARTHEST:
    3.99 -            start<InitTour<false>, FarthestSelection, DefaultInsert>();
   3.100 -            break;
   3.101 -          case INSERT_CHEAPEST:
   3.102 -            start<InitTour<true>, CheapestSelection, CheapestInsert>();
   3.103 -            break;
   3.104 -          case INSERT_RANDOM:
   3.105 -            start<InitTour<true>, RandomSelection, DefaultInsert>();
   3.106 -            break;
   3.107 -        }
   3.108 -        return sum;
   3.109 -      }
   3.110 -
   3.111 -      template <typename L>
   3.112 -      void tourNodes(L &container) {
   3.113 -        container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
   3.114 -      }
   3.115 -      
   3.116 -      template <template <typename> class L>
   3.117 -      L<Node> tourNodes() {
   3.118 -        return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
   3.119 -      }
   3.120 -      
   3.121 -      const std::vector<Node>& tourNodes() {
   3.122 -        return nodesPath;
   3.123 -      }
   3.124 -      
   3.125 -      Path<FullGraph> tour() {
   3.126 -        Path<FullGraph> p;
   3.127 -        if (nodesPath.size()<2)
   3.128 -          return p;
   3.129 -        
   3.130 -        for (unsigned int i=0; i<nodesPath.size()-1; ++i)
   3.131 -          p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
   3.132 -        
   3.133 -        p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
   3.134 -        return p;
   3.135 -      }
   3.136 -      
   3.137 -      Cost tourCost() {
   3.138 -        return sum;
   3.139 -      }
   3.140 -
   3.141  
   3.142      private:
   3.143  
   3.144 -      template <bool MIN>
   3.145 -      class InitTour {
   3.146 +      GRAPH_TYPEDEFS(FullGraph);
   3.147 +
   3.148 +      const FullGraph &_gr;
   3.149 +      const CostMap &_cost;
   3.150 +      std::vector<Node> _notused;
   3.151 +      std::vector<Node> _path;
   3.152 +      Cost _sum;
   3.153 +
   3.154 +    public:
   3.155 +
   3.156 +      /// \brief Constants for specifying the node selection rule.
   3.157 +      ///
   3.158 +      /// Enum type containing constants for specifying the node selection
   3.159 +      /// rule for the \ref run() function.
   3.160 +      ///
   3.161 +      /// During the algorithm, nodes are selected for addition to the current
   3.162 +      /// subtour according to the applied rule.
   3.163 +      /// In general, the FARTHEST yields the best tours, thus it is the
   3.164 +      /// default option. RANDOM usually gives somewhat worse results, but
   3.165 +      /// it is much faster than the others and it is the most robust.
   3.166 +      ///
   3.167 +      /// The desired selection rule can be specified as a parameter of the
   3.168 +      /// \ref run() function.
   3.169 +      enum SelectionRule {
   3.170 +
   3.171 +        /// An unvisited node having minimum distance from the current
   3.172 +        /// subtour is selected at each step.
   3.173 +        /// The algorithm runs in O(n<sup>3</sup>) time using this
   3.174 +        /// selection rule.
   3.175 +        NEAREST,
   3.176 +
   3.177 +        /// An unvisited node having maximum distance from the current
   3.178 +        /// subtour is selected at each step.
   3.179 +        /// The algorithm runs in O(n<sup>3</sup>) time using this
   3.180 +        /// selection rule.
   3.181 +        FARTHEST,
   3.182 +
   3.183 +        /// An unvisited node whose insertion results in the least
   3.184 +        /// increase of the subtour's total cost is selected at each step.
   3.185 +        /// The algorithm runs in O(n<sup>3</sup>) time using this
   3.186 +        /// selection rule.
   3.187 +        CHEAPEST,
   3.188 +
   3.189 +        /// An unvisited node is selected randomly without any evaluation
   3.190 +        /// at each step.
   3.191 +        /// The global \ref rnd "random number generator instance" is used.
   3.192 +        /// You can seed it before executing the algorithm, if you
   3.193 +        /// would like to.
   3.194 +        /// The algorithm runs in O(n<sup>2</sup>) time using this
   3.195 +        /// selection rule.
   3.196 +        RANDOM
   3.197 +      };
   3.198 +
   3.199 +    public:
   3.200 +
   3.201 +      /// \brief Constructor
   3.202 +      ///
   3.203 +      /// Constructor.
   3.204 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
   3.205 +      /// \param cost The cost map.
   3.206 +      InsertionTsp(const FullGraph &gr, const CostMap &cost)
   3.207 +        : _gr(gr), _cost(cost) {}
   3.208 +
   3.209 +      /// \name Execution Control
   3.210 +      /// @{
   3.211 +
   3.212 +      /// \brief Runs the algorithm.
   3.213 +      ///
   3.214 +      /// This function runs the algorithm.
   3.215 +      ///
   3.216 +      /// \param rule The node selection rule. For more information, see
   3.217 +      /// \ref SelectionRule.
   3.218 +      ///
   3.219 +      /// \return The total cost of the found tour.
   3.220 +      Cost run(SelectionRule rule = FARTHEST) {
   3.221 +        _path.clear();
   3.222 +
   3.223 +        if (_gr.nodeNum() == 0) return _sum = 0;
   3.224 +        else if (_gr.nodeNum() == 1) {
   3.225 +          _path.push_back(_gr(0));
   3.226 +          return _sum = 0;
   3.227 +        }
   3.228 +
   3.229 +        switch (rule) {
   3.230 +          case NEAREST:
   3.231 +            init(true);
   3.232 +            start<NearestSelection, DefaultInsertion>();
   3.233 +            break;
   3.234 +          case FARTHEST:
   3.235 +            init(false);
   3.236 +            start<FarthestSelection, DefaultInsertion>();
   3.237 +            break;
   3.238 +          case CHEAPEST:
   3.239 +            init(true);
   3.240 +            start<CheapestSelection, CheapestInsertion>();
   3.241 +            break;
   3.242 +          case RANDOM:
   3.243 +            init(true);
   3.244 +            start<RandomSelection, DefaultInsertion>();
   3.245 +            break;
   3.246 +        }
   3.247 +        return _sum;
   3.248 +      }
   3.249 +
   3.250 +      /// @}
   3.251 +
   3.252 +      /// \name Query Functions
   3.253 +      /// @{
   3.254 +
   3.255 +      /// \brief The total cost of the found tour.
   3.256 +      ///
   3.257 +      /// This function returns the total cost of the found tour.
   3.258 +      ///
   3.259 +      /// \pre run() must be called before using this function.
   3.260 +      Cost tourCost() const {
   3.261 +        return _sum;
   3.262 +      }
   3.263 +
   3.264 +      /// \brief Returns a const reference to the node sequence of the
   3.265 +      /// found tour.
   3.266 +      ///
   3.267 +      /// This function returns a const reference to the internal structure
   3.268 +      /// that stores the node sequence of the found tour.
   3.269 +      ///
   3.270 +      /// \pre run() must be called before using this function.
   3.271 +      const std::vector<Node>& tourNodes() const {
   3.272 +        return _path;
   3.273 +      }
   3.274 +
   3.275 +      /// \brief Gives back the node sequence of the found tour.
   3.276 +      ///
   3.277 +      /// This function copies the node sequence of the found tour into
   3.278 +      /// the given standard container.
   3.279 +      ///
   3.280 +      /// \pre run() must be called before using this function.
   3.281 +      template <typename Container>
   3.282 +      void tourNodes(Container &container) const {
   3.283 +        container.assign(_path.begin(), _path.end());
   3.284 +      }
   3.285 +
   3.286 +      /// \brief Gives back the found tour as a path.
   3.287 +      ///
   3.288 +      /// This function copies the found tour as a list of arcs/edges into
   3.289 +      /// the given \ref concept::Path "path structure".
   3.290 +      ///
   3.291 +      /// \pre run() must be called before using this function.
   3.292 +      template <typename Path>
   3.293 +      void tour(Path &path) const {
   3.294 +        path.clear();
   3.295 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   3.296 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   3.297 +        }
   3.298 +        if (int(_path.size()) >= 2) {
   3.299 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   3.300 +        }
   3.301 +      }
   3.302 +
   3.303 +      /// @}
   3.304 +
   3.305 +    private:
   3.306 +
   3.307 +      // Initializes the algorithm
   3.308 +      void init(bool min) {
   3.309 +        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
   3.310 +
   3.311 +        _path.clear();
   3.312 +        _path.push_back(_gr.u(min_edge));
   3.313 +        _path.push_back(_gr.v(min_edge));
   3.314 +
   3.315 +        _notused.clear();
   3.316 +        for (NodeIt n(_gr); n!=INVALID; ++n) {
   3.317 +          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
   3.318 +            _notused.push_back(n);
   3.319 +          }
   3.320 +        }
   3.321 +
   3.322 +        _sum = _cost[min_edge] * 2;
   3.323 +      }
   3.324 +
   3.325 +      // Executes the algorithm
   3.326 +      template <class SelectionFunctor, class InsertionFunctor>
   3.327 +      void start() {
   3.328 +        SelectionFunctor selectNode(_gr, _cost, _path, _notused);
   3.329 +        InsertionFunctor insertNode(_gr, _cost, _path, _sum);
   3.330 +
   3.331 +        for (int i=0; i<_gr.nodeNum()-2; ++i) {
   3.332 +          insertNode.insert(selectNode.select());
   3.333 +        }
   3.334 +
   3.335 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   3.336 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   3.337 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   3.338 +        }
   3.339 +      }
   3.340 +
   3.341 +
   3.342 +      // Implementation of the nearest selection rule
   3.343 +      class NearestSelection {
   3.344          public:
   3.345 -          InitTour(const FullGraph &gr, const CostMap &cost,
   3.346 -                   std::vector<Node> &used, std::vector<Node> &notused,
   3.347 -                   Cost &fullcost) :
   3.348 -              _gr(gr), _cost(cost), _used(used), _notused(notused),
   3.349 -              _fullcost(fullcost) {}
   3.350 +          NearestSelection(const FullGraph &gr, const CostMap &cost,
   3.351 +                           std::vector<Node> &path, std::vector<Node> &notused)
   3.352 +            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
   3.353  
   3.354 -          std::vector<Node> init() const {
   3.355 -            Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
   3.356 -            std::vector<Node> path;
   3.357 -            path.push_back(_gr.u(min));
   3.358 -            path.push_back(_gr.v(min));
   3.359 -            
   3.360 -            _used.clear();
   3.361 -            _notused.clear();
   3.362 -            for (NodeIt n(_gr); n!=INVALID; ++n) {
   3.363 -              if (n != _gr.u(min) && n != _gr.v(min)) {
   3.364 -                _notused.push_back(n);
   3.365 +          Node select() const {
   3.366 +            Cost insert_val = 0;
   3.367 +            int insert_node = -1;
   3.368 +
   3.369 +            for (unsigned int i=0; i<_notused.size(); ++i) {
   3.370 +              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
   3.371 +              int min_node = 0;
   3.372 +
   3.373 +              for (unsigned int j=1; j<_path.size(); ++j) {
   3.374 +                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
   3.375 +                if (min_val > curr) {
   3.376 +                    min_val = curr;
   3.377 +                    min_node = j;
   3.378 +                }
   3.379 +              }
   3.380 +
   3.381 +              if (insert_val > min_val || insert_node == -1) {
   3.382 +                insert_val = min_val;
   3.383 +                insert_node = i;
   3.384                }
   3.385              }
   3.386 -            _used.push_back(_gr.u(min));
   3.387 -            _used.push_back(_gr.v(min));
   3.388 -            
   3.389 -            _fullcost = _cost[min]*2;
   3.390 -            return path;
   3.391 +
   3.392 +            Node n = _notused[insert_node];
   3.393 +            _notused.erase(_notused.begin()+insert_node);
   3.394 +
   3.395 +            return n;
   3.396            }
   3.397  
   3.398          private:
   3.399            const FullGraph &_gr;
   3.400            const CostMap &_cost;
   3.401 -          std::vector<Node> &_used;
   3.402 -          std::vector<Node> &_notused;
   3.403 -          Cost &_fullcost;
   3.404 -      };
   3.405 -
   3.406 -      class NearestSelection {
   3.407 -        public:
   3.408 -          NearestSelection(const FullGraph &gr, const CostMap &cost,
   3.409 -                           std::vector<Node> &used, std::vector<Node> &notused) : 
   3.410 -              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
   3.411 -      
   3.412 -          Node select() const {
   3.413 -
   3.414 -            Cost insert_val =
   3.415 -              std::numeric_limits<Cost>::max();
   3.416 -            int insert_node = -1;
   3.417 -            
   3.418 -            for (unsigned int i=0; i<_notused.size(); ++i) {
   3.419 -              Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
   3.420 -              int min_node = 0;
   3.421 -            
   3.422 -              for (unsigned int j=1; j<_used.size(); ++j) {
   3.423 -                if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
   3.424 -                    min_val = _cost[_gr.edge(_notused[i], _used[j])];
   3.425 -                    min_node = j;
   3.426 -                }
   3.427 -              }
   3.428 -              
   3.429 -              if (insert_val > min_val) {
   3.430 -                insert_val = min_val;
   3.431 -                insert_node = i;
   3.432 -              }
   3.433 -            }
   3.434 -            
   3.435 -            Node n = _notused[insert_node];
   3.436 -            _notused.erase(_notused.begin()+insert_node);
   3.437 -            
   3.438 -            return n;
   3.439 -          }
   3.440 -          
   3.441 -        private:
   3.442 -          const FullGraph &_gr;
   3.443 -          const CostMap &_cost;
   3.444 -          std::vector<Node> &_used;
   3.445 +          std::vector<Node> &_path;
   3.446            std::vector<Node> &_notused;
   3.447        };
   3.448  
   3.449 +
   3.450 +      // Implementation of the farthest selection rule
   3.451        class FarthestSelection {
   3.452          public:
   3.453            FarthestSelection(const FullGraph &gr, const CostMap &cost,
   3.454 -                            std::vector<Node> &used, std::vector<Node> &notused) : 
   3.455 -              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
   3.456 -      
   3.457 +                            std::vector<Node> &path, std::vector<Node> &notused)
   3.458 +            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
   3.459 +
   3.460            Node select() const {
   3.461 +            Cost insert_val = 0;
   3.462 +            int insert_node = -1;
   3.463  
   3.464 -            Cost insert_val =
   3.465 -              std::numeric_limits<Cost>::min();
   3.466 -            int insert_node = -1;
   3.467 -            
   3.468              for (unsigned int i=0; i<_notused.size(); ++i) {
   3.469 -              Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
   3.470 +              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
   3.471                int min_node = 0;
   3.472 -              
   3.473 -              for (unsigned int j=1; j<_used.size(); ++j) {
   3.474 -                if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
   3.475 -                  min_val = _cost[_gr.edge(_notused[i], _used[j])];
   3.476 +
   3.477 +              for (unsigned int j=1; j<_path.size(); ++j) {
   3.478 +                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
   3.479 +                if (min_val > curr) {
   3.480 +                  min_val = curr;
   3.481                    min_node = j;
   3.482                  }
   3.483                }
   3.484 -              
   3.485 +
   3.486                if (insert_val < min_val || insert_node == -1) {
   3.487                  insert_val = min_val;
   3.488                  insert_node = i;
   3.489                }
   3.490              }
   3.491 -            
   3.492 +
   3.493              Node n = _notused[insert_node];
   3.494              _notused.erase(_notused.begin()+insert_node);
   3.495 -            
   3.496 +
   3.497              return n;
   3.498            }
   3.499 -          
   3.500 +
   3.501          private:
   3.502            const FullGraph &_gr;
   3.503            const CostMap &_cost;
   3.504 -          std::vector<Node> &_used;
   3.505 +          std::vector<Node> &_path;
   3.506            std::vector<Node> &_notused;
   3.507        };
   3.508  
   3.509  
   3.510 +      // Implementation of the cheapest selection rule
   3.511        class CheapestSelection {
   3.512          private:
   3.513            Cost costDiff(Node u, Node v, Node w) const {
   3.514 -            return 
   3.515 +            return
   3.516                _cost[_gr.edge(u, w)] +
   3.517                _cost[_gr.edge(v, w)] -
   3.518                _cost[_gr.edge(u, v)];
   3.519 @@ -227,24 +351,23 @@
   3.520  
   3.521          public:
   3.522            CheapestSelection(const FullGraph &gr, const CostMap &cost,
   3.523 -                            std::vector<Node> &used, std::vector<Node> &notused) : 
   3.524 -              _gr(gr), _cost(cost), _used(used), _notused(notused) {}
   3.525 -        
   3.526 +                            std::vector<Node> &path, std::vector<Node> &notused)
   3.527 +            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
   3.528 +
   3.529            Cost select() const {
   3.530              int insert_notused = -1;
   3.531              int best_insert_index = -1;
   3.532 -            Cost insert_val =
   3.533 -              std::numeric_limits<Cost>::max();
   3.534 -            
   3.535 +            Cost insert_val = 0;
   3.536 +
   3.537              for (unsigned int i=0; i<_notused.size(); ++i) {
   3.538                int min = i;
   3.539                int best_insert_tmp = 0;
   3.540                Cost min_val =
   3.541 -                costDiff(_used.front(), _used.back(), _notused[i]);
   3.542 -              
   3.543 -              for (unsigned int j=1; j<_used.size(); ++j) {
   3.544 +                costDiff(_path.front(), _path.back(), _notused[i]);
   3.545 +
   3.546 +              for (unsigned int j=1; j<_path.size(); ++j) {
   3.547                  Cost tmp =
   3.548 -                  costDiff(_used[j-1], _used[j], _notused[i]);
   3.549 +                  costDiff(_path[j-1], _path[j], _notused[i]);
   3.550  
   3.551                  if (min_val > tmp) {
   3.552                    min = i;
   3.553 @@ -253,34 +376,34 @@
   3.554                  }
   3.555                }
   3.556  
   3.557 -              if (insert_val > min_val) {
   3.558 +              if (insert_val > min_val || insert_notused == -1) {
   3.559                  insert_notused = min;
   3.560                  insert_val = min_val;
   3.561                  best_insert_index = best_insert_tmp;
   3.562                }
   3.563              }
   3.564  
   3.565 -            _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
   3.566 +            _path.insert(_path.begin()+best_insert_index,
   3.567 +                         _notused[insert_notused]);
   3.568              _notused.erase(_notused.begin()+insert_notused);
   3.569  
   3.570              return insert_val;
   3.571            }
   3.572 -          
   3.573 +
   3.574          private:
   3.575            const FullGraph &_gr;
   3.576            const CostMap &_cost;
   3.577 -          std::vector<Node> &_used;
   3.578 +          std::vector<Node> &_path;
   3.579            std::vector<Node> &_notused;
   3.580        };
   3.581  
   3.582 +      // Implementation of the random selection rule
   3.583        class RandomSelection {
   3.584          public:
   3.585            RandomSelection(const FullGraph &, const CostMap &,
   3.586 -                            std::vector<Node> &, std::vector<Node> &notused) : 
   3.587 -                           _notused(notused) {
   3.588 -            rnd.seedFromTime();
   3.589 -          }
   3.590 -          
   3.591 +                          std::vector<Node> &, std::vector<Node> &notused)
   3.592 +            : _notused(notused) {}
   3.593 +
   3.594            Node select() const {
   3.595              const int index = rnd[_notused.size()];
   3.596              Node n = _notused[index];
   3.597 @@ -292,25 +415,26 @@
   3.598        };
   3.599  
   3.600  
   3.601 -      class DefaultInsert {
   3.602 +      // Implementation of the default insertion method
   3.603 +      class DefaultInsertion {
   3.604          private:
   3.605            Cost costDiff(Node u, Node v, Node w) const {
   3.606 -            return 
   3.607 +            return
   3.608                _cost[_gr.edge(u, w)] +
   3.609                _cost[_gr.edge(v, w)] -
   3.610                _cost[_gr.edge(u, v)];
   3.611            }
   3.612 -  
   3.613 +
   3.614          public:
   3.615 -          DefaultInsert(const FullGraph &gr, const CostMap &cost,
   3.616 -                        std::vector<Node> &path, Cost &fullcost) : 
   3.617 -            _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
   3.618 -          
   3.619 +          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
   3.620 +                           std::vector<Node> &path, Cost &total_cost) :
   3.621 +            _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
   3.622 +
   3.623            void insert(Node n) const {
   3.624              int min = 0;
   3.625              Cost min_val =
   3.626                costDiff(_path.front(), _path.back(), n);
   3.627 -            
   3.628 +
   3.629              for (unsigned int i=1; i<_path.size(); ++i) {
   3.630                Cost tmp = costDiff(_path[i-1], _path[i], n);
   3.631                if (tmp < min_val) {
   3.632 @@ -318,58 +442,37 @@
   3.633                  min_val = tmp;
   3.634                }
   3.635              }
   3.636 -            
   3.637 +
   3.638              _path.insert(_path.begin()+min, n);
   3.639 -            _fullcost += min_val;
   3.640 +            _total += min_val;
   3.641            }
   3.642 -        
   3.643 +
   3.644          private:
   3.645            const FullGraph &_gr;
   3.646            const CostMap &_cost;
   3.647            std::vector<Node> &_path;
   3.648 -          Cost &_fullcost;
   3.649 +          Cost &_total;
   3.650        };
   3.651 -  
   3.652 -      class CheapestInsert {
   3.653 +
   3.654 +      // Implementation of a special insertion method for the cheapest
   3.655 +      // selection rule
   3.656 +      class CheapestInsertion {
   3.657          TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
   3.658          public:
   3.659 -          CheapestInsert(const FullGraph &, const CostMap &,
   3.660 -                         std::vector<Node> &, Cost &fullcost) : 
   3.661 -            _fullcost(fullcost) {}
   3.662 -          
   3.663 +          CheapestInsertion(const FullGraph &, const CostMap &,
   3.664 +                            std::vector<Node> &, Cost &total_cost) :
   3.665 +            _total(total_cost) {}
   3.666 +
   3.667            void insert(Cost diff) const {
   3.668 -            _fullcost += diff;
   3.669 +            _total += diff;
   3.670            }
   3.671  
   3.672          private:
   3.673 -          Cost &_fullcost;
   3.674 -      };  
   3.675 -      
   3.676 -      
   3.677 -      template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
   3.678 -      void start() {
   3.679 -        InitFunctor init(_gr, _cost, nodesPath, notused, sum);
   3.680 -        SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
   3.681 -        InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
   3.682 -        
   3.683 -        nodesPath = init.init();
   3.684 -        
   3.685 -        for (int i=0; i<_gr.nodeNum()-2; ++i) {
   3.686 -          insertNode.insert(selectNode.select());
   3.687 -        }
   3.688 -        
   3.689 -        sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
   3.690 -        for (unsigned int i=0; i<nodesPath.size()-1; ++i)
   3.691 -          sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
   3.692 -      }
   3.693 -    
   3.694 -      const FullGraph &_gr;
   3.695 -      const CostMap &_cost;
   3.696 -      std::vector<Node> notused;
   3.697 -      std::vector<Node> nodesPath;
   3.698 -      Cost sum;
   3.699 +          Cost &_total;
   3.700 +      };
   3.701 +
   3.702    };
   3.703 -  
   3.704 +
   3.705  }; // namespace lemon
   3.706  
   3.707  #endif
     4.1 --- a/lemon/nearest_neighbor_tsp.h	Sat Jan 08 22:49:09 2011 +0100
     4.2 +++ b/lemon/nearest_neighbor_tsp.h	Sat Jan 08 22:51:16 2011 +0100
     4.3 @@ -1,145 +1,216 @@
     4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     4.5 + *
     4.6 + * This file is a part of LEMON, a generic C++ optimization library.
     4.7 + *
     4.8 + * Copyright (C) 2003-2010
     4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    4.11 + *
    4.12 + * Permission to use, modify and distribute this software is granted
    4.13 + * provided that this copyright notice appears in all copies. For
    4.14 + * precise terms see the accompanying LICENSE file.
    4.15 + *
    4.16 + * This software is provided "AS IS" with no warranty of any kind,
    4.17 + * express or implied, and with no claim as to its suitability for any
    4.18 + * purpose.
    4.19 + *
    4.20 + */
    4.21 +
    4.22  #ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
    4.23  #define LEMON_NEAREST_NEIGHBOUR_TSP_H
    4.24  
    4.25 +/// \ingroup tsp
    4.26 +/// \file
    4.27 +/// \brief Nearest neighbor algorithm for symmetric TSP
    4.28 +
    4.29  #include <deque>
    4.30 +#include <limits>
    4.31  #include <lemon/full_graph.h>
    4.32 -#include <lemon/path.h>
    4.33  #include <lemon/maps.h>
    4.34  
    4.35  namespace lemon {
    4.36 -  
    4.37 -  namespace nn_helper {
    4.38 -    template <class L>
    4.39 -    L dequeConvert(const std::deque<FullGraph::Node> &_path) {
    4.40 -      return L(_path.begin(), _path.end());
    4.41 -    }
    4.42  
    4.43 -    template <>
    4.44 -    std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
    4.45 -      return _path;
    4.46 -    }
    4.47 -  }
    4.48 -  
    4.49 +  /// \brief Nearest neighbor algorithm for symmetric TSP.
    4.50 +  ///
    4.51 +  /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
    4.52 +  /// symmetric \ref tsp "TSP".
    4.53 +  ///
    4.54 +  /// This is probably the simplest TSP heuristic.
    4.55 +  /// It starts with a minimum cost edge and at each step, it connects the
    4.56 +  /// nearest unvisited node to the current path.
    4.57 +  /// Finally, it connects the two end points of the path to form a tour.
    4.58 +  ///
    4.59 +  /// This method runs in O(n<sup>2</sup>) time.
    4.60 +  /// It quickly finds an effectively short tour for most TSP
    4.61 +  /// instances, but in special cases, it could yield a really bad
    4.62 +  /// (or even the worst) solution.
    4.63 +  ///
    4.64 +  /// \tparam CM Type of the cost map.
    4.65    template <typename CM>
    4.66 -  class NearestNeighborTsp {
    4.67 +  class NearestNeighborTsp
    4.68 +  {
    4.69 +    public:
    4.70 +
    4.71 +      /// Type of the cost map
    4.72 +      typedef CM CostMap;
    4.73 +      /// Type of the edge costs
    4.74 +      typedef typename CM::Value Cost;
    4.75 +
    4.76      private:
    4.77 +
    4.78        GRAPH_TYPEDEFS(FullGraph);
    4.79  
    4.80 +      const FullGraph &_gr;
    4.81 +      const CostMap &_cost;
    4.82 +      Cost _sum;
    4.83 +      std::deque<Node> _path;
    4.84 +
    4.85      public:
    4.86 -      typedef CM CostMap;
    4.87 -      typedef typename CM::Value Cost;
    4.88 -    
    4.89 -      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
    4.90  
    4.91 +      /// \brief Constructor
    4.92 +      ///
    4.93 +      /// Constructor.
    4.94 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
    4.95 +      /// \param cost The cost map.
    4.96 +      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
    4.97 +        : _gr(gr), _cost(cost) {}
    4.98 +
    4.99 +      /// \name Execution Control
   4.100 +      /// @{
   4.101 +
   4.102 +      /// \brief Runs the algorithm.
   4.103 +      ///
   4.104 +      /// This function runs the algorithm.
   4.105 +      ///
   4.106 +      /// \return The total cost of the found tour.
   4.107        Cost run() {
   4.108          _path.clear();
   4.109  
   4.110 +        if (_gr.nodeNum() == 0) return _sum = 0;
   4.111 +        else if (_gr.nodeNum() == 1) {
   4.112 +          _path.push_back(_gr(0));
   4.113 +          return _sum = 0;
   4.114 +        }
   4.115 +
   4.116          Edge min_edge1 = INVALID,
   4.117               min_edge2 = INVALID;
   4.118 -        
   4.119 +
   4.120          min_edge1 = mapMin(_gr, _cost);
   4.121 -
   4.122 -        FullGraph::NodeMap<bool> used(_gr, false);
   4.123 -
   4.124 -        Node n1 = _gr.u(min_edge1), 
   4.125 +        Node n1 = _gr.u(min_edge1),
   4.126               n2 = _gr.v(min_edge1);
   4.127 -        
   4.128          _path.push_back(n1);
   4.129          _path.push_back(n2);
   4.130  
   4.131 +        FullGraph::NodeMap<bool> used(_gr, false);
   4.132          used[n1] = true;
   4.133          used[n2] = true;
   4.134  
   4.135          min_edge1 = INVALID;
   4.136 -
   4.137          while (int(_path.size()) != _gr.nodeNum()) {
   4.138            if (min_edge1 == INVALID) {
   4.139 -            for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
   4.140 -              if (!used[_gr.runningNode(e)]) {
   4.141 -                if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
   4.142 -                  min_edge1 = e;
   4.143 +            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
   4.144 +              if (!used[_gr.runningNode(e)] &&
   4.145 +                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
   4.146 +                min_edge1 = e;
   4.147                }
   4.148              }
   4.149            }
   4.150  
   4.151            if (min_edge2 == INVALID) {
   4.152 -            for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
   4.153 -              if (!used[_gr.runningNode(e)]) {
   4.154 -                if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
   4.155 -                  min_edge2 = e;
   4.156 +            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
   4.157 +              if (!used[_gr.runningNode(e)] &&
   4.158 +                  (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
   4.159 +                min_edge2 = e;
   4.160                }
   4.161              }
   4.162            }
   4.163  
   4.164 -          if ( _cost[min_edge1] < _cost[min_edge2] ) {
   4.165 -            n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
   4.166 +          if (_cost[min_edge1] < _cost[min_edge2]) {
   4.167 +            n1 = _gr.oppositeNode(n1, min_edge1);
   4.168              _path.push_front(n1);
   4.169  
   4.170              used[n1] = true;
   4.171              min_edge1 = INVALID;
   4.172  
   4.173 -            if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
   4.174 +            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
   4.175                min_edge2 = INVALID;
   4.176            } else {
   4.177 -            n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
   4.178 +            n2 = _gr.oppositeNode(n2, min_edge2);
   4.179              _path.push_back(n2);
   4.180  
   4.181              used[n2] = true;
   4.182              min_edge2 = INVALID;
   4.183  
   4.184 -            if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
   4.185 +            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
   4.186                min_edge1 = INVALID;
   4.187            }
   4.188          }
   4.189  
   4.190 -        _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
   4.191 -        for (unsigned int i=0; i<_path.size()-1; ++i)
   4.192 -          _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
   4.193 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   4.194 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   4.195 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   4.196 +        }
   4.197  
   4.198          return _sum;
   4.199        }
   4.200  
   4.201 -      
   4.202 -      template <typename L>
   4.203 -      void tourNodes(L &container) {
   4.204 -        container(nn_helper::dequeConvert<L>(_path));
   4.205 +      /// @}
   4.206 +
   4.207 +      /// \name Query Functions
   4.208 +      /// @{
   4.209 +
   4.210 +      /// \brief The total cost of the found tour.
   4.211 +      ///
   4.212 +      /// This function returns the total cost of the found tour.
   4.213 +      ///
   4.214 +      /// \pre run() must be called before using this function.
   4.215 +      Cost tourCost() const {
   4.216 +        return _sum;
   4.217        }
   4.218 -      
   4.219 -      template <template <typename> class L>
   4.220 -      L<Node> tourNodes() {
   4.221 -        return nn_helper::dequeConvert<L<Node> >(_path);
   4.222 -      }      
   4.223  
   4.224 -      const std::deque<Node>& tourNodes() {
   4.225 +      /// \brief Returns a const reference to the node sequence of the
   4.226 +      /// found tour.
   4.227 +      ///
   4.228 +      /// This function returns a const reference to the internal structure
   4.229 +      /// that stores the node sequence of the found tour.
   4.230 +      ///
   4.231 +      /// \pre run() must be called before using this function.
   4.232 +      const std::deque<Node>& tourNodes() const {
   4.233          return _path;
   4.234        }
   4.235 -      
   4.236 -      Path<FullGraph> tour() {
   4.237 -        Path<FullGraph> p;
   4.238 -        if (_path.size()<2)
   4.239 -          return p;
   4.240 -        
   4.241 -        for (unsigned int i=0; i<_path.size()-1; ++i) {
   4.242 -          p.addBack(_gr.arc(_path[i], _path[i+1]));
   4.243 +
   4.244 +      /// \brief Gives back the node sequence of the found tour.
   4.245 +      ///
   4.246 +      /// This function copies the node sequence of the found tour into
   4.247 +      /// the given standard container.
   4.248 +      ///
   4.249 +      /// \pre run() must be called before using this function.
   4.250 +      template <typename Container>
   4.251 +      void tourNodes(Container &container) const {
   4.252 +        container.assign(_path.begin(), _path.end());
   4.253 +      }
   4.254 +
   4.255 +      /// \brief Gives back the found tour as a path.
   4.256 +      ///
   4.257 +      /// This function copies the found tour as a list of arcs/edges into
   4.258 +      /// the given \ref concept::Path "path structure".
   4.259 +      ///
   4.260 +      /// \pre run() must be called before using this function.
   4.261 +      template <typename Path>
   4.262 +      void tour(Path &path) const {
   4.263 +        path.clear();
   4.264 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   4.265 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   4.266          }
   4.267 -        p.addBack(_gr.arc(_path.back(), _path.front()));
   4.268 -        
   4.269 -        return p;
   4.270 +        if (int(_path.size()) >= 2) {
   4.271 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   4.272 +        }
   4.273        }
   4.274 -      
   4.275 -      Cost tourCost() {
   4.276 -        return _sum;
   4.277 -      }
   4.278 -      
   4.279  
   4.280 -  private:
   4.281 -    const FullGraph &_gr;
   4.282 -    const CostMap &_cost;
   4.283 -    Cost _sum;
   4.284 -    std::deque<Node> _path;
   4.285 +      /// @}
   4.286 +
   4.287    };
   4.288  
   4.289 -
   4.290  }; // namespace lemon
   4.291  
   4.292  #endif
     5.1 --- a/lemon/opt2_tsp.h	Sat Jan 08 22:49:09 2011 +0100
     5.2 +++ b/lemon/opt2_tsp.h	Sat Jan 08 22:51:16 2011 +0100
     5.3 @@ -1,203 +1,354 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2010
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22  #ifndef LEMON_OPT2_TSP_H
    5.23  #define LEMON_OPT2_TSP_H
    5.24  
    5.25 +/// \ingroup tsp
    5.26 +/// \file
    5.27 +/// \brief 2-opt algorithm for symmetric TSP
    5.28 +
    5.29  #include <vector>
    5.30  #include <lemon/full_graph.h>
    5.31 -#include <lemon/path.h>
    5.32  
    5.33  namespace lemon {
    5.34 -  
    5.35 -  namespace opt2_helper {
    5.36 -    template <class L>
    5.37 -    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    5.38 -      return L(_path.begin(), _path.end());
    5.39 -    }
    5.40 -  
    5.41 -    template <>
    5.42 -    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    5.43 -      return _path;
    5.44 -    }
    5.45 -  }
    5.46 -  
    5.47 +
    5.48 +  /// \brief 2-opt algorithm for symmetric TSP.
    5.49 +  ///
    5.50 +  /// Opt2Tsp implements the 2-opt heuristic for solving
    5.51 +  /// symmetric \ref tsp "TSP".
    5.52 +  ///
    5.53 +  /// This algorithm starts with an initial tour and iteratively improves it.
    5.54 +  /// At each step, it removes two edges and the reconnects the created two
    5.55 +  /// paths in the other way if the resulting tour is shorter.
    5.56 +  /// The algorithm finishes when no such 2-opt move can be applied, and so
    5.57 +  /// the tour is 2-optimal.
    5.58 +  ///
    5.59 +  /// If no starting tour is given to the \ref run() function, then the
    5.60 +  /// algorithm uses the node sequence determined by the node IDs.
    5.61 +  /// Oherwise, it starts with the given tour.
    5.62 +  ///
    5.63 +  /// This is a relatively slow but powerful method. 
    5.64 +  /// A typical usage of it is the improvement of a solution that is resulted
    5.65 +  /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
    5.66 +  ///
    5.67 +  /// \tparam CM Type of the cost map.
    5.68    template <typename CM>
    5.69 -  class Opt2Tsp {
    5.70 +  class Opt2Tsp
    5.71 +  {
    5.72 +    public:
    5.73 +
    5.74 +      /// Type of the cost map
    5.75 +      typedef CM CostMap;
    5.76 +      /// Type of the edge costs
    5.77 +      typedef typename CM::Value Cost;
    5.78 +
    5.79      private:
    5.80 +
    5.81        GRAPH_TYPEDEFS(FullGraph);
    5.82  
    5.83 +      const FullGraph &_gr;
    5.84 +      const CostMap &_cost;
    5.85 +      Cost _sum;
    5.86 +      std::vector<int> _plist;
    5.87 +      std::vector<Node> _path;
    5.88 +
    5.89      public:
    5.90 -      typedef CM CostMap;
    5.91 -      typedef typename CM::Value Cost;
    5.92 -      
    5.93 -    
    5.94 -      Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost), 
    5.95 -            tmppath(_gr.nodeNum()*2) {
    5.96 -            
    5.97 -        for (int i=1; i<_gr.nodeNum()-1; ++i) {
    5.98 -          tmppath[2*i] = i-1;
    5.99 -          tmppath[2*i+1] = i+1;
   5.100 +
   5.101 +      /// \brief Constructor
   5.102 +      ///
   5.103 +      /// Constructor.
   5.104 +      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
   5.105 +      /// \param cost The cost map.
   5.106 +      Opt2Tsp(const FullGraph &gr, const CostMap &cost)
   5.107 +        : _gr(gr), _cost(cost) {}
   5.108 +
   5.109 +      /// \name Execution Control
   5.110 +      /// @{
   5.111 +
   5.112 +      /// \brief Runs the algorithm from scratch.
   5.113 +      ///
   5.114 +      /// This function runs the algorithm starting from the tour that is
   5.115 +      /// determined by the node ID sequence.
   5.116 +      ///
   5.117 +      /// \return The total cost of the found tour.
   5.118 +      Cost run() {
   5.119 +        _path.clear();
   5.120 +
   5.121 +        if (_gr.nodeNum() == 0) return _sum = 0;
   5.122 +        else if (_gr.nodeNum() == 1) {
   5.123 +          _path.push_back(_gr(0));
   5.124 +          return _sum = 0;
   5.125          }
   5.126 -        tmppath[0] = _gr.nodeNum()-1;
   5.127 -        tmppath[1] = 1;
   5.128 -        tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
   5.129 -        tmppath[2*(_gr.nodeNum()-1)+1] = 0;
   5.130 -      }
   5.131 -      
   5.132 -      Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) : 
   5.133 -              _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
   5.134 +        else if (_gr.nodeNum() == 2) {
   5.135 +          _path.push_back(_gr(0));
   5.136 +          _path.push_back(_gr(1));
   5.137 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   5.138 +        }
   5.139  
   5.140 -        for (unsigned int i=1; i<path.size()-1; ++i) {
   5.141 -          tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
   5.142 -          tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
   5.143 +        _plist.resize(2*_gr.nodeNum());
   5.144 +        for (int i = 1; i < _gr.nodeNum()-1; ++i) {
   5.145 +          _plist[2*i] = i-1;
   5.146 +          _plist[2*i+1] = i+1;
   5.147          }
   5.148 -        
   5.149 -        tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
   5.150 -        tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
   5.151 -        tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
   5.152 -        tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
   5.153 +        _plist[0] = _gr.nodeNum()-1;
   5.154 +        _plist[1] = 1;
   5.155 +        _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
   5.156 +        _plist[2*_gr.nodeNum()-1] = 0;
   5.157 +
   5.158 +        return start();
   5.159        }
   5.160  
   5.161 +      /// \brief Runs the algorithm from the given tour.
   5.162 +      ///
   5.163 +      /// This function runs the algorithm starting from the given tour.
   5.164 +      ///
   5.165 +      /// \param tour The tour as a path structure. It must be a
   5.166 +      /// \ref checkPath() "valid path" containing excactly n arcs.
   5.167 +      ///
   5.168 +      /// \return The total cost of the found tour.
   5.169 +      template <typename Path>
   5.170 +      Cost run(const Path& tour) {
   5.171 +        _path.clear();
   5.172 +
   5.173 +        if (_gr.nodeNum() == 0) return _sum = 0;
   5.174 +        else if (_gr.nodeNum() == 1) {
   5.175 +          _path.push_back(_gr(0));
   5.176 +          return _sum = 0;
   5.177 +        }
   5.178 +        else if (_gr.nodeNum() == 2) {
   5.179 +          _path.push_back(_gr(0));
   5.180 +          _path.push_back(_gr(1));
   5.181 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   5.182 +        }
   5.183 +
   5.184 +        _plist.resize(2*_gr.nodeNum());
   5.185 +        typename Path::ArcIt it(tour);
   5.186 +        int first = _gr.id(_gr.source(it)),
   5.187 +            prev = first,
   5.188 +            curr = _gr.id(_gr.target(it)),
   5.189 +            next = -1;
   5.190 +        _plist[2*first+1] = curr;
   5.191 +        for (++it; it != INVALID; ++it) {
   5.192 +          next = _gr.id(_gr.target(it));
   5.193 +          _plist[2*curr] = prev;
   5.194 +          _plist[2*curr+1] = next;
   5.195 +          prev = curr;
   5.196 +          curr = next;
   5.197 +        }
   5.198 +        _plist[2*first] = prev;
   5.199 +
   5.200 +        return start();
   5.201 +      }
   5.202 +
   5.203 +      /// \brief Runs the algorithm from the given tour.
   5.204 +      ///
   5.205 +      /// This function runs the algorithm starting from the given tour.
   5.206 +      ///
   5.207 +      /// \param tour The tour as a node sequence. It must be a standard
   5.208 +      /// sequence container storing all <tt>Node</tt>s in the desired order.
   5.209 +      ///
   5.210 +      /// \return The total cost of the found tour.
   5.211 +      template <template <typename> class Container>
   5.212 +      Cost run(const Container<Node>& tour) {
   5.213 +        _path.clear();
   5.214 +
   5.215 +        if (_gr.nodeNum() == 0) return _sum = 0;
   5.216 +        else if (_gr.nodeNum() == 1) {
   5.217 +          _path.push_back(_gr(0));
   5.218 +          return _sum = 0;
   5.219 +        }
   5.220 +        else if (_gr.nodeNum() == 2) {
   5.221 +          _path.push_back(_gr(0));
   5.222 +          _path.push_back(_gr(1));
   5.223 +          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
   5.224 +        }
   5.225 +
   5.226 +        _plist.resize(2*_gr.nodeNum());
   5.227 +        typename Container<Node>::const_iterator it = tour.begin();
   5.228 +        int first = _gr.id(*it),
   5.229 +            prev = first,
   5.230 +            curr = _gr.id(*(++it)),
   5.231 +            next = -1;
   5.232 +        _plist[2*first+1] = curr;
   5.233 +        for (++it; it != tour.end(); ++it) {
   5.234 +          next = _gr.id(*it);
   5.235 +          _plist[2*curr] = prev;
   5.236 +          _plist[2*curr+1] = next;
   5.237 +          prev = curr;
   5.238 +          curr = next;
   5.239 +        }
   5.240 +        _plist[2*first] = curr;
   5.241 +        _plist[2*curr] = prev;
   5.242 +        _plist[2*curr+1] = first;
   5.243 +
   5.244 +        return start();
   5.245 +      }
   5.246 +
   5.247 +      /// @}
   5.248 +
   5.249 +      /// \name Query Functions
   5.250 +      /// @{
   5.251 +
   5.252 +      /// \brief The total cost of the found tour.
   5.253 +      ///
   5.254 +      /// This function returns the total cost of the found tour.
   5.255 +      ///
   5.256 +      /// \pre run() must be called before using this function.
   5.257 +      Cost tourCost() const {
   5.258 +        return _sum;
   5.259 +      }
   5.260 +
   5.261 +      /// \brief Returns a const reference to the node sequence of the
   5.262 +      /// found tour.
   5.263 +      ///
   5.264 +      /// This function returns a const reference to the internal structure
   5.265 +      /// that stores the node sequence of the found tour.
   5.266 +      ///
   5.267 +      /// \pre run() must be called before using this function.
   5.268 +      const std::vector<Node>& tourNodes() const {
   5.269 +        return _path;
   5.270 +      }
   5.271 +
   5.272 +      /// \brief Gives back the node sequence of the found tour.
   5.273 +      ///
   5.274 +      /// This function copies the node sequence of the found tour into
   5.275 +      /// the given standard container.
   5.276 +      ///
   5.277 +      /// \pre run() must be called before using this function.
   5.278 +      template <typename Container>
   5.279 +      void tourNodes(Container &container) const {
   5.280 +        container.assign(_path.begin(), _path.end());
   5.281 +      }
   5.282 +
   5.283 +      /// \brief Gives back the found tour as a path.
   5.284 +      ///
   5.285 +      /// This function copies the found tour as a list of arcs/edges into
   5.286 +      /// the given \ref concept::Path "path structure".
   5.287 +      ///
   5.288 +      /// \pre run() must be called before using this function.
   5.289 +      template <typename Path>
   5.290 +      void tour(Path &path) const {
   5.291 +        path.clear();
   5.292 +        for (int i = 0; i < int(_path.size()) - 1; ++i) {
   5.293 +          path.addBack(_gr.arc(_path[i], _path[i+1]));
   5.294 +        }
   5.295 +        if (int(_path.size()) >= 2) {
   5.296 +          path.addBack(_gr.arc(_path.back(), _path.front()));
   5.297 +        }
   5.298 +      }
   5.299 +
   5.300 +      /// @}
   5.301 +
   5.302      private:
   5.303 -      Cost c(int u, int v) {
   5.304 -        return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
   5.305 -      }
   5.306 -      
   5.307 -      class It {
   5.308 +
   5.309 +      // Iterator class for the linked list storage of the tour
   5.310 +      class PathListIt {
   5.311          public:
   5.312 -          It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
   5.313 -          It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
   5.314 +          PathListIt(const std::vector<int> &pl, int i=0)
   5.315 +            : plist(&pl), act(i), last(pl[2*act]) {}
   5.316 +          PathListIt(const std::vector<int> &pl, int i, int l)
   5.317 +            : plist(&pl), act(i), last(l) {}
   5.318  
   5.319 -          int next_index() const {
   5.320 -            return (tmppath[2*act]==last)? 2*act+1 : 2*act;
   5.321 +          int nextIndex() const {
   5.322 +            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
   5.323            }
   5.324 -          
   5.325 -          int prev_index() const {
   5.326 -            return (tmppath[2*act]==last)? 2*act : 2*act+1;
   5.327 +
   5.328 +          int prevIndex() const {
   5.329 +            return (*plist)[2*act] == last ? 2*act : 2*act+1;
   5.330            }
   5.331 -          
   5.332 +
   5.333            int next() const {
   5.334 -            return tmppath[next_index()];
   5.335 +            int x = (*plist)[2*act];
   5.336 +            return x == last ? (*plist)[2*act+1] : x;
   5.337            }
   5.338  
   5.339            int prev() const {
   5.340 -            return tmppath[prev_index()];
   5.341 +            return last;
   5.342            }
   5.343 -          
   5.344 -          It& operator++() {
   5.345 +
   5.346 +          PathListIt& operator++() {
   5.347              int tmp = act;
   5.348              act = next();
   5.349              last = tmp;
   5.350              return *this;
   5.351            }
   5.352 -          
   5.353 +
   5.354            operator int() const {
   5.355              return act;
   5.356            }
   5.357 -          
   5.358 +
   5.359          private:
   5.360 -          const std::vector<int> &tmppath;
   5.361 +          const std::vector<int> *plist;
   5.362            int act;
   5.363            int last;
   5.364        };
   5.365  
   5.366 -      bool check(std::vector<int> &path, It i, It j) {
   5.367 -        if (c(i, i.next()) + c(j, j.next()) > 
   5.368 -            c(i, j) + c(j.next(), i.next())) {
   5.369 +      // Checks and applies 2-opt move (if it improves the tour)
   5.370 +      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
   5.371 +        Node u  = _gr.nodeFromId(i),
   5.372 +             un = _gr.nodeFromId(i.next()),
   5.373 +             v  = _gr.nodeFromId(j),
   5.374 +             vn = _gr.nodeFromId(j.next());
   5.375  
   5.376 -            path[ It(path, i.next(), i).prev_index() ] = j.next();
   5.377 -            path[ It(path, j.next(), j).prev_index() ] = i.next();
   5.378 +        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
   5.379 +            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
   5.380 +        {
   5.381 +          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
   5.382 +          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
   5.383  
   5.384 -            path[i.next_index()] = j;
   5.385 -            path[j.next_index()] = i;
   5.386 +          _plist[i.nextIndex()] = j;
   5.387 +          _plist[j.nextIndex()] = i;
   5.388  
   5.389 -            return true;
   5.390 +          return true;
   5.391          }
   5.392 +
   5.393          return false;
   5.394 -      }
   5.395 -      
   5.396 -    public:
   5.397 -      
   5.398 -      Cost run() {
   5.399 -        _path.clear();
   5.400 +     }
   5.401  
   5.402 -        if (_gr.nodeNum()>3) {
   5.403 +      // Executes the algorithm from the initial tour
   5.404 +      Cost start() {
   5.405  
   5.406 -opt2_tsp_label:
   5.407 -          It i(tmppath);
   5.408 -          It j(tmppath, i, i.prev());
   5.409 -          ++j; ++j;
   5.410 -          for (; j.next()!=0; ++j) {
   5.411 -            if (check(tmppath, i, j))
   5.412 -              goto opt2_tsp_label;
   5.413 -          }
   5.414 -          
   5.415 -          for (++i; i.next()!=0; ++i) {
   5.416 -            It j(tmppath, i, i.prev());
   5.417 -            if (++j==0)
   5.418 -              break;
   5.419 -            if (++j==0)
   5.420 -              break;
   5.421 -            
   5.422 -            for (; j!=0; ++j) {
   5.423 -              if (check(tmppath, i, j))
   5.424 -                goto opt2_tsp_label;
   5.425 -            }
   5.426 +      restart_search:
   5.427 +        for (PathListIt i(_plist); true; ++i) {
   5.428 +          PathListIt j = i;
   5.429 +          if (++j == 0 || ++j == 0) break;
   5.430 +          for (; j != 0 && j != i.prev(); ++j) {
   5.431 +            if (checkOpt2(i, j))
   5.432 +              goto restart_search;
   5.433            }
   5.434          }
   5.435  
   5.436 -        It k(tmppath);
   5.437 -        _path.push_back(_gr.nodeFromId(k));
   5.438 -        for (++k; k!=0; ++k)
   5.439 -          _path.push_back(_gr.nodeFromId(k));
   5.440 +        PathListIt i(_plist);
   5.441 +        _path.push_back(_gr.nodeFromId(i));
   5.442 +        for (++i; i != 0; ++i)
   5.443 +          _path.push_back(_gr.nodeFromId(i));
   5.444  
   5.445 -        
   5.446 +        _sum = _cost[_gr.edge(_path.back(), _path.front())];
   5.447 +        for (int i = 0; i < int(_path.size())-1; ++i) {
   5.448 +          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
   5.449 +        }
   5.450  
   5.451 -        _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
   5.452 -        for (unsigned int i=0; i<_path.size()-1; ++i)
   5.453 -          _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
   5.454          return _sum;
   5.455        }
   5.456  
   5.457 -      
   5.458 -      template <typename L>
   5.459 -      void tourNodes(L &container) {
   5.460 -        container(opt2_helper::vectorConvert<L>(_path));
   5.461 -      }
   5.462 -      
   5.463 -      template <template <typename> class L>
   5.464 -      L<Node> tourNodes() {
   5.465 -        return opt2_helper::vectorConvert<L<Node> >(_path);
   5.466 -      }
   5.467 -
   5.468 -      const std::vector<Node>& tourNodes() {
   5.469 -        return _path;
   5.470 -      }
   5.471 -      
   5.472 -      Path<FullGraph> tour() {
   5.473 -        Path<FullGraph> p;
   5.474 -        if (_path.size()<2)
   5.475 -          return p;
   5.476 -
   5.477 -        for (unsigned int i=0; i<_path.size()-1; ++i) {
   5.478 -          p.addBack(_gr.arc(_path[i], _path[i+1]));
   5.479 -        }
   5.480 -        p.addBack(_gr.arc(_path.back(), _path.front()));
   5.481 -        return p;
   5.482 -      }
   5.483 -      
   5.484 -      Cost tourCost() {
   5.485 -        return _sum;
   5.486 -      }
   5.487 -      
   5.488 -
   5.489 -  private:
   5.490 -    const FullGraph &_gr;
   5.491 -    const CostMap &_cost;
   5.492 -    Cost _sum;
   5.493 -    std::vector<int> tmppath;
   5.494 -    std::vector<Node> _path;
   5.495    };
   5.496  
   5.497 -
   5.498  }; // namespace lemon
   5.499  
   5.500  #endif