1.1 --- a/src/lemon/graph_utils.h Wed May 04 13:07:10 2005 +0000
1.2 +++ b/src/lemon/graph_utils.h Thu May 05 11:05:25 2005 +0000
1.3 @@ -18,6 +18,7 @@
1.4 #define LEMON_GRAPH_UTILS_H
1.5
1.6 #include <iterator>
1.7 +#include <map>
1.8
1.9 #include <lemon/invalid.h>
1.10 #include <lemon/utility.h>
1.11 @@ -334,7 +335,361 @@
1.12 };
1.13
1.14 /// @}
1.15 +
1.16 + /// \addtogroup graph_maps
1.17 + /// @{
1.18 +
1.19 + /// Provides an immutable and unique id for each item in the graph.
1.20 +
1.21 + /// The IdMap class provides an unique and immutable mapping for each item
1.22 + /// in the graph.
1.23 + ///
1.24 + template <typename _Graph, typename _Item>
1.25 + class IdMap {
1.26 + public:
1.27 + typedef _Graph Graph;
1.28 + typedef int Value;
1.29 + typedef _Item Item;
1.30 + typedef _Item Key;
1.31 +
1.32 + /// \brief The class represents the inverse of the map.
1.33 + ///
1.34 + /// The class represents the inverse of the map.
1.35 + /// \see inverse()
1.36 + class InverseMap {
1.37 + public:
1.38 + /// \brief Constructor.
1.39 + ///
1.40 + /// Constructor for creating an id-to-item map.
1.41 + InverseMap(const Graph& _graph) : graph(&_graph) {}
1.42 + /// \brief Gives back the given item from its id.
1.43 + ///
1.44 + /// Gives back the given item from its id.
1.45 + ///
1.46 + Item operator[](int id) const { return graph->fromId(id, Item());}
1.47 + private:
1.48 + const Graph* graph;
1.49 + };
1.50 +
1.51 + /// \brief Constructor.
1.52 + ///
1.53 + /// Constructor for creating id map.
1.54 + IdMap(const Graph& _graph) : graph(&_graph) {}
1.55 +
1.56 + /// \brief Gives back the \e id of the item.
1.57 + ///
1.58 + /// Gives back the immutable and unique \e id of the map.
1.59 + int operator[](const Item& item) const { return graph->id(item);}
1.60 +
1.61 + /// \brief Gives back the inverse of the map.
1.62 + ///
1.63 + /// Gives back the inverse of the map.
1.64 + InverseMap inverse() const { return InverseMap(*graph);}
1.65 +
1.66 + private:
1.67 + const Graph* graph;
1.68 +
1.69 + };
1.70 +
1.71
1.72 + template <typename Map, typename Enable = void>
1.73 + struct ReferenceMapTraits {
1.74 + typedef typename Map::Value Value;
1.75 + typedef typename Map::Value& Reference;
1.76 + typedef const typename Map::Value& ConstReference;
1.77 + typedef typename Map::Value* Pointer;
1.78 + typedef const typename Map::Value* ConstPointer;
1.79 + };
1.80 +
1.81 + template <typename Map>
1.82 + struct ReferenceMapTraits<
1.83 + Map,
1.84 + typename enable_if<typename Map::FullTypeTag, void>::type
1.85 + > {
1.86 + typedef typename Map::Value Value;
1.87 + typedef typename Map::Reference Reference;
1.88 + typedef typename Map::ConstReference ConstReference;
1.89 + typedef typename Map::Pointer Pointer;
1.90 + typedef typename Map::ConstPointer ConstPointer;
1.91 + };
1.92 +
1.93 + /// \brief General inversable graph-map type.
1.94 +
1.95 + /// This type provides simple inversable map functions.
1.96 + /// The InversableMap wraps an arbitrary ReadWriteMap
1.97 + /// and if a key is setted to a new value then store it
1.98 + /// in the inverse map.
1.99 + /// \param _Graph The graph type.
1.100 + /// \param _Map The map to extend with inversable functionality.
1.101 + template <
1.102 + typename _Graph,
1.103 + typename _Item,
1.104 + typename _Value,
1.105 + typename _Map
1.106 + = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
1.107 + >
1.108 + class InversableMap : protected _Map {
1.109 +
1.110 + public:
1.111 +
1.112 + typedef _Map Map;
1.113 + typedef _Graph Graph;
1.114 + /// The key type of InversableMap (Node, Edge, UndirEdge).
1.115 + typedef typename _Map::Key Key;
1.116 + /// The value type of the InversableMap.
1.117 + typedef typename _Map::Value Value;
1.118 +
1.119 + typedef std::map<Value, Key> InverseMap;
1.120 +
1.121 + typedef typename _Map::ConstReference ConstReference;
1.122 +
1.123 + /// \brief Constructor.
1.124 + ///
1.125 + /// Construct a new InversableMap for the graph.
1.126 + ///
1.127 + InversableMap(const Graph& graph) : Map(graph) {}
1.128 +
1.129 + /// \brief The setter function of the map.
1.130 + ///
1.131 +
1.132 + void set(const Key& key, const Value& val) {
1.133 + Value oldval = Map::operator[](key);
1.134 + typename InverseMap::iterator it = invMap.find(oldval);
1.135 + if (it != invMap.end() && it->second == key) {
1.136 + invMap.erase(it);
1.137 + }
1.138 + invMap.insert(make_pair(val, key));
1.139 + Map::set(key, val);
1.140 + }
1.141 +
1.142 + /// \brief The getter function of the map.
1.143 + ///
1.144 + /// It gives back the value associated with the key.
1.145 + ConstReference operator[](const Key& key) const {
1.146 + return Map::operator[](key);
1.147 + }
1.148 +
1.149 + /// \brief Add a new key to the map.
1.150 + ///
1.151 + /// Add a new key to the map. It is called by the
1.152 + /// \c AlterationNotifier.
1.153 + virtual void add(const Key& key) {
1.154 + Map::add(key);
1.155 + }
1.156 +
1.157 + /// \brief Erase the key from the map.
1.158 + ///
1.159 + /// Erase the key to the map. It is called by the
1.160 + /// \c AlterationNotifier.
1.161 + virtual void erase(const Key& key) {
1.162 + Value val = Map::operator[](key);
1.163 + typename InverseMap::iterator it = invMap.find(val);
1.164 + if (it != invMap.end() && it->second == key) {
1.165 + invMap.erase(it);
1.166 + }
1.167 + Map::erase(key);
1.168 + }
1.169 +
1.170 + /// \brief Clear the keys from the map and inverse map.
1.171 + ///
1.172 + /// Clear the keys from the map and inverse map. It is called by the
1.173 + /// \c AlterationNotifier.
1.174 + virtual void clear() {
1.175 + invMap.clear();
1.176 + Map::clear();
1.177 + }
1.178 +
1.179 + /// \brief It gives back the just readeable inverse map.
1.180 + ///
1.181 + /// It gives back the just readeable inverse map.
1.182 + const InverseMap& inverse() const {
1.183 + return invMap;
1.184 + }
1.185 +
1.186 +
1.187 + private:
1.188 + InverseMap invMap;
1.189 + };
1.190 +
1.191 + /// \brief Provides a mutable, continuous and unique descriptor for each
1.192 + /// item in the graph.
1.193 + ///
1.194 + /// The DescriptorMap class provides a mutable, continuous and immutable
1.195 + /// mapping for each item in the graph.
1.196 + ///
1.197 + /// \param _Graph The graph class the \c DescriptorMap belongs to.
1.198 + /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1.199 + /// UndirEdge.
1.200 + /// \param _Map A ReadWriteMap mapping from the item type to integer.
1.201 +
1.202 + template <
1.203 + typename _Graph,
1.204 + typename _Item,
1.205 + typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
1.206 + >
1.207 + class DescriptorMap : protected _Map {
1.208 +
1.209 + typedef _Item Item;
1.210 + typedef _Map Map;
1.211 +
1.212 + public:
1.213 + /// The graph class of DescriptorMap.
1.214 + typedef _Graph Graph;
1.215 +
1.216 + /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1.217 + typedef typename _Map::Key Key;
1.218 + /// The value type of DescriptorMap.
1.219 + typedef typename _Map::Value Value;
1.220 +
1.221 + typedef std::vector<Item> InverseMap;
1.222 +
1.223 + /// \brief Constructor.
1.224 + ///
1.225 + /// Constructor for creating descriptor map.
1.226 + DescriptorMap(const Graph& _graph) : Map(_graph) {
1.227 + build();
1.228 + }
1.229 +
1.230 + /// \brief Add a new key to the map.
1.231 + ///
1.232 + /// Add a new key to the map. It is called by the
1.233 + /// \c AlterationNotifier.
1.234 + virtual void add(const Item& item) {
1.235 + Map::add(item);
1.236 + Map::set(item, invMap.size());
1.237 + invMap.push_back(item);
1.238 + }
1.239 +
1.240 + /// \brief Erase the key from the map.
1.241 + ///
1.242 + /// Erase the key to the map. It is called by the
1.243 + /// \c AlterationNotifier.
1.244 + virtual void erase(const Item& item) {
1.245 + Map::set(invMap.back(), Map::operator[](item));
1.246 + invMap[Map::operator[](item)] = invMap.back();
1.247 + Map::erase(item);
1.248 + }
1.249 +
1.250 + /// \brief Build the unique map.
1.251 + ///
1.252 + /// Build the unique map. It is called by the
1.253 + /// \c AlterationNotifier.
1.254 + virtual void build() {
1.255 + Map::build();
1.256 + Item it;
1.257 + const typename Map::Graph* graph = Map::getGraph();
1.258 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.259 + Map::set(it, invMap.size());
1.260 + invMap.push_back(it);
1.261 + }
1.262 + }
1.263 +
1.264 + /// \brief Clear the keys from the map.
1.265 + ///
1.266 + /// Clear the keys from the map. It is called by the
1.267 + /// \c AlterationNotifier.
1.268 + virtual void clear() {
1.269 + invMap.clear();
1.270 + Map::clear();
1.271 + }
1.272 +
1.273 + /// \brief Gives back the \e descriptor of the item.
1.274 + ///
1.275 + /// Gives back the mutable and unique \e descriptor of the map.
1.276 + int operator[](const Item& item) const {
1.277 + return Map::operator[](item);
1.278 + }
1.279 +
1.280 + /// \brief Gives back the inverse of the map.
1.281 + ///
1.282 + /// Gives back the inverse of the map.
1.283 + const InverseMap inverse() const {
1.284 + return invMap;
1.285 + }
1.286 +
1.287 + private:
1.288 + std::vector<Item> invMap;
1.289 + };
1.290 +
1.291 + /// \brief Returns the source of the given edge.
1.292 + ///
1.293 + /// The SourceMap gives back the source Node of the given edge.
1.294 + /// \author Balazs Dezso
1.295 + template <typename Graph>
1.296 + class SourceMap {
1.297 + public:
1.298 + typedef typename Graph::Node Value;
1.299 + typedef typename Graph::Edge Key;
1.300 +
1.301 + /// \brief Constructor
1.302 + ///
1.303 + /// Constructor
1.304 + /// \param _graph The graph that the map belongs to.
1.305 + SourceMap(const Graph& _graph) : graph(_graph) {}
1.306 +
1.307 + /// \brief The subscript operator.
1.308 + ///
1.309 + /// The subscript operator.
1.310 + /// \param edge The edge
1.311 + /// \return The source of the edge
1.312 + Value operator[](const Key& edge) {
1.313 + return graph.source(edge);
1.314 + }
1.315 +
1.316 + private:
1.317 + const Graph& graph;
1.318 + };
1.319 +
1.320 + /// \brief Returns a \ref SourceMap class
1.321 + ///
1.322 + /// This function just returns an \ref SourceMap class.
1.323 + /// \relates SourceMap
1.324 + template <typename Graph>
1.325 + inline SourceMap<Graph> sourceMap(const Graph& graph) {
1.326 + return SourceMap<Graph>(graph);
1.327 + }
1.328 +
1.329 + /// \brief Returns the target of the given edge.
1.330 + ///
1.331 + /// The TargetMap gives back the target Node of the given edge.
1.332 + /// \author Balazs Dezso
1.333 + template <typename Graph>
1.334 + class TargetMap {
1.335 + public:
1.336 + typedef typename Graph::Node Value;
1.337 + typedef typename Graph::Edge Key;
1.338 +
1.339 + /// \brief Constructor
1.340 + ///
1.341 + /// Constructor
1.342 + /// \param _graph The graph that the map belongs to.
1.343 + TargetMap(const Graph& _graph) : graph(_graph) {}
1.344 +
1.345 + /// \brief The subscript operator.
1.346 + ///
1.347 + /// The subscript operator.
1.348 + /// \param edge The edge
1.349 + /// \return The target of the edge
1.350 + Value operator[](const Key& key) {
1.351 + return graph.target(key);
1.352 + }
1.353 +
1.354 + private:
1.355 + const Graph& graph;
1.356 + };
1.357 +
1.358 + /// \brief Returns a \ref TargetMap class
1.359 +
1.360 + /// This function just returns an \ref TargetMap class.
1.361 + /// \relates TargetMap
1.362 + template <typename Graph>
1.363 + inline TargetMap<Graph> targetMap(const Graph& graph) {
1.364 + return TargetMap<Graph>(graph);
1.365 + }
1.366 +
1.367 +
1.368 + /// @}
1.369 +
1.370 } //END OF NAMESPACE LEMON
1.371
1.372 #endif