lemon: lemon/insertion_tsp.h@ae0b056593a7

     1 #ifndef LEMON_INSERTION_TSP_H

     2 #define LEMON_INSERTION_TSP_H

     4 #include <lemon/full_graph.h>

     5 #include <lemon/path.h>

     6 #include <lemon/maps.h>

     7 #include <lemon/random.h>

     8 #include <vector>

    10 namespace lemon {

    12   namespace insertion_tsp_helper {

    14     template <class L>

    15     L vectorConvert(const std::vector<FullGraph::Node> &_path) {

    16       return L(_path.begin(), _path.end());

    17     };

    19     template <>

    20     std::vector<FullGraph::Node> vectorConvert(

    21         const std::vector<FullGraph::Node> &_path) {

    22       return _path;

    23     };

    25   };

    27   template <typename CM>

    28   class InsertionTsp {

    29     private:

    30       GRAPH_TYPEDEFS(FullGraph);

    32     public:

    33       typedef CM CostMap;

    34       typedef typename CM::Value Cost;

    36       InsertionTsp(const FullGraph &gr, const CostMap &cost) :

    37             _gr(gr), _cost(cost) {}

    39       enum InsertionMethod {

    40         INSERT_NEAREST,

    41         INSERT_FARTHEST,

    42         INSERT_CHEAPEST,

    43         INSERT_RANDOM

    44       };

    46       Cost run(InsertionMethod method = INSERT_FARTHEST) {

    47         switch (method) {

    48           case INSERT_NEAREST:

    49             start<InitTour<true>, NearestSelection, DefaultInsert>();

    50             break;

    51           case INSERT_FARTHEST:

    52             start<InitTour<false>, FarthestSelection, DefaultInsert>();

    53             break;

    54           case INSERT_CHEAPEST:

    55             start<InitTour<true>, CheapestSelection, CheapestInsert>();

    56             break;

    57           case INSERT_RANDOM:

    58             start<InitTour<true>, RandomSelection, DefaultInsert>();

    59             break;

    60         }

    61         return sum;

    62       }

    64       template <typename L>

    65       void tourNodes(L &container) {

    66         container(insertion_tsp_helper::vectorConvert<L>(nodesPath));

    67       }

    69       template <template <typename> class L>

    70       L<Node> tourNodes() {

    71         return insertion_tsp_helper::vectorConvert<L<Node> >(nodesPath);

    72       }

    74       const std::vector<Node>& tourNodes() {

    75         return nodesPath;

    76       }

    78       Path<FullGraph> tour() {

    79         Path<FullGraph> p;

    80         if (nodesPath.size()<2)

    81           return p;

    83         for (unsigned int i=0; i<nodesPath.size()-1; ++i)

    84           p.addBack(_gr.arc(nodesPath[i], nodesPath[i+1]));

    86         p.addBack(_gr.arc(nodesPath.back(), nodesPath.front()));

    87         return p;

    88       }

    90       Cost tourCost() {

    91         return sum;

    92       }

    95     private:

    97       template <bool MIN>

    98       class InitTour {

    99         public:

   100           InitTour(const FullGraph &gr, const CostMap &cost,

   101                    std::vector<Node> &used, std::vector<Node> &notused,

   102                    Cost &fullcost) :

   103               _gr(gr), _cost(cost), _used(used), _notused(notused),

   104               _fullcost(fullcost) {}

   106           std::vector<Node> init() const {

   107             Edge min = (MIN) ? mapMin(_gr, _cost) : mapMax(_gr, _cost);

   108             std::vector<Node> path;

   109             path.push_back(_gr.u(min));

   110             path.push_back(_gr.v(min));

   112             _used.clear();

   113             _notused.clear();

   114             for (NodeIt n(_gr); n!=INVALID; ++n) {

   115               if (n != _gr.u(min) && n != _gr.v(min)) {

   116                 _notused.push_back(n);

   117               }

   118             }

   119             _used.push_back(_gr.u(min));

   120             _used.push_back(_gr.v(min));

   122             _fullcost = _cost[min]*2;

   123             return path;

   124           }

   126         private:

   127           const FullGraph &_gr;

   128           const CostMap &_cost;

   129           std::vector<Node> &_used;

   130           std::vector<Node> &_notused;

   131           Cost &_fullcost;

   132       };

   134       class NearestSelection {

   135         public:

   136           NearestSelection(const FullGraph &gr, const CostMap &cost,

   137                            std::vector<Node> &used, std::vector<Node> &notused) :

   138               _gr(gr), _cost(cost), _used(used), _notused(notused) {}

   140           Node select() const {

   142             Cost insert_val =

   143               std::numeric_limits<Cost>::max();

   144             int insert_node = -1;

   146             for (unsigned int i=0; i<_notused.size(); ++i) {

   147               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];

   148               int min_node = 0;

   150               for (unsigned int j=1; j<_used.size(); ++j) {

   151                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {

   152                     min_val = _cost[_gr.edge(_notused[i], _used[j])];

   153                     min_node = j;

   154                 }

   155               }

   157               if (insert_val > min_val) {

   158                 insert_val = min_val;

   159                 insert_node = i;

   160               }

   161             }

   163             Node n = _notused[insert_node];

   164             _notused.erase(_notused.begin()+insert_node);

   166             return n;

   167           }

   169         private:

   170           const FullGraph &_gr;

   171           const CostMap &_cost;

   172           std::vector<Node> &_used;

   173           std::vector<Node> &_notused;

   174       };

   176       class FarthestSelection {

   177         public:

   178           FarthestSelection(const FullGraph &gr, const CostMap &cost,

   179                             std::vector<Node> &used, std::vector<Node> &notused) :

   180               _gr(gr), _cost(cost), _used(used), _notused(notused) {}

   182           Node select() const {

   184             Cost insert_val =

   185               std::numeric_limits<Cost>::min();

   186             int insert_node = -1;

   188             for (unsigned int i=0; i<_notused.size(); ++i) {

   189               Cost min_val = _cost[_gr.edge(_notused[i], _used[0])];

   190               int min_node = 0;

   192               for (unsigned int j=1; j<_used.size(); ++j) {

   193                 if (min_val > _cost[_gr.edge(_notused[i], _used[j])]) {

   194                   min_val = _cost[_gr.edge(_notused[i], _used[j])];

   195                   min_node = j;

   196                 }

   197               }

   199               if (insert_val < min_val || insert_node == -1) {

   200                 insert_val = min_val;

   201                 insert_node = i;

   202               }

   203             }

   205             Node n = _notused[insert_node];

   206             _notused.erase(_notused.begin()+insert_node);

   208             return n;

   209           }

   211         private:

   212           const FullGraph &_gr;

   213           const CostMap &_cost;

   214           std::vector<Node> &_used;

   215           std::vector<Node> &_notused;

   216       };

   219       class CheapestSelection {

   220         private:

   221           Cost costDiff(Node u, Node v, Node w) const {

   222             return

   223               _cost[_gr.edge(u, w)] +

   224               _cost[_gr.edge(v, w)] -

   225               _cost[_gr.edge(u, v)];

   226           }

   228         public:

   229           CheapestSelection(const FullGraph &gr, const CostMap &cost,

   230                             std::vector<Node> &used, std::vector<Node> &notused) :

   231               _gr(gr), _cost(cost), _used(used), _notused(notused) {}

   233           Cost select() const {

   234             int insert_notused = -1;

   235             int best_insert_index = -1;

   236             Cost insert_val =

   237               std::numeric_limits<Cost>::max();

   239             for (unsigned int i=0; i<_notused.size(); ++i) {

   240               int min = i;

   241               int best_insert_tmp = 0;

   242               Cost min_val =

   243                 costDiff(_used.front(), _used.back(), _notused[i]);

   245               for (unsigned int j=1; j<_used.size(); ++j) {

   246                 Cost tmp =

   247                   costDiff(_used[j-1], _used[j], _notused[i]);

   249                 if (min_val > tmp) {

   250                   min = i;

   251                   min_val = tmp;

   252                   best_insert_tmp = j;

   253                 }

   254               }

   256               if (insert_val > min_val) {

   257                 insert_notused = min;

   258                 insert_val = min_val;

   259                 best_insert_index = best_insert_tmp;

   260               }

   261             }

   263             _used.insert(_used.begin()+best_insert_index, _notused[insert_notused]);

   264             _notused.erase(_notused.begin()+insert_notused);

   266             return insert_val;

   267           }

   269         private:

   270           const FullGraph &_gr;

   271           const CostMap &_cost;

   272           std::vector<Node> &_used;

   273           std::vector<Node> &_notused;

   274       };

   276       class RandomSelection {

   277         public:

   278           RandomSelection(const FullGraph &, const CostMap &,

   279                             std::vector<Node> &, std::vector<Node> &notused) :

   280                            _notused(notused) {

   281             rnd.seedFromTime();

   282           }

   284           Node select() const {

   285             const int index = rnd[_notused.size()];

   286             Node n = _notused[index];

   287             _notused.erase(_notused.begin()+index);

   288             return n;

   289           }

   290         private:

   291           std::vector<Node> &_notused;

   292       };

   295       class DefaultInsert {

   296         private:

   297           Cost costDiff(Node u, Node v, Node w) const {

   298             return

   299               _cost[_gr.edge(u, w)] +

   300               _cost[_gr.edge(v, w)] -

   301               _cost[_gr.edge(u, v)];

   302           }

   304         public:

   305           DefaultInsert(const FullGraph &gr, const CostMap &cost,

   306                         std::vector<Node> &path, Cost &fullcost) :

   307             _gr(gr), _cost(cost), _path(path), _fullcost(fullcost) {}

   309           void insert(Node n) const {

   310             int min = 0;

   311             Cost min_val =

   312               costDiff(_path.front(), _path.back(), n);

   314             for (unsigned int i=1; i<_path.size(); ++i) {

   315               Cost tmp = costDiff(_path[i-1], _path[i], n);

   316               if (tmp < min_val) {

   317                 min = i;

   318                 min_val = tmp;

   319               }

   320             }

   322             _path.insert(_path.begin()+min, n);

   323             _fullcost += min_val;

   324           }

   326         private:

   327           const FullGraph &_gr;

   328           const CostMap &_cost;

   329           std::vector<Node> &_path;

   330           Cost &_fullcost;

   331       };

   333       class CheapestInsert {

   334         TEMPLATE_GRAPH_TYPEDEFS(FullGraph);

   335         public:

   336           CheapestInsert(const FullGraph &, const CostMap &,

   337                          std::vector<Node> &, Cost &fullcost) :

   338             _fullcost(fullcost) {}

   340           void insert(Cost diff) const {

   341             _fullcost += diff;

   342           }

   344         private:

   345           Cost &_fullcost;

   346       };

   349       template <class InitFunctor, class SelectionFunctor, class InsertFunctor>

   350       void start() {

   351         InitFunctor init(_gr, _cost, nodesPath, notused, sum);

   352         SelectionFunctor selectNode(_gr, _cost, nodesPath, notused);

   353         InsertFunctor insertNode(_gr, _cost, nodesPath, sum);

   355         nodesPath = init.init();

   357         for (int i=0; i<_gr.nodeNum()-2; ++i) {

   358           insertNode.insert(selectNode.select());

   359         }

   361         sum = _cost[ _gr.edge(nodesPath.front(), nodesPath.back()) ];

   362         for (unsigned int i=0; i<nodesPath.size()-1; ++i)

   363           sum += _cost[ _gr.edge(nodesPath[i], nodesPath[i+1]) ];

   364       }

   366       const FullGraph &_gr;

   367       const CostMap &_cost;

   368       std::vector<Node> notused;

   369       std::vector<Node> nodesPath;

   370       Cost sum;

   371   };

   373 }; // namespace lemon

   375 #endif

author	Gabor Varga <f4c3@inf.elte.hu>
	Sat, 08 Jan 2011 21:59:56 +0100
changeset 1199	ae0b056593a7
child 1201	9a51db038228
permissions	-rw-r--r--