1.1 --- a/lemon/Makefile.am Tue Nov 16 07:46:01 2010 +0100
1.2 +++ b/lemon/Makefile.am Sat Jan 08 21:59:56 2011 +0100
1.3 @@ -64,6 +64,7 @@
1.4 lemon/bucket_heap.h \
1.5 lemon/capacity_scaling.h \
1.6 lemon/cbc.h \
1.7 + lemon/christofides_tsp.h \
1.8 lemon/circulation.h \
1.9 lemon/clp.h \
1.10 lemon/color.h \
1.11 @@ -89,11 +90,13 @@
1.12 lemon/glpk.h \
1.13 lemon/gomory_hu.h \
1.14 lemon/graph_to_eps.h \
1.15 + lemon/greedy_tsp.h \
1.16 lemon/grid_graph.h \
1.17 lemon/grosso_locatelli_pullan_mc.h \
1.18 lemon/hartmann_orlin_mmc.h \
1.19 lemon/howard_mmc.h \
1.20 lemon/hypercube_graph.h \
1.21 + lemon/insertion_tsp.h \
1.22 lemon/karp_mmc.h \
1.23 lemon/kruskal.h \
1.24 lemon/hao_orlin.h \
1.25 @@ -110,7 +113,9 @@
1.26 lemon/max_cardinality_search.h \
1.27 lemon/nagamochi_ibaraki.h \
1.28 lemon/nauty_reader.h \
1.29 + lemon/nearest_neighbor_tsp.h \
1.30 lemon/network_simplex.h \
1.31 + lemon/opt2_tsp.h \
1.32 lemon/pairing_heap.h \
1.33 lemon/path.h \
1.34 lemon/planarity.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/christofides_tsp.h Sat Jan 08 21:59:56 2011 +0100
2.3 @@ -0,0 +1,129 @@
2.4 +#ifndef LEMON_CHRISTOFIDES_TSP_H
2.5 +#define LEMON_CHRISTOFIDES_TSP_H
2.6 +
2.7 +#include <lemon/full_graph.h>
2.8 +#include <lemon/smart_graph.h>
2.9 +#include <lemon/path.h>
2.10 +#include <lemon/kruskal.h>
2.11 +#include <lemon/matching.h>
2.12 +#include <lemon/adaptors.h>
2.13 +#include <lemon/maps.h>
2.14 +#include <lemon/euler.h>
2.15 +
2.16 +namespace lemon {
2.17 +
2.18 + namespace christofides_helper {
2.19 + template <class L>
2.20 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
2.21 + return L(_path.begin(), _path.end());
2.22 + }
2.23 +
2.24 + template <>
2.25 + std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
2.26 + return _path;
2.27 + }
2.28 + }
2.29 +
2.30 + template <typename CM>
2.31 + class ChristofidesTsp {
2.32 + private:
2.33 + GRAPH_TYPEDEFS(SmartGraph);
2.34 +
2.35 + public:
2.36 + typedef typename CM::Value Cost;
2.37 + typedef SmartGraph::EdgeMap<Cost> CostMap;
2.38 +
2.39 + ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
2.40 + graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
2.41 + }
2.42 +
2.43 + Cost run() {
2.44 + _path.clear();
2.45 +
2.46 + SmartGraph::EdgeMap<bool> tree(_gr);
2.47 + kruskal(_gr, _cost, tree);
2.48 +
2.49 + FilterEdges<SmartGraph> treefiltered(_gr, tree);
2.50 + InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
2.51 +
2.52 + SmartGraph::NodeMap<bool> oddfilter(_gr, false);
2.53 + FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
2.54 +
2.55 + for (NodeIt n(_gr); n!=INVALID; ++n) {
2.56 + if (deg[n]%2 == 1) {
2.57 + oddNodes.enable(n);
2.58 + }
2.59 + }
2.60 +
2.61 + NegMap<CostMap> negmap(_cost);
2.62 + MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
2.63 + NegMap<CostMap> > perfmatch(oddNodes, negmap);
2.64 + perfmatch.run();
2.65 +
2.66 + for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
2.67 + if (perfmatch.matching(e)) {
2.68 + treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
2.69 + }
2.70 + }
2.71 +
2.72 + FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
2.73 + for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
2.74 + if (seen[treefiltered.target(e)]==false) {
2.75 + _path.push_back(nr[treefiltered.target(e)]);
2.76 + seen[treefiltered.target(e)] = true;
2.77 + }
2.78 + }
2.79 +
2.80 + _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
2.81 + for (unsigned int i=0; i<_path.size()-1; ++i)
2.82 + _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
2.83 +
2.84 + return _sum;
2.85 + }
2.86 +
2.87 + template <typename L>
2.88 + void tourNodes(L &container) {
2.89 + container(christofides_helper::vectorConvert<L>(_path));
2.90 + }
2.91 +
2.92 + template <template <typename> class L>
2.93 + L<FullGraph::Node> tourNodes() {
2.94 + return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
2.95 + }
2.96 +
2.97 + const std::vector<Node>& tourNodes() {
2.98 + return _path;
2.99 + }
2.100 +
2.101 + Path<FullGraph> tour() {
2.102 + Path<FullGraph> p;
2.103 + if (_path.size()<2)
2.104 + return p;
2.105 +
2.106 + for (unsigned int i=0; i<_path.size()-1; ++i) {
2.107 + p.addBack(fullg.arc(_path[i], _path[i+1]));
2.108 + }
2.109 + p.addBack(fullg.arc(_path.back(), _path.front()));
2.110 +
2.111 + return p;
2.112 + }
2.113 +
2.114 + Cost tourCost() {
2.115 + return _sum;
2.116 + }
2.117 +
2.118 +
2.119 + private:
2.120 + SmartGraph _gr;
2.121 + CostMap _cost;
2.122 + Cost _sum;
2.123 + const FullGraph &fullg;
2.124 + const CM &fullcost;
2.125 + std::vector<FullGraph::Node> _path;
2.126 + SmartGraph::NodeMap<FullGraph::Node> nr;
2.127 + };
2.128 +
2.129 +
2.130 +}; // namespace lemon
2.131 +
2.132 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/greedy_tsp.h Sat Jan 08 21:59:56 2011 +0100
3.3 @@ -0,0 +1,176 @@
3.4 +#ifndef LEMON_GREEDY_TSP_H
3.5 +#define LEMON_GREEDY_TSP_H
3.6 +
3.7 +#include <lemon/path.h>
3.8 +#include <lemon/full_graph.h>
3.9 +#include <lemon/unionfind.h>
3.10 +#include <algorithm>
3.11 +
3.12 +namespace lemon {
3.13 +
3.14 + namespace greedy_tsp_helper {
3.15 +
3.16 + template <typename CostMap>
3.17 + class KeyComp {
3.18 + typedef typename CostMap::Key Key;
3.19 + const CostMap &cost;
3.20 +
3.21 + public:
3.22 + KeyComp(const CostMap &_cost) : cost(_cost) {}
3.23 +
3.24 + bool operator() (const Key &a, const Key &b) const {
3.25 + return cost[a] < cost[b];
3.26 + }
3.27 + };
3.28 +
3.29 +
3.30 + template <class L>
3.31 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
3.32 + return L(_path.begin(), _path.end());
3.33 + }
3.34 +
3.35 + template <>
3.36 + std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
3.37 + return _path;
3.38 + }
3.39 +
3.40 + }
3.41 +
3.42 +
3.43 + template <typename CM>
3.44 + class GreedyTsp {
3.45 + private:
3.46 + GRAPH_TYPEDEFS(FullGraph);
3.47 +
3.48 + public:
3.49 + typedef CM CostMap;
3.50 + typedef typename CM::Value Cost;
3.51 +
3.52 + GreedyTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
3.53 +
3.54 + Cost run() {
3.55 + typedef UnionFind<FullGraph::NodeMap<int> > Union;
3.56 + _nodes.clear();
3.57 +
3.58 + std::vector<int> path;
3.59 + path.resize(_gr.nodeNum()*2, -1);
3.60 +
3.61 + std::vector<typename CostMap::Key> sorted_edges;
3.62 + sorted_edges.reserve(_gr.edgeNum());
3.63 + for (EdgeIt n(_gr); n != INVALID; ++n)
3.64 + sorted_edges.push_back(n);
3.65 +
3.66 + std::sort(sorted_edges.begin(), sorted_edges.end(), greedy_tsp_helper::KeyComp<CostMap>(_cost));
3.67 +
3.68 + FullGraph::NodeMap<int> nodemap(_gr);
3.69 + Union unionfind(nodemap);
3.70 +
3.71 + for (NodeIt n(_gr); n != INVALID; ++n)
3.72 + unionfind.insert(n);
3.73 +
3.74 + FullGraph::NodeMap<int> degree(_gr, 0);
3.75 +
3.76 + int nodesNum = 0, i = 0;
3.77 +
3.78 + while ( nodesNum != _gr.nodeNum()-1 ) {
3.79 + const Edge &e = sorted_edges[i];
3.80 +
3.81 + const Node u = _gr.u(e),
3.82 + v = _gr.v(e);
3.83 +
3.84 + if (degree[u]<=1 && degree[v]<=1) {
3.85 + if (unionfind.join(u, v)) {
3.86 + ++degree[u];
3.87 + ++degree[v];
3.88 + ++nodesNum;
3.89 +
3.90 + const int uid = _gr.id(u),
3.91 + vid = _gr.id(v);
3.92 +
3.93 +
3.94 + path[uid*2 + (path[uid*2]==-1 ? 0 : 1)] = vid;
3.95 + path[vid*2 + (path[vid*2]==-1 ? 0 : 1)] = uid;
3.96 + }
3.97 + }
3.98 +
3.99 + ++i;
3.100 + }
3.101 +
3.102 +
3.103 + for (int i=0, n=-1; i<_gr.nodeNum()*2; ++i) {
3.104 + if (path[i] == -1) {
3.105 + if (n==-1) {
3.106 + n = i;
3.107 + } else {
3.108 + path[n] = i/2;
3.109 + path[i] = n/2;
3.110 + break;
3.111 + }
3.112 + }
3.113 + }
3.114 +
3.115 +
3.116 + for (int i=0, j=0, last=-1; i!=_gr.nodeNum(); ++i) {
3.117 + _nodes.push_back(_gr.nodeFromId(j));
3.118 +
3.119 + if (path[2*j] != last) {
3.120 + last = j;
3.121 + j = path[2*j];
3.122 + } else {
3.123 + last = j;
3.124 + j = path[2*j+1];
3.125 + }
3.126 + }
3.127 +
3.128 + _sum = _cost[_gr.edge(_nodes.back(), _nodes.front())];
3.129 + for (unsigned int i=0; i<_nodes.size()-1; ++i)
3.130 + _sum += _cost[_gr.edge(_nodes[i], _nodes[i+1])];
3.131 +
3.132 + return _sum;
3.133 + }
3.134 +
3.135 +
3.136 +
3.137 + template <typename L>
3.138 + void tourNodes(L &container) {
3.139 + container(greedy_tsp_helper::vectorConvert<L>(_nodes));
3.140 + }
3.141 +
3.142 + template <template <typename> class L>
3.143 + L<Node> tourNodes() {
3.144 + return greedy_tsp_helper::vectorConvert<L<Node> >(_nodes);
3.145 + }
3.146 +
3.147 + const std::vector<Node>& tourNodes() {
3.148 + return _nodes;
3.149 + }
3.150 +
3.151 + Path<FullGraph> tour() {
3.152 + Path<FullGraph> p;
3.153 + if (_nodes.size()<2)
3.154 + return p;
3.155 +
3.156 + for (unsigned int i=0; i<_nodes.size()-1; ++i) {
3.157 + p.addBack(_gr.arc(_nodes[i], _nodes[i+1]));
3.158 + }
3.159 +
3.160 + p.addBack(_gr.arc(_nodes.back(), _nodes.front()));
3.161 +
3.162 + return p;
3.163 + }
3.164 +
3.165 + Cost tourCost() {
3.166 + return _sum;
3.167 + }
3.168 +
3.169 +
3.170 + private:
3.171 + const FullGraph &_gr;
3.172 + const CostMap &_cost;
3.173 + Cost _sum;
3.174 + std::vector<Node> _nodes;
3.175 + };
3.176 +
3.177 +}; // namespace lemon
3.178 +
3.179 +#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/insertion_tsp.h Sat Jan 08 21:59:56 2011 +0100
4.3 @@ -0,0 +1,375 @@
4.4 +#ifndef LEMON_INSERTION_TSP_H
4.5 +#define LEMON_INSERTION_TSP_H
4.6 +
4.7 +#include <lemon/full_graph.h>
4.8 +#include <lemon/path.h>
4.9 +#include <lemon/maps.h>
4.10 +#include <lemon/random.h>
4.11 +#include <vector>
4.12 +
4.13 +namespace lemon {
4.14 +
4.15 + namespace insertion_tsp_helper {
4.16 +
4.17 + template <class L>
4.18 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
4.19 + return L(_path.begin(), _path.end());
4.20 + };
4.21 +
4.22 + template <>
4.23 + std::vector<FullGraph::Node> vectorConvert(
4.24 + const std::vector<FullGraph::Node> &_path) {
4.25 + return _path;
4.26 + };
4.27 +
4.28 + };
4.29 +
4.30 + template <typename CM>
4.31 + class InsertionTsp {
4.32 + private:
4.33 + GRAPH_TYPEDEFS(FullGraph);
4.34 +
4.35 + public:
4.36 + typedef CM CostMap;
4.37 + typedef typename CM::Value Cost;
4.38 +
4.39 + InsertionTsp(const FullGraph &gr, const CostMap &cost) :
4.40 + _gr(gr), _cost(cost) {}
4.41 +
4.42 + enum InsertionMethod {
4.43 + INSERT_NEAREST,
4.44 + INSERT_FARTHEST,
4.45 + INSERT_CHEAPEST,
4.46 + INSERT_RANDOM
4.47 + };
4.48 +
4.49 + Cost run(InsertionMethod method = INSERT_FARTHEST) {
4.50 + switch (method) {
4.51 + case INSERT_NEAREST:
4.52 + start<InitTour<true>, NearestSelection, DefaultInsert>();
4.53 + break;
4.54 + case INSERT_FARTHEST:
4.55 + start<InitTour<false>, FarthestSelection, DefaultInsert>();
4.56 + break;
4.57 + case INSERT_CHEAPEST:
4.58 + start<InitTour<true>, CheapestSelection, CheapestInsert>();
4.59 + break;
4.60 + case INSERT_RANDOM:
4.61 + start<InitTour<true>, RandomSelection, DefaultInsert>();
4.62 + break;
4.63 + }
4.64 + return sum;
4.65 + }
4.66 +
4.67 + template <typename L>
4.68 + void tourNodes(L &container) {
4.69 + container(insertion_tsp_helper::vectorConvert<L>(nodesPath));
4.70 + }
4.71 +
4.72 + template <template <typename> class L>
4.73 + L<Node> tourNodes() {
4.74 + return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);
4.75 + }
4.76 +
4.77 + const std::vector<Node>& tourNodes() {
4.78 + return nodesPath;
4.79 + }
4.80 +
4.81 + Path<FullGraph> tour() {
4.82 + Path<FullGraph> p;
4.83 + if (nodesPath.size()<2)
4.84 + return p;
4.85 +
4.86 + for (unsigned int i=0; i<nodesPath.size()-1; ++i)
4.87 + p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));
4.88 +
4.89 + p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));
4.90 + return p;
4.91 + }
4.92 +
4.93 + Cost tourCost() {
4.94 + return sum;
4.95 + }
4.96 +
4.97 +
4.98 + private:
4.99 +
4.100 + template <bool MIN>
4.101 + class InitTour {
4.102 + public:
4.103 + InitTour(const FullGraph &gr, const CostMap &cost,
4.104 + std::vector<Node> &used, std::vector<Node> ¬used,
4.105 + Cost &fullcost) :
4.106 + _gr(gr), _cost(cost), _used(used), _notused(notused),
4.107 + _fullcost(fullcost) {}
4.108 +
4.109 + std::vector<Node> init() const {
4.110 + Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);
4.111 + std::vector<Node> path;
4.112 + path.push_back(_gr.u(min));
4.113 + path.push_back(_gr.v(min));
4.114 +
4.115 + _used.clear();
4.116 + _notused.clear();
4.117 + for (NodeIt n(_gr); n!=INVALID; ++n) {
4.118 + if (n != _gr.u(min) && n != _gr.v(min)) {
4.119 + _notused.push_back(n);
4.120 + }
4.121 + }
4.122 + _used.push_back(_gr.u(min));
4.123 + _used.push_back(_gr.v(min));
4.124 +
4.125 + _fullcost = _cost[min]*2;
4.126 + return path;
4.127 + }
4.128 +
4.129 + private:
4.130 + const FullGraph &_gr;
4.131 + const CostMap &_cost;
4.132 + std::vector<Node> &_used;
4.133 + std::vector<Node> &_notused;
4.134 + Cost &_fullcost;
4.135 + };
4.136 +
4.137 + class NearestSelection {
4.138 + public:
4.139 + NearestSelection(const FullGraph &gr, const CostMap &cost,
4.140 + std::vector<Node> &used, std::vector<Node> ¬used) :
4.141 + _gr(gr), _cost(cost), _used(used), _notused(notused) {}
4.142 +
4.143 + Node select() const {
4.144 +
4.145 + Cost insert_val =
4.146 + std::numeric_limits<Cost>::max();
4.147 + int insert_node = -1;
4.148 +
4.149 + for (unsigned int i=0; i<_notused.size(); ++i) {
4.150 + Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
4.151 + int min_node = 0;
4.152 +
4.153 + for (unsigned int j=1; j<_used.size(); ++j) {
4.154 + if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
4.155 + min_val = _cost[_gr.edge(_notused[i], _used[j])];
4.156 + min_node = j;
4.157 + }
4.158 + }
4.159 +
4.160 + if (insert_val > min_val) {
4.161 + insert_val = min_val;
4.162 + insert_node = i;
4.163 + }
4.164 + }
4.165 +
4.166 + Node n = _notused[insert_node];
4.167 + _notused.erase(_notused.begin()+insert_node);
4.168 +
4.169 + return n;
4.170 + }
4.171 +
4.172 + private:
4.173 + const FullGraph &_gr;
4.174 + const CostMap &_cost;
4.175 + std::vector<Node> &_used;
4.176 + std::vector<Node> &_notused;
4.177 + };
4.178 +
4.179 + class FarthestSelection {
4.180 + public:
4.181 + FarthestSelection(const FullGraph &gr, const CostMap &cost,
4.182 + std::vector<Node> &used, std::vector<Node> ¬used) :
4.183 + _gr(gr), _cost(cost), _used(used), _notused(notused) {}
4.184 +
4.185 + Node select() const {
4.186 +
4.187 + Cost insert_val =
4.188 + std::numeric_limits<Cost>::min();
4.189 + int insert_node = -1;
4.190 +
4.191 + for (unsigned int i=0; i<_notused.size(); ++i) {
4.192 + Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];
4.193 + int min_node = 0;
4.194 +
4.195 + for (unsigned int j=1; j<_used.size(); ++j) {
4.196 + if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {
4.197 + min_val = _cost[_gr.edge(_notused[i], _used[j])];
4.198 + min_node = j;
4.199 + }
4.200 + }
4.201 +
4.202 + if (insert_val < min_val || insert_node == -1) {
4.203 + insert_val = min_val;
4.204 + insert_node = i;
4.205 + }
4.206 + }
4.207 +
4.208 + Node n = _notused[insert_node];
4.209 + _notused.erase(_notused.begin()+insert_node);
4.210 +
4.211 + return n;
4.212 + }
4.213 +
4.214 + private:
4.215 + const FullGraph &_gr;
4.216 + const CostMap &_cost;
4.217 + std::vector<Node> &_used;
4.218 + std::vector<Node> &_notused;
4.219 + };
4.220 +
4.221 +
4.222 + class CheapestSelection {
4.223 + private:
4.224 + Cost costDiff(Node u, Node v, Node w) const {
4.225 + return
4.226 + _cost[_gr.edge(u, w)] +
4.227 + _cost[_gr.edge(v, w)] -
4.228 + _cost[_gr.edge(u, v)];
4.229 + }
4.230 +
4.231 + public:
4.232 + CheapestSelection(const FullGraph &gr, const CostMap &cost,
4.233 + std::vector<Node> &used, std::vector<Node> ¬used) :
4.234 + _gr(gr), _cost(cost), _used(used), _notused(notused) {}
4.235 +
4.236 + Cost select() const {
4.237 + int insert_notused = -1;
4.238 + int best_insert_index = -1;
4.239 + Cost insert_val =
4.240 + std::numeric_limits<Cost>::max();
4.241 +
4.242 + for (unsigned int i=0; i<_notused.size(); ++i) {
4.243 + int min = i;
4.244 + int best_insert_tmp = 0;
4.245 + Cost min_val =
4.246 + costDiff(_used.front(), _used.back(), _notused[i]);
4.247 +
4.248 + for (unsigned int j=1; j<_used.size(); ++j) {
4.249 + Cost tmp =
4.250 + costDiff(_used[j-1], _used[j], _notused[i]);
4.251 +
4.252 + if (min_val > tmp) {
4.253 + min = i;
4.254 + min_val = tmp;
4.255 + best_insert_tmp = j;
4.256 + }
4.257 + }
4.258 +
4.259 + if (insert_val > min_val) {
4.260 + insert_notused = min;
4.261 + insert_val = min_val;
4.262 + best_insert_index = best_insert_tmp;
4.263 + }
4.264 + }
4.265 +
4.266 + _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);
4.267 + _notused.erase(_notused.begin()+insert_notused);
4.268 +
4.269 + return insert_val;
4.270 + }
4.271 +
4.272 + private:
4.273 + const FullGraph &_gr;
4.274 + const CostMap &_cost;
4.275 + std::vector<Node> &_used;
4.276 + std::vector<Node> &_notused;
4.277 + };
4.278 +
4.279 + class RandomSelection {
4.280 + public:
4.281 + RandomSelection(const FullGraph &, const CostMap &,
4.282 + std::vector<Node> &, std::vector<Node> ¬used) :
4.283 + _notused(notused) {
4.284 + rnd.seedFromTime();
4.285 + }
4.286 +
4.287 + Node select() const {
4.288 + const int index = rnd[_notused.size()];
4.289 + Node n = _notused[index];
4.290 + _notused.erase(_notused.begin()+index);
4.291 + return n;
4.292 + }
4.293 + private:
4.294 + std::vector<Node> &_notused;
4.295 + };
4.296 +
4.297 +
4.298 + class DefaultInsert {
4.299 + private:
4.300 + Cost costDiff(Node u, Node v, Node w) const {
4.301 + return
4.302 + _cost[_gr.edge(u, w)] +
4.303 + _cost[_gr.edge(v, w)] -
4.304 + _cost[_gr.edge(u, v)];
4.305 + }
4.306 +
4.307 + public:
4.308 + DefaultInsert(const FullGraph &gr, const CostMap &cost,
4.309 + std::vector<Node> &path, Cost &fullcost) :
4.310 + _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}
4.311 +
4.312 + void insert(Node n) const {
4.313 + int min = 0;
4.314 + Cost min_val =
4.315 + costDiff(_path.front(), _path.back(), n);
4.316 +
4.317 + for (unsigned int i=1; i<_path.size(); ++i) {
4.318 + Cost tmp = costDiff(_path[i-1], _path[i], n);
4.319 + if (tmp < min_val) {
4.320 + min = i;
4.321 + min_val = tmp;
4.322 + }
4.323 + }
4.324 +
4.325 + _path.insert(_path.begin()+min, n);
4.326 + _fullcost += min_val;
4.327 + }
4.328 +
4.329 + private:
4.330 + const FullGraph &_gr;
4.331 + const CostMap &_cost;
4.332 + std::vector<Node> &_path;
4.333 + Cost &_fullcost;
4.334 + };
4.335 +
4.336 + class CheapestInsert {
4.337 + TEMPLATE_GRAPH_TYPEDEFS(FullGraph);
4.338 + public:
4.339 + CheapestInsert(const FullGraph &, const CostMap &,
4.340 + std::vector<Node> &, Cost &fullcost) :
4.341 + _fullcost(fullcost) {}
4.342 +
4.343 + void insert(Cost diff) const {
4.344 + _fullcost += diff;
4.345 + }
4.346 +
4.347 + private:
4.348 + Cost &_fullcost;
4.349 + };
4.350 +
4.351 +
4.352 + template <class InitFunctor, class SelectionFunctor, class InsertFunctor>
4.353 + void start() {
4.354 + InitFunctor init(_gr, _cost, nodesPath, notused, sum);
4.355 + SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);
4.356 + InsertFunctor insertNode(_gr, _cost, nodesPath, sum);
4.357 +
4.358 + nodesPath = init.init();
4.359 +
4.360 + for (int i=0; i<_gr.nodeNum()-2; ++i) {
4.361 + insertNode.insert(selectNode.select());
4.362 + }
4.363 +
4.364 + sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];
4.365 + for (unsigned int i=0; i<nodesPath.size()-1; ++i)
4.366 + sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];
4.367 + }
4.368 +
4.369 + const FullGraph &_gr;
4.370 + const CostMap &_cost;
4.371 + std::vector<Node> notused;
4.372 + std::vector<Node> nodesPath;
4.373 + Cost sum;
4.374 + };
4.375 +
4.376 +}; // namespace lemon
4.377 +
4.378 +#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/nearest_neighbor_tsp.h Sat Jan 08 21:59:56 2011 +0100
5.3 @@ -0,0 +1,145 @@
5.4 +#ifndef LEMON_NEAREST_NEIGHBOUR_TSP_H
5.5 +#define LEMON_NEAREST_NEIGHBOUR_TSP_H
5.6 +
5.7 +#include <deque>
5.8 +#include <lemon/full_graph.h>
5.9 +#include <lemon/path.h>
5.10 +#include <lemon/maps.h>
5.11 +
5.12 +namespace lemon {
5.13 +
5.14 + namespace nn_helper {
5.15 + template <class L>
5.16 + L dequeConvert(const std::deque<FullGraph::Node> &_path) {
5.17 + return L(_path.begin(), _path.end());
5.18 + }
5.19 +
5.20 + template <>
5.21 + std::deque<FullGraph::Node> dequeConvert(const std::deque<FullGraph::Node> &_path) {
5.22 + return _path;
5.23 + }
5.24 + }
5.25 +
5.26 + template <typename CM>
5.27 + class NearestNeighborTsp {
5.28 + private:
5.29 + GRAPH_TYPEDEFS(FullGraph);
5.30 +
5.31 + public:
5.32 + typedef CM CostMap;
5.33 + typedef typename CM::Value Cost;
5.34 +
5.35 + NearestNeighborTsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost) {}
5.36 +
5.37 + Cost run() {
5.38 + _path.clear();
5.39 +
5.40 + Edge min_edge1 = INVALID,
5.41 + min_edge2 = INVALID;
5.42 +
5.43 + min_edge1 = mapMin(_gr, _cost);
5.44 +
5.45 + FullGraph::NodeMap<bool> used(_gr, false);
5.46 +
5.47 + Node n1 = _gr.u(min_edge1),
5.48 + n2 = _gr.v(min_edge1);
5.49 +
5.50 + _path.push_back(n1);
5.51 + _path.push_back(n2);
5.52 +
5.53 + used[n1] = true;
5.54 + used[n2] = true;
5.55 +
5.56 + min_edge1 = INVALID;
5.57 +
5.58 + while (int(_path.size()) != _gr.nodeNum()) {
5.59 + if (min_edge1 == INVALID) {
5.60 + for (IncEdgeIt e(_gr, n1); e!=INVALID; ++e) {
5.61 + if (!used[_gr.runningNode(e)]) {
5.62 + if (min_edge1==INVALID || _cost[min_edge1] > _cost[e])
5.63 + min_edge1 = e;
5.64 + }
5.65 + }
5.66 + }
5.67 +
5.68 + if (min_edge2 == INVALID) {
5.69 + for (IncEdgeIt e(_gr, n2); e!=INVALID; ++e) {
5.70 + if (!used[_gr.runningNode(e)]) {
5.71 + if (min_edge2==INVALID || _cost[min_edge2] > _cost[e])
5.72 + min_edge2 = e;
5.73 + }
5.74 + }
5.75 + }
5.76 +
5.77 + if ( _cost[min_edge1] < _cost[min_edge2] ) {
5.78 + n1 = (_gr.u(min_edge1) == n1) ? _gr.v(min_edge1) : _gr.u(min_edge1);
5.79 + _path.push_front(n1);
5.80 +
5.81 + used[n1] = true;
5.82 + min_edge1 = INVALID;
5.83 +
5.84 + if (_gr.u(min_edge2)==n1 || _gr.v(min_edge2)==n1)
5.85 + min_edge2 = INVALID;
5.86 + } else {
5.87 + n2 = (_gr.u(min_edge2) == n2) ? _gr.v(min_edge2) : _gr.u(min_edge2);
5.88 + _path.push_back(n2);
5.89 +
5.90 + used[n2] = true;
5.91 + min_edge2 = INVALID;
5.92 +
5.93 + if (_gr.u(min_edge1)==n2 || _gr.v(min_edge1)==n2)
5.94 + min_edge1 = INVALID;
5.95 + }
5.96 + }
5.97 +
5.98 + _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
5.99 + for (unsigned int i=0; i<_path.size()-1; ++i)
5.100 + _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
5.101 +
5.102 + return _sum;
5.103 + }
5.104 +
5.105 +
5.106 + template <typename L>
5.107 + void tourNodes(L &container) {
5.108 + container(nn_helper::dequeConvert<L>(_path));
5.109 + }
5.110 +
5.111 + template <template <typename> class L>
5.112 + L<Node> tourNodes() {
5.113 + return nn_helper::dequeConvert<L<Node> >(_path);
5.114 + }
5.115 +
5.116 + const std::deque<Node>& tourNodes() {
5.117 + return _path;
5.118 + }
5.119 +
5.120 + Path<FullGraph> tour() {
5.121 + Path<FullGraph> p;
5.122 + if (_path.size()<2)
5.123 + return p;
5.124 +
5.125 + for (unsigned int i=0; i<_path.size()-1; ++i) {
5.126 + p.addBack(_gr.arc(_path[i], _path[i+1]));
5.127 + }
5.128 + p.addBack(_gr.arc(_path.back(), _path.front()));
5.129 +
5.130 + return p;
5.131 + }
5.132 +
5.133 + Cost tourCost() {
5.134 + return _sum;
5.135 + }
5.136 +
5.137 +
5.138 + private:
5.139 + const FullGraph &_gr;
5.140 + const CostMap &_cost;
5.141 + Cost _sum;
5.142 + std::deque<Node> _path;
5.143 + };
5.144 +
5.145 +
5.146 +}; // namespace lemon
5.147 +
5.148 +#endif
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/opt2_tsp.h Sat Jan 08 21:59:56 2011 +0100
6.3 @@ -0,0 +1,203 @@
6.4 +#ifndef LEMON_OPT2_TSP_H
6.5 +#define LEMON_OPT2_TSP_H
6.6 +
6.7 +#include <vector>
6.8 +#include <lemon/full_graph.h>
6.9 +#include <lemon/path.h>
6.10 +
6.11 +namespace lemon {
6.12 +
6.13 + namespace opt2_helper {
6.14 + template <class L>
6.15 + L vectorConvert(const std::vector<FullGraph::Node> &_path) {
6.16 + return L(_path.begin(), _path.end());
6.17 + }
6.18 +
6.19 + template <>
6.20 + std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
6.21 + return _path;
6.22 + }
6.23 + }
6.24 +
6.25 + template <typename CM>
6.26 + class Opt2Tsp {
6.27 + private:
6.28 + GRAPH_TYPEDEFS(FullGraph);
6.29 +
6.30 + public:
6.31 + typedef CM CostMap;
6.32 + typedef typename CM::Value Cost;
6.33 +
6.34 +
6.35 + Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
6.36 + tmppath(_gr.nodeNum()*2) {
6.37 +
6.38 + for (int i=1; i<_gr.nodeNum()-1; ++i) {
6.39 + tmppath[2*i] = i-1;
6.40 + tmppath[2*i+1] = i+1;
6.41 + }
6.42 + tmppath[0] = _gr.nodeNum()-1;
6.43 + tmppath[1] = 1;
6.44 + tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
6.45 + tmppath[2*(_gr.nodeNum()-1)+1] = 0;
6.46 + }
6.47 +
6.48 + Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
6.49 + _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
6.50 +
6.51 + for (unsigned int i=1; i<path.size()-1; ++i) {
6.52 + tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
6.53 + tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
6.54 + }
6.55 +
6.56 + tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
6.57 + tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
6.58 + tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
6.59 + tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
6.60 + }
6.61 +
6.62 + private:
6.63 + Cost c(int u, int v) {
6.64 + return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
6.65 + }
6.66 +
6.67 + class It {
6.68 + public:
6.69 + It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
6.70 + It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
6.71 +
6.72 + int next_index() const {
6.73 + return (tmppath[2*act]==last)? 2*act+1 : 2*act;
6.74 + }
6.75 +
6.76 + int prev_index() const {
6.77 + return (tmppath[2*act]==last)? 2*act : 2*act+1;
6.78 + }
6.79 +
6.80 + int next() const {
6.81 + return tmppath[next_index()];
6.82 + }
6.83 +
6.84 + int prev() const {
6.85 + return tmppath[prev_index()];
6.86 + }
6.87 +
6.88 + It& operator++() {
6.89 + int tmp = act;
6.90 + act = next();
6.91 + last = tmp;
6.92 + return *this;
6.93 + }
6.94 +
6.95 + operator int() const {
6.96 + return act;
6.97 + }
6.98 +
6.99 + private:
6.100 + const std::vector<int> &tmppath;
6.101 + int act;
6.102 + int last;
6.103 + };
6.104 +
6.105 + bool check(std::vector<int> &path, It i, It j) {
6.106 + if (c(i, i.next()) + c(j, j.next()) >
6.107 + c(i, j) + c(j.next(), i.next())) {
6.108 +
6.109 + path[ It(path, i.next(), i).prev_index() ] = j.next();
6.110 + path[ It(path, j.next(), j).prev_index() ] = i.next();
6.111 +
6.112 + path[i.next_index()] = j;
6.113 + path[j.next_index()] = i;
6.114 +
6.115 + return true;
6.116 + }
6.117 + return false;
6.118 + }
6.119 +
6.120 + public:
6.121 +
6.122 + Cost run() {
6.123 + _path.clear();
6.124 +
6.125 + if (_gr.nodeNum()>3) {
6.126 +
6.127 +opt2_tsp_label:
6.128 + It i(tmppath);
6.129 + It j(tmppath, i, i.prev());
6.130 + ++j; ++j;
6.131 + for (; j.next()!=0; ++j) {
6.132 + if (check(tmppath, i, j))
6.133 + goto opt2_tsp_label;
6.134 + }
6.135 +
6.136 + for (++i; i.next()!=0; ++i) {
6.137 + It j(tmppath, i, i.prev());
6.138 + if (++j==0)
6.139 + break;
6.140 + if (++j==0)
6.141 + break;
6.142 +
6.143 + for (; j!=0; ++j) {
6.144 + if (check(tmppath, i, j))
6.145 + goto opt2_tsp_label;
6.146 + }
6.147 + }
6.148 + }
6.149 +
6.150 + It k(tmppath);
6.151 + _path.push_back(_gr.nodeFromId(k));
6.152 + for (++k; k!=0; ++k)
6.153 + _path.push_back(_gr.nodeFromId(k));
6.154 +
6.155 +
6.156 +
6.157 + _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
6.158 + for (unsigned int i=0; i<_path.size()-1; ++i)
6.159 + _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
6.160 + return _sum;
6.161 + }
6.162 +
6.163 +
6.164 + template <typename L>
6.165 + void tourNodes(L &container) {
6.166 + container(opt2_helper::vectorConvert<L>(_path));
6.167 + }
6.168 +
6.169 + template <template <typename> class L>
6.170 + L<Node> tourNodes() {
6.171 + return opt2_helper::vectorConvert<L<Node> >(_path);
6.172 + }
6.173 +
6.174 + const std::vector<Node>& tourNodes() {
6.175 + return _path;
6.176 + }
6.177 +
6.178 + Path<FullGraph> tour() {
6.179 + Path<FullGraph> p;
6.180 + if (_path.size()<2)
6.181 + return p;
6.182 +
6.183 + for (unsigned int i=0; i<_path.size()-1; ++i) {
6.184 + p.addBack(_gr.arc(_path[i], _path[i+1]));
6.185 + }
6.186 + p.addBack(_gr.arc(_path.back(), _path.front()));
6.187 + return p;
6.188 + }
6.189 +
6.190 + Cost tourCost() {
6.191 + return _sum;
6.192 + }
6.193 +
6.194 +
6.195 + private:
6.196 + const FullGraph &_gr;
6.197 + const CostMap &_cost;
6.198 + Cost _sum;
6.199 + std::vector<int> tmppath;
6.200 + std::vector<Node> _path;
6.201 + };
6.202 +
6.203 +
6.204 +}; // namespace lemon
6.205 +
6.206 +#endif