COIN-OR::LEMON - Graph Library

Changeset 1201:9a51db038228 in lemon


Ignore:
Timestamp:
01/08/11 22:51:16 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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?.
Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/christofides_tsp.h

    r1199 r1201  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#ifndef LEMON_CHRISTOFIDES_TSP_H
    220#define LEMON_CHRISTOFIDES_TSP_H
    321
     22/// \ingroup tsp
     23/// \file
     24/// \brief Christofides algorithm for symmetric TSP
     25
    426#include <lemon/full_graph.h>
    527#include <lemon/smart_graph.h>
    6 #include <lemon/path.h>
    728#include <lemon/kruskal.h>
    829#include <lemon/matching.h>
    9 #include <lemon/adaptors.h>
    10 #include <lemon/maps.h>
    1130#include <lemon/euler.h>
    1231
    1332namespace lemon {
    1433 
    15   namespace christofides_helper {
    16     template <class L>
    17     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    18       return L(_path.begin(), _path.end());
    19     }
    20  
    21     template <>
    22     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    23       return _path;
    24     }
    25   }
    26  
     34  /// \brief Christofides algorithm for symmetric TSP.
     35  ///
     36  /// ChristofidesTsp implements Christofides' heuristic for solving
     37  /// symmetric \ref tsp "TSP".
     38  ///
     39  /// This a well-known approximation method for the TSP problem with
     40  /// \ref checkMetricCost() "metric cost function".
     41  /// It yields a tour whose total cost is at most 3/2 of the optimum,
     42  /// but it is usually much better.
     43  /// This implementation runs in O(n<sup>3</sup>log(n)) time.
     44  ///
     45  /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
     46  /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
     47  /// in the subgraph induced by the nodes that have odd degree in the
     48  /// spanning tree.
     49  /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
     50  /// of the union of the spanning tree and the matching.
     51  /// During this last step, the algorithm simply skips the visited nodes
     52  /// (i.e. creates shortcuts) assuming that the triangle inequality holds
     53  /// for the cost function.
     54  ///
     55  /// \tparam CM Type of the cost map.
     56  ///
     57  /// \warning \& CM::Value must be signed type.
    2758  template <typename CM>
    28   class ChristofidesTsp {
     59  class ChristofidesTsp
     60  {
     61    public:
     62
     63      /// Type of the cost map
     64      typedef CM CostMap;
     65      /// Type of the edge costs
     66      typedef typename CM::Value Cost;
     67
    2968    private:
    30       GRAPH_TYPEDEFS(SmartGraph);
     69
     70      GRAPH_TYPEDEFS(FullGraph);
     71
     72      const FullGraph &_gr;
     73      const CostMap &_cost;
     74      std::vector<Node> _path;
     75      Cost _sum;
    3176
    3277    public:
    33       typedef typename CM::Value Cost;
    34       typedef SmartGraph::EdgeMap<Cost> CostMap;
    35    
    36       ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
    37         graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
    38       }
    39 
     78
     79      /// \brief Constructor
     80      ///
     81      /// Constructor.
     82      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     83      /// \param cost The cost map.
     84      ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
     85        : _gr(gr), _cost(cost) {}
     86
     87      /// \name Execution Control
     88      /// @{
     89
     90      /// \brief Runs the algorithm.
     91      ///
     92      /// This function runs the algorithm.
     93      ///
     94      /// \return The total cost of the found tour.
    4095      Cost run() {
    4196        _path.clear();
    42        
    43         SmartGraph::EdgeMap<bool> tree(_gr);
    44         kruskal(_gr, _cost, tree);
    45        
    46         FilterEdges<SmartGraph> treefiltered(_gr, tree);
    47         InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
    48        
    49         SmartGraph::NodeMap<bool> oddfilter(_gr, false);
    50         FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
    51        
    52         for (NodeIt n(_gr); n!=INVALID; ++n) {
    53           if (deg[n]%2 == 1) {
    54             oddNodes.enable(n);
     97
     98        if (_gr.nodeNum() == 0) return _sum = 0;
     99        else if (_gr.nodeNum() == 1) {
     100          _path.push_back(_gr(0));
     101          return _sum = 0;
     102        }
     103        else if (_gr.nodeNum() == 2) {
     104          _path.push_back(_gr(0));
     105          _path.push_back(_gr(1));
     106          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     107        }
     108       
     109        // Compute min. cost spanning tree
     110        std::vector<Edge> tree;
     111        kruskal(_gr, _cost, std::back_inserter(tree));
     112       
     113        FullGraph::NodeMap<int> deg(_gr, 0);
     114        for (int i = 0; i != int(tree.size()); ++i) {
     115          Edge e = tree[i];
     116          ++deg[_gr.u(e)];
     117          ++deg[_gr.v(e)];
     118        }
     119
     120        // Copy the induced subgraph of odd nodes
     121        std::vector<Node> odd_nodes;
     122        for (NodeIt u(_gr); u != INVALID; ++u) {
     123          if (deg[u] % 2 == 1) odd_nodes.push_back(u);
     124        }
     125 
     126        SmartGraph sgr;
     127        SmartGraph::EdgeMap<Cost> scost(sgr);
     128        for (int i = 0; i != int(odd_nodes.size()); ++i) {
     129          sgr.addNode();
     130        }
     131        for (int i = 0; i != int(odd_nodes.size()); ++i) {
     132          for (int j = 0; j != int(odd_nodes.size()); ++j) {
     133            if (j == i) continue;
     134            SmartGraph::Edge e =
     135              sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
     136            scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
    55137          }
    56138        }
    57139       
    58         NegMap<CostMap> negmap(_cost);
    59         MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
    60                   NegMap<CostMap> > perfmatch(oddNodes, negmap);
    61         perfmatch.run();
    62        
    63         for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
    64           if (perfmatch.matching(e)) {
    65             treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
     140        // Compute min. cost perfect matching
     141        MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
     142          mwpm(sgr, scost);
     143        mwpm.run();
     144       
     145        for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
     146          if (mwpm.matching(e)) {
     147            tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
     148                                     odd_nodes[sgr.id(sgr.v(e))]) );
    66149          }
    67150        }
    68151       
    69         FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
    70         for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
    71           if (seen[treefiltered.target(e)]==false) {
    72             _path.push_back(nr[treefiltered.target(e)]);
    73             seen[treefiltered.target(e)] = true;
     152        // Join the spanning tree and the matching       
     153        sgr.clear();
     154        for (int i = 0; i != _gr.nodeNum(); ++i) {
     155          sgr.addNode();
     156        }
     157        for (int i = 0; i != int(tree.size()); ++i) {
     158          int ui = _gr.id(_gr.u(tree[i])),
     159              vi = _gr.id(_gr.v(tree[i]));
     160          sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
     161        }
     162
     163        // Compute the tour from the Euler traversal
     164        SmartGraph::NodeMap<bool> visited(sgr, false);
     165        for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
     166          SmartGraph::Node n = sgr.target(e);
     167          if (!visited[n]) {
     168            _path.push_back(_gr(sgr.id(n)));
     169            visited[n] = true;
    74170          }
    75171        }
    76172
    77         _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
    78         for (unsigned int i=0; i<_path.size()-1; ++i)
    79           _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
     173        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     174        for (int i = 0; i < int(_path.size())-1; ++i) {
     175          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     176        }
    80177
    81178        return _sum;
    82179      }
    83180
    84       template <typename L>
    85       void tourNodes(L &container) {
    86         container(christofides_helper::vectorConvert<L>(_path));
    87       }
    88      
    89       template <template <typename> class L>
    90       L<FullGraph::Node> tourNodes() {
    91         return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
    92       }
    93 
    94       const std::vector<Node>& tourNodes() {
     181      /// @}
     182     
     183      /// \name Query Functions
     184      /// @{
     185     
     186      /// \brief The total cost of the found tour.
     187      ///
     188      /// This function returns the total cost of the found tour.
     189      ///
     190      /// \pre run() must be called before using this function.
     191      Cost tourCost() const {
     192        return _sum;
     193      }
     194     
     195      /// \brief Returns a const reference to the node sequence of the
     196      /// found tour.
     197      ///
     198      /// This function returns a const reference to the internal structure
     199      /// that stores the node sequence of the found tour.
     200      ///
     201      /// \pre run() must be called before using this function.
     202      const std::vector<Node>& tourNodes() const {
    95203        return _path;
    96204      }
    97      
    98       Path<FullGraph> tour() {
    99         Path<FullGraph> p;
    100         if (_path.size()<2)
    101           return p;
    102 
    103         for (unsigned int i=0; i<_path.size()-1; ++i) {
    104           p.addBack(fullg.arc(_path[i], _path[i+1]));
    105         }
    106         p.addBack(fullg.arc(_path.back(), _path.front()));
    107        
    108         return p;
    109       }
    110      
    111       Cost tourCost() {
    112         return _sum;
    113       }
    114      
    115 
    116   private:
    117     SmartGraph _gr;
    118     CostMap _cost;
    119     Cost _sum;
    120     const FullGraph &fullg;
    121     const CM &fullcost;
    122     std::vector<FullGraph::Node> _path;
    123     SmartGraph::NodeMap<FullGraph::Node> nr;
     205
     206      /// \brief Gives back the node sequence of the found tour.
     207      ///
     208      /// This function copies the node sequence of the found tour into
     209      /// the given standard container.
     210      ///
     211      /// \pre run() must be called before using this function.
     212      template <typename Container>
     213      void tourNodes(Container &container) const {
     214        container.assign(_path.begin(), _path.end());
     215      }
     216     
     217      /// \brief Gives back the found tour as a path.
     218      ///
     219      /// This function copies the found tour as a list of arcs/edges into
     220      /// the given \ref concept::Path "path structure".
     221      ///
     222      /// \pre run() must be called before using this function.
     223      template <typename Path>
     224      void tour(Path &path) const {
     225        path.clear();
     226        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     227          path.addBack(_gr.arc(_path[i], _path[i+1]));
     228        }
     229        if (int(_path.size()) >= 2) {
     230          path.addBack(_gr.arc(_path.back(), _path.front()));
     231        }
     232      }
     233     
     234      /// @}
     235     
    124236  };
    125237
    126 
    127238}; // namespace lemon
    128239
  • lemon/greedy_tsp.h

    r1199 r1201  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#ifndef LEMON_GREEDY_TSP_H
    220#define LEMON_GREEDY_TSP_H
    321
    4 #include <lemon/path.h>
     22/// \ingroup tsp
     23/// \file
     24/// \brief Greedy algorithm for symmetric TSP
     25
     26#include <vector>
     27#include <algorithm>
    528#include <lemon/full_graph.h>
    629#include <lemon/unionfind.h>
    7 #include <algorithm>
    830
    931namespace lemon {
    1032
    11   namespace greedy_tsp_helper {
    12 
    13     template <typename CostMap>
    14     class KeyComp {
    15       typedef typename CostMap::Key Key;
    16       const CostMap &cost;
     33  /// \brief Greedy algorithm for symmetric TSP.
     34  ///
     35  /// GreedyTsp implements the greedy heuristic for solving
     36  /// symmetric \ref tsp "TSP".
     37  ///
     38  /// This algorithm is quite similar to the \ref NearestNeighborTsp
     39  /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
     40  /// At each step, the shortest possible edge is added to these paths
     41  /// as long as it does not create a cycle of less than n edges and it does
     42  /// not increase the degree of any node above two.
     43  ///
     44  /// This method runs in O(n<sup>2</sup>log(n)) time.
     45  /// It quickly finds an effectively short tour for most TSP
     46  /// instances, but in special cases, it could yield a really bad
     47  /// (or even the worst) solution.
     48  ///
     49  /// \tparam CM Type of the cost map.
     50  template <typename CM>
     51  class GreedyTsp
     52  {
     53    public:
     54
     55      /// Type of the cost map
     56      typedef CM CostMap;
     57      /// Type of the edge costs
     58      typedef typename CM::Value Cost;
     59
     60    private:
     61
     62      GRAPH_TYPEDEFS(FullGraph);
     63
     64      const FullGraph &_gr;
     65      const CostMap &_cost;
     66      Cost _sum;
     67      std::vector<Node> _path;
    1768     
     69    private:
     70   
     71      // Functor class to compare edges by their costs
     72      class EdgeComp {
     73      private:
     74        const CostMap &_cost;
     75
    1876      public:
    19         KeyComp(const CostMap &_cost) : cost(_cost) {}
    20      
    21         bool operator() (const Key &a, const Key &b) const {
    22           return cost[a] < cost[b];
    23         }
    24     };
    25 
    26  
    27     template <class L>
    28     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    29       return L(_path.begin(), _path.end());
    30     }
    31  
    32     template <>
    33     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    34       return _path;
    35     }
    36    
    37   }
    38 
    39 
    40   template <typename CM>
    41   class GreedyTsp {
    42     private:
    43       GRAPH_TYPEDEFS(FullGraph);
    44    
     77        EdgeComp(const CostMap &cost) : _cost(cost) {}
     78
     79        bool operator()(const Edge &a, const Edge &b) const {
     80          return _cost[a] < _cost[b];
     81        }
     82      };
     83
    4584    public:
    46       typedef CM CostMap;
    47       typedef typename CM::Value Cost;
    48      
    49       GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {} 
    50 
     85
     86      /// \brief Constructor
     87      ///
     88      /// Constructor.
     89      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     90      /// \param cost The cost map.
     91      GreedyTsp(const FullGraph &gr, const CostMap &cost)
     92        : _gr(gr), _cost(cost) {}
     93
     94      /// \name Execution Control
     95      /// @{
     96
     97      /// \brief Runs the algorithm.
     98      ///
     99      /// This function runs the algorithm.
     100      ///
     101      /// \return The total cost of the found tour.
    51102      Cost run() {
    52         typedef UnionFind<FullGraph::NodeMap<int> > Union;
    53         _nodes.clear();
    54        
    55         std::vector<int> path;
    56         path.resize(_gr.nodeNum()*2, -1);
    57        
    58         std::vector<typename CostMap::Key> sorted_edges;
     103        _path.clear();
     104
     105        if (_gr.nodeNum() == 0) return _sum = 0;
     106        else if (_gr.nodeNum() == 1) {
     107          _path.push_back(_gr(0));
     108          return _sum = 0;
     109        }
     110
     111        std::vector<int> plist;
     112        plist.resize(_gr.nodeNum()*2, -1);
     113
     114        std::vector<Edge> sorted_edges;
    59115        sorted_edges.reserve(_gr.edgeNum());
    60         for (EdgeIt n(_gr); n != INVALID; ++n)
    61           sorted_edges.push_back(n);
    62 
    63         std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
    64 
    65         FullGraph::NodeMap<int> nodemap(_gr);
    66         Union unionfind(nodemap);
    67 
     116        for (EdgeIt e(_gr); e != INVALID; ++e)
     117          sorted_edges.push_back(e);
     118        std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
     119
     120        FullGraph::NodeMap<int> item_int_map(_gr);
     121        UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
    68122        for (NodeIt n(_gr); n != INVALID; ++n)
    69           unionfind.insert(n);
    70        
     123          union_find.insert(n);
     124
    71125        FullGraph::NodeMap<int> degree(_gr, 0);
    72126
    73127        int nodesNum = 0, i = 0;
    74 
    75         while ( nodesNum != _gr.nodeNum()-1 ) {
    76           const Edge &e = sorted_edges[i];
    77          
    78           const Node u = _gr.u(e),
    79                      v = _gr.v(e);
    80          
    81           if (degree[u]<=1 && degree[v]<=1) {
    82             if (unionfind.join(u, v)) {
     128        while (nodesNum != _gr.nodeNum()-1) {
     129          Edge e = sorted_edges[i++];
     130          Node u = _gr.u(e),
     131               v = _gr.v(e);
     132
     133          if (degree[u] <= 1 && degree[v] <= 1) {
     134            if (union_find.join(u, v)) {
     135              const int uid = _gr.id(u),
     136                        vid = _gr.id(v);
     137
     138              plist[uid*2 + degree[u]] = vid;
     139              plist[vid*2 + degree[v]] = uid;
     140
    83141              ++degree[u];
    84142              ++degree[v];
    85143              ++nodesNum;
    86              
    87               const int uid = _gr.id(u),
    88                         vid = _gr.id(v);
    89              
    90              
    91               path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
    92               path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
    93144            }
    94145          }
    95 
    96           ++i;
    97         }
    98 
     146        }
    99147
    100148        for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
    101           if (path[i] == -1) {
     149          if (plist[i] == -1) {
    102150            if (n==-1) {
    103151              n = i;
    104152            } else {
    105               path[n] = i/2;
    106               path[i] = n/2;
     153              plist[n] = i/2;
     154              plist[i] = n/2;
    107155              break;
    108156            }
     
    110158        }
    111159
    112 
    113         for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
    114           _nodes.push_back(_gr.nodeFromId(j));
    115          
    116           if (path[2*j] != last) {
    117             last = j;
    118             j = path[2*j];
     160        for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
     161          _path.push_back(_gr.nodeFromId(next));
     162          if (plist[2*next] != last) {
     163            last = next;
     164            next = plist[2*next];
    119165          } else {
    120             last = j;
    121             j = path[2*j+1];
     166            last = next;
     167            next = plist[2*next+1];
    122168          }
    123169        }
    124170
    125         _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
    126         for (unsigned int i=0; i<_nodes.size()-1; ++i)
    127           _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
     171        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     172        for (int i = 0; i < int(_path.size())-1; ++i) {
     173          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     174        }
    128175
    129176        return _sum;
    130177      }
    131178
    132 
    133 
    134       template <typename L>
    135       void tourNodes(L &container) {
    136         container(greedy_tsp_helper::vectorConvert<L>(_nodes));
    137       }
    138      
    139       template <template <typename> class L>
    140       L<Node> tourNodes() {
    141         return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
    142       }
    143      
    144       const std::vector<Node>& tourNodes() {
    145         return _nodes;
    146       }
    147      
    148       Path<FullGraph> tour() {
    149         Path<FullGraph> p;
    150         if (_nodes.size()<2)
    151           return p;
    152        
    153         for (unsigned int i=0; i<_nodes.size()-1; ++i) {
    154           p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
    155         }
    156        
    157         p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
    158        
    159         return p;
    160       }
    161      
    162       Cost tourCost() {
     179      /// @}
     180
     181      /// \name Query Functions
     182      /// @{
     183
     184      /// \brief The total cost of the found tour.
     185      ///
     186      /// This function returns the total cost of the found tour.
     187      ///
     188      /// \pre run() must be called before using this function.
     189      Cost tourCost() const {
    163190        return _sum;
    164191      }
    165      
    166 
    167     private:
    168       const FullGraph &_gr;
    169       const CostMap &_cost;
    170       Cost _sum;
    171       std::vector<Node> _nodes;
     192
     193      /// \brief Returns a const reference to the node sequence of the
     194      /// found tour.
     195      ///
     196      /// This function returns a const reference to the internal structure
     197      /// that stores the node sequence of the found tour.
     198      ///
     199      /// \pre run() must be called before using this function.
     200      const std::vector<Node>& tourNodes() const {
     201        return _path;
     202      }
     203
     204      /// \brief Gives back the node sequence of the found tour.
     205      ///
     206      /// This function copies the node sequence of the found tour into
     207      /// the given standard container.
     208      ///
     209      /// \pre run() must be called before using this function.
     210      template <typename Container>
     211      void tourNodes(Container &container) const {
     212        container.assign(_path.begin(), _path.end());
     213      }
     214
     215      /// \brief Gives back the found tour as a path.
     216      ///
     217      /// This function copies the found tour as a list of arcs/edges into
     218      /// the given \ref concept::Path "path structure".
     219      ///
     220      /// \pre run() must be called before using this function.
     221      template <typename Path>
     222      void tour(Path &path) const {
     223        path.clear();
     224        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     225          path.addBack(_gr.arc(_path[i], _path[i+1]));
     226        }
     227        if (int(_path.size()) >= 2) {
     228          path.addBack(_gr.arc(_path.back(), _path.front()));
     229        }
     230      }
     231
     232      /// @}
     233
    172234  };
    173235
  • lemon/insertion_tsp.h

    r1199 r1201  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#ifndef LEMON_INSERTION_TSP_H
    220#define LEMON_INSERTION_TSP_H
    321
     22/// \ingroup tsp
     23/// \file
     24/// \brief Insertion algorithm for symmetric TSP
     25
     26#include <vector>
    427#include <lemon/full_graph.h>
    5 #include <lemon/path.h>
    628#include <lemon/maps.h>
    729#include <lemon/random.h>
    8 #include <vector>
    930
    1031namespace lemon {
    1132
    12   namespace insertion_tsp_helper {
    13  
    14     template <class L>
    15     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    16       return L(_path.begin(), _path.end());
    17     };
    18  
    19     template <>
    20     std::vector<FullGraph::Node> vectorConvert(
    21         const std::vector<FullGraph::Node> &_path) {
    22       return _path;
    23     };
    24    
    25   };
    26 
     33  /// \brief Insertion algorithm for symmetric TSP.
     34  ///
     35  /// InsertionTsp implements the insertion heuristic for solving
     36  /// symmetric \ref tsp "TSP".
     37  ///
     38  /// This is a basic TSP heuristic that has many variants.
     39  /// It starts with a subtour containing a few nodes of the graph and it
     40  /// iteratively inserts the other nodes into this subtour according to a
     41  /// certain node selection rule.
     42  ///
     43  /// This implementation provides four different node selection rules,
     44  /// from which the most powerful one is used by default.
     45  /// For more information, see \ref SelectionRule.
     46  ///
     47  /// \tparam CM Type of the cost map.
    2748  template <typename CM>
    28   class InsertionTsp {
     49  class InsertionTsp
     50  {
     51    public:
     52
     53      /// Type of the cost map
     54      typedef CM CostMap;
     55      /// Type of the edge costs
     56      typedef typename CM::Value Cost;
     57
    2958    private:
     59
    3060      GRAPH_TYPEDEFS(FullGraph);
    3161
    32     public:     
    33       typedef CM CostMap;
    34       typedef typename CM::Value Cost;
    35      
    36       InsertionTsp(const FullGraph &gr, const CostMap &cost) :
    37             _gr(gr), _cost(cost) {}
    38      
    39       enum InsertionMethod {
    40         INSERT_NEAREST,
    41         INSERT_FARTHEST,
    42         INSERT_CHEAPEST,
    43         INSERT_RANDOM
    44       };     
    45      
    46       Cost run(InsertionMethod method = INSERT_FARTHEST) {
    47         switch (method) {
    48           case INSERT_NEAREST:
    49             start<InitTour<true>, NearestSelection, DefaultInsert>();
     62      const FullGraph &_gr;
     63      const CostMap &_cost;
     64      std::vector<Node> _notused;
     65      std::vector<Node> _path;
     66      Cost _sum;
     67
     68    public:
     69
     70      /// \brief Constants for specifying the node selection rule.
     71      ///
     72      /// Enum type containing constants for specifying the node selection
     73      /// rule for the \ref run() function.
     74      ///
     75      /// During the algorithm, nodes are selected for addition to the current
     76      /// subtour according to the applied rule.
     77      /// In general, the FARTHEST yields the best tours, thus it is the
     78      /// default option. RANDOM usually gives somewhat worse results, but
     79      /// it is much faster than the others and it is the most robust.
     80      ///
     81      /// The desired selection rule can be specified as a parameter of the
     82      /// \ref run() function.
     83      enum SelectionRule {
     84
     85        /// An unvisited node having minimum distance from the current
     86        /// subtour is selected at each step.
     87        /// The algorithm runs in O(n<sup>3</sup>) time using this
     88        /// selection rule.
     89        NEAREST,
     90
     91        /// An unvisited node having maximum distance from the current
     92        /// subtour is selected at each step.
     93        /// The algorithm runs in O(n<sup>3</sup>) time using this
     94        /// selection rule.
     95        FARTHEST,
     96
     97        /// An unvisited node whose insertion results in the least
     98        /// increase of the subtour's total cost is selected at each step.
     99        /// The algorithm runs in O(n<sup>3</sup>) time using this
     100        /// selection rule.
     101        CHEAPEST,
     102
     103        /// An unvisited node is selected randomly without any evaluation
     104        /// at each step.
     105        /// The global \ref rnd "random number generator instance" is used.
     106        /// You can seed it before executing the algorithm, if you
     107        /// would like to.
     108        /// The algorithm runs in O(n<sup>2</sup>) time using this
     109        /// selection rule.
     110        RANDOM
     111      };
     112
     113    public:
     114
     115      /// \brief Constructor
     116      ///
     117      /// Constructor.
     118      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     119      /// \param cost The cost map.
     120      InsertionTsp(const FullGraph &gr, const CostMap &cost)
     121        : _gr(gr), _cost(cost) {}
     122
     123      /// \name Execution Control
     124      /// @{
     125
     126      /// \brief Runs the algorithm.
     127      ///
     128      /// This function runs the algorithm.
     129      ///
     130      /// \param rule The node selection rule. For more information, see
     131      /// \ref SelectionRule.
     132      ///
     133      /// \return The total cost of the found tour.
     134      Cost run(SelectionRule rule = FARTHEST) {
     135        _path.clear();
     136
     137        if (_gr.nodeNum() == 0) return _sum = 0;
     138        else if (_gr.nodeNum() == 1) {
     139          _path.push_back(_gr(0));
     140          return _sum = 0;
     141        }
     142
     143        switch (rule) {
     144          case NEAREST:
     145            init(true);
     146            start<NearestSelection, DefaultInsertion>();
    50147            break;
    51           case INSERT_FARTHEST:
    52             start<InitTour<false>, FarthestSelection, DefaultInsert>();
     148          case FARTHEST:
     149            init(false);
     150            start<FarthestSelection, DefaultInsertion>();
    53151            break;
    54           case INSERT_CHEAPEST:
    55             start<InitTour<true>, CheapestSelection, CheapestInsert>();
     152          case CHEAPEST:
     153            init(true);
     154            start<CheapestSelection, CheapestInsertion>();
    56155            break;
    57           case INSERT_RANDOM:
    58             start<InitTour<true>, RandomSelection, DefaultInsert>();
     156          case RANDOM:
     157            init(true);
     158            start<RandomSelection, DefaultInsertion>();
    59159            break;
    60160        }
    61         return sum;
    62       }
    63 
    64       template <typename L>
    65       void tourNodes(L &container) {
    66         container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
    67       }
    68      
    69       template <template <typename> class L>
    70       L<Node> tourNodes() {
    71         return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
    72       }
    73      
    74       const std::vector<Node>& tourNodes() {
    75         return nodesPath;
    76       }
    77      
    78       Path<FullGraph> tour() {
    79         Path<FullGraph> p;
    80         if (nodesPath.size()<2)
    81           return p;
    82        
    83         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
    84           p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
    85        
    86         p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
    87         return p;
    88       }
    89      
    90       Cost tourCost() {
    91         return sum;
    92       }
    93 
     161        return _sum;
     162      }
     163
     164      /// @}
     165
     166      /// \name Query Functions
     167      /// @{
     168
     169      /// \brief The total cost of the found tour.
     170      ///
     171      /// This function returns the total cost of the found tour.
     172      ///
     173      /// \pre run() must be called before using this function.
     174      Cost tourCost() const {
     175        return _sum;
     176      }
     177
     178      /// \brief Returns a const reference to the node sequence of the
     179      /// found tour.
     180      ///
     181      /// This function returns a const reference to the internal structure
     182      /// that stores the node sequence of the found tour.
     183      ///
     184      /// \pre run() must be called before using this function.
     185      const std::vector<Node>& tourNodes() const {
     186        return _path;
     187      }
     188
     189      /// \brief Gives back the node sequence of the found tour.
     190      ///
     191      /// This function copies the node sequence of the found tour into
     192      /// the given standard container.
     193      ///
     194      /// \pre run() must be called before using this function.
     195      template <typename Container>
     196      void tourNodes(Container &container) const {
     197        container.assign(_path.begin(), _path.end());
     198      }
     199
     200      /// \brief Gives back the found tour as a path.
     201      ///
     202      /// This function copies the found tour as a list of arcs/edges into
     203      /// the given \ref concept::Path "path structure".
     204      ///
     205      /// \pre run() must be called before using this function.
     206      template <typename Path>
     207      void tour(Path &path) const {
     208        path.clear();
     209        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     210          path.addBack(_gr.arc(_path[i], _path[i+1]));
     211        }
     212        if (int(_path.size()) >= 2) {
     213          path.addBack(_gr.arc(_path.back(), _path.front()));
     214        }
     215      }
     216
     217      /// @}
    94218
    95219    private:
    96220
    97       template <bool MIN>
    98       class InitTour {
    99         public:
    100           InitTour(const FullGraph &gr, const CostMap &cost,
    101                    std::vector<Node> &used, std::vector<Node> &notused,
    102                    Cost &fullcost) :
    103               _gr(gr), _cost(cost), _used(used), _notused(notused),
    104               _fullcost(fullcost) {}
    105 
    106           std::vector<Node> init() const {
    107             Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
    108             std::vector<Node> path;
    109             path.push_back(_gr.u(min));
    110             path.push_back(_gr.v(min));
    111            
    112             _used.clear();
    113             _notused.clear();
    114             for (NodeIt n(_gr); n!=INVALID; ++n) {
    115               if (n != _gr.u(min) && n != _gr.v(min)) {
    116                 _notused.push_back(n);
     221      // Initializes the algorithm
     222      void init(bool min) {
     223        Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
     224
     225        _path.clear();
     226        _path.push_back(_gr.u(min_edge));
     227        _path.push_back(_gr.v(min_edge));
     228
     229        _notused.clear();
     230        for (NodeIt n(_gr); n!=INVALID; ++n) {
     231          if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) {
     232            _notused.push_back(n);
     233          }
     234        }
     235
     236        _sum = _cost[min_edge] * 2;
     237      }
     238
     239      // Executes the algorithm
     240      template <class SelectionFunctor, class InsertionFunctor>
     241      void start() {
     242        SelectionFunctor selectNode(_gr, _cost, _path, _notused);
     243        InsertionFunctor insertNode(_gr, _cost, _path, _sum);
     244
     245        for (int i=0; i<_gr.nodeNum()-2; ++i) {
     246          insertNode.insert(selectNode.select());
     247        }
     248
     249        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     250        for (int i = 0; i < int(_path.size())-1; ++i) {
     251          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     252        }
     253      }
     254
     255
     256      // Implementation of the nearest selection rule
     257      class NearestSelection {
     258        public:
     259          NearestSelection(const FullGraph &gr, const CostMap &cost,
     260                           std::vector<Node> &path, std::vector<Node> &notused)
     261            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
     262
     263          Node select() const {
     264            Cost insert_val = 0;
     265            int insert_node = -1;
     266
     267            for (unsigned int i=0; i<_notused.size(); ++i) {
     268              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
     269              int min_node = 0;
     270
     271              for (unsigned int j=1; j<_path.size(); ++j) {
     272                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
     273                if (min_val > curr) {
     274                    min_val = curr;
     275                    min_node = j;
     276                }
     277              }
     278
     279              if (insert_val > min_val || insert_node == -1) {
     280                insert_val = min_val;
     281                insert_node = i;
    117282              }
    118283            }
    119             _used.push_back(_gr.u(min));
    120             _used.push_back(_gr.v(min));
    121            
    122             _fullcost = _cost[min]*2;
    123             return path;
     284
     285            Node n = _notused[insert_node];
     286            _notused.erase(_notused.begin()+insert_node);
     287
     288            return n;
    124289          }
    125290
     
    127292          const FullGraph &_gr;
    128293          const CostMap &_cost;
    129           std::vector<Node> &_used;
     294          std::vector<Node> &_path;
    130295          std::vector<Node> &_notused;
    131           Cost &_fullcost;
    132       };
    133 
    134       class NearestSelection {
    135         public:
    136           NearestSelection(const FullGraph &gr, const CostMap &cost,
    137                            std::vector<Node> &used, std::vector<Node> &notused) :
    138               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
    139      
     296      };
     297
     298
     299      // Implementation of the farthest selection rule
     300      class FarthestSelection {
     301        public:
     302          FarthestSelection(const FullGraph &gr, const CostMap &cost,
     303                            std::vector<Node> &path, std::vector<Node> &notused)
     304            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
     305
    140306          Node select() const {
    141 
    142             Cost insert_val =
    143               std::numeric_limits<Cost>::max();
     307            Cost insert_val = 0;
    144308            int insert_node = -1;
    145            
     309
    146310            for (unsigned int i=0; i<_notused.size(); ++i) {
    147               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
     311              Cost min_val = _cost[_gr.edge(_notused[i], _path[0])];
    148312              int min_node = 0;
    149            
    150               for (unsigned int j=1; j<_used.size(); ++j) {
    151                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
    152                     min_val = _cost[_gr.edge(_notused[i], _used[j])];
    153                     min_node = j;
    154                 }
    155               }
    156              
    157               if (insert_val > min_val) {
    158                 insert_val = min_val;
    159                 insert_node = i;
    160               }
    161             }
    162            
    163             Node n = _notused[insert_node];
    164             _notused.erase(_notused.begin()+insert_node);
    165            
    166             return n;
    167           }
    168          
    169         private:
    170           const FullGraph &_gr;
    171           const CostMap &_cost;
    172           std::vector<Node> &_used;
    173           std::vector<Node> &_notused;
    174       };
    175 
    176       class FarthestSelection {
    177         public:
    178           FarthestSelection(const FullGraph &gr, const CostMap &cost,
    179                             std::vector<Node> &used, std::vector<Node> &notused) :
    180               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
    181      
    182           Node select() const {
    183 
    184             Cost insert_val =
    185               std::numeric_limits<Cost>::min();
    186             int insert_node = -1;
    187            
    188             for (unsigned int i=0; i<_notused.size(); ++i) {
    189               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
    190               int min_node = 0;
    191              
    192               for (unsigned int j=1; j<_used.size(); ++j) {
    193                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
    194                   min_val = _cost[_gr.edge(_notused[i], _used[j])];
     313
     314              for (unsigned int j=1; j<_path.size(); ++j) {
     315                Cost curr = _cost[_gr.edge(_notused[i], _path[j])];
     316                if (min_val > curr) {
     317                  min_val = curr;
    195318                  min_node = j;
    196319                }
    197320              }
    198              
     321
    199322              if (insert_val < min_val || insert_node == -1) {
    200323                insert_val = min_val;
     
    202325              }
    203326            }
    204            
     327
    205328            Node n = _notused[insert_node];
    206329            _notused.erase(_notused.begin()+insert_node);
    207            
     330
    208331            return n;
    209332          }
    210          
     333
    211334        private:
    212335          const FullGraph &_gr;
    213336          const CostMap &_cost;
    214           std::vector<Node> &_used;
     337          std::vector<Node> &_path;
    215338          std::vector<Node> &_notused;
    216339      };
    217340
    218341
     342      // Implementation of the cheapest selection rule
    219343      class CheapestSelection {
    220344        private:
    221345          Cost costDiff(Node u, Node v, Node w) const {
    222             return 
     346            return
    223347              _cost[_gr.edge(u, w)] +
    224348              _cost[_gr.edge(v, w)] -
     
    228352        public:
    229353          CheapestSelection(const FullGraph &gr, const CostMap &cost,
    230                             std::vector<Node> &used, std::vector<Node> &notused) :
    231               _gr(gr), _cost(cost), _used(used), _notused(notused) {}
    232        
     354                            std::vector<Node> &path, std::vector<Node> &notused)
     355            : _gr(gr), _cost(cost), _path(path), _notused(notused) {}
     356
    233357          Cost select() const {
    234358            int insert_notused = -1;
    235359            int best_insert_index = -1;
    236             Cost insert_val =
    237               std::numeric_limits<Cost>::max();
    238            
     360            Cost insert_val = 0;
     361
    239362            for (unsigned int i=0; i<_notused.size(); ++i) {
    240363              int min = i;
    241364              int best_insert_tmp = 0;
    242365              Cost min_val =
    243                 costDiff(_used.front(), _used.back(), _notused[i]);
    244              
    245               for (unsigned int j=1; j<_used.size(); ++j) {
     366                costDiff(_path.front(), _path.back(), _notused[i]);
     367
     368              for (unsigned int j=1; j<_path.size(); ++j) {
    246369                Cost tmp =
    247                   costDiff(_used[j-1], _used[j], _notused[i]);
     370                  costDiff(_path[j-1], _path[j], _notused[i]);
    248371
    249372                if (min_val > tmp) {
     
    254377              }
    255378
    256               if (insert_val > min_val) {
     379              if (insert_val > min_val || insert_notused == -1) {
    257380                insert_notused = min;
    258381                insert_val = min_val;
     
    261384            }
    262385
    263             _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
     386            _path.insert(_path.begin()+best_insert_index,
     387                         _notused[insert_notused]);
    264388            _notused.erase(_notused.begin()+insert_notused);
    265389
    266390            return insert_val;
    267391          }
    268          
     392
    269393        private:
    270394          const FullGraph &_gr;
    271395          const CostMap &_cost;
    272           std::vector<Node> &_used;
     396          std::vector<Node> &_path;
    273397          std::vector<Node> &_notused;
    274398      };
    275399
     400      // Implementation of the random selection rule
    276401      class RandomSelection {
    277402        public:
    278403          RandomSelection(const FullGraph &, const CostMap &,
    279                             std::vector<Node> &, std::vector<Node> &notused) :
    280                            _notused(notused) {
    281             rnd.seedFromTime();
    282           }
    283          
     404                          std::vector<Node> &, std::vector<Node> &notused)
     405            : _notused(notused) {}
     406
    284407          Node select() const {
    285408            const int index = rnd[_notused.size()];
     
    293416
    294417
    295       class DefaultInsert {
     418      // Implementation of the default insertion method
     419      class DefaultInsertion {
    296420        private:
    297421          Cost costDiff(Node u, Node v, Node w) const {
    298             return 
     422            return
    299423              _cost[_gr.edge(u, w)] +
    300424              _cost[_gr.edge(v, w)] -
    301425              _cost[_gr.edge(u, v)];
    302426          }
    303  
    304         public:
    305           DefaultInsert(const FullGraph &gr, const CostMap &cost,
    306                         std::vector<Node> &path, Cost &fullcost) :
    307             _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
    308          
     427
     428        public:
     429          DefaultInsertion(const FullGraph &gr, const CostMap &cost,
     430                           std::vector<Node> &path, Cost &total_cost) :
     431            _gr(gr), _cost(cost), _path(path), _total(total_cost) {}
     432
    309433          void insert(Node n) const {
    310434            int min = 0;
    311435            Cost min_val =
    312436              costDiff(_path.front(), _path.back(), n);
    313            
     437
    314438            for (unsigned int i=1; i<_path.size(); ++i) {
    315439              Cost tmp = costDiff(_path[i-1], _path[i], n);
     
    319443              }
    320444            }
    321            
     445
    322446            _path.insert(_path.begin()+min, n);
    323             _fullcost += min_val;
    324           }
    325        
     447            _total += min_val;
     448          }
     449
    326450        private:
    327451          const FullGraph &_gr;
    328452          const CostMap &_cost;
    329453          std::vector<Node> &_path;
    330           Cost &_fullcost;
    331       };
    332  
    333       class CheapestInsert {
     454          Cost &_total;
     455      };
     456
     457      // Implementation of a special insertion method for the cheapest
     458      // selection rule
     459      class CheapestInsertion {
    334460        TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
    335461        public:
    336           CheapestInsert(const FullGraph &, const CostMap &,
    337                          std::vector<Node> &, Cost &fullcost) :
    338             _fullcost(fullcost) {}
    339          
     462          CheapestInsertion(const FullGraph &, const CostMap &,
     463                            std::vector<Node> &, Cost &total_cost) :
     464            _total(total_cost) {}
     465
    340466          void insert(Cost diff) const {
    341             _fullcost += diff;
    342           }
    343 
    344         private:
    345           Cost &_fullcost;
    346       }; 
    347      
    348      
    349       template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
    350       void start() {
    351         InitFunctor init(_gr, _cost, nodesPath, notused, sum);
    352         SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
    353         InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
    354        
    355         nodesPath = init.init();
    356        
    357         for (int i=0; i<_gr.nodeNum()-2; ++i) {
    358           insertNode.insert(selectNode.select());
    359         }
    360        
    361         sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
    362         for (unsigned int i=0; i<nodesPath.size()-1; ++i)
    363           sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
    364       }
    365    
    366       const FullGraph &_gr;
    367       const CostMap &_cost;
    368       std::vector<Node> notused;
    369       std::vector<Node> nodesPath;
    370       Cost sum;
     467            _total += diff;
     468          }
     469
     470        private:
     471          Cost &_total;
     472      };
     473
    371474  };
    372  
     475
    373476}; // namespace lemon
    374477
  • lemon/nearest_neighbor_tsp.h

    r1199 r1201  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
    220#define LEMON_NEAREST_NEIGHBOUR_TSP_H
    321
     22/// \ingroup tsp
     23/// \file
     24/// \brief Nearest neighbor algorithm for symmetric TSP
     25
    426#include <deque>
     27#include <limits>
    528#include <lemon/full_graph.h>
    6 #include <lemon/path.h>
    729#include <lemon/maps.h>
    830
    931namespace lemon {
    10  
    11   namespace nn_helper {
    12     template <class L>
    13     L dequeConvert(const std::deque<FullGraph::Node> &_path) {
    14       return L(_path.begin(), _path.end());
    15     }
    16 
    17     template <>
    18     std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
    19       return _path;
    20     }
    21   }
    22  
     32
     33  /// \brief Nearest neighbor algorithm for symmetric TSP.
     34  ///
     35  /// NearestNeighborTsp implements the nearest neighbor heuristic for solving
     36  /// symmetric \ref tsp "TSP".
     37  ///
     38  /// This is probably the simplest TSP heuristic.
     39  /// It starts with a minimum cost edge and at each step, it connects the
     40  /// nearest unvisited node to the current path.
     41  /// Finally, it connects the two end points of the path to form a tour.
     42  ///
     43  /// This method runs in O(n<sup>2</sup>) time.
     44  /// It quickly finds an effectively short tour for most TSP
     45  /// instances, but in special cases, it could yield a really bad
     46  /// (or even the worst) solution.
     47  ///
     48  /// \tparam CM Type of the cost map.
    2349  template <typename CM>
    24   class NearestNeighborTsp {
     50  class NearestNeighborTsp
     51  {
     52    public:
     53
     54      /// Type of the cost map
     55      typedef CM CostMap;
     56      /// Type of the edge costs
     57      typedef typename CM::Value Cost;
     58
    2559    private:
     60
    2661      GRAPH_TYPEDEFS(FullGraph);
    2762
     63      const FullGraph &_gr;
     64      const CostMap &_cost;
     65      Cost _sum;
     66      std::deque<Node> _path;
     67
    2868    public:
    29       typedef CM CostMap;
    30       typedef typename CM::Value Cost;
    31    
    32       NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
    33 
     69
     70      /// \brief Constructor
     71      ///
     72      /// Constructor.
     73      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     74      /// \param cost The cost map.
     75      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost)
     76        : _gr(gr), _cost(cost) {}
     77
     78      /// \name Execution Control
     79      /// @{
     80
     81      /// \brief Runs the algorithm.
     82      ///
     83      /// This function runs the algorithm.
     84      ///
     85      /// \return The total cost of the found tour.
    3486      Cost run() {
    3587        _path.clear();
    3688
     89        if (_gr.nodeNum() == 0) return _sum = 0;
     90        else if (_gr.nodeNum() == 1) {
     91          _path.push_back(_gr(0));
     92          return _sum = 0;
     93        }
     94
    3795        Edge min_edge1 = INVALID,
    3896             min_edge2 = INVALID;
    39        
     97
    4098        min_edge1 = mapMin(_gr, _cost);
    41 
    42         FullGraph::NodeMap<bool> used(_gr, false);
    43 
    44         Node n1 = _gr.u(min_edge1),
     99        Node n1 = _gr.u(min_edge1),
    45100             n2 = _gr.v(min_edge1);
    46        
    47101        _path.push_back(n1);
    48102        _path.push_back(n2);
    49103
     104        FullGraph::NodeMap<bool> used(_gr, false);
    50105        used[n1] = true;
    51106        used[n2] = true;
    52107
    53108        min_edge1 = INVALID;
    54 
    55109        while (int(_path.size()) != _gr.nodeNum()) {
    56110          if (min_edge1 == INVALID) {
    57             for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
    58               if (!used[_gr.runningNode(e)]) {
    59                 if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
    60                   min_edge1 = e;
     111            for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
     112              if (!used[_gr.runningNode(e)] &&
     113                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
     114                min_edge1 = e;
    61115              }
    62116            }
     
    64118
    65119          if (min_edge2 == INVALID) {
    66             for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
    67               if (!used[_gr.runningNode(e)]) {
    68                 if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
    69                   min_edge2 = e;
     120            for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
     121              if (!used[_gr.runningNode(e)] &&
     122                  (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
     123                min_edge2 = e;
    70124              }
    71125            }
    72126          }
    73127
    74           if ( _cost[min_edge1] < _cost[min_edge2] ) {
    75             n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
     128          if (_cost[min_edge1] < _cost[min_edge2]) {
     129            n1 = _gr.oppositeNode(n1, min_edge1);
    76130            _path.push_front(n1);
    77131
     
    79133            min_edge1 = INVALID;
    80134
    81             if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
     135            if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1)
    82136              min_edge2 = INVALID;
    83137          } else {
    84             n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
     138            n2 = _gr.oppositeNode(n2, min_edge2);
    85139            _path.push_back(n2);
    86140
     
    88142            min_edge2 = INVALID;
    89143
    90             if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
     144            if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2)
    91145              min_edge1 = INVALID;
    92146          }
    93147        }
    94148
    95         _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
    96         for (unsigned int i=0; i<_path.size()-1; ++i)
    97           _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
     149        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     150        for (int i = 0; i < int(_path.size())-1; ++i) {
     151          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     152        }
    98153
    99154        return _sum;
    100155      }
    101156
    102      
    103       template <typename L>
    104       void tourNodes(L &container) {
    105         container(nn_helper::dequeConvert<L>(_path));
    106       }
    107      
    108       template <template <typename> class L>
    109       L<Node> tourNodes() {
    110         return nn_helper::dequeConvert<L<Node> >(_path);
    111       }     
    112 
    113       const std::deque<Node>& tourNodes() {
     157      /// @}
     158
     159      /// \name Query Functions
     160      /// @{
     161
     162      /// \brief The total cost of the found tour.
     163      ///
     164      /// This function returns the total cost of the found tour.
     165      ///
     166      /// \pre run() must be called before using this function.
     167      Cost tourCost() const {
     168        return _sum;
     169      }
     170
     171      /// \brief Returns a const reference to the node sequence of the
     172      /// found tour.
     173      ///
     174      /// This function returns a const reference to the internal structure
     175      /// that stores the node sequence of the found tour.
     176      ///
     177      /// \pre run() must be called before using this function.
     178      const std::deque<Node>& tourNodes() const {
    114179        return _path;
    115180      }
    116      
    117       Path<FullGraph> tour() {
    118         Path<FullGraph> p;
    119         if (_path.size()<2)
    120           return p;
    121        
    122         for (unsigned int i=0; i<_path.size()-1; ++i) {
    123           p.addBack(_gr.arc(_path[i], _path[i+1]));
    124         }
    125         p.addBack(_gr.arc(_path.back(), _path.front()));
    126        
    127         return p;
    128       }
    129      
    130       Cost tourCost() {
    131         return _sum;
    132       }
    133      
    134 
    135   private:
    136     const FullGraph &_gr;
    137     const CostMap &_cost;
    138     Cost _sum;
    139     std::deque<Node> _path;
     181
     182      /// \brief Gives back the node sequence of the found tour.
     183      ///
     184      /// This function copies the node sequence of the found tour into
     185      /// the given standard container.
     186      ///
     187      /// \pre run() must be called before using this function.
     188      template <typename Container>
     189      void tourNodes(Container &container) const {
     190        container.assign(_path.begin(), _path.end());
     191      }
     192
     193      /// \brief Gives back the found tour as a path.
     194      ///
     195      /// This function copies the found tour as a list of arcs/edges into
     196      /// the given \ref concept::Path "path structure".
     197      ///
     198      /// \pre run() must be called before using this function.
     199      template <typename Path>
     200      void tour(Path &path) const {
     201        path.clear();
     202        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     203          path.addBack(_gr.arc(_path[i], _path[i+1]));
     204        }
     205        if (int(_path.size()) >= 2) {
     206          path.addBack(_gr.arc(_path.back(), _path.front()));
     207        }
     208      }
     209
     210      /// @}
     211
    140212  };
    141213
    142 
    143214}; // namespace lemon
    144215
  • lemon/opt2_tsp.h

    r1199 r1201  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2010
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#ifndef LEMON_OPT2_TSP_H
    220#define LEMON_OPT2_TSP_H
    321
     22/// \ingroup tsp
     23/// \file
     24/// \brief 2-opt algorithm for symmetric TSP
     25
    426#include <vector>
    527#include <lemon/full_graph.h>
    6 #include <lemon/path.h>
    728
    829namespace lemon {
    9  
    10   namespace opt2_helper {
    11     template <class L>
    12     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    13       return L(_path.begin(), _path.end());
    14     }
    15  
    16     template <>
    17     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    18       return _path;
    19     }
    20   }
    21  
     30
     31  /// \brief 2-opt algorithm for symmetric TSP.
     32  ///
     33  /// Opt2Tsp implements the 2-opt heuristic for solving
     34  /// symmetric \ref tsp "TSP".
     35  ///
     36  /// This algorithm starts with an initial tour and iteratively improves it.
     37  /// At each step, it removes two edges and the reconnects the created two
     38  /// paths in the other way if the resulting tour is shorter.
     39  /// The algorithm finishes when no such 2-opt move can be applied, and so
     40  /// the tour is 2-optimal.
     41  ///
     42  /// If no starting tour is given to the \ref run() function, then the
     43  /// algorithm uses the node sequence determined by the node IDs.
     44  /// Oherwise, it starts with the given tour.
     45  ///
     46  /// This is a relatively slow but powerful method.
     47  /// A typical usage of it is the improvement of a solution that is resulted
     48  /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
     49  ///
     50  /// \tparam CM Type of the cost map.
    2251  template <typename CM>
    23   class Opt2Tsp {
     52  class Opt2Tsp
     53  {
     54    public:
     55
     56      /// Type of the cost map
     57      typedef CM CostMap;
     58      /// Type of the edge costs
     59      typedef typename CM::Value Cost;
     60
    2461    private:
     62
    2563      GRAPH_TYPEDEFS(FullGraph);
    2664
     65      const FullGraph &_gr;
     66      const CostMap &_cost;
     67      Cost _sum;
     68      std::vector<int> _plist;
     69      std::vector<Node> _path;
     70
    2771    public:
    28       typedef CM CostMap;
    29       typedef typename CM::Value Cost;
    30      
    31    
    32       Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
    33             tmppath(_gr.nodeNum()*2) {
    34            
    35         for (int i=1; i<_gr.nodeNum()-1; ++i) {
    36           tmppath[2*i] = i-1;
    37           tmppath[2*i+1] = i+1;
    38         }
    39         tmppath[0] = _gr.nodeNum()-1;
    40         tmppath[1] = 1;
    41         tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
    42         tmppath[2*(_gr.nodeNum()-1)+1] = 0;
    43       }
    44      
    45       Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
    46               _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
    47 
    48         for (unsigned int i=1; i<path.size()-1; ++i) {
    49           tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
    50           tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
    51         }
    52        
    53         tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
    54         tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
    55         tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
    56         tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
    57       }
     72
     73      /// \brief Constructor
     74      ///
     75      /// Constructor.
     76      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     77      /// \param cost The cost map.
     78      Opt2Tsp(const FullGraph &gr, const CostMap &cost)
     79        : _gr(gr), _cost(cost) {}
     80
     81      /// \name Execution Control
     82      /// @{
     83
     84      /// \brief Runs the algorithm from scratch.
     85      ///
     86      /// This function runs the algorithm starting from the tour that is
     87      /// determined by the node ID sequence.
     88      ///
     89      /// \return The total cost of the found tour.
     90      Cost run() {
     91        _path.clear();
     92
     93        if (_gr.nodeNum() == 0) return _sum = 0;
     94        else if (_gr.nodeNum() == 1) {
     95          _path.push_back(_gr(0));
     96          return _sum = 0;
     97        }
     98        else if (_gr.nodeNum() == 2) {
     99          _path.push_back(_gr(0));
     100          _path.push_back(_gr(1));
     101          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     102        }
     103
     104        _plist.resize(2*_gr.nodeNum());
     105        for (int i = 1; i < _gr.nodeNum()-1; ++i) {
     106          _plist[2*i] = i-1;
     107          _plist[2*i+1] = i+1;
     108        }
     109        _plist[0] = _gr.nodeNum()-1;
     110        _plist[1] = 1;
     111        _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
     112        _plist[2*_gr.nodeNum()-1] = 0;
     113
     114        return start();
     115      }
     116
     117      /// \brief Runs the algorithm from the given tour.
     118      ///
     119      /// This function runs the algorithm starting from the given tour.
     120      ///
     121      /// \param tour The tour as a path structure. It must be a
     122      /// \ref checkPath() "valid path" containing excactly n arcs.
     123      ///
     124      /// \return The total cost of the found tour.
     125      template <typename Path>
     126      Cost run(const Path& tour) {
     127        _path.clear();
     128
     129        if (_gr.nodeNum() == 0) return _sum = 0;
     130        else if (_gr.nodeNum() == 1) {
     131          _path.push_back(_gr(0));
     132          return _sum = 0;
     133        }
     134        else if (_gr.nodeNum() == 2) {
     135          _path.push_back(_gr(0));
     136          _path.push_back(_gr(1));
     137          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     138        }
     139
     140        _plist.resize(2*_gr.nodeNum());
     141        typename Path::ArcIt it(tour);
     142        int first = _gr.id(_gr.source(it)),
     143            prev = first,
     144            curr = _gr.id(_gr.target(it)),
     145            next = -1;
     146        _plist[2*first+1] = curr;
     147        for (++it; it != INVALID; ++it) {
     148          next = _gr.id(_gr.target(it));
     149          _plist[2*curr] = prev;
     150          _plist[2*curr+1] = next;
     151          prev = curr;
     152          curr = next;
     153        }
     154        _plist[2*first] = prev;
     155
     156        return start();
     157      }
     158
     159      /// \brief Runs the algorithm from the given tour.
     160      ///
     161      /// This function runs the algorithm starting from the given tour.
     162      ///
     163      /// \param tour The tour as a node sequence. It must be a standard
     164      /// sequence container storing all <tt>Node</tt>s in the desired order.
     165      ///
     166      /// \return The total cost of the found tour.
     167      template <template <typename> class Container>
     168      Cost run(const Container<Node>& tour) {
     169        _path.clear();
     170
     171        if (_gr.nodeNum() == 0) return _sum = 0;
     172        else if (_gr.nodeNum() == 1) {
     173          _path.push_back(_gr(0));
     174          return _sum = 0;
     175        }
     176        else if (_gr.nodeNum() == 2) {
     177          _path.push_back(_gr(0));
     178          _path.push_back(_gr(1));
     179          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     180        }
     181
     182        _plist.resize(2*_gr.nodeNum());
     183        typename Container<Node>::const_iterator it = tour.begin();
     184        int first = _gr.id(*it),
     185            prev = first,
     186            curr = _gr.id(*(++it)),
     187            next = -1;
     188        _plist[2*first+1] = curr;
     189        for (++it; it != tour.end(); ++it) {
     190          next = _gr.id(*it);
     191          _plist[2*curr] = prev;
     192          _plist[2*curr+1] = next;
     193          prev = curr;
     194          curr = next;
     195        }
     196        _plist[2*first] = curr;
     197        _plist[2*curr] = prev;
     198        _plist[2*curr+1] = first;
     199
     200        return start();
     201      }
     202
     203      /// @}
     204
     205      /// \name Query Functions
     206      /// @{
     207
     208      /// \brief The total cost of the found tour.
     209      ///
     210      /// This function returns the total cost of the found tour.
     211      ///
     212      /// \pre run() must be called before using this function.
     213      Cost tourCost() const {
     214        return _sum;
     215      }
     216
     217      /// \brief Returns a const reference to the node sequence of the
     218      /// found tour.
     219      ///
     220      /// This function returns a const reference to the internal structure
     221      /// that stores the node sequence of the found tour.
     222      ///
     223      /// \pre run() must be called before using this function.
     224      const std::vector<Node>& tourNodes() const {
     225        return _path;
     226      }
     227
     228      /// \brief Gives back the node sequence of the found tour.
     229      ///
     230      /// This function copies the node sequence of the found tour into
     231      /// the given standard container.
     232      ///
     233      /// \pre run() must be called before using this function.
     234      template <typename Container>
     235      void tourNodes(Container &container) const {
     236        container.assign(_path.begin(), _path.end());
     237      }
     238
     239      /// \brief Gives back the found tour as a path.
     240      ///
     241      /// This function copies the found tour as a list of arcs/edges into
     242      /// the given \ref concept::Path "path structure".
     243      ///
     244      /// \pre run() must be called before using this function.
     245      template <typename Path>
     246      void tour(Path &path) const {
     247        path.clear();
     248        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     249          path.addBack(_gr.arc(_path[i], _path[i+1]));
     250        }
     251        if (int(_path.size()) >= 2) {
     252          path.addBack(_gr.arc(_path.back(), _path.front()));
     253        }
     254      }
     255
     256      /// @}
    58257
    59258    private:
    60       Cost c(int u, int v) {
    61         return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
    62       }
    63      
    64       class It {
     259
     260      // Iterator class for the linked list storage of the tour
     261      class PathListIt {
    65262        public:
    66           It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
    67           It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
    68 
    69           int next_index() const {
    70             return (tmppath[2*act]==last)? 2*act+1 : 2*act;
    71           }
    72          
    73           int prev_index() const {
    74             return (tmppath[2*act]==last)? 2*act : 2*act+1;
    75           }
    76          
     263          PathListIt(const std::vector<int> &pl, int i=0)
     264            : plist(&pl), act(i), last(pl[2*act]) {}
     265          PathListIt(const std::vector<int> &pl, int i, int l)
     266            : plist(&pl), act(i), last(l) {}
     267
     268          int nextIndex() const {
     269            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
     270          }
     271
     272          int prevIndex() const {
     273            return (*plist)[2*act] == last ? 2*act : 2*act+1;
     274          }
     275
    77276          int next() const {
    78             return tmppath[next_index()];
     277            int x = (*plist)[2*act];
     278            return x == last ? (*plist)[2*act+1] : x;
    79279          }
    80280
    81281          int prev() const {
    82             return tmppath[prev_index()];
    83           }
    84          
    85           It& operator++() {
     282            return last;
     283          }
     284
     285          PathListIt& operator++() {
    86286            int tmp = act;
    87287            act = next();
     
    89289            return *this;
    90290          }
    91          
     291
    92292          operator int() const {
    93293            return act;
    94294          }
    95          
     295
    96296        private:
    97           const std::vector<int> &tmppath;
     297          const std::vector<int> *plist;
    98298          int act;
    99299          int last;
    100300      };
    101301
    102       bool check(std::vector<int> &path, It i, It j) {
    103         if (c(i, i.next()) + c(j, j.next()) >
    104             c(i, j) + c(j.next(), i.next())) {
    105 
    106             path[ It(path, i.next(), i).prev_index() ] = j.next();
    107             path[ It(path, j.next(), j).prev_index() ] = i.next();
    108 
    109             path[i.next_index()] = j;
    110             path[j.next_index()] = i;
    111 
    112             return true;
    113         }
     302      // Checks and applies 2-opt move (if it improves the tour)
     303      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
     304        Node u  = _gr.nodeFromId(i),
     305             un = _gr.nodeFromId(i.next()),
     306             v  = _gr.nodeFromId(j),
     307             vn = _gr.nodeFromId(j.next());
     308
     309        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
     310            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
     311        {
     312          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
     313          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
     314
     315          _plist[i.nextIndex()] = j;
     316          _plist[j.nextIndex()] = i;
     317
     318          return true;
     319        }
     320
    114321        return false;
    115       }
    116      
    117     public:
    118      
    119       Cost run() {
    120         _path.clear();
    121 
    122         if (_gr.nodeNum()>3) {
    123 
    124 opt2_tsp_label:
    125           It i(tmppath);
    126           It j(tmppath, i, i.prev());
    127           ++j; ++j;
    128           for (; j.next()!=0; ++j) {
    129             if (check(tmppath, i, j))
    130               goto opt2_tsp_label;
    131           }
    132          
    133           for (++i; i.next()!=0; ++i) {
    134             It j(tmppath, i, i.prev());
    135             if (++j==0)
    136               break;
    137             if (++j==0)
    138               break;
    139            
    140             for (; j!=0; ++j) {
    141               if (check(tmppath, i, j))
    142                 goto opt2_tsp_label;
    143             }
    144           }
    145         }
    146 
    147         It k(tmppath);
    148         _path.push_back(_gr.nodeFromId(k));
    149         for (++k; k!=0; ++k)
    150           _path.push_back(_gr.nodeFromId(k));
    151 
    152        
    153 
    154         _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
    155         for (unsigned int i=0; i<_path.size()-1; ++i)
    156           _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
     322     }
     323
     324      // Executes the algorithm from the initial tour
     325      Cost start() {
     326
     327      restart_search:
     328        for (PathListIt i(_plist); true; ++i) {
     329          PathListIt j = i;
     330          if (++j == 0 || ++j == 0) break;
     331          for (; j != 0 && j != i.prev(); ++j) {
     332            if (checkOpt2(i, j))
     333              goto restart_search;
     334          }
     335        }
     336
     337        PathListIt i(_plist);
     338        _path.push_back(_gr.nodeFromId(i));
     339        for (++i; i != 0; ++i)
     340          _path.push_back(_gr.nodeFromId(i));
     341
     342        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     343        for (int i = 0; i < int(_path.size())-1; ++i) {
     344          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     345        }
     346
    157347        return _sum;
    158348      }
    159349
    160      
    161       template <typename L>
    162       void tourNodes(L &container) {
    163         container(opt2_helper::vectorConvert<L>(_path));
    164       }
    165      
    166       template <template <typename> class L>
    167       L<Node> tourNodes() {
    168         return opt2_helper::vectorConvert<L<Node> >(_path);
    169       }
    170 
    171       const std::vector<Node>& tourNodes() {
    172         return _path;
    173       }
    174      
    175       Path<FullGraph> tour() {
    176         Path<FullGraph> p;
    177         if (_path.size()<2)
    178           return p;
    179 
    180         for (unsigned int i=0; i<_path.size()-1; ++i) {
    181           p.addBack(_gr.arc(_path[i], _path[i+1]));
    182         }
    183         p.addBack(_gr.arc(_path.back(), _path.front()));
    184         return p;
    185       }
    186      
    187       Cost tourCost() {
    188         return _sum;
    189       }
    190      
    191 
    192   private:
    193     const FullGraph &_gr;
    194     const CostMap &_cost;
    195     Cost _sum;
    196     std::vector<int> tmppath;
    197     std::vector<Node> _path;
    198350  };
    199351
    200 
    201352}; // namespace lemon
    202353
Note: See TracChangeset for help on using the changeset viewer.