lemon-1.3: comparison lemon/christofides

equal deleted inserted replaced

-:d52bf89e78f7
+:343df894a6e5
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2010
+* Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 #include <lemon/kruskal.h>
 #include <lemon/matching.h>
 #include <lemon/euler.h>
 namespace lemon {
 /// \ingroup tsp
 ///
 /// \brief Christofides algorithm for symmetric TSP.
 ///
 /// ChristofidesTsp implements Christofides' heuristic for solving
 else if (_gr.nodeNum() == 2) {
 _path.push_back(_gr(0));
 _path.push_back(_gr(1));
 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
 }
 // Compute min. cost spanning tree
 std::vector<Edge> tree;
 kruskal(_gr, _cost, std::back_inserter(tree));
 FullGraph::NodeMap<int> deg(_gr, 0);
 for (int i = 0; i != int(tree.size()); ++i) {
 Edge e = tree[i];
 ++deg[_gr.u(e)];
 ++deg[_gr.v(e)];
 // Copy the induced subgraph of odd nodes
 std::vector<Node> odd_nodes;
 for (NodeIt u(_gr); u != INVALID; ++u) {
 if (deg[u] % 2 == 1) odd_nodes.push_back(u);
 }
 SmartGraph sgr;
 SmartGraph::EdgeMap<Cost> scost(sgr);
 for (int i = 0; i != int(odd_nodes.size()); ++i) {
 sgr.addNode();
 }
 SmartGraph::Edge e =
 sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
 scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
 }
 }
 // Compute min. cost perfect matching
 MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
 mwpm(sgr, scost);
 mwpm.run();
 for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
 if (mwpm.matching(e)) {
 tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
 odd_nodes[sgr.id(sgr.v(e))]) );
 }
 }
 // Join the spanning tree and the matching
 sgr.clear();
 for (int i = 0; i != _gr.nodeNum(); ++i) {
 sgr.addNode();
 }
 for (int i = 0; i != int(tree.size()); ++i) {
 return _sum;
 }
 /// @}
 /// \name Query Functions
 /// @{
 /// \brief 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.
 Cost tourCost() const {
 return _sum;
 }
 /// \brief Returns a const reference to the node sequence of the
 /// found tour.
 ///
 /// This function returns a const reference to a vector
 /// that stores the node sequence of the found tour.
 /// \pre run() must be called before using this function.
 template <typename Iterator>
 void tourNodes(Iterator out) const {
 std::copy(_path.begin(), _path.end(), out);
 }
 /// \brief Gives back the found tour as a path.
 ///
 /// This function copies the found tour as a list of arcs/edges into
 /// the given \ref lemon::concepts::Path "path structure".
 ///
 }
 if (int(_path.size()) >= 2) {
 path.addBack(_gr.arc(_path.back(), _path.front()));
 }
 }
 /// @}
 };
 }; // namespace lemon
 #endif

changeset 1174	1e5da3fc4fbc
parent 1076	97d978243703