1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/nearest_neighbor_tsp.h Sat Jan 08 21:59:56 2011 +0100
1.3 @@ -0,0 +1,145 @@
1.4 +#ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
1.5 +#define LEMON_NEAREST_NEIGHBOUR_TSP_H
1.6 +
1.7 +#include <deque>
1.8 +#include <lemon/full_graph.h>
1.9 +#include <lemon/path.h>
1.10 +#include <lemon/maps.h>
1.11 +
1.12 +namespace lemon {
1.13 +
1.14 + namespace nn_helper {
1.15 + template <class L>
1.16 + L dequeConvert(const std::deque<FullGraph::Node> &_path) {
1.17 + return L(_path.begin(), _path.end());
1.18 + }
1.19 +
1.20 + template <>
1.21 + std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
1.22 + return _path;
1.23 + }
1.24 + }
1.25 +
1.26 + template <typename CM>
1.27 + class NearestNeighborTsp {
1.28 + private:
1.29 + GRAPH_TYPEDEFS(FullGraph);
1.30 +
1.31 + public:
1.32 + typedef CM CostMap;
1.33 + typedef typename CM::Value Cost;
1.34 +
1.35 + NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
1.36 +
1.37 + Cost run() {
1.38 + _path.clear();
1.39 +
1.40 + Edge min_edge1 = INVALID,
1.41 + min_edge2 = INVALID;
1.42 +
1.43 + min_edge1 = mapMin(_gr, _cost);
1.44 +
1.45 + FullGraph::NodeMap<bool> used(_gr, false);
1.46 +
1.47 + Node n1 = _gr.u(min_edge1),
1.48 + n2 = _gr.v(min_edge1);
1.49 +
1.50 + _path.push_back(n1);
1.51 + _path.push_back(n2);
1.52 +
1.53 + used[n1] = true;
1.54 + used[n2] = true;
1.55 +
1.56 + min_edge1 = INVALID;
1.57 +
1.58 + while (int(_path.size()) != _gr.nodeNum()) {
1.59 + if (min_edge1 == INVALID) {
1.60 + for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
1.61 + if (!used[_gr.runningNode(e)]) {
1.62 + if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
1.63 + min_edge1 = e;
1.64 + }
1.65 + }
1.66 + }
1.67 +
1.68 + if (min_edge2 == INVALID) {
1.69 + for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
1.70 + if (!used[_gr.runningNode(e)]) {
1.71 + if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
1.72 + min_edge2 = e;
1.73 + }
1.74 + }
1.75 + }
1.76 +
1.77 + if ( _cost[min_edge1] < _cost[min_edge2] ) {
1.78 + n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
1.79 + _path.push_front(n1);
1.80 +
1.81 + used[n1] = true;
1.82 + min_edge1 = INVALID;
1.83 +
1.84 + if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
1.85 + min_edge2 = INVALID;
1.86 + } else {
1.87 + n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
1.88 + _path.push_back(n2);
1.89 +
1.90 + used[n2] = true;
1.91 + min_edge2 = INVALID;
1.92 +
1.93 + if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
1.94 + min_edge1 = INVALID;
1.95 + }
1.96 + }
1.97 +
1.98 + _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
1.99 + for (unsigned int i=0; i<_path.size()-1; ++i)
1.100 + _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
1.101 +
1.102 + return _sum;
1.103 + }
1.104 +
1.105 +
1.106 + template <typename L>
1.107 + void tourNodes(L &container) {
1.108 + container(nn_helper::dequeConvert<L>(_path));
1.109 + }
1.110 +
1.111 + template <template <typename> class L>
1.112 + L<Node> tourNodes() {
1.113 + return nn_helper::dequeConvert<L<Node> >(_path);
1.114 + }
1.115 +
1.116 + const std::deque<Node>& tourNodes() {
1.117 + return _path;
1.118 + }
1.119 +
1.120 + Path<FullGraph> tour() {
1.121 + Path<FullGraph> p;
1.122 + if (_path.size()<2)
1.123 + return p;
1.124 +
1.125 + for (unsigned int i=0; i<_path.size()-1; ++i) {
1.126 + p.addBack(_gr.arc(_path[i], _path[i+1]));
1.127 + }
1.128 + p.addBack(_gr.arc(_path.back(), _path.front()));
1.129 +
1.130 + return p;
1.131 + }
1.132 +
1.133 + Cost tourCost() {
1.134 + return _sum;
1.135 + }
1.136 +
1.137 +
1.138 + private:
1.139 + const FullGraph &_gr;
1.140 + const CostMap &_cost;
1.141 + Cost _sum;
1.142 + std::deque<Node> _path;
1.143 + };
1.144 +
1.145 +
1.146 +}; // namespace lemon
1.147 +
1.148 +#endif