1.1 --- a/doc/groups.dox Wed May 04 13:07:10 2005 +0000
1.2 +++ b/doc/groups.dox Thu May 05 11:05:25 2005 +0000
1.3 @@ -48,6 +48,30 @@
1.4 new maps from existing ones.
1.5 */
1.6
1.7 +
1.8 +/**
1.9 +@defgroup graph_maps Graph Maps
1.10 +@ingroup maps
1.11 +\brief Special Graph-Related Maps.
1.12 +
1.13 +These maps are specifically designed to assign values to the nodes and edges of
1.14 +graphs.
1.15 +*/
1.16 +
1.17 +
1.18 +/**
1.19 +\defgroup map_adaptors Map Adaptors
1.20 +\ingroup maps
1.21 +\brief Tools to create new maps from existing ones
1.22 +
1.23 +Map adaptors are used to create "implicit" maps from other maps.
1.24 +
1.25 +Most of them are \ref concept::ReadMap "ReadMap"s. They can
1.26 +make arithmetic oprerations between one or two maps (negation, scalig,
1.27 +addition, multiplication etc.) or e.g. convert a map to another one
1.28 +of different Value type.
1.29 +*/
1.30 +
1.31 /**
1.32 @defgroup auxdat Auxiliary Data Structures
1.33 @ingroup datas
2.1 --- a/src/lemon/Makefile.am Wed May 04 13:07:10 2005 +0000
2.2 +++ b/src/lemon/Makefile.am Thu May 05 11:05:25 2005 +0000
2.3 @@ -54,7 +54,6 @@
2.4 utility.h \
2.5 graph_reader.h \
2.6 graph_writer.h \
2.7 - map_utils.h \
2.8 bits/alteration_notifier.h \
2.9 bits/map_iterator.h \
2.10 bits/array_map.h \
3.1 --- a/src/lemon/bits/map_iterator.h Wed May 04 13:07:10 2005 +0000
3.2 +++ b/src/lemon/bits/map_iterator.h Thu May 05 11:05:25 2005 +0000
3.3 @@ -20,7 +20,7 @@
3.4 #include <iterator>
3.5
3.6 #include <lemon/bits/extended_pair.h>
3.7 -#include <lemon/map_utils.h>
3.8 +#include <lemon/graph_utils.h>
3.9
3.10 ///\ingroup graphmaps
3.11 ///\file
4.1 --- a/src/lemon/graph_utils.h Wed May 04 13:07:10 2005 +0000
4.2 +++ b/src/lemon/graph_utils.h Thu May 05 11:05:25 2005 +0000
4.3 @@ -18,6 +18,7 @@
4.4 #define LEMON_GRAPH_UTILS_H
4.5
4.6 #include <iterator>
4.7 +#include <map>
4.8
4.9 #include <lemon/invalid.h>
4.10 #include <lemon/utility.h>
4.11 @@ -334,7 +335,361 @@
4.12 };
4.13
4.14 /// @}
4.15 +
4.16 + /// \addtogroup graph_maps
4.17 + /// @{
4.18 +
4.19 + /// Provides an immutable and unique id for each item in the graph.
4.20 +
4.21 + /// The IdMap class provides an unique and immutable mapping for each item
4.22 + /// in the graph.
4.23 + ///
4.24 + template <typename _Graph, typename _Item>
4.25 + class IdMap {
4.26 + public:
4.27 + typedef _Graph Graph;
4.28 + typedef int Value;
4.29 + typedef _Item Item;
4.30 + typedef _Item Key;
4.31 +
4.32 + /// \brief The class represents the inverse of the map.
4.33 + ///
4.34 + /// The class represents the inverse of the map.
4.35 + /// \see inverse()
4.36 + class InverseMap {
4.37 + public:
4.38 + /// \brief Constructor.
4.39 + ///
4.40 + /// Constructor for creating an id-to-item map.
4.41 + InverseMap(const Graph& _graph) : graph(&_graph) {}
4.42 + /// \brief Gives back the given item from its id.
4.43 + ///
4.44 + /// Gives back the given item from its id.
4.45 + ///
4.46 + Item operator[](int id) const { return graph->fromId(id, Item());}
4.47 + private:
4.48 + const Graph* graph;
4.49 + };
4.50 +
4.51 + /// \brief Constructor.
4.52 + ///
4.53 + /// Constructor for creating id map.
4.54 + IdMap(const Graph& _graph) : graph(&_graph) {}
4.55 +
4.56 + /// \brief Gives back the \e id of the item.
4.57 + ///
4.58 + /// Gives back the immutable and unique \e id of the map.
4.59 + int operator[](const Item& item) const { return graph->id(item);}
4.60 +
4.61 + /// \brief Gives back the inverse of the map.
4.62 + ///
4.63 + /// Gives back the inverse of the map.
4.64 + InverseMap inverse() const { return InverseMap(*graph);}
4.65 +
4.66 + private:
4.67 + const Graph* graph;
4.68 +
4.69 + };
4.70 +
4.71
4.72 + template <typename Map, typename Enable = void>
4.73 + struct ReferenceMapTraits {
4.74 + typedef typename Map::Value Value;
4.75 + typedef typename Map::Value& Reference;
4.76 + typedef const typename Map::Value& ConstReference;
4.77 + typedef typename Map::Value* Pointer;
4.78 + typedef const typename Map::Value* ConstPointer;
4.79 + };
4.80 +
4.81 + template <typename Map>
4.82 + struct ReferenceMapTraits<
4.83 + Map,
4.84 + typename enable_if<typename Map::FullTypeTag, void>::type
4.85 + > {
4.86 + typedef typename Map::Value Value;
4.87 + typedef typename Map::Reference Reference;
4.88 + typedef typename Map::ConstReference ConstReference;
4.89 + typedef typename Map::Pointer Pointer;
4.90 + typedef typename Map::ConstPointer ConstPointer;
4.91 + };
4.92 +
4.93 + /// \brief General inversable graph-map type.
4.94 +
4.95 + /// This type provides simple inversable map functions.
4.96 + /// The InversableMap wraps an arbitrary ReadWriteMap
4.97 + /// and if a key is setted to a new value then store it
4.98 + /// in the inverse map.
4.99 + /// \param _Graph The graph type.
4.100 + /// \param _Map The map to extend with inversable functionality.
4.101 + template <
4.102 + typename _Graph,
4.103 + typename _Item,
4.104 + typename _Value,
4.105 + typename _Map
4.106 + = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
4.107 + >
4.108 + class InversableMap : protected _Map {
4.109 +
4.110 + public:
4.111 +
4.112 + typedef _Map Map;
4.113 + typedef _Graph Graph;
4.114 + /// The key type of InversableMap (Node, Edge, UndirEdge).
4.115 + typedef typename _Map::Key Key;
4.116 + /// The value type of the InversableMap.
4.117 + typedef typename _Map::Value Value;
4.118 +
4.119 + typedef std::map<Value, Key> InverseMap;
4.120 +
4.121 + typedef typename _Map::ConstReference ConstReference;
4.122 +
4.123 + /// \brief Constructor.
4.124 + ///
4.125 + /// Construct a new InversableMap for the graph.
4.126 + ///
4.127 + InversableMap(const Graph& graph) : Map(graph) {}
4.128 +
4.129 + /// \brief The setter function of the map.
4.130 + ///
4.131 +
4.132 + void set(const Key& key, const Value& val) {
4.133 + Value oldval = Map::operator[](key);
4.134 + typename InverseMap::iterator it = invMap.find(oldval);
4.135 + if (it != invMap.end() && it->second == key) {
4.136 + invMap.erase(it);
4.137 + }
4.138 + invMap.insert(make_pair(val, key));
4.139 + Map::set(key, val);
4.140 + }
4.141 +
4.142 + /// \brief The getter function of the map.
4.143 + ///
4.144 + /// It gives back the value associated with the key.
4.145 + ConstReference operator[](const Key& key) const {
4.146 + return Map::operator[](key);
4.147 + }
4.148 +
4.149 + /// \brief Add a new key to the map.
4.150 + ///
4.151 + /// Add a new key to the map. It is called by the
4.152 + /// \c AlterationNotifier.
4.153 + virtual void add(const Key& key) {
4.154 + Map::add(key);
4.155 + }
4.156 +
4.157 + /// \brief Erase the key from the map.
4.158 + ///
4.159 + /// Erase the key to the map. It is called by the
4.160 + /// \c AlterationNotifier.
4.161 + virtual void erase(const Key& key) {
4.162 + Value val = Map::operator[](key);
4.163 + typename InverseMap::iterator it = invMap.find(val);
4.164 + if (it != invMap.end() && it->second == key) {
4.165 + invMap.erase(it);
4.166 + }
4.167 + Map::erase(key);
4.168 + }
4.169 +
4.170 + /// \brief Clear the keys from the map and inverse map.
4.171 + ///
4.172 + /// Clear the keys from the map and inverse map. It is called by the
4.173 + /// \c AlterationNotifier.
4.174 + virtual void clear() {
4.175 + invMap.clear();
4.176 + Map::clear();
4.177 + }
4.178 +
4.179 + /// \brief It gives back the just readeable inverse map.
4.180 + ///
4.181 + /// It gives back the just readeable inverse map.
4.182 + const InverseMap& inverse() const {
4.183 + return invMap;
4.184 + }
4.185 +
4.186 +
4.187 + private:
4.188 + InverseMap invMap;
4.189 + };
4.190 +
4.191 + /// \brief Provides a mutable, continuous and unique descriptor for each
4.192 + /// item in the graph.
4.193 + ///
4.194 + /// The DescriptorMap class provides a mutable, continuous and immutable
4.195 + /// mapping for each item in the graph.
4.196 + ///
4.197 + /// \param _Graph The graph class the \c DescriptorMap belongs to.
4.198 + /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
4.199 + /// UndirEdge.
4.200 + /// \param _Map A ReadWriteMap mapping from the item type to integer.
4.201 +
4.202 + template <
4.203 + typename _Graph,
4.204 + typename _Item,
4.205 + typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
4.206 + >
4.207 + class DescriptorMap : protected _Map {
4.208 +
4.209 + typedef _Item Item;
4.210 + typedef _Map Map;
4.211 +
4.212 + public:
4.213 + /// The graph class of DescriptorMap.
4.214 + typedef _Graph Graph;
4.215 +
4.216 + /// The key type of DescriptorMap (Node, Edge, UndirEdge).
4.217 + typedef typename _Map::Key Key;
4.218 + /// The value type of DescriptorMap.
4.219 + typedef typename _Map::Value Value;
4.220 +
4.221 + typedef std::vector<Item> InverseMap;
4.222 +
4.223 + /// \brief Constructor.
4.224 + ///
4.225 + /// Constructor for creating descriptor map.
4.226 + DescriptorMap(const Graph& _graph) : Map(_graph) {
4.227 + build();
4.228 + }
4.229 +
4.230 + /// \brief Add a new key to the map.
4.231 + ///
4.232 + /// Add a new key to the map. It is called by the
4.233 + /// \c AlterationNotifier.
4.234 + virtual void add(const Item& item) {
4.235 + Map::add(item);
4.236 + Map::set(item, invMap.size());
4.237 + invMap.push_back(item);
4.238 + }
4.239 +
4.240 + /// \brief Erase the key from the map.
4.241 + ///
4.242 + /// Erase the key to the map. It is called by the
4.243 + /// \c AlterationNotifier.
4.244 + virtual void erase(const Item& item) {
4.245 + Map::set(invMap.back(), Map::operator[](item));
4.246 + invMap[Map::operator[](item)] = invMap.back();
4.247 + Map::erase(item);
4.248 + }
4.249 +
4.250 + /// \brief Build the unique map.
4.251 + ///
4.252 + /// Build the unique map. It is called by the
4.253 + /// \c AlterationNotifier.
4.254 + virtual void build() {
4.255 + Map::build();
4.256 + Item it;
4.257 + const typename Map::Graph* graph = Map::getGraph();
4.258 + for (graph->first(it); it != INVALID; graph->next(it)) {
4.259 + Map::set(it, invMap.size());
4.260 + invMap.push_back(it);
4.261 + }
4.262 + }
4.263 +
4.264 + /// \brief Clear the keys from the map.
4.265 + ///
4.266 + /// Clear the keys from the map. It is called by the
4.267 + /// \c AlterationNotifier.
4.268 + virtual void clear() {
4.269 + invMap.clear();
4.270 + Map::clear();
4.271 + }
4.272 +
4.273 + /// \brief Gives back the \e descriptor of the item.
4.274 + ///
4.275 + /// Gives back the mutable and unique \e descriptor of the map.
4.276 + int operator[](const Item& item) const {
4.277 + return Map::operator[](item);
4.278 + }
4.279 +
4.280 + /// \brief Gives back the inverse of the map.
4.281 + ///
4.282 + /// Gives back the inverse of the map.
4.283 + const InverseMap inverse() const {
4.284 + return invMap;
4.285 + }
4.286 +
4.287 + private:
4.288 + std::vector<Item> invMap;
4.289 + };
4.290 +
4.291 + /// \brief Returns the source of the given edge.
4.292 + ///
4.293 + /// The SourceMap gives back the source Node of the given edge.
4.294 + /// \author Balazs Dezso
4.295 + template <typename Graph>
4.296 + class SourceMap {
4.297 + public:
4.298 + typedef typename Graph::Node Value;
4.299 + typedef typename Graph::Edge Key;
4.300 +
4.301 + /// \brief Constructor
4.302 + ///
4.303 + /// Constructor
4.304 + /// \param _graph The graph that the map belongs to.
4.305 + SourceMap(const Graph& _graph) : graph(_graph) {}
4.306 +
4.307 + /// \brief The subscript operator.
4.308 + ///
4.309 + /// The subscript operator.
4.310 + /// \param edge The edge
4.311 + /// \return The source of the edge
4.312 + Value operator[](const Key& edge) {
4.313 + return graph.source(edge);
4.314 + }
4.315 +
4.316 + private:
4.317 + const Graph& graph;
4.318 + };
4.319 +
4.320 + /// \brief Returns a \ref SourceMap class
4.321 + ///
4.322 + /// This function just returns an \ref SourceMap class.
4.323 + /// \relates SourceMap
4.324 + template <typename Graph>
4.325 + inline SourceMap<Graph> sourceMap(const Graph& graph) {
4.326 + return SourceMap<Graph>(graph);
4.327 + }
4.328 +
4.329 + /// \brief Returns the target of the given edge.
4.330 + ///
4.331 + /// The TargetMap gives back the target Node of the given edge.
4.332 + /// \author Balazs Dezso
4.333 + template <typename Graph>
4.334 + class TargetMap {
4.335 + public:
4.336 + typedef typename Graph::Node Value;
4.337 + typedef typename Graph::Edge Key;
4.338 +
4.339 + /// \brief Constructor
4.340 + ///
4.341 + /// Constructor
4.342 + /// \param _graph The graph that the map belongs to.
4.343 + TargetMap(const Graph& _graph) : graph(_graph) {}
4.344 +
4.345 + /// \brief The subscript operator.
4.346 + ///
4.347 + /// The subscript operator.
4.348 + /// \param edge The edge
4.349 + /// \return The target of the edge
4.350 + Value operator[](const Key& key) {
4.351 + return graph.target(key);
4.352 + }
4.353 +
4.354 + private:
4.355 + const Graph& graph;
4.356 + };
4.357 +
4.358 + /// \brief Returns a \ref TargetMap class
4.359 +
4.360 + /// This function just returns an \ref TargetMap class.
4.361 + /// \relates TargetMap
4.362 + template <typename Graph>
4.363 + inline TargetMap<Graph> targetMap(const Graph& graph) {
4.364 + return TargetMap<Graph>(graph);
4.365 + }
4.366 +
4.367 +
4.368 + /// @}
4.369 +
4.370 } //END OF NAMESPACE LEMON
4.371
4.372 #endif
5.1 --- a/src/lemon/graph_writer.h Wed May 04 13:07:10 2005 +0000
5.2 +++ b/src/lemon/graph_writer.h Thu May 05 11:05:25 2005 +0000
5.3 @@ -29,7 +29,7 @@
5.4
5.5 #include <memory>
5.6
5.7 -#include <lemon/map_utils.h>
5.8 +#include <lemon/graph_utils.h>
5.9
5.10 #include <lemon/invalid.h>
5.11 #include <lemon/error.h>
6.1 --- a/src/lemon/map_utils.h Wed May 04 13:07:10 2005 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,311 +0,0 @@
6.4 -/* -*- C++ -*-
6.5 - * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
6.6 - *
6.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.9 - *
6.10 - * Permission to use, modify and distribute this software is granted
6.11 - * provided that this copyright notice appears in all copies. For
6.12 - * precise terms see the accompanying LICENSE file.
6.13 - *
6.14 - * This software is provided "AS IS" with no warranty of any kind,
6.15 - * express or implied, and with no claim as to its suitability for any
6.16 - * purpose.
6.17 - *
6.18 - */
6.19 -
6.20 -
6.21 -///\ingroup mutils
6.22 -///\file
6.23 -///\brief Map utilities.
6.24 -
6.25 -#ifndef LEMON_MAP_UTILS_H
6.26 -#define LEMON_MAP_UTILS_H
6.27 -
6.28 -#include <map>
6.29 -#include <vector>
6.30 -
6.31 -#include <lemon/graph_utils.h>
6.32 -
6.33 -namespace lemon {
6.34 -
6.35 - /// \addtogroup mutils
6.36 - /// @{
6.37 -
6.38 -
6.39 - template <typename Map, typename Enable = void>
6.40 - struct ReferenceMapTraits {
6.41 - typedef typename Map::Value Value;
6.42 - typedef typename Map::Value& Reference;
6.43 - typedef const typename Map::Value& ConstReference;
6.44 - typedef typename Map::Value* Pointer;
6.45 - typedef const typename Map::Value* ConstPointer;
6.46 - };
6.47 -
6.48 - template <typename Map>
6.49 - struct ReferenceMapTraits<
6.50 - Map,
6.51 - typename enable_if<typename Map::FullTypeTag, void>::type
6.52 - > {
6.53 - typedef typename Map::Value Value;
6.54 - typedef typename Map::Reference Reference;
6.55 - typedef typename Map::ConstReference ConstReference;
6.56 - typedef typename Map::Pointer Pointer;
6.57 - typedef typename Map::ConstPointer ConstPointer;
6.58 - };
6.59 -
6.60 - /// \brief General inversable map type.
6.61 -
6.62 - /// This type provides simple inversable map functions.
6.63 - /// The InversableMap wraps an arbitrary ReadWriteMap
6.64 - /// and if a key is setted to a new value then store it
6.65 - /// in the inverse map.
6.66 - /// \param _Graph The graph type.
6.67 - /// \param _Map The map to extend with inversable functionality.
6.68 - template <
6.69 - typename _Graph,
6.70 - typename _Item,
6.71 - typename _Value,
6.72 - typename _Map
6.73 - = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
6.74 - >
6.75 - class InversableMap : protected _Map {
6.76 -
6.77 - public:
6.78 -
6.79 - typedef _Map Map;
6.80 - typedef _Graph Graph;
6.81 - /// The key type of InversableMap (Node, Edge, UndirEdge).
6.82 - typedef typename _Map::Key Key;
6.83 - /// The value type of the InversableMap.
6.84 - typedef typename _Map::Value Value;
6.85 -
6.86 - typedef std::map<Value, Key> InverseMap;
6.87 -
6.88 - typedef typename _Map::ConstReference ConstReference;
6.89 -
6.90 - /// \brief Constructor.
6.91 - ///
6.92 - /// Construct a new InversableMap for the graph.
6.93 - ///
6.94 - InversableMap(const Graph& graph) : Map(graph) {}
6.95 -
6.96 - /// \brief The setter function of the map.
6.97 - ///
6.98 -
6.99 - void set(const Key& key, const Value& val) {
6.100 - Value oldval = Map::operator[](key);
6.101 - typename InverseMap::iterator it = invMap.find(oldval);
6.102 - if (it != invMap.end() && it->second == key) {
6.103 - invMap.erase(it);
6.104 - }
6.105 - invMap.insert(make_pair(val, key));
6.106 - Map::set(key, val);
6.107 - }
6.108 -
6.109 - /// \brief The getter function of the map.
6.110 - ///
6.111 - /// It gives back the value associated with the key.
6.112 - ConstReference operator[](const Key& key) const {
6.113 - return Map::operator[](key);
6.114 - }
6.115 -
6.116 - /// \brief Add a new key to the map.
6.117 - ///
6.118 - /// Add a new key to the map. It is called by the
6.119 - /// \c AlterationNotifier.
6.120 - virtual void add(const Key& key) {
6.121 - Map::add(key);
6.122 - }
6.123 -
6.124 - /// \brief Erase the key from the map.
6.125 - ///
6.126 - /// Erase the key to the map. It is called by the
6.127 - /// \c AlterationNotifier.
6.128 - virtual void erase(const Key& key) {
6.129 - Value val = Map::operator[](key);
6.130 - typename InverseMap::iterator it = invMap.find(val);
6.131 - if (it != invMap.end() && it->second == key) {
6.132 - invMap.erase(it);
6.133 - }
6.134 - Map::erase(key);
6.135 - }
6.136 -
6.137 - /// \brief Clear the keys from the map and inverse map.
6.138 - ///
6.139 - /// Clear the keys from the map and inverse map. It is called by the
6.140 - /// \c AlterationNotifier.
6.141 - virtual void clear() {
6.142 - invMap.clear();
6.143 - Map::clear();
6.144 - }
6.145 -
6.146 - /// \brief It gives back the just readeable inverse map.
6.147 - ///
6.148 - /// It gives back the just readeable inverse map.
6.149 - const InverseMap& inverse() const {
6.150 - return invMap;
6.151 - }
6.152 -
6.153 -
6.154 - private:
6.155 - InverseMap invMap;
6.156 - };
6.157 -
6.158 -
6.159 -
6.160 - /// \brief Provides a mutable, continous and unique descriptor for each
6.161 - /// item in the graph.
6.162 - ///
6.163 - /// The DescriptorMap class provides a mutable, continous and immutable
6.164 - /// mapping for each item in the graph.
6.165 - ///
6.166 - /// \param _Graph The graph class the \c DescriptorMap belongs to.
6.167 - /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
6.168 - /// UndirEdge.
6.169 - /// \param _Map A ReadWriteMap mapping from the item type to integer.
6.170 -
6.171 - template <
6.172 - typename _Graph,
6.173 - typename _Item,
6.174 - typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
6.175 - >
6.176 - class DescriptorMap : protected _Map {
6.177 -
6.178 - typedef _Item Item;
6.179 - typedef _Map Map;
6.180 -
6.181 - public:
6.182 - /// The graph class of DescriptorMap.
6.183 - typedef _Graph Graph;
6.184 -
6.185 - /// The key type of DescriptorMap (Node, Edge, UndirEdge).
6.186 - typedef typename _Map::Key Key;
6.187 - /// The value type of DescriptorMap.
6.188 - typedef typename _Map::Value Value;
6.189 -
6.190 - typedef std::vector<Item> InverseMap;
6.191 -
6.192 - /// \brief Constructor.
6.193 - ///
6.194 - /// Constructor for creating descriptor map.
6.195 - DescriptorMap(const Graph& _graph) : Map(_graph) {
6.196 - build();
6.197 - }
6.198 -
6.199 - /// \brief Add a new key to the map.
6.200 - ///
6.201 - /// Add a new key to the map. It is called by the
6.202 - /// \c AlterationNotifier.
6.203 - virtual void add(const Item& item) {
6.204 - Map::add(item);
6.205 - Map::set(item, invMap.size());
6.206 - invMap.push_back(item);
6.207 - }
6.208 -
6.209 - /// \brief Erase the key from the map.
6.210 - ///
6.211 - /// Erase the key to the map. It is called by the
6.212 - /// \c AlterationNotifier.
6.213 - virtual void erase(const Item& item) {
6.214 - Map::set(invMap.back(), Map::operator[](item));
6.215 - invMap[Map::operator[](item)] = invMap.back();
6.216 - Map::erase(item);
6.217 - }
6.218 -
6.219 - /// \brief Build the unique map.
6.220 - ///
6.221 - /// Build the unique map. It is called by the
6.222 - /// \c AlterationNotifier.
6.223 - virtual void build() {
6.224 - Map::build();
6.225 - Item it;
6.226 - const typename Map::Graph* graph = Map::getGraph();
6.227 - for (graph->first(it); it != INVALID; graph->next(it)) {
6.228 - Map::set(it, invMap.size());
6.229 - invMap.push_back(it);
6.230 - }
6.231 - }
6.232 -
6.233 - /// \brief Clear the keys from the map.
6.234 - ///
6.235 - /// Clear the keys from the map. It is called by the
6.236 - /// \c AlterationNotifier.
6.237 - virtual void clear() {
6.238 - invMap.clear();
6.239 - Map::clear();
6.240 - }
6.241 -
6.242 - /// \brief Gives back the \e descriptor of the item.
6.243 - ///
6.244 - /// Gives back the mutable and unique \e descriptor of the map.
6.245 - int operator[](const Item& item) const {
6.246 - return Map::operator[](item);
6.247 - }
6.248 -
6.249 - /// \brief Gives back the inverse of the map.
6.250 - ///
6.251 - /// Gives back the inverse of the map.
6.252 - const InverseMap inverse() const {
6.253 - return invMap;
6.254 - }
6.255 -
6.256 - private:
6.257 - std::vector<Item> invMap;
6.258 - };
6.259 -
6.260 - /// Provides an immutable and unique id for each item in the graph.
6.261 -
6.262 - /// The IdMap class provides an unique and immutable mapping for each item
6.263 - /// in the graph.
6.264 - ///
6.265 - template <typename _Graph, typename _Item>
6.266 - class IdMap {
6.267 - public:
6.268 - typedef _Graph Graph;
6.269 - typedef int Value;
6.270 - typedef _Item Item;
6.271 - typedef _Item Key;
6.272 -
6.273 - /// \brief The class represents the inverse of the map.
6.274 - ///
6.275 - /// The class represents the inverse of the map.
6.276 - /// \see inverse()
6.277 - class InverseMap {
6.278 - public:
6.279 - /// \brief Constructor.
6.280 - ///
6.281 - /// Constructor for creating an id-to-item map.
6.282 - InverseMap(const Graph& _graph) : graph(&_graph) {}
6.283 - /// \brief Gives back the given item from its id.
6.284 - ///
6.285 - /// Gives back the given item from its id.
6.286 - ///
6.287 - Item operator[](int id) const { return graph->fromId(id, Item());}
6.288 - private:
6.289 - const Graph* graph;
6.290 - };
6.291 -
6.292 - /// \brief Constructor.
6.293 - ///
6.294 - /// Constructor for creating id map.
6.295 - IdMap(const Graph& _graph) : graph(&_graph) {}
6.296 -
6.297 - /// \brief Gives back the \e id of the item.
6.298 - ///
6.299 - /// Gives back the immutable and unique \e id of the map.
6.300 - int operator[](const Item& item) const { return graph->id(item);}
6.301 -
6.302 - /// \brief Gives back the inverse of the map.
6.303 - ///
6.304 - /// Gives back the inverse of the map.
6.305 - InverseMap inverse() const { return InverseMap(*graph);}
6.306 -
6.307 - private:
6.308 - const Graph* graph;
6.309 -
6.310 - };
6.311 -
6.312 -}
6.313 -
6.314 -#endif
7.1 --- a/src/lemon/maps.h Wed May 04 13:07:10 2005 +0000
7.2 +++ b/src/lemon/maps.h Thu May 05 11:05:25 2005 +0000
7.3 @@ -17,7 +17,6 @@
7.4 #ifndef LEMON_MAPS_H
7.5 #define LEMON_MAPS_H
7.6
7.7 -#include<math.h>
7.8
7.9 ///\file
7.10 ///\ingroup maps
7.11 @@ -186,6 +185,12 @@
7.12 };
7.13 };
7.14
7.15 + /// @}
7.16 +
7.17 + /// \addtogroup map_adaptors
7.18 + /// @{
7.19 +
7.20 +
7.21 ///Convert the \c Value of a maps to another type.
7.22
7.23 ///This \ref concept::ReadMap "read only map"
7.24 @@ -236,82 +241,6 @@
7.25 return ConvertMap<M,T>(m);
7.26 }
7.27
7.28 - /// \brief Returns the source of the given edge.
7.29 - ///
7.30 - /// The SourceMap gives back the source Node of the given edge.
7.31 - /// \author Balazs Dezso
7.32 - template <typename Graph>
7.33 - class SourceMap {
7.34 - public:
7.35 - typedef typename Graph::Node Value;
7.36 - typedef typename Graph::Edge Key;
7.37 -
7.38 - /// \brief Constructor
7.39 - ///
7.40 - /// Constructor
7.41 - /// \param _graph The graph that the map belongs to.
7.42 - SourceMap(const Graph& _graph) : graph(_graph) {}
7.43 -
7.44 - /// \brief The subscript operator.
7.45 - ///
7.46 - /// The subscript operator.
7.47 - /// \param edge The edge
7.48 - /// \return The source of the edge
7.49 - Value operator[](const Key& edge) {
7.50 - return graph.source(edge);
7.51 - }
7.52 -
7.53 - private:
7.54 - const Graph& graph;
7.55 - };
7.56 -
7.57 - /// \brief Returns a \ref SourceMap class
7.58 -
7.59 - /// This function just returns an \ref SourceMap class.
7.60 - /// \relates SourceMap
7.61 - template <typename Graph>
7.62 - inline SourceMap<Graph> sourceMap(const Graph& graph) {
7.63 - return SourceMap<Graph>(graph);
7.64 - }
7.65 -
7.66 - /// \brief Returns the target of the given edge.
7.67 - ///
7.68 - /// The TargetMap gives back the target Node of the given edge.
7.69 - /// \author Balazs Dezso
7.70 - template <typename Graph>
7.71 - class TargetMap {
7.72 - public:
7.73 - typedef typename Graph::Node Value;
7.74 - typedef typename Graph::Edge Key;
7.75 -
7.76 - /// \brief Constructor
7.77 - ///
7.78 - /// Constructor
7.79 - /// \param _graph The graph that the map belongs to.
7.80 - TargetMap(const Graph& _graph) : graph(_graph) {}
7.81 -
7.82 - /// \brief The subscript operator.
7.83 - ///
7.84 - /// The subscript operator.
7.85 - /// \param edge The edge
7.86 - /// \return The target of the edge
7.87 - Value operator[](const Key& key) {
7.88 - return graph.target(key);
7.89 - }
7.90 -
7.91 - private:
7.92 - const Graph& graph;
7.93 - };
7.94 -
7.95 - /// \brief Returns a \ref TargetMap class
7.96 -
7.97 - /// This function just returns an \ref TargetMap class.
7.98 - /// \relates TargetMap
7.99 - template <typename Graph>
7.100 - inline TargetMap<Graph> targetMap(const Graph& graph) {
7.101 - return TargetMap<Graph>(graph);
7.102 - }
7.103 -
7.104 ///Sum of two maps
7.105
7.106 ///This \ref concept::ReadMap "read only map" returns the sum of the two
7.107 @@ -732,7 +661,7 @@
7.108 return AbsMap<M>(m);
7.109 }
7.110
7.111 - ///Converts an STL style functor to a a map
7.112 + ///Converts an STL style functor to a map
7.113
7.114 ///This \ref concept::ReadMap "read only map" returns the value
7.115 ///of a