lemon/unionfind.h
changeset 561 6e0525ec5355
parent 440 88ed40ad0d4f
child 786 e20173729589
child 867 5b926cc36a4b
equal deleted inserted replaced
6:afe1068aba23 7:22bce061f57c
    49   /// cost spanning tree in a graph.
    49   /// cost spanning tree in a graph.
    50   /// \sa kruskal()
    50   /// \sa kruskal()
    51   ///
    51   ///
    52   /// \pre You need to add all the elements by the \ref insert()
    52   /// \pre You need to add all the elements by the \ref insert()
    53   /// method.
    53   /// method.
    54   template <typename _ItemIntMap>
    54   template <typename IM>
    55   class UnionFind {
    55   class UnionFind {
    56   public:
    56   public:
    57 
    57 
    58     typedef _ItemIntMap ItemIntMap;
    58     ///\e
       
    59     typedef IM ItemIntMap;
       
    60     ///\e
    59     typedef typename ItemIntMap::Key Item;
    61     typedef typename ItemIntMap::Key Item;
    60 
    62 
    61   private:
    63   private:
    62     // If the items vector stores negative value for an item then
    64     // If the items vector stores negative value for an item then
    63     // that item is root item and it has -items[it] component size.
    65     // that item is root item and it has -items[it] component size.
   168   /// the find operation uses path compression.
   170   /// the find operation uses path compression.
   169   ///
   171   ///
   170   /// \pre You need to add all the elements by the \ref insert()
   172   /// \pre You need to add all the elements by the \ref insert()
   171   /// method.
   173   /// method.
   172   ///
   174   ///
   173   template <typename _ItemIntMap>
   175   template <typename IM>
   174   class UnionFindEnum {
   176   class UnionFindEnum {
   175   public:
   177   public:
   176 
   178 
   177     typedef _ItemIntMap ItemIntMap;
   179     ///\e
       
   180     typedef IM ItemIntMap;
       
   181     ///\e
   178     typedef typename ItemIntMap::Key Item;
   182     typedef typename ItemIntMap::Key Item;
   179 
   183 
   180   private:
   184   private:
   181 
   185 
   182     ItemIntMap& index;
   186     ItemIntMap& index;
   625   /// component. The data structure is a simplification of the
   629   /// component. The data structure is a simplification of the
   626   /// Union-Find structure, and it does not allow to merge two components.
   630   /// Union-Find structure, and it does not allow to merge two components.
   627   ///
   631   ///
   628   /// \pre You need to add all the elements by the \ref insert()
   632   /// \pre You need to add all the elements by the \ref insert()
   629   /// method.
   633   /// method.
   630   template <typename _ItemIntMap>
   634   template <typename IM>
   631   class ExtendFindEnum {
   635   class ExtendFindEnum {
   632   public:
   636   public:
   633 
   637 
   634     typedef _ItemIntMap ItemIntMap;
   638     ///\e
       
   639     typedef IM ItemIntMap;
       
   640     ///\e
   635     typedef typename ItemIntMap::Key Item;
   641     typedef typename ItemIntMap::Key Item;
   636 
   642 
   637   private:
   643   private:
   638 
   644 
   639     ItemIntMap& index;
   645     ItemIntMap& index;
   946   /// number of joined components or the number of the components
   952   /// number of joined components or the number of the components
   947   /// after the split.
   953   /// after the split.
   948   ///
   954   ///
   949   /// \pre You need to add all the elements by the \ref insert()
   955   /// \pre You need to add all the elements by the \ref insert()
   950   /// method.
   956   /// method.
   951   ///
   957   template <typename V, typename IM, typename Comp = std::less<V> >
   952   template <typename _Value, typename _ItemIntMap,
       
   953             typename _Comp = std::less<_Value> >
       
   954   class HeapUnionFind {
   958   class HeapUnionFind {
   955   public:
   959   public:
   956 
   960 
   957     typedef _Value Value;
   961     ///\e
   958     typedef typename _ItemIntMap::Key Item;
   962     typedef V Value;
   959 
   963     ///\e
   960     typedef _ItemIntMap ItemIntMap;
   964     typedef typename IM::Key Item;
   961 
   965     ///\e
   962     typedef _Comp Comp;
   966     typedef IM ItemIntMap;
       
   967     ///\e
       
   968     typedef Comp Compare;
   963 
   969 
   964   private:
   970   private:
   965 
   971 
   966     static const int cmax = 16;
   972     static const int cmax = 16;
   967 
   973 
  1599       }
  1605       }
  1600     }
  1606     }
  1601 
  1607 
  1602     /// \brief Gives back the priority of the current item.
  1608     /// \brief Gives back the priority of the current item.
  1603     ///
  1609     ///
  1604     /// \return Gives back the priority of the current item.
  1610     /// Gives back the priority of the current item.
  1605     const Value& operator[](const Item& item) const {
  1611     const Value& operator[](const Item& item) const {
  1606       return nodes[index[item]].prio;
  1612       return nodes[index[item]].prio;
  1607     }
  1613     }
  1608 
  1614 
  1609     /// \brief Sets the priority of the current item.
  1615     /// \brief Sets the priority of the current item.
  1644       }
  1650       }
  1645     }
  1651     }
  1646 
  1652 
  1647     /// \brief Gives back the minimum priority of the class.
  1653     /// \brief Gives back the minimum priority of the class.
  1648     ///
  1654     ///
  1649     /// \return Gives back the minimum priority of the class.
  1655     /// Gives back the minimum priority of the class.
  1650     const Value& classPrio(int cls) const {
  1656     const Value& classPrio(int cls) const {
  1651       return nodes[~(classes[cls].parent)].prio;
  1657       return nodes[~(classes[cls].parent)].prio;
  1652     }
  1658     }
  1653 
  1659 
  1654     /// \brief Gives back the minimum priority item of the class.
  1660     /// \brief Gives back the minimum priority item of the class.
  1658       return nodes[~(classes[cls].parent)].item;
  1664       return nodes[~(classes[cls].parent)].item;
  1659     }
  1665     }
  1660 
  1666 
  1661     /// \brief Gives back a representant item of the class.
  1667     /// \brief Gives back a representant item of the class.
  1662     ///
  1668     ///
       
  1669     /// Gives back a representant item of the class.
  1663     /// The representant is indpendent from the priorities of the
  1670     /// The representant is indpendent from the priorities of the
  1664     /// items.
  1671     /// items.
  1665     /// \return Gives back a representant item of the class.
       
  1666     const Item& classRep(int id) const {
  1672     const Item& classRep(int id) const {
  1667       int parent = classes[id].parent;
  1673       int parent = classes[id].parent;
  1668       return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
  1674       return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
  1669     }
  1675     }
  1670 
  1676