COIN-OR::LEMON - Graph Library

Changeset 1037:d3dcc49e6403 in lemon-main


Ignore:
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:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/christofides_tsp.h

    r1036 r1037  
    210210      ///
    211211      /// This function copies the node sequence of the found tour into
    212       /// the given standard container.
    213       ///
    214       /// \pre run() must be called before using this function.
    215       template <typename Container>
    216       void tourNodes(Container &container) const {
    217         container.assign(_path.begin(), _path.end());
     212      /// an STL container through the given output iterator. The
     213      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
     214      /// For example,
     215      /// \code
     216      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
     217      /// tsp.tourNodes(nodes.begin());
     218      /// \endcode
     219      /// or
     220      /// \code
     221      /// std::list<FullGraph::Node> nodes;
     222      /// tsp.tourNodes(std::back_inserter(nodes));
     223      /// \endcode
     224      ///
     225      /// \pre run() must be called before using this function.
     226      template <typename Iterator>
     227      void tourNodes(Iterator out) const {
     228        std::copy(_path.begin(), _path.end(), out);
    218229      }
    219230     
  • lemon/greedy_tsp.h

    r1036 r1037  
    207207      ///
    208208      /// This function copies the node sequence of the found tour into
    209       /// the given standard container.
    210       ///
    211       /// \pre run() must be called before using this function.
    212       template <typename Container>
    213       void tourNodes(Container &container) const {
    214         container.assign(_path.begin(), _path.end());
     209      /// an STL container through the given output iterator. The
     210      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
     211      /// For example,
     212      /// \code
     213      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
     214      /// tsp.tourNodes(nodes.begin());
     215      /// \endcode
     216      /// or
     217      /// \code
     218      /// std::list<FullGraph::Node> nodes;
     219      /// tsp.tourNodes(std::back_inserter(nodes));
     220      /// \endcode
     221      ///
     222      /// \pre run() must be called before using this function.
     223      template <typename Iterator>
     224      void tourNodes(Iterator out) const {
     225        std::copy(_path.begin(), _path.end(), out);
    215226      }
    216227
  • lemon/insertion_tsp.h

    r1036 r1037  
    204204      ///
    205205      /// This function copies the node sequence of the found tour into
    206       /// the given standard container.
     206      /// an STL container through the given output iterator. The
     207      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
     208      /// For example,
     209      /// \code
     210      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
     211      /// tsp.tourNodes(nodes.begin());
     212      /// \endcode
     213      /// or
     214      /// \code
     215      /// std::list<FullGraph::Node> nodes;
     216      /// tsp.tourNodes(std::back_inserter(nodes));
     217      /// \endcode
    207218      ///
    208219      /// \pre run() must be called before using this function.
    209       template <typename Container>
    210       void tourNodes(Container &container) const {
    211         container.assign(_tour.begin(), _tour.end());
     220      template <typename Iterator>
     221      void tourNodes(Iterator out) const {
     222        std::copy(_tour.begin(), _tour.end(), out);
    212223      }
    213224
  • lemon/nearest_neighbor_tsp.h

    r1036 r1037  
    194194      ///
    195195      /// This function copies the node sequence of the found tour into
    196       /// the given standard container.
    197       ///
    198       /// \pre run() must be called before using this function.
    199       template <typename Container>
    200       void tourNodes(Container &container) const {
    201         container.assign(_path.begin(), _path.end());
     196      /// an STL container through the given output iterator. The
     197      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
     198      /// For example,
     199      /// \code
     200      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
     201      /// tsp.tourNodes(nodes.begin());
     202      /// \endcode
     203      /// or
     204      /// \code
     205      /// std::list<FullGraph::Node> nodes;
     206      /// tsp.tourNodes(std::back_inserter(nodes));
     207      /// \endcode
     208      ///
     209      /// \pre run() must be called before using this function.
     210      template <typename Iterator>
     211      void tourNodes(Iterator out) const {
     212        std::copy(_path.begin(), _path.end(), out);
    202213      }
    203214
  • lemon/opt2_tsp.h

    r1036 r1037  
    231231      ///
    232232      /// This function copies the node sequence of the found tour into
    233       /// the given standard container.
     233      /// an STL container through the given output iterator. The
     234      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
     235      /// For example,
     236      /// \code
     237      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
     238      /// tsp.tourNodes(nodes.begin());
     239      /// \endcode
     240      /// or
     241      /// \code
     242      /// std::list<FullGraph::Node> nodes;
     243      /// tsp.tourNodes(std::back_inserter(nodes));
     244      /// \endcode
    234245      ///
    235246      /// \pre run() must be called before using this function.
    236       template <typename Container>
    237       void tourNodes(Container &container) const {
    238         container.assign(_path.begin(), _path.end());
     247      template <typename Iterator>
     248      void tourNodes(Iterator out) const {
     249        std::copy(_path.begin(), _path.end(), out);
    239250      }
    240251
  • test/tsp_test.cc

    r1035 r1037  
    6262
    6363// Checks tour validity
    64 bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) {
     64template <typename Container>
     65bool checkTour(const FullGraph &gr, const Container &p) {
    6566  FullGraph::NodeMap<bool> used(gr, false);
    6667 
    67   int nodes = 0;
    68   for (int i = 0; i < int(p.size()); ++i) {
    69     if (used[p[i]]) return false;
    70     used[p[i]] = true;
    71     ++nodes;
     68  int node_cnt = 0;
     69  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
     70    FullGraph::Node node = *it;
     71    if (used[node]) return false;
     72    used[node] = true;
     73    ++node_cnt;
    7274  }
    7375 
    74   return (nodes == gr.nodeNum());
     76  return (node_cnt == gr.nodeNum());
    7577}
    7678
    7779// Checks tour validity
    78 bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) {
     80bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
    7981  FullGraph::NodeMap<bool> used(gr, false);
    8082 
     
    135137    check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
    136138
    137     std::list<Node> list;
    138     std::vector<Node> vec;
    139     alg.tourNodes(list);
    140     alg.tourNodes(vec);
    141     check(list.size() == nsize, alg_name + ": Wrong node sequence");
    142     check(vec.size() == nsize,  alg_name + ": Wrong node sequence");
    143     check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence");
    144     check(checkTour(g, vec), alg_name + ": Wrong node sequence");
    145     check(checkCost(g, vec, constMap<Edge, int>(1), esize),
     139    std::list<Node> list1(nsize), list2;
     140    std::vector<Node> vec1(nsize), vec2;
     141    alg.tourNodes(list1.begin());
     142    alg.tourNodes(vec1.begin());
     143    alg.tourNodes(std::front_inserter(list2));
     144    alg.tourNodes(std::back_inserter(vec2));
     145    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
     146    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
     147    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
     148    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
     149    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
     150    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
    146151      alg_name + ": Wrong tour cost");
    147152
     
    149154    alg.tour(path);
    150155    check(path.length() == esize, alg_name + ": Wrong tour");
    151     check(checkTour(g, path), alg_name + ": Wrong tour");
     156    check(checkTourPath(g, path), alg_name + ": Wrong tour");
    152157    check(checkCost(g, path, constMap<Edge, int>(1), esize),
    153158      alg_name + ": Wrong tour cost");
     
    181186
    182187    std::vector<Node> vec;
    183     alg.tourNodes(vec);
     188    alg.tourNodes(std::back_inserter(vec));
    184189    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
    185190    check(checkCost(g, vec, cost, alg.tourCost()),
     
    188193    SimplePath<FullGraph> path;
    189194    alg.tour(path);
    190     check(checkTour(g, path), alg_name + ": Wrong tour");
     195    check(checkTourPath(g, path), alg_name + ": Wrong tour");
    191196    check(checkCost(g, path, cost, alg.tourCost()),
    192197      alg_name + ": Wrong tour cost");
Note: See TracChangeset for help on using the changeset viewer.