COIN-OR::LEMON - Graph Library

Changeset 824:157115b5814a in lemon-0.x for src


Ignore:
Timestamp:
09/09/04 09:09:11 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1120
Message:

Shorter template parameter names to be more readable in Doxygen.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/kruskal.h

    r812 r824  
    2222///Kruskal's algorithm to compute a minimum cost tree.
    2323
     24///\weakgroup spantree
    2425namespace hugo {
    2526
     
    3536  /// \param in This object is used to describe the edge costs. It must
    3637  /// be an STL compatible 'Forward Container'
    37   /// with <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,
     38  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
    3839  /// where X is the type of the costs. It must contain every edge in
    3940  /// cost-ascending order.
     
    5354  /// \return The cost of the found tree.
    5455
    55   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
    56   typename InputEdgeOrder::value_type::second_type
    57   kruskal(Graph const& G, InputEdgeOrder const& in,
    58                  OutBoolMap& out)
     56  template <class GR, class IN, class OUT>
     57  typename IN::value_type::second_type
     58  kruskal(GR const& G, IN const& in,
     59                 OUT& out)
    5960  {
    60     typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
    61     typedef typename Graph::template NodeMap<int> NodeIntMap;
    62     typedef typename Graph::Node Node;
     61    typedef typename IN::value_type::second_type EdgeCost;
     62    typedef typename GR::template NodeMap<int> NodeIntMap;
     63    typedef typename GR::Node Node;
    6364
    6465    NodeIntMap comp(G, -1);
     
    6667     
    6768    EdgeCost tot_cost = 0;
    68     for (typename InputEdgeOrder::const_iterator p = in.begin();
     69    for (typename IN::const_iterator p = in.begin();
    6970         p!=in.end(); ++p ) {
    7071      if ( uf.join(G.head((*p).first),
     
    8485  ///\bug What is this? Or why doesn't it work?
    8586  ///
    86   template<typename Map>
     87  template<class Map>
    8788  class NonConstMapWr {
    8889    const Map &m;
     
    9293    NonConstMapWr(const Map &_m) : m(_m) {}
    9394
    94     template<typename KeyType>
     95    template<class KeyType>
    9596    void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
    9697  };
    9798
    98   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
    99   inline
    100   typename InputEdgeOrder::ValueType
    101   kruskal(Graph const& G, InputEdgeOrder const& edges,
    102           OutBoolMap const& out_map)
     99  template <class GR, class IN, class OUT>
     100  inline
     101  typename IN::ValueType
     102  kruskal(GR const& G, IN const& edges,
     103          OUT const& out_map)
    103104  {
    104     NonConstMapWr<OutBoolMap> map_wr(out_map);
     105    NonConstMapWr<OUT> map_wr(out_map);
    105106    return kruskal(G, edges, map_wr);
    106107  } 
     
    116117  /// \sa makeKruskalMapInput()
    117118  ///
    118   ///\param Graph The type of the graph the algorithm runs on.
     119  ///\param GR The type of the graph the algorithm runs on.
    119120  ///\param Map An edge map containing the cost of the edges.
    120121  ///\par
     
    124125  ///computing the total cost of the tree).
    125126  ///
    126   template<typename Graph, typename Map>
     127  template<class GR, class Map>
    127128  class KruskalMapInput
    128     : public std::vector< std::pair<typename Graph::Edge,
     129    : public std::vector< std::pair<typename GR::Edge,
    129130                                    typename Map::ValueType> > {
    130131   
    131132  public:
    132     typedef std::vector< std::pair<typename Graph::Edge,
     133    typedef std::vector< std::pair<typename GR::Edge,
    133134                                   typename Map::ValueType> > Parent;
    134135    typedef typename Parent::value_type value_type;
     
    149150    }
    150151
    151     KruskalMapInput(Graph const& G, Map const& m) {
    152       typedef typename Graph::EdgeIt EdgeIt;
     152    KruskalMapInput(GR const& G, Map const& m) {
     153      typedef typename GR::EdgeIt EdgeIt;
    153154     
    154155      this->clear();
     
    177178  ///\return An appropriate input source for \ref kruskal().
    178179  ///
    179   template<typename Graph, typename Map>
    180   inline
    181   KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)
     180  template<class GR, class Map>
     181  inline
     182  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
    182183  {
    183     return KruskalMapInput<Graph,Map>(G,m);
     184    return KruskalMapInput<GR,Map>(G,m);
    184185  }
    185186 
     
    195196  /// \todo This class may be of wider usage, therefore it could move to
    196197  /// <tt>maps.h</tt>
    197   template<typename Iterator>
     198  template<class Iterator>
    198199  class SequenceOutput {
    199200    mutable Iterator it;
     
    208209  };
    209210
    210   template<typename Iterator>
     211  template<class Iterator>
    211212  inline
    212213  SequenceOutput<Iterator>
     
    241242
    242243
    243   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
    244   inline
    245   typename EdgeCostMap::ValueType
    246   kruskalEdgeMap(Graph const& G,
    247                  EdgeCostMap const& in,
    248                  RetEdgeBoolMap &out) {
     244  template <class GR, class IN, class RET>
     245  inline
     246  typename IN::ValueType
     247  kruskalEdgeMap(GR const& G,
     248                 IN const& in,
     249                 RET &out) {
    249250    return kruskal(G,
    250                    KruskalMapInput<Graph,EdgeCostMap>(G,in),
     251                   KruskalMapInput<GR,IN>(G,in),
    251252                   out);
    252253  }
     
    267268  ///
    268269  /// \retval out This must be an iteraror of an STL Container with
    269   /// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.
     270  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
    270271  /// The algorithm copies the elements of the found tree into this sequence.
    271272  /// For example, if we know that the spanning tree of the graph \c G has
    272273  /// say 53 edges then
    273   /// we can put its edges into a vector \c tree with a code like this.
     274  /// we can put its edges into a STL vector \c tree with a code like this.
    274275  /// \code
    275276  /// std::vector<Edge> tree(53);
     
    285286  ///
    286287  /// \bug its name does not follow the coding style.
    287   template <typename Graph, typename EdgeCostMap, typename RetIterator>
    288   inline
    289   typename EdgeCostMap::ValueType
    290   kruskalEdgeMap_IteratorOut(const Graph& G,
    291                              const EdgeCostMap& in,
    292                              RetIterator out)
     288  template <class GR, class IN, class RET>
     289  inline
     290  typename IN::ValueType
     291  kruskalEdgeMap_IteratorOut(const GR& G,
     292                             const IN& in,
     293                             RET out)
    293294  {
    294     SequenceOutput<RetIterator> _out(out);
     295    SequenceOutput<RET> _out(out);
    295296    return kruskal(G,
    296                    KruskalMapInput<Graph, EdgeCostMap>(G, in),
     297                   KruskalMapInput<GR,IN>(G, in),
    297298                   _out);
    298299  }
Note: See TracChangeset for help on using the changeset viewer.