1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_GREEDY_TSP_H
20 #define LEMON_GREEDY_TSP_H
24 /// \brief Greedy algorithm for symmetric TSP
28 #include <lemon/full_graph.h>
29 #include <lemon/unionfind.h>
33 /// \brief Greedy algorithm for symmetric TSP.
35 /// GreedyTsp implements the greedy heuristic for solving
36 /// symmetric \ref tsp "TSP".
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.
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.
49 /// \tparam CM Type of the cost map.
50 template <typename CM>
55 /// Type of the cost map
57 /// Type of the edge costs
58 typedef typename CM::Value Cost;
62 GRAPH_TYPEDEFS(FullGraph);
67 std::vector<Node> _path;
71 // Functor class to compare edges by their costs
77 EdgeComp(const CostMap &cost) : _cost(cost) {}
79 bool operator()(const Edge &a, const Edge &b) const {
80 return _cost[a] < _cost[b];
86 /// \brief 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) {}
94 /// \name Execution Control
97 /// \brief Runs the algorithm.
99 /// This function runs the algorithm.
101 /// \return The total cost of the found tour.
105 if (_gr.nodeNum() == 0) return _sum = 0;
106 else if (_gr.nodeNum() == 1) {
107 _path.push_back(_gr(0));
111 std::vector<int> plist;
112 plist.resize(_gr.nodeNum()*2, -1);
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));
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);
125 FullGraph::NodeMap<int> degree(_gr, 0);
127 int nodesNum = 0, i = 0;
128 while (nodesNum != _gr.nodeNum()-1) {
129 Edge e = sorted_edges[i++];
133 if (degree[u] <= 1 && degree[v] <= 1) {
134 if (union_find.join(u, v)) {
135 const int uid = _gr.id(u),
138 plist[uid*2 + degree[u]] = vid;
139 plist[vid*2 + degree[v]] = uid;
148 for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
149 if (plist[i] == -1) {
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) {
164 next = plist[2*next];
167 next = plist[2*next+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])];
181 /// \name Query Functions
184 /// \brief The total cost of the found tour.
186 /// This function returns the total cost of the found tour.
188 /// \pre run() must be called before using this function.
189 Cost tourCost() const {
193 /// \brief Returns a const reference to the node sequence of the
196 /// This function returns a const reference to the internal structure
197 /// that stores the node sequence of the found tour.
199 /// \pre run() must be called before using this function.
200 const std::vector<Node>& tourNodes() const {
204 /// \brief Gives back the node sequence of the found tour.
206 /// This function copies the node sequence of the found tour into
207 /// the given standard container.
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());
215 /// \brief Gives back the found tour as a path.
217 /// This function copies the found tour as a list of arcs/edges into
218 /// the given \ref concept::Path "path structure".
220 /// \pre run() must be called before using this function.
221 template <typename Path>
222 void tour(Path &path) const {
224 for (int i = 0; i < int(_path.size()) - 1; ++i) {
225 path.addBack(_gr.arc(_path[i], _path[i+1]));
227 if (int(_path.size()) >= 2) {
228 path.addBack(_gr.arc(_path.back(), _path.front()));
236 }; // namespace lemon