COIN-OR::LEMON - Graph Library

Changeset 885:5e59c44b6ba2 in lemon-0.x


Ignore:
Timestamp:
09/19/04 17:24:56 (20 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1193
Message:

Kruskal cleanup:

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/kruskal.h

    r881 r885  
    8282  /* A work-around for running Kruskal with const-reference bool maps... */
    8383
    84   ///\bug What is this? Or why doesn't it work?
    85   ///
     84  /// Helper class for calling kruskal with "constant" output map.
     85
     86  /// Helper class for calling kruskal with output maps constructed
     87  /// on-the-fly.
     88  ///
     89  /// A typical examle is the following call:
     90  /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
     91  /// Here, the third argument is a temporary object (which wraps around an
     92  /// iterator with a writable bool map interface), and thus by rules of C++
     93  /// is a \c const object. To enable call like this exist this class and
     94  /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
     95  /// third argument.
    8696  template<class Map>
    8797  class NonConstMapWr {
     
    98108  template <class GR, class IN, class OUT>
    99109  inline
    100   typename IN::ValueType
    101   kruskal(GR const& G, IN const& edges,
    102           OUT const& out_map)
     110  typename IN::value_type::second_type
     111  kruskal(GR const& G, IN const& edges, OUT const& out_map)
    103112  {
    104113    NonConstMapWr<OUT> map_wr(out_map);
     
    152161      typedef typename GR::EdgeIt EdgeIt;
    153162     
    154       this->clear();
    155       for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
     163      for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
    156164      sort();
    157165    }
     
    185193 
    186194 
    187   /* ** ** Output-objects: simple writable bool maps** ** */
     195
     196  /* ** ** Output-objects: simple writable bool maps ** ** */
    188197 
     198
     199
    189200  /// A writable bool-map that makes a sequence of "true" keys
    190201
    191202  /// A writable bool-map that creates a sequence out of keys that receives
    192203  /// the value "true".
     204  ///
     205  /// \sa makeKruskalSequenceOutput()
     206  ///
     207  /// Very often, when looking for a min cost spanning tree, we want as
     208  /// output a container containing the edges of the found tree. For this
     209  /// purpose exist this class that wraps around an STL iterator with a
     210  /// writable bool map interface. When a key gets value "true" this key
     211  /// is added to sequence pointed by the iterator.
     212  ///
     213  /// A typical usage:
     214  /// \code
     215  /// std::vector<Graph::Edge> v;
     216  /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
     217  /// \endcode
     218  ///
     219  /// For the most common case, when the input is given by a simple edge
     220  /// map and the output is a sequence of the tree edges, a special
     221  /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
     222  ///
    193223  /// \warning Not a regular property map, as it doesn't know its KeyType
    194   /// \bug Missing documentation.
    195   /// \todo This class may be of wider usage, therefore it could move to
    196   /// <tt>maps.h</tt>
     224
    197225  template<class Iterator>
    198   class SequenceOutput {
     226  class KruskalSequenceOutput {
    199227    mutable Iterator it;
    200228
     
    202230    typedef bool ValueType;
    203231
    204     SequenceOutput(Iterator const &_it) : it(_it) {}
     232    KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
    205233
    206234    template<typename KeyType>
     
    210238  template<class Iterator>
    211239  inline
    212   SequenceOutput<Iterator>
    213   makeSequenceOutput(Iterator it) {
    214     return SequenceOutput<Iterator>(it);
    215   }
     240  KruskalSequenceOutput<Iterator>
     241  makeKruskalSequenceOutput(Iterator it) {
     242    return KruskalSequenceOutput<Iterator>(it);
     243  }
     244
     245
    216246
    217247  /* ** ** Wrapper funtions ** ** */
     248
    218249
    219250
     
    239270  ///
    240271  /// \return The cost of the found tree.
    241 
    242272
    243273  template <class GR, class IN, class RET>
     
    285315  ///
    286316  /// \bug its name does not follow the coding style.
     317
    287318  template <class GR, class IN, class RET>
    288319  inline
     
    292323                             RET out)
    293324  {
    294     SequenceOutput<RET> _out(out);
    295     return kruskal(G,
    296                    KruskalMapInput<GR,IN>(G, in),
    297                    _out);
     325    KruskalSequenceOutput<RET> _out(out);
     326    return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
    298327  }
    299328
  • src/test/kruskal_test.cc

    r880 r885  
    8282        "Total cost should be -31.");
    8383
     84  tree_edge_vec.clear();
     85
     86  //The above test could also be coded like this:
     87  check(kruskal(G,
     88                makeKruskalMapInput(G, edge_cost_map),
     89                makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
     90        ==-31,
     91        "Total cost should be -31.");
     92
    8493  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
    8594
Note: See TracChangeset for help on using the changeset viewer.