COIN-OR::LEMON - Graph Library

source: lemon/lemon/greedy_tsp.h @ 1201:9a51db038228

Last change on this file since 1201:9a51db038228 was 1201:9a51db038228, checked in by Peter Kovacs <kpeter@…>, 9 years ago

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 size: 6.6 KB
Line 
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
19#ifndef LEMON_GREEDY_TSP_H
20#define LEMON_GREEDY_TSP_H
21
22/// \ingroup tsp
23/// \file
24/// \brief Greedy algorithm for symmetric TSP
25
26#include <vector>
27#include <algorithm>
28#include <lemon/full_graph.h>
29#include <lemon/unionfind.h>
30
31namespace lemon {
32
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;
68     
69    private:
70   
71      // Functor class to compare edges by their costs
72      class EdgeComp {
73      private:
74        const CostMap &_cost;
75
76      public:
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
84    public:
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.
102      Cost run() {
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;
115        sorted_edges.reserve(_gr.edgeNum());
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);
122        for (NodeIt n(_gr); n != INVALID; ++n)
123          union_find.insert(n);
124
125        FullGraph::NodeMap<int> degree(_gr, 0);
126
127        int nodesNum = 0, i = 0;
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
141              ++degree[u];
142              ++degree[v];
143              ++nodesNum;
144            }
145          }
146        }
147
148        for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
149          if (plist[i] == -1) {
150            if (n==-1) {
151              n = i;
152            } else {
153              plist[n] = i/2;
154              plist[i] = n/2;
155              break;
156            }
157          }
158        }
159
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];
165          } else {
166            last = next;
167            next = plist[2*next+1];
168          }
169        }
170
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        }
175
176        return _sum;
177      }
178
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 {
190        return _sum;
191      }
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
234  };
235
236}; // namespace lemon
237
238#endif
Note: See TracBrowser for help on using the repository browser.