COIN-OR::LEMON - Graph Library

source: lemon/lemon/christofides_tsp.h @ 1199:ae0b056593a7

Last change on this file since 1199:ae0b056593a7 was 1199:ae0b056593a7, checked in by Gabor Varga <f4c3@…>, 9 years ago

Heuristic algorithms for symmetric TSP (#386)

File size: 3.5 KB
Line 
1#ifndef LEMON_CHRISTOFIDES_TSP_H
2#define LEMON_CHRISTOFIDES_TSP_H
3
4#include <lemon/full_graph.h>
5#include <lemon/smart_graph.h>
6#include <lemon/path.h>
7#include <lemon/kruskal.h>
8#include <lemon/matching.h>
9#include <lemon/adaptors.h>
10#include <lemon/maps.h>
11#include <lemon/euler.h>
12
13namespace lemon {
14 
15  namespace christofides_helper {
16    template <class L>
17    L vectorConvert(const std::vector<FullGraph::Node> &_path) {
18      return L(_path.begin(), _path.end());
19    }
20 
21    template <>
22    std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
23      return _path;
24    }
25  }
26 
27  template <typename CM>
28  class ChristofidesTsp {
29    private:
30      GRAPH_TYPEDEFS(SmartGraph);
31
32    public:
33      typedef typename CM::Value Cost;
34      typedef SmartGraph::EdgeMap<Cost> CostMap;
35   
36      ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) {
37        graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run();
38      }
39
40      Cost run() {
41        _path.clear();
42       
43        SmartGraph::EdgeMap<bool> tree(_gr);
44        kruskal(_gr, _cost, tree);
45       
46        FilterEdges<SmartGraph> treefiltered(_gr, tree);
47        InDegMap<FilterEdges<SmartGraph> > deg(treefiltered);
48       
49        SmartGraph::NodeMap<bool> oddfilter(_gr, false);
50        FilterNodes<SmartGraph> oddNodes(_gr, oddfilter);
51       
52        for (NodeIt n(_gr); n!=INVALID; ++n) {
53          if (deg[n]%2 == 1) {
54            oddNodes.enable(n);
55          }
56        }
57       
58        NegMap<CostMap> negmap(_cost);
59        MaxWeightedPerfectMatching<FilterNodes<SmartGraph>,
60                  NegMap<CostMap> > perfmatch(oddNodes, negmap);
61        perfmatch.run();
62       
63        for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) {
64          if (perfmatch.matching(e)) {
65            treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e)));
66          }
67        }
68       
69        FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false);
70        for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) {
71          if (seen[treefiltered.target(e)]==false) {
72            _path.push_back(nr[treefiltered.target(e)]);
73            seen[treefiltered.target(e)] = true;
74          }
75        }
76
77        _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ];
78        for (unsigned int i=0; i<_path.size()-1; ++i)
79          _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ];
80
81        return _sum;
82      }
83
84      template <typename L>
85      void tourNodes(L &container) {
86        container(christofides_helper::vectorConvert<L>(_path));
87      }
88     
89      template <template <typename> class L>
90      L<FullGraph::Node> tourNodes() {
91        return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path);
92      }
93
94      const std::vector<Node>& tourNodes() {
95        return _path;
96      }
97     
98      Path<FullGraph> tour() {
99        Path<FullGraph> p;
100        if (_path.size()<2)
101          return p;
102
103        for (unsigned int i=0; i<_path.size()-1; ++i) {
104          p.addBack(fullg.arc(_path[i], _path[i+1]));
105        }
106        p.addBack(fullg.arc(_path.back(), _path.front()));
107       
108        return p;
109      }
110     
111      Cost tourCost() {
112        return _sum;
113      }
114     
115
116  private:
117    SmartGraph _gr;
118    CostMap _cost;
119    Cost _sum;
120    const FullGraph &fullg;
121    const CM &fullcost;
122    std::vector<FullGraph::Node> _path;
123    SmartGraph::NodeMap<FullGraph::Node> nr;
124  };
125
126
127}; // namespace lemon
128
129#endif
Note: See TracBrowser for help on using the repository browser.