lemon/path.h
changeset 565 7ab97e2a0c33
parent 517 2b6d5d22bb23
child 751 f5f260a63a9b
child 802 994c7df296c9
equal deleted inserted replaced
14:a3302a0b5143 15:ba43a09e5283
    38 
    38 
    39 
    39 
    40   /// \brief A structure for representing directed paths in a digraph.
    40   /// \brief A structure for representing directed paths in a digraph.
    41   ///
    41   ///
    42   /// A structure for representing directed path in a digraph.
    42   /// A structure for representing directed path in a digraph.
    43   /// \tparam _Digraph The digraph type in which the path is.
    43   /// \tparam GR The digraph type in which the path is.
    44   ///
    44   ///
    45   /// In a sense, the path can be treated as a list of arcs. The
    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
    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
    47   /// cannot enumerate the nodes of the path and the source node of
    48   /// a zero length path is undefined.
    48   /// a zero length path is undefined.
    50   /// This implementation is a back and front insertable and erasable
    50   /// This implementation is a back and front insertable and erasable
    51   /// path type. It can be indexed in O(1) time. The front and back
    51   /// path type. It can be indexed in O(1) time. The front and back
    52   /// insertion and erase is done in O(1) (amortized) time. The
    52   /// insertion and erase is done in O(1) (amortized) time. The
    53   /// implementation uses two vectors for storing the front and back
    53   /// implementation uses two vectors for storing the front and back
    54   /// insertions.
    54   /// insertions.
    55   template <typename _Digraph>
    55   template <typename GR>
    56   class Path {
    56   class Path {
    57   public:
    57   public:
    58 
    58 
    59     typedef _Digraph Digraph;
    59     typedef GR Digraph;
    60     typedef typename Digraph::Arc Arc;
    60     typedef typename Digraph::Arc Arc;
    61 
    61 
    62     /// \brief Default constructor
    62     /// \brief Default constructor
    63     ///
    63     ///
    64     /// Default constructor
    64     /// Default constructor
   135     /// \brief Reset the path to an empty one.
   135     /// \brief Reset the path to an empty one.
   136     void clear() { head.clear(); tail.clear(); }
   136     void clear() { head.clear(); tail.clear(); }
   137 
   137 
   138     /// \brief The nth arc.
   138     /// \brief The nth arc.
   139     ///
   139     ///
   140     /// \pre n is in the [0..length() - 1] range
   140     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   141     const Arc& nth(int n) const {
   141     const Arc& nth(int n) const {
   142       return n < int(head.size()) ? *(head.rbegin() + n) :
   142       return n < int(head.size()) ? *(head.rbegin() + n) :
   143         *(tail.begin() + (n - head.size()));
   143         *(tail.begin() + (n - head.size()));
   144     }
   144     }
   145 
   145 
   146     /// \brief Initialize arc iterator to point to the nth arc
   146     /// \brief Initialize arc iterator to point to the nth arc
   147     ///
   147     ///
   148     /// \pre n is in the [0..length() - 1] range
   148     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   149     ArcIt nthIt(int n) const {
   149     ArcIt nthIt(int n) const {
   150       return ArcIt(*this, n);
   150       return ArcIt(*this, n);
   151     }
   151     }
   152 
   152 
   153     /// \brief The first arc of the path
   153     /// \brief The first arc of the path
   226   };
   226   };
   227 
   227 
   228   /// \brief A structure for representing directed paths in a digraph.
   228   /// \brief A structure for representing directed paths in a digraph.
   229   ///
   229   ///
   230   /// A structure for representing directed path in a digraph.
   230   /// A structure for representing directed path in a digraph.
   231   /// \tparam _Digraph The digraph type in which the path is.
   231   /// \tparam GR The digraph type in which the path is.
   232   ///
   232   ///
   233   /// In a sense, the path can be treated as a list of arcs. The
   233   /// In a sense, the path can be treated as a list of arcs. The
   234   /// lemon path type stores just this list. As a consequence it
   234   /// lemon path type stores just this list. As a consequence it
   235   /// cannot enumerate the nodes in the path and the zero length paths
   235   /// cannot enumerate the nodes in the path and the zero length paths
   236   /// cannot store the source.
   236   /// cannot store the source.
   238   /// This implementation is a just back insertable and erasable path
   238   /// This implementation is a just back insertable and erasable path
   239   /// type. It can be indexed in O(1) time. The back insertion and
   239   /// type. It can be indexed in O(1) time. The back insertion and
   240   /// erasure is amortized O(1) time. This implementation is faster
   240   /// erasure is amortized O(1) time. This implementation is faster
   241   /// then the \c Path type because it use just one vector for the
   241   /// then the \c Path type because it use just one vector for the
   242   /// arcs.
   242   /// arcs.
   243   template <typename _Digraph>
   243   template <typename GR>
   244   class SimplePath {
   244   class SimplePath {
   245   public:
   245   public:
   246 
   246 
   247     typedef _Digraph Digraph;
   247     typedef GR Digraph;
   248     typedef typename Digraph::Arc Arc;
   248     typedef typename Digraph::Arc Arc;
   249 
   249 
   250     /// \brief Default constructor
   250     /// \brief Default constructor
   251     ///
   251     ///
   252     /// Default constructor
   252     /// Default constructor
   327     /// \brief Reset the path to an empty one.
   327     /// \brief Reset the path to an empty one.
   328     void clear() { data.clear(); }
   328     void clear() { data.clear(); }
   329 
   329 
   330     /// \brief The nth arc.
   330     /// \brief The nth arc.
   331     ///
   331     ///
   332     /// \pre n is in the [0..length() - 1] range
   332     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   333     const Arc& nth(int n) const {
   333     const Arc& nth(int n) const {
   334       return data[n];
   334       return data[n];
   335     }
   335     }
   336 
   336 
   337     /// \brief  Initializes arc iterator to point to the nth arc.
   337     /// \brief  Initializes arc iterator to point to the nth arc.
   390   };
   390   };
   391 
   391 
   392   /// \brief A structure for representing directed paths in a digraph.
   392   /// \brief A structure for representing directed paths in a digraph.
   393   ///
   393   ///
   394   /// A structure for representing directed path in a digraph.
   394   /// A structure for representing directed path in a digraph.
   395   /// \tparam _Digraph The digraph type in which the path is.
   395   /// \tparam GR The digraph type in which the path is.
   396   ///
   396   ///
   397   /// In a sense, the path can be treated as a list of arcs. The
   397   /// In a sense, the path can be treated as a list of arcs. The
   398   /// lemon path type stores just this list. As a consequence it
   398   /// lemon path type stores just this list. As a consequence it
   399   /// cannot enumerate the nodes in the path and the zero length paths
   399   /// cannot enumerate the nodes in the path and the zero length paths
   400   /// cannot store the source.
   400   /// cannot store the source.
   402   /// This implementation is a back and front insertable and erasable
   402   /// This implementation is a back and front insertable and erasable
   403   /// path type. It can be indexed in O(k) time, where k is the rank
   403   /// path type. It can be indexed in O(k) time, where k is the rank
   404   /// of the arc in the path. The length can be computed in O(n)
   404   /// of the arc in the path. The length can be computed in O(n)
   405   /// time. The front and back insertion and erasure is O(1) time
   405   /// time. The front and back insertion and erasure is O(1) time
   406   /// and it can be splited and spliced in O(1) time.
   406   /// and it can be splited and spliced in O(1) time.
   407   template <typename _Digraph>
   407   template <typename GR>
   408   class ListPath {
   408   class ListPath {
   409   public:
   409   public:
   410 
   410 
   411     typedef _Digraph Digraph;
   411     typedef GR Digraph;
   412     typedef typename Digraph::Arc Arc;
   412     typedef typename Digraph::Arc Arc;
   413 
   413 
   414   protected:
   414   protected:
   415 
   415 
   416     // the std::list<> is incompatible
   416     // the std::list<> is incompatible
   505     };
   505     };
   506 
   506 
   507     /// \brief The nth arc.
   507     /// \brief The nth arc.
   508     ///
   508     ///
   509     /// This function looks for the nth arc in O(n) time.
   509     /// This function looks for the nth arc in O(n) time.
   510     /// \pre n is in the [0..length() - 1] range
   510     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   511     const Arc& nth(int n) const {
   511     const Arc& nth(int n) const {
   512       Node *node = first;
   512       Node *node = first;
   513       for (int i = 0; i < n; ++i) {
   513       for (int i = 0; i < n; ++i) {
   514         node = node->next;
   514         node = node->next;
   515       }
   515       }
   730   };
   730   };
   731 
   731 
   732   /// \brief A structure for representing directed paths in a digraph.
   732   /// \brief A structure for representing directed paths in a digraph.
   733   ///
   733   ///
   734   /// A structure for representing directed path in a digraph.
   734   /// A structure for representing directed path in a digraph.
   735   /// \tparam _Digraph The digraph type in which the path is.
   735   /// \tparam GR The digraph type in which the path is.
   736   ///
   736   ///
   737   /// In a sense, the path can be treated as a list of arcs. The
   737   /// In a sense, the path can be treated as a list of arcs. The
   738   /// lemon path type stores just this list. As a consequence it
   738   /// lemon path type stores just this list. As a consequence it
   739   /// cannot enumerate the nodes in the path and the source node of
   739   /// cannot enumerate the nodes in the path and the source node of
   740   /// a zero length path is undefined.
   740   /// a zero length path is undefined.
   744   /// modified.
   744   /// modified.
   745   ///
   745   ///
   746   /// Being the the most memory efficient path type in LEMON,
   746   /// Being the the most memory efficient path type in LEMON,
   747   /// it is intented to be
   747   /// it is intented to be
   748   /// used when you want to store a large number of paths.
   748   /// used when you want to store a large number of paths.
   749   template <typename _Digraph>
   749   template <typename GR>
   750   class StaticPath {
   750   class StaticPath {
   751   public:
   751   public:
   752 
   752 
   753     typedef _Digraph Digraph;
   753     typedef GR Digraph;
   754     typedef typename Digraph::Arc Arc;
   754     typedef typename Digraph::Arc Arc;
   755 
   755 
   756     /// \brief Default constructor
   756     /// \brief Default constructor
   757     ///
   757     ///
   758     /// Default constructor
   758     /// Default constructor
   831       int idx;
   831       int idx;
   832     };
   832     };
   833 
   833 
   834     /// \brief The nth arc.
   834     /// \brief The nth arc.
   835     ///
   835     ///
   836     /// \pre n is in the [0..length() - 1] range
   836     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   837     const Arc& nth(int n) const {
   837     const Arc& nth(int n) const {
   838       return arcs[n];
   838       return arcs[n];
   839     }
   839     }
   840 
   840 
   841     /// \brief The arc iterator pointing to the nth arc.
   841     /// \brief The arc iterator pointing to the nth arc.