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

Timestamp:

05/05/05 13:05:25 (20 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:

• src/lemon/graph_utils.h (modified) (2 diffs)

src/lemon/graph_utils.h

@@ -19 +19 @@
 
 #include <iterator>
+#include <map>
 
 #include <lemon/invalid.h>
@@ -335 +336 @@
 
   /// @}
+
+  /// \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 <typename _Graph, typename _Item>
+  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 <typename Map, typename Enable = void>
+  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 <typename Map>
+  struct ReferenceMapTraits<
+    Map, 
+    typename enable_if<typename Map::FullTypeTag, void>::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<Value, Key> 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<int>
+  >
+  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<Item> 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<Item> invMap;
+  };
+
+  /// \brief Returns the source of the given edge.
+  ///
+  /// The SourceMap gives back the source Node of the given edge. 
+  /// \author Balazs Dezso
+  template <typename Graph>
+  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 <typename Graph>
+  inline SourceMap<Graph> sourceMap(const Graph& graph) {
+    return SourceMap<Graph>(graph);
+  } 
+
+  /// \brief Returns the target of the given edge.
+  ///
+  /// The TargetMap gives back the target Node of the given edge. 
+  /// \author Balazs Dezso
+  template <typename Graph>
+  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 <typename Graph>
+  inline TargetMap<Graph> targetMap(const Graph& graph) {
+    return TargetMap<Graph>(graph);
+  }
+
+
+  /// @}
+
 } //END OF NAMESPACE LEMON