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