1.1 --- a/lemon/Makefile.am Fri Jan 05 10:59:18 2007 +0000
1.2 +++ b/lemon/Makefile.am Mon Jan 08 10:39:59 2007 +0000
1.3 @@ -86,6 +86,7 @@
1.4 lemon/mip_cplex.h \
1.5 lemon/nagamochi_ibaraki.h \
1.6 lemon/path.h \
1.7 + lemon/path_utils.h \
1.8 lemon/polynomial.h \
1.9 lemon/preflow.h \
1.10 lemon/prim.h \
1.11 @@ -121,6 +122,7 @@
1.12 lemon/bits/item_writer.h \
1.13 lemon/bits/map_extender.h \
1.14 lemon/bits/mingw32_time.h \
1.15 + lemon/bits/path_dump.h \
1.16 lemon/bits/traits.h \
1.17 lemon/bits/utility.h \
1.18 lemon/bits/variant.h \
2.1 --- a/lemon/bellman_ford.h Fri Jan 05 10:59:18 2007 +0000
2.2 +++ b/lemon/bellman_ford.h Mon Jan 08 10:39:59 2007 +0000
2.3 @@ -25,6 +25,7 @@
2.4 ///
2.5
2.6 #include <lemon/list_graph.h>
2.7 +#include <lemon/bits/path_dump.h>
2.8 #include <lemon/bits/invalid.h>
2.9 #include <lemon/error.h>
2.10 #include <lemon/maps.h>
2.11 @@ -427,7 +428,7 @@
2.12 /// calculates the at most \f$ k \f$ length path lengths.
2.13 ///
2.14 /// \warning The paths with limited edge number cannot be retrieved
2.15 - /// easily with \ref getPath() or \ref predEdge() functions. If you
2.16 + /// easily with \ref path() or \ref predEdge() functions. If you
2.17 /// need the shortest path and not just the distance you should store
2.18 /// after each iteration the \ref predEdgeMap() map and manually build
2.19 /// the path.
2.20 @@ -540,7 +541,7 @@
2.21 /// most \c num edge.
2.22 ///
2.23 /// \warning The paths with limited edge number cannot be retrieved
2.24 - /// easily with \ref getPath() or \ref predEdge() functions. If you
2.25 + /// easily with \ref path() or \ref predEdge() functions. If you
2.26 /// need the shortest path and not just the distance you should store
2.27 /// after each iteration the \ref predEdgeMap() map and manually build
2.28 /// the path.
2.29 @@ -658,70 +659,56 @@
2.30 int _index;
2.31 };
2.32
2.33 - /// \brief Copies the shortest path to \c t into \c p
2.34 + typedef PredMapPath<Graph, PredMap> Path;
2.35 +
2.36 + /// \brief Gives back the shortest path.
2.37 ///
2.38 - /// This function copies the shortest path to \c t into \c p.
2.39 - /// If it \c t is a source itself or unreachable, then it does not
2.40 - /// alter \c p.
2.41 - ///
2.42 - /// \return Returns \c true if a path to \c t was actually copied to \c p,
2.43 - /// \c false otherwise.
2.44 - /// \sa DirPath
2.45 - template <typename Path>
2.46 - bool getPath(Path &p, Node t) {
2.47 - if(reached(t)) {
2.48 - p.clear();
2.49 - typename Path::Builder b(p);
2.50 - for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
2.51 - b.pushFront(predEdge(t));
2.52 - b.commit();
2.53 - return true;
2.54 - }
2.55 - return false;
2.56 + /// Gives back the shortest path.
2.57 + /// \pre The \c t should be reachable from the source.
2.58 + Path path(Node t)
2.59 + {
2.60 + return Path(*graph, *_pred, t);
2.61 }
2.62
2.63 - /// \brief Copies a negative cycle into path \c p.
2.64 - ///
2.65 - /// This function copies a negative cycle into path \c p.
2.66 - /// If the algorithm have not found yet negative cycle it will not change
2.67 - /// the given path and gives back false.
2.68 - ///
2.69 - /// \return Returns \c true if a cycle was actually copied to \c p,
2.70 - /// \c false otherwise.
2.71 - /// \sa DirPath
2.72 - template <typename Path>
2.73 - bool getNegativeCycle(Path& p) {
2.74 - typename Graph::template NodeMap<int> state(*graph, 0);
2.75 - for (ActiveIt it(*this); it != INVALID; ++it) {
2.76 - if (state[it] == 0) {
2.77 - for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
2.78 - if (state[t] == 0) {
2.79 - state[t] = 1;
2.80 - } else if (state[t] == 2) {
2.81 - break;
2.82 - } else {
2.83 - p.clear();
2.84 - typename Path::Builder b(p);
2.85 - b.setStartNode(t);
2.86 - b.pushFront(predEdge(t));
2.87 - for(Node s = predNode(t); s != t; s = predNode(s)) {
2.88 - b.pushFront(predEdge(s));
2.89 - }
2.90 - b.commit();
2.91 - return true;
2.92 - }
2.93 - }
2.94 - for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
2.95 - if (state[t] == 1) {
2.96 - state[t] = 2;
2.97 - } else {
2.98 - break;
2.99 - }
2.100 - }
2.101 - }
2.102 - }
2.103 - return false;
2.104 - }
2.105 +
2.106 + // TODO : implement negative cycle
2.107 +// /// \brief Gives back a negative cycle.
2.108 +// ///
2.109 +// /// This function gives back a negative cycle.
2.110 +// /// If the algorithm have not found yet negative cycle it will give back
2.111 +// /// an empty path.
2.112 +// Path negativeCycle() {
2.113 +// typename Graph::template NodeMap<int> state(*graph, 0);
2.114 +// for (ActiveIt it(*this); it != INVALID; ++it) {
2.115 +// if (state[it] == 0) {
2.116 +// for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
2.117 +// if (state[t] == 0) {
2.118 +// state[t] = 1;
2.119 +// } else if (state[t] == 2) {
2.120 +// break;
2.121 +// } else {
2.122 +// p.clear();
2.123 +// typename Path::Builder b(p);
2.124 +// b.setStartNode(t);
2.125 +// b.pushFront(predEdge(t));
2.126 +// for(Node s = predNode(t); s != t; s = predNode(s)) {
2.127 +// b.pushFront(predEdge(s));
2.128 +// }
2.129 +// b.commit();
2.130 +// return true;
2.131 +// }
2.132 +// }
2.133 +// for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
2.134 +// if (state[t] == 1) {
2.135 +// state[t] = 2;
2.136 +// } else {
2.137 +// break;
2.138 +// }
2.139 +// }
2.140 +// }
2.141 +// }
2.142 +// return false;
2.143 +// }
2.144
2.145 /// \brief The distance of a node from the root.
2.146 ///
3.1 --- a/lemon/bfs.h Fri Jan 05 10:59:18 2007 +0000
3.2 +++ b/lemon/bfs.h Mon Jan 08 10:39:59 2007 +0000
3.3 @@ -25,6 +25,7 @@
3.4
3.5 #include <lemon/list_graph.h>
3.6 #include <lemon/graph_utils.h>
3.7 +#include <lemon/bits/path_dump.h>
3.8 #include <lemon/bits/invalid.h>
3.9 #include <lemon/error.h>
3.10 #include <lemon/maps.h>
3.11 @@ -676,26 +677,15 @@
3.12
3.13 ///@{
3.14
3.15 - ///Copies the shortest path to \c t into \c p
3.16 + typedef PredMapPath<Graph, PredMap> Path;
3.17 +
3.18 + ///Gives back the shortest path.
3.19
3.20 - ///This function copies the shortest path to \c t into \c p.
3.21 - ///If \c t is a source itself or unreachable, then it does not
3.22 - ///alter \c p.
3.23 - ///\return Returns \c true if a path to \c t was actually copied to \c p,
3.24 - ///\c false otherwise.
3.25 - ///\sa DirPath
3.26 - template<class P>
3.27 - bool getPath(P &p,Node t)
3.28 + ///Gives back the shortest path.
3.29 + ///\pre The \c t should be reachable from the source.
3.30 + Path path(Node t)
3.31 {
3.32 - if(reached(t)) {
3.33 - p.clear();
3.34 - typename P::Builder b(p);
3.35 - for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
3.36 - b.pushFront(predEdge(t));
3.37 - b.commit();
3.38 - return true;
3.39 - }
3.40 - return false;
3.41 + return Path(*G, *_pred, t);
3.42 }
3.43
3.44 ///The distance of a node from the root(s).
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/bits/path_dump.h Mon Jan 08 10:39:59 2007 +0000
4.3 @@ -0,0 +1,169 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2006
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_BITS_PRED_MAP_PATH_H
4.23 +#define LEMON_BITS_PRED_MAP_PATH_H
4.24 +
4.25 +namespace lemon {
4.26 +
4.27 + template <typename _Graph, typename _PredMap>
4.28 + class PredMapPath {
4.29 + public:
4.30 + typedef True RevPathTag;
4.31 +
4.32 + typedef _Graph Graph;
4.33 + typedef typename Graph::Edge Edge;
4.34 + typedef _PredMap PredMap;
4.35 +
4.36 + PredMapPath(const Graph& _graph, const PredMap& _predMap,
4.37 + typename Graph::Node _target)
4.38 + : graph(_graph), predMap(_predMap), target(_target) {}
4.39 +
4.40 + int length() const {
4.41 + int len = 0;
4.42 + typename Graph::Node node = target;
4.43 + typename Graph::Edge edge;
4.44 + while ((edge = predMap[node]) != INVALID) {
4.45 + node = graph.source(edge);
4.46 + ++len;
4.47 + }
4.48 + return len;
4.49 + }
4.50 +
4.51 + bool empty() const {
4.52 + return predMap[target] != INVALID;
4.53 + }
4.54 +
4.55 + class RevIt {
4.56 + public:
4.57 + RevIt() {}
4.58 + RevIt(Invalid) : path(0), current(INVALID) {}
4.59 + RevIt(const PredMapPath& _path)
4.60 + : path(&_path), current(_path.target) {}
4.61 +
4.62 + operator const typename Graph::Edge() const {
4.63 + return path->predMap[current];
4.64 + }
4.65 +
4.66 + RevIt& operator++() {
4.67 + current = path->graph.source(path->predMap[current]);
4.68 + if (path->predMap[current] == INVALID) current = INVALID;
4.69 + return *this;
4.70 + }
4.71 +
4.72 + bool operator==(const RevIt& e) const {
4.73 + return current == e.current;
4.74 + }
4.75 +
4.76 + bool operator!=(const RevIt& e) const {
4.77 + return current != e.current;
4.78 + }
4.79 +
4.80 + bool operator<(const RevIt& e) const {
4.81 + return current < e.current;
4.82 + }
4.83 +
4.84 + private:
4.85 + const PredMapPath* path;
4.86 + typename Graph::Node current;
4.87 + };
4.88 +
4.89 + private:
4.90 + const Graph& graph;
4.91 + const PredMap& predMap;
4.92 + typename Graph::Node target;
4.93 + };
4.94 +
4.95 +
4.96 + template <typename _Graph, typename _PredMatrixMap>
4.97 + class PredMatrixMapPath {
4.98 + public:
4.99 + typedef True RevPathTag;
4.100 +
4.101 + typedef _Graph Graph;
4.102 + typedef typename Graph::Edge Edge;
4.103 + typedef _PredMatrixMap PredMatrixMap;
4.104 +
4.105 + PredMatrixMapPath(const Graph& _graph,
4.106 + const PredMatrixMap& _predMatrixMap,
4.107 + typename Graph::Node _source,
4.108 + typename Graph::Node _target)
4.109 + : graph(_graph), predMatrixMap(_predMatrixMap),
4.110 + source(_source), target(_target) {}
4.111 +
4.112 + int length() const {
4.113 + int len = 0;
4.114 + typename Graph::Node node = target;
4.115 + typename Graph::Edge edge;
4.116 + while ((edge = predMatrixMap(source, node)) != INVALID) {
4.117 + node = graph.source(edge);
4.118 + ++len;
4.119 + }
4.120 + return len;
4.121 + }
4.122 +
4.123 + bool empty() const {
4.124 + return source != target;
4.125 + }
4.126 +
4.127 + class RevIt {
4.128 + public:
4.129 + RevIt() {}
4.130 + RevIt(Invalid) : path(0), current(INVALID) {}
4.131 + RevIt(const PredMatrixMapPath& _path)
4.132 + : path(&_path), current(_path.target) {}
4.133 +
4.134 + operator const typename Graph::Edge() const {
4.135 + return path->predMatrixMap(path->source, current);
4.136 + }
4.137 +
4.138 + RevIt& operator++() {
4.139 + current =
4.140 + path->graph.source(path->predMatrixMap(path->source, current));
4.141 + if (path->predMatrixMap(path->source, current) == INVALID)
4.142 + current = INVALID;
4.143 + return *this;
4.144 + }
4.145 +
4.146 + bool operator==(const RevIt& e) const {
4.147 + return current == e.current;
4.148 + }
4.149 +
4.150 + bool operator!=(const RevIt& e) const {
4.151 + return current != e.current;
4.152 + }
4.153 +
4.154 + bool operator<(const RevIt& e) const {
4.155 + return current < e.current;
4.156 + }
4.157 +
4.158 + private:
4.159 + const PredMatrixMapPath* path;
4.160 + typename Graph::Node current;
4.161 + };
4.162 +
4.163 + private:
4.164 + const Graph& graph;
4.165 + const PredMatrixMap& predMatrixMap;
4.166 + typename Graph::Node source;
4.167 + typename Graph::Node target;
4.168 + };
4.169 +
4.170 +}
4.171 +
4.172 +#endif
5.1 --- a/lemon/concepts/path.h Fri Jan 05 10:59:18 2007 +0000
5.2 +++ b/lemon/concepts/path.h Mon Jan 08 10:39:59 2007 +0000
5.3 @@ -26,23 +26,28 @@
5.4 #define LEMON_CONCEPT_PATH_H
5.5
5.6 #include <lemon/bits/invalid.h>
5.7 +#include <lemon/bits/utility.h>
5.8 #include <lemon/concept_check.h>
5.9
5.10 namespace lemon {
5.11 namespace concepts {
5.12 +
5.13 /// \addtogroup concept
5.14 /// @{
5.15
5.16 -
5.17 - //! \brief A skeleton structure for representing directed paths in a graph.
5.18 - //!
5.19 - //! A skeleton structure for representing directed paths in a graph.
5.20 - //! \param _Graph The graph type in which the path is.
5.21 - //!
5.22 - //! In a sense, the path can be treated as a graph, for it has \c NodeIt
5.23 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
5.24 - //! and \c Edge of the original graph.
5.25 - template<typename _Graph>
5.26 + /// \brief A skeleton structure for representing directed paths in
5.27 + /// a graph.
5.28 + ///
5.29 + /// A skeleton structure for representing directed paths in a
5.30 + /// graph.
5.31 + /// \param _Graph The graph type in which the path is.
5.32 + ///
5.33 + /// In a sense, the path can be treated as a list of edges. The
5.34 + /// lemon path type stores just this list. As a consequence it
5.35 + /// cannot enumerate the nodes in the path and the zero length
5.36 + /// paths cannot store the source.
5.37 + ///
5.38 + template <typename _Graph>
5.39 class Path {
5.40 public:
5.41
5.42 @@ -50,20 +55,22 @@
5.43 typedef _Graph Graph;
5.44 /// Edge type of the underlying graph.
5.45 typedef typename Graph::Edge Edge;
5.46 - /// Node type of the underlying graph.
5.47 - typedef typename Graph::Node Node;
5.48
5.49 - class NodeIt;
5.50 class EdgeIt;
5.51
5.52 - /// \param _g The graph in which the path is.
5.53 - ///
5.54 - Path(const Graph &_g) {
5.55 - ignore_unused_variable_warning(_g);
5.56 - }
5.57 + /// \brief Default constructor
5.58 + Path() {}
5.59 +
5.60 + /// \brief Template constructor
5.61 + template <typename CPath>
5.62 + Path(const CPath& cpath) {}
5.63 +
5.64 + /// \brief Template assigment
5.65 + template <typename CPath>
5.66 + Path& operator=(const CPath& cpath) {}
5.67
5.68 /// Length of the path ie. the number of edges in the path.
5.69 - int length() const {return 0;}
5.70 + int length() const { return 0;}
5.71
5.72 /// Returns whether the path is empty.
5.73 bool empty() const { return true;}
5.74 @@ -71,71 +78,19 @@
5.75 /// Resets the path to an empty path.
5.76 void clear() {}
5.77
5.78 - /// \brief Starting point of the path.
5.79 + /// \brief Lemon style iterator for path edges
5.80 ///
5.81 - /// Starting point of the path.
5.82 - /// Returns INVALID if the path is empty.
5.83 - Node target() const {return INVALID;}
5.84 - /// \brief End point of the path.
5.85 - ///
5.86 - /// End point of the path.
5.87 - /// Returns INVALID if the path is empty.
5.88 - Node source() const {return INVALID;}
5.89 -
5.90 - /// \brief The target of an edge.
5.91 - ///
5.92 - /// Returns node iterator pointing to the target node of the
5.93 - /// given edge iterator.
5.94 - NodeIt target(const EdgeIt&) const {return INVALID;}
5.95 -
5.96 - /// \brief The source of an edge.
5.97 - ///
5.98 - /// Returns node iterator pointing to the source node of the
5.99 - /// given edge iterator.
5.100 - NodeIt source(const EdgeIt&) const {return INVALID;}
5.101 -
5.102 - /// \brief Iterator class to iterate on the nodes of the paths
5.103 - ///
5.104 - /// This class is used to iterate on the nodes of the paths
5.105 - ///
5.106 - /// Of course it converts to Graph::Node.
5.107 - class NodeIt {
5.108 - public:
5.109 - /// Default constructor
5.110 - NodeIt() {}
5.111 - /// Invalid constructor
5.112 - NodeIt(Invalid) {}
5.113 - /// Constructor with starting point
5.114 - NodeIt(const Path &) {}
5.115 -
5.116 - ///Conversion to Graph::Node
5.117 - operator Node() const { return INVALID; }
5.118 - /// Next node
5.119 - NodeIt& operator++() {return *this;}
5.120 -
5.121 - /// Comparison operator
5.122 - bool operator==(const NodeIt&) const {return true;}
5.123 - /// Comparison operator
5.124 - bool operator!=(const NodeIt&) const {return true;}
5.125 - /// Comparison operator
5.126 - bool operator<(const NodeIt&) const {return false;}
5.127 -
5.128 - };
5.129 -
5.130 - /// \brief Iterator class to iterate on the edges of the paths
5.131 - ///
5.132 - /// This class is used to iterate on the edges of the paths
5.133 - ///
5.134 - /// Of course it converts to Graph::Edge
5.135 + /// This class is used to iterate on the edges of the paths.
5.136 class EdgeIt {
5.137 public:
5.138 /// Default constructor
5.139 EdgeIt() {}
5.140 /// Invalid constructor
5.141 EdgeIt(Invalid) {}
5.142 - /// Constructor with starting point
5.143 + /// Constructor for first edge
5.144 EdgeIt(const Path &) {}
5.145
5.146 + /// Conversion to Edge
5.147 operator Edge() const { return INVALID; }
5.148
5.149 /// Next edge
5.150 @@ -150,143 +105,205 @@
5.151
5.152 };
5.153
5.154 + template <typename _Path>
5.155 + struct Constraints {
5.156 + void constraints() {
5.157 + Path<Graph> pc;
5.158 + _Path p, pp(pc);
5.159 + int l = p.length();
5.160 + int e = p.empty();
5.161 + p.clear();
5.162
5.163 - friend class Builder;
5.164 + p = pc;
5.165
5.166 - /// \brief Class to build paths
5.167 + typename _Path::EdgeIt id, ii(INVALID), i(p);
5.168 +
5.169 + ++i;
5.170 + typename Graph::Edge ed = i;
5.171 +
5.172 + e = (i == ii);
5.173 + e = (i != ii);
5.174 + e = (i < ii);
5.175 +
5.176 + ignore_unused_variable_warning(l);
5.177 + ignore_unused_variable_warning(pp);
5.178 + ignore_unused_variable_warning(e);
5.179 + ignore_unused_variable_warning(id);
5.180 + ignore_unused_variable_warning(ii);
5.181 + ignore_unused_variable_warning(ed);
5.182 + }
5.183 + };
5.184 +
5.185 + };
5.186 +
5.187 + namespace _path_bits {
5.188 +
5.189 + template <typename _Graph, typename _Path, typename RevPathTag = void>
5.190 + struct PathDumperConstraints {
5.191 + void constraints() {
5.192 + int l = p.length();
5.193 + int e = p.empty();
5.194 +
5.195 + typename _Path::EdgeIt id, ii(INVALID), i(p);
5.196 +
5.197 + ++i;
5.198 + typename _Graph::Edge ed = i;
5.199 +
5.200 + e = (i == ii);
5.201 + e = (i != ii);
5.202 + e = (i < ii);
5.203 +
5.204 + ignore_unused_variable_warning(l);
5.205 + ignore_unused_variable_warning(e);
5.206 + ignore_unused_variable_warning(id);
5.207 + ignore_unused_variable_warning(ii);
5.208 + ignore_unused_variable_warning(ed);
5.209 + }
5.210 + _Path& p;
5.211 + };
5.212 +
5.213 + template <typename _Graph, typename _Path>
5.214 + struct PathDumperConstraints<
5.215 + _Graph, _Path,
5.216 + typename enable_if<typename _Path::RevPathTag, void>::type
5.217 + > {
5.218 + void constraints() {
5.219 + int l = p.length();
5.220 + int e = p.empty();
5.221 +
5.222 + typename _Path::RevIt id, ii(INVALID), i(p);
5.223 +
5.224 + ++i;
5.225 + typename _Graph::Edge ed = i;
5.226 +
5.227 + e = (i == ii);
5.228 + e = (i != ii);
5.229 + e = (i < ii);
5.230 +
5.231 + ignore_unused_variable_warning(l);
5.232 + ignore_unused_variable_warning(e);
5.233 + ignore_unused_variable_warning(id);
5.234 + ignore_unused_variable_warning(ii);
5.235 + ignore_unused_variable_warning(ed);
5.236 + }
5.237 + _Path& p;
5.238 + };
5.239 +
5.240 + }
5.241 +
5.242 +
5.243 + /// \brief A skeleton structure for path dumpers.
5.244 + ///
5.245 + /// A skeleton structure for path dumpers. The path dumpers are
5.246 + /// the generalization of the paths. The path dumpers can
5.247 + /// enumerate the edges of the path wheter in forward or in
5.248 + /// backward order. In most time these classes are not used
5.249 + /// directly rather it used to assign a dumped class to a real
5.250 + /// path type.
5.251 + ///
5.252 + /// The main purpose of this concept is that the shortest path
5.253 + /// algorithms can enumerate easily the edges in reverse order.
5.254 + /// If we would like to give back a real path from these
5.255 + /// algorithms then we should create a temporarly path object. In
5.256 + /// Lemon such algorithms gives back a path dumper what can
5.257 + /// assigned to a real path and the dumpers can be implemented as
5.258 + /// an adaptor class to the predecessor map.
5.259 +
5.260 + /// \param _Graph The graph type in which the path is.
5.261 + ///
5.262 + /// The paths can be constructed from any path type by a
5.263 + /// template constructor or a template assignment operator.
5.264 + ///
5.265 + template <typename _Graph>
5.266 + class PathDumper {
5.267 + public:
5.268 +
5.269 + /// Type of the underlying graph.
5.270 + typedef _Graph Graph;
5.271 + /// Edge type of the underlying graph.
5.272 + typedef typename Graph::Edge Edge;
5.273 +
5.274 + /// Length of the path ie. the number of edges in the path.
5.275 + int length() const { return 0;}
5.276 +
5.277 + /// Returns whether the path is empty.
5.278 + bool empty() const { return true;}
5.279 +
5.280 + /// \brief Forward or reverse dumping
5.281 ///
5.282 - /// This class is used to fill a path with edges.
5.283 + /// If the RevPathTag is defined and true then reverse dumping
5.284 + /// is provided in the path proxy. In this case instead of the
5.285 + /// EdgeIt the RevIt iterator should be implemented in the
5.286 + /// proxy.
5.287 + typedef False RevPathTag;
5.288 +
5.289 + /// \brief Lemon style iterator for path edges
5.290 ///
5.291 - /// You can push new edges to the front and to the back of the path in
5.292 - /// arbitrary order then you should commit these changes to the graph.
5.293 + /// This class is used to iterate on the edges of the paths.
5.294 + class EdgeIt {
5.295 + public:
5.296 + /// Default constructor
5.297 + EdgeIt() {}
5.298 + /// Invalid constructor
5.299 + EdgeIt(Invalid) {}
5.300 + /// Constructor for first edge
5.301 + EdgeIt(const PathDumper&) {}
5.302 +
5.303 + /// Conversion to Edge
5.304 + operator Edge() const { return INVALID; }
5.305 +
5.306 + /// Next edge
5.307 + EdgeIt& operator++() {return *this;}
5.308 +
5.309 + /// Comparison operator
5.310 + bool operator==(const EdgeIt&) const {return true;}
5.311 + /// Comparison operator
5.312 + bool operator!=(const EdgeIt&) const {return true;}
5.313 + /// Comparison operator
5.314 + bool operator<(const EdgeIt&) const {return false;}
5.315 +
5.316 + };
5.317 +
5.318 + /// \brief Lemon style iterator for path edges
5.319 ///
5.320 - /// While the builder is active (after the first modifying
5.321 - /// operation and until the call of \ref commit()) the
5.322 - /// underlining Path is in a "transitional" state (operations on
5.323 - /// it have undefined result).
5.324 - class Builder {
5.325 + /// This class is used to iterate on the edges of the paths in
5.326 + /// reverse direction.
5.327 + class RevIt {
5.328 public:
5.329 + /// Default constructor
5.330 + RevIt() {}
5.331 + /// Invalid constructor
5.332 + RevIt(Invalid) {}
5.333 + /// Constructor for first edge
5.334 + RevIt(const PathDumper &) {}
5.335
5.336 - /// Constructor
5.337 + /// Conversion to Edge
5.338 + operator Edge() const { return INVALID; }
5.339
5.340 - /// Constructor
5.341 - /// \param _path the path you want to fill in.
5.342 - ///
5.343 + /// Next edge
5.344 + RevIt& operator++() {return *this;}
5.345
5.346 - Builder(Path &_path) { ignore_unused_variable_warning(_path); }
5.347 + /// Comparison operator
5.348 + bool operator==(const RevIt&) const {return true;}
5.349 + /// Comparison operator
5.350 + bool operator!=(const RevIt&) const {return true;}
5.351 + /// Comparison operator
5.352 + bool operator<(const RevIt&) const {return false;}
5.353
5.354 - /// Sets the starting node of the path.
5.355 -
5.356 - /// Sets the starting node of the path. Edge added to the path
5.357 - /// afterwards have to be incident to this node.
5.358 - /// You \em must start building an empty path with these functions.
5.359 - /// (And you \em must \em not use it later).
5.360 - /// \sa pushFront()
5.361 - /// \sa pushBack()
5.362 - void setStartNode(const Node &) {}
5.363 -
5.364 - ///Push a new edge to the front of the path
5.365 -
5.366 - ///Push a new edge to the front of the path.
5.367 - ///If the path is empty, you \em must call \ref setStartNode() before
5.368 - ///the first use of \ref pushFront().
5.369 - void pushFront(const Edge&) {}
5.370 -
5.371 - ///Push a new edge to the back of the path
5.372 -
5.373 - ///Push a new edge to the back of the path.
5.374 - ///If the path is empty, you \em must call \ref setStartNode() before
5.375 - ///the first use of \ref pushBack().
5.376 - void pushBack(const Edge&) {}
5.377 -
5.378 - ///Commit the changes to the path.
5.379 -
5.380 - ///Commit the changes to the path.
5.381 - ///
5.382 - void commit() {}
5.383 -
5.384 - ///Reserve (front) storage for the builder in advance.
5.385 -
5.386 - ///If you know a reasonable upper bound on the number of the edges
5.387 - ///to add to the front of the path,
5.388 - ///using this function you may speed up the building.
5.389 - void reserveFront(size_t) {}
5.390 - ///Reserve (back) storage for the builder in advance.
5.391 -
5.392 - ///If you know a reasonable upper bound on the number of the edges
5.393 - ///to add to the back of the path,
5.394 - ///using this function you may speed up the building.
5.395 - void reserveBack(size_t) {}
5.396 };
5.397
5.398 template <typename _Path>
5.399 struct Constraints {
5.400 - void constraints() {
5.401 - typedef typename _Path::Node Node;
5.402 - typedef typename _Path::NodeIt NodeIt;
5.403 - typedef typename Graph::Node GraphNode;
5.404 -
5.405 - typedef typename _Path::Edge Edge;
5.406 - typedef typename _Path::EdgeIt EdgeIt;
5.407 - typedef typename Graph::Edge GraphEdge;
5.408 -
5.409 - typedef typename _Path::Builder Builder;
5.410 -
5.411 - path = _Path(graph);
5.412 -
5.413 - bool b = cpath.empty();
5.414 - int l = cpath.length();
5.415 -
5.416 - Node gn;
5.417 - Edge ge;
5.418 - gn = cpath.source();
5.419 - gn = cpath.target();
5.420 -
5.421 - NodeIt nit;
5.422 - EdgeIt eit(INVALID);
5.423 - nit = path.source(eit);
5.424 - nit = path.target(eit);
5.425 -
5.426 - nit = NodeIt();
5.427 - nit = NodeIt(cpath);
5.428 - nit = INVALID;
5.429 - gn = nit;
5.430 - ++nit;
5.431 - b = nit == nit;
5.432 - b = nit != nit;
5.433 - b = nit < nit;
5.434 -
5.435 - eit = EdgeIt();
5.436 - eit = EdgeIt(cpath);
5.437 - eit = INVALID;
5.438 - ge = eit;
5.439 - ++eit;
5.440 - b = eit == eit;
5.441 - b = eit != eit;
5.442 - b = eit < eit;
5.443 -
5.444 - size_t st = 0;
5.445 -
5.446 - Builder builder(path);
5.447 - builder.setStartNode(gn);
5.448 - builder.pushFront(ge);
5.449 - builder.pushBack(ge);
5.450 - builder.commit();
5.451 - builder.reserveFront(st);
5.452 - builder.reserveBack(st);
5.453 -
5.454 - ignore_unused_variable_warning(l);
5.455 - ignore_unused_variable_warning(b);
5.456 - }
5.457 -
5.458 - const Graph& graph;
5.459 - const _Path& cpath;
5.460 - _Path& path;
5.461 + void constraints() {
5.462 + function_requires<_path_bits::
5.463 + PathDumperConstraints<Graph, _Path> >();
5.464 + }
5.465 };
5.466
5.467 };
5.468
5.469 - ///@}
5.470 +
5.471 + ///@}
5.472 }
5.473
5.474 } // namespace lemon
6.1 --- a/lemon/dag_shortest_path.h Fri Jan 05 10:59:18 2007 +0000
6.2 +++ b/lemon/dag_shortest_path.h Mon Jan 08 10:39:59 2007 +0000
6.3 @@ -722,26 +722,15 @@
6.4
6.5 ///@{
6.6
6.7 - /// \brief Copies the shortest path to \c t into \c p
6.8 - ///
6.9 - /// This function copies the shortest path to \c t into \c p.
6.10 - /// If it \c t is a source itself or unreachable, then it does not
6.11 - /// alter \c p.
6.12 - ///
6.13 - /// \return Returns \c true if a path to \c t was actually copied to \c p,
6.14 - /// \c false otherwise.
6.15 - /// \sa DirPath
6.16 - template <typename Path>
6.17 - bool getPath(Path &p, Node t) {
6.18 - if(reached(t)) {
6.19 - p.clear();
6.20 - typename Path::Builder b(p);
6.21 - for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
6.22 - b.pushFront(predEdge(t));
6.23 - b.commit();
6.24 - return true;
6.25 - }
6.26 - return false;
6.27 + typedef PredMapPath<Graph, PredMap> Path;
6.28 +
6.29 + ///Gives back the shortest path.
6.30 +
6.31 + ///Gives back the shortest path.
6.32 + ///\pre The \c t should be reachable from the source.
6.33 + Path path(Node t)
6.34 + {
6.35 + return Path(*graph, *_pred, t);
6.36 }
6.37
6.38 /// \brief The distance of a node from the root.
7.1 --- a/lemon/dfs.h Fri Jan 05 10:59:18 2007 +0000
7.2 +++ b/lemon/dfs.h Mon Jan 08 10:39:59 2007 +0000
7.3 @@ -25,6 +25,7 @@
7.4
7.5 #include <lemon/list_graph.h>
7.6 #include <lemon/graph_utils.h>
7.7 +#include <lemon/bits/path_dump.h>
7.8 #include <lemon/bits/invalid.h>
7.9 #include <lemon/error.h>
7.10 #include <lemon/maps.h>
7.11 @@ -652,27 +653,15 @@
7.12
7.13 ///@{
7.14
7.15 - ///Copies the path to \c t on the DFS tree into \c p
7.16 + typedef PredMapPath<Graph, PredMap> Path;
7.17 +
7.18 + ///Gives back the shortest path.
7.19
7.20 - ///This function copies the path to \c t on the DFS tree into \c p.
7.21 - ///If \c t is a source itself or unreachable, then it does not
7.22 - ///alter \c p.
7.23 - ///
7.24 - ///\return Returns \c true if a path to \c t was actually copied to \c p,
7.25 - ///\c false otherwise.
7.26 - ///\sa DirPath
7.27 - template<class P>
7.28 - bool getPath(P &p,Node t)
7.29 + ///Gives back the shortest path.
7.30 + ///\pre The \c t should be reachable from the source.
7.31 + Path path(Node t)
7.32 {
7.33 - if(reached(t)) {
7.34 - p.clear();
7.35 - typename P::Builder b(p);
7.36 - for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
7.37 - b.pushFront(predEdge(t));
7.38 - b.commit();
7.39 - return true;
7.40 - }
7.41 - return false;
7.42 + return Path(*G, *_pred, t);
7.43 }
7.44
7.45 ///The distance of a node from the root(s).
8.1 --- a/lemon/dijkstra.h Fri Jan 05 10:59:18 2007 +0000
8.2 +++ b/lemon/dijkstra.h Mon Jan 08 10:39:59 2007 +0000
8.3 @@ -27,10 +27,12 @@
8.4
8.5 #include <lemon/list_graph.h>
8.6 #include <lemon/bin_heap.h>
8.7 +#include <lemon/bits/path_dump.h>
8.8 #include <lemon/bits/invalid.h>
8.9 #include <lemon/error.h>
8.10 #include <lemon/maps.h>
8.11
8.12 +
8.13 namespace lemon {
8.14
8.15 template<class T> T dijkstraZero() {return 0;}
8.16 @@ -717,28 +719,17 @@
8.17
8.18 ///@{
8.19
8.20 - ///Copies the shortest path to \c t into \c p
8.21 + typedef PredMapPath<Graph, PredMap> Path;
8.22 +
8.23 + ///Gives back the shortest path.
8.24
8.25 - ///This function copies the shortest path to \c t into \c p.
8.26 - ///If it \c t is a source itself or unreachable, then it does not
8.27 - ///alter \c p.
8.28 - ///\return Returns \c true if a path to \c t was actually copied to \c p,
8.29 - ///\c false otherwise.
8.30 - ///\sa DirPath
8.31 - template<class P>
8.32 - bool getPath(P &p,Node t)
8.33 + ///Gives back the shortest path.
8.34 + ///\pre The \c t should be reachable from the source.
8.35 + Path path(Node t)
8.36 {
8.37 - if(reached(t)) {
8.38 - p.clear();
8.39 - typename P::Builder b(p);
8.40 - for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
8.41 - b.pushFront(predEdge(t));
8.42 - b.commit();
8.43 - return true;
8.44 - }
8.45 - return false;
8.46 + return Path(*G, *_pred, t);
8.47 }
8.48 -
8.49 +
8.50 ///The distance of a node from the root.
8.51
8.52 ///Returns the distance of a node from the root.
9.1 --- a/lemon/floyd_warshall.h Fri Jan 05 10:59:18 2007 +0000
9.2 +++ b/lemon/floyd_warshall.h Mon Jan 08 10:39:59 2007 +0000
9.3 @@ -26,6 +26,7 @@
9.4
9.5 #include <lemon/list_graph.h>
9.6 #include <lemon/graph_utils.h>
9.7 +#include <lemon/bits/path_dump.h>
9.8 #include <lemon/bits/invalid.h>
9.9 #include <lemon/error.h>
9.10 #include <lemon/matrix_maps.h>
9.11 @@ -480,27 +481,15 @@
9.12
9.13 ///@{
9.14
9.15 - /// \brief Copies the shortest path to \c t into \c p
9.16 - ///
9.17 - /// This function copies the shortest path to \c t into \c p.
9.18 - /// If it \c t is a source itself or unreachable, then it does not
9.19 - /// alter \c p.
9.20 - /// \return Returns \c true if a path to \c t was actually copied to \c p,
9.21 - /// \c false otherwise.
9.22 - /// \sa DirPath
9.23 - template <typename Path>
9.24 - bool getPath(Path &p, Node source, Node target) {
9.25 - if (connected(source, target)) {
9.26 - p.clear();
9.27 - typename Path::Builder b(target);
9.28 - for(b.setStartNode(target); predEdge(source, target) != INVALID;
9.29 - target = predNode(target)) {
9.30 - b.pushFront(predEdge(source, target));
9.31 - }
9.32 - b.commit();
9.33 - return true;
9.34 - }
9.35 - return false;
9.36 + typedef PredMatrixMapPath<Graph, PredMap> Path;
9.37 +
9.38 + ///Gives back the shortest path.
9.39 +
9.40 + ///Gives back the shortest path.
9.41 + ///\pre The \c t should be reachable from the \c t.
9.42 + Path path(Node s, Node t)
9.43 + {
9.44 + return Path(*graph, *_pred, s, t);
9.45 }
9.46
9.47 /// \brief The distance between two nodes.
10.1 --- a/lemon/johnson.h Fri Jan 05 10:59:18 2007 +0000
10.2 +++ b/lemon/johnson.h Mon Jan 08 10:39:59 2007 +0000
10.3 @@ -28,6 +28,7 @@
10.4 #include <lemon/graph_utils.h>
10.5 #include <lemon/dijkstra.h>
10.6 #include <lemon/bellman_ford.h>
10.7 +#include <lemon/bits/path_dump.h>
10.8 #include <lemon/bits/invalid.h>
10.9 #include <lemon/error.h>
10.10 #include <lemon/maps.h>
10.11 @@ -629,27 +630,15 @@
10.12
10.13 ///@{
10.14
10.15 - /// \brief Copies the shortest path to \c t into \c p
10.16 - ///
10.17 - /// This function copies the shortest path to \c t into \c p.
10.18 - /// If it \c t is a source itself or unreachable, then it does not
10.19 - /// alter \c p.
10.20 - /// \return Returns \c true if a path to \c t was actually copied to \c p,
10.21 - /// \c false otherwise.
10.22 - /// \sa DirPath
10.23 - template <typename Path>
10.24 - bool getPath(Path &p, Node source, Node target) {
10.25 - if (connected(source, target)) {
10.26 - p.clear();
10.27 - typename Path::Builder b(target);
10.28 - for(b.setStartNode(target); predEdge(source, target) != INVALID;
10.29 - target = predNode(target)) {
10.30 - b.pushFront(predEdge(source, target));
10.31 - }
10.32 - b.commit();
10.33 - return true;
10.34 - }
10.35 - return false;
10.36 + typedef PredMatrixMapPath<Graph, PredMap> Path;
10.37 +
10.38 + ///Gives back the shortest path.
10.39 +
10.40 + ///Gives back the shortest path.
10.41 + ///\pre The \c t should be reachable from the \c t.
10.42 + Path path(Node s, Node t)
10.43 + {
10.44 + return Path(*graph, *_pred, s, t);
10.45 }
10.46
10.47 /// \brief The distance between two nodes.
11.1 --- a/lemon/path.h Fri Jan 05 10:59:18 2007 +0000
11.2 +++ b/lemon/path.h Mon Jan 08 10:39:59 2007 +0000
11.3 @@ -28,6 +28,7 @@
11.4 #include <vector>
11.5 #include <algorithm>
11.6
11.7 +#include <lemon/path_utils.h>
11.8 #include <lemon/error.h>
11.9 #include <lemon/bits/invalid.h>
11.10
11.11 @@ -37,392 +38,858 @@
11.12 /// @{
11.13
11.14
11.15 - //! \brief A structure for representing directed paths in a graph.
11.16 - //!
11.17 - //! A structure for representing directed path in a graph.
11.18 - //! \param Graph The graph type in which the path is.
11.19 - //!
11.20 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
11.21 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
11.22 - //! and \c Edge of the original graph.
11.23 - //!
11.24 - //! \todo Thoroughfully check all the range and consistency tests.
11.25 - template<typename Graph>
11.26 + /// \brief A structure for representing directed paths in a graph.
11.27 + ///
11.28 + /// A structure for representing directed path in a graph.
11.29 + /// \param Graph The graph type in which the path is.
11.30 + ///
11.31 + /// In a sense, the path can be treated as a list of edges. The
11.32 + /// lemon path type stores just this list. As a consequence it
11.33 + /// cannot enumerate the nodes in the path and the zero length paths
11.34 + /// cannot store the source.
11.35 + ///
11.36 + /// This implementation is a back and front insertable and erasable
11.37 + /// path type. It can be indexed in O(1) time. The front and back
11.38 + /// insertion and erasure is amortized O(1) time. The
11.39 + /// impelementation is based on two opposite organized vectors.
11.40 + template <typename _Graph>
11.41 class Path {
11.42 public:
11.43 - /// Edge type of the underlying graph.
11.44 +
11.45 + typedef _Graph Graph;
11.46 typedef typename Graph::Edge Edge;
11.47 - /// Node type of the underlying graph.
11.48 - typedef typename Graph::Node Node;
11.49
11.50 - class NodeIt;
11.51 - class EdgeIt;
11.52 + /// \brief Default constructor
11.53 + ///
11.54 + /// Default constructor
11.55 + Path() {}
11.56
11.57 - struct PathError : public LogicError {
11.58 - virtual const char* what() const throw() {
11.59 - return "lemon::PathError";
11.60 - }
11.61 - };
11.62 -
11.63 - public:
11.64 -
11.65 - /// \brief Constructor
11.66 + /// \brief Template copy constructor
11.67 ///
11.68 - /// Constructor
11.69 - /// \param _G The graph in which the path is.
11.70 - Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
11.71 -
11.72 - /// \brief Subpath constructor.
11.73 - ///
11.74 - /// Subpath defined by two nodes.
11.75 - /// \warning It is an error if the two edges are not in order!
11.76 - Path(const Path &other, const NodeIt &a, const NodeIt &b) {
11.77 - graph = other.graph;
11.78 - start = a;
11.79 - edges.insert(edges.end(),
11.80 - other.edges.begin() + a.id, other.edges.begin() + b.id);
11.81 + /// This path can be initialized with any other path type. It just
11.82 + /// makes a copy of the given path.
11.83 + template <typename CPath>
11.84 + Path(const CPath& cpath) {
11.85 + copyPath(*this, cpath);
11.86 }
11.87
11.88 - /// \brief Subpath constructor.
11.89 + /// \brief Template copy assignment
11.90 ///
11.91 - /// Subpath defined by two edges. Contains edges in [a,b)
11.92 - /// \warning It is an error if the two edges are not in order!
11.93 - Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
11.94 - graph = other.graph;
11.95 - start = graph->source(a);
11.96 - edges.insert(edges.end(),
11.97 - other.edges.begin() + a.id, other.edges.begin() + b.id);
11.98 + /// This path can be initialized with any other path type. It just
11.99 + /// makes a copy of the given path.
11.100 + template <typename CPath>
11.101 + Path& operator=(const CPath& cpath) {
11.102 + copyPath(*this, cpath);
11.103 + return *this;
11.104 }
11.105
11.106 - /// \brief Length of the path.
11.107 + /// \brief Lemon style iterator for path edges
11.108 ///
11.109 - /// The number of the edges in the path. It can be zero if the
11.110 - /// path has only one node or it is empty.
11.111 - int length() const { return edges.size(); }
11.112 -
11.113 - /// \brief Returns whether the path is empty.
11.114 - ///
11.115 - /// Returns true when the path does not contain neither edge nor
11.116 - /// node.
11.117 - bool empty() const { return start == INVALID; }
11.118 -
11.119 - /// \brief Resets the path to an empty path.
11.120 - ///
11.121 - /// Resets the path to an empty path.
11.122 - void clear() { edges.clear(); start = INVALID; }
11.123 -
11.124 - /// \brief Starting point of the path.
11.125 - ///
11.126 - /// Starting point of the path.
11.127 - /// Returns INVALID if the path is empty.
11.128 - Node source() const {
11.129 - return start;
11.130 - }
11.131 - /// \brief End point of the path.
11.132 - ///
11.133 - /// End point of the path.
11.134 - /// Returns INVALID if the path is empty.
11.135 - Node target() const {
11.136 - return length() == 0 ? start : graph->target(edges[length()-1]);
11.137 - }
11.138 -
11.139 - /// \brief Gives back a node iterator to point to the node of a
11.140 - /// given index.
11.141 - ///
11.142 - /// Gives back a node iterator to point to the node of a given
11.143 - /// index.
11.144 - /// \pre n should less or equal to \c length()
11.145 - NodeIt nthNode(int n) const {
11.146 - return NodeIt(*this, n);
11.147 - }
11.148 -
11.149 - /// \brief Gives back an edge iterator to point to the edge of a
11.150 - /// given index.
11.151 - ///
11.152 - /// Gives back an edge iterator to point to the node of a given
11.153 - /// index.
11.154 - /// \pre n should less than \c length()
11.155 - EdgeIt nthEdge(int n) const {
11.156 - return EdgeIt(*this, n);
11.157 - }
11.158 -
11.159 - /// \brief Returns node iterator pointing to the source node of the
11.160 - /// given edge iterator.
11.161 - ///
11.162 - /// Returns node iterator pointing to the source node of the given
11.163 - /// edge iterator.
11.164 - NodeIt source(const EdgeIt& e) const {
11.165 - return NodeIt(*this, e.id);
11.166 - }
11.167 -
11.168 - /// \brief Returns node iterator pointing to the target node of the
11.169 - /// given edge iterator.
11.170 - ///
11.171 - /// Returns node iterator pointing to the target node of the given
11.172 - /// edge iterator.
11.173 - NodeIt target(const EdgeIt& e) const {
11.174 - return NodeIt(*this, e.id + 1);
11.175 - }
11.176 -
11.177 -
11.178 - /// \brief Iterator class to iterate on the nodes of the paths
11.179 - ///
11.180 - /// This class is used to iterate on the nodes of the paths
11.181 - ///
11.182 - /// Of course it converts to Graph::Node
11.183 - class NodeIt {
11.184 + /// This class is used to iterate on the edges of the paths.
11.185 + class EdgeIt {
11.186 friend class Path;
11.187 public:
11.188 + /// \brief Default constructor
11.189 + EdgeIt() {}
11.190 + /// \brief Invalid constructor
11.191 + EdgeIt(Invalid) : path(0), idx(-1) {}
11.192 + /// \brief Initializate the constructor to the first edge of path
11.193 + EdgeIt(const Path &_path)
11.194 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
11.195
11.196 - /// \brief Default constructor
11.197 - ///
11.198 - /// Default constructor
11.199 - NodeIt() {}
11.200 + private:
11.201
11.202 - /// \brief Invalid constructor
11.203 - ///
11.204 - /// Invalid constructor
11.205 - NodeIt(Invalid) : id(-1), path(0) {}
11.206 + EdgeIt(const Path &_path, int _idx)
11.207 + : idx(_idx), path(&_path) {}
11.208
11.209 - /// \brief Constructor with starting point
11.210 - ///
11.211 - /// Constructor with starting point
11.212 - NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
11.213 - if (id > path->length()) id = -1;
11.214 + public:
11.215 +
11.216 + /// \brief Conversion to Edge
11.217 + operator const Edge&() const {
11.218 + return path->nth(idx);
11.219 }
11.220
11.221 - /// \brief Conversion to Graph::Node
11.222 - ///
11.223 - /// Conversion to Graph::Node
11.224 - operator Node() const {
11.225 - if (id > 0) {
11.226 - return path->graph->target(path->edges[id - 1]);
11.227 - } else if (id == 0) {
11.228 - return path->start;
11.229 - } else {
11.230 - return INVALID;
11.231 - }
11.232 - }
11.233 -
11.234 - /// \brief Steps to the next node
11.235 - ///
11.236 - /// Steps to the next node
11.237 - NodeIt& operator++() {
11.238 - ++id;
11.239 - if (id > path->length()) id = -1;
11.240 + /// \brief Next edge
11.241 + EdgeIt& operator++() {
11.242 + ++idx;
11.243 + if (idx >= path->length()) idx = -1;
11.244 return *this;
11.245 }
11.246
11.247 /// \brief Comparison operator
11.248 - ///
11.249 - /// Comparison operator
11.250 - bool operator==(const NodeIt& n) const { return id == n.id; }
11.251 -
11.252 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
11.253 /// \brief Comparison operator
11.254 - ///
11.255 - /// Comparison operator
11.256 - bool operator!=(const NodeIt& n) const { return id != n.id; }
11.257 -
11.258 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
11.259 /// \brief Comparison operator
11.260 - ///
11.261 - /// Comparison operator
11.262 - bool operator<(const NodeIt& n) const { return id < n.id; }
11.263 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
11.264
11.265 private:
11.266 - int id;
11.267 const Path *path;
11.268 + int idx;
11.269 };
11.270
11.271 + /// \brief Length of the path.
11.272 + int length() const { return head.size() + tail.size(); }
11.273 + /// \brief Returns whether the path is empty.
11.274 + bool empty() const { return head.empty() && tail.empty(); }
11.275 +
11.276 + /// \brief Resets the path to an empty path.
11.277 + void clear() { head.clear(); tail.clear(); }
11.278 +
11.279 + /// \brief Gives back the nth edge.
11.280 + ///
11.281 + /// \pre n is in the [0..length() - 1] range
11.282 + const Edge& nth(int n) const {
11.283 + return n < (int)head.size() ? *(head.rbegin() + n) :
11.284 + *(tail.begin() + (n - head.size()));
11.285 + }
11.286 +
11.287 + /// \brief Initializes edge iterator to point to the nth edge
11.288 + ///
11.289 + /// \pre n is in the [0..length() - 1] range
11.290 + EdgeIt nthIt(int n) const {
11.291 + return EdgeIt(*this, n);
11.292 + }
11.293 +
11.294 + /// \brief Gives back the first edge of the path
11.295 + const Edge& front() const {
11.296 + return head.empty() ? tail.front() : head.back();
11.297 + }
11.298 +
11.299 + /// \brief Add a new edge before the current path
11.300 + void addFront(const Edge& edge) {
11.301 + head.push_back(edge);
11.302 + }
11.303 +
11.304 + /// \brief Erase the first edge of the path
11.305 + void eraseFront() {
11.306 + if (!head.empty()) {
11.307 + head.pop_back();
11.308 + } else {
11.309 + head.clear();
11.310 + int halfsize = tail.size() / 2;
11.311 + head.resize(halfsize);
11.312 + std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
11.313 + head.rbegin());
11.314 + std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
11.315 + tail.resize(tail.size() - halfsize - 1);
11.316 + }
11.317 + }
11.318 +
11.319 + /// \brief Gives back the last edge of the path
11.320 + const Edge& back() const {
11.321 + return tail.empty() ? head.front() : tail.back();
11.322 + }
11.323 +
11.324 + /// \brief Add a new edge behind the current path
11.325 + void addBack(const Edge& edge) {
11.326 + tail.push_back(edge);
11.327 + }
11.328 +
11.329 + /// \brief Erase the last edge of the path
11.330 + void eraseBack() {
11.331 + if (!tail.empty()) {
11.332 + tail.pop_back();
11.333 + } else {
11.334 + int halfsize = head.size() / 2;
11.335 + tail.resize(halfsize);
11.336 + std::copy(head.begin() + 1, head.begin() + halfsize + 1,
11.337 + tail.rbegin());
11.338 + std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
11.339 + head.resize(head.size() - halfsize - 1);
11.340 + }
11.341 + }
11.342 +
11.343 +
11.344 +
11.345 + typedef True BuildTag;
11.346 +
11.347 + template <typename CPath>
11.348 + void build(const CPath& path) {
11.349 + int len = path.length();
11.350 + tail.reserve(len);
11.351 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
11.352 + tail.push_back(it);
11.353 + }
11.354 + }
11.355 +
11.356 + template <typename CPath>
11.357 + void buildRev(const CPath& path) {
11.358 + int len = path.length();
11.359 + head.reserve(len);
11.360 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
11.361 + head.push_back(it);
11.362 + }
11.363 + }
11.364 +
11.365 + protected:
11.366 + typedef std::vector<Edge> Container;
11.367 + Container head, tail;
11.368 +
11.369 + };
11.370 +
11.371 + /// \brief A structure for representing directed paths in a graph.
11.372 + ///
11.373 + /// A structure for representing directed path in a graph.
11.374 + /// \param Graph The graph type in which the path is.
11.375 + ///
11.376 + /// In a sense, the path can be treated as a list of edges. The
11.377 + /// lemon path type stores just this list. As a consequence it
11.378 + /// cannot enumerate the nodes in the path and the zero length paths
11.379 + /// cannot store the source.
11.380 + ///
11.381 + /// This implementation is a just back insertable and erasable path
11.382 + /// type. It can be indexed in O(1) time. The back insertion and
11.383 + /// erasure is amortized O(1) time. This implementation is faster
11.384 + /// then the \c Path type because it use just one vector for the
11.385 + /// edges.
11.386 + template <typename _Graph>
11.387 + class SimplePath {
11.388 + public:
11.389 +
11.390 + typedef _Graph Graph;
11.391 + typedef typename Graph::Edge Edge;
11.392 +
11.393 + /// \brief Default constructor
11.394 + ///
11.395 + /// Default constructor
11.396 + SimplePath() {}
11.397 +
11.398 + /// \brief Template copy constructor
11.399 + ///
11.400 + /// This path can be initialized with any other path type. It just
11.401 + /// makes a copy of the given path.
11.402 + template <typename CPath>
11.403 + SimplePath(const CPath& cpath) {
11.404 + copyPath(*this, cpath);
11.405 + }
11.406 +
11.407 + /// \brief Template copy assignment
11.408 + ///
11.409 + /// This path can be initialized with any other path type. It just
11.410 + /// makes a copy of the given path.
11.411 + template <typename CPath>
11.412 + SimplePath& operator=(const CPath& cpath) {
11.413 + copyPath(*this, cpath);
11.414 + return *this;
11.415 + }
11.416 +
11.417 /// \brief Iterator class to iterate on the edges of the paths
11.418 ///
11.419 /// This class is used to iterate on the edges of the paths
11.420 + ///
11.421 /// Of course it converts to Graph::Edge
11.422 class EdgeIt {
11.423 - friend class Path;
11.424 + friend class SimplePath;
11.425 + public:
11.426 + /// Default constructor
11.427 + EdgeIt() {}
11.428 + /// Invalid constructor
11.429 + EdgeIt(Invalid) : path(0), idx(-1) {}
11.430 + /// \brief Initializate the constructor to the first edge of path
11.431 + EdgeIt(const SimplePath &_path)
11.432 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
11.433 +
11.434 + private:
11.435 +
11.436 + /// Constructor with starting point
11.437 + EdgeIt(const SimplePath &_path, int _idx)
11.438 + : idx(_idx), path(&_path) {}
11.439 +
11.440 public:
11.441
11.442 - /// \brief Default constructor
11.443 - ///
11.444 - /// Default constructor
11.445 - EdgeIt() {}
11.446 -
11.447 - /// \brief Invalid constructor
11.448 - ///
11.449 - /// Invalid constructor
11.450 - EdgeIt(Invalid) : id(-1), path(0) {}
11.451 -
11.452 - /// \brief Constructor with starting point
11.453 - ///
11.454 - /// Constructor with starting point
11.455 - EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
11.456 - if (id >= path->length()) id = -1;
11.457 + ///Conversion to Graph::Edge
11.458 + operator const Edge&() const {
11.459 + return path->nth(idx);
11.460 }
11.461
11.462 - /// \brief Conversion to Graph::Edge
11.463 - ///
11.464 - /// Conversion to Graph::Edge
11.465 - operator Edge() const {
11.466 - return id != -1 ? path->edges[id] : INVALID;
11.467 - }
11.468 -
11.469 - /// \brief Steps to the next edge
11.470 - ///
11.471 - /// Steps to the next edge
11.472 + /// Next edge
11.473 EdgeIt& operator++() {
11.474 - ++id;
11.475 - if (id >= path->length()) id = -1;
11.476 + ++idx;
11.477 + if (idx >= path->length()) idx = -1;
11.478 return *this;
11.479 }
11.480
11.481 - /// \brief Comparison operator
11.482 - ///
11.483 /// Comparison operator
11.484 - bool operator==(const EdgeIt& e) const { return id == e.id; }
11.485 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
11.486 + /// Comparison operator
11.487 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
11.488 + /// Comparison operator
11.489 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
11.490
11.491 - /// \brief Comparison operator
11.492 - ///
11.493 + private:
11.494 + const SimplePath *path;
11.495 + int idx;
11.496 + };
11.497 +
11.498 + /// \brief Length of the path.
11.499 + int length() const { return data.size(); }
11.500 + /// \brief Returns whether the path is empty.
11.501 + bool empty() const { return data.empty(); }
11.502 +
11.503 + /// \brief Resets the path to an empty path.
11.504 + void clear() { data.clear(); }
11.505 +
11.506 + /// \brief Gives back the nth edge.
11.507 + ///
11.508 + /// \pre n is in the [0..length() - 1] range
11.509 + const Edge& nth(int n) const {
11.510 + return data[n];
11.511 + }
11.512 +
11.513 + /// \brief Initializes edge iterator to point to the nth edge.
11.514 + EdgeIt nthIt(int n) const {
11.515 + return EdgeIt(*this, n);
11.516 + }
11.517 +
11.518 + /// \brief Gives back the last edge of the path.
11.519 + const Edge& back() const {
11.520 + return data.back();
11.521 + }
11.522 +
11.523 + /// \brief Add a new edge behind the current path.
11.524 + void addBack(const Edge& edge) {
11.525 + data.push_back(edge);
11.526 + }
11.527 +
11.528 + /// \brief Erase the last edge of the path
11.529 + void eraseBack() {
11.530 + data.pop_back();
11.531 + }
11.532 +
11.533 + typedef True BuildTag;
11.534 +
11.535 + template <typename CPath>
11.536 + void build(const CPath& path) {
11.537 + int len = path.length();
11.538 + data.resize(len);
11.539 + int index = 0;
11.540 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
11.541 + data[index] = it;;
11.542 + ++index;
11.543 + }
11.544 + }
11.545 +
11.546 + template <typename CPath>
11.547 + void buildRev(const CPath& path) {
11.548 + int len = path.length();
11.549 + data.resize(len);
11.550 + int index = len;
11.551 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
11.552 + --index;
11.553 + data[index] = it;;
11.554 + }
11.555 + }
11.556 +
11.557 + protected:
11.558 + typedef std::vector<Edge> Container;
11.559 + Container data;
11.560 +
11.561 + };
11.562 +
11.563 + /// \brief A structure for representing directed paths in a graph.
11.564 + ///
11.565 + /// A structure for representing directed path in a graph.
11.566 + /// \param Graph The graph type in which the path is.
11.567 + ///
11.568 + /// In a sense, the path can be treated as a list of edges. The
11.569 + /// lemon path type stores just this list. As a consequence it
11.570 + /// cannot enumerate the nodes in the path and the zero length paths
11.571 + /// cannot store the source.
11.572 + ///
11.573 + /// This implementation is a back and front insertable and erasable
11.574 + /// path type. It can be indexed in O(k) time, where k is the rank
11.575 + /// of the edge in the path. The length can be computed in O(n)
11.576 + /// time. The front and back insertion and erasure is O(1) time
11.577 + /// and it can be splited and spliced in O(1) time.
11.578 + template <typename _Graph>
11.579 + class ListPath {
11.580 + public:
11.581 +
11.582 + typedef _Graph Graph;
11.583 + typedef typename Graph::Edge Edge;
11.584 +
11.585 + protected:
11.586 +
11.587 + // the std::list<> is incompatible
11.588 + // hard to create invalid iterator
11.589 + struct Node {
11.590 + Edge edge;
11.591 + Node *next, *prev;
11.592 + };
11.593 +
11.594 + Node *first, *last;
11.595 +
11.596 + std::allocator<Node> alloc;
11.597 +
11.598 + public:
11.599 +
11.600 + /// \brief Default constructor
11.601 + ///
11.602 + /// Default constructor
11.603 + ListPath() : first(0), last(0) {}
11.604 +
11.605 + /// \brief Template copy constructor
11.606 + ///
11.607 + /// This path can be initialized with any other path type. It just
11.608 + /// makes a copy of the given path.
11.609 + template <typename CPath>
11.610 + ListPath(const CPath& cpath) : first(0), last(0) {
11.611 + copyPath(*this, cpath);
11.612 + }
11.613 +
11.614 + /// \brief Destructor of the path
11.615 + ///
11.616 + /// Destructor of the path
11.617 + ~ListPath() {
11.618 + clear();
11.619 + }
11.620 +
11.621 + /// \brief Template copy assignment
11.622 + ///
11.623 + /// This path can be initialized with any other path type. It just
11.624 + /// makes a copy of the given path.
11.625 + template <typename CPath>
11.626 + ListPath& operator=(const CPath& cpath) {
11.627 + copyPath(*this, cpath);
11.628 + return *this;
11.629 + }
11.630 +
11.631 + /// \brief Iterator class to iterate on the edges of the paths
11.632 + ///
11.633 + /// This class is used to iterate on the edges of the paths
11.634 + ///
11.635 + /// Of course it converts to Graph::Edge
11.636 + class EdgeIt {
11.637 + friend class ListPath;
11.638 + public:
11.639 + /// Default constructor
11.640 + EdgeIt() {}
11.641 + /// Invalid constructor
11.642 + EdgeIt(Invalid) : path(0), node(0) {}
11.643 + /// \brief Initializate the constructor to the first edge of path
11.644 + EdgeIt(const ListPath &_path)
11.645 + : path(&_path), node(_path.first) {}
11.646 +
11.647 + protected:
11.648 +
11.649 + EdgeIt(const ListPath &_path, Node *_node)
11.650 + : path(&_path), node(_node) {}
11.651 +
11.652 +
11.653 + public:
11.654 +
11.655 + ///Conversion to Graph::Edge
11.656 + operator const Edge&() const {
11.657 + return node->edge;
11.658 + }
11.659 +
11.660 + /// Next edge
11.661 + EdgeIt& operator++() {
11.662 + node = node->next;
11.663 + return *this;
11.664 + }
11.665 +
11.666 /// Comparison operator
11.667 - bool operator!=(const EdgeIt& e) const { return id != e.id; }
11.668 + bool operator==(const EdgeIt& e) const { return node==e.node; }
11.669 + /// Comparison operator
11.670 + bool operator!=(const EdgeIt& e) const { return node!=e.node; }
11.671 + /// Comparison operator
11.672 + bool operator<(const EdgeIt& e) const { return node<e.node; }
11.673
11.674 - /// \brief Comparison operator
11.675 - ///
11.676 - /// Comparison operator
11.677 - bool operator<(const EdgeIt& e) const { return id < e.id; }
11.678 + private:
11.679 + const ListPath *path;
11.680 + Node *node;
11.681 + };
11.682 +
11.683 + /// \brief Gives back the nth edge.
11.684 + ///
11.685 + /// Gives back the nth edge in O(n) time.
11.686 + /// \pre n is in the [0..length() - 1] range
11.687 + const Edge& nth(int n) const {
11.688 + Node *node = first;
11.689 + for (int i = 0; i < n; ++i) {
11.690 + node = node->next;
11.691 + }
11.692 + return node->edge;
11.693 + }
11.694 +
11.695 + /// \brief Initializes edge iterator to point to the nth edge.
11.696 + EdgeIt nthIt(int n) const {
11.697 + Node *node = first;
11.698 + for (int i = 0; i < n; ++i) {
11.699 + node = node->next;
11.700 + }
11.701 + return EdgeIt(*this, node);
11.702 + }
11.703 +
11.704 + /// \brief Length of the path.
11.705 + int length() const {
11.706 + int len = 0;
11.707 + Node *node = first;
11.708 + while (node != 0) {
11.709 + node = node->next;
11.710 + ++len;
11.711 + }
11.712 + return len;
11.713 + }
11.714 +
11.715 + /// \brief Returns whether the path is empty.
11.716 + bool empty() const { return first == 0; }
11.717 +
11.718 + /// \brief Resets the path to an empty path.
11.719 + void clear() {
11.720 + while (first != 0) {
11.721 + last = first->next;
11.722 + alloc.destroy(first);
11.723 + alloc.deallocate(first, 1);
11.724 + first = last;
11.725 + }
11.726 + }
11.727 +
11.728 + /// \brief Gives back the first edge of the path
11.729 + const Edge& front() const {
11.730 + return first->edge;
11.731 + }
11.732 +
11.733 + /// \brief Add a new edge before the current path
11.734 + void addFront(const Edge& edge) {
11.735 + Node *node = alloc.allocate(1);
11.736 + alloc.construct(node, Node());
11.737 + node->prev = 0;
11.738 + node->next = first;
11.739 + node->edge = edge;
11.740 + if (first) {
11.741 + first->prev = node;
11.742 + first = node;
11.743 + } else {
11.744 + first = last = node;
11.745 + }
11.746 + }
11.747 +
11.748 + /// \brief Erase the first edge of the path
11.749 + void eraseFront() {
11.750 + Node *node = first;
11.751 + first = first->next;
11.752 + if (first) {
11.753 + first->prev = 0;
11.754 + } else {
11.755 + last = 0;
11.756 + }
11.757 + alloc.destroy(node);
11.758 + alloc.deallocate(node, 1);
11.759 + }
11.760 +
11.761 + /// \brief Gives back the last edge of the path.
11.762 + const Edge& back() const {
11.763 + return last->edge;
11.764 + }
11.765 +
11.766 + /// \brief Add a new edge behind the current path.
11.767 + void addBack(const Edge& edge) {
11.768 + Node *node = alloc.allocate(1);
11.769 + alloc.construct(node, Node());
11.770 + node->next = 0;
11.771 + node->prev = last;
11.772 + node->edge = edge;
11.773 + if (last) {
11.774 + last->next = node;
11.775 + last = node;
11.776 + } else {
11.777 + last = first = node;
11.778 + }
11.779 + }
11.780 +
11.781 + /// \brief Erase the last edge of the path
11.782 + void eraseBack() {
11.783 + Node *node = last;
11.784 + last = last->prev;
11.785 + if (last) {
11.786 + last->next = 0;
11.787 + } else {
11.788 + first = 0;
11.789 + }
11.790 + alloc.destroy(node);
11.791 + alloc.deallocate(node, 1);
11.792 + }
11.793 +
11.794 + /// \brief Splicing the given path to the current path.
11.795 + ///
11.796 + /// It splices the \c tpath to the back of the current path and \c
11.797 + /// tpath becomes empty. The time complexity of this function is
11.798 + /// O(1).
11.799 + void spliceBack(ListPath& tpath) {
11.800 + if (first) {
11.801 + if (tpath.first) {
11.802 + last->next = tpath.first;
11.803 + tpath.first->prev = last;
11.804 + last = tpath.last;
11.805 + }
11.806 + } else {
11.807 + first = tpath.first;
11.808 + last = tpath.last;
11.809 + }
11.810 + tpath.first = tpath.last = 0;
11.811 + }
11.812 +
11.813 + /// \brief Splicing the given path to the current path.
11.814 + ///
11.815 + /// It splices the \c tpath before the current path and \c tpath
11.816 + /// becomes empty. The time complexity of this function
11.817 + /// is O(1).
11.818 + void spliceFront(ListPath& tpath) {
11.819 + if (first) {
11.820 + if (tpath.first) {
11.821 + first->prev = tpath.last;
11.822 + tpath.last->next = first;
11.823 + first = tpath.first;
11.824 + }
11.825 + } else {
11.826 + first = tpath.first;
11.827 + last = tpath.last;
11.828 + }
11.829 + tpath.first = tpath.last = 0;
11.830 + }
11.831 +
11.832 + /// \brief Splicing the given path into the current path.
11.833 + ///
11.834 + /// It splices the \c tpath into the current path before the
11.835 + /// position of \c it iterator and \c tpath becomes empty. The
11.836 + /// time complexity of this function is O(1). If the \c it is \c
11.837 + /// INVALID then it will splice behind the current path.
11.838 + void splice(EdgeIt it, ListPath& tpath) {
11.839 + if (it.node) {
11.840 + if (tpath.first) {
11.841 + tpath.first->prev = it.node->prev;
11.842 + if (it.node->prev) {
11.843 + it.node->prev->next = tpath.first;
11.844 + } else {
11.845 + first = tpath.first;
11.846 + }
11.847 + it.node->prev = tpath.last;
11.848 + tpath.last->next = it.node;
11.849 + }
11.850 + } else {
11.851 + if (first) {
11.852 + if (tpath.first) {
11.853 + last->next = tpath.first;
11.854 + tpath.first->prev = last;
11.855 + last = tpath.last;
11.856 + }
11.857 + } else {
11.858 + first = tpath.first;
11.859 + last = tpath.last;
11.860 + }
11.861 + }
11.862 + tpath.first = tpath.last = 0;
11.863 + }
11.864 +
11.865 + /// \brief Spliting the current path.
11.866 + ///
11.867 + /// It splits the current path into two parts. The part before \c
11.868 + /// it iterator will remain in the current path and the part from
11.869 + /// the it will put into the \c tpath. If the \c tpath had edges
11.870 + /// before the operation they will be removed first. The time
11.871 + /// complexity of this function is O(1) plus the clearing of \c
11.872 + /// tpath. If the \c it is \c INVALID then it just clears \c
11.873 + /// tpath.
11.874 + void split(EdgeIt it, ListPath& tpath) {
11.875 + tpath.clear();
11.876 + if (it.node) {
11.877 + tpath.first = it.node;
11.878 + tpath.last = last;
11.879 + if (it.node->prev) {
11.880 + last = it.node->prev;
11.881 + last->next = 0;
11.882 + } else {
11.883 + first = last = 0;
11.884 + }
11.885 + it.node->prev = 0;
11.886 + }
11.887 + }
11.888 +
11.889 +
11.890 + typedef True BuildTag;
11.891 +
11.892 + template <typename CPath>
11.893 + void build(const CPath& path) {
11.894 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
11.895 + addBack(it);
11.896 + }
11.897 + }
11.898 +
11.899 + template <typename CPath>
11.900 + void buildRev(const CPath& path) {
11.901 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
11.902 + addFront(it);
11.903 + }
11.904 + }
11.905 +
11.906 + };
11.907 +
11.908 + /// \brief A structure for representing directed paths in a graph.
11.909 + ///
11.910 + /// A structure for representing directed path in a graph.
11.911 + /// \param Graph The graph type in which the path is.
11.912 + ///
11.913 + /// In a sense, the path can be treated as a list of edges. The
11.914 + /// lemon path type stores just this list. As a consequence it
11.915 + /// cannot enumerate the nodes in the path and the zero length paths
11.916 + /// cannot store the source.
11.917 + ///
11.918 + /// This implementation is completly static, so it cannot be
11.919 + /// modified exclude the assign an other path. It is intented to be
11.920 + /// used when you want to store a large amount paths because it is
11.921 + /// the most memory efficient path type in the lemon.
11.922 + template <typename _Graph>
11.923 + class StaticPath {
11.924 + public:
11.925 +
11.926 + typedef _Graph Graph;
11.927 + typedef typename Graph::Edge Edge;
11.928 +
11.929 + /// \brief Default constructor
11.930 + ///
11.931 + /// Default constructor
11.932 + StaticPath() : len(0), edges(0) {}
11.933 +
11.934 + /// \brief Template copy constructor
11.935 + ///
11.936 + /// This path can be initialized with any other path type. It just
11.937 + /// makes a copy of the given path.
11.938 + template <typename CPath>
11.939 + StaticPath(const CPath& cpath) : edges(0) {
11.940 + copyPath(*this, cpath);
11.941 + }
11.942 +
11.943 + /// \brief Destructor of the path
11.944 + ///
11.945 + /// Destructor of the path
11.946 + ~StaticPath() {
11.947 + if (edges) delete[] edges;
11.948 + }
11.949 +
11.950 + /// \brief Template copy assignment
11.951 + ///
11.952 + /// This path can be initialized with any other path type. It just
11.953 + /// makes a copy of the given path.
11.954 + template <typename CPath>
11.955 + StaticPath& operator=(const CPath& cpath) {
11.956 + copyPath(*this, cpath);
11.957 + return *this;
11.958 + }
11.959 +
11.960 + /// \brief Iterator class to iterate on the edges of the paths
11.961 + ///
11.962 + /// This class is used to iterate on the edges of the paths
11.963 + ///
11.964 + /// Of course it converts to Graph::Edge
11.965 + class EdgeIt {
11.966 + friend class StaticPath;
11.967 + public:
11.968 + /// Default constructor
11.969 + EdgeIt() {}
11.970 + /// Invalid constructor
11.971 + EdgeIt(Invalid) : path(0), idx(-1) {}
11.972 + /// Initializate the constructor to the first edge of path
11.973 + EdgeIt(const StaticPath &_path)
11.974 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
11.975
11.976 private:
11.977
11.978 - int id;
11.979 - const Path *path;
11.980 + /// Constructor with starting point
11.981 + EdgeIt(const StaticPath &_path, int _idx)
11.982 + : idx(_idx), path(&_path) {}
11.983 +
11.984 + public:
11.985 +
11.986 + ///Conversion to Graph::Edge
11.987 + operator const Edge&() const {
11.988 + return path->nth(idx);
11.989 + }
11.990 +
11.991 + /// Next edge
11.992 + EdgeIt& operator++() {
11.993 + ++idx;
11.994 + if (idx >= path->length()) idx = -1;
11.995 + return *this;
11.996 + }
11.997 +
11.998 + /// Comparison operator
11.999 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
11.1000 + /// Comparison operator
11.1001 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
11.1002 + /// Comparison operator
11.1003 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
11.1004 +
11.1005 + private:
11.1006 + const StaticPath *path;
11.1007 + int idx;
11.1008 };
11.1009
11.1010 - protected:
11.1011 + /// \brief Gives back the nth edge.
11.1012 + ///
11.1013 + /// \pre n is in the [0..length() - 1] range
11.1014 + const Edge& nth(int n) const {
11.1015 + return edges[n];
11.1016 + }
11.1017
11.1018 - const Graph *graph;
11.1019 + /// \brief Initializes edge iterator to point to the nth edge.
11.1020 + EdgeIt nthIt(int n) const {
11.1021 + return EdgeIt(*this, n);
11.1022 + }
11.1023
11.1024 - typedef std::vector<Edge> Container;
11.1025 - Container edges;
11.1026 - Node start;
11.1027 + /// \brief Gives back the length of the path.
11.1028 + int length() const { return len; }
11.1029
11.1030 - public:
11.1031 + /// \brief Returns true when the path is empty.
11.1032 + int empty() const { return len == 0; }
11.1033
11.1034 - friend class Builder;
11.1035 + /// \break Erase all edge in the graph.
11.1036 + void clear() {
11.1037 + len = 0;
11.1038 + if (edges) delete[] edges;
11.1039 + edges = 0;
11.1040 + }
11.1041
11.1042 - /// \brief Class to build paths
11.1043 - ///
11.1044 - /// This class is used to fill a path with edges.
11.1045 - ///
11.1046 - /// You can push new edges to the front and to the back of the
11.1047 - /// path in arbitrary order then you should commit these changes
11.1048 - /// to the graph.
11.1049 - ///
11.1050 - /// Fundamentally, for most "Paths" (classes fulfilling the
11.1051 - /// PathConcept) while the builder is active (after the first
11.1052 - /// modifying operation and until the commit()) the original Path
11.1053 - /// is in a "transitional" state (operations on it have undefined
11.1054 - /// result). But in the case of Path the original path remains
11.1055 - /// unchanged until the commit. However we don't recomend that you
11.1056 - /// use this feature.
11.1057 - class Builder {
11.1058 - public:
11.1059 - /// \brief Constructor
11.1060 - ///
11.1061 - /// Constructor
11.1062 - /// \param _path the path you want to fill in.
11.1063 - Builder(Path &_path) : path(_path), start(INVALID) {}
11.1064 + /// \brief Gives back the first edge of the path.
11.1065 + const Edge& front() const {
11.1066 + return edges[0];
11.1067 + }
11.1068
11.1069 - /// \brief Destructor
11.1070 - ///
11.1071 - /// Destructor
11.1072 - ~Builder() {
11.1073 - LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
11.1074 - PathError());
11.1075 + /// \brief Gives back the last edge of the path.
11.1076 + const Edge& back() const {
11.1077 + return edges[len - 1];
11.1078 + }
11.1079 +
11.1080 +
11.1081 + typedef True BuildTag;
11.1082 +
11.1083 + template <typename CPath>
11.1084 + void build(const CPath& path) {
11.1085 + len = path.length();
11.1086 + edges = new Edge[len];
11.1087 + int index = 0;
11.1088 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
11.1089 + edges[index] = it;
11.1090 + ++index;
11.1091 }
11.1092 + }
11.1093
11.1094 - /// \brief Sets the starting node of the path.
11.1095 - ///
11.1096 - /// Sets the starting node of the path. Edge added to the path
11.1097 - /// afterwards have to be incident to this node. It should be
11.1098 - /// called if and only if the path is empty and before any call
11.1099 - /// to \ref pushFront() or \ref pushBack()
11.1100 - void setStartNode(const Node &_start) {
11.1101 - LEMON_ASSERT(path.empty() && start == INVALID, PathError());
11.1102 - start = _start;
11.1103 + template <typename CPath>
11.1104 + void buildRev(const CPath& path) {
11.1105 + len = path.length();
11.1106 + edges = new Edge[len];
11.1107 + int index = len;
11.1108 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
11.1109 + --index;
11.1110 + edges[index] = it;
11.1111 }
11.1112 + }
11.1113
11.1114 - /// \brief Push a new edge to the front of the path
11.1115 - ///
11.1116 - /// Push a new edge to the front of the path.
11.1117 - /// \sa setStartNode
11.1118 - void pushFront(const Edge& e) {
11.1119 - LEMON_ASSERT(front.empty() ||
11.1120 - (path.graph->source(front.back()) ==
11.1121 - path.graph->target(e)), PathError());
11.1122 - LEMON_ASSERT(path.empty() ||
11.1123 - (path.source() == path.graph->target(e)), PathError());
11.1124 - LEMON_ASSERT(!path.empty() || !front.empty() ||
11.1125 - (start == path.graph->target(e)), PathError());
11.1126 - front.push_back(e);
11.1127 - }
11.1128 -
11.1129 - /// \brief Push a new edge to the back of the path
11.1130 - ///
11.1131 - /// Push a new edge to the back of the path.
11.1132 - /// \sa setStartNode
11.1133 - void pushBack(const Edge& e) {
11.1134 - LEMON_ASSERT(back.empty() ||
11.1135 - (path.graph->target(back.back()) ==
11.1136 - path.graph->source(e)), PathError());
11.1137 - LEMON_ASSERT(path.empty() ||
11.1138 - (path.target() == path.graph->source(e)), PathError());
11.1139 - LEMON_ASSERT(!path.empty() || !back.empty() ||
11.1140 - (start == path.graph->source(e)), PathError());
11.1141 - back.push_back(e);
11.1142 - }
11.1143 -
11.1144 - /// \brief Commit the changes to the path.
11.1145 - ///
11.1146 - /// Commit the changes to the path.
11.1147 - void commit() {
11.1148 - if( !front.empty() || !back.empty() || start != INVALID) {
11.1149 - Container tmp;
11.1150 - tmp.reserve(front.size() + back.size() + path.length());
11.1151 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
11.1152 - tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
11.1153 - tmp.insert(tmp.end(), back.begin(), back.end());
11.1154 - path.edges.swap(tmp);
11.1155 - if (!front.empty()) {
11.1156 - path.start = path.graph->source(front.back());
11.1157 - } else {
11.1158 - path.start = start;
11.1159 - }
11.1160 - start = INVALID;
11.1161 - front.clear();
11.1162 - back.clear();
11.1163 - }
11.1164 - }
11.1165 -
11.1166 - /// \brief Reserve storage for the builder in advance.
11.1167 - ///
11.1168 - /// If you know a reasonable upper bound of the number of the
11.1169 - /// edges to add to the front, using this function you can speed
11.1170 - /// up the building.
11.1171 - void reserveFront(size_t r) {front.reserve(r);}
11.1172 -
11.1173 - /// \brief Reserve storage for the builder in advance.
11.1174 - ///
11.1175 - /// If you know a reasonable upper bound of the number of the
11.1176 - /// edges to add to the back, using this function you can speed
11.1177 - /// up the building.
11.1178 - void reserveBack(size_t r) {back.reserve(r);}
11.1179 -
11.1180 - private:
11.1181 -
11.1182 - Path &path;
11.1183 - Container front, back;
11.1184 - Node start;
11.1185 -
11.1186 - };
11.1187 -
11.1188 + private:
11.1189 + int len;
11.1190 + Edge* edges;
11.1191 };
11.1192
11.1193 ///@}
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/lemon/path_utils.h Mon Jan 08 10:39:59 2007 +0000
12.3 @@ -0,0 +1,140 @@
12.4 +/* -*- C++ -*-
12.5 + *
12.6 + * This file is a part of LEMON, a generic C++ optimization library
12.7 + *
12.8 + * Copyright (C) 2003-2006
12.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
12.11 + *
12.12 + * Permission to use, modify and distribute this software is granted
12.13 + * provided that this copyright notice appears in all copies. For
12.14 + * precise terms see the accompanying LICENSE file.
12.15 + *
12.16 + * This software is provided "AS IS" with no warranty of any kind,
12.17 + * express or implied, and with no claim as to its suitability for any
12.18 + * purpose.
12.19 + *
12.20 + */
12.21 +
12.22 +
12.23 +///\ingroup paths
12.24 +///\file
12.25 +///\brief Classes for representing paths in graphs.
12.26 +///
12.27 +
12.28 +#ifndef LEMON_PATH_UTILS_H
12.29 +#define LEMON_PATH_UTILS_H
12.30 +
12.31 +#include <lemon/concepts/path.h>
12.32 +
12.33 +namespace lemon {
12.34 +
12.35 + namespace _path_bits {
12.36 +
12.37 + template <typename Path, typename Enable = void>
12.38 + struct RevTagIndicator {
12.39 + static const bool value = false;
12.40 + };
12.41 +
12.42 + template <typename Graph>
12.43 + struct RevTagIndicator<
12.44 + Graph,
12.45 + typename enable_if<typename Graph::RevTag, void>::type
12.46 + > {
12.47 + static const bool value = true;
12.48 + };
12.49 +
12.50 + template <typename Target, typename Source,
12.51 + typename BuildEnable = void, typename RevEnable = void>
12.52 + struct PathCopySelector {
12.53 + static void copy(Target& target, const Source& source) {
12.54 + source.clear();
12.55 + for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
12.56 + target.addBack(it);
12.57 + }
12.58 + }
12.59 + };
12.60 +
12.61 + template <typename Target, typename Source, typename BuildEnable>
12.62 + struct PathCopySelector<
12.63 + Target, Source, BuildEnable,
12.64 + typename enable_if<typename Source::RevPathTag, void>::type> {
12.65 + static void copy(Target& target, const Source& source) {
12.66 + source.clear();
12.67 + for (typename Source::RevIt it(source); it != INVALID; ++it) {
12.68 + target.addFront(it);
12.69 + }
12.70 + }
12.71 + };
12.72 +
12.73 + template <typename Target, typename Source, typename RevEnable>
12.74 + struct PathCopySelector<
12.75 + Target, Source,
12.76 + typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
12.77 + static void copy(Target& target, const Source& source) {
12.78 + target.clear();
12.79 + target.build(source);
12.80 + }
12.81 + };
12.82 +
12.83 + template <typename Target, typename Source>
12.84 + struct PathCopySelector<
12.85 + Target, Source,
12.86 + typename enable_if<typename Target::BuildTag, void>::type,
12.87 + typename enable_if<typename Source::RevPathTag, void>::type> {
12.88 + static void copy(Target& target, const Source& source) {
12.89 + target.clear();
12.90 + target.buildRev(source);
12.91 + }
12.92 + };
12.93 +
12.94 + }
12.95 +
12.96 +
12.97 + /// \brief Make of copy of a path.
12.98 + ///
12.99 + /// Make of copy of a path.
12.100 + template <typename Target, typename Source>
12.101 + void copyPath(Target& target, const Source& source) {
12.102 + checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();
12.103 + _path_bits::PathCopySelector<Target, Source>::copy(target, source);
12.104 + }
12.105 +
12.106 + /// \brief Checks the path's consistency.
12.107 + ///
12.108 + /// Checks that each edge's target is the next's source.
12.109 + /// \Checks the path's consistency.
12.110 + ///
12.111 + /// Checks that each edge's target is the next's source.
12.112 + template <typename Graph, typename Path>
12.113 + bool checkPath(const Graph& graph, const Path& path) {
12.114 + typename Path::EdgeIt it(path);
12.115 + if (it == INVALID) return true;
12.116 + typename Graph::Node node = graph.target(it);
12.117 + ++it;
12.118 + while (it != INVALID) {
12.119 + if (graph.source(it) != node) return false;
12.120 + node = graph.target(it);
12.121 + ++it;
12.122 + }
12.123 + return true;
12.124 + }
12.125 +
12.126 + /// \brief Gives back the source of the path
12.127 + ///
12.128 + /// Gives back the source of the path.
12.129 + template <typename Graph, typename Path>
12.130 + typename Graph::Node pathSource(const Graph& graph, const Path& path) {
12.131 + return graph.source(path.front());
12.132 + }
12.133 +
12.134 + /// \brief Gives back the target of the path
12.135 + ///
12.136 + /// Gives back the target of the path.
12.137 + template <typename Graph, typename Path>
12.138 + typename Graph::Node pathTarget(const Graph& graph, const Path& path) {
12.139 + return graph.target(path.back());
12.140 + }
12.141 +}
12.142 +
12.143 +#endif
13.1 --- a/lemon/suurballe.h Fri Jan 05 10:59:18 2007 +0000
13.2 +++ b/lemon/suurballe.h Mon Jan 08 10:39:59 2007 +0000
13.3 @@ -26,6 +26,7 @@
13.4
13.5 #include <lemon/maps.h>
13.6 #include <vector>
13.7 +#include <lemon/path.h>
13.8 #include <lemon/ssp_min_cost_flow.h>
13.9
13.10 namespace lemon {
13.11 @@ -82,7 +83,7 @@
13.12 SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
13.13
13.14 //Container to store found paths
13.15 - std::vector< std::vector<Edge> > paths;
13.16 + std::vector<SimplePath<Graph> > paths;
13.17
13.18 public :
13.19
13.20 @@ -134,7 +135,7 @@
13.21 ++e;
13.22 }
13.23 n = G.target(e);
13.24 - paths[j].push_back(e);
13.25 + paths[j].addBack(e);
13.26 reversed[e] = 1-reversed[e];
13.27 }
13.28
13.29 @@ -170,6 +171,8 @@
13.30 return min_cost_flow.checkComplementarySlackness();
13.31 }
13.32
13.33 + typedef SimplePath<Graph> Path;
13.34 +
13.35 /// \brief Read the found paths.
13.36 ///
13.37 /// This function gives back the \c j-th path in argument p.
13.38 @@ -181,25 +184,17 @@
13.39 /// previous \c run, then the result here will be an empty path
13.40 /// (\c j can be 0 as well).
13.41 ///
13.42 - /// \param Path The type of the path structure to put the result
13.43 - /// to (must meet lemon path concept).
13.44 - /// \param p The path to put the result to.
13.45 /// \param j Which path you want to get from the found paths (in a
13.46 /// real application you would get the found paths iteratively).
13.47 - template<typename Path>
13.48 - void getPath(Path& p, size_t j){
13.49 + Path path(int j) const {
13.50 + return paths[j];
13.51 + }
13.52
13.53 - p.clear();
13.54 - if (j>paths.size()-1){
13.55 - return;
13.56 - }
13.57 - typename Path::Builder B(p);
13.58 - for(typename std::vector<Edge>::iterator i=paths[j].begin();
13.59 - i!=paths[j].end(); ++i ){
13.60 - B.pushBack(*i);
13.61 - }
13.62 -
13.63 - B.commit();
13.64 + /// \brief Gives back the number of the paths.
13.65 + ///
13.66 + /// Gives back the number of the constructed paths.
13.67 + int pathNum() const {
13.68 + return paths.size();
13.69 }
13.70
13.71 }; //class Suurballe
14.1 --- a/test/all_pairs_shortest_path_test.cc Fri Jan 05 10:59:18 2007 +0000
14.2 +++ b/test/all_pairs_shortest_path_test.cc Mon Jan 08 10:39:59 2007 +0000
14.3 @@ -29,6 +29,8 @@
14.4
14.5 #include <lemon/fib_heap.h>
14.6
14.7 +#include <lemon/path.h>
14.8 +
14.9 #include <lemon/time_measure.h>
14.10 #include "test_tools.h"
14.11
14.12 @@ -90,6 +92,8 @@
14.13 cout << "FloydWarshall: " << timer << endl;
14.14 }
14.15
14.16 + bool checked_path = false;
14.17 +
14.18 for (NodeIt it(graph); it != INVALID; ++it) {
14.19 for (NodeIt jt(graph); jt != INVALID; ++jt) {
14.20 check(johnson.connected(it, jt) == floyd.connected(it, jt),
14.21 @@ -97,6 +101,22 @@
14.22 check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
14.23 "Wrong connection in all pairs shortest path");
14.24 if (johnson.connected(it, jt)) {
14.25 + if (it != jt && !checked_path) {
14.26 + {
14.27 + Path<Graph> path = johnson.path(it, jt);
14.28 + check(checkPath(graph, path), "Wrong path.");
14.29 + check(pathSource(graph, path) == it, "Wrong path.");
14.30 + check(pathTarget(graph, path) == jt, "Wrong path.");
14.31 + }
14.32 + {
14.33 + Path<Graph> path = floyd.path(it, jt);
14.34 + check(checkPath(graph, path), "Wrong path.");
14.35 + check(pathSource(graph, path) == it, "Wrong path.");
14.36 + check(pathTarget(graph, path) == jt, "Wrong path.");
14.37 + }
14.38 + checked_path = true;
14.39 + std::cout << "Path checked" << std::endl;
14.40 + }
14.41 check(johnson.dist(it, jt) == floyd.dist(it, jt),
14.42 "Wrong distance in all pairs shortest path");
14.43 check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
15.1 --- a/test/bfs_test.cc Fri Jan 05 10:59:18 2007 +0000
15.2 +++ b/test/bfs_test.cc Mon Jan 08 10:39:59 2007 +0000
15.3 @@ -59,8 +59,7 @@
15.4 // pn = bfs_test.predNodeMap();
15.5 b = bfs_test.reached(n);
15.6
15.7 - Path<Graph> pp(G);
15.8 - bfs_test.getPath(pp,n);
15.9 + Path<Graph> pp = bfs_test.path(n);
15.10 }
15.11
15.12 void check_Bfs_Function_Compile()
15.13 @@ -109,9 +108,11 @@
15.14
15.15 check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
15.16
15.17 - Path<Graph> p(G);
15.18 - check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
15.19 + Path<Graph> p = bfs_test.path(t);
15.20 check(p.length()==3,"getPath() found a wrong path.");
15.21 + check(checkPath(G, p),"path() found a wrong path.");
15.22 + check(pathSource(G, p) == s,"path() found a wrong path.");
15.23 + check(pathTarget(G, p) == t,"path() found a wrong path.");
15.24
15.25
15.26 for(EdgeIt e(G); e==INVALID; ++e) {
16.1 --- a/test/dfs_test.cc Fri Jan 05 10:59:18 2007 +0000
16.2 +++ b/test/dfs_test.cc Mon Jan 08 10:39:59 2007 +0000
16.3 @@ -59,8 +59,7 @@
16.4 // pn = dfs_test.predNodeMap();
16.5 b = dfs_test.reached(n);
16.6
16.7 - Path<Graph> pp(G);
16.8 - dfs_test.getPath(pp,n);
16.9 + Path<Graph> pp = dfs_test.path(n);
16.10 }
16.11
16.12
16.13 @@ -108,9 +107,11 @@
16.14 Dfs<Graph> dfs_test(G);
16.15 dfs_test.run(s);
16.16
16.17 - Path<Graph> p(G);
16.18 - check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
16.19 - check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
16.20 + Path<Graph> p = dfs_test.path(t);
16.21 + check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
16.22 + check(checkPath(G, p),"path() found a wrong path.");
16.23 + check(pathSource(G, p) == s,"path() found a wrong path.");
16.24 + check(pathTarget(G, p) == t,"path() found a wrong path.");
16.25
16.26 for(NodeIt v(G); v!=INVALID; ++v) {
16.27 check(dfs_test.reached(v),"Each node should be reached.");
17.1 --- a/test/dijkstra_test.cc Fri Jan 05 10:59:18 2007 +0000
17.2 +++ b/test/dijkstra_test.cc Mon Jan 08 10:39:59 2007 +0000
17.3 @@ -63,8 +63,7 @@
17.4 // pn = dijkstra_test.predNodeMap();
17.5 b = dijkstra_test.reached(n);
17.6
17.7 - Path<Graph> pp(G);
17.8 - dijkstra_test.getPath(pp,n);
17.9 + Path<Graph> pp = dijkstra_test.path(n);
17.10 }
17.11
17.12 void check_Dijkstra_Function_Compile()
17.13 @@ -120,9 +119,11 @@
17.14 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
17.15
17.16
17.17 - Path<Graph> p(G);
17.18 - check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
17.19 + Path<Graph> p = dijkstra_test.path(t);
17.20 check(p.length()==4,"getPath() found a wrong path.");
17.21 + check(checkPath(G, p),"path() found a wrong path.");
17.22 + check(pathSource(G, p) == s,"path() found a wrong path.");
17.23 + check(pathTarget(G, p) == t,"path() found a wrong path.");
17.24
17.25
17.26 for(EdgeIt e(G); e!=INVALID; ++e) {
18.1 --- a/test/path_test.cc Fri Jan 05 10:59:18 2007 +0000
18.2 +++ b/test/path_test.cc Mon Jan 08 10:39:59 2007 +0000
18.3 @@ -31,78 +31,14 @@
18.4 using namespace lemon;
18.5
18.6 void check_concepts() {
18.7 - checkConcept<concepts::Path<concepts::Graph>,
18.8 - concepts::Path<concepts::Graph> >();
18.9 - checkConcept<concepts::Path<concepts::Graph>,
18.10 - Path<concepts::Graph> >();
18.11 + checkConcept<concepts::Path<ListGraph>, concepts::Path<ListGraph> >();
18.12 checkConcept<concepts::Path<ListGraph>, Path<ListGraph> >();
18.13 + checkConcept<concepts::Path<ListGraph>, SimplePath<ListGraph> >();
18.14 + checkConcept<concepts::Path<ListGraph>, StaticPath<ListGraph> >();
18.15 + checkConcept<concepts::Path<ListGraph>, ListPath<ListGraph> >();
18.16 }
18.17
18.18 int main() {
18.19 - check_concepts();
18.20 -
18.21 - ListGraph g;
18.22 -
18.23 - ListGraph::Node n1 = g.addNode();
18.24 - ListGraph::Node n2 = g.addNode();
18.25 - ListGraph::Node n3 = g.addNode();
18.26 - ListGraph::Node n4 = g.addNode();
18.27 - ListGraph::Node n5 = g.addNode();
18.28 -
18.29 - ListGraph::Edge e1 = g.addEdge(n1, n2);
18.30 - ListGraph::Edge e2 = g.addEdge(n2, n3);
18.31 - ListGraph::Edge e3 = g.addEdge(n3, n4);
18.32 - ListGraph::Edge e4 = g.addEdge(n4, n5);
18.33 - ListGraph::Edge e5 = g.addEdge(n5, n1);
18.34 -
18.35 - {
18.36 - Path<ListGraph> p(g);
18.37 -
18.38 - check(p.empty(), "Wrong Path");
18.39 - check(p.length() == 0, "Wrong Path");
18.40 -
18.41 - {
18.42 - Path<ListGraph>::Builder b(p);
18.43 - b.setStartNode(n3);
18.44 - b.commit();
18.45 - }
18.46 -
18.47 - check(!p.empty(), "Wrong Path");
18.48 - check(p.length() == 0, "Wrong Path");
18.49 - check(p.source() == n3, "Wrong Path");
18.50 - check(p.target() == n3, "Wrong Path");
18.51 -
18.52 - {
18.53 - Path<ListGraph>::Builder b(p);
18.54 - b.pushBack(e3);
18.55 - b.pushBack(e4);
18.56 - b.pushFront(e2);
18.57 - b.commit();
18.58 - }
18.59 -
18.60 - check(!p.empty(), "Wrong Path");
18.61 - check(p.length() == 3, "Wrong Path");
18.62 - check(p.source() == n2, "Wrong Path");
18.63 - check(p.target() == n5, "Wrong Path");
18.64 -
18.65 - {
18.66 - Path<ListGraph>::NodeIt it(p);
18.67 - check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
18.68 - check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
18.69 - check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
18.70 - check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
18.71 - check((ListGraph::Node)it == INVALID, "Wrong Path");
18.72 - }
18.73 -
18.74 - {
18.75 - Path<ListGraph>::EdgeIt it(p);
18.76 - check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
18.77 - check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
18.78 - check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
18.79 - check((ListGraph::Edge)it == INVALID, "Wrong Path");
18.80 - }
18.81 -
18.82 - }
18.83 -
18.84 + check_concepts();
18.85 return 0;
18.86 }