Path

Declared in lemon/path.h, in the group Path Structures; the same class on the Doxygen site.

template< typename GR >
class Path

A structure for representing directed paths in a digraph.

A structure for representing directed path in a digraph.

In a sense, a path can be treated as a list of arcs. The LEMON path type simply stores this list. As a consequence, it cannot enumerate the nodes in the path, and the source node of a zero-length path is undefined.

This implementation is a back and front insertable and erasable path type. It can be indexed in O(1) time. The front and back insertion and erase is done in O(1) (amortized) time. The implementation uses two vectors for storing the front and back insertions.

Template Parameters:

GR – The digraph type in which the path is.

Public Types

typedef GR Digraph
typedef Digraph::Arc Arc
typedef True BuildTag

Public Functions

inline Path()

Default constructor

inline Path( const Path & cpath )

Copy constructor.

template< typename CPath >
inline Path( const CPath & cpath )

Template copy constructor.

This constuctor initializes the path from any other path type. It simply makes a copy of the given path.

inline Path & operator=( const Path & cpath )

Copy assignment.

template< typename CPath >
inline Path & operator=( const CPath & cpath )

Template copy assignment.

This operator makes a copy of a path of any other type.

inline LemonRangeWrapper1< ArcIt , Path > arcs() const

Gets the collection of the arcs of the path.

This function can be used for iterating on the arcs of the path. It returns a wrapped ArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example you can write:

for( auto a : p.arcs() )
 doSomething( a );

inline int length() const

Length of the path.

inline bool empty() const

Return whether the path is empty.

inline void clear()

Reset the path to an empty one.

inline const Arc & nth( int n ) const

The n-th arc.

Gives back the n-th arc. This function runs in O(1) time.

Pre:

n is in the range [0..length() - 1].

inline ArcIt nthIt( int n ) const

Initialize arc iterator to point to the n-th arc.

Pre:

n is in the [0..length() - 1] range.

inline const Arc & operator[]( int n ) const

The n-th arc.

Gives back the n-th arc. This operator is just an alias for nth(), it runs in O(1) time.

Pre:

n is in the range [0..length() - 1].

inline const Arc & front() const

The first arc of the path.

inline void addFront( const Arc & arc )

Add a new arc before the current path.

inline void eraseFront()

Erase the first arc of the path.

inline const Arc & back() const

The last arc of the path.

inline void addBack( const Arc & arc )

Add a new arc behind the current path.

inline void eraseBack()

Erase the last arc of the path.

template< typename CPath >
inline void build( const CPath & path )
template< typename CPath >
inline void buildRev( const CPath & path )

Protected Types

typedef std::vector< Arc > Container

Protected Attributes

Container head
Container tail
class ArcIt

LEMON style iterator for path arcs.

This class is used to iterate on the arcs of the paths.

Public Functions

inline ArcIt()

Default constructor.

inline ArcIt(Invalid)

Invalid constructor.

inline ArcIt( const Path & _path )

Initializate the iterator to the first arc of path.

inline operator const Arc&() const

Conversion to Arc.

inline ArcIt & operator++()

Next arc.

inline bool operator==( const ArcIt & e ) const

Comparison operator.

inline bool operator!=( const ArcIt & e ) const

Comparison operator.

inline bool operator<( const ArcIt & e ) const

Comparison operator.