abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Path< GR > Class Template Reference

A structure for representing directed paths in a digraph. More...

#include <lemon/path.h>

Classes

class  ArcIt
 LEMON style iterator for path arcs. More...

Public Member Functions

 Path ()
 Default constructor.
 Path (const Path &cpath)
 Copy constructor.
template< typename CPath >
 Path (const CPath &cpath)
 Template copy constructor.
Path & operator= (const Path &cpath)
 Copy assignment.
template< typename CPath >
Path & operator= (const CPath &cpath)
 Template copy assignment.
LemonRangeWrapper1< ArcIt , Path > arcs () const
 Gets the collection of the arcs of the path.
int length () const
 Length of the path.
bool empty () const
 Return whether the path is empty.
void clear ()
 Reset the path to an empty one.
const Arc & nth (int n) const
 The n-th arc.
ArcIt nthIt (int n) const
 Initialize arc iterator to point to the n-th arc.
const Arc & operator[] (int n) const
 The n-th arc.
const Arc & front () const
 The first arc of the path.
void addFront (const Arc &arc)
 Add a new arc before the current path.
void eraseFront ()
 Erase the first arc of the path.
const Arc & back () const
 The last arc of the path.
void addBack (const Arc &arc)
 Add a new arc behind the current path.
void eraseBack ()
 Erase the last arc of the path.

Detailed Description

template< typename GR >
class lemon::Path< GR >

A structure for representing directed path in a digraph.

Template Parameters
GRThe digraph type in which the path is.

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.

Constructor & Destructor Documentation

◆ Path() [1/2]

template< typename GR >
Path ( )
inline

Default constructor

◆ Path() [2/2]

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

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

Member Function Documentation

◆ operator=()

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

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

◆ arcs()

template< typename GR >
LemonRangeWrapper1< ArcIt , Path > arcs ( ) const
inline

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 );

◆ nth()

template< typename GR >
const Arc & nth ( int n) const
inline

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

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

◆ nthIt()

template< typename GR >
ArcIt nthIt ( int n) const
inline
Precondition
n is in the [0..length() - 1] range.

◆ operator[]()

template< typename GR >
const Arc & operator[] ( int n) const
inline

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

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