# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1362067994 -3600
# Node ID d3dcc49e64033041370e77c0c7488499bbf7241f
# Parent dff32ce3db712f2d6e262e75fae4d9404798afa8
Use output iterator instead of a container (#386)
in tourNodes() functions of TSP algorithms
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/christofides_tsp.h
--- a/lemon/christofides_tsp.h Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/christofides_tsp.h Thu Feb 28 17:13:14 2013 +0100
@@ -209,12 +209,23 @@
/// \brief Gives back the node sequence of the found tour.
///
/// 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);
}
/// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/greedy_tsp.h
--- a/lemon/greedy_tsp.h Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/greedy_tsp.h Thu Feb 28 17:13:14 2013 +0100
@@ -206,12 +206,23 @@
/// \brief Gives back the node sequence of the found tour.
///
/// 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);
}
/// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/insertion_tsp.h
--- a/lemon/insertion_tsp.h Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/insertion_tsp.h Thu Feb 28 17:13:14 2013 +0100
@@ -203,12 +203,23 @@
/// \brief Gives back the node sequence of the found tour.
///
/// 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);
}
/// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/nearest_neighbor_tsp.h
--- a/lemon/nearest_neighbor_tsp.h Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/nearest_neighbor_tsp.h Thu Feb 28 17:13:14 2013 +0100
@@ -193,12 +193,23 @@
/// \brief Gives back the node sequence of the found tour.
///
/// 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);
}
/// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/opt2_tsp.h
--- a/lemon/opt2_tsp.h Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/opt2_tsp.h Thu Feb 28 17:13:14 2013 +0100
@@ -230,12 +230,23 @@
/// \brief Gives back the node sequence of the found tour.
///
/// 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);
}
/// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 test/tsp_test.cc
--- a/test/tsp_test.cc Sun Jan 09 15:06:55 2011 +0100
+++ b/test/tsp_test.cc Thu Feb 28 17:13:14 2013 +0100
@@ -61,21 +61,23 @@
// }
// 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);
if (!checkPath(gr, p)) return false;
@@ -134,21 +136,24 @@
check(alg.run() == esize, alg_name + ": Wrong total cost");
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");
SimplePath<FullGraph> path;
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");
}
@@ -180,14 +185,14 @@
check(alg.run() > 0, alg_name + ": Wrong total cost");
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()),
alg_name + ": Wrong tour cost");
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");