COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon for lemon/kruskal.h


Ignore:
Timestamp:
07/13/08 20:51:02 (12 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/kruskal.h

    r194 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    4646    template <typename Digraph, typename In, typename Out>
    4747    typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
    48                        typename In::value_type::second_type >::type
     48                       typename In::value_type::second_type >::type
    4949    kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {
    5050      typedef typename In::value_type::second_type Value;
    5151      typedef typename Digraph::template NodeMap<int> IndexMap;
    5252      typedef typename Digraph::Node Node;
    53      
     53
    5454      IndexMap index(digraph);
    5555      UnionFind<IndexMap> uf(index);
     
    5757        uf.insert(it);
    5858      }
    59      
     59
    6060      Value tree_value = 0;
    6161      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
     
    7575    template <typename Graph, typename In, typename Out>
    7676    typename enable_if<lemon::UndirectedTagIndicator<Graph>,
    77                        typename In::value_type::second_type >::type
     77                       typename In::value_type::second_type >::type
    7878    kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) {
    7979      typedef typename In::value_type::second_type Value;
    8080      typedef typename Graph::template NodeMap<int> IndexMap;
    8181      typedef typename Graph::Node Node;
    82      
     82
    8383      IndexMap index(graph);
    8484      UnionFind<IndexMap> uf(index);
     
    8686        uf.insert(it);
    8787      }
    88      
     88
    8989      Value tree_value = 0;
    9090      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
     
    105105      typedef typename Sequence::value_type Value;
    106106      bool operator()(const Value& left, const Value& right) {
    107         return left.second < right.second;
     107        return left.second < right.second;
    108108      }
    109109    };
     
    115115
    116116    template <typename In>
    117     struct SequenceInputIndicator<In, 
     117    struct SequenceInputIndicator<In,
    118118      typename exists<typename In::value_type::first_type>::type> {
    119119      static const bool value = true;
     
    126126
    127127    template <typename In>
    128     struct MapInputIndicator<In, 
     128    struct MapInputIndicator<In,
    129129      typename exists<typename In::Value>::type> {
    130130      static const bool value = true;
     
    135135      static const bool value = false;
    136136    };
    137  
     137
    138138    template <typename Out>
    139     struct SequenceOutputIndicator<Out, 
     139    struct SequenceOutputIndicator<Out,
    140140      typename exists<typename Out::value_type>::type> {
    141141      static const bool value = true;
     
    148148
    149149    template <typename Out>
    150     struct MapOutputIndicator<Out, 
     150    struct MapOutputIndicator<Out,
    151151      typename exists<typename Out::Value>::type> {
    152152      static const bool value = true;
     
    158158    template <typename In>
    159159    struct KruskalValueSelector<In,
    160       typename enable_if<SequenceInputIndicator<In>, void>::type> 
    161     {
    162       typedef typename In::value_type::second_type Value;
    163     };   
     160      typename enable_if<SequenceInputIndicator<In>, void>::type>
     161    {
     162      typedef typename In::value_type::second_type Value;
     163    };
    164164
    165165    template <typename In>
    166166    struct KruskalValueSelector<In,
    167       typename enable_if<MapInputIndicator<In>, void>::type> 
     167      typename enable_if<MapInputIndicator<In>, void>::type>
    168168    {
    169169      typedef typename In::Value Value;
    170     };   
    171    
     170    };
     171
    172172    template <typename Graph, typename In, typename Out,
    173173              typename InEnable = void>
     
    177177              typename InEnable = void>
    178178    struct KruskalOutputSelector {};
    179    
     179
    180180    template <typename Graph, typename In, typename Out>
    181181    struct KruskalInputSelector<Graph, In, Out,
    182       typename enable_if<SequenceInputIndicator<In>, void>::type > 
     182      typename enable_if<SequenceInputIndicator<In>, void>::type >
    183183    {
    184184      typedef typename In::value_type::second_type Value;
     
    193193    template <typename Graph, typename In, typename Out>
    194194    struct KruskalInputSelector<Graph, In, Out,
    195       typename enable_if<MapInputIndicator<In>, void>::type > 
     195      typename enable_if<MapInputIndicator<In>, void>::type >
    196196    {
    197197      typedef typename In::Value Value;
     
    202202        typedef std::vector<std::pair<MapArc, Value> > Sequence;
    203203        Sequence seq;
    204        
     204
    205205        for (MapArcIt it(graph); it != INVALID; ++it) {
    206206          seq.push_back(std::make_pair(it, in[it]));
     
    225225    template <typename Graph, typename In, typename Out>
    226226    struct KruskalOutputSelector<Graph, In, Out,
    227       typename enable_if<SequenceOutputIndicator<Out>, void>::type > 
     227      typename enable_if<SequenceOutputIndicator<Out>, void>::type >
    228228    {
    229229      typedef typename In::value_type::second_type Value;
     
    239239    template <typename Graph, typename In, typename Out>
    240240    struct KruskalOutputSelector<Graph, In, Out,
    241       typename enable_if<MapOutputIndicator<Out>, void>::type > 
     241      typename enable_if<MapOutputIndicator<Out>, void>::type >
    242242    {
    243243      typedef typename In::value_type::second_type Value;
     
    255255  /// a graph.
    256256  ///
    257   /// This function runs Kruskal's algorithm to find a minimum cost 
     257  /// This function runs Kruskal's algorithm to find a minimum cost
    258258  /// spanning tree.
    259259  /// Due to some C++ hacking, it accepts various input and output types.
    260260  ///
    261261  /// \param g The graph the algorithm runs on.
    262   /// It can be either \ref concepts::Digraph "directed" or 
     262  /// It can be either \ref concepts::Digraph "directed" or
    263263  /// \ref concepts::Graph "undirected".
    264   /// If the graph is directed, the algorithm consider it to be 
     264  /// If the graph is directed, the algorithm consider it to be
    265265  /// undirected by disregarding the direction of the arcs.
    266266  ///
    267   /// \param in This object is used to describe the arc/edge costs. 
     267  /// \param in This object is used to describe the arc/edge costs.
    268268  /// It can be one of the following choices.
    269269  /// - An STL compatible 'Forward Container' with
     
    273273  /// along with the assigned cost. <em>They must be in a
    274274  /// cost-ascending order.</em>
    275   /// - Any readable arc/edge map. The values of the map indicate the 
     275  /// - Any readable arc/edge map. The values of the map indicate the
    276276  /// arc/edge costs.
    277277  ///
     
    293293  ///\endcode
    294294  /// Or if we don't know in advance the size of the tree, we can
    295   /// write this. 
     295  /// write this.
    296296  ///\code
    297297  /// std::vector<Arc> tree;
    298   /// kruskal(g,cost,std::back_inserter(tree)); 
     298  /// kruskal(g,cost,std::back_inserter(tree));
    299299  ///\endcode
    300300  ///
     
    308308  template <class Graph, class In, class Out>
    309309  Value kruskal(GR const& g, const In& in, Out& out)
    310 #else 
     310#else
    311311  template <class Graph, class In, class Out>
    312   inline typename _kruskal_bits::KruskalValueSelector<In>::Value 
    313   kruskal(const Graph& graph, const In& in, Out& out) 
     312  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
     313  kruskal(const Graph& graph, const In& in, Out& out)
    314314#endif
    315315  {
     
    318318  }
    319319
    320  
    321  
     320
     321
    322322
    323323  template <class Graph, class In, class Out>
     
    327327    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
    328328      kruskal(graph, in, out);
    329   } 
     329  }
    330330
    331331} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.