Changeset - r97:ee1324c91288
« 96:b55e50
98:c4582f »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Doc improvements
0 2 0
default
2 files changed with 73 insertions and 72 deletions:
lemon/path.h
60
60
lemon/path_utils.h
13
12
↑ Collapse diff ↑
lemon/path.h
Ignore white space 2 line context
... ... 
@@ -45,5 +45,5 @@
45 45 
  /// In a sense, the path can be treated as a list of arcs. The
46 
  /// lemon path type stores just this list. As a consequence it
47 
  /// cannot enumerate the nodes in the path and the zero length paths
48 
  /// cannot store the source.
46 
  /// lemon path type stores just this list. As a consequence, it
47 
  /// cannot enumerate the nodes of the path and the source node of
48 
  /// a zero length path is undefined.
49 49 
  ///
... ... 
@@ -51,4 +51,5 @@
51 51 
  /// path type. It can be indexed in O(1) time. The front and back
52 
  /// insertion and erasure is amortized O(1) time. The
53 
  /// impelementation is based on two opposite organized vectors.
52 
  /// insertion and erase is done in O(1) (amortized) time. The
53 
  /// implementation uses two vectors for storing the front and back
54 
  /// insertions.
54 55 
  template <typename _Digraph>
... ... 
@@ -67,4 +68,4 @@
67 68 
    ///
68 
    /// This path can be initialized with any other path type. It just
69 
    /// makes a copy of the given path.
69 
    /// This constuctor initializes the path from any other path type.
70 
    /// It simply makes a copy of the given path.
70 71 
    template <typename CPath>
... ... 
@@ -76,4 +77,3 @@
76 77 
    ///
77 
    /// This path can be initialized with any other path type. It just
78 
    /// makes a copy of the given path.
78 
    /// This operator makes a copy of a path of any other type.
79 79 
    template <typename CPath>
... ... 
@@ -94,3 +94,3 @@
94 94 
      ArcIt(Invalid) : path(0), idx(-1) {}
95 
      /// \brief Initializate the constructor to the first arc of path
95 
      /// \brief Initializate the iterator to the first arc of path
96 96 
      ArcIt(const Path &_path)
... ... 
@@ -131,9 +131,9 @@
131 131 
    int length() const { return head.size() + tail.size(); }
132 
    /// \brief Returns whether the path is empty.
132 
    /// \brief Return whether the path is empty.
133 133 
    bool empty() const { return head.empty() && tail.empty(); }
134 134 

			




	135
	
	
		
    /// \brief Resets the path to an empty path.


			




	
	135
	
		
    /// \brief Reset the path to an empty one.


			




	136
	136
	
		
    void clear() { head.clear(); tail.clear(); }


			




	137
	137
	
		

			




	138
	
	
		
    /// \brief Gives back the nth arc.


			




	
	138
	
		
    /// \brief The nth arc.


			




	139
	139
	
		
    ///


			




	...
	...
	
		
@@ -145,3 +145,3 @@


			




	145
	145
	
		

			




	146
	
	
		
    /// \brief Initializes arc iterator to point to the nth arc


			




	
	146
	
		
    /// \brief Initialize arc iterator to point to the nth arc


			




	147
	147
	
		
    ///


			




	...
	...
	
		
@@ -152,3 +152,3 @@


			




	152
	152
	
		

			




	153
	
	
		
    /// \brief Gives back the first arc of the path


			




	
	153
	
		
    /// \brief The first arc of the path


			




	154
	154
	
		
    const Arc& front() const {


			




	...
	...
	
		
@@ -177,3 +177,3 @@


			




	177
	177
	
		

			




	178
	
	
		
    /// \brief Gives back the last arc of the path


			




	
	178
	
		
    /// \brief The last arc of the path


			




	179
	179
	
		
    const Arc& back() const {


			




	...
	...
	
		
@@ -201,4 +201,2 @@


			




	201
	201
	
		

			




	202
	
	
		

			




	203
	
	
		

			




	204
	202
	
		
    typedef True BuildTag;


			




	...
	...
	
		
@@ -325,9 +323,9 @@


			




	325
	323
	
		
    int length() const { return data.size(); }


			




	326
	
	
		
    /// \brief Returns whether the path is empty.


			




	
	324
	
		
    /// \brief Return true if the path is empty.


			




	327
	325
	
		
    bool empty() const { return data.empty(); }


			




	328
	326
	
		

			




	329
	
	
		
    /// \brief Resets the path to an empty path.


			




	
	327
	
		
    /// \brief Reset the path to an empty one.


			




	330
	328
	
		
    void clear() { data.clear(); }


			




	331
	329
	
		

			




	332
	
	
		
    /// \brief Gives back the nth arc.


			




	
	330
	
		
    /// \brief The nth arc.


			




	333
	331
	
		
    ///


			




	...
	...
	
		
@@ -343,3 +341,3 @@


			




	343
	341
	
		

			




	344
	
	
		
    /// \brief Gives back the first arc of the path.


			




	
	342
	
		
    /// \brief The first arc of the path.


			




	345
	343
	
		
    const Arc& front() const {


			




	...
	...
	
		
@@ -348,3 +346,3 @@


			




	348
	346
	
		

			




	349
	
	
		
    /// \brief Gives back the last arc of the path.


			




	
	347
	
		
    /// \brief The last arc of the path.


			




	350
	348
	
		
    const Arc& back() const {


			




	...
	...
	
		
@@ -508,5 +506,5 @@


			




	508
	506
	
		

			




	509
	
	
		
    /// \brief Gives back the nth arc.


			




	
	507
	
		
    /// \brief The nth arc.


			




	510
	508
	
		
    ///


			




	511
	
	
		
    /// Gives back the nth arc in O(n) time.


			




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


			




	512
	510
	
		
    /// \pre n is in the [0..length() - 1] range


			




	...
	...
	
		
@@ -540,6 +538,6 @@


			




	540
	538
	
		

			




	541
	
	
		
    /// \brief Returns whether the path is empty.


			




	
	539
	
		
    /// \brief Return true if the path is empty.


			




	542
	540
	
		
    bool empty() const { return first == 0; }


			




	543
	541
	
		

			




	544
	
	
		
    /// \brief Resets the path to an empty path.


			




	
	542
	
		
    /// \brief Reset the path to an empty one.


			




	545
	543
	
		
    void clear() {


			




	...
	...
	
		
@@ -553,3 +551,3 @@


			




	553
	551
	
		

			




	554
	
	
		
    /// \brief Gives back the first arc of the path


			




	
	552
	
		
    /// \brief The first arc of the path


			




	555
	553
	
		
    const Arc& front() const {


			




	...
	...
	
		
@@ -586,3 +584,3 @@


			




	586
	584
	
		

			




	587
	
	
		
    /// \brief Gives back the last arc of the path.


			




	
	585
	
		
    /// \brief The last arc of the path.


			




	588
	586
	
		
    const Arc& back() const {


			




	...
	...
	
		
@@ -619,5 +617,5 @@


			




	619
	617
	
		

			




	620
	
	
		
    /// \brief Splicing the given path to the current path.


			




	
	618
	
		
    /// \brief Splice a path to the back of the current path.


			




	621
	619
	
		
    ///


			




	622
	
	
		
    /// It splices the \c tpath to the back of the current path and \c


			




	
	620
	
		
    /// It splices \c tpath to the back of the current path and \c


			




	623
	621
	
		
    /// tpath becomes empty. The time complexity of this function is


			




	...
	...
	
		
@@ -638,5 +636,5 @@


			




	638
	636
	
		

			




	639
	
	
		
    /// \brief Splicing the given path to the current path.


			




	
	637
	
		
    /// \brief Splice a path to the front of the current path.


			




	640
	638
	
		
    ///


			




	641
	
	
		
    /// It splices the \c tpath before the current path and \c tpath


			




	
	639
	
		
    /// It splices \c tpath before the current path and \c tpath


			




	642
	640
	
		
    /// becomes empty. The time complexity of this function


			




	...
	...
	
		
@@ -657,3 +655,3 @@


			




	657
	655
	
		

			




	658
	
	
		
    /// \brief Splicing the given path into the current path.


			




	
	656
	
		
    /// \brief Splice a path into the current path.


			




	659
	657
	
		
    ///


			




	...
	...
	
		
@@ -661,4 +659,4 @@


			




	661
	659
	
		
    /// position of \c it iterator and \c tpath becomes empty. The


			




	662
	
	
		
    /// time complexity of this function is O(1). If the \c it is \c


			




	663
	
	
		
    /// INVALID then it will splice behind the current path.


			




	
	660
	
		
    /// time complexity of this function is O(1). If the \c it is


			




	
	661
	
		
    /// \c INVALID then it will splice behind the current path.


			




	664
	662
	
		
    void splice(ArcIt it, ListPath& tpath) {


			




	...
	...
	
		
@@ -690,11 +688,11 @@


			




	690
	688
	
		

			




	691
	
	
		
    /// \brief Spliting the current path.


			




	
	689
	
		
    /// \brief Split the current path.


			




	692
	690
	
		
    ///


			




	693
	
	
		
    /// It splits the current path into two parts. The part before \c


			




	694
	
	
		
    /// it iterator will remain in the current path and the part from


			




	695
	
	
		
    /// the it will put into the \c tpath. If the \c tpath had arcs


			




	696
	
	
		
    /// before the operation they will be removed first.  The time


			




	697
	
	
		
    /// complexity of this function is O(1) plus the clearing of \c


			




	698
	
	
		
    /// tpath. If the \c it is \c INVALID then it just clears \c


			




	699
	
	
		
    /// tpath.


			




	
	691
	
		
    /// It splits the current path into two parts. The part before


			




	
	692
	
		
    /// the iterator \c it will remain in the current path and the part


			




	
	693
	
		
    /// starting with


			




	
	694
	
		
    /// \c it will put into \c tpath. If \c tpath have arcs


			




	
	695
	
		
    /// before the operation they are removed first.  The time


			




	
	696
	
		
    /// complexity of this function is O(1) plus the the time of emtying


			




	
	697
	
		
    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath


			




	700
	698
	
		
    void split(ArcIt it, ListPath& tpath) {


			




	...
	...
	
		
@@ -740,9 +738,12 @@


			




	740
	738
	
		
  /// lemon path type stores just this list. As a consequence it


			




	741
	
	
		
  /// cannot enumerate the nodes in the path and the zero length paths


			




	742
	
	
		
  /// cannot store the source.


			




	
	739
	
		
  /// cannot enumerate the nodes in the path and the source node of


			




	
	740
	
		
  /// a zero length path is undefined.


			




	743
	741
	
		
  ///


			




	744
	
	
		
  /// This implementation is completly static, so it cannot be


			




	745
	
	
		
  /// modified exclude the assign an other path. It is intented to be


			




	746
	
	
		
  /// used when you want to store a large number of paths because it is


			




	747
	
	
		
  /// the most memory efficient path type in the lemon.


			




	
	742
	
		
  /// This implementation is completly static, i.e. it can be copy constucted


			




	
	743
	
		
  /// or copy assigned from another path, but otherwise it cannot be


			




	
	744
	
		
  /// modified.


			




	
	745
	
		
  ///


			




	
	746
	
		
  /// Being the the most memory efficient path type in LEMON,


			




	
	747
	
		
  /// it is intented to be


			




	
	748
	
		
  /// used when you want to store a large number of paths.


			




	748
	749
	
		
  template <typename _Digraph>


			




	...
	...
	
		
@@ -761,4 +762,3 @@


			




	761
	762
	
		
    ///


			




	762
	
	
		
    /// This path can be initialized with any other path type. It just


			




	763
	
	
		
    /// makes a copy of the given path.


			




	
	763
	
		
    /// This path can be initialized from any other path type.


			




	764
	764
	
		
    template <typename CPath>


			




	...
	...
	
		
@@ -777,3 +777,3 @@


			




	777
	777
	
		
    ///


			




	778
	
	
		
    /// This path can be initialized with any other path type. It just


			




	
	778
	
		
    /// This path can be made equal to any other path type. It simply


			




	779
	779
	
		
    /// makes a copy of the given path.


			




	...
	...
	
		
@@ -833,3 +833,3 @@


			




	833
	833
	
		

			




	834
	
	
		
    /// \brief Gives back the nth arc.


			




	
	834
	
		
    /// \brief The nth arc.


			




	835
	835
	
		
    ///


			




	...
	...
	
		
@@ -840,3 +840,3 @@


			




	840
	840
	
		

			




	841
	
	
		
    /// \brief Initializes arc iterator to point to the nth arc.


			




	
	841
	
		
    /// \brief The arc iterator pointing to the nth arc.


			




	842
	842
	
		
    ArcIt nthIt(int n) const {


			




	...
	...
	
		
@@ -845,9 +845,9 @@


			




	845
	845
	
		

			




	846
	
	
		
    /// \brief Gives back the length of the path.


			




	
	846
	
		
    /// \brief The length of the path.


			




	847
	847
	
		
    int length() const { return len; }


			




	848
	848
	
		

			




	849
	
	
		
    /// \brief Returns true when the path is empty.


			




	
	849
	
		
    /// \brief Return true when the path is empty.


			




	850
	850
	
		
    int empty() const { return len == 0; }


			




	851
	851
	
		

			




	852
	
	
		
    /// \break Erase all arc in the digraph.


			




	
	852
	
		
    /// \break Erase all arcs in the digraph.


			




	853
	853
	
		
    void clear() {


			




	...
	...
	
		
@@ -858,3 +858,3 @@


			




	858
	858
	
		

			




	859
	
	
		
    /// \brief Gives back the first arc of the path.


			




	
	859
	
		
    /// \brief The first arc of the path.


			




	860
	860
	
		
    const Arc& front() const {


			




	...
	...
	
		
@@ -863,3 +863,3 @@


			




	863
	863
	
		

			




	864
	
	
		
    /// \brief Gives back the last arc of the path.


			




	
	864
	
		
    /// \brief The last arc of the path.


			




	865
	865
	
		
    const Arc& back() const {

			




        

    

    

    

        

            

                

                    lemon/path_utils.h
                

                

                  
                  
                  
                  Ignore white space
                  2 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -92,5 +92,5 @@


			




	92
	92
	
		

			




	93
	
	
		
  /// \brief Make of copy of a path.


			




	
	93
	
		
  /// \brief Make a copy of a path.


			




	94
	94
	
		
  ///


			




	95
	
	
		
  ///  Make of copy of a path.


			




	
	95
	
		
  ///  This function makes a copy of a path.


			




	96
	96
	
		
  template <typename Target, typename Source>


			




	...
	...
	
		
@@ -101,5 +101,6 @@


			




	101
	101
	
		

			




	102
	
	
		
  /// \brief Checks the path's consistency.


			




	
	102
	
		
  /// \brief Check the consistency of a path.


			




	103
	103
	
		
  ///


			




	104
	
	
		
  /// Checks that each arc's target is the next's source. 


			




	
	104
	
		
  /// This function checks that the target of each arc is the same


			




	
	105
	
		
  /// as the source of the next one. 


			




	105
	106
	
		
  /// 


			




	...
	...
	
		
@@ -119,5 +120,5 @@


			




	119
	120
	
		

			




	120
	
	
		
  /// \brief Gives back the source of the path


			




	
	121
	
		
  /// \brief The source of a path


			




	121
	122
	
		
  ///


			




	122
	
	
		
  /// Gives back the source of the path.


			




	
	123
	
		
  /// This function returns the source of the given path.


			




	123
	124
	
		
  template <typename Digraph, typename Path>


			




	...
	...
	
		
@@ -127,5 +128,5 @@


			




	127
	128
	
		

			




	128
	
	
		
  /// \brief Gives back the target of the path


			




	
	129
	
		
  /// \brief The target of a path


			




	129
	130
	
		
  ///


			




	130
	
	
		
  /// Gives back the target of the path.


			




	
	131
	
		
  /// This function returns the target of the given path.


			




	131
	132
	
		
  template <typename Digraph, typename Path>


			




	...
	...
	
		
@@ -135,11 +136,11 @@


			




	135
	136
	
		

			




	136
	
	
		
  /// \brief Class which helps to iterate the nodes of a path


			




	
	137
	
		
  /// \brief Class which helps to iterate through the nodes of a path


			




	137
	138
	
		
  ///


			




	138
	139
	
		
  /// In a sense, the path can be treated as a list of arcs. The


			




	139
	
	
		
  /// lemon path type stores just this list. As a consequence it


			




	
	140
	
		
  /// lemon path type stores only this list. As a consequence, it


			




	140
	141
	
		
  /// cannot enumerate the nodes in the path and the zero length paths


			




	141
	
	
		
  /// cannot store the node.


			




	
	142
	
		
  /// cannot have a source node.


			




	142
	143
	
		
  ///


			




	143
	144
	
		
  /// This class implements the node iterator of a path structure. To


			




	144
	
	
		
  /// provide this feature, the underlying digraph should be given to


			




	
	145
	
		
  /// provide this feature, the underlying digraph should be passed to


			




	145
	146
	
		
  /// the constructor of the iterator.


			




        

    






    
    



    


    

     
    
0 comments (0 inline)