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