SplitNodes

Declared in lemon/adaptors.h, in the group Adaptor Classes for Graphs; the same class on the Doxygen site.

template< typename DGR >
class SplitNodes

Adaptor class for splitting the nodes of a digraph.

SplitNodes adaptor can be used for splitting each node into an in-node and an out-node in a digraph. Formaly, the adaptor replaces each node \( u \) in the digraph with two nodes, namely node \( u_{in} \) and node \( u_{out} \). If there is a \( (v, u) \) arc in the original digraph, then the new target of the arc will be \( u_{in} \) and similarly the source of each original \( (u, v) \) arc will be \( u_{out} \). The adaptor adds an additional bind arc from \( u_{in} \) to \( u_{out} \) for each node \( u \) of the original digraph.

The aim of this class is running an algorithm with respect to node costs or capacities if the algorithm considers only arc costs or capacities directly. In this case you can use SplitNodes adaptor, and set the node costs/capacities of the original digraph to the bind arcs in the adaptor.

This class provides item counting in the same time as the adapted digraph structure.

Note

The Node type of this adaptor is converible to the Node type of the adapted digraph.

Template Parameters:

DGR – The type of the adapted digraph. It must conform to the Digraph concept. It is implicitly const.

Public Types

typedef DGR Digraph
typedef DGR::Node DigraphNode
typedef DGR::Arc DigraphArc
typedef Parent::Node Node
typedef Parent::Arc Arc

Public Functions

inline SplitNodes( const DGR & g )

Constructor.

Constructor of the adaptor.

Public Static Functions

static inline bool inNode( const Node & n )

Returns true if the given node is an in-node.

static inline bool outNode( const Node & n )

Returns true if the given node is an out-node.

static inline bool origArc( const Arc & a )

Returns true if the given arc is an original arc.

Returns true if the given arc is one of the arcs in the original digraph.

static inline bool bindArc( const Arc & a )

Returns true if the given arc is a bind arc.

Returns true if the given arc is a bind arc, i.e. it connects an in-node and an out-node.

static inline Node inNode( const DigraphNode & n )

Returns the in-node created from the given original node.

static inline Node outNode( const DigraphNode & n )

Returns the out-node created from the given original node.

static inline Arc arc( const DigraphNode & n )

Returns the bind arc that corresponds to the given original node.

Returns the bind arc in the adaptor that corresponds to the given original node, i.e. the arc connecting the in-node and out-node of n.

static inline Arc arc( const DigraphArc & a )

Returns the arc that corresponds to the given original arc.

Returns the arc in the adaptor that corresponds to the given original arc.

template< typename In , typename Out >
static inline CombinedNodeMap< In , Out > combinedNodeMap(
In & in_map,
Out & out_map
)

Returns a combined node map.

This function just returns a combined node map.

template< typename In , typename Out >
static inline CombinedNodeMap< const In , Out > combinedNodeMap(
const In & in_map,
Out & out_map
)
template< typename In , typename Out >
static inline CombinedNodeMap< In , const Out > combinedNodeMap(
In & in_map,
const Out & out_map
)
template< typename In , typename Out >
static inline CombinedNodeMap< const In , const Out > combinedNodeMap(
const In & in_map,
const Out & out_map
)
template< typename ArcMap , typename NodeMap >
static inline CombinedArcMap< ArcMap , NodeMap > combinedArcMap(
ArcMap & arc_map,
NodeMap & node_map
)

Returns a combined arc map.

This function just returns a combined arc map.

template< typename ArcMap , typename NodeMap >
static inline CombinedArcMap< const ArcMap , NodeMap > combinedArcMap(
const ArcMap & arc_map,
NodeMap & node_map
)
template< typename ArcMap , typename NodeMap >
static inline CombinedArcMap< ArcMap , const NodeMap > combinedArcMap(
ArcMap & arc_map,
const NodeMap & node_map
)
template< typename ArcMap , typename NodeMap >
static inline CombinedArcMap< const ArcMap , const NodeMap > combinedArcMap(
const ArcMap & arc_map,
const NodeMap & node_map
)
template< typename In , typename Out >
class CombinedNodeMap

Node map combined from two original node maps.

This map adaptor class adapts two node maps of the original digraph to get a node map of the split digraph. Its value type is inherited from the first node map type (In).

Template Parameters:
  • In – The type of the node map for the in-nodes.

  • Out – The type of the node map for the out-nodes.

Public Types

typedef Node Key

The key type of the map.

typedef In::Value Value

The value type of the map.

typedef MapTraits< In >::ReferenceMapTag ReferenceMapTag
typedef MapTraits< In >::ReturnValue ReturnValue
typedef MapTraits< In >::ConstReturnValue ConstReturnValue
typedef MapTraits< In >::ReturnValue Reference
typedef MapTraits< In >::ConstReturnValue ConstReference

Public Functions

inline CombinedNodeMap( In & in_map , Out & out_map )

Constructor.

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

Returns the value associated with the given key.

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

Returns a reference to the value associated with the given key.

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

Sets the value associated with the given key.

template< typename AM , typename NM >
class CombinedArcMap

Arc map combined from an arc map and a node map of the original digraph.

This map adaptor class adapts an arc map and a node map of the original digraph to get an arc map of the split digraph. Its value type is inherited from the original arc map type (AM).

Template Parameters:
  • AM – The type of the arc map.

  • NM – the type of the node map.

Public Types

typedef Arc Key

The key type of the map.

typedef AM::Value Value

The value type of the map.

typedef MapTraits< AM >::ReferenceMapTag ReferenceMapTag
typedef MapTraits< AM >::ReturnValue ReturnValue
typedef MapTraits< AM >::ConstReturnValue ConstReturnValue
typedef MapTraits< AM >::ReturnValue Reference
typedef MapTraits< AM >::ConstReturnValue ConstReference

Public Functions

inline CombinedArcMap( AM & arc_map , NM & node_map )

Constructor.

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

Returns the value associated with the given key.

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

Returns a reference to the value associated with the given key.

inline void set( const Arc & arc , const Value & val )

Sets the value associated with the given key.