CrossRefMap

Declared in lemon/maps.h, in the group Graph Maps; the same class on the Doxygen site.

template< typename GR , typename K , typename V >
class CrossRefMap : protected Type< GR , K >

General cross reference graph map type.

This class provides simple invertable graph maps. It wraps a standard graph map (NodeMap, ArcMap or EdgeMap) and if a key is set to a new value, then stores it in the inverse map. The graph items can be accessed by their values either using InverseMap or operator()(), and the values of the map can be accessed with an STL compatible forward iterator (ValueIt).

This map is intended to be used when all associated values are different (the map is actually invertable) or there are only a few items with the same value. Otherwise consider to use IterableValueMap, which is more suitable and more efficient for such cases. It provides iterators to traverse the items with the same associated value, but it does not have InverseMap.

This type is not reference map, so it cannot be modified with the subscript operator.

See also

IterableValueMap

Template Parameters:
  • GR – The graph type.

  • K – The key type of the map (GR::Node, GR::Arc or GR::Edge).

  • V – The value type of the map.

Public Types

typedef GR Graph

The graph type of CrossRefMap.

typedef GR Digraph
typedef K Item

The key type of CrossRefMap (Node, Arc or Edge).

typedef K Key

The key type of CrossRefMap (Node, Arc or Edge).

typedef V Value

The value type of CrossRefMap.

typedef ValueIt ValueIterator

Alias for ValueIt.

Public Functions

inline explicit CrossRefMap( const Graph & graph )

Constructor.

Construct a new CrossRefMap for the given graph.

inline ValueIt beginValue() const

Returns an iterator to the first value.

Returns an STL compatible iterator to the first value of the map. The values of the map can be accessed in the [beginValue, endValue) range.

inline ValueIt endValue() const

Returns an iterator after the last value.

Returns an STL compatible iterator after the last value of the map. The values of the map can be accessed in the [beginValue, endValue) range.

inline void set( const Key & key , const Value & val )

Sets the value associated with the given key.

inline MapTraits< Map >::ConstReturnValue operator[]( const Key & key ) const

Returns the value associated with the given key.

inline Key operator()( const Value & val ) const

Gives back an item by its value.

This function gives back an item that is assigned to the given value or INVALID if no such item exists. If there are more items with the same associated value, only one of them is returned.

inline int count( const Value & val ) const

Returns the number of items with the given value.

This function returns the number of items with the given value associated with it.

inline InverseMap inverse() const

Gives back the inverse of the map.

Gives back the inverse of the CrossRefMap.

Protected Functions

inline virtual void erase( const Key & key )

Erase the key from the map and the inverse map. It is called by the AlterationNotifier.

inline virtual void erase( const std::vector< Key > & keys )

Erase more keys from the map and the inverse map. It is called by the AlterationNotifier.

inline virtual void clear()

Clear the keys from the map and the inverse map. It is called by the AlterationNotifier.

class ValueIt

Forward iterator for values.

This iterator is an STL compatible forward iterator on the values of the map. The values can be accessed in the [beginValue, endValue) range. They are considered with multiplicity, so each value is traversed for each item it is assigned to.

Public Types

typedef std::forward_iterator_tag iterator_category
typedef Value value_type
typedef std::ptrdiff_t difference_type
typedef Value * pointer
typedef Value & reference

Public Functions

inline ValueIt()

Constructor.

inline ValueIt & operator++()

inline ValueIt operator++(int)

inline const Value & operator*() const

inline const Value * operator->() const

inline bool operator==( ValueIt jt ) const

inline bool operator!=( ValueIt jt ) const

class InverseMap

The inverse map type of CrossRefMap. The subscript operator gives back an item by its value. This type conforms to the ReadMap concept.

See also

inverse()

Public Types

typedef CrossRefMap::Key Value

The value type of the InverseMap.

typedef CrossRefMap::Value Key

The key type of the InverseMap.

Public Functions

inline explicit InverseMap( const CrossRefMap & inverted )

Constructor.

Constructor of the InverseMap.

inline Value operator[]( const Key & key ) const

Subscript operator. It gives back an item that is assigned to the given value or INVALID if no such item exists.