Changeset 1205:d3dcc49e6403 in lemon

Timestamp:

02/28/13 17:13:14 (12 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Use output iterator instead of a container (#386)
in tourNodes() functions of TSP algorithms

Files:

• lemon/christofides_tsp.h (modified) (1 diff)
• lemon/greedy_tsp.h (modified) (1 diff)
• lemon/insertion_tsp.h (modified) (1 diff)
• lemon/nearest_neighbor_tsp.h (modified) (1 diff)
• lemon/opt2_tsp.h (modified) (1 diff)
• test/tsp_test.cc (modified) (5 diffs)

lemon/christofides_tsp.h

@@ -210 +210 @@
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
-      ///
-      /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
       

lemon/greedy_tsp.h

@@ -207 +207 @@
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
-      ///
-      /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
 

lemon/insertion_tsp.h

@@ -204 +204 @@
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_tour.begin(), _tour.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_tour.begin(), _tour.end(), out);
       }
 

lemon/nearest_neighbor_tsp.h

@@ -194 +194 @@
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
-      ///
-      /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
+      ///
+      /// \pre run() must be called before using this function.
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
 

lemon/opt2_tsp.h

@@ -231 +231 @@
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
 

test/tsp_test.cc

@@ -62 +62 @@
 
 // Checks tour validity
-bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) {
+template <typename Container>
+bool checkTour(const FullGraph &gr, const Container &p) {
   FullGraph::NodeMap<bool> used(gr, false);
   
-  int nodes = 0;
-  for (int i = 0; i < int(p.size()); ++i) {
-    if (used[p[i]]) return false;
-    used[p[i]] = true;
-    ++nodes;
+  int node_cnt = 0;
+  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
+    FullGraph::Node node = *it;
+    if (used[node]) return false;
+    used[node] = true;
+    ++node_cnt;
   }
   
-  return (nodes == gr.nodeNum());
+  return (node_cnt == gr.nodeNum());
 }
 
 // Checks tour validity
-bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) {
+bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
   FullGraph::NodeMap<bool> used(gr, false);
   
@@ -135 +137 @@
     check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
 
-    std::list<Node> list;
-    std::vector<Node> vec;
-    alg.tourNodes(list);
-    alg.tourNodes(vec);
-    check(list.size() == nsize, alg_name + ": Wrong node sequence");
-    check(vec.size() == nsize,  alg_name + ": Wrong node sequence");
-    check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence");
-    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
-    check(checkCost(g, vec, constMap<Edge, int>(1), esize),
+    std::list<Node> list1(nsize), list2;
+    std::vector<Node> vec1(nsize), vec2;
+    alg.tourNodes(list1.begin());
+    alg.tourNodes(vec1.begin());
+    alg.tourNodes(std::front_inserter(list2));
+    alg.tourNodes(std::back_inserter(vec2));
+    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
+    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
+    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
+    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
       alg_name + ": Wrong tour cost");
 
@@ -149 +154 @@
     alg.tour(path);
     check(path.length() == esize, alg_name + ": Wrong tour");
-    check(checkTour(g, path), alg_name + ": Wrong tour");
+    check(checkTourPath(g, path), alg_name + ": Wrong tour");
     check(checkCost(g, path, constMap<Edge, int>(1), esize),
       alg_name + ": Wrong tour cost");
@@ -181 +186 @@
 
     std::vector<Node> vec;
-    alg.tourNodes(vec);
+    alg.tourNodes(std::back_inserter(vec));
     check(checkTour(g, vec), alg_name + ": Wrong node sequence");
     check(checkCost(g, vec, cost, alg.tourCost()),
@@ -188 +193 @@
     SimplePath<FullGraph> path;
     alg.tour(path);
-    check(checkTour(g, path), alg_name + ": Wrong tour");
+    check(checkTourPath(g, path), alg_name + ": Wrong tour");
     check(checkCost(g, path, cost, alg.tourCost()),
       alg_name + ": Wrong tour cost");