lemon/concepts/path.h
changeset 808 9c428bb2b105
parent 559 c5fd2d996909
child 976 426a704d7483
equal deleted inserted replaced
11:62f45f90425f 12:7ff945a3768a
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 ///\ingroup concept
    19 ///\ingroup concept
    20 ///\file
    20 ///\file
    21 ///\brief Classes for representing paths in digraphs.
    21 ///\brief The concept of paths
    22 ///
    22 ///
    23 
    23 
    24 #ifndef LEMON_CONCEPTS_PATH_H
    24 #ifndef LEMON_CONCEPTS_PATH_H
    25 #define LEMON_CONCEPTS_PATH_H
    25 #define LEMON_CONCEPTS_PATH_H
    26 
    26 
    36     /// \brief A skeleton structure for representing directed paths in
    36     /// \brief A skeleton structure for representing directed paths in
    37     /// a digraph.
    37     /// a digraph.
    38     ///
    38     ///
    39     /// A skeleton structure for representing directed paths in a
    39     /// A skeleton structure for representing directed paths in a
    40     /// digraph.
    40     /// digraph.
       
    41     /// In a sense, a path can be treated as a list of arcs.
       
    42     /// LEMON path types just store this list. As a consequence, they cannot
       
    43     /// enumerate the nodes on the path directly and a zero length path
       
    44     /// cannot store its source node.
       
    45     ///
       
    46     /// The arcs of a path should be stored in the order of their directions,
       
    47     /// i.e. the target node of each arc should be the same as the source
       
    48     /// node of the next arc. This consistency could be checked using
       
    49     /// \ref checkPath().
       
    50     /// The source and target nodes of a (consistent) path can be obtained
       
    51     /// using \ref pathSource() and \ref pathTarget().
       
    52     ///
       
    53     /// A path can be constructed from another path of any type using the
       
    54     /// copy constructor or the assignment operator.
       
    55     ///
    41     /// \tparam GR The digraph type in which the path is.
    56     /// \tparam GR The digraph type in which the path is.
    42     ///
       
    43     /// In a sense, the path can be treated as a list of arcs. The
       
    44     /// lemon path type stores just this list. As a consequence it
       
    45     /// cannot enumerate the nodes in the path and the zero length
       
    46     /// paths cannot store the source.
       
    47     ///
       
    48     template <typename GR>
    57     template <typename GR>
    49     class Path {
    58     class Path {
    50     public:
    59     public:
    51 
    60 
    52       /// Type of the underlying digraph.
    61       /// Type of the underlying digraph.
    57       class ArcIt;
    66       class ArcIt;
    58 
    67 
    59       /// \brief Default constructor
    68       /// \brief Default constructor
    60       Path() {}
    69       Path() {}
    61 
    70 
    62       /// \brief Template constructor
    71       /// \brief Template copy constructor
    63       template <typename CPath>
    72       template <typename CPath>
    64       Path(const CPath& cpath) {}
    73       Path(const CPath& cpath) {}
    65 
    74 
    66       /// \brief Template assigment
    75       /// \brief Template assigment operator
    67       template <typename CPath>
    76       template <typename CPath>
    68       Path& operator=(const CPath& cpath) {
    77       Path& operator=(const CPath& cpath) {
    69         ignore_unused_variable_warning(cpath);
    78         ignore_unused_variable_warning(cpath);
    70         return *this;
    79         return *this;
    71       }
    80       }
    72 
    81 
    73       /// Length of the path ie. the number of arcs in the path.
    82       /// Length of the path, i.e. the number of arcs on the path.
    74       int length() const { return 0;}
    83       int length() const { return 0;}
    75 
    84 
    76       /// Returns whether the path is empty.
    85       /// Returns whether the path is empty.
    77       bool empty() const { return true;}
    86       bool empty() const { return true;}
    78 
    87 
    79       /// Resets the path to an empty path.
    88       /// Resets the path to an empty path.
    80       void clear() {}
    89       void clear() {}
    81 
    90 
    82       /// \brief LEMON style iterator for path arcs
    91       /// \brief LEMON style iterator for enumerating the arcs of a path.
    83       ///
    92       ///
    84       /// This class is used to iterate on the arcs of the paths.
    93       /// LEMON style iterator class for enumerating the arcs of a path.
    85       class ArcIt {
    94       class ArcIt {
    86       public:
    95       public:
    87         /// Default constructor
    96         /// Default constructor
    88         ArcIt() {}
    97         ArcIt() {}
    89         /// Invalid constructor
    98         /// Invalid constructor
    90         ArcIt(Invalid) {}
    99         ArcIt(Invalid) {}
    91         /// Constructor for first arc
   100         /// Sets the iterator to the first arc of the given path
    92         ArcIt(const Path &) {}
   101         ArcIt(const Path &) {}
    93 
   102 
    94         /// Conversion to Arc
   103         /// Conversion to \c Arc
    95         operator Arc() const { return INVALID; }
   104         operator Arc() const { return INVALID; }
    96 
   105 
    97         /// Next arc
   106         /// Next arc
    98         ArcIt& operator++() {return *this;}
   107         ArcIt& operator++() {return *this;}
    99 
   108 
   190 
   199 
   191 
   200 
   192     /// \brief A skeleton structure for path dumpers.
   201     /// \brief A skeleton structure for path dumpers.
   193     ///
   202     ///
   194     /// A skeleton structure for path dumpers. The path dumpers are
   203     /// A skeleton structure for path dumpers. The path dumpers are
   195     /// the generalization of the paths. The path dumpers can
   204     /// the generalization of the paths, they can enumerate the arcs
   196     /// enumerate the arcs of the path wheter in forward or in
   205     /// of the path either in forward or in backward order.
   197     /// backward order.  In most time these classes are not used
   206     /// These classes are typically not used directly, they are rather
   198     /// directly rather it used to assign a dumped class to a real
   207     /// used to be assigned to a real path type.
   199     /// path type.
       
   200     ///
   208     ///
   201     /// The main purpose of this concept is that the shortest path
   209     /// The main purpose of this concept is that the shortest path
   202     /// algorithms can enumerate easily the arcs in reverse order.
   210     /// algorithms can enumerate the arcs easily in reverse order.
   203     /// If we would like to give back a real path from these
   211     /// In LEMON, such algorithms give back a (reverse) path dumper that
   204     /// algorithms then we should create a temporarly path object. In
   212     /// can be assigned to a real path. The dumpers can be implemented as
   205     /// LEMON such algorithms gives back a path dumper what can
       
   206     /// assigned to a real path and the dumpers can be implemented as
       
   207     /// an adaptor class to the predecessor map.
   213     /// an adaptor class to the predecessor map.
   208     ///
   214     ///
   209     /// \tparam GR The digraph type in which the path is.
   215     /// \tparam GR The digraph type in which the path is.
   210     ///
       
   211     /// The paths can be constructed from any path type by a
       
   212     /// template constructor or a template assignment operator.
       
   213     template <typename GR>
   216     template <typename GR>
   214     class PathDumper {
   217     class PathDumper {
   215     public:
   218     public:
   216 
   219 
   217       /// Type of the underlying digraph.
   220       /// Type of the underlying digraph.
   218       typedef GR Digraph;
   221       typedef GR Digraph;
   219       /// Arc type of the underlying digraph.
   222       /// Arc type of the underlying digraph.
   220       typedef typename Digraph::Arc Arc;
   223       typedef typename Digraph::Arc Arc;
   221 
   224 
   222       /// Length of the path ie. the number of arcs in the path.
   225       /// Length of the path, i.e. the number of arcs on the path.
   223       int length() const { return 0;}
   226       int length() const { return 0;}
   224 
   227 
   225       /// Returns whether the path is empty.
   228       /// Returns whether the path is empty.
   226       bool empty() const { return true;}
   229       bool empty() const { return true;}
   227 
   230 
   228       /// \brief Forward or reverse dumping
   231       /// \brief Forward or reverse dumping
   229       ///
   232       ///
   230       /// If the RevPathTag is defined and true then reverse dumping
   233       /// If this tag is defined to be \c True, then reverse dumping
   231       /// is provided in the path dumper. In this case instead of the
   234       /// is provided in the path dumper. In this case, \c RevArcIt
   232       /// ArcIt the RevArcIt iterator should be implemented in the
   235       /// iterator should be implemented instead of \c ArcIt iterator.
   233       /// dumper.
       
   234       typedef False RevPathTag;
   236       typedef False RevPathTag;
   235 
   237 
   236       /// \brief LEMON style iterator for path arcs
   238       /// \brief LEMON style iterator for enumerating the arcs of a path.
   237       ///
   239       ///
   238       /// This class is used to iterate on the arcs of the paths.
   240       /// LEMON style iterator class for enumerating the arcs of a path.
   239       class ArcIt {
   241       class ArcIt {
   240       public:
   242       public:
   241         /// Default constructor
   243         /// Default constructor
   242         ArcIt() {}
   244         ArcIt() {}
   243         /// Invalid constructor
   245         /// Invalid constructor
   244         ArcIt(Invalid) {}
   246         ArcIt(Invalid) {}
   245         /// Constructor for first arc
   247         /// Sets the iterator to the first arc of the given path
   246         ArcIt(const PathDumper&) {}
   248         ArcIt(const PathDumper&) {}
   247 
   249 
   248         /// Conversion to Arc
   250         /// Conversion to \c Arc
   249         operator Arc() const { return INVALID; }
   251         operator Arc() const { return INVALID; }
   250 
   252 
   251         /// Next arc
   253         /// Next arc
   252         ArcIt& operator++() {return *this;}
   254         ArcIt& operator++() {return *this;}
   253 
   255 
   258         /// Comparison operator
   260         /// Comparison operator
   259         bool operator<(const ArcIt&) const {return false;}
   261         bool operator<(const ArcIt&) const {return false;}
   260 
   262 
   261       };
   263       };
   262 
   264 
   263       /// \brief LEMON style iterator for path arcs
   265       /// \brief LEMON style iterator for enumerating the arcs of a path
       
   266       /// in reverse direction.
   264       ///
   267       ///
   265       /// This class is used to iterate on the arcs of the paths in
   268       /// LEMON style iterator class for enumerating the arcs of a path
   266       /// reverse direction.
   269       /// in reverse direction.
   267       class RevArcIt {
   270       class RevArcIt {
   268       public:
   271       public:
   269         /// Default constructor
   272         /// Default constructor
   270         RevArcIt() {}
   273         RevArcIt() {}
   271         /// Invalid constructor
   274         /// Invalid constructor
   272         RevArcIt(Invalid) {}
   275         RevArcIt(Invalid) {}
   273         /// Constructor for first arc
   276         /// Sets the iterator to the last arc of the given path
   274         RevArcIt(const PathDumper &) {}
   277         RevArcIt(const PathDumper &) {}
   275 
   278 
   276         /// Conversion to Arc
   279         /// Conversion to \c Arc
   277         operator Arc() const { return INVALID; }
   280         operator Arc() const { return INVALID; }
   278 
   281 
   279         /// Next arc
   282         /// Next arc
   280         RevArcIt& operator++() {return *this;}
   283         RevArcIt& operator++() {return *this;}
   281 
   284