# HG changeset patch # User alpar # Date 1115291125 0 # Node ID 655d8e78454d0638ee47c49bfbd01c1f1e863d77 # Parent 9588dcef67938101f6964f58c24108d0baecf909 Special maps' placement in the headers and in the doxigen modules reorganized diff -r 9588dcef6793 -r 655d8e78454d doc/groups.dox --- a/doc/groups.dox Wed May 04 13:07:10 2005 +0000 +++ b/doc/groups.dox Thu May 05 11:05:25 2005 +0000 @@ -48,6 +48,30 @@ new maps from existing ones. */ + +/** +@defgroup graph_maps Graph Maps +@ingroup maps +\brief Special Graph-Related Maps. + +These maps are specifically designed to assign values to the nodes and edges of +graphs. +*/ + + +/** +\defgroup map_adaptors Map Adaptors +\ingroup maps +\brief Tools to create new maps from existing ones + +Map adaptors are used to create "implicit" maps from other maps. + +Most of them are \ref concept::ReadMap "ReadMap"s. They can +make arithmetic oprerations between one or two maps (negation, scalig, +addition, multiplication etc.) or e.g. convert a map to another one +of different Value type. +*/ + /** @defgroup auxdat Auxiliary Data Structures @ingroup datas diff -r 9588dcef6793 -r 655d8e78454d src/lemon/Makefile.am --- a/src/lemon/Makefile.am Wed May 04 13:07:10 2005 +0000 +++ b/src/lemon/Makefile.am Thu May 05 11:05:25 2005 +0000 @@ -54,7 +54,6 @@ utility.h \ graph_reader.h \ graph_writer.h \ - map_utils.h \ bits/alteration_notifier.h \ bits/map_iterator.h \ bits/array_map.h \ diff -r 9588dcef6793 -r 655d8e78454d src/lemon/bits/map_iterator.h --- a/src/lemon/bits/map_iterator.h Wed May 04 13:07:10 2005 +0000 +++ b/src/lemon/bits/map_iterator.h Thu May 05 11:05:25 2005 +0000 @@ -20,7 +20,7 @@ #include #include -#include +#include ///\ingroup graphmaps ///\file diff -r 9588dcef6793 -r 655d8e78454d src/lemon/graph_utils.h --- a/src/lemon/graph_utils.h Wed May 04 13:07:10 2005 +0000 +++ b/src/lemon/graph_utils.h Thu May 05 11:05:25 2005 +0000 @@ -18,6 +18,7 @@ #define LEMON_GRAPH_UTILS_H #include +#include #include #include @@ -334,7 +335,361 @@ }; /// @} + + /// \addtogroup graph_maps + /// @{ + + /// Provides an immutable and unique id for each item in the graph. + + /// The IdMap class provides an unique and immutable mapping for each item + /// in the graph. + /// + template + class IdMap { + public: + typedef _Graph Graph; + typedef int Value; + typedef _Item Item; + typedef _Item Key; + + /// \brief The class represents the inverse of the map. + /// + /// The class represents the inverse of the map. + /// \see inverse() + class InverseMap { + public: + /// \brief Constructor. + /// + /// Constructor for creating an id-to-item map. + InverseMap(const Graph& _graph) : graph(&_graph) {} + /// \brief Gives back the given item from its id. + /// + /// Gives back the given item from its id. + /// + Item operator[](int id) const { return graph->fromId(id, Item());} + private: + const Graph* graph; + }; + + /// \brief Constructor. + /// + /// Constructor for creating id map. + IdMap(const Graph& _graph) : graph(&_graph) {} + + /// \brief Gives back the \e id of the item. + /// + /// Gives back the immutable and unique \e id of the map. + int operator[](const Item& item) const { return graph->id(item);} + + /// \brief Gives back the inverse of the map. + /// + /// Gives back the inverse of the map. + InverseMap inverse() const { return InverseMap(*graph);} + + private: + const Graph* graph; + + }; + + template + struct ReferenceMapTraits { + typedef typename Map::Value Value; + typedef typename Map::Value& Reference; + typedef const typename Map::Value& ConstReference; + typedef typename Map::Value* Pointer; + typedef const typename Map::Value* ConstPointer; + }; + + template + struct ReferenceMapTraits< + Map, + typename enable_if::type + > { + typedef typename Map::Value Value; + typedef typename Map::Reference Reference; + typedef typename Map::ConstReference ConstReference; + typedef typename Map::Pointer Pointer; + typedef typename Map::ConstPointer ConstPointer; + }; + + /// \brief General inversable graph-map type. + + /// This type provides simple inversable map functions. + /// The InversableMap wraps an arbitrary ReadWriteMap + /// and if a key is setted to a new value then store it + /// in the inverse map. + /// \param _Graph The graph type. + /// \param _Map The map to extend with inversable functionality. + template < + typename _Graph, + typename _Item, + typename _Value, + typename _Map + = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> + > + class InversableMap : protected _Map { + + public: + + typedef _Map Map; + typedef _Graph Graph; + /// The key type of InversableMap (Node, Edge, UndirEdge). + typedef typename _Map::Key Key; + /// The value type of the InversableMap. + typedef typename _Map::Value Value; + + typedef std::map InverseMap; + + typedef typename _Map::ConstReference ConstReference; + + /// \brief Constructor. + /// + /// Construct a new InversableMap for the graph. + /// + InversableMap(const Graph& graph) : Map(graph) {} + + /// \brief The setter function of the map. + /// + + void set(const Key& key, const Value& val) { + Value oldval = Map::operator[](key); + typename InverseMap::iterator it = invMap.find(oldval); + if (it != invMap.end() && it->second == key) { + invMap.erase(it); + } + invMap.insert(make_pair(val, key)); + Map::set(key, val); + } + + /// \brief The getter function of the map. + /// + /// It gives back the value associated with the key. + ConstReference operator[](const Key& key) const { + return Map::operator[](key); + } + + /// \brief Add a new key to the map. + /// + /// Add a new key to the map. It is called by the + /// \c AlterationNotifier. + virtual void add(const Key& key) { + Map::add(key); + } + + /// \brief Erase the key from the map. + /// + /// Erase the key to the map. It is called by the + /// \c AlterationNotifier. + virtual void erase(const Key& key) { + Value val = Map::operator[](key); + typename InverseMap::iterator it = invMap.find(val); + if (it != invMap.end() && it->second == key) { + invMap.erase(it); + } + Map::erase(key); + } + + /// \brief Clear the keys from the map and inverse map. + /// + /// Clear the keys from the map and inverse map. It is called by the + /// \c AlterationNotifier. + virtual void clear() { + invMap.clear(); + Map::clear(); + } + + /// \brief It gives back the just readeable inverse map. + /// + /// It gives back the just readeable inverse map. + const InverseMap& inverse() const { + return invMap; + } + + + private: + InverseMap invMap; + }; + + /// \brief Provides a mutable, continuous and unique descriptor for each + /// item in the graph. + /// + /// The DescriptorMap class provides a mutable, continuous and immutable + /// mapping for each item in the graph. + /// + /// \param _Graph The graph class the \c DescriptorMap belongs to. + /// \param _Item The Item is the Key of the Map. It may be Node, Edge or + /// UndirEdge. + /// \param _Map A ReadWriteMap mapping from the item type to integer. + + template < + typename _Graph, + typename _Item, + typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map + > + class DescriptorMap : protected _Map { + + typedef _Item Item; + typedef _Map Map; + + public: + /// The graph class of DescriptorMap. + typedef _Graph Graph; + + /// The key type of DescriptorMap (Node, Edge, UndirEdge). + typedef typename _Map::Key Key; + /// The value type of DescriptorMap. + typedef typename _Map::Value Value; + + typedef std::vector InverseMap; + + /// \brief Constructor. + /// + /// Constructor for creating descriptor map. + DescriptorMap(const Graph& _graph) : Map(_graph) { + build(); + } + + /// \brief Add a new key to the map. + /// + /// Add a new key to the map. It is called by the + /// \c AlterationNotifier. + virtual void add(const Item& item) { + Map::add(item); + Map::set(item, invMap.size()); + invMap.push_back(item); + } + + /// \brief Erase the key from the map. + /// + /// Erase the key to the map. It is called by the + /// \c AlterationNotifier. + virtual void erase(const Item& item) { + Map::set(invMap.back(), Map::operator[](item)); + invMap[Map::operator[](item)] = invMap.back(); + Map::erase(item); + } + + /// \brief Build the unique map. + /// + /// Build the unique map. It is called by the + /// \c AlterationNotifier. + virtual void build() { + Map::build(); + Item it; + const typename Map::Graph* graph = Map::getGraph(); + for (graph->first(it); it != INVALID; graph->next(it)) { + Map::set(it, invMap.size()); + invMap.push_back(it); + } + } + + /// \brief Clear the keys from the map. + /// + /// Clear the keys from the map. It is called by the + /// \c AlterationNotifier. + virtual void clear() { + invMap.clear(); + Map::clear(); + } + + /// \brief Gives back the \e descriptor of the item. + /// + /// Gives back the mutable and unique \e descriptor of the map. + int operator[](const Item& item) const { + return Map::operator[](item); + } + + /// \brief Gives back the inverse of the map. + /// + /// Gives back the inverse of the map. + const InverseMap inverse() const { + return invMap; + } + + private: + std::vector invMap; + }; + + /// \brief Returns the source of the given edge. + /// + /// The SourceMap gives back the source Node of the given edge. + /// \author Balazs Dezso + template + class SourceMap { + public: + typedef typename Graph::Node Value; + typedef typename Graph::Edge Key; + + /// \brief Constructor + /// + /// Constructor + /// \param _graph The graph that the map belongs to. + SourceMap(const Graph& _graph) : graph(_graph) {} + + /// \brief The subscript operator. + /// + /// The subscript operator. + /// \param edge The edge + /// \return The source of the edge + Value operator[](const Key& edge) { + return graph.source(edge); + } + + private: + const Graph& graph; + }; + + /// \brief Returns a \ref SourceMap class + /// + /// This function just returns an \ref SourceMap class. + /// \relates SourceMap + template + inline SourceMap sourceMap(const Graph& graph) { + return SourceMap(graph); + } + + /// \brief Returns the target of the given edge. + /// + /// The TargetMap gives back the target Node of the given edge. + /// \author Balazs Dezso + template + class TargetMap { + public: + typedef typename Graph::Node Value; + typedef typename Graph::Edge Key; + + /// \brief Constructor + /// + /// Constructor + /// \param _graph The graph that the map belongs to. + TargetMap(const Graph& _graph) : graph(_graph) {} + + /// \brief The subscript operator. + /// + /// The subscript operator. + /// \param edge The edge + /// \return The target of the edge + Value operator[](const Key& key) { + return graph.target(key); + } + + private: + const Graph& graph; + }; + + /// \brief Returns a \ref TargetMap class + + /// This function just returns an \ref TargetMap class. + /// \relates TargetMap + template + inline TargetMap targetMap(const Graph& graph) { + return TargetMap(graph); + } + + + /// @} + } //END OF NAMESPACE LEMON #endif diff -r 9588dcef6793 -r 655d8e78454d src/lemon/graph_writer.h --- a/src/lemon/graph_writer.h Wed May 04 13:07:10 2005 +0000 +++ b/src/lemon/graph_writer.h Thu May 05 11:05:25 2005 +0000 @@ -29,7 +29,7 @@ #include -#include +#include #include #include diff -r 9588dcef6793 -r 655d8e78454d src/lemon/map_utils.h --- a/src/lemon/map_utils.h Wed May 04 13:07:10 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,311 +0,0 @@ -/* -*- C++ -*- - * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - - -///\ingroup mutils -///\file -///\brief Map utilities. - -#ifndef LEMON_MAP_UTILS_H -#define LEMON_MAP_UTILS_H - -#include -#include - -#include - -namespace lemon { - - /// \addtogroup mutils - /// @{ - - - template - struct ReferenceMapTraits { - typedef typename Map::Value Value; - typedef typename Map::Value& Reference; - typedef const typename Map::Value& ConstReference; - typedef typename Map::Value* Pointer; - typedef const typename Map::Value* ConstPointer; - }; - - template - struct ReferenceMapTraits< - Map, - typename enable_if::type - > { - typedef typename Map::Value Value; - typedef typename Map::Reference Reference; - typedef typename Map::ConstReference ConstReference; - typedef typename Map::Pointer Pointer; - typedef typename Map::ConstPointer ConstPointer; - }; - - /// \brief General inversable map type. - - /// This type provides simple inversable map functions. - /// The InversableMap wraps an arbitrary ReadWriteMap - /// and if a key is setted to a new value then store it - /// in the inverse map. - /// \param _Graph The graph type. - /// \param _Map The map to extend with inversable functionality. - template < - typename _Graph, - typename _Item, - typename _Value, - typename _Map - = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> - > - class InversableMap : protected _Map { - - public: - - typedef _Map Map; - typedef _Graph Graph; - /// The key type of InversableMap (Node, Edge, UndirEdge). - typedef typename _Map::Key Key; - /// The value type of the InversableMap. - typedef typename _Map::Value Value; - - typedef std::map InverseMap; - - typedef typename _Map::ConstReference ConstReference; - - /// \brief Constructor. - /// - /// Construct a new InversableMap for the graph. - /// - InversableMap(const Graph& graph) : Map(graph) {} - - /// \brief The setter function of the map. - /// - - void set(const Key& key, const Value& val) { - Value oldval = Map::operator[](key); - typename InverseMap::iterator it = invMap.find(oldval); - if (it != invMap.end() && it->second == key) { - invMap.erase(it); - } - invMap.insert(make_pair(val, key)); - Map::set(key, val); - } - - /// \brief The getter function of the map. - /// - /// It gives back the value associated with the key. - ConstReference operator[](const Key& key) const { - return Map::operator[](key); - } - - /// \brief Add a new key to the map. - /// - /// Add a new key to the map. It is called by the - /// \c AlterationNotifier. - virtual void add(const Key& key) { - Map::add(key); - } - - /// \brief Erase the key from the map. - /// - /// Erase the key to the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const Key& key) { - Value val = Map::operator[](key); - typename InverseMap::iterator it = invMap.find(val); - if (it != invMap.end() && it->second == key) { - invMap.erase(it); - } - Map::erase(key); - } - - /// \brief Clear the keys from the map and inverse map. - /// - /// Clear the keys from the map and inverse map. It is called by the - /// \c AlterationNotifier. - virtual void clear() { - invMap.clear(); - Map::clear(); - } - - /// \brief It gives back the just readeable inverse map. - /// - /// It gives back the just readeable inverse map. - const InverseMap& inverse() const { - return invMap; - } - - - private: - InverseMap invMap; - }; - - - - /// \brief Provides a mutable, continous and unique descriptor for each - /// item in the graph. - /// - /// The DescriptorMap class provides a mutable, continous and immutable - /// mapping for each item in the graph. - /// - /// \param _Graph The graph class the \c DescriptorMap belongs to. - /// \param _Item The Item is the Key of the Map. It may be Node, Edge or - /// UndirEdge. - /// \param _Map A ReadWriteMap mapping from the item type to integer. - - template < - typename _Graph, - typename _Item, - typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map - > - class DescriptorMap : protected _Map { - - typedef _Item Item; - typedef _Map Map; - - public: - /// The graph class of DescriptorMap. - typedef _Graph Graph; - - /// The key type of DescriptorMap (Node, Edge, UndirEdge). - typedef typename _Map::Key Key; - /// The value type of DescriptorMap. - typedef typename _Map::Value Value; - - typedef std::vector InverseMap; - - /// \brief Constructor. - /// - /// Constructor for creating descriptor map. - DescriptorMap(const Graph& _graph) : Map(_graph) { - build(); - } - - /// \brief Add a new key to the map. - /// - /// Add a new key to the map. It is called by the - /// \c AlterationNotifier. - virtual void add(const Item& item) { - Map::add(item); - Map::set(item, invMap.size()); - invMap.push_back(item); - } - - /// \brief Erase the key from the map. - /// - /// Erase the key to the map. It is called by the - /// \c AlterationNotifier. - virtual void erase(const Item& item) { - Map::set(invMap.back(), Map::operator[](item)); - invMap[Map::operator[](item)] = invMap.back(); - Map::erase(item); - } - - /// \brief Build the unique map. - /// - /// Build the unique map. It is called by the - /// \c AlterationNotifier. - virtual void build() { - Map::build(); - Item it; - const typename Map::Graph* graph = Map::getGraph(); - for (graph->first(it); it != INVALID; graph->next(it)) { - Map::set(it, invMap.size()); - invMap.push_back(it); - } - } - - /// \brief Clear the keys from the map. - /// - /// Clear the keys from the map. It is called by the - /// \c AlterationNotifier. - virtual void clear() { - invMap.clear(); - Map::clear(); - } - - /// \brief Gives back the \e descriptor of the item. - /// - /// Gives back the mutable and unique \e descriptor of the map. - int operator[](const Item& item) const { - return Map::operator[](item); - } - - /// \brief Gives back the inverse of the map. - /// - /// Gives back the inverse of the map. - const InverseMap inverse() const { - return invMap; - } - - private: - std::vector invMap; - }; - - /// Provides an immutable and unique id for each item in the graph. - - /// The IdMap class provides an unique and immutable mapping for each item - /// in the graph. - /// - template - class IdMap { - public: - typedef _Graph Graph; - typedef int Value; - typedef _Item Item; - typedef _Item Key; - - /// \brief The class represents the inverse of the map. - /// - /// The class represents the inverse of the map. - /// \see inverse() - class InverseMap { - public: - /// \brief Constructor. - /// - /// Constructor for creating an id-to-item map. - InverseMap(const Graph& _graph) : graph(&_graph) {} - /// \brief Gives back the given item from its id. - /// - /// Gives back the given item from its id. - /// - Item operator[](int id) const { return graph->fromId(id, Item());} - private: - const Graph* graph; - }; - - /// \brief Constructor. - /// - /// Constructor for creating id map. - IdMap(const Graph& _graph) : graph(&_graph) {} - - /// \brief Gives back the \e id of the item. - /// - /// Gives back the immutable and unique \e id of the map. - int operator[](const Item& item) const { return graph->id(item);} - - /// \brief Gives back the inverse of the map. - /// - /// Gives back the inverse of the map. - InverseMap inverse() const { return InverseMap(*graph);} - - private: - const Graph* graph; - - }; - -} - -#endif diff -r 9588dcef6793 -r 655d8e78454d src/lemon/maps.h --- a/src/lemon/maps.h Wed May 04 13:07:10 2005 +0000 +++ b/src/lemon/maps.h Thu May 05 11:05:25 2005 +0000 @@ -17,7 +17,6 @@ #ifndef LEMON_MAPS_H #define LEMON_MAPS_H -#include ///\file ///\ingroup maps @@ -186,6 +185,12 @@ }; }; + /// @} + + /// \addtogroup map_adaptors + /// @{ + + ///Convert the \c Value of a maps to another type. ///This \ref concept::ReadMap "read only map" @@ -236,82 +241,6 @@ return ConvertMap(m); } - /// \brief Returns the source of the given edge. - /// - /// The SourceMap gives back the source Node of the given edge. - /// \author Balazs Dezso - template - class SourceMap { - public: - typedef typename Graph::Node Value; - typedef typename Graph::Edge Key; - - /// \brief Constructor - /// - /// Constructor - /// \param _graph The graph that the map belongs to. - SourceMap(const Graph& _graph) : graph(_graph) {} - - /// \brief The subscript operator. - /// - /// The subscript operator. - /// \param edge The edge - /// \return The source of the edge - Value operator[](const Key& edge) { - return graph.source(edge); - } - - private: - const Graph& graph; - }; - - /// \brief Returns a \ref SourceMap class - - /// This function just returns an \ref SourceMap class. - /// \relates SourceMap - template - inline SourceMap sourceMap(const Graph& graph) { - return SourceMap(graph); - } - - /// \brief Returns the target of the given edge. - /// - /// The TargetMap gives back the target Node of the given edge. - /// \author Balazs Dezso - template - class TargetMap { - public: - typedef typename Graph::Node Value; - typedef typename Graph::Edge Key; - - /// \brief Constructor - /// - /// Constructor - /// \param _graph The graph that the map belongs to. - TargetMap(const Graph& _graph) : graph(_graph) {} - - /// \brief The subscript operator. - /// - /// The subscript operator. - /// \param edge The edge - /// \return The target of the edge - Value operator[](const Key& key) { - return graph.target(key); - } - - private: - const Graph& graph; - }; - - /// \brief Returns a \ref TargetMap class - - /// This function just returns an \ref TargetMap class. - /// \relates TargetMap - template - inline TargetMap targetMap(const Graph& graph) { - return TargetMap(graph); - } - ///Sum of two maps ///This \ref concept::ReadMap "read only map" returns the sum of the two @@ -732,7 +661,7 @@ return AbsMap(m); } - ///Converts an STL style functor to a a map + ///Converts an STL style functor to a map ///This \ref concept::ReadMap "read only map" returns the value ///of a