COIN-OR::LEMON - Graph Library

Changeset 2424:95cd24940d00 in lemon-0.x for lemon/kruskal.h


Ignore:
Timestamp:
04/19/07 17:11:58 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3260
Message:

Redesigned Kruskal algorithm

The interface of function type implementation is not changed
Additional class type implementation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/kruskal.h

    r2391 r2424  
    2323#include <vector>
    2424#include <lemon/unionfind.h>
     25#include <lemon/graph_utils.h>
     26#include <lemon/maps.h>
     27
     28#include <lemon/radix_sort.h>
     29
    2530#include <lemon/bits/utility.h>
    2631#include <lemon/bits/traits.h>
     
    3540namespace lemon {
    3641
    37   /// \addtogroup spantree
    38   /// @{
    39 
    40   /// Kruskal's algorithm to find a minimum cost tree of a graph.
    41 
     42  namespace _kruskal_bits {
     43
     44    template <typename Map, typename Comp>
     45    struct MappedComp {
     46
     47      typedef typename Map::Key Key;
     48
     49      const Map& map;
     50      Comp comp;
     51
     52      MappedComp(const Map& _map)
     53        : map(_map), comp() {}
     54
     55      bool operator()(const Key& left, const Key& right) {
     56        return comp(map[left], map[right]);
     57      }
     58
     59    };
     60 
     61  }
     62
     63  /// \ingroup spantree
     64  ///
     65  /// \brief Default traits class of Kruskal class.
     66  ///
     67  /// Default traits class of Kruskal class.
     68  /// \param _UGraph Undirected graph type.
     69  /// \param _CostMap Type of cost map.
     70  template <typename _UGraph, typename _CostMap>
     71  struct KruskalDefaultTraits{
     72
     73    /// \brief The graph type the algorithm runs on.
     74    typedef _UGraph UGraph;
     75
     76    /// \brief The type of the map that stores the edge costs.
     77    ///
     78    /// The type of the map that stores the edge costs.
     79    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
     80    typedef _CostMap CostMap;
     81
     82    /// \brief The type of the cost of the edges.
     83    typedef typename _CostMap::Value Value;
     84
     85    /// \brief The type of the map that stores whether an edge is in the
     86    /// spanning tree or not.
     87    ///
     88    /// The type of the map that stores whether an edge is in the
     89    /// spanning tree or not.
     90    typedef typename _UGraph::template UEdgeMap<bool> TreeMap;
     91
     92    /// \brief Instantiates a TreeMap.
     93    ///
     94    /// This function instantiates a \ref TreeMap.
     95    ///
     96    /// The first parameter is the graph, to which
     97    /// we would like to define the \ref TreeMap
     98    static TreeMap *createTreeMap(const _UGraph& graph){
     99      return new TreeMap(graph);
     100    }
     101
     102    template <typename Iterator>
     103    static void sort(Iterator begin, Iterator end, const CostMap& cost) {
     104      _kruskal_bits::MappedComp<CostMap, std::less<Value> > comp(cost);
     105      std::sort(begin, end, comp);
     106    }
     107
     108  };
     109
     110  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
     111  ///
     112  /// This class implements Kruskal's algorithm to find a minimum cost
     113  /// spanning tree. The
     114  ///
     115  /// \param _UGraph Undirected graph type.
     116  /// \param _CostMap Type of cost map.
     117  template <typename _UGraph, typename _CostMap,
     118            typename _Traits = KruskalDefaultTraits<_UGraph, _CostMap> >
     119  class Kruskal {
     120  public:
     121
     122    typedef _Traits Traits;
     123
     124    typedef typename _Traits::UGraph UGraph;
     125    typedef typename _Traits::CostMap CostMap;
     126
     127    typedef typename _Traits::TreeMap TreeMap;
     128
     129    typedef typename _Traits::Value Value;
     130
     131    template <typename Comp>
     132    struct DefSortCompareTraits : public Traits {
     133      template <typename Iterator>
     134      static void sort(Iterator begin, Iterator end, const CostMap& cost) {
     135        _kruskal_bits::MappedComp<CostMap, Comp> comp(cost, Comp());
     136        std::sort(begin, end, comp);
     137      }
     138    };
     139
     140    /// \brief \ref named-templ-param "Named parameter" for setting the
     141    /// comparator object of the standard sort
     142    ///
     143    /// \ref named-templ-param "Named parameter" for setting the
     144    /// comparator object of the standard sort
     145    template <typename Comp>
     146    struct DefSortCompare
     147      : public Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > {
     148      typedef Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > Create;
     149    };   
     150
     151    struct DefRadixSortTraits : public Traits {
     152      template <typename Iterator>
     153      static void sort(Iterator begin, Iterator end, const CostMap& cost) {
     154        radixSort(begin, end, cost);
     155      }
     156    };
     157
     158    /// \brief \ref named-templ-param "Named parameter" for setting the
     159    /// sort function to radix sort
     160    ///
     161    /// \brief \ref named-templ-param "Named parameter" for setting the
     162    /// sort function to radix sort. The value type of the cost map should
     163    /// be integral, of course.
     164    struct DefRadixSort
     165      : public Kruskal<UGraph, CostMap, DefRadixSortTraits> {
     166      typedef Kruskal<UGraph, CostMap, DefRadixSortTraits> Create;
     167    };   
     168
     169    template <class TM>
     170    struct DefTreeMapTraits : public Traits {
     171      typedef TM TreeMap;
     172      static TreeMap *createTreeMap(const UGraph &) {
     173        throw UninitializedParameter();
     174      }
     175    };
     176
     177    /// \brief \ref named-templ-param "Named parameter" for setting
     178    /// TreeMap
     179    ///
     180    /// \ref named-templ-param "Named parameter" for setting TreeMap
     181    ///
     182    template <class TM>
     183    struct DefTreeMap
     184      : public Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > {
     185      typedef Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
     186    };   
     187   
     188
     189  private:
     190
     191    typedef typename UGraph::Node Node;
     192    typedef typename UGraph::NodeIt NodeIt;
     193
     194    typedef typename UGraph::UEdge UEdge;
     195    typedef typename UGraph::UEdgeIt UEdgeIt;
     196
     197    const UGraph& graph;
     198    const CostMap& cost;
     199   
     200    std::vector<UEdge> edges;
     201   
     202    typedef typename UGraph::template NodeMap<int> UfIndex;
     203    typedef UnionFind<UfIndex> Uf;
     204    UfIndex *ufi;
     205    Uf *uf;
     206
     207    int index;
     208
     209    void initStructures() {
     210      if (!_tree) {
     211        _tree = Traits::createTreeMap(graph);
     212        local_tree = true;
     213      }
     214      if (!uf) {
     215        ufi = new typename UGraph::template NodeMap<int>(graph);
     216        uf = new UnionFind<typename UGraph::template NodeMap<int> >(*ufi);
     217      }
     218    }
     219   
     220    void initUnionFind() {
     221      uf->clear();
     222      for (NodeIt it(graph); it != INVALID; ++it) {
     223        uf->insert(it);
     224      }
     225    }
     226
     227    bool local_tree;
     228    TreeMap* _tree;
     229
     230  public:
     231
     232    /// \brief Constructor
     233    ///
     234    /// Constructor of the algorithm.
     235    Kruskal(const UGraph& _graph, const CostMap& _cost)
     236      : graph(_graph), cost(_cost),
     237        ufi(0), uf(0), local_tree(false), _tree(0) {}
     238
     239    /// \brief Destructor
     240    ///
     241    /// Destructor
     242    ~Kruskal() {
     243      if (local_tree) {
     244        delete _tree;
     245      }
     246      if (uf) {
     247        delete uf;
     248        delete ufi;
     249      }
     250    }
     251
     252    /// \brief Sets the map storing the tree edges.
     253    ///
     254    /// Sets the map storing the tree edges.
     255    /// If you don't use this function before calling \ref run(),
     256    /// it will allocate one. The destuctor deallocates this
     257    /// automatically allocated map, of course.
     258    /// \return \c *this </tt>
     259    Kruskal& treeMap(TreeMap &m){
     260      if (local_tree) {
     261        delete _tree;
     262        local_tree = false;
     263      }
     264      _tree = &m;
     265      return *this;
     266    }
     267
     268    /// \brief Initialize the algorithm
     269    ///
     270    /// This member function initializes the unionfind data structure
     271    /// and sorts the edges into ascending order
     272    void init() {
     273      initStructures();
     274      initUnionFind();
     275      for (UEdgeIt e(graph); e != INVALID; ++e) {
     276        edges.push_back(e);
     277        _tree->set(e, false);
     278      }     
     279      Traits::sort(edges.begin(), edges.end(), cost);
     280      index = 0;
     281    }
     282
     283
     284    /// \brief Initialize the algorithm
     285    ///
     286    /// This member function initializes the unionfind data structure
     287    /// and sets the edge order to the given sequence. The given
     288    /// sequence should be a valid STL range of undirected edges.
     289    template <typename Iterator>
     290    void initPresorted(Iterator begin, Iterator end) {
     291      initStructures();
     292      initUnionFind();
     293      edges.clear();
     294      std::copy(begin, end, std::back_inserter(edges));
     295      index = 0;
     296    }
     297
     298    /// \brief Initialize the algorithm
     299    ///
     300    /// This member function initializes the unionfind data structure
     301    /// and sets the edge order to the given sequence. The given
     302    /// sequence should be a valid STL range of undirected edges.
     303    void reinit() {
     304      initStructures();
     305      initUnionFind();
     306      for (UEdgeIt e(graph); e != INVALID; ++e) {
     307        _tree->set(e, false);
     308      }
     309      index = 0;
     310    }
     311
     312
     313    /// \brief Executes the algorithm.
     314    ///
     315    /// Executes the algorithm.
     316    ///
     317    /// \pre init() must be called before using this function.
     318    ///
     319    /// This method runs the %Kruskal algorithm.
     320    void start() {
     321      while (index < int(edges.size())) {
     322        if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
     323          _tree->set(edges[index], true);
     324        }
     325        ++index;
     326      }
     327    }
     328
     329    /// \brief Runs the prim algorithm until it find a new tree edge
     330    ///
     331    /// Runs the prim algorithm until it find a new tree edge. If it
     332    /// does not next tree edge in the sequence it gives back \c INVALID.
     333    UEdge findNextTreeEdge() {
     334      while (index < int(edges.size())) {
     335        if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
     336          _tree->set(edges[index], true);
     337          return edges[index++];
     338        }       
     339        ++index;
     340      }
     341      return INVALID;
     342    }
     343     
     344    /// \brief Processes the next edge in the sequence
     345    ///
     346    /// Processes the next edge in the sequence.
     347    ///
     348    /// \return The prcocessed edge.
     349    ///
     350    /// \warning The sequence must not be empty!
     351    UEdge processNextEdge() {
     352      UEdge edge = edges[index++];
     353      processEdge(edge);
     354      return edge;
     355    }
     356
     357    /// \brief Processes an arbitrary edge
     358    ///
     359    /// Processes the next edge in the sequence.
     360    ///
     361    /// \return True when the edge is a tree edge.
     362    bool processEdge(const UEdge& edge) {
     363      if (uf->join(graph.target(edge), graph.source(edge))) {
     364        _tree->set(edge, true);
     365        return true;
     366      } else {
     367        return false;
     368      }   
     369    }
     370
     371    /// \brief Returns \c false if there are edge to be processed in
     372    /// sequence
     373    ///
     374    /// Returns \c false if there are nodes to be processed in the
     375    /// sequence
     376    bool emptyQueue() {
     377      return index == int(edges.size());
     378    }
     379
     380    /// \brief Returns the next edge to be processed
     381    ///
     382    /// Returns the next edge to be processed
     383    ///
     384    UEdge nextEdge() const {
     385      return edges[index];
     386    }
     387
     388    /// \brief Runs %Kruskal algorithm.
     389    ///
     390    /// This method runs the %Kruskal algorithm in order to compute the
     391    /// minimum spanning tree (or minimum spanning forest).  The
     392    /// method also works on graphs that has more than one components.
     393    /// In this case it computes the minimum spanning forest.
     394    void run() {
     395      init();
     396      start();
     397    }
     398
     399    /// \brief Returns a reference to the tree edges map
     400    ///
     401    /// Returns a reference to the TreeEdgeMap of the edges of the
     402    /// minimum spanning tree. The value of the map is \c true only if
     403    /// the edge is in the minimum spanning tree.
     404    ///
     405    const TreeMap &treeMap() const { return *_tree;}
     406
     407    /// \brief Returns the total cost of the tree
     408    ///
     409    /// Returns the total cost of the tree
     410    Value treeValue() const {
     411      Value value = 0;
     412      for (UEdgeIt it(graph); it != INVALID; ++it) {
     413        if ((*_tree)[it]) {
     414          value += cost[it];
     415        }
     416      }
     417      return value;
     418    }
     419
     420    /// \brief Returns true when the given edge is tree edge
     421    ///
     422    /// Returns true when the given edge is tree edge
     423    bool tree(UEdge e) const {
     424      return (*_tree)[e];
     425    }
     426   
     427   
     428  };
     429
     430
     431  namespace _kruskal_bits {
     432
     433    template <typename Graph, typename In, typename Out>
     434    typename In::value_type::second_type
     435    kruskal(const Graph& graph, const In& in, Out& out) {
     436      typedef typename In::value_type::second_type Value;
     437      typedef typename Graph::template NodeMap<int> IndexMap;
     438      typedef typename Graph::Node Node;
     439     
     440      IndexMap index(graph);
     441      UnionFind<IndexMap> uf(index);
     442      for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
     443        uf.insert(it);
     444      }
     445     
     446      Value tree_value = 0;
     447      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
     448        if (uf.join(graph.target(it->first),graph.source(it->first))) {
     449          out.set(it->first, true);
     450          tree_value += it->second;
     451        }
     452        else {
     453          out.set(it->first, false);
     454        }
     455      }
     456      return tree_value;
     457    }
     458
     459
     460    template <typename Sequence>
     461    struct PairComp {
     462      typedef typename Sequence::value_type Value;
     463      bool operator()(const Value& left, const Value& right) {
     464        return left.second < right.second;
     465      }
     466    };
     467
     468    template <typename In, typename Enable = void>
     469    struct SequenceInputIndicator {
     470      static const bool value = false;
     471    };
     472
     473    template <typename In>
     474    struct SequenceInputIndicator<In,
     475      typename exists<typename In::value_type::first_type>::type> {
     476      static const bool value = true;
     477    };
     478
     479    template <typename In, typename Enable = void>
     480    struct MapInputIndicator {
     481      static const bool value = false;
     482    };
     483
     484    template <typename In>
     485    struct MapInputIndicator<In,
     486      typename exists<typename In::Value>::type> {
     487      static const bool value = true;
     488    };
     489
     490    template <typename In, typename Enable = void>
     491    struct SequenceOutputIndicator {
     492      static const bool value = false;
     493    };
     494 
     495    template <typename Out>
     496    struct SequenceOutputIndicator<Out,
     497      typename exists<typename Out::value_type>::type> {
     498      static const bool value = true;
     499    };
     500
     501    template <typename Out, typename Enable = void>
     502    struct MapOutputIndicator {
     503      static const bool value = false;
     504    };
     505
     506    template <typename Out>
     507    struct MapOutputIndicator<Out,
     508      typename exists<typename Out::Value>::type> {
     509      static const bool value = true;
     510    };
     511
     512    template <typename In, typename InEnable = void>
     513    struct KruskalValueSelector {};
     514
     515    template <typename In>
     516    struct KruskalValueSelector<In,
     517      typename enable_if<SequenceInputIndicator<In>, void>::type>
     518    {
     519      typedef typename In::value_type::second_type Value;
     520    };   
     521
     522    template <typename In>
     523    struct KruskalValueSelector<In,
     524      typename enable_if<MapInputIndicator<In>, void>::type>
     525    {
     526      typedef typename In::Value Value;
     527    };   
     528   
     529    template <typename Graph, typename In, typename Out,
     530              typename InEnable = void>
     531    struct KruskalInputSelector {};
     532
     533    template <typename Graph, typename In, typename Out,
     534              typename InEnable = void>
     535    struct KruskalOutputSelector {};
     536   
     537    template <typename Graph, typename In, typename Out>
     538    struct KruskalInputSelector<Graph, In, Out,
     539      typename enable_if<SequenceInputIndicator<In>, void>::type >
     540    {
     541      typedef typename In::value_type::second_type Value;
     542
     543      static Value kruskal(const Graph& graph, const In& in, Out& out) {
     544        return KruskalOutputSelector<Graph, In, Out>::
     545          kruskal(graph, in, out);
     546      }
     547
     548    };
     549
     550    template <typename Graph, typename In, typename Out>
     551    struct KruskalInputSelector<Graph, In, Out,
     552      typename enable_if<MapInputIndicator<In>, void>::type >
     553    {
     554      typedef typename In::Value Value;
     555      static Value kruskal(const Graph& graph, const In& in, Out& out) {
     556        typedef typename In::Key MapEdge;
     557        typedef typename In::Value Value;
     558        typedef typename ItemSetTraits<Graph, MapEdge>::ItemIt MapEdgeIt;
     559        typedef std::vector<std::pair<MapEdge, Value> > Sequence;
     560        Sequence seq;
     561       
     562        for (MapEdgeIt it(graph); it != INVALID; ++it) {
     563          seq.push_back(make_pair(it, in[it]));
     564        }
     565
     566        std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
     567        return KruskalOutputSelector<Graph, Sequence, Out>::
     568          kruskal(graph, seq, out);
     569      }
     570    };
     571
     572    template <typename Graph, typename In, typename Out>
     573    struct KruskalOutputSelector<Graph, In, Out,
     574      typename enable_if<SequenceOutputIndicator<Out>, void>::type >
     575    {
     576      typedef typename In::value_type::second_type Value;
     577
     578      static Value kruskal(const Graph& graph, const In& in, Out& out) {
     579        typedef StoreBoolMap<Out> Map;
     580        Map map(out);
     581        return _kruskal_bits::kruskal(graph, in, map);
     582      }
     583
     584    };
     585
     586    template <typename Graph, typename In, typename Out>
     587    struct KruskalOutputSelector<Graph, In, Out,
     588      typename enable_if<MapOutputIndicator<Out>, void>::type >
     589    {
     590      typedef typename In::value_type::second_type Value;
     591
     592      static Value kruskal(const Graph& graph, const In& in, Out& out) {
     593        return _kruskal_bits::kruskal(graph, in, out);
     594      }
     595    };
     596
     597  }
     598
     599  /// \ingroup spantree
     600  ///
     601  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
     602  ///
    42603  /// This function runs Kruskal's algorithm to find a minimum cost tree.
    43604  /// Due to hard C++ hacking, it accepts various input and output types.
     
    51612  /// \param in This object is used to describe the edge costs. It can be one
    52613  /// of the following choices.
    53   /// - An STL compatible 'Forward Container'
    54   /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
    55   /// where \c X is the type of the costs. The pairs indicates the edges along
    56   /// with the assigned cost. <em>They must be in a
     614  ///
     615  /// - An STL compatible 'Forward Container' with
     616  /// <tt>std::pair<GR::UEdge,X></tt> or
     617  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
     618  /// \c X is the type of the costs. The pairs indicates the edges
     619  /// along with the assigned cost. <em>They must be in a
    57620  /// cost-ascending order.</em>
    58621  /// - Any readable Edge map. The values of the map indicate the edge costs.
    59622  ///
    60623  /// \retval out Here we also have a choise.
    61   /// - It can be a writable \c bool edge map.
    62   /// After running the algorithm
    63   /// this will contain the found minimum cost spanning tree: the value of an
    64   /// edge will be set to \c true if it belongs to the tree, otherwise it will
    65   /// be set to \c false. The value of each edge will be set exactly once.
     624  /// - It can be a writable \c bool edge map.  After running the
     625  /// algorithm this will contain the found minimum cost spanning
     626  /// tree: the value of an edge will be set to \c true if it belongs
     627  /// to the tree, otherwise it will be set to \c false. The value of
     628  /// each edge will be set exactly once.
    66629  /// - It can also be an iteraror of an STL Container with
    67   /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
    68   /// The algorithm copies the elements of the found tree into this sequence.
    69   /// For example, if we know that the spanning tree of the graph \c g has
    70   /// say 53 edges, then
    71   /// we can put its edges into an STL vector \c tree with a code like this.
     630  /// <tt>GR::UEdge</tt> or <tt>GR::Edge</tt> as its
     631  /// <tt>value_type</tt>.  The algorithm copies the elements of the
     632  /// found tree into this sequence.  For example, if we know that the
     633  /// spanning tree of the graph \c g has say 53 edges, then we can
     634  /// put its edges into an STL vector \c tree with a code like this.
    72635  ///\code
    73636  /// std::vector<Edge> tree(53);
    74637  /// kruskal(g,cost,tree.begin());
    75638  ///\endcode
    76   /// Or if we don't know in advance the size of the tree, we can write this.
    77   ///\code
    78   /// std::vector<Edge> tree;
    79   /// kruskal(g,cost,std::back_inserter(tree));
     639  /// Or if we don't know in advance the size of the tree, we can
     640  /// write this. 
     641  ///\code std::vector<Edge> tree;
     642  /// kruskal(g,cost,std::back_inserter(tree)); 
    80643  ///\endcode
    81644  ///
    82   /// \return The cost of the found tree.
    83   ///
    84   /// \warning If kruskal runs on an
    85   /// \ref lemon::concepts::UGraph "undirected graph", be sure that the
    86   /// map storing the tree is also undirected
    87   /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the
    88   /// half of the edges will not be set.
     645  /// \return The total cost of the found tree.
     646  ///
     647  /// \warning If kruskal runs on an be consistent of using the same
     648  /// Edge type for input and output.
    89649  ///
    90650
    91651#ifdef DOXYGEN
    92   template <class GR, class IN, class OUT>
    93   CostType
    94   kruskal(GR const& g, IN const& in,
    95           OUT& out)
    96 #else
    97   template <class GR, class IN, class OUT>
    98   typename IN::value_type::second_type
    99   kruskal(GR const& g, IN const& in,
    100           OUT& out,
    101 //        typename IN::value_type::first_type = typename GR::Edge()
    102 //        ,typename OUT::Key = OUT::Key()
    103 //        //,typename OUT::Key = typename GR::Edge()
    104           const typename IN::value_type::first_type * =
    105           reinterpret_cast<const typename IN::value_type::first_type*>(0),
    106           const typename OUT::Key * =
    107           reinterpret_cast<const typename OUT::Key*>(0)
    108           )
     652  template <class Graph, class In, class Out>
     653  Value kruskal(GR const& g, const In& in, Out& out)
     654#else
     655  template <class Graph, class In, class Out>
     656  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
     657  kruskal(const Graph& graph, const In& in, Out& out)
    109658#endif
    110659  {
    111     typedef typename IN::value_type::second_type EdgeCost;
    112     typedef typename GR::template NodeMap<int> NodeIntMap;
    113     typedef typename GR::Node Node;
    114 
    115     NodeIntMap comp(g);
    116     UnionFind<NodeIntMap> uf(comp);
    117     for (typename GR::NodeIt it(g); it != INVALID; ++it) {
    118       uf.insert(it);
    119     }
    120      
    121     EdgeCost tot_cost = 0;
    122     for (typename IN::const_iterator p = in.begin();
    123          p!=in.end(); ++p ) {
    124       if ( uf.join(g.target((*p).first),
    125                    g.source((*p).first)) ) {
    126         out.set((*p).first, true);
    127         tot_cost += (*p).second;
    128       }
    129       else {
    130         out.set((*p).first, false);
    131       }
    132     }
    133     return tot_cost;
     660    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
     661      kruskal(graph, in, out);
    134662  }
    135663
    136664 
    137   /// @}
    138 
    139665 
    140   /* A work-around for running Kruskal with const-reference bool maps... */
    141 
    142   /// Helper class for calling kruskal with "constant" output map.
    143 
    144   /// Helper class for calling kruskal with output maps constructed
    145   /// on-the-fly.
    146   ///
    147   /// A typical examle is the following call:
    148   /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
    149   /// Here, the third argument is a temporary object (which wraps around an
    150   /// iterator with a writable bool map interface), and thus by rules of C++
    151   /// is a \c const object. To enable call like this exist this class and
    152   /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
    153   /// third argument.
    154   template<class Map>
    155   class NonConstMapWr {
    156     const Map &m;
    157   public:
    158     typedef typename Map::Key Key;
    159     typedef typename Map::Value Value;
    160 
    161     NonConstMapWr(const Map &_m) : m(_m) {}
    162 
    163     template<class Key>
    164     void set(Key const& k, Value const &v) const { m.set(k,v); }
    165   };
    166 
    167   template <class GR, class IN, class OUT>
    168   inline
    169   typename IN::value_type::second_type
    170   kruskal(GR const& g, IN const& edges, OUT const& out_map,
    171 //        typename IN::value_type::first_type = typename GR::Edge(),
    172 //        typename OUT::Key = GR::Edge()
    173           const typename IN::value_type::first_type * =
    174           reinterpret_cast<const typename IN::value_type::first_type*>(0),
    175           const typename OUT::Key * =
    176           reinterpret_cast<const typename OUT::Key*>(0)
    177           )
     666
     667  template <class Graph, class In, class Out>
     668  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
     669  kruskal(const Graph& graph, const In& in, const Out& out)
    178670  {
    179     NonConstMapWr<OUT> map_wr(out_map);
    180     return kruskal(g, edges, map_wr);
     671    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
     672      kruskal(graph, in, out);
    181673  } 
    182674
    183   /* ** ** Input-objects ** ** */
    184 
    185   /// Kruskal's input source.
    186  
    187   /// Kruskal's input source.
    188   ///
    189   /// In most cases you possibly want to use the \ref kruskal() instead.
    190   ///
    191   /// \sa makeKruskalMapInput()
    192   ///
    193   ///\param GR The type of the graph the algorithm runs on.
    194   ///\param Map An edge map containing the cost of the edges.
    195   ///\par
    196   ///The cost type can be any type satisfying
    197   ///the STL 'LessThan comparable'
    198   ///concept if it also has an operator+() implemented. (It is necessary for
    199   ///computing the total cost of the tree).
    200   ///
    201   template<class GR, class Map>
    202   class KruskalMapInput
    203     : public std::vector< std::pair<typename GR::Edge,
    204                                     typename Map::Value> > {
    205    
    206   public:
    207     typedef std::vector< std::pair<typename GR::Edge,
    208                                    typename Map::Value> > Parent;
    209     typedef typename Parent::value_type value_type;
    210 
    211   private:
    212     class comparePair {
    213     public:
    214       bool operator()(const value_type& a,
    215                       const value_type& b) {
    216         return a.second < b.second;
    217       }
    218     };
    219 
    220     template<class _GR>
    221     typename enable_if<UndirectedTagIndicator<_GR>,void>::type
    222     fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
    223     {
    224       for(typename GR::UEdgeIt e(g);e!=INVALID;++e)
    225         push_back(value_type(g.direct(e, true), m[e]));
    226     }
    227 
    228     template<class _GR>
    229     typename disable_if<UndirectedTagIndicator<_GR>,void>::type
    230     fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
    231     {
    232       for(typename GR::EdgeIt e(g);e!=INVALID;++e)
    233         push_back(value_type(e, m[e]));
    234     }
    235    
    236    
    237   public:
    238 
    239     void sort() {
    240       std::sort(this->begin(), this->end(), comparePair());
    241     }
    242 
    243     KruskalMapInput(GR const& g, Map const& m) {
    244       fillWithEdges(g,m);
    245       sort();
    246     }
    247   };
    248 
    249   /// Creates a KruskalMapInput object for \ref kruskal()
    250 
    251   /// It makes easier to use
    252   /// \ref KruskalMapInput by making it unnecessary
    253   /// to explicitly give the type of the parameters.
    254   ///
    255   /// In most cases you possibly
    256   /// want to use \ref kruskal() instead.
    257   ///
    258   ///\param g The type of the graph the algorithm runs on.
    259   ///\param m An edge map containing the cost of the edges.
    260   ///\par
    261   ///The cost type can be any type satisfying the
    262   ///STL 'LessThan Comparable'
    263   ///concept if it also has an operator+() implemented. (It is necessary for
    264   ///computing the total cost of the tree).
    265   ///
    266   ///\return An appropriate input source for \ref kruskal().
    267   ///
    268   template<class GR, class Map>
    269   inline
    270   KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
    271   {
    272     return KruskalMapInput<GR,Map>(g,m);
    273   }
    274  
    275  
    276 
    277   /* ** ** Output-objects: simple writable bool maps ** ** */
    278  
    279 
    280 
    281   /// A writable bool-map that makes a sequence of "true" keys
    282 
    283   /// A writable bool-map that creates a sequence out of keys that receives
    284   /// the value "true".
    285   ///
    286   /// \sa makeKruskalSequenceOutput()
    287   ///
    288   /// Very often, when looking for a min cost spanning tree, we want as
    289   /// output a container containing the edges of the found tree. For this
    290   /// purpose exist this class that wraps around an STL iterator with a
    291   /// writable bool map interface. When a key gets value "true" this key
    292   /// is added to sequence pointed by the iterator.
    293   ///
    294   /// A typical usage:
    295   ///\code
    296   /// std::vector<Graph::Edge> v;
    297   /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
    298   ///\endcode
    299   ///
    300   /// For the most common case, when the input is given by a simple edge
    301   /// map and the output is a sequence of the tree edges, a special
    302   /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
    303   ///
    304   /// \warning Not a regular property map, as it doesn't know its Key
    305 
    306   template<class Iterator>
    307   class KruskalSequenceOutput {
    308     mutable Iterator it;
    309 
    310   public:
    311     typedef typename std::iterator_traits<Iterator>::value_type Key;
    312     typedef bool Value;
    313 
    314     KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
    315 
    316     template<typename Key>
    317     void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
    318   };
    319 
    320   template<class Iterator>
    321   inline
    322   KruskalSequenceOutput<Iterator>
    323   makeKruskalSequenceOutput(Iterator it) {
    324     return KruskalSequenceOutput<Iterator>(it);
    325   }
    326 
    327 
    328 
    329   /* ** ** Wrapper funtions ** ** */
    330 
    331 //   \brief Wrapper function to kruskal().
    332 //   Input is from an edge map, output is a plain bool map.
    333 // 
    334 //   Wrapper function to kruskal().
    335 //   Input is from an edge map, output is a plain bool map.
    336 // 
    337 //   \param g The type of the graph the algorithm runs on.
    338 //   \param in An edge map containing the cost of the edges.
    339 //   \par
    340 //   The cost type can be any type satisfying the
    341 //   STL 'LessThan Comparable'
    342 //   concept if it also has an operator+() implemented. (It is necessary for
    343 //   computing the total cost of the tree).
    344 // 
    345 //   \retval out This must be a writable \c bool edge map.
    346 //   After running the algorithm
    347 //   this will contain the found minimum cost spanning tree: the value of an
    348 //   edge will be set to \c true if it belongs to the tree, otherwise it will
    349 //   be set to \c false. The value of each edge will be set exactly once.
    350 // 
    351 //   \return The cost of the found tree.
    352 
    353   template <class GR, class IN, class RET>
    354   inline
    355   typename IN::Value
    356   kruskal(GR const& g,
    357           IN const& in,
    358           RET &out,
    359           //      typename IN::Key = typename GR::Edge(),
    360           //typename IN::Key = typename IN::Key (),
    361           //      typename RET::Key = typename GR::Edge()
    362           const typename IN::Key * =
    363           reinterpret_cast<const typename IN::Key*>(0),
    364           const typename RET::Key * =
    365           reinterpret_cast<const typename RET::Key*>(0)
    366           )
    367   {
    368     return kruskal(g,
    369                    KruskalMapInput<GR,IN>(g,in),
    370                    out);
    371   }
    372 
    373 //   \brief Wrapper function to kruskal().
    374 //   Input is from an edge map, output is an STL Sequence.
    375 // 
    376 //   Wrapper function to kruskal().
    377 //   Input is from an edge map, output is an STL Sequence.
    378 // 
    379 //   \param g The type of the graph the algorithm runs on.
    380 //   \param in An edge map containing the cost of the edges.
    381 //   \par
    382 //   The cost type can be any type satisfying the
    383 //   STL 'LessThan Comparable'
    384 //   concept if it also has an operator+() implemented. (It is necessary for
    385 //   computing the total cost of the tree).
    386 // 
    387 //   \retval out This must be an iteraror of an STL Container with
    388 //   <tt>GR::Edge</tt> as its <tt>value_type</tt>.
    389 //   The algorithm copies the elements of the found tree into this sequence.
    390 //   For example, if we know that the spanning tree of the graph \c g has
    391 //   say 53 edges, then
    392 //   we can put its edges into an STL vector \c tree with a code like this.
    393 //\code
    394 //   std::vector<Edge> tree(53);
    395 //   kruskal(g,cost,tree.begin());
    396 //\endcode
    397 //   Or if we don't know in advance the size of the tree, we can write this.
    398 //\code
    399 //   std::vector<Edge> tree;
    400 //   kruskal(g,cost,std::back_inserter(tree));
    401 //\endcode
    402 // 
    403 //   \return The cost of the found tree.
    404 // 
    405 //   \bug its name does not follow the coding style.
    406 
    407   template <class GR, class IN, class RET>
    408   inline
    409   typename IN::Value
    410   kruskal(const GR& g,
    411           const IN& in,
    412           RET out,
    413           const typename RET::value_type * =
    414           reinterpret_cast<const typename RET::value_type*>(0)
    415           )
    416   {
    417     KruskalSequenceOutput<RET> _out(out);
    418     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
    419   }
    420  
    421   template <class GR, class IN, class RET>
    422   inline
    423   typename IN::Value
    424   kruskal(const GR& g,
    425           const IN& in,
    426           RET *out
    427           )
    428   {
    429     KruskalSequenceOutput<RET*> _out(out);
    430     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
    431   }
    432  
    433   /// @}
    434 
    435675} //namespace lemon
    436676
Note: See TracChangeset for help on using the changeset viewer.