Classes | Public Member Functions

ListPath< GR > Class Template Reference


Detailed Description

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

A structure for representing directed path in a digraph.

Template Parameters:
GRThe 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>

List of all members.

Classes

class  ArcIt
 Iterator class to iterate on the arcs 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 >
ListPathoperator= (const CPath &cpath)
 Template copy assignment.
const Arc & nth (int n) const
 The nth arc.
ArcIt nthIt (int n) const
 Initializes arc iterator to point to the nth 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 ( ) [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 Arc& nth ( int  n) const [inline]

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

Precondition:
n is in the [0..length() - 1] range.
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).

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

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.

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

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines