Loading...
Searching...
No Matches
ListPath< GR > Class Template Reference
Data Structures » Path Structures

## Detailed Description

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

A structure for representing directed path in a digraph.

Template Parameters

  GR | The digraph type in which the path is.

In a sense, the path can be treated as a list of arcs. The LEMON path type stores just this list. As a consequence it cannot enumerate the nodes in the path and the zero length paths cannot store the source.

This implementation is a back and front insertable and erasable path type. It can be indexed in O(k) time, where k is the rank of the arc in the path. The length can be computed in O(n) time. The front and back insertion and erasure is O(1) time and it can be splited and spliced in O(1) time.

`#include <lemon/path.h>`

## Classes

class | ArcIt
| Iterator class to iterate on the arcs of the paths. More...

## Public Member Functions

| ListPath ()
| Default constructor.
| ListPath (const ListPath &cpath)
| Copy constructor.
template<typename CPath>
| ListPath (const CPath &cpath)
| Template copy constructor.
| ~ListPath ()
| Destructor of the path.
ListPath & | operator= (const ListPath &cpath)
| Copy assignment.
template<typename CPath>
ListPath & | operator= (const CPath &cpath)
| Template copy assignment.
const Arc & | nth (int n) const
| The n-th arc.
ArcIt | nthIt (int n) const
| Initializes arc iterator to point to the n-th arc.
int | length () const
| Length of the path.
bool | empty () const
| Return true if the path is empty.
void | clear ()
| Reset the path to an empty one.
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.
void | spliceBack (ListPath &tpath)
| Splice a path to the back of the current path.
void | spliceFront (ListPath &tpath)
| Splice a path to the front of the current path.
void | splice (ArcIt it, ListPath &tpath)
| Splice a path into the current path.
void | split (ArcIt it, ListPath &tpath)
| Split the current path.

## Constructor & Destructor Documentation

## ListPath() [1/2]

template<typename GR>

ListPath | ( |  | ) |

inline

Default constructor

## ListPath() [2/2]

template<typename GR>
template<typename CPath>

ListPath | ( | const CPath & | cpath | ) |

inline

This path can be initialized with any other path type. It just makes a copy of the given path.

## ~ListPath()

template<typename GR>

~ListPath | ( |  | ) |

inline

Destructor of the path

## Member Function Documentation

## operator=()

template<typename GR>
template<typename CPath>

ListPath & operator= | ( | const CPath & | cpath | ) |

inline

This path can be initialized with any other path type. It just makes a copy of the given path.

## nth()

template<typename GR>

const Arc & nth | ( | int | n | ) | const

inline

This function looks for the n-th arc in O(n) time.

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

## spliceBack()

template<typename GR>

void spliceBack | ( | ListPath< GR > & | tpath | ) |

inline

It splices `tpath` to the back of the current path and `tpath` becomes empty. The time complexity of this function is O(1).

## spliceFront()

template<typename GR>

void spliceFront | ( | ListPath< GR > & | tpath | ) |

inline

It splices `tpath` before the current path and `tpath` becomes empty. The time complexity of this function is O(1).

## splice()

template<typename GR>

void splice | ( | ArcIt | it,
|  | ListPath< GR > & | tpath )

inline

It splices the `tpath` into the current path before the position of `it` iterator and `tpath` becomes empty. The time complexity of this function is O(1). If the `it` is `INVALID` then it will splice behind the current path.

## split()

template<typename GR>

void split | ( | ArcIt | it,
|  | ListPath< GR > & | tpath )

inline

It splits the current path into two parts. The part before the iterator `it` will remain in the current path and the part starting with `it` will put into `tpath`. If `tpath` have arcs before the operation they are removed first. The time complexity of this function is O(1) plus the the time of emtying `tpath`. If `it` is `INVALID` then it just clears `tpath`