COIN-OR::LEMON - Graph Library

Changeset 1402:655d8e78454d in lemon-0.x for src/lemon/graph_utils.h


Ignore:
Timestamp:
05/05/05 13:05:25 (16 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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.