COIN-OR::LEMON - Graph Library

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?.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.