COIN-OR::LEMON - Graph Library

Changeset 1557:3e8d928e283d in lemon-0.x


Ignore:
Timestamp:
07/14/05 14:23:15 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2053
Message:

Each version of Kruskal is called the same ( kruskal(g,in,out) ) independently
from the input source and the output type.

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/kruskal.h

    r1555 r1557  
    3737///
    3838///Kruskal's algorithm to compute a minimum cost tree.
     39///
     40///\todo The file still needs some clean-up.
    3941
    4042namespace lemon {
     
    4648
    4749  /// This function runs Kruskal's algorithm to find a minimum cost tree.
     50  /// Due to hard C++ hacking, it accepts various input and output types.
     51  ///
    4852  /// \param g The graph the algorithm runs on.
    4953  /// It can be either \ref concept::StaticGraph "directed" or
     
    5256  /// undirected by disregarding the direction of the edges.
    5357  ///
    54   /// \param in This object is used to describe the edge costs. It must
    55   /// be an STL compatible 'Forward Container'
     58  /// \param in This object is used to describe the edge costs. It can be one
     59  /// of the following choices.
     60  /// - An STL compatible 'Forward Container'
    5661  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
    57   /// where X is the type of the costs. It must contain every edge in
    58   /// cost-ascending order.
    59   ///\par
    60   /// For the sake of simplicity, there is a helper class KruskalMapInput,
    61   /// which converts a
    62   /// simple edge map to an input of this form. Alternatively, you can use
    63   /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
    64   /// the edge costs are given by an edge map.
    65   ///
    66   /// \retval out This must be a writable \c bool edge map.
     62  /// where \c X is the type of the costs. The pairs indicates the edges along
     63  /// with the assigned cost. <em>They must be in a
     64  /// cost-ascending order.</em>
     65  /// - Any readable Edge map. The values of the map indicate the edge costs.
     66  ///
     67  /// \retval out Here we also have a choise.
     68  /// - Is can be a writable \c bool edge map.
    6769  /// After running the algorithm
    6870  /// this will contain the found minimum cost spanning tree: the value of an
    6971  /// edge will be set to \c true if it belongs to the tree, otherwise it will
    7072  /// be set to \c false. The value of each edge will be set exactly once.
     73  /// - It can also be an iteraror of an STL Container with
     74  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
     75  /// The algorithm copies the elements of the found tree into this sequence.
     76  /// For example, if we know that the spanning tree of the graph \c g has
     77  /// say 53 edges then
     78  /// we can put its edges into a STL vector \c tree with a code like this.
     79  /// \code
     80  /// std::vector<Edge> tree(53);
     81  /// kruskal(g,cost,tree.begin());
     82  /// \endcode
     83  /// Or if we don't know in advance the size of the tree, we can write this.
     84  /// \code
     85  /// std::vector<Edge> tree;
     86  /// kruskal(g,cost,std::back_inserter(tree));
     87  /// \endcode
    7188  ///
    7289  /// \return The cost of the found tree.
     
    7895  /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
    7996
     97#ifdef DOXYGEN
    8098  template <class GR, class IN, class OUT>
    8199  typename IN::value_type::second_type
    82100  kruskal(GR const& g, IN const& in,
    83                  OUT& out)
     101          OUT& out)
     102#else
     103  template <class GR, class IN, class OUT>
     104  typename IN::value_type::second_type
     105  kruskal(GR const& g, IN const& in,
     106          OUT& out,
     107//        typename IN::value_type::first_type = typename GR::Edge()
     108//        ,typename OUT::Key = OUT::Key()
     109//        //,typename OUT::Key = typename GR::Edge()
     110          const typename IN::value_type::first_type * =
     111          (const typename IN::value_type::first_type *)(0),
     112          const typename OUT::Key * = (const typename OUT::Key *)(0)
     113          )
     114#endif
    84115  {
    85116    typedef typename IN::value_type::second_type EdgeCost;
     
    105136  }
    106137
     138 
     139  /// @}
     140
     141 
    107142  /* A work-around for running Kruskal with const-reference bool maps... */
    108143
     
    123158    const Map &m;
    124159  public:
     160    typedef typename Map::Key Key;
    125161    typedef typename Map::Value Value;
    126162
     
    134170  inline
    135171  typename IN::value_type::second_type
    136   kruskal(GR const& g, IN const& edges, OUT const& out_map)
     172  kruskal(GR const& g, IN const& edges, OUT const& out_map,
     173//        typename IN::value_type::first_type = typename GR::Edge(),
     174//        typename OUT::Key = GR::Edge()
     175          const typename IN::value_type::first_type * =
     176          (const typename IN::value_type::first_type *)(0),
     177          const typename OUT::Key * = (const typename OUT::Key *)(0)
     178          )
    137179  {
    138180    NonConstMapWr<OUT> map_wr(out_map);
     
    143185
    144186  /// Kruskal's input source.
    145 
     187 
    146188  /// Kruskal's input source.
    147189  ///
     
    268310
    269311  public:
     312    typedef typename Iterator::value_type Key;
    270313    typedef bool Value;
    271314
     
    287330  /* ** ** Wrapper funtions ** ** */
    288331
    289 
    290 
    291   /// \brief Wrapper function to kruskal().
    292   /// Input is from an edge map, output is a plain bool map.
    293   ///
    294   /// Wrapper function to kruskal().
    295   /// Input is from an edge map, output is a plain bool map.
    296   ///
    297   ///\param g The type of the graph the algorithm runs on.
    298   ///\param in An edge map containing the cost of the edges.
    299   ///\par
    300   ///The cost type can be any type satisfying the
    301   ///STL 'LessThan Comparable'
    302   ///concept if it also has an operator+() implemented. (It is necessary for
    303   ///computing the total cost of the tree).
    304   ///
    305   /// \retval out This must be a writable \c bool edge map.
    306   /// After running the algorithm
    307   /// this will contain the found minimum cost spanning tree: the value of an
    308   /// edge will be set to \c true if it belongs to the tree, otherwise it will
    309   /// be set to \c false. The value of each edge will be set exactly once.
    310   ///
    311   /// \return The cost of the found tree.
     332//   \brief Wrapper function to kruskal().
     333//   Input is from an edge map, output is a plain bool map.
     334// 
     335//   Wrapper function to kruskal().
     336//   Input is from an edge map, output is a plain bool map.
     337// 
     338//   \param g The type of the graph the algorithm runs on.
     339//   \param in An edge map containing the cost of the edges.
     340//   \par
     341//   The cost type can be any type satisfying the
     342//   STL 'LessThan Comparable'
     343//   concept if it also has an operator+() implemented. (It is necessary for
     344//   computing the total cost of the tree).
     345// 
     346//   \retval out This must be a writable \c bool edge map.
     347//   After running the algorithm
     348//   this will contain the found minimum cost spanning tree: the value of an
     349//   edge will be set to \c true if it belongs to the tree, otherwise it will
     350//   be set to \c false. The value of each edge will be set exactly once.
     351// 
     352//   \return The cost of the found tree.
    312353
    313354  template <class GR, class IN, class RET>
    314355  inline
    315356  typename IN::Value
    316   kruskalEdgeMap(GR const& g,
    317                  IN const& in,
    318                  RET &out) {
     357  kruskal(GR const& g,
     358          IN const& in,
     359          RET &out,
     360          //      typename IN::Key = typename GR::Edge(),
     361          //typename IN::Key = typename IN::Key (),
     362          //      typename RET::Key = typename GR::Edge()
     363          const typename IN::Key *  = (const typename IN::Key *)(0),
     364          const typename RET::Key * = (const typename RET::Key *)(0)
     365          )
     366  {
    319367    return kruskal(g,
    320368                   KruskalMapInput<GR,IN>(g,in),
     
    322370  }
    323371
    324   /// \brief Wrapper function to kruskal().
    325   /// Input is from an edge map, output is an STL Sequence.
    326   ///
    327   /// Wrapper function to kruskal().
    328   /// Input is from an edge map, output is an STL Sequence.
    329   ///
    330   ///\param g The type of the graph the algorithm runs on.
    331   ///\param in An edge map containing the cost of the edges.
    332   ///\par
    333   ///The cost type can be any type satisfying the
    334   ///STL 'LessThan Comparable'
    335   ///concept if it also has an operator+() implemented. (It is necessary for
    336   ///computing the total cost of the tree).
    337   ///
    338   /// \retval out This must be an iteraror of an STL Container with
    339   /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
    340   /// The algorithm copies the elements of the found tree into this sequence.
    341   /// For example, if we know that the spanning tree of the graph \c g has
    342   /// say 53 edges then
    343   /// we can put its edges into a STL vector \c tree with a code like this.
    344   /// \code
    345   /// std::vector<Edge> tree(53);
    346   /// kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
    347   /// \endcode
    348   /// Or if we don't know in advance the size of the tree, we can write this.
    349   /// \code
    350   /// std::vector<Edge> tree;
    351   /// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
    352   /// \endcode
    353   ///
    354   /// \return The cost of the found tree.
    355   ///
    356   /// \bug its name does not follow the coding style.
     372//  \brief Wrapper function to kruskal().
     373//  Input is from an edge map, output is an STL Sequence.
     374// 
     375//  Wrapper function to kruskal().
     376//  Input is from an edge map, output is an STL Sequence.
     377// 
     378//   \param g The type of the graph the algorithm runs on.
     379//   \param in An edge map containing the cost of the edges.
     380//   \par
     381//   The cost type can be any type satisfying the
     382//   STL 'LessThan Comparable'
     383//   concept if it also has an operator+() implemented. (It is necessary for
     384//   computing the total cost of the tree).
     385// 
     386//  \retval out This must be an iteraror of an STL Container with
     387//  <tt>GR::Edge</tt> as its <tt>value_type</tt>.
     388//  The algorithm copies the elements of the found tree into this sequence.
     389//  For example, if we know that the spanning tree of the graph \c g has
     390//  say 53 edges then
     391//  we can put its edges into a STL vector \c tree with a code like this.
     392//  \code
     393//  std::vector<Edge> tree(53);
     394//  kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
     395//  \endcode
     396//  Or if we don't know in advance the size of the tree, we can write this.
     397//  \code
     398//  std::vector<Edge> tree;
     399//  kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
     400//  \endcode
     401// 
     402//  \return The cost of the found tree.
     403// 
     404//  \bug its name does not follow the coding style.
    357405
    358406  template <class GR, class IN, class RET>
    359407  inline
    360408  typename IN::Value
    361   kruskalEdgeMap_IteratorOut(const GR& g,
    362                              const IN& in,
    363                              RET out)
     409  kruskal(const GR& g,
     410          const IN& in,
     411          RET out,
     412          //,typename RET::value_type = typename GR::Edge()
     413          //,typename RET::value_type = typename RET::value_type()
     414          const typename RET::value_type * =
     415          (const typename RET::value_type *)(0)
     416          )
    364417  {
    365418    KruskalSequenceOutput<RET> _out(out);
    366419    return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
    367420  }
    368 
     421 
    369422  /// @}
    370423
  • test/kruskal_test.cc

    r1435 r1557  
    3333  concept::WriteMap<concept::StaticGraph::Edge,bool> w;
    3434
    35   kruskalEdgeMap(concept::StaticGraph(),
    36                 concept::ReadMap<concept::StaticGraph::Edge,int>(),
    37                 w);
     35  kruskal(concept::StaticGraph(),
     36          concept::ReadMap<concept::StaticGraph::Edge,int>(),
     37          w);
    3838}
    3939
     
    7373
    7474  //Test with const map.
    75   check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
     75  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    7676        "Total cost should be 10");
    7777  //Test with a edge map (filled with uniform costs).
    78   check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
     78  check(kruskal(G, edge_cost_map, tree_map)==10,
    7979        "Total cost should be 10");
    8080
     
    9090  edge_cost_map.set(e10, -1);
    9191
    92   vector<Edge> tree_edge_vec;
     92  vector<Edge> tree_edge_vec(5);
    9393
    9494  //Test with a edge map and inserter.
    95   check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
    96                                    back_inserter(tree_edge_vec))
     95  check(kruskal(G, edge_cost_map,
     96                 tree_edge_vec.begin())
    9797        ==-31,
    9898        "Total cost should be -31.");
    99 
     99 
    100100  tree_edge_vec.clear();
    101101
     102  check(kruskal(G, edge_cost_map,
     103                back_inserter(tree_edge_vec))
     104        ==-31,
     105        "Total cost should be -31.");
     106 
     107  tree_edge_vec.clear();
     108 
    102109  //The above test could also be coded like this:
    103110  check(kruskal(G,
Note: See TracChangeset for help on using the changeset viewer.