COIN-OR::LEMON - Graph Library

Changeset 1402:655d8e78454d in lemon-0.x


Ignore:
Timestamp:
05/05/05 13:05:25 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1864
Message:

Special maps' placement in the headers and in the doxigen modules
reorganized

Files:
1 deleted
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1401 r1402  
    4747LEMON provides several special maps that e.g. combine
    4848new maps from existing ones.
     49*/
     50
     51
     52/**
     53@defgroup graph_maps Graph Maps
     54@ingroup maps
     55\brief Special Graph-Related Maps.
     56
     57These maps are specifically designed to assign values to the nodes and edges of
     58graphs.
     59*/
     60
     61
     62/**
     63\defgroup map_adaptors Map Adaptors
     64\ingroup maps
     65\brief Tools to create new maps from existing ones
     66
     67Map adaptors are used to create "implicit" maps from other maps.
     68
     69Most of them are \ref concept::ReadMap "ReadMap"s. They can
     70make arithmetic oprerations between one or two maps (negation, scalig,
     71addition, multiplication etc.) or e.g. convert a map to another one
     72of different Value type.
    4973*/
    5074
  • src/lemon/Makefile.am

    r1401 r1402  
    5555        graph_reader.h \
    5656        graph_writer.h \
    57         map_utils.h \
    5857        bits/alteration_notifier.h \
    5958        bits/map_iterator.h \
  • src/lemon/bits/map_iterator.h

    r1359 r1402  
    2121
    2222#include <lemon/bits/extended_pair.h>
    23 #include <lemon/map_utils.h>
     23#include <lemon/graph_utils.h>
    2424
    2525///\ingroup graphmaps
  • src/lemon/graph_utils.h

    r1359 r1402  
    1919
    2020#include <iterator>
     21#include <map>
    2122
    2223#include <lemon/invalid.h>
     
    335336
    336337  /// @}
     338
     339  /// \addtogroup graph_maps
     340  /// @{
     341
     342  /// Provides an immutable and unique id for each item in the graph.
     343
     344  /// The IdMap class provides an unique and immutable mapping for each item
     345  /// in the graph.
     346  ///
     347  template <typename _Graph, typename _Item>
     348  class IdMap {
     349  public:
     350    typedef _Graph Graph;
     351    typedef int Value;
     352    typedef _Item Item;
     353    typedef _Item Key;
     354
     355    /// \brief The class represents the inverse of the map.
     356    ///
     357    /// The class represents the inverse of the map.
     358    /// \see inverse()
     359    class InverseMap {
     360    public:
     361      /// \brief Constructor.
     362      ///
     363      /// Constructor for creating an id-to-item map.
     364      InverseMap(const Graph& _graph) : graph(&_graph) {}
     365      /// \brief Gives back the given item from its id.
     366      ///
     367      /// Gives back the given item from its id.
     368      ///
     369      Item operator[](int id) const { return graph->fromId(id, Item());}
     370    private:
     371      const Graph* graph;
     372    };
     373
     374    /// \brief Constructor.
     375    ///
     376    /// Constructor for creating id map.
     377    IdMap(const Graph& _graph) : graph(&_graph) {}
     378
     379    /// \brief Gives back the \e id of the item.
     380    ///
     381    /// Gives back the immutable and unique \e id of the map.
     382    int operator[](const Item& item) const { return graph->id(item);}
     383
     384    /// \brief Gives back the inverse of the map.
     385    ///
     386    /// Gives back the inverse of the map.
     387    InverseMap inverse() const { return InverseMap(*graph);}
     388
     389  private:
     390    const Graph* graph;
     391
     392  };
     393
    337394 
     395  template <typename Map, typename Enable = void>
     396  struct ReferenceMapTraits {
     397    typedef typename Map::Value Value;
     398    typedef typename Map::Value& Reference;
     399    typedef const typename Map::Value& ConstReference;
     400    typedef typename Map::Value* Pointer;
     401    typedef const typename Map::Value* ConstPointer;
     402  };
     403
     404  template <typename Map>
     405  struct ReferenceMapTraits<
     406    Map,
     407    typename enable_if<typename Map::FullTypeTag, void>::type
     408  > {
     409    typedef typename Map::Value Value;
     410    typedef typename Map::Reference Reference;
     411    typedef typename Map::ConstReference ConstReference;
     412    typedef typename Map::Pointer Pointer;
     413    typedef typename Map::ConstPointer ConstPointer;
     414  };
     415
     416  /// \brief General inversable graph-map type.
     417
     418  /// This type provides simple inversable map functions.
     419  /// The InversableMap wraps an arbitrary ReadWriteMap
     420  /// and if a key is setted to a new value then store it
     421  /// in the inverse map.
     422  /// \param _Graph The graph type.
     423  /// \param _Map The map to extend with inversable functionality.
     424  template <
     425    typename _Graph,
     426    typename _Item,
     427    typename _Value,
     428    typename _Map
     429    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
     430  >
     431  class InversableMap : protected _Map {
     432
     433  public:
     434 
     435    typedef _Map Map;
     436    typedef _Graph Graph;
     437   /// The key type of InversableMap (Node, Edge, UndirEdge).
     438    typedef typename _Map::Key Key;
     439    /// The value type of the InversableMap.
     440    typedef typename _Map::Value Value;
     441
     442    typedef std::map<Value, Key> InverseMap;
     443   
     444    typedef typename _Map::ConstReference ConstReference;
     445
     446    /// \brief Constructor.
     447    ///
     448    /// Construct a new InversableMap for the graph.
     449    ///
     450    InversableMap(const Graph& graph) : Map(graph) {}
     451   
     452    /// \brief The setter function of the map.
     453    ///
     454
     455    void set(const Key& key, const Value& val) {
     456      Value oldval = Map::operator[](key);
     457      typename InverseMap::iterator it = invMap.find(oldval);
     458      if (it != invMap.end() && it->second == key) {
     459        invMap.erase(it);
     460      }     
     461      invMap.insert(make_pair(val, key));
     462      Map::set(key, val);
     463    }
     464
     465    /// \brief The getter function of the map.
     466    ///
     467    /// It gives back the value associated with the key.
     468    ConstReference operator[](const Key& key) const {
     469      return Map::operator[](key);
     470    }
     471
     472    /// \brief Add a new key to the map.
     473    ///
     474    /// Add a new key to the map. It is called by the
     475    /// \c AlterationNotifier.
     476    virtual void add(const Key& key) {
     477      Map::add(key);
     478    }
     479
     480    /// \brief Erase the key from the map.
     481    ///
     482    /// Erase the key to the map. It is called by the
     483    /// \c AlterationNotifier.
     484    virtual void erase(const Key& key) {
     485      Value val = Map::operator[](key);
     486      typename InverseMap::iterator it = invMap.find(val);
     487      if (it != invMap.end() && it->second == key) {
     488        invMap.erase(it);
     489      }
     490      Map::erase(key);
     491    }
     492
     493    /// \brief Clear the keys from the map and inverse map.
     494    ///
     495    /// Clear the keys from the map and inverse map. It is called by the
     496    /// \c AlterationNotifier.
     497    virtual void clear() {
     498      invMap.clear();
     499      Map::clear();
     500    }
     501
     502    /// \brief It gives back the just readeable inverse map.
     503    ///
     504    /// It gives back the just readeable inverse map.
     505    const InverseMap& inverse() const {
     506      return invMap;
     507    }
     508
     509
     510  private:
     511    InverseMap invMap;   
     512  };
     513
     514  /// \brief Provides a mutable, continuous and unique descriptor for each
     515  /// item in the graph.
     516  ///
     517  /// The DescriptorMap class provides a mutable, continuous and immutable
     518  /// mapping for each item in the graph.
     519  ///
     520  /// \param _Graph The graph class the \c DescriptorMap belongs to.
     521  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
     522  /// UndirEdge.
     523  /// \param _Map A ReadWriteMap mapping from the item type to integer.
     524
     525  template <
     526    typename _Graph,   
     527    typename _Item,
     528    typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
     529  >
     530  class DescriptorMap : protected _Map {
     531
     532    typedef _Item Item;
     533    typedef _Map Map;
     534
     535  public:
     536    /// The graph class of DescriptorMap.
     537    typedef _Graph Graph;
     538
     539    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
     540    typedef typename _Map::Key Key;
     541    /// The value type of DescriptorMap.
     542    typedef typename _Map::Value Value;
     543
     544    typedef std::vector<Item> InverseMap;
     545
     546    /// \brief Constructor.
     547    ///
     548    /// Constructor for creating descriptor map.
     549    DescriptorMap(const Graph& _graph) : Map(_graph) {
     550      build();
     551    }
     552
     553    /// \brief Add a new key to the map.
     554    ///
     555    /// Add a new key to the map. It is called by the
     556    /// \c AlterationNotifier.
     557    virtual void add(const Item& item) {
     558      Map::add(item);
     559      Map::set(item, invMap.size());
     560      invMap.push_back(item);
     561    }
     562
     563    /// \brief Erase the key from the map.
     564    ///
     565    /// Erase the key to the map. It is called by the
     566    /// \c AlterationNotifier.
     567    virtual void erase(const Item& item) {
     568      Map::set(invMap.back(), Map::operator[](item));
     569      invMap[Map::operator[](item)] = invMap.back();
     570      Map::erase(item);
     571    }
     572
     573    /// \brief Build the unique map.
     574    ///
     575    /// Build the unique map. It is called by the
     576    /// \c AlterationNotifier.
     577    virtual void build() {
     578      Map::build();
     579      Item it;
     580      const typename Map::Graph* graph = Map::getGraph();
     581      for (graph->first(it); it != INVALID; graph->next(it)) {
     582        Map::set(it, invMap.size());
     583        invMap.push_back(it);   
     584      }     
     585    }
     586   
     587    /// \brief Clear the keys from the map.
     588    ///
     589    /// Clear the keys from the map. It is called by the
     590    /// \c AlterationNotifier.
     591    virtual void clear() {
     592      invMap.clear();
     593      Map::clear();
     594    }
     595
     596    /// \brief Gives back the \e descriptor of the item.
     597    ///
     598    /// Gives back the mutable and unique \e descriptor of the map.
     599    int operator[](const Item& item) const {
     600      return Map::operator[](item);
     601    }
     602   
     603    /// \brief Gives back the inverse of the map.
     604    ///
     605    /// Gives back the inverse of the map.
     606    const InverseMap inverse() const {
     607      return invMap;
     608    }
     609
     610  private:
     611    std::vector<Item> invMap;
     612  };
     613
     614  /// \brief Returns the source of the given edge.
     615  ///
     616  /// The SourceMap gives back the source Node of the given edge.
     617  /// \author Balazs Dezso
     618  template <typename Graph>
     619  class SourceMap {
     620  public:
     621    typedef typename Graph::Node Value;
     622    typedef typename Graph::Edge Key;
     623
     624    /// \brief Constructor
     625    ///
     626    /// Constructor
     627    /// \param _graph The graph that the map belongs to.
     628    SourceMap(const Graph& _graph) : graph(_graph) {}
     629
     630    /// \brief The subscript operator.
     631    ///
     632    /// The subscript operator.
     633    /// \param edge The edge
     634    /// \return The source of the edge
     635    Value operator[](const Key& edge) {
     636      return graph.source(edge);
     637    }
     638
     639  private:
     640    const Graph& graph;
     641  };
     642
     643  /// \brief Returns a \ref SourceMap class
     644  ///
     645  /// This function just returns an \ref SourceMap class.
     646  /// \relates SourceMap
     647  template <typename Graph>
     648  inline SourceMap<Graph> sourceMap(const Graph& graph) {
     649    return SourceMap<Graph>(graph);
     650  }
     651
     652  /// \brief Returns the target of the given edge.
     653  ///
     654  /// The TargetMap gives back the target Node of the given edge.
     655  /// \author Balazs Dezso
     656  template <typename Graph>
     657  class TargetMap {
     658  public:
     659    typedef typename Graph::Node Value;
     660    typedef typename Graph::Edge Key;
     661
     662    /// \brief Constructor
     663    ///
     664    /// Constructor
     665    /// \param _graph The graph that the map belongs to.
     666    TargetMap(const Graph& _graph) : graph(_graph) {}
     667
     668    /// \brief The subscript operator.
     669    ///
     670    /// The subscript operator.
     671    /// \param edge The edge
     672    /// \return The target of the edge
     673    Value operator[](const Key& key) {
     674      return graph.target(key);
     675    }
     676
     677  private:
     678    const Graph& graph;
     679  };
     680
     681  /// \brief Returns a \ref TargetMap class
     682
     683  /// This function just returns an \ref TargetMap class.
     684  /// \relates TargetMap
     685  template <typename Graph>
     686  inline TargetMap<Graph> targetMap(const Graph& graph) {
     687    return TargetMap<Graph>(graph);
     688  }
     689
     690
     691  /// @}
     692
    338693} //END OF NAMESPACE LEMON
    339694
  • src/lemon/graph_writer.h

    r1396 r1402  
    3030#include <memory>
    3131
    32 #include <lemon/map_utils.h>
     32#include <lemon/graph_utils.h>
    3333
    3434#include <lemon/invalid.h>
  • src/lemon/maps.h

    r1359 r1402  
    1818#define LEMON_MAPS_H
    1919
    20 #include<math.h>
    2120
    2221///\file
     
    187186  };
    188187
     188  /// @}
     189
     190  /// \addtogroup map_adaptors
     191  /// @{
     192
     193
    189194  ///Convert the \c Value of a maps to another type.
    190195
     
    235240  {
    236241    return ConvertMap<M,T>(m);
    237   }
    238 
    239   /// \brief Returns the source of the given edge.
    240   ///
    241   /// The SourceMap gives back the source Node of the given edge.
    242   /// \author Balazs Dezso
    243   template <typename Graph>
    244   class SourceMap {
    245   public:
    246     typedef typename Graph::Node Value;
    247     typedef typename Graph::Edge Key;
    248 
    249     /// \brief Constructor
    250     ///
    251     /// Constructor
    252     /// \param _graph The graph that the map belongs to.
    253     SourceMap(const Graph& _graph) : graph(_graph) {}
    254 
    255     /// \brief The subscript operator.
    256     ///
    257     /// The subscript operator.
    258     /// \param edge The edge
    259     /// \return The source of the edge
    260     Value operator[](const Key& edge) {
    261       return graph.source(edge);
    262     }
    263 
    264   private:
    265     const Graph& graph;
    266   };
    267 
    268   /// \brief Returns a \ref SourceMap class
    269 
    270   /// This function just returns an \ref SourceMap class.
    271   /// \relates SourceMap
    272   template <typename Graph>
    273   inline SourceMap<Graph> sourceMap(const Graph& graph) {
    274     return SourceMap<Graph>(graph);
    275   }
    276 
    277   /// \brief Returns the target of the given edge.
    278   ///
    279   /// The TargetMap gives back the target Node of the given edge.
    280   /// \author Balazs Dezso
    281   template <typename Graph>
    282   class TargetMap {
    283   public:
    284     typedef typename Graph::Node Value;
    285     typedef typename Graph::Edge Key;
    286 
    287     /// \brief Constructor
    288     ///
    289     /// Constructor
    290     /// \param _graph The graph that the map belongs to.
    291     TargetMap(const Graph& _graph) : graph(_graph) {}
    292 
    293     /// \brief The subscript operator.
    294     ///
    295     /// The subscript operator.
    296     /// \param edge The edge
    297     /// \return The target of the edge
    298     Value operator[](const Key& key) {
    299       return graph.target(key);
    300     }
    301 
    302   private:
    303     const Graph& graph;
    304   };
    305 
    306   /// \brief Returns a \ref TargetMap class
    307 
    308   /// This function just returns an \ref TargetMap class.
    309   /// \relates TargetMap
    310   template <typename Graph>
    311   inline TargetMap<Graph> targetMap(const Graph& graph) {
    312     return TargetMap<Graph>(graph);
    313242  }
    314243
     
    733662  }
    734663
    735   ///Converts an STL style functor to a a map
     664  ///Converts an STL style functor to a map
    736665
    737666  ///This \ref concept::ReadMap "read only map" returns the value
Note: See TracChangeset for help on using the changeset viewer.