/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

 #include <lemon/kruskal.h>

 #include <lemon/kruskal.h>

 #include <lemon/matching.h>

 #include <lemon/matching.h>

 #include <lemon/euler.h>

 #include <lemon/euler.h>

 namespace lemon {

 namespace lemon {

   /// \ingroup tsp

   /// \ingroup tsp

   ///

   ///

   /// \brief Christofides algorithm for symmetric TSP.

   /// \brief Christofides algorithm for symmetric TSP.

   ///

   ///

   /// ChristofidesTsp implements Christofides' heuristic for solving

   /// ChristofidesTsp implements Christofides' heuristic for solving

         else if (_gr.nodeNum() == 2) {

         else if (_gr.nodeNum() == 2) {

           _path.push_back(_gr(0));

           _path.push_back(_gr(0));

           _path.push_back(_gr(1));

           _path.push_back(_gr(1));

           return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];

           return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];

         }

         }

         // Compute min. cost spanning tree

         // Compute min. cost spanning tree

         std::vector<Edge> tree;

         std::vector<Edge> tree;

         kruskal(_gr, _cost, std::back_inserter(tree));

         kruskal(_gr, _cost, std::back_inserter(tree));

         FullGraph::NodeMap<int> deg(_gr, 0);

         FullGraph::NodeMap<int> deg(_gr, 0);

         for (int i = 0; i != int(tree.size()); ++i) {

         for (int i = 0; i != int(tree.size()); ++i) {

           Edge e = tree[i];

           Edge e = tree[i];

           ++deg[_gr.u(e)];

           ++deg[_gr.u(e)];

           ++deg[_gr.v(e)];

           ++deg[_gr.v(e)];

         // Copy the induced subgraph of odd nodes

         // Copy the induced subgraph of odd nodes

         std::vector<Node> odd_nodes;

         std::vector<Node> odd_nodes;

         for (NodeIt u(_gr); u != INVALID; ++u) {

         for (NodeIt u(_gr); u != INVALID; ++u) {

           if (deg[u] % 2 == 1) odd_nodes.push_back(u);

           if (deg[u] % 2 == 1) odd_nodes.push_back(u);

         }

         }

         SmartGraph sgr;

         SmartGraph sgr;

         SmartGraph::EdgeMap<Cost> scost(sgr);

         SmartGraph::EdgeMap<Cost> scost(sgr);

         for (int i = 0; i != int(odd_nodes.size()); ++i) {

         for (int i = 0; i != int(odd_nodes.size()); ++i) {

           sgr.addNode();

           sgr.addNode();

         }

         }

             SmartGraph::Edge e =

             SmartGraph::Edge e =

               sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));

               sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));

             scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];

             scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];

           }

           }

         }

         }

         // Compute min. cost perfect matching

         // Compute min. cost perfect matching

         MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >

         MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >

           mwpm(sgr, scost);

           mwpm(sgr, scost);

         mwpm.run();

         mwpm.run();

         for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {

         for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {

           if (mwpm.matching(e)) {

           if (mwpm.matching(e)) {

             tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],

             tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],

                                      odd_nodes[sgr.id(sgr.v(e))]) );

                                      odd_nodes[sgr.id(sgr.v(e))]) );

           }

           }

         }

         }

         sgr.clear();

         sgr.clear();

         for (int i = 0; i != _gr.nodeNum(); ++i) {

         for (int i = 0; i != _gr.nodeNum(); ++i) {

           sgr.addNode();

           sgr.addNode();

         }

         }

         for (int i = 0; i != int(tree.size()); ++i) {

         for (int i = 0; i != int(tree.size()); ++i) {

         return _sum;

         return _sum;

       }

       }

       /// @}

       /// @}

       /// \name Query Functions

       /// \name Query Functions

       /// @{

       /// @{

       /// \brief The total cost of the found tour.

       /// \brief The total cost of the found tour.

       ///

       ///

       /// This function returns the total cost of the found tour.

       /// This function returns the total cost of the found tour.

       ///

       ///

       /// \pre run() must be called before using this function.

       /// \pre run() must be called before using this function.

       Cost tourCost() const {

       Cost tourCost() const {

         return _sum;

         return _sum;

       }

       }

       /// \brief Returns a const reference to the node sequence of the

       /// \brief Returns a const reference to the node sequence of the

       /// found tour.

       /// found tour.

       ///

       ///

       /// This function returns a const reference to a vector

       /// This function returns a const reference to a vector

       /// that stores the node sequence of the found tour.

       /// that stores the node sequence of the found tour.

       /// \pre run() must be called before using this function.

       /// \pre run() must be called before using this function.

       template <typename Iterator>

       template <typename Iterator>

       void tourNodes(Iterator out) const {

       void tourNodes(Iterator out) const {

         std::copy(_path.begin(), _path.end(), out);

         std::copy(_path.begin(), _path.end(), out);

       }

       }

       /// \brief Gives back the found tour as a path.

       /// \brief Gives back the found tour as a path.

       ///

       ///

       /// This function copies the found tour as a list of arcs/edges into

       /// This function copies the found tour as a list of arcs/edges into

       /// the given \ref lemon::concepts::Path "path structure".

       /// the given \ref lemon::concepts::Path "path structure".

       ///

       ///

         }

         }

         if (int(_path.size()) >= 2) {

         if (int(_path.size()) >= 2) {

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

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

         }

         }

       }

       }

       /// @}

       /// @}

   };

   };

 }; // namespace lemon

 }; // namespace lemon

 #endif

 #endif