COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2335:27aa03cd3121 in lemon-0.x


Ignore:
Timestamp:
01/08/07 11:39:59 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3123
Message:

New path concept and path structures

TODO: BellmanFord::negativeCycle()

Files:
2 added
16 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r2316 r2335  
    8787        lemon/nagamochi_ibaraki.h \
    8888        lemon/path.h \
     89        lemon/path_utils.h \
    8990        lemon/polynomial.h \
    9091        lemon/preflow.h \
    … …  
    122123        lemon/bits/map_extender.h \
    123124        lemon/bits/mingw32_time.h \
     125        lemon/bits/path_dump.h \
    124126        lemon/bits/traits.h \
    125127        lemon/bits/utility.h \

  • lemon/bellman_ford.h

    r2260 r2335  
    2626
    2727#include <lemon/list_graph.h>
     28#include <lemon/bits/path_dump.h>
    2829#include <lemon/bits/invalid.h>
    2930#include <lemon/error.h>
    … …  
    428429    ///
    429430    /// \warning The paths with limited edge number cannot be retrieved
    430     /// easily with \ref getPath() or \ref predEdge() functions. If you
     431    /// easily with \ref path() or \ref predEdge() functions. If you
    431432    /// need the shortest path and not just the distance you should store
    432433    /// after each iteration the \ref predEdgeMap() map and manually build
    … …  
    541542    ///
    542543    /// \warning The paths with limited edge number cannot be retrieved
    543     /// easily with \ref getPath() or \ref predEdge() functions. If you
     544    /// easily with \ref path() or \ref predEdge() functions. If you
    544545    /// need the shortest path and not just the distance you should store
    545546    /// after each iteration the \ref predEdgeMap() map and manually build
    … …  
    659660    };
    660661
    661     /// \brief Copies the shortest path to \c t into \c p
     662    typedef PredMapPath<Graph, PredMap> Path;
     663
     664    /// \brief Gives back the shortest path.
    662665    ///   
    663     /// This function copies the shortest path to \c t into \c p.
    664     /// If it \c t is a source itself or unreachable, then it does not
    665     /// alter \c p.
    666     ///
    667     /// \return Returns \c true if a path to \c t was actually copied to \c p,
    668     /// \c false otherwise.
    669     /// \sa DirPath
    670     template <typename Path>
    671     bool getPath(Path &p, Node t) {
    672       if(reached(t)) {
    673         p.clear();
    674         typename Path::Builder b(p);
    675         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
    676           b.pushFront(predEdge(t));
    677         b.commit();
    678         return true;
    679       }
    680       return false;
    681     }
    682 
    683     /// \brief Copies a negative cycle into path \c p.
    684     ///   
    685     /// This function copies a negative cycle into path \c p.
    686     /// If the algorithm have not found yet negative cycle it will not change
    687     /// the given path and gives back false.
    688     ///
    689     /// \return Returns \c true if a cycle was actually copied to \c p,
    690     /// \c false otherwise.
    691     /// \sa DirPath
    692     template <typename Path>
    693     bool getNegativeCycle(Path& p) {
    694       typename Graph::template NodeMap<int> state(*graph, 0);
    695       for (ActiveIt it(*this); it != INVALID; ++it) {
    696         if (state[it] == 0) {
    697           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
    698             if (state[t] == 0) {
    699               state[t] = 1;
    700             } else if (state[t] == 2) {
    701               break;
    702             } else {
    703               p.clear();
    704               typename Path::Builder b(p);
    705               b.setStartNode(t);
    706               b.pushFront(predEdge(t));
    707               for(Node s = predNode(t); s != t; s = predNode(s)) {
    708                 b.pushFront(predEdge(s));
    709               }
    710               b.commit();
    711               return true;
    712             }
    713           }
    714           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
    715             if (state[t] == 1) {
    716               state[t] = 2;
    717             } else {
    718               break;
    719             }
    720           }
    721         }
    722       }
    723       return false;
    724     }
     666    /// Gives back the shortest path.
     667    /// \pre The \c t should be reachable from the source.
     668    Path path(Node t)
     669    {
     670      return Path(*graph, *_pred, t);
     671    }
     672
     673
     674    // TODO : implement negative cycle
     675//     /// \brief Gives back a negative cycle.
     676//     ///   
     677//     /// This function gives back a negative cycle.
     678//     /// If the algorithm have not found yet negative cycle it will give back
     679//     /// an empty path.
     680//     Path negativeCycle() {
     681//       typename Graph::template NodeMap<int> state(*graph, 0);
     682//       for (ActiveIt it(*this); it != INVALID; ++it) {
     683//         if (state[it] == 0) {
     684//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
     685//             if (state[t] == 0) {
     686//               state[t] = 1;
     687//             } else if (state[t] == 2) {
     688//               break;
     689//             } else {
     690//               p.clear();
     691//               typename Path::Builder b(p);
     692//               b.setStartNode(t);
     693//               b.pushFront(predEdge(t));
     694//               for(Node s = predNode(t); s != t; s = predNode(s)) {
     695//                 b.pushFront(predEdge(s));
     696//               }
     697//               b.commit();
     698//               return true;
     699//             }
     700//           }
     701//           for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
     702//             if (state[t] == 1) {
     703//               state[t] = 2;
     704//             } else {
     705//               break;
     706//             }
     707//           }
     708//         }
     709//       }
     710//       return false;
     711//     }
    725712         
    726713    /// \brief The distance of a node from the root.

  • lemon/bfs.h

    r2307 r2335  
    2626#include <lemon/list_graph.h>
    2727#include <lemon/graph_utils.h>
     28#include <lemon/bits/path_dump.h>
    2829#include <lemon/bits/invalid.h>
    2930#include <lemon/error.h>
    … …  
    677678    ///@{
    678679
    679     ///Copies the shortest path to \c t into \c p
    680    
    681     ///This function copies the shortest path to \c t into \c p.
    682     ///If \c t is a source itself or unreachable, then it does not
    683     ///alter \c p.
    684     ///\return Returns \c true if a path to \c t was actually copied to \c p,
    685     ///\c false otherwise.
    686     ///\sa DirPath
    687     template<class P>
    688     bool getPath(P &p,Node t)
    689     {
    690       if(reached(t)) {
    691         p.clear();
    692         typename P::Builder b(p);
    693         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
    694           b.pushFront(predEdge(t));
    695         b.commit();
    696         return true;
    697       }
    698       return false;
     680    typedef PredMapPath<Graph, PredMap> Path;
     681
     682    ///Gives back the shortest path.
     683   
     684    ///Gives back the shortest path.
     685    ///\pre The \c t should be reachable from the source.
     686    Path path(Node t)
     687    {
     688      return Path(*G, *_pred, t);
    699689    }
    700690

  • lemon/concepts/path.h

    r2260 r2335  
    2727
    2828#include <lemon/bits/invalid.h>
     29#include <lemon/bits/utility.h>
    2930#include <lemon/concept_check.h>
    3031
    3132namespace lemon {
    3233  namespace concepts {
     34
    3335    /// \addtogroup concept
    3436    /// @{
    3537
    36 
    37     //! \brief A skeleton structure for representing directed paths in a graph.
    38     //!
    39     //! A skeleton structure for representing directed paths in a graph.
    40     //! \param _Graph The graph type in which the path is.
    41     //!
    42     //! In a sense, the path can be treated as a graph, for it has \c NodeIt
    43     //! and \c EdgeIt with the same usage. These types converts to the \c Node
    44     //! and \c Edge of the original graph.
    45     template<typename _Graph>
     38    /// \brief A skeleton structure for representing directed paths in
     39    /// a graph.
     40    ///
     41    /// A skeleton structure for representing directed paths in a
     42    /// graph. 
     43    /// \param _Graph The graph type in which the path is.
     44    ///
     45    /// In a sense, the path can be treated as a list of edges. 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
     48    /// paths cannot store the source.
     49    ///
     50    template <typename _Graph>
    4651    class Path {
    4752    public:
    … …  
    5156      /// Edge type of the underlying graph.
    5257      typedef typename Graph::Edge Edge;
    53       /// Node type of the underlying graph.
    54       typedef typename Graph::Node Node;
    55 
    56       class NodeIt;
     58
    5759      class EdgeIt;
    5860
    59       /// \param _g The graph in which the path is.
    60       ///
    61       Path(const Graph &_g) {
    62         ignore_unused_variable_warning(_g);
    63       }
     61      /// \brief Default constructor
     62      Path() {}
     63
     64      /// \brief Template constructor
     65      template <typename CPath>
     66      Path(const CPath& cpath) {}
     67
     68      /// \brief Template assigment
     69      template <typename CPath>
     70      Path& operator=(const CPath& cpath) {}
    6471
    6572      /// Length of the path ie. the number of edges in the path.
    66       int length() const {return 0;}
     73      int length() const { return 0;}
    6774
    6875      /// Returns whether the path is empty.
    … …  
    7279      void clear() {}
    7380
    74       /// \brief Starting point of the path.
     81      /// \brief Lemon style iterator for path edges
    7582      ///
    76       /// Starting point of the path.
    77       /// Returns INVALID if the path is empty.
    78       Node target() const {return INVALID;}
    79       /// \brief End point of the path.
    80       ///
    81       /// End point of the path.
    82       /// Returns INVALID if the path is empty.
    83       Node source() const {return INVALID;}
    84 
    85       /// \brief The target of an edge.
    86       ///
    87       /// Returns node iterator pointing to the target node of the
    88       /// given edge iterator.
    89       NodeIt target(const EdgeIt&) const {return INVALID;}
    90 
    91       /// \brief The source of an edge.
    92       ///
    93       /// Returns node iterator pointing to the source node of the
    94       /// given edge iterator.
    95       NodeIt source(const EdgeIt&) const {return INVALID;}
    96 
    97       /// \brief Iterator class to iterate on the nodes of the paths
    98       ///
    99       /// This class is used to iterate on the nodes of the paths
    100       ///
    101       /// Of course it converts to Graph::Node.
    102       class NodeIt {
    103       public:
    104         /// Default constructor
    105         NodeIt() {}
    106         /// Invalid constructor
    107         NodeIt(Invalid) {}
    108         /// Constructor with starting point
    109         NodeIt(const Path &) {}
    110 
    111         ///Conversion to Graph::Node
    112         operator Node() const { return INVALID; }
    113         /// Next node
    114         NodeIt& operator++() {return *this;}
    115 
    116         /// Comparison operator
    117         bool operator==(const NodeIt&) const {return true;}
    118         /// Comparison operator
    119         bool operator!=(const NodeIt&) const {return true;}
    120         /// Comparison operator
    121         bool operator<(const NodeIt&) const {return false;}
    122 
    123       };
    124 
    125       /// \brief Iterator class to iterate on the edges of the paths
    126       ///
    127       /// This class is used to iterate on the edges of the paths
    128       ///
    129       /// Of course it converts to Graph::Edge
     83      /// This class is used to iterate on the edges of the paths.
    13084      class EdgeIt {
    13185      public:
    … …  
    13488        /// Invalid constructor
    13589        EdgeIt(Invalid) {}
    136         /// Constructor with starting point
     90        /// Constructor for first edge
    13791        EdgeIt(const Path &) {}
    13892
     93        /// Conversion to Edge
    13994        operator Edge() const { return INVALID; }
    14095
    … …  
    151106      };
    152107
    153 
    154       friend class Builder;
    155 
    156       /// \brief Class to build paths
    157       ///
    158       /// This class is used to fill a path with edges.
    159       ///
    160       /// You can push new edges to the front and to the back of the path in
    161       /// arbitrary order then you should commit these changes to the graph.
    162       ///
    163       /// While the builder is active (after the first modifying
    164       /// operation and until the call of \ref commit()) the
    165       /// underlining Path is in a "transitional" state (operations on
    166       /// it have undefined result).
    167       class Builder {
    168       public:
    169 
    170         /// Constructor
    171 
    172         /// Constructor
    173         /// \param _path the path you want to fill in.
    174         ///
    175 
    176         Builder(Path &_path) { ignore_unused_variable_warning(_path); }
    177 
    178         /// Sets the starting node of the path.
    179 
    180         /// Sets the starting node of the path. Edge added to the path
    181         /// afterwards have to be incident to this node.
    182         /// You \em must start building an empty path with these functions.
    183         /// (And you \em must \em not use it later).
    184         /// \sa pushFront()
    185         /// \sa pushBack()
    186         void setStartNode(const Node &) {}
    187 
    188         ///Push a new edge to the front of the path
    189 
    190         ///Push a new edge to the front of the path.
    191         ///If the path is empty, you \em must call \ref setStartNode() before
    192         ///the first use of \ref pushFront().
    193         void pushFront(const Edge&) {}
    194 
    195         ///Push a new edge to the back of the path
    196 
    197         ///Push a new edge to the back of the path.
    198         ///If the path is empty, you \em must call \ref setStartNode() before
    199         ///the first use of \ref pushBack().
    200         void pushBack(const Edge&) {}
    201 
    202         ///Commit the changes to the path.
    203 
    204         ///Commit the changes to the path.
    205         ///
    206         void commit() {}
    207 
    208         ///Reserve (front) storage for the builder in advance.
    209 
    210         ///If you know a reasonable upper bound on the number of the edges
    211         ///to add to the front of the path,
    212         ///using this function you may speed up the building.
    213         void reserveFront(size_t) {}
    214         ///Reserve (back) storage for the builder in advance.
    215 
    216         ///If you know a reasonable upper bound on the number of the edges
    217         ///to add to the back of the path,
    218         ///using this function you may speed up the building.
    219         void reserveBack(size_t) {}
    220       };
    221 
    222108      template <typename _Path>
    223109      struct Constraints {
    224         void constraints() {
    225           typedef typename _Path::Node Node;
    226           typedef typename _Path::NodeIt NodeIt;
    227           typedef typename Graph::Node GraphNode;
    228 
    229           typedef typename _Path::Edge Edge;
    230           typedef typename _Path::EdgeIt EdgeIt;
    231           typedef typename Graph::Edge GraphEdge;
    232 
    233           typedef typename _Path::Builder Builder;
    234 
    235           path = _Path(graph);
    236 
    237           bool b = cpath.empty();
    238           int l = cpath.length();
    239 
    240           Node gn;
    241           Edge ge;
    242           gn = cpath.source();
    243           gn = cpath.target();
    244 
    245           NodeIt nit;
    246           EdgeIt eit(INVALID);
    247           nit = path.source(eit);
    248           nit = path.target(eit);
    249          
    250           nit = NodeIt();
    251           nit = NodeIt(cpath);
    252           nit = INVALID;
    253           gn = nit;
    254           ++nit;
    255           b = nit == nit;
    256           b = nit != nit;
    257           b = nit < nit;
    258 
    259           eit = EdgeIt();
    260           eit = EdgeIt(cpath);
    261           eit = INVALID;
    262           ge = eit;
    263           ++eit;
    264           b = eit == eit;
    265           b = eit != eit;
    266           b = eit < eit;
    267 
    268           size_t st = 0;
    269 
    270           Builder builder(path);
    271           builder.setStartNode(gn);
    272           builder.pushFront(ge);
    273           builder.pushBack(ge);
    274           builder.commit();
    275           builder.reserveFront(st);
    276           builder.reserveBack(st);
    277          
     110        void constraints() {
     111          Path<Graph> pc;
     112          _Path p, pp(pc);
     113          int l = p.length();
     114          int e = p.empty();
     115          p.clear();
     116
     117          p = pc;
     118
     119          typename _Path::EdgeIt id, ii(INVALID), i(p);
     120
     121          ++i;
     122          typename Graph::Edge ed = i;
     123
     124          e = (i == ii);
     125          e = (i != ii);
     126          e = (i < ii);
     127
    278128          ignore_unused_variable_warning(l);
    279           ignore_unused_variable_warning(b);
    280         }
    281 
    282         const Graph& graph;
    283         const _Path& cpath;
    284         _Path& path;
     129          ignore_unused_variable_warning(pp);
     130          ignore_unused_variable_warning(e);
     131          ignore_unused_variable_warning(id);
     132          ignore_unused_variable_warning(ii);
     133          ignore_unused_variable_warning(ed);
     134        }
    285135      };
    286136
    287137    };
    288138
    289   ///@}
     139    namespace _path_bits {
     140     
     141      template <typename _Graph, typename _Path, typename RevPathTag = void>
     142      struct PathDumperConstraints {
     143        void constraints() {
     144          int l = p.length();
     145          int e = p.empty();
     146
     147          typename _Path::EdgeIt id, ii(INVALID), i(p);
     148
     149          ++i;
     150          typename _Graph::Edge ed = i;
     151
     152          e = (i == ii);
     153          e = (i != ii);
     154          e = (i < ii);
     155
     156          ignore_unused_variable_warning(l);
     157          ignore_unused_variable_warning(e);
     158          ignore_unused_variable_warning(id);
     159          ignore_unused_variable_warning(ii);
     160          ignore_unused_variable_warning(ed);
     161        }
     162        _Path& p;
     163      };
     164
     165      template <typename _Graph, typename _Path>
     166      struct PathDumperConstraints<
     167        _Graph, _Path,
     168        typename enable_if<typename _Path::RevPathTag, void>::type
     169      > {
     170        void constraints() {
     171          int l = p.length();
     172          int e = p.empty();
     173
     174          typename _Path::RevIt id, ii(INVALID), i(p);
     175
     176          ++i;
     177          typename _Graph::Edge ed = i;
     178
     179          e = (i == ii);
     180          e = (i != ii);
     181          e = (i < ii);
     182
     183          ignore_unused_variable_warning(l);
     184          ignore_unused_variable_warning(e);
     185          ignore_unused_variable_warning(id);
     186          ignore_unused_variable_warning(ii);
     187          ignore_unused_variable_warning(ed);
     188        }
     189        _Path& p;
     190      };
     191   
     192    }
     193
     194
     195    /// \brief A skeleton structure for path dumpers.
     196    ///
     197    /// A skeleton structure for path dumpers. The path dumpers are
     198    /// the generalization of the paths. The path dumpers can
     199    /// enumerate the edges of the path wheter in forward or in
     200    /// backward order.  In most time these classes are not used
     201    /// directly rather it used to assign a dumped class to a real
     202    /// path type.
     203    ///
     204    /// The main purpose of this concept is that the shortest path
     205    /// algorithms can enumerate easily the edges in reverse order.
     206    /// If we would like to give back a real path from these
     207    /// algorithms then we should create a temporarly path object. In
     208    /// Lemon such algorithms gives back a path dumper what can
     209    /// assigned to a real path and the dumpers can be implemented as
     210    /// an adaptor class to the predecessor map.
     211
     212    /// \param _Graph  The graph type in which the path is.
     213    ///
     214    /// The paths can be constructed from any path type by a
     215    /// template constructor or a template assignment operator.
     216    ///
     217    template <typename _Graph>
     218    class PathDumper {
     219    public:
     220
     221      /// Type of the underlying graph.
     222      typedef _Graph Graph;
     223      /// Edge type of the underlying graph.
     224      typedef typename Graph::Edge Edge;
     225
     226      /// Length of the path ie. the number of edges in the path.
     227      int length() const { return 0;}
     228
     229      /// Returns whether the path is empty.
     230      bool empty() const { return true;}
     231
     232      /// \brief Forward or reverse dumping
     233      ///
     234      /// If the RevPathTag is defined and true then reverse dumping
     235      /// is provided in the path proxy. In this case instead of the
     236      /// EdgeIt the RevIt iterator should be implemented in the
     237      /// proxy.
     238      typedef False RevPathTag;
     239
     240      /// \brief Lemon style iterator for path edges
     241      ///
     242      /// This class is used to iterate on the edges of the paths.
     243      class EdgeIt {
     244      public:
     245        /// Default constructor
     246        EdgeIt() {}
     247        /// Invalid constructor
     248        EdgeIt(Invalid) {}
     249        /// Constructor for first edge
     250        EdgeIt(const PathDumper&) {}
     251
     252        /// Conversion to Edge
     253        operator Edge() const { return INVALID; }
     254
     255        /// Next edge
     256        EdgeIt& operator++() {return *this;}
     257
     258        /// Comparison operator
     259        bool operator==(const EdgeIt&) const {return true;}
     260        /// Comparison operator
     261        bool operator!=(const EdgeIt&) const {return true;}
     262        /// Comparison operator
     263        bool operator<(const EdgeIt&) const {return false;}
     264
     265      };
     266
     267      /// \brief Lemon style iterator for path edges
     268      ///
     269      /// This class is used to iterate on the edges of the paths in
     270      /// reverse direction.
     271      class RevIt {
     272      public:
     273        /// Default constructor
     274        RevIt() {}
     275        /// Invalid constructor
     276        RevIt(Invalid) {}
     277        /// Constructor for first edge
     278        RevIt(const PathDumper &) {}
     279
     280        /// Conversion to Edge
     281        operator Edge() const { return INVALID; }
     282
     283        /// Next edge
     284        RevIt& operator++() {return *this;}
     285
     286        /// Comparison operator
     287        bool operator==(const RevIt&) const {return true;}
     288        /// Comparison operator
     289        bool operator!=(const RevIt&) const {return true;}
     290        /// Comparison operator
     291        bool operator<(const RevIt&) const {return false;}
     292
     293      };
     294
     295      template <typename _Path>
     296      struct Constraints {
     297        void constraints() {
     298          function_requires<_path_bits::
     299            PathDumperConstraints<Graph, _Path> >();
     300        }
     301      };
     302
     303    };
     304
     305
     306    ///@}
    290307  }
    291308

  • lemon/dag_shortest_path.h

    r2260 r2335  
    723723    ///@{
    724724
    725     /// \brief Copies the shortest path to \c t into \c p
    726     ///   
    727     /// This function copies the shortest path to \c t into \c p.
    728     /// If it \c t is a source itself or unreachable, then it does not
    729     /// alter \c p.
    730     ///
    731     /// \return Returns \c true if a path to \c t was actually copied to \c p,
    732     /// \c false otherwise.
    733     /// \sa DirPath
    734     template <typename Path>
    735     bool getPath(Path &p, Node t) {
    736       if(reached(t)) {
    737         p.clear();
    738         typename Path::Builder b(p);
    739         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
    740           b.pushFront(predEdge(t));
    741         b.commit();
    742         return true;
    743       }
    744       return false;
     725    typedef PredMapPath<Graph, PredMap> Path;
     726
     727    ///Gives back the shortest path.
     728   
     729    ///Gives back the shortest path.
     730    ///\pre The \c t should be reachable from the source.
     731    Path path(Node t)
     732    {
     733      return Path(*graph, *_pred, t);
    745734    }
    746735         

  • lemon/dfs.h

    r2260 r2335  
    2626#include <lemon/list_graph.h>
    2727#include <lemon/graph_utils.h>
     28#include <lemon/bits/path_dump.h>
    2829#include <lemon/bits/invalid.h>
    2930#include <lemon/error.h>
    … …  
    653654    ///@{
    654655
    655     ///Copies the path to \c t on the DFS tree into \c p
    656    
    657     ///This function copies the path to \c t on the DFS tree  into \c p.
    658     ///If \c t is a source itself or unreachable, then it does not
    659     ///alter \c p.
    660     ///
    661     ///\return Returns \c true if a path to \c t was actually copied to \c p,
    662     ///\c false otherwise.
    663     ///\sa DirPath
    664     template<class P>
    665     bool getPath(P &p,Node t)
    666     {
    667       if(reached(t)) {
    668         p.clear();
    669         typename P::Builder b(p);
    670         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
    671           b.pushFront(predEdge(t));
    672         b.commit();
    673         return true;
    674       }
    675       return false;
     656    typedef PredMapPath<Graph, PredMap> Path;
     657
     658    ///Gives back the shortest path.
     659   
     660    ///Gives back the shortest path.
     661    ///\pre The \c t should be reachable from the source.
     662    Path path(Node t)
     663    {
     664      return Path(*G, *_pred, t);
    676665    }
    677666

  • lemon/dijkstra.h

    r2269 r2335  
    2828#include <lemon/list_graph.h>
    2929#include <lemon/bin_heap.h>
     30#include <lemon/bits/path_dump.h>
    3031#include <lemon/bits/invalid.h>
    3132#include <lemon/error.h>
    3233#include <lemon/maps.h>
     34
    3335
    3436namespace lemon {
    … …  
    718720    ///@{
    719721
    720     ///Copies the shortest path to \c t into \c p
    721    
    722     ///This function copies the shortest path to \c t into \c p.
    723     ///If it \c t is a source itself or unreachable, then it does not
    724     ///alter \c p.
    725     ///\return Returns \c true if a path to \c t was actually copied to \c p,
    726     ///\c false otherwise.
    727     ///\sa DirPath
    728     template<class P>
    729     bool getPath(P &p,Node t)
    730     {
    731       if(reached(t)) {
    732         p.clear();
    733         typename P::Builder b(p);
    734         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
    735           b.pushFront(predEdge(t));
    736         b.commit();
    737         return true;
    738       }
    739       return false;
    740     }
    741          
     722    typedef PredMapPath<Graph, PredMap> Path;
     723
     724    ///Gives back the shortest path.
     725   
     726    ///Gives back the shortest path.
     727    ///\pre The \c t should be reachable from the source.
     728    Path path(Node t)
     729    {
     730      return Path(*G, *_pred, t);
     731    }
     732
    742733    ///The distance of a node from the root.
    743734

  • lemon/floyd_warshall.h

    r2260 r2335  
    2727#include <lemon/list_graph.h>
    2828#include <lemon/graph_utils.h>
     29#include <lemon/bits/path_dump.h>
    2930#include <lemon/bits/invalid.h>
    3031#include <lemon/error.h>
    … …  
    481482    ///@{
    482483
    483     /// \brief Copies the shortest path to \c t into \c p
    484     ///   
    485     /// This function copies the shortest path to \c t into \c p.
    486     /// If it \c t is a source itself or unreachable, then it does not
    487     /// alter \c p.
    488     /// \return Returns \c true if a path to \c t was actually copied to \c p,
    489     /// \c false otherwise.
    490     /// \sa DirPath
    491     template <typename Path>
    492     bool getPath(Path &p, Node source, Node target) {
    493       if (connected(source, target)) {
    494         p.clear();
    495         typename Path::Builder b(target);
    496         for(b.setStartNode(target); predEdge(source, target) != INVALID;
    497             target = predNode(target)) {
    498           b.pushFront(predEdge(source, target));
    499         }
    500         b.commit();
    501         return true;
    502       }
    503       return false;
     484    typedef PredMatrixMapPath<Graph, PredMap> Path;
     485
     486    ///Gives back the shortest path.
     487   
     488    ///Gives back the shortest path.
     489    ///\pre The \c t should be reachable from the \c t.
     490    Path path(Node s, Node t)
     491    {
     492      return Path(*graph, *_pred, s, t);
    504493    }
    505494         

  • lemon/johnson.h

    r2263 r2335  
    2929#include <lemon/dijkstra.h>
    3030#include <lemon/bellman_ford.h>
     31#include <lemon/bits/path_dump.h>
    3132#include <lemon/bits/invalid.h>
    3233#include <lemon/error.h>
    … …  
    630631    ///@{
    631632
    632     /// \brief Copies the shortest path to \c t into \c p
    633     ///   
    634     /// This function copies the shortest path to \c t into \c p.
    635     /// If it \c t is a source itself or unreachable, then it does not
    636     /// alter \c p.
    637     /// \return Returns \c true if a path to \c t was actually copied to \c p,
    638     /// \c false otherwise.
    639     /// \sa DirPath
    640     template <typename Path>
    641     bool getPath(Path &p, Node source, Node target) {
    642       if (connected(source, target)) {
    643         p.clear();
    644         typename Path::Builder b(target);
    645         for(b.setStartNode(target); predEdge(source, target) != INVALID;
    646             target = predNode(target)) {
    647           b.pushFront(predEdge(source, target));
    648         }
    649         b.commit();
    650         return true;
    651       }
    652       return false;
     633    typedef PredMatrixMapPath<Graph, PredMap> Path;
     634
     635    ///Gives back the shortest path.
     636   
     637    ///Gives back the shortest path.
     638    ///\pre The \c t should be reachable from the \c t.
     639    Path path(Node s, Node t)
     640    {
     641      return Path(*graph, *_pred, s, t);
    653642    }
    654643         

  • lemon/path.h

    r2247 r2335  
    2929#include <algorithm>
    3030
     31#include <lemon/path_utils.h>
    3132#include <lemon/error.h>
    3233#include <lemon/bits/invalid.h>
    … …  
    3839
    3940
    40   //! \brief A structure for representing directed paths in a graph.
    41   //!
    42   //! A structure for representing directed path in a graph.
    43   //! \param Graph The graph type in which the path is.
    44   //!
    45   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    46   //! and \c EdgeIt with the same usage. These types converts to the \c Node
    47   //! and \c Edge of the original graph.
    48   //!
    49   //! \todo Thoroughfully check all the range and consistency tests.
    50   template<typename Graph>
     41  /// \brief A structure for representing directed paths in a graph.
     42  ///
     43  /// A structure for representing directed path in a graph.
     44  /// \param Graph The graph type in which the path is.
     45  ///
     46  /// In a sense, the path can be treated as a list of edges. The
     47  /// lemon path type stores just this list. As a consequence it
     48  /// cannot enumerate the nodes in the path and the zero length paths
     49  /// cannot store the source.
     50  ///
     51  /// This implementation is a back and front insertable and erasable
     52  /// path type. It can be indexed in O(1) time. The front and back
     53  /// insertion and erasure is amortized O(1) time. The
     54  /// impelementation is based on two opposite organized vectors.
     55  template <typename _Graph>
    5156  class Path {
    5257  public:
    53     /// Edge type of the underlying graph.
     58
     59    typedef _Graph Graph;
    5460    typedef typename Graph::Edge Edge;
    55     /// Node type of the underlying graph.
    56     typedef typename Graph::Node Node;
    57 
    58     class NodeIt;
    59     class EdgeIt;
    60 
    61     struct PathError : public LogicError {
    62       virtual const char* what() const throw() {
    63         return "lemon::PathError";
    64       }     
    65     };
    66 
    67   public:
    68 
    69     /// \brief Constructor
    70     ///
    71     /// Constructor
    72     /// \param _G The graph in which the path is.
    73     Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
    74    
    75     /// \brief Subpath constructor.
    76     ///
    77     /// Subpath defined by two nodes.
    78     /// \warning It is an error if the two edges are not in order!
    79     Path(const Path &other, const NodeIt &a, const NodeIt &b) {
    80       graph = other.graph;
    81       start = a;
    82       edges.insert(edges.end(),
    83                    other.edges.begin() + a.id, other.edges.begin() + b.id);
    84     }
    85 
    86     /// \brief Subpath constructor.
    87     ///
    88     /// Subpath defined by two edges. Contains edges in [a,b)
    89     /// \warning It is an error if the two edges are not in order!
    90     Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
    91       graph = other.graph;
    92       start = graph->source(a);
    93       edges.insert(edges.end(),
    94                    other.edges.begin() + a.id, other.edges.begin() + b.id);
    95     }
    96 
    97     /// \brief Length of the path.
    98     ///
    99     /// The number of the edges in the path. It can be zero if the
    100     /// path has only one node or it is empty.
    101     int length() const { return edges.size(); }
    102 
    103     /// \brief Returns whether the path is empty.
    104     ///
    105     /// Returns true when the path does not contain neither edge nor
    106     /// node.
    107     bool empty() const { return start == INVALID; }
    108 
    109     /// \brief Resets the path to an empty path.
    110     ///
    111     /// Resets the path to an empty path.
    112     void clear() { edges.clear(); start = INVALID; }
    113 
    114     /// \brief Starting point of the path.
    115     ///
    116     /// Starting point of the path.
    117     /// Returns INVALID if the path is empty.
    118     Node source() const {
    119       return start;
    120     }
    121     /// \brief End point of the path.
    122     ///
    123     /// End point of the path.
    124     /// Returns INVALID if the path is empty.
    125     Node target() const {
    126       return length() == 0 ? start : graph->target(edges[length()-1]);
    127     }
    128 
    129     /// \brief Gives back a node iterator to point to the node of a
    130     /// given index.
    131     ///
    132     /// Gives back a node iterator to point to the node of a given
    133     /// index.
    134     /// \pre n should less or equal to \c length()
    135     NodeIt nthNode(int n) const {
    136       return NodeIt(*this, n);
    137     }
    138 
    139     /// \brief Gives back an edge iterator to point to the edge of a
    140     /// given index.
    141     ///
    142     /// Gives back an edge iterator to point to the node of a given
    143     /// index. 
    144     /// \pre n should less than \c length()
    145     EdgeIt nthEdge(int n) const {
    146       return EdgeIt(*this, n);
    147     }
    148 
    149     /// \brief Returns node iterator pointing to the source node of the
    150     /// given edge iterator.
    151     ///
    152     /// Returns node iterator pointing to the source node of the given
    153     /// edge iterator.
    154     NodeIt source(const EdgeIt& e) const {
    155       return NodeIt(*this, e.id);
    156     }
    157 
    158     /// \brief Returns node iterator pointing to the target node of the
    159     /// given edge iterator.
    160     ///
    161     /// Returns node iterator pointing to the target node of the given
    162     /// edge iterator.
    163     NodeIt target(const EdgeIt& e) const {
    164       return NodeIt(*this, e.id + 1);
    165     }
    166 
    167 
    168     /// \brief Iterator class to iterate on the nodes of the paths
    169     ///
    170     /// This class is used to iterate on the nodes of the paths
    171     ///
    172     /// Of course it converts to Graph::Node
    173     class NodeIt {
    174       friend class Path;
    175     public:
    176 
    177       /// \brief Default constructor
    178       ///
    179       /// Default constructor
    180       NodeIt() {}
    181 
    182       /// \brief Invalid constructor
    183       ///
    184       /// Invalid constructor
    185       NodeIt(Invalid) : id(-1), path(0) {}
    186 
    187       /// \brief Constructor with starting point
    188       ///
    189       /// Constructor with starting point
    190       NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
    191         if (id > path->length()) id = -1;
    192       }
    193 
    194       /// \brief Conversion to Graph::Node
    195       ///
    196       /// Conversion to Graph::Node
    197       operator Node() const {
    198         if (id > 0) {
    199           return path->graph->target(path->edges[id - 1]);
    200         } else if (id == 0) {
    201           return path->start;
    202         } else {
    203           return INVALID;
    204         }
    205       }
    206 
    207       /// \brief Steps to the next node
    208       ///
    209       /// Steps to the next node
    210       NodeIt& operator++() {
    211         ++id;
    212         if (id > path->length()) id = -1;
    213         return *this;
    214       }
    215 
    216       /// \brief Comparison operator
    217       ///
    218       /// Comparison operator
    219       bool operator==(const NodeIt& n) const { return id == n.id; }
    220 
    221       /// \brief Comparison operator
    222       ///
    223       /// Comparison operator
    224       bool operator!=(const NodeIt& n) const { return id != n.id; }
    225 
    226       /// \brief Comparison operator
    227       ///
    228       /// Comparison operator
    229       bool operator<(const NodeIt& n) const { return id < n.id; }
    230 
    231     private:
    232       int id;
    233       const Path *path;
    234     };
    235 
    236     /// \brief Iterator class to iterate on the edges of the paths
    237     ///
    238     /// This class is used to iterate on the edges of the paths
    239     /// Of course it converts to Graph::Edge
     61
     62    /// \brief Default constructor
     63    ///
     64    /// Default constructor
     65    Path() {}
     66
     67    /// \brief Template copy constructor
     68    ///
     69    /// This path can be initialized with any other path type. It just
     70    /// makes a copy of the given path.
     71    template <typename CPath>
     72    Path(const CPath& cpath) {
     73      copyPath(*this, cpath);
     74    }
     75
     76    /// \brief Template copy assignment
     77    ///
     78    /// This path can be initialized with any other path type. It just
     79    /// makes a copy of the given path.
     80    template <typename CPath>
     81    Path& operator=(const CPath& cpath) {
     82      copyPath(*this, cpath);
     83      return *this;
     84    }
     85
     86    /// \brief Lemon style iterator for path edges
     87    ///
     88    /// This class is used to iterate on the edges of the paths.
    24089    class EdgeIt {
    24190      friend class Path;
    24291    public:
    243 
    24492      /// \brief Default constructor
    245       ///
     93      EdgeIt() {}
     94      /// \brief Invalid constructor
     95      EdgeIt(Invalid) : path(0), idx(-1) {}
     96      /// \brief Initializate the constructor to the first edge of path
     97      EdgeIt(const Path &_path)
     98        : path(&_path), idx(_path.empty() ? -1 : 0) {}
     99
     100    private:
     101
     102      EdgeIt(const Path &_path, int _idx)
     103        : idx(_idx), path(&_path) {}
     104
     105    public:
     106
     107      /// \brief Conversion to Edge
     108      operator const Edge&() const {
     109        return path->nth(idx);
     110      }
     111
     112      /// \brief Next edge
     113      EdgeIt& operator++() {
     114        ++idx;
     115        if (idx >= path->length()) idx = -1;
     116        return *this;
     117      }
     118
     119      /// \brief Comparison operator
     120      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
     121      /// \brief Comparison operator
     122      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
     123      /// \brief Comparison operator
     124      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     125
     126    private:
     127      const Path *path;
     128      int idx;
     129    };
     130
     131    /// \brief Length of the path.
     132    int length() const { return head.size() + tail.size(); }
     133    /// \brief Returns whether the path is empty.
     134    bool empty() const { return head.empty() && tail.empty(); }
     135
     136    /// \brief Resets the path to an empty path.
     137    void clear() { head.clear(); tail.clear(); }
     138
     139    /// \brief Gives back the nth edge.
     140    ///
     141    /// \pre n is in the [0..length() - 1] range
     142    const Edge& nth(int n) const {
     143      return n < (int)head.size() ? *(head.rbegin() + n) :
     144        *(tail.begin() + (n - head.size()));
     145    }
     146
     147    /// \brief Initializes edge iterator to point to the nth edge
     148    ///
     149    /// \pre n is in the [0..length() - 1] range
     150    EdgeIt nthIt(int n) const {
     151      return EdgeIt(*this, n);
     152    }
     153
     154    /// \brief Gives back the first edge of the path
     155    const Edge& front() const {
     156      return head.empty() ? tail.front() : head.back();
     157    }
     158
     159    /// \brief Add a new edge before the current path
     160    void addFront(const Edge& edge) {
     161      head.push_back(edge);
     162    }
     163
     164    /// \brief Erase the first edge of the path
     165    void eraseFront() {
     166      if (!head.empty()) {
     167        head.pop_back();
     168      } else {
     169        head.clear();
     170        int halfsize = tail.size() / 2;
     171        head.resize(halfsize);
     172        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
     173                  head.rbegin());
     174        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
     175        tail.resize(tail.size() - halfsize - 1);
     176      }
     177    }
     178
     179    /// \brief Gives back the last edge of the path
     180    const Edge& back() const {
     181      return tail.empty() ? head.front() : tail.back();
     182    }
     183
     184    /// \brief Add a new edge behind the current path
     185    void addBack(const Edge& edge) {
     186      tail.push_back(edge);
     187    }
     188
     189    /// \brief Erase the last edge of the path
     190    void eraseBack() {
     191      if (!tail.empty()) {
     192        tail.pop_back();
     193      } else {
     194        int halfsize = head.size() / 2;
     195        tail.resize(halfsize);
     196        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
     197                  tail.rbegin());
     198        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
     199        head.resize(head.size() - halfsize - 1);
     200      }
     201    }
     202
     203
     204
     205    typedef True BuildTag;
     206
     207    template <typename CPath>
     208    void build(const CPath& path) {
     209      int len = path.length();
     210      tail.reserve(len);
     211      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     212        tail.push_back(it);
     213      }
     214    }
     215
     216    template <typename CPath>
     217    void buildRev(const CPath& path) {
     218      int len = path.length();
     219      head.reserve(len);
     220      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     221        head.push_back(it);
     222      }
     223    }
     224
     225  protected:
     226    typedef std::vector<Edge> Container;
     227    Container head, tail;
     228
     229  };
     230
     231  /// \brief A structure for representing directed paths in a graph.
     232  ///
     233  /// A structure for representing directed path in a graph.
     234  /// \param Graph The graph type in which the path is.
     235  ///
     236  /// In a sense, the path can be treated as a list of edges. The
     237  /// lemon path type stores just this list. As a consequence it
     238  /// cannot enumerate the nodes in the path and the zero length paths
     239  /// cannot store the source.
     240  ///
     241  /// This implementation is a just back insertable and erasable path
     242  /// type. It can be indexed in O(1) time. The back insertion and
     243  /// erasure is amortized O(1) time. This implementation is faster
     244  /// then the \c Path type because it use just one vector for the
     245  /// edges.
     246  template <typename _Graph>
     247  class SimplePath {
     248  public:
     249
     250    typedef _Graph Graph;
     251    typedef typename Graph::Edge Edge;
     252
     253    /// \brief Default constructor
     254    ///
     255    /// Default constructor
     256    SimplePath() {}
     257
     258    /// \brief Template copy constructor
     259    ///
     260    /// This path can be initialized with any other path type. It just
     261    /// makes a copy of the given path.
     262    template <typename CPath>
     263    SimplePath(const CPath& cpath) {
     264      copyPath(*this, cpath);
     265    }
     266
     267    /// \brief Template copy assignment
     268    ///
     269    /// This path can be initialized with any other path type. It just
     270    /// makes a copy of the given path.
     271    template <typename CPath>
     272    SimplePath& operator=(const CPath& cpath) {
     273      copyPath(*this, cpath);
     274      return *this;
     275    }
     276
     277    /// \brief Iterator class to iterate on the edges of the paths
     278    ///
     279    /// This class is used to iterate on the edges of the paths
     280    ///
     281    /// Of course it converts to Graph::Edge
     282    class EdgeIt {
     283      friend class SimplePath;
     284    public:
    246285      /// Default constructor
    247286      EdgeIt() {}
    248 
    249       /// \brief Invalid constructor
    250       ///
    251287      /// Invalid constructor
    252       EdgeIt(Invalid) : id(-1), path(0) {}
    253 
    254       /// \brief Constructor with starting point
    255       ///
     288      EdgeIt(Invalid) : path(0), idx(-1) {}
     289      /// \brief Initializate the constructor to the first edge of path
     290      EdgeIt(const SimplePath &_path)
     291        : path(&_path), idx(_path.empty() ? -1 : 0) {}
     292
     293    private:
     294
    256295      /// Constructor with starting point
    257       EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
    258         if (id >= path->length()) id = -1;
    259       }
    260 
    261       /// \brief Conversion to Graph::Edge
    262       ///
    263       /// Conversion to Graph::Edge
    264       operator Edge() const {
    265         return id != -1 ? path->edges[id] : INVALID;
    266       }
    267 
    268       /// \brief Steps to the next edge
    269       ///
    270       /// Steps to the next edge
     296      EdgeIt(const SimplePath &_path, int _idx)
     297        : idx(_idx), path(&_path) {}
     298
     299    public:
     300
     301      ///Conversion to Graph::Edge
     302      operator const Edge&() const {
     303        return path->nth(idx);
     304      }
     305
     306      /// Next edge
    271307      EdgeIt& operator++() {
    272         ++id;
    273         if (id >= path->length()) id = -1;
     308        ++idx;
     309        if (idx >= path->length()) idx = -1;
    274310        return *this;
    275311      }
    276312
    277       /// \brief Comparison operator
    278       ///
    279313      /// Comparison operator
    280       bool operator==(const EdgeIt& e) const { return id == e.id; }
    281 
    282       /// \brief Comparison operator
    283       ///
     314      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
    284315      /// Comparison operator
    285       bool operator!=(const EdgeIt& e) const { return id != e.id; }
    286 
    287       /// \brief Comparison operator
    288       ///
     316      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
    289317      /// Comparison operator
    290       bool operator<(const EdgeIt& e) const { return id < e.id; }
     318      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
    291319
    292320    private:
    293 
    294       int id;
    295       const Path *path;
     321      const SimplePath *path;
     322      int idx;
    296323    };
    297324
     325    /// \brief Length of the path.
     326    int length() const { return data.size(); }
     327    /// \brief Returns whether the path is empty.
     328    bool empty() const { return data.empty(); }
     329
     330    /// \brief Resets the path to an empty path.
     331    void clear() { data.clear(); }
     332
     333    /// \brief Gives back the nth edge.
     334    ///
     335    /// \pre n is in the [0..length() - 1] range
     336    const Edge& nth(int n) const {
     337      return data[n];
     338    }
     339
     340    /// \brief  Initializes edge iterator to point to the nth edge.
     341    EdgeIt nthIt(int n) const {
     342      return EdgeIt(*this, n);
     343    }
     344
     345    /// \brief Gives back the last edge of the path.
     346    const Edge& back() const {
     347      return data.back();
     348    }
     349
     350    /// \brief Add a new edge behind the current path.
     351    void addBack(const Edge& edge) {
     352      data.push_back(edge);
     353    }
     354
     355    /// \brief Erase the last edge of the path
     356    void eraseBack() {
     357      data.pop_back();
     358    }
     359
     360    typedef True BuildTag;
     361
     362    template <typename CPath>
     363    void build(const CPath& path) {
     364      int len = path.length();
     365      data.resize(len);
     366      int index = 0;
     367      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     368        data[index] = it;;
     369        ++index;
     370      }
     371    }
     372
     373    template <typename CPath>
     374    void buildRev(const CPath& path) {
     375      int len = path.length();
     376      data.resize(len);
     377      int index = len;
     378      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     379        --index;
     380        data[index] = it;;
     381      }
     382    }
     383
    298384  protected:
    299 
    300     const Graph *graph;
    301 
    302385    typedef std::vector<Edge> Container;
    303     Container edges;
    304     Node start;
    305 
     386    Container data;
     387
     388  };
     389
     390  /// \brief A structure for representing directed paths in a graph.
     391  ///
     392  /// A structure for representing directed path in a graph.
     393  /// \param Graph The graph type in which the path is.
     394  ///
     395  /// In a sense, the path can be treated as a list of edges. The
     396  /// lemon path type stores just this list. As a consequence it
     397  /// cannot enumerate the nodes in the path and the zero length paths
     398  /// cannot store the source.
     399  ///
     400  /// This implementation is a back and front insertable and erasable
     401  /// path type. It can be indexed in O(k) time, where k is the rank
     402  /// of the edge in the path. The length can be computed in O(n)
     403  /// time. The front and back insertion and erasure is O(1) time
     404  /// and it can be splited and spliced in O(1) time.
     405  template <typename _Graph>
     406  class ListPath {
    306407  public:
    307408
    308     friend class Builder;
    309 
    310     /// \brief Class to build paths
    311     ///
    312     /// This class is used to fill a path with edges.
    313     ///
    314     /// You can push new edges to the front and to the back of the
    315     /// path in arbitrary order then you should commit these changes
    316     /// to the graph.
    317     ///
    318     /// Fundamentally, for most "Paths" (classes fulfilling the
    319     /// PathConcept) while the builder is active (after the first
    320     /// modifying operation and until the commit()) the original Path
    321     /// is in a "transitional" state (operations on it have undefined
    322     /// result). But in the case of Path the original path remains
    323     /// unchanged until the commit. However we don't recomend that you
    324     /// use this feature.
    325     class Builder {
     409    typedef _Graph Graph;
     410    typedef typename Graph::Edge Edge;
     411
     412  protected:
     413
     414    // the std::list<> is incompatible
     415    // hard to create invalid iterator
     416    struct Node {
     417      Edge edge;
     418      Node *next, *prev;
     419    };
     420
     421    Node *first, *last;
     422
     423    std::allocator<Node> alloc;
     424
     425  public:
     426 
     427    /// \brief Default constructor
     428    ///
     429    /// Default constructor
     430    ListPath() : first(0), last(0) {}
     431
     432    /// \brief Template copy constructor
     433    ///
     434    /// This path can be initialized with any other path type. It just
     435    /// makes a copy of the given path.
     436    template <typename CPath>
     437    ListPath(const CPath& cpath) : first(0), last(0) {
     438      copyPath(*this, cpath);
     439    }
     440
     441    /// \brief Destructor of the path
     442    ///
     443    /// Destructor of the path
     444    ~ListPath() {
     445      clear();
     446    }
     447
     448    /// \brief Template copy assignment
     449    ///
     450    /// This path can be initialized with any other path type. It just
     451    /// makes a copy of the given path.
     452    template <typename CPath>
     453    ListPath& operator=(const CPath& cpath) {
     454      copyPath(*this, cpath);
     455      return *this;
     456    }
     457
     458    /// \brief Iterator class to iterate on the edges of the paths
     459    ///
     460    /// This class is used to iterate on the edges of the paths
     461    ///
     462    /// Of course it converts to Graph::Edge
     463    class EdgeIt {
     464      friend class ListPath;
    326465    public:
    327       /// \brief Constructor
    328       ///
    329       /// Constructor
    330       /// \param _path the path you want to fill in.
    331       Builder(Path &_path) : path(_path), start(INVALID) {}
    332 
    333       /// \brief Destructor
    334       ///
    335       /// Destructor
    336       ~Builder() {
    337         LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
    338                      PathError());
    339       }
    340 
    341       /// \brief Sets the starting node of the path.
    342       ///
    343       /// Sets the starting node of the path. Edge added to the path
    344       /// afterwards have to be incident to this node.  It should be
    345       /// called if and only if the path is empty and before any call
    346       /// to \ref pushFront() or \ref pushBack()
    347       void setStartNode(const Node &_start) {
    348         LEMON_ASSERT(path.empty() && start == INVALID, PathError());
    349         start = _start;
    350       }
    351 
    352       /// \brief Push a new edge to the front of the path
    353       ///
    354       /// Push a new edge to the front of the path. 
    355       /// \sa setStartNode
    356       void pushFront(const Edge& e) {
    357         LEMON_ASSERT(front.empty() ||
    358                      (path.graph->source(front.back()) ==
    359                       path.graph->target(e)), PathError());
    360         LEMON_ASSERT(path.empty() ||
    361                      (path.source() == path.graph->target(e)), PathError());
    362         LEMON_ASSERT(!path.empty() || !front.empty() ||
    363                      (start == path.graph->target(e)), PathError());
    364         front.push_back(e);
    365       }
    366 
    367       /// \brief Push a new edge to the back of the path
    368       ///
    369       /// Push a new edge to the back of the path.
    370       /// \sa setStartNode
    371       void pushBack(const Edge& e) {
    372         LEMON_ASSERT(back.empty() ||
    373                      (path.graph->target(back.back()) ==
    374                       path.graph->source(e)), PathError());
    375         LEMON_ASSERT(path.empty() ||
    376                      (path.target() == path.graph->source(e)), PathError());
    377         LEMON_ASSERT(!path.empty() || !back.empty() ||
    378                      (start == path.graph->source(e)), PathError());
    379         back.push_back(e);
    380       }
    381 
    382       /// \brief Commit the changes to the path.
    383       ///
    384       /// Commit the changes to the path.
    385       void commit() {
    386         if( !front.empty() || !back.empty() || start != INVALID) {
    387           Container tmp;
    388           tmp.reserve(front.size() + back.size() + path.length());
    389           tmp.insert(tmp.end(), front.rbegin(), front.rend());
    390           tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
    391           tmp.insert(tmp.end(), back.begin(), back.end());
    392           path.edges.swap(tmp);
    393           if (!front.empty()) {
    394             path.start = path.graph->source(front.back());
     466      /// Default constructor
     467      EdgeIt() {}
     468      /// Invalid constructor
     469      EdgeIt(Invalid) : path(0), node(0) {}
     470      /// \brief Initializate the constructor to the first edge of path
     471      EdgeIt(const ListPath &_path)
     472        : path(&_path), node(_path.first) {}
     473
     474    protected:
     475
     476      EdgeIt(const ListPath &_path, Node *_node)
     477        : path(&_path), node(_node) {}
     478
     479
     480    public:
     481
     482      ///Conversion to Graph::Edge
     483      operator const Edge&() const {
     484        return node->edge;
     485      }
     486
     487      /// Next edge
     488      EdgeIt& operator++() {
     489        node = node->next;
     490        return *this;
     491      }
     492
     493      /// Comparison operator
     494      bool operator==(const EdgeIt& e) const { return node==e.node; }
     495      /// Comparison operator
     496      bool operator!=(const EdgeIt& e) const { return node!=e.node; }
     497      /// Comparison operator
     498      bool operator<(const EdgeIt& e) const { return node<e.node; }
     499
     500    private:
     501      const ListPath *path;
     502      Node *node;
     503    };
     504
     505    /// \brief Gives back the nth edge.
     506    ///
     507    /// Gives back the nth edge in O(n) time.
     508    /// \pre n is in the [0..length() - 1] range
     509    const Edge& nth(int n) const {
     510      Node *node = first;
     511      for (int i = 0; i < n; ++i) {
     512        node = node->next;
     513      }
     514      return node->edge;
     515    }
     516
     517    /// \brief Initializes edge iterator to point to the nth edge.
     518    EdgeIt nthIt(int n) const {
     519      Node *node = first;
     520      for (int i = 0; i < n; ++i) {
     521        node = node->next;
     522      }
     523      return EdgeIt(*this, node);
     524    }
     525
     526    /// \brief Length of the path.
     527    int length() const {
     528      int len = 0;
     529      Node *node = first;
     530      while (node != 0) {
     531        node = node->next;
     532        ++len;
     533      }
     534      return len;
     535    }
     536
     537    /// \brief Returns whether the path is empty.
     538    bool empty() const { return first == 0; }
     539
     540    /// \brief Resets the path to an empty path.
     541    void clear() {
     542      while (first != 0) {
     543        last = first->next;
     544        alloc.destroy(first);
     545        alloc.deallocate(first, 1);
     546        first = last;
     547      }
     548    }
     549
     550    /// \brief Gives back the first edge of the path
     551    const Edge& front() const {
     552      return first->edge;
     553    }
     554
     555    /// \brief Add a new edge before the current path
     556    void addFront(const Edge& edge) {
     557      Node *node = alloc.allocate(1);
     558      alloc.construct(node, Node());
     559      node->prev = 0;
     560      node->next = first;
     561      node->edge = edge;
     562      if (first) {
     563        first->prev = node;
     564        first = node;
     565      } else {
     566        first = last = node;
     567      }
     568    }
     569
     570    /// \brief Erase the first edge of the path
     571    void eraseFront() {
     572      Node *node = first;
     573      first = first->next;
     574      if (first) {
     575        first->prev = 0;
     576      } else {
     577        last = 0;
     578      }
     579      alloc.destroy(node);
     580      alloc.deallocate(node, 1);
     581    }
     582
     583    /// \brief Gives back the last edge of the path.
     584    const Edge& back() const {
     585      return last->edge;
     586    }
     587
     588    /// \brief Add a new edge behind the current path.
     589    void addBack(const Edge& edge) {
     590      Node *node = alloc.allocate(1);
     591      alloc.construct(node, Node());
     592      node->next = 0;
     593      node->prev = last;
     594      node->edge = edge;
     595      if (last) {
     596        last->next = node;
     597        last = node;
     598      } else {
     599        last = first = node;
     600      }
     601    }
     602
     603    /// \brief Erase the last edge of the path
     604    void eraseBack() {
     605      Node *node = last;
     606      last = last->prev;
     607      if (last) {
     608        last->next = 0;
     609      } else {
     610        first = 0;
     611      }
     612      alloc.destroy(node);
     613      alloc.deallocate(node, 1);
     614    }
     615
     616    /// \brief Splicing the given path to the current path.
     617    ///
     618    /// It splices the \c tpath to the back of the current path and \c
     619    /// tpath becomes empty. The time complexity of this function is
     620    /// O(1).
     621    void spliceBack(ListPath& tpath) {
     622      if (first) {
     623        if (tpath.first) {
     624          last->next = tpath.first;
     625          tpath.first->prev = last;
     626          last = tpath.last;
     627        }
     628      } else {
     629        first = tpath.first;
     630        last = tpath.last;
     631      }
     632      tpath.first = tpath.last = 0;
     633    }
     634
     635    /// \brief Splicing the given path to the current path.
     636    ///
     637    /// It splices the \c tpath before the current path and \c tpath
     638    /// becomes empty. The time complexity of this function
     639    /// is O(1).
     640    void spliceFront(ListPath& tpath) {
     641      if (first) {
     642        if (tpath.first) {
     643          first->prev = tpath.last;
     644          tpath.last->next = first;
     645          first = tpath.first;
     646        }
     647      } else {
     648        first = tpath.first;
     649        last = tpath.last;
     650      }
     651      tpath.first = tpath.last = 0;
     652    }
     653
     654    /// \brief Splicing the given path into the current path.
     655    ///
     656    /// It splices the \c tpath into the current path before the
     657    /// position of \c it iterator and \c tpath becomes empty. The
     658    /// time complexity of this function is O(1). If the \c it is \c
     659    /// INVALID then it will splice behind the current path.
     660    void splice(EdgeIt it, ListPath& tpath) {
     661      if (it.node) {
     662        if (tpath.first) {
     663          tpath.first->prev = it.node->prev;
     664          if (it.node->prev) {
     665            it.node->prev->next = tpath.first;
    395666          } else {
    396             path.start = start;
     667            first = tpath.first;
    397668          }
    398           start = INVALID;
    399           front.clear();
    400           back.clear();
    401         }
    402       }
    403 
    404       /// \brief Reserve storage for the builder in advance.
    405       ///
    406       /// If you know a reasonable upper bound of the number of the
    407       /// edges to add to the front, using this function you can speed
    408       /// up the building.
    409       void reserveFront(size_t r) {front.reserve(r);}
    410 
    411       /// \brief Reserve storage for the builder in advance.
    412       ///
    413       /// If you know a reasonable upper bound of the number of the
    414       /// edges to add to the back, using this function you can speed
    415       /// up the building.
    416       void reserveBack(size_t r) {back.reserve(r);}
     669          it.node->prev = tpath.last;
     670          tpath.last->next = it.node;
     671        }
     672      } else {
     673        if (first) {
     674          if (tpath.first) {
     675            last->next = tpath.first;
     676            tpath.first->prev = last;
     677            last = tpath.last;
     678          }
     679        } else {
     680          first = tpath.first;
     681          last = tpath.last;
     682        }
     683      }
     684      tpath.first = tpath.last = 0;
     685    }
     686
     687    /// \brief Spliting the current path.
     688    ///
     689    /// It splits the current path into two parts. The part before \c
     690    /// it iterator will remain in the current path and the part from
     691    /// the it will put into the \c tpath. If the \c tpath had edges
     692    /// before the operation they will be removed first.  The time
     693    /// complexity of this function is O(1) plus the clearing of \c
     694    /// tpath. If the \c it is \c INVALID then it just clears \c
     695    /// tpath.
     696    void split(EdgeIt it, ListPath& tpath) {
     697      tpath.clear();
     698      if (it.node) {
     699        tpath.first = it.node;
     700        tpath.last = last;
     701        if (it.node->prev) {
     702          last = it.node->prev;
     703          last->next = 0;
     704        } else {
     705          first = last = 0;
     706        }
     707        it.node->prev = 0;
     708      }
     709    }
     710
     711
     712    typedef True BuildTag;
     713
     714    template <typename CPath>
     715    void build(const CPath& path) {
     716      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     717        addBack(it);
     718      }
     719    }
     720
     721    template <typename CPath>
     722    void buildRev(const CPath& path) {
     723      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     724        addFront(it);
     725      }
     726    }
     727
     728  };
     729
     730  /// \brief A structure for representing directed paths in a graph.
     731  ///
     732  /// A structure for representing directed path in a graph.
     733  /// \param Graph The graph type in which the path is.
     734  ///
     735  /// In a sense, the path can be treated as a list of edges. The
     736  /// lemon path type stores just this list. As a consequence it
     737  /// cannot enumerate the nodes in the path and the zero length paths
     738  /// cannot store the source.
     739  ///
     740  /// This implementation is completly static, so it cannot be
     741  /// modified exclude the assign an other path. It is intented to be
     742  /// used when you want to store a large amount paths because it is
     743  /// the most memory efficient path type in the lemon.
     744  template <typename _Graph>
     745  class StaticPath {
     746  public:
     747
     748    typedef _Graph Graph;
     749    typedef typename Graph::Edge Edge;
     750
     751    /// \brief Default constructor
     752    ///
     753    /// Default constructor
     754    StaticPath() : len(0), edges(0) {}
     755   
     756    /// \brief Template copy constructor
     757    ///
     758    /// This path can be initialized with any other path type. It just
     759    /// makes a copy of the given path.
     760    template <typename CPath>
     761    StaticPath(const CPath& cpath) : edges(0) {
     762      copyPath(*this, cpath);
     763    }
     764
     765    /// \brief Destructor of the path
     766    ///
     767    /// Destructor of the path
     768    ~StaticPath() {
     769      if (edges) delete[] edges;
     770    }
     771
     772    /// \brief Template copy assignment
     773    ///
     774    /// This path can be initialized with any other path type. It just
     775    /// makes a copy of the given path.
     776    template <typename CPath>
     777    StaticPath& operator=(const CPath& cpath) {
     778      copyPath(*this, cpath);
     779      return *this;
     780    }
     781
     782    /// \brief Iterator class to iterate on the edges of the paths
     783    ///
     784    /// This class is used to iterate on the edges of the paths
     785    ///
     786    /// Of course it converts to Graph::Edge
     787    class EdgeIt {
     788      friend class StaticPath;
     789    public:
     790      /// Default constructor
     791      EdgeIt() {}
     792      /// Invalid constructor
     793      EdgeIt(Invalid) : path(0), idx(-1) {}
     794      /// Initializate the constructor to the first edge of path
     795      EdgeIt(const StaticPath &_path)
     796        : path(&_path), idx(_path.empty() ? -1 : 0) {}
    417797
    418798    private:
    419799
    420       Path &path;
    421       Container front, back;
    422       Node start;
    423 
     800      /// Constructor with starting point
     801      EdgeIt(const StaticPath &_path, int _idx)
     802        : idx(_idx), path(&_path) {}
     803
     804    public:
     805
     806      ///Conversion to Graph::Edge
     807      operator const Edge&() const {
     808        return path->nth(idx);
     809      }
     810
     811      /// Next edge
     812      EdgeIt& operator++() {
     813        ++idx;
     814        if (idx >= path->length()) idx = -1;
     815        return *this;
     816      }
     817
     818      /// Comparison operator
     819      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
     820      /// Comparison operator
     821      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
     822      /// Comparison operator
     823      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
     824
     825    private:
     826      const StaticPath *path;
     827      int idx;
    424828    };
    425829
     830    /// \brief Gives back the nth edge.
     831    ///
     832    /// \pre n is in the [0..length() - 1] range
     833    const Edge& nth(int n) const {
     834      return edges[n];
     835    }
     836
     837    /// \brief Initializes edge iterator to point to the nth edge.
     838    EdgeIt nthIt(int n) const {
     839      return EdgeIt(*this, n);
     840    }
     841
     842    /// \brief Gives back the length of the path.
     843    int length() const { return len; }
     844
     845    /// \brief Returns true when the path is empty.
     846    int empty() const { return len == 0; }
     847
     848    /// \break Erase all edge in the graph.
     849    void clear() {
     850      len = 0;
     851      if (edges) delete[] edges;
     852      edges = 0;
     853    }
     854
     855    /// \brief Gives back the first edge of the path.
     856    const Edge& front() const {
     857      return edges[0];
     858    }
     859
     860    /// \brief Gives back the last edge of the path.
     861    const Edge& back() const {
     862      return edges[len - 1];
     863    }
     864
     865
     866    typedef True BuildTag;
     867
     868    template <typename CPath>
     869    void build(const CPath& path) {
     870      len = path.length();
     871      edges = new Edge[len];
     872      int index = 0;
     873      for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
     874        edges[index] = it;
     875        ++index;
     876      }
     877    }
     878
     879    template <typename CPath>
     880    void buildRev(const CPath& path) {
     881      len = path.length();
     882      edges = new Edge[len];
     883      int index = len;
     884      for (typename CPath::RevIt it(path); it != INVALID; ++it) {
     885        --index;
     886        edges[index] = it;
     887      }
     888    }
     889
     890  private:
     891    int len;
     892    Edge* edges;
    426893  };
    427894

  • lemon/suurballe.h

    r2276 r2335  
    2727#include <lemon/maps.h>
    2828#include <vector>
     29#include <lemon/path.h>
    2930#include <lemon/ssp_min_cost_flow.h>
    3031
    … …  
    8384
    8485    //Container to store found paths
    85     std::vector< std::vector<Edge> > paths;
     86    std::vector<SimplePath<Graph> > paths;
    8687
    8788  public :
    … …  
    135136          }
    136137          n = G.target(e);
    137           paths[j].push_back(e);
     138          paths[j].addBack(e);
    138139          reversed[e] = 1-reversed[e];
    139140        }
    … …  
    171172    }
    172173
     174    typedef SimplePath<Graph> Path;
     175
    173176    /// \brief Read the found paths.
    174177    ///
    … …  
    182185    /// (\c j can be 0 as well).
    183186    ///
    184     /// \param Path The type of the path structure to put the result
    185     /// to (must meet lemon path concept).
    186     /// \param p The path to put the result to.
    187187    /// \param j Which path you want to get from the found paths (in a
    188188    /// real application you would get the found paths iteratively).
    189     template<typename Path>
    190     void getPath(Path& p, size_t j){
    191 
    192       p.clear();
    193       if (j>paths.size()-1){
    194         return;
    195       }
    196       typename Path::Builder B(p);
    197       for(typename std::vector<Edge>::iterator i=paths[j].begin();
    198           i!=paths[j].end(); ++i ){
    199         B.pushBack(*i);
    200       }
    201 
    202       B.commit();
     189    Path path(int j) const {
     190      return paths[j];
     191    }
     192
     193    /// \brief Gives back the number of the paths.
     194    ///
     195    /// Gives back the number of the constructed paths.
     196    int pathNum() const {
     197      return paths.size();
    203198    }
    204199

  • test/all_pairs_shortest_path_test.cc

    r2269 r2335  
    2929
    3030#include <lemon/fib_heap.h>
     31
     32#include <lemon/path.h>
    3133
    3234#include <lemon/time_measure.h>
    … …  
    9193  }   
    9294
     95  bool checked_path = false;
     96
    9397  for (NodeIt it(graph); it != INVALID; ++it) {
    9498    for (NodeIt jt(graph); jt != INVALID; ++jt) {
    … …  
    98102            "Wrong connection in all pairs shortest path");
    99103      if (johnson.connected(it, jt)) {
     104        if (it != jt && !checked_path) {
     105          {
     106            Path<Graph> path = johnson.path(it, jt);
     107            check(checkPath(graph, path), "Wrong path.");
     108            check(pathSource(graph, path) == it, "Wrong path.");
     109            check(pathTarget(graph, path) == jt, "Wrong path.");
     110          }
     111          {
     112            Path<Graph> path = floyd.path(it, jt);
     113            check(checkPath(graph, path), "Wrong path.");
     114            check(pathSource(graph, path) == it, "Wrong path.");
     115            check(pathTarget(graph, path) == jt, "Wrong path.");
     116          }
     117          checked_path = true;
     118          std::cout << "Path checked" << std::endl;
     119        }
    100120        check(johnson.dist(it, jt) == floyd.dist(it, jt),
    101121              "Wrong distance in all pairs shortest path");

  • test/bfs_test.cc

    r2260 r2335  
    6060  b  = bfs_test.reached(n);
    6161
    62   Path<Graph> pp(G);
    63   bfs_test.getPath(pp,n);
     62  Path<Graph> pp = bfs_test.path(n);
    6463}
    6564
    … …  
    110109  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
    111110
    112   Path<Graph> p(G);
    113   check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
     111  Path<Graph> p = bfs_test.path(t);
    114112  check(p.length()==3,"getPath() found a wrong path.");
     113  check(checkPath(G, p),"path() found a wrong path.");
     114  check(pathSource(G, p) == s,"path() found a wrong path.");
     115  check(pathTarget(G, p) == t,"path() found a wrong path.");
    115116 
    116117

  • test/dfs_test.cc

    r2260 r2335  
    6060  b  = dfs_test.reached(n);
    6161
    62   Path<Graph> pp(G);
    63   dfs_test.getPath(pp,n);
     62  Path<Graph> pp = dfs_test.path(n);
    6463}
    6564
    … …  
    109108  dfs_test.run(s); 
    110109 
    111   Path<Graph> p(G);
    112   check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
    113   check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
     110  Path<Graph> p = dfs_test.path(t);
     111  check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
     112  check(checkPath(G, p),"path() found a wrong path.");
     113  check(pathSource(G, p) == s,"path() found a wrong path.");
     114  check(pathTarget(G, p) == t,"path() found a wrong path.");
    114115 
    115116  for(NodeIt v(G); v!=INVALID; ++v) {

  • test/dijkstra_test.cc

    r2298 r2335  
    6464  b  = dijkstra_test.reached(n);
    6565
    66   Path<Graph> pp(G);
    67   dijkstra_test.getPath(pp,n);
     66  Path<Graph> pp = dijkstra_test.path(n);
    6867}
    6968
    … …  
    121120
    122121
    123   Path<Graph> p(G);
    124   check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
     122  Path<Graph> p = dijkstra_test.path(t);
    125123  check(p.length()==4,"getPath() found a wrong path.");
     124  check(checkPath(G, p),"path() found a wrong path.");
     125  check(pathSource(G, p) == s,"path() found a wrong path.");
     126  check(pathTarget(G, p) == t,"path() found a wrong path.");
    126127 
    127128

  • test/path_test.cc

    r2260 r2335  
    3232
    3333void check_concepts() {
    34   checkConcept<concepts::Path<concepts::Graph>,
    35     concepts::Path<concepts::Graph> >();
    36   checkConcept<concepts::Path<concepts::Graph>,
    37     Path<concepts::Graph> >();
     34  checkConcept<concepts::Path<ListGraph>, concepts::Path<ListGraph> >();
    3835  checkConcept<concepts::Path<ListGraph>, Path<ListGraph> >();
     36  checkConcept<concepts::Path<ListGraph>, SimplePath<ListGraph> >();
     37  checkConcept<concepts::Path<ListGraph>, StaticPath<ListGraph> >();
     38  checkConcept<concepts::Path<ListGraph>, ListPath<ListGraph> >();
    3939}
    4040
    4141int main() {
    42   check_concepts();
    43  
    44   ListGraph g;
    45  
    46   ListGraph::Node n1 = g.addNode();
    47   ListGraph::Node n2 = g.addNode();
    48   ListGraph::Node n3 = g.addNode();
    49   ListGraph::Node n4 = g.addNode();
    50   ListGraph::Node n5 = g.addNode();
    51  
    52   ListGraph::Edge e1 = g.addEdge(n1, n2);
    53   ListGraph::Edge e2 = g.addEdge(n2, n3);
    54   ListGraph::Edge e3 = g.addEdge(n3, n4);
    55   ListGraph::Edge e4 = g.addEdge(n4, n5);
    56   ListGraph::Edge e5 = g.addEdge(n5, n1);
    57 
    58   {
    59     Path<ListGraph> p(g);
    60 
    61     check(p.empty(), "Wrong Path");
    62     check(p.length() == 0, "Wrong Path");
    63    
    64     {
    65       Path<ListGraph>::Builder b(p);
    66       b.setStartNode(n3);
    67       b.commit();
    68     }
    69 
    70     check(!p.empty(), "Wrong Path");
    71     check(p.length() == 0, "Wrong Path");
    72     check(p.source() == n3, "Wrong Path");
    73     check(p.target() == n3, "Wrong Path");
    74 
    75     {
    76       Path<ListGraph>::Builder b(p);
    77       b.pushBack(e3);
    78       b.pushBack(e4);
    79       b.pushFront(e2);
    80       b.commit();
    81     }
    82 
    83     check(!p.empty(), "Wrong Path");
    84     check(p.length() == 3, "Wrong Path");
    85     check(p.source() == n2, "Wrong Path");
    86     check(p.target() == n5, "Wrong Path");
    87    
    88     {
    89       Path<ListGraph>::NodeIt it(p);
    90       check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
    91       check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
    92       check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
    93       check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
    94       check((ListGraph::Node)it == INVALID, "Wrong Path");
    95     }
    96 
    97     {
    98       Path<ListGraph>::EdgeIt it(p);
    99       check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
    100       check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
    101       check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
    102       check((ListGraph::Edge)it == INVALID, "Wrong Path");
    103     }
    104    
    105   }
    106  
     42  check_concepts(); 
    10743  return 0;
    10844}
Note: See TracChangeset for help on using the changeset viewer.