lemon/maps.h
changeset 844 a6eb9698c321
parent 786 e20173729589
parent 789 8ddb7deabab9
child 877 141f9c0db4a3
equal deleted inserted replaced
45:b3d7d2637835 47:b99d7f8c037d
  3762   PotentialDifferenceMap<GR, POT>
  3762   PotentialDifferenceMap<GR, POT>
  3763   potentialDifferenceMap(const GR& gr, const POT& potential) {
  3763   potentialDifferenceMap(const GR& gr, const POT& potential) {
  3764     return PotentialDifferenceMap<GR, POT>(gr, potential);
  3764     return PotentialDifferenceMap<GR, POT>(gr, potential);
  3765   }
  3765   }
  3766 
  3766 
       
  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 
  3767   /// @}
  4054   /// @}
  3768 }
  4055 }
  3769 
  4056 
  3770 #endif // LEMON_MAPS_H
  4057 #endif // LEMON_MAPS_H