COIN-OR::LEMON - Graph Library

Changeset 1413:3f45d58969d4 in lemon-0.x


Ignore:
Timestamp:
05/11/05 19:36:25 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1882
Message:

Fixing invertable maps:

InvertableMap?
DescriptorMap?
IdMap?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_utils.h

    r1402 r1413  
    2323#include <lemon/invalid.h>
    2424#include <lemon/utility.h>
     25#include <lemon/maps.h>
    2526
    2627///\ingroup gutils
     
    340341  /// @{
    341342
    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 
    394  
    395343  template <typename Map, typename Enable = void>
    396344  struct ReferenceMapTraits {
     
    414362  };
    415363
     364
     365  /// Provides an immutable and unique id for each item in the graph.
     366
     367  /// The IdMap class provides an unique and immutable mapping for each item
     368  /// in the graph.
     369  ///
     370  template <typename _Graph, typename _Item>
     371  class IdMap {
     372  public:
     373    typedef _Graph Graph;
     374    typedef int Value;
     375    typedef _Item Item;
     376    typedef _Item Key;
     377
     378    /// \brief Constructor.
     379    ///
     380    /// Constructor for creating id map.
     381    IdMap(const Graph& _graph) : graph(&_graph) {}
     382
     383    /// \brief Gives back the \e id of the item.
     384    ///
     385    /// Gives back the immutable and unique \e id of the map.
     386    int operator[](const Item& item) const { return graph->id(item);}
     387
     388
     389  private:
     390    const Graph* graph;
     391
     392  public:
     393
     394    /// \brief The class represents the inverse of the map.
     395    ///
     396    /// The class represents the inverse of the map.
     397    /// \see inverse()
     398    class InverseMap {
     399    public:
     400      /// \brief Constructor.
     401      ///
     402      /// Constructor for creating an id-to-item map.
     403      InverseMap(const Graph& _graph) : graph(&_graph) {}
     404
     405      /// \brief Constructor.
     406      ///
     407      /// Constructor for creating an id-to-item map.
     408      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
     409
     410      /// \brief Gives back the given item from its id.
     411      ///
     412      /// Gives back the given item from its id.
     413      ///
     414      Item operator[](int id) const { return graph->fromId(id, Item());}
     415    private:
     416      const Graph* graph;
     417    };
     418
     419    /// \brief Gives back the inverse of the map.
     420    ///
     421    /// Gives back the inverse of the map.
     422    InverseMap inverse() const { return InverseMap(*graph);}
     423
     424  };
     425
     426 
    416427  /// \brief General inversable graph-map type.
    417428
     
    427438    typename _Value,
    428439    typename _Map
    429     = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
     440    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
    430441  >
    431   class InversableMap : protected _Map {
     442  class InvertableMap : protected _Map {
    432443
    433444  public:
     
    435446    typedef _Map Map;
    436447    typedef _Graph Graph;
    437    /// The key type of InversableMap (Node, Edge, UndirEdge).
     448
     449    /// The key type of InvertableMap (Node, Edge, UndirEdge).
    438450    typedef typename _Map::Key Key;
    439     /// The value type of the InversableMap.
     451    /// The value type of the InvertableMap.
    440452    typedef typename _Map::Value Value;
    441453
    442     typedef std::map<Value, Key> InverseMap;
    443    
    444     typedef typename _Map::ConstReference ConstReference;
    445 
    446454    /// \brief Constructor.
    447455    ///
    448     /// Construct a new InversableMap for the graph.
    449     ///
    450     InversableMap(const Graph& graph) : Map(graph) {}
     456    /// Construct a new InvertableMap for the graph.
     457    ///
     458    InvertableMap(const Graph& graph) : Map(graph) {}
    451459   
    452460    /// \brief The setter function of the map.
    453461    ///
    454 
     462    /// Sets the mapped value.
    455463    void set(const Key& key, const Value& val) {
    456464      Value oldval = Map::operator[](key);
    457       typename InverseMap::iterator it = invMap.find(oldval);
     465      typename Container::iterator it = invMap.find(oldval);
    458466      if (it != invMap.end() && it->second == key) {
    459467        invMap.erase(it);
     
    466474    ///
    467475    /// It gives back the value associated with the key.
    468     ConstReference operator[](const Key& key) const {
     476    const Value operator[](const Key& key) const {
    469477      return Map::operator[](key);
    470478    }
     
    484492    virtual void erase(const Key& key) {
    485493      Value val = Map::operator[](key);
    486       typename InverseMap::iterator it = invMap.find(val);
     494      typename Container::iterator it = invMap.find(val);
    487495      if (it != invMap.end() && it->second == key) {
    488496        invMap.erase(it);
     
    500508    }
    501509
     510  private:
     511   
     512    typedef std::map<Value, Key> Container;
     513    Container invMap;   
     514
     515  public:
     516
     517    /// \brief The inverse map type.
     518    ///
     519    /// The inverse of this map. The subscript operator of the map
     520    /// gives back always the item what was last assigned to the value.
     521    class InverseMap {
     522    public:
     523      /// \brief Constructor of the InverseMap.
     524      ///
     525      /// Constructor of the InverseMap.
     526      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
     527
     528      /// The value type of the InverseMap.
     529      typedef typename InvertableMap::Key Value;
     530      /// The key type of the InverseMap.
     531      typedef typename InvertableMap::Value Key;
     532
     533      /// \brief Subscript operator.
     534      ///
     535      /// Subscript operator. It gives back always the item
     536      /// what was last assigned to the value.
     537      Value operator[](const Key& key) const {
     538        typename Container::const_iterator it = inverted.invMap.find(key);
     539        return it->second;
     540      }
     541     
     542    private:
     543      const InvertableMap& inverted;
     544    };
     545
    502546    /// \brief It gives back the just readeable inverse map.
    503547    ///
    504548    /// It gives back the just readeable inverse map.
    505     const InverseMap& inverse() const {
    506       return invMap;
     549    InverseMap inverse() const {
     550      return InverseMap(*this);
    507551    }
    508552
    509553
    510   private:
    511     InverseMap invMap;   
     554   
    512555  };
    513556
     
    516559  ///
    517560  /// The DescriptorMap class provides a mutable, continuous and immutable
    518   /// mapping for each item in the graph.
     561  /// mapping for each item in the graph. The value for an item may mutated
     562  /// on each operation when the an item erased or added to graph.
    519563  ///
    520564  /// \param _Graph The graph class the \c DescriptorMap belongs to.
     
    522566  /// UndirEdge.
    523567  /// \param _Map A ReadWriteMap mapping from the item type to integer.
    524 
    525568  template <
    526569    typename _Graph,   
    527570    typename _Item,
    528     typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
     571    typename _Map
     572    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
    529573  >
    530574  class DescriptorMap : protected _Map {
     
    542586    typedef typename _Map::Value Value;
    543587
    544     typedef std::vector<Item> InverseMap;
    545 
    546588    /// \brief Constructor.
    547589    ///
    548     /// Constructor for creating descriptor map.
     590    /// Constructor for descriptor map.
    549591    DescriptorMap(const Graph& _graph) : Map(_graph) {
    550592      build();
     
    568610      Map::set(invMap.back(), Map::operator[](item));
    569611      invMap[Map::operator[](item)] = invMap.back();
     612      invMap.pop_back();
    570613      Map::erase(item);
    571614    }
     
    601644    }
    602645   
     646  private:
     647
     648    typedef std::vector<Item> Container;
     649    Container invMap;
     650
     651  public:
     652    /// \brief The inverse map type.
     653    ///
     654    /// The inverse map type.
     655    class InverseMap {
     656    public:
     657      /// \brief Constructor of the InverseMap.
     658      ///
     659      /// Constructor of the InverseMap.
     660      InverseMap(const DescriptorMap& _inverted)
     661        : inverted(_inverted) {}
     662
     663
     664      /// The value type of the InverseMap.
     665      typedef typename DescriptorMap::Key Value;
     666      /// The key type of the InverseMap.
     667      typedef typename DescriptorMap::Value Key;
     668
     669      /// \brief Subscript operator.
     670      ///
     671      /// Subscript operator. It gives back the item
     672      /// that the descriptor belongs to currently.
     673      Value operator[](const Key& key) const {
     674        return inverted.invMap[key];
     675      }
     676     
     677    private:
     678      const DescriptorMap& inverted;
     679    };
     680
    603681    /// \brief Gives back the inverse of the map.
    604682    ///
    605683    /// Gives back the inverse of the map.
    606684    const InverseMap inverse() const {
    607       return invMap;
    608     }
    609 
    610   private:
    611     std::vector<Item> invMap;
     685      return InverseMap(*this);
     686    }
    612687  };
    613688
Note: See TracChangeset for help on using the changeset viewer.