1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/greedy_tsp.h Sat Jan 08 21:59:56 2011 +0100
1.3 @@ -0,0 +1,176 @@
1.4 +#ifndef LEMON_GREEDY_TSP_H
1.5 +#define LEMON_GREEDY_TSP_H
1.6 +
1.7 +#include <lemon/path.h>
1.8 +#include <lemon/full_graph.h>
1.9 +#include <lemon/unionfind.h>
1.10 +#include <algorithm>
1.11 +
1.12 +namespace lemon {
1.13 +
1.14 + namespace greedy_tsp_helper {
1.15 +
1.16 + template <typename CostMap>
1.17 + class KeyComp {
1.18 + typedef typename CostMap::Key Key;
1.19 + const CostMap &cost;
1.20 +
1.21 + public:
1.22 + KeyComp(const CostMap &_cost) : cost(_cost) {}
1.23 +
1.24 + bool operator() (const Key &a, const Key &b) const {
1.25 + return cost[a] < cost[b];
1.26 + }
1.27 + };
1.28 +
1.29 +
1.30 + template <class L>
1.31 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.32 + return L(_path.begin(), _path.end());
1.33 + }
1.34 +
1.35 + template <>
1.36 + std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.37 + return _path;
1.38 + }
1.39 +
1.40 + }
1.41 +
1.42 +
1.43 + template <typename CM>
1.44 + class GreedyTsp {
1.45 + private:
1.46 + GRAPH_TYPEDEFS(FullGraph);
1.47 +
1.48 + public:
1.49 + typedef CM CostMap;
1.50 + typedef typename CM::Value Cost;
1.51 +
1.52 + GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
1.53 +
1.54 + Cost run() {
1.55 + typedef UnionFind<FullGraph::NodeMap<int> > Union;
1.56 + _nodes.clear();
1.57 +
1.58 + std::vector<int> path;
1.59 + path.resize(_gr.nodeNum()*2, -1);
1.60 +
1.61 + std::vector<typename CostMap::Key> sorted_edges;
1.62 + sorted_edges.reserve(_gr.edgeNum());
1.63 + for (EdgeIt n(_gr); n != INVALID; ++n)
1.64 + sorted_edges.push_back(n);
1.65 +
1.66 + std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
1.67 +
1.68 + FullGraph::NodeMap<int> nodemap(_gr);
1.69 + Union unionfind(nodemap);
1.70 +
1.71 + for (NodeIt n(_gr); n != INVALID; ++n)
1.72 + unionfind.insert(n);
1.73 +
1.74 + FullGraph::NodeMap<int> degree(_gr, 0);
1.75 +
1.76 + int nodesNum = 0, i = 0;
1.77 +
1.78 + while ( nodesNum != _gr.nodeNum()-1 ) {
1.79 + const Edge &e = sorted_edges[i];
1.80 +
1.81 + const Node u = _gr.u(e),
1.82 + v = _gr.v(e);
1.83 +
1.84 + if (degree[u]<=1 && degree[v]<=1) {
1.85 + if (unionfind.join(u, v)) {
1.86 + ++degree[u];
1.87 + ++degree[v];
1.88 + ++nodesNum;
1.89 +
1.90 + const int uid = _gr.id(u),
1.91 + vid = _gr.id(v);
1.92 +
1.93 +
1.94 + path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
1.95 + path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
1.96 + }
1.97 + }
1.98 +
1.99 + ++i;
1.100 + }
1.101 +
1.102 +
1.103 + for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
1.104 + if (path[i] == -1) {
1.105 + if (n==-1) {
1.106 + n = i;
1.107 + } else {
1.108 + path[n] = i/2;
1.109 + path[i] = n/2;
1.110 + break;
1.111 + }
1.112 + }
1.113 + }
1.114 +
1.115 +
1.116 + for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
1.117 + _nodes.push_back(_gr.nodeFromId(j));
1.118 +
1.119 + if (path[2*j] != last) {
1.120 + last = j;
1.121 + j = path[2*j];
1.122 + } else {
1.123 + last = j;
1.124 + j = path[2*j+1];
1.125 + }
1.126 + }
1.127 +
1.128 + _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
1.129 + for (unsigned int i=0; i<_nodes.size()-1; ++i)
1.130 + _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
1.131 +
1.132 + return _sum;
1.133 + }
1.134 +
1.135 +
1.136 +
1.137 + template <typename L>
1.138 + void tourNodes(L &container) {
1.139 + container(greedy_tsp_helper::vectorConvert<L>(_nodes));
1.140 + }
1.141 +
1.142 + template <template <typename> class L>
1.143 + L<Node> tourNodes() {
1.144 + return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
1.145 + }
1.146 +
1.147 + const std::vector<Node>& tourNodes() {
1.148 + return _nodes;
1.149 + }
1.150 +
1.151 + Path<FullGraph> tour() {
1.152 + Path<FullGraph> p;
1.153 + if (_nodes.size()<2)
1.154 + return p;
1.155 +
1.156 + for (unsigned int i=0; i<_nodes.size()-1; ++i) {
1.157 + p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
1.158 + }
1.159 +
1.160 + p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
1.161 +
1.162 + return p;
1.163 + }
1.164 +
1.165 + Cost tourCost() {
1.166 + return _sum;
1.167 + }
1.168 +
1.169 +
1.170 + private:
1.171 + const FullGraph &_gr;
1.172 + const CostMap &_cost;
1.173 + Cost _sum;
1.174 + std::vector<Node> _nodes;
1.175 + };
1.176 +
1.177 +}; // namespace lemon
1.178 +
1.179 +#endif