ListPath< _Graph > Class Template Reference
[Path Structures]

---

Detailed Description

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

A structure for representing directed path in a graph.

Parameters:

Graph

The graph type in which the path is.

In a sense, the path can be treated as a list of edges. 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 edge 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>

List of all members.

Classes
class	EdgeIt
	Iterator class to iterate on the edges of the paths. More...
Public Member Functions
	ListPath ()
	Default constructor.
template<typename CPath >
	ListPath (const CPath &cpath)
	Template copy constructor.
	~ListPath ()
	Destructor of the path.
template<typename CPath >
ListPath &	operator= (const CPath &cpath)
	Template copy assignment.
const Edge &	nth (int n) const
	Gives back the nth edge.
EdgeIt	nthIt (int n) const
	Initializes edge iterator to point to the nth edge.
int	length () const
	Length of the path.
bool	empty () const
	Returns whether the path is empty.
void	clear ()
	Resets the path to an empty path.
const Edge &	front () const
	Gives back the first edge of the path.
void	addFront (const Edge &edge)
	Add a new edge before the current path.
void	eraseFront ()
	Erase the first edge of the path.
const Edge &	back () const
	Gives back the last edge of the path.
void	addBack (const Edge &edge)
	Add a new edge behind the current path.
void	eraseBack ()
	Erase the last edge of the path.
void	spliceBack (ListPath &tpath)
	Splicing the given path to the current path.
void	spliceFront (ListPath &tpath)
	Splicing the given path to the current path.
void	splice (EdgeIt it, ListPath &tpath)
	Splicing the given path into the current path.
void	split (EdgeIt it, ListPath &tpath)
	Spliting the current path.

---

Constructor & Destructor Documentation

ListPath

(

)

[inline]

Default constructor

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

(

)

[inline]

Destructor of the path

---

Member Function Documentation

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.

const Edge& nth

(

int

n

)

const [inline]

Gives back the nth edge in O(n) time.

Precondition:

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

void spliceBack

(

ListPath< _Graph > &

tpath

)

[inline]

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

void spliceFront

(

ListPath< _Graph > &

tpath

)

[inline]

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

void splice	(	EdgeIt	it,
		ListPath< _Graph > &	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.

void split	(	EdgeIt	it,
		ListPath< _Graph > &	tpath
	)			[inline]

It splits the current path into two parts. The part before it iterator will remain in the current path and the part from the it will put into the tpath. If the tpath had edges before the operation they will be removed first. The time complexity of this function is O(1) plus the clearing of tpath. If the it is INVALID then it just clears tpath.