COIN-OR::LEMON - Graph Library

Changeset 839:a2d5fd4c309a in lemon


Ignore:
Timestamp:
11/18/09 14:38:38 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
840:7c0ad6bd6a63, 859:921d5bf41ac2
Parents:
835:c92296660262 (diff), 838:4e3484a2e90c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r833 r839  
    37653765  }
    37663766
     3767
     3768  /// \brief Copy the values of a graph map to another map.
     3769  ///
     3770  /// This function copies the values of a graph map to another graph map.
     3771  /// \c To::Key must be equal or convertible to \c From::Key and
     3772  /// \c From::Value must be equal or convertible to \c To::Value.
     3773  ///
     3774  /// For example, an edge map of \c int value type can be copied to
     3775  /// an arc map of \c double value type in an undirected graph, but
     3776  /// an arc map cannot be copied to an edge map.
     3777  /// Note that even a \ref ConstMap can be copied to a standard graph map,
     3778  /// but \ref mapFill() can also be used for this purpose.
     3779  ///
     3780  /// \param gr The graph for which the maps are defined.
     3781  /// \param from The map from which the values have to be copied.
     3782  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     3783  /// \param to The map to which the values have to be copied.
     3784  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     3785  template <typename GR, typename From, typename To>
     3786  void mapCopy(const GR& gr, const From& from, To& to) {
     3787    typedef typename To::Key Item;
     3788    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     3789   
     3790    for (ItemIt it(gr); it != INVALID; ++it) {
     3791      to.set(it, from[it]);
     3792    }
     3793  }
     3794
     3795  /// \brief Compare two graph maps.
     3796  ///
     3797  /// This function compares the values of two graph maps. It returns
     3798  /// \c true if the maps assign the same value for all items in the graph.
     3799  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
     3800  /// and their \c Value types must be comparable using \c %operator==().
     3801  ///
     3802  /// \param gr The graph for which the maps are defined.
     3803  /// \param map1 The first map.
     3804  /// \param map2 The second map.
     3805  template <typename GR, typename Map1, typename Map2>
     3806  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
     3807    typedef typename Map2::Key Item;
     3808    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     3809   
     3810    for (ItemIt it(gr); it != INVALID; ++it) {
     3811      if (!(map1[it] == map2[it])) return false;
     3812    }
     3813    return true;
     3814  }
     3815
     3816  /// \brief Return an item having minimum value of a graph map.
     3817  ///
     3818  /// This function returns an item (\c Node, \c Arc or \c Edge) having
     3819  /// minimum value of the given graph map.
     3820  /// If the item set is empty, it returns \c INVALID.
     3821  ///
     3822  /// \param gr The graph for which the map is defined.
     3823  /// \param map The graph map.
     3824  template <typename GR, typename Map>
     3825  typename Map::Key mapMin(const GR& gr, const Map& map) {
     3826    return mapMin(gr, map, std::less<typename Map::Value>());
     3827  }
     3828
     3829  /// \brief Return an item having minimum value of a graph map.
     3830  ///
     3831  /// This function returns an item (\c Node, \c Arc or \c Edge) having
     3832  /// minimum value of the given graph map.
     3833  /// If the item set is empty, it returns \c INVALID.
     3834  ///
     3835  /// \param gr The graph for which the map is defined.
     3836  /// \param map The graph map.
     3837  /// \param comp Comparison function object.
     3838  template <typename GR, typename Map, typename Comp>
     3839  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
     3840    typedef typename Map::Key Item;
     3841    typedef typename Map::Value Value;
     3842    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     3843
     3844    ItemIt min_item(gr);
     3845    if (min_item == INVALID) return INVALID;
     3846    Value min = map[min_item];
     3847    for (ItemIt it(gr); it != INVALID; ++it) {
     3848      if (comp(map[it], min)) {
     3849        min = map[it];
     3850        min_item = it;
     3851      }
     3852    }
     3853    return min_item;
     3854  }
     3855
     3856  /// \brief Return an item having maximum value of a graph map.
     3857  ///
     3858  /// This function returns an item (\c Node, \c Arc or \c Edge) having
     3859  /// maximum value of the given graph map.
     3860  /// If the item set is empty, it returns \c INVALID.
     3861  ///
     3862  /// \param gr The graph for which the map is defined.
     3863  /// \param map The graph map.
     3864  template <typename GR, typename Map>
     3865  typename Map::Key mapMax(const GR& gr, const Map& map) {
     3866    return mapMax(gr, map, std::less<typename Map::Value>());
     3867  }
     3868
     3869  /// \brief Return an item having maximum value of a graph map.
     3870  ///
     3871  /// This function returns an item (\c Node, \c Arc or \c Edge) having
     3872  /// maximum value of the given graph map.
     3873  /// If the item set is empty, it returns \c INVALID.
     3874  ///
     3875  /// \param gr The graph for which the map is defined.
     3876  /// \param map The graph map.
     3877  /// \param comp Comparison function object.
     3878  template <typename GR, typename Map, typename Comp>
     3879  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
     3880    typedef typename Map::Key Item;
     3881    typedef typename Map::Value Value;
     3882    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     3883
     3884    ItemIt max_item(gr);
     3885    if (max_item == INVALID) return INVALID;
     3886    Value max = map[max_item];
     3887    for (ItemIt it(gr); it != INVALID; ++it) {
     3888      if (comp(max, map[it])) {
     3889        max = map[it];
     3890        max_item = it;
     3891      }
     3892    }
     3893    return max_item;
     3894  }
     3895
     3896  /// \brief Return the minimum value of a graph map.
     3897  ///
     3898  /// This function returns the minimum value of the given graph map.
     3899  /// The corresponding item set of the graph must not be empty.
     3900  ///
     3901  /// \param gr The graph for which the map is defined.
     3902  /// \param map The graph map.
     3903  template <typename GR, typename Map>
     3904  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
     3905    return map[mapMin(gr, map, std::less<typename Map::Value>())];
     3906  }
     3907
     3908  /// \brief Return the minimum value of a graph map.
     3909  ///
     3910  /// This function returns the minimum value of the given graph map.
     3911  /// The corresponding item set of the graph must not be empty.
     3912  ///
     3913  /// \param gr The graph for which the map is defined.
     3914  /// \param map The graph map.
     3915  /// \param comp Comparison function object.
     3916  template <typename GR, typename Map, typename Comp>
     3917  typename Map::Value
     3918  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
     3919    return map[mapMin(gr, map, comp)];
     3920  }
     3921
     3922  /// \brief Return the maximum value of a graph map.
     3923  ///
     3924  /// This function returns the maximum value of the given graph map.
     3925  /// The corresponding item set of the graph must not be empty.
     3926  ///
     3927  /// \param gr The graph for which the map is defined.
     3928  /// \param map The graph map.
     3929  template <typename GR, typename Map>
     3930  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
     3931    return map[mapMax(gr, map, std::less<typename Map::Value>())];
     3932  }
     3933
     3934  /// \brief Return the maximum value of a graph map.
     3935  ///
     3936  /// This function returns the maximum value of the given graph map.
     3937  /// The corresponding item set of the graph must not be empty.
     3938  ///
     3939  /// \param gr The graph for which the map is defined.
     3940  /// \param map The graph map.
     3941  /// \param comp Comparison function object.
     3942  template <typename GR, typename Map, typename Comp>
     3943  typename Map::Value
     3944  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
     3945    return map[mapMax(gr, map, comp)];
     3946  }
     3947
     3948  /// \brief Return an item having a specified value in a graph map.
     3949  ///
     3950  /// This function returns an item (\c Node, \c Arc or \c Edge) having
     3951  /// the specified assigned value in the given graph map.
     3952  /// If no such item exists, it returns \c INVALID.
     3953  ///
     3954  /// \param gr The graph for which the map is defined.
     3955  /// \param map The graph map.
     3956  /// \param val The value that have to be found.
     3957  template <typename GR, typename Map>
     3958  typename Map::Key
     3959  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
     3960    typedef typename Map::Key Item;
     3961    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     3962
     3963    for (ItemIt it(gr); it != INVALID; ++it) {
     3964      if (map[it] == val) return it;
     3965    }
     3966    return INVALID;
     3967  }
     3968
     3969  /// \brief Return an item having value for which a certain predicate is
     3970  /// true in a graph map.
     3971  ///
     3972  /// This function returns an item (\c Node, \c Arc or \c Edge) having
     3973  /// such assigned value for which the specified predicate is true
     3974  /// in the given graph map.
     3975  /// If no such item exists, it returns \c INVALID.
     3976  ///
     3977  /// \param gr The graph for which the map is defined.
     3978  /// \param map The graph map.
     3979  /// \param pred The predicate function object.
     3980  template <typename GR, typename Map, typename Pred>
     3981  typename Map::Key
     3982  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
     3983    typedef typename Map::Key Item;
     3984    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     3985
     3986    for (ItemIt it(gr); it != INVALID; ++it) {
     3987      if (pred(map[it])) return it;
     3988    }
     3989    return INVALID;
     3990  }
     3991
     3992  /// \brief Return the number of items having a specified value in a
     3993  /// graph map.
     3994  ///
     3995  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
     3996  /// having the specified assigned value in the given graph map.
     3997  ///
     3998  /// \param gr The graph for which the map is defined.
     3999  /// \param map The graph map.
     4000  /// \param val The value that have to be counted.
     4001  template <typename GR, typename Map>
     4002  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
     4003    typedef typename Map::Key Item;
     4004    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     4005
     4006    int cnt = 0;
     4007    for (ItemIt it(gr); it != INVALID; ++it) {
     4008      if (map[it] == val) ++cnt;
     4009    }
     4010    return cnt;
     4011  }
     4012
     4013  /// \brief Return the number of items having values for which a certain
     4014  /// predicate is true in a graph map.
     4015  ///
     4016  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
     4017  /// having such assigned values for which the specified predicate is true
     4018  /// in the given graph map.
     4019  ///
     4020  /// \param gr The graph for which the map is defined.
     4021  /// \param map The graph map.
     4022  /// \param pred The predicate function object.
     4023  template <typename GR, typename Map, typename Pred>
     4024  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
     4025    typedef typename Map::Key Item;
     4026    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     4027
     4028    int cnt = 0;
     4029    for (ItemIt it(gr); it != INVALID; ++it) {
     4030      if (pred(map[it])) ++cnt;
     4031    }
     4032    return cnt;
     4033  }
     4034
     4035  /// \brief Fill a graph map with a certain value.
     4036  ///
     4037  /// This function sets the specified value for all items (\c Node,
     4038  /// \c Arc or \c Edge) in the given graph map.
     4039  ///
     4040  /// \param gr The graph for which the map is defined.
     4041  /// \param map The graph map. It must conform to the
     4042  /// \ref concepts::WriteMap "WriteMap" concept.
     4043  /// \param val The value.
     4044  template <typename GR, typename Map>
     4045  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
     4046    typedef typename Map::Key Item;
     4047    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
     4048
     4049    for (ItemIt it(gr); it != INVALID; ++it) {
     4050      map.set(it, val);
     4051    }
     4052  }
     4053
    37674054  /// @}
    37684055}
  • lemon/maps.h

    r836 r839  
    231231  /// This map is essentially a wrapper for \c std::vector. It assigns
    232232  /// values to integer keys from the range <tt>[0..size-1]</tt>.
    233   /// It can be used with some data structures, for example
    234   /// \c UnionFind, \c BinHeap, when the used items are small
     233  /// It can be used together with some data structures, e.g.
     234  /// heap types and \c UnionFind, when the used items are small
    235235  /// integers. This map conforms to the \ref concepts::ReferenceMap
    236   /// "ReferenceMap" concept.
     236  /// "ReferenceMap" concept. 
    237237  ///
    238238  /// The simplest way of using this map is through the rangeMap()
     
    349349  /// The name of this type also refers to this important usage.
    350350  ///
    351   /// Apart form that this map can be used in many other cases since it
     351  /// Apart form that, this map can be used in many other cases since it
    352352  /// is based on \c std::map, which is a general associative container.
    353   /// However keep in mind that it is usually not as efficient as other
     353  /// However, keep in mind that it is usually not as efficient as other
    354354  /// maps.
    355355  ///
     
    17861786  /// The most important usage of it is storing certain nodes or arcs
    17871787  /// that were marked \c true by an algorithm.
    1788   /// For example it makes easier to store the nodes in the processing
     1788  /// For example, it makes easier to store the nodes in the processing
    17891789  /// order of Dfs algorithm, as the following examples show.
    17901790  /// \code
     
    18011801  ///
    18021802  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
    1803   /// it cannot be used when a readable map is needed, for example as
     1803  /// it cannot be used when a readable map is needed, for example, as
    18041804  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
    18051805  ///
     
    19231923  /// Otherwise consider to use \c IterableValueMap, which is more
    19241924  /// suitable and more efficient for such cases. It provides iterators
    1925   /// to traverse the items with the same associated value, however
     1925  /// to traverse the items with the same associated value, but
    19261926  /// it does not have \c InverseMap.
    19271927  ///
     
    34673467  /// may provide alternative ways to modify the digraph.
    34683468  /// The correct behavior of InDegMap is not guarantied if these additional
    3469   /// features are used. For example the functions
     3469  /// features are used. For example, the functions
    34703470  /// \ref ListDigraph::changeSource() "changeSource()",
    34713471  /// \ref ListDigraph::changeTarget() "changeTarget()" and
     
    35973597  /// may provide alternative ways to modify the digraph.
    35983598  /// The correct behavior of OutDegMap is not guarantied if these additional
    3599   /// features are used. For example the functions
     3599  /// features are used. For example, the functions
    36003600  /// \ref ListDigraph::changeSource() "changeSource()",
    36013601  /// \ref ListDigraph::changeTarget() "changeTarget()" and
Note: See TracChangeset for help on using the changeset viewer.