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