# source:lemon/lemon/nearest_neighbor_tsp.h@1199:ae0b056593a7

Last change on this file since 1199:ae0b056593a7 was 1199:ae0b056593a7, checked in by Gabor Varga <f4c3@…>, 11 years ago

Heuristic algorithms for symmetric TSP (#386)

File size: 3.5 KB
Line
1#ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
2#define LEMON_NEAREST_NEIGHBOUR_TSP_H
3
4#include <deque>
5#include <lemon/full_graph.h>
6#include <lemon/path.h>
7#include <lemon/maps.h>
8
9namespace lemon {
10
11  namespace nn_helper {
12    template <class L>
13    L dequeConvert(const std::deque<FullGraph::Node> &_path) {
14      return L(_path.begin(), _path.end());
15    }
16
17    template <>
18    std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
19      return _path;
20    }
21  }
22
23  template <typename CM>
24  class NearestNeighborTsp {
25    private:
26      GRAPH_TYPEDEFS(FullGraph);
27
28    public:
29      typedef CM CostMap;
30      typedef typename CM::Value Cost;
31
32      NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
33
34      Cost run() {
35        _path.clear();
36
37        Edge min_edge1 = INVALID,
38             min_edge2 = INVALID;
39
40        min_edge1 = mapMin(_gr, _cost);
41
42        FullGraph::NodeMap<bool> used(_gr, false);
43
44        Node n1 = _gr.u(min_edge1),
45             n2 = _gr.v(min_edge1);
46
47        _path.push_back(n1);
48        _path.push_back(n2);
49
50        used[n1] = true;
51        used[n2] = true;
52
53        min_edge1 = INVALID;
54
55        while (int(_path.size()) != _gr.nodeNum()) {
56          if (min_edge1 == INVALID) {
57            for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
58              if (!used[_gr.runningNode(e)]) {
59                if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
60                  min_edge1 = e;
61              }
62            }
63          }
64
65          if (min_edge2 == INVALID) {
66            for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
67              if (!used[_gr.runningNode(e)]) {
68                if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
69                  min_edge2 = e;
70              }
71            }
72          }
73
74          if ( _cost[min_edge1] < _cost[min_edge2] ) {
75            n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
76            _path.push_front(n1);
77
78            used[n1] = true;
79            min_edge1 = INVALID;
80
81            if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
82              min_edge2 = INVALID;
83          } else {
84            n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
85            _path.push_back(n2);
86
87            used[n2] = true;
88            min_edge2 = INVALID;
89
90            if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
91              min_edge1 = INVALID;
92          }
93        }
94
95        _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
96        for (unsigned int i=0; i<_path.size()-1; ++i)
97          _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
98
99        return _sum;
100      }
101
102
103      template <typename L>
104      void tourNodes(L &container) {
105        container(nn_helper::dequeConvert<L>(_path));
106      }
107
108      template <template <typename> class L>
109      L<Node> tourNodes() {
110        return nn_helper::dequeConvert<L<Node> >(_path);
111      }
112
113      const std::deque<Node>& tourNodes() {
114        return _path;
115      }
116
117      Path<FullGraph> tour() {
118        Path<FullGraph> p;
119        if (_path.size()<2)
120          return p;
121
122        for (unsigned int i=0; i<_path.size()-1; ++i) {
123          p.addBack(_gr.arc(_path[i], _path[i+1]));
124        }
125        p.addBack(_gr.arc(_path.back(), _path.front()));
126
127        return p;
128      }
129
130      Cost tourCost() {
131        return _sum;
132      }
133
134
135  private:
136    const FullGraph &_gr;
137    const CostMap &_cost;
138    Cost _sum;
139    std::deque<Node> _path;
140  };
141
142
143}; // namespace lemon
144
145#endif
Note: See TracBrowser for help on using the repository browser.