ListPath
Declared in lemon/path.h, in the group Path Structures; the same class on the Doxygen site.
-
template< typename GR >
class ListPath 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(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.
- Template Parameters:
GR – The digraph type in which the path is.
Public Functions
-
inline ListPath()
Default constructor
-
template< typename CPath >
inline ListPath( const CPath & cpath ) Template copy constructor.
This path can be initialized with any other path type. It just makes a copy of the given path.
-
inline ~ListPath()
Destructor of the path
-
template< typename CPath >
inline ListPath & operator=( const CPath & cpath ) Template copy assignment.
This path can be initialized with any other path type. It just makes a copy of the given path.
-
inline LemonRangeWrapper1< ArcIt , ListPath > 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 const Arc & nth( int n ) const
The n-th arc.
This function looks for the n-th arc in O(n) time.
- Pre:
nis in the range[0..length() - 1].
-
inline const Arc & operator[]( int n ) const
The n-th arc.
Looks for the n-th arc in O(n) time. This operator is just an alias for nth().
- Pre:
nis in the range[0..length() - 1].
-
inline int length() const
Length of the path.
-
inline bool empty() const
Return true if the path is empty.
-
inline void clear()
Reset the path to an empty one.
-
inline void eraseFront()
Erase the first arc of the path.
-
inline void eraseBack()
Erase the last arc of the path.
-
inline void spliceBack( ListPath & tpath )
Splice a path to the back of the current path.
It splices
tpathto the back of the current path andtpathbecomes empty. The time complexity of this function is O(1).
-
inline void spliceFront( ListPath & tpath )
Splice a path to the front of the current path.
It splices
tpathbefore the current path andtpathbecomes empty. The time complexity of this function is O(1).
-
inline void splice( ArcIt it , ListPath & tpath )
Splice a path into the current path.
It splices the
tpathinto the current path before the position ofititerator andtpathbecomes empty. The time complexity of this function is O(1). If theitisINVALIDthen it will splice behind the current path.
-
inline void split( ArcIt it , ListPath & tpath )
Split the current path.
It splits the current path into two parts. The part before the iterator
itwill remain in the current path and the part starting withitwill put intotpath. Iftpathhave arcs before the operation they are removed first. The time complexity of this function is O(1) plus the time of emtyingtpath. IfitisINVALIDthen it just clearstpath
-
struct Node