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>
35 /// \brief Greedy algorithm for symmetric TSP.
37 /// GreedyTsp implements the greedy heuristic for solving
38 /// symmetric \ref tsp "TSP".
40 /// This algorithm is quite similar to the \ref NearestNeighborTsp
41 /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths.
42 /// At each step, the shortest possible edge is added to these paths
43 /// as long as it does not create a cycle of less than n edges and it does
44 /// not increase the degree of any node above two.
46 /// This method runs in O(n<sup>2</sup>log(n)) time.
47 /// It quickly finds a short tour for most TSP instances, but in special
48 /// cases, it could yield a really bad (or even the worst) solution.
50 /// \tparam CM Type of the cost map.
51 template <typename CM>
56 /// Type of the cost map
58 /// Type of the edge costs
59 typedef typename CM::Value Cost;
63 GRAPH_TYPEDEFS(FullGraph);
68 std::vector<Node> _path;
72 // Functor class to compare edges by their costs
78 EdgeComp(const CostMap &cost) : _cost(cost) {}
80 bool operator()(const Edge &a, const Edge &b) const {
81 return _cost[a] < _cost[b];
87 /// \brief Constructor
90 /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
91 /// \param cost The cost map.
92 GreedyTsp(const FullGraph &gr, const CostMap &cost)
93 : _gr(gr), _cost(cost) {}
95 /// \name Execution Control
98 /// \brief Runs the algorithm.
100 /// This function runs the algorithm.
102 /// \return The total cost of the found tour.
106 if (_gr.nodeNum() == 0) return _sum = 0;
107 else if (_gr.nodeNum() == 1) {
108 _path.push_back(_gr(0));
112 std::vector<int> plist;
113 plist.resize(_gr.nodeNum()*2, -1);
115 std::vector<Edge> sorted_edges;
116 sorted_edges.reserve(_gr.edgeNum());
117 for (EdgeIt e(_gr); e != INVALID; ++e)
118 sorted_edges.push_back(e);
119 std::sort(sorted_edges.begin(), sorted_edges.end(), EdgeComp(_cost));
121 FullGraph::NodeMap<int> item_int_map(_gr);
122 UnionFind<FullGraph::NodeMap<int> > union_find(item_int_map);
123 for (NodeIt n(_gr); n != INVALID; ++n)
124 union_find.insert(n);
126 FullGraph::NodeMap<int> degree(_gr, 0);
128 int nodesNum = 0, i = 0;
129 while (nodesNum != _gr.nodeNum()-1) {
130 Edge e = sorted_edges[i++];
134 if (degree[u] <= 1 && degree[v] <= 1) {
135 if (union_find.join(u, v)) {
136 const int uid = _gr.id(u),
139 plist[uid*2 + degree[u]] = vid;
140 plist[vid*2 + degree[v]] = uid;
149 for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
150 if (plist[i] == -1) {
161 for (int i=0, next=0, last=-1; i!=_gr.nodeNum(); ++i) {
162 _path.push_back(_gr.nodeFromId(next));
163 if (plist[2*next] != last) {
165 next = plist[2*next];
168 next = plist[2*next+1];
172 _sum = _cost[_gr.edge(_path.back(), _path.front())];
173 for (int i = 0; i < int(_path.size())-1; ++i) {
174 _sum += _cost[_gr.edge(_path[i], _path[i+1])];
182 /// \name Query Functions
185 /// \brief The total cost of the found tour.
187 /// This function returns the total cost of the found tour.
189 /// \pre run() must be called before using this function.
190 Cost tourCost() const {
194 /// \brief Returns a const reference to the node sequence of the
197 /// This function returns a const reference to a vector
198 /// that stores the node sequence of the found tour.
200 /// \pre run() must be called before using this function.
201 const std::vector<Node>& tourNodes() const {
205 /// \brief Gives back the node sequence of the found tour.
207 /// This function copies the node sequence of the found tour into
208 /// the given standard container.
210 /// \pre run() must be called before using this function.
211 template <typename Container>
212 void tourNodes(Container &container) const {
213 container.assign(_path.begin(), _path.end());
216 /// \brief Gives back the found tour as a path.
218 /// This function copies the found tour as a list of arcs/edges into
219 /// the given \ref concept::Path "path structure".
221 /// \pre run() must be called before using this function.
222 template <typename Path>
223 void tour(Path &path) const {
225 for (int i = 0; i < int(_path.size()) - 1; ++i) {
226 path.addBack(_gr.arc(_path[i], _path[i+1]));
228 if (int(_path.size()) >= 2) {
229 path.addBack(_gr.arc(_path.back(), _path.front()));
237 }; // namespace lemon