#ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H

 #define LEMON_NEAREST_NEIGHBOUR_TSP_H

 #include <deque>

 #include <lemon/full_graph.h>

 #include <lemon/path.h>

 #include <lemon/maps.h>

 namespace lemon {

   namespace nn_helper {

     template <class L>

     L dequeConvert(const std::deque<FullGraph::Node> &_path) {

       return L(_path.begin(), _path.end());

     }

     template <>

     std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {

       return _path;

     }

   }

   template <typename CM>

   class NearestNeighborTsp {

     private:

       GRAPH_TYPEDEFS(FullGraph);

     public:

       typedef CM CostMap;

       typedef typename CM::Value Cost;

       NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}

       Cost run() {

         _path.clear();

         Edge min_edge1 = INVALID,

              min_edge2 = INVALID;

         min_edge1 = mapMin(_gr, _cost);

         FullGraph::NodeMap<bool> used(_gr, false);

         Node n1 = _gr.u(min_edge1), 

              n2 = _gr.v(min_edge1);

         _path.push_back(n1);

         _path.push_back(n2);

         used[n1] = true;

         used[n2] = true;

         min_edge1 = INVALID;

         while (int(_path.size()) != _gr.nodeNum()) {

           if (min_edge1 == INVALID) {

             for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {

               if (!used[_gr.runningNode(e)]) {

                 if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])

                   min_edge1 = e;

               }

             }

           }

           if (min_edge2 == INVALID) {

             for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {

               if (!used[_gr.runningNode(e)]) {

                 if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])

                   min_edge2 = e;

               }

             }

           }

           if ( _cost[min_edge1] < _cost[min_edge2] ) {

             n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);

             _path.push_front(n1);

             used[n1] = true;

             min_edge1 = INVALID;

             if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)

               min_edge2 = INVALID;

           } else {

             n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);

             _path.push_back(n2);

             used[n2] = true;

             min_edge2 = INVALID;

             if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)

               min_edge1 = INVALID;

           }

         }

         _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];

         for (unsigned int i=0; i<_path.size()-1; ++i)

           _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];

         return _sum;

       }

       template <typename L>

       void tourNodes(L &container) {

         container(nn_helper::dequeConvert<L>(_path));

       }

       template <template <typename> class L>

       L<Node> tourNodes() {

         return nn_helper::dequeConvert<L<Node> >(_path);

       }      

       const std::deque<Node>& tourNodes() {

         return _path;

       }

       Path<FullGraph> tour() {

         Path<FullGraph> p;

         if (_path.size()<2)

           return p;

         for (unsigned int i=0; i<_path.size()-1; ++i) {

           p.addBack(_gr.arc(_path[i], _path[i+1]));

         }

         p.addBack(_gr.arc(_path.back(), _path.front()));

         return p;

       }

       Cost tourCost() {

         return _sum;

       }

   private:

     const FullGraph &_gr;

     const CostMap &_cost;

     Cost _sum;

     std::deque<Node> _path;

   };

 }; // namespace lemon

 #endif