COIN-OR::LEMON - Graph Library

Changeset 1201:9a51db038228 in lemon for lemon/greedy_tsp.h


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