1.1 --- a/lemon/path_utils.h Tue Aug 28 13:58:54 2007 +0000
1.2 +++ b/lemon/path_utils.h Tue Aug 28 14:00:42 2007 +0000
1.3 @@ -25,6 +25,8 @@
1.4 #define LEMON_PATH_UTILS_H
1.5
1.6 #include <lemon/concepts/path.h>
1.7 +#include <lemon/lemon_reader.h>
1.8 +#include <lemon/lemon_writer.h>
1.9
1.10 namespace lemon {
1.11
1.12 @@ -132,6 +134,261 @@
1.13 typename Graph::Node pathTarget(const Graph& graph, const Path& path) {
1.14 return graph.target(path.back());
1.15 }
1.16 +
1.17 + /// \brief Class which helps to iterate the nodes of a path
1.18 + ///
1.19 + /// In a sense, the path can be treated as a list of edges. The
1.20 + /// lemon path type stores just this list. As a consequence it
1.21 + /// cannot enumerate the nodes in the path and the zero length paths
1.22 + /// cannot store the node.
1.23 + ///
1.24 + /// This class implements the node iterator of a path structure. To
1.25 + /// provide this feature, the underlying graph should be given to
1.26 + /// the constructor of the iterator.
1.27 + template <typename Path>
1.28 + class PathNodeIt {
1.29 + private:
1.30 + const typename Path::Graph *_graph;
1.31 + typename Path::EdgeIt _it;
1.32 + typename Path::Graph::Node _nd;
1.33 +
1.34 + public:
1.35 +
1.36 + typedef typename Path::Graph Graph;
1.37 + typedef typename Graph::Node Node;
1.38 +
1.39 + /// Default constructor
1.40 + PathNodeIt() {}
1.41 + /// Invalid constructor
1.42 + PathNodeIt(Invalid)
1.43 + : _graph(0), _it(INVALID), _nd(INVALID) {}
1.44 + /// Constructor
1.45 + PathNodeIt(const Graph& graph, const Path& path)
1.46 + : _graph(&graph), _it(path) {
1.47 + _nd = (_it != INVALID ? _graph->source(_it) : INVALID);
1.48 + }
1.49 + /// Constructor
1.50 + PathNodeIt(const Graph& graph, const Path& path, const Node& src)
1.51 + : _graph(&graph), _it(path), _nd(src) {}
1.52 +
1.53 + ///Conversion to Graph::Node
1.54 + operator Node() const {
1.55 + return _nd;
1.56 + }
1.57 +
1.58 + /// Next node
1.59 + PathNodeIt& operator++() {
1.60 + if (_it == INVALID) _nd = INVALID;
1.61 + else {
1.62 + _nd = _graph->target(_it);
1.63 + ++_it;
1.64 + }
1.65 + return *this;
1.66 + }
1.67 +
1.68 + /// Comparison operator
1.69 + bool operator==(const PathNodeIt& n) const {
1.70 + return _it == n._it && _nd == n._nd;
1.71 + }
1.72 + /// Comparison operator
1.73 + bool operator!=(const PathNodeIt& n) const {
1.74 + return _it != n._it || _nd != n._nd;
1.75 + }
1.76 + /// Comparison operator
1.77 + bool operator<(const PathNodeIt& n) const {
1.78 + return (_it < n._it && _nd != INVALID);
1.79 + }
1.80 +
1.81 + };
1.82 +
1.83 + /// \brief Item writer for paths
1.84 + ///
1.85 + /// This class can write paths into files. You can store paths in
1.86 + /// distinict mapset or in attributes section.
1.87 + ///
1.88 + ///\code
1.89 + /// GraphWriter<SmartGraph> gw(std::cout, g);
1.90 + /// NodeMapWriter<SmartGraph> nmw(gw, g, gw);
1.91 + ///
1.92 + /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
1.93 + /// for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
1.94 + /// pnm[n] = bfs.path(n);
1.95 + /// }
1.96 + /// nmw.writeNodeMap("pnm", pnm, PathWriter<Path<SmartGraph> >(gw));
1.97 + ///
1.98 + /// gw.run();
1.99 + ///\endcode
1.100 + ///
1.101 + /// \warning Do not use this class to write node or edge map values
1.102 + /// into usual nodesets or edgesets. You will not be able to read
1.103 + /// back your paths. Rather use NodeMapWriter, EdgeSetWriter or
1.104 + /// UEdgeSetWriter to dump paths from maps to lemon file.
1.105 + template <typename Path>
1.106 + class PathWriter {
1.107 + private:
1.108 +
1.109 + typedef typename Path::Edge Edge;
1.110 + std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > edgeLabelWriter;
1.111 +
1.112 + public:
1.113 +
1.114 + typedef Path Value;
1.115 +
1.116 + PathWriter(const PathWriter& pw) {
1.117 + edgeLabelWriter.reset(pw.edgeLabelWriter->clone());
1.118 + }
1.119 +
1.120 + /// \brief Constructor
1.121 + ///
1.122 + /// The paramter shold be an edge label writer which could
1.123 + /// be a GraphWriter or an EdgeSetWriter.
1.124 + template <typename EdgeLabelWriter>
1.125 + explicit PathWriter(const EdgeLabelWriter& _edgeLabelWriter) {
1.126 + edgeLabelWriter.reset(new _writer_bits::
1.127 + LabelWriter<Edge, EdgeLabelWriter>(_edgeLabelWriter));
1.128 + }
1.129 +
1.130 + /// \brief Writer function
1.131 + ///
1.132 + /// Writes the path to the current stream. The representation
1.133 + /// is the edge labels beetween parentheses.
1.134 + void write(std::ostream& os, const Value& value) const {
1.135 + if (!edgeLabelWriter->isLabelWriter()) {
1.136 + throw DataFormatError("Cannot find edgeset or label map");
1.137 + }
1.138 + os << '(' << ' ';
1.139 + for (typename Path::EdgeIt e(value); e != INVALID; ++e) {
1.140 + edgeLabelWriter->write(os, e);
1.141 + os << ' ';
1.142 + }
1.143 + os << ')';
1.144 + }
1.145 +
1.146 + };
1.147 +
1.148 + namespace _path_bits {
1.149 +
1.150 + template <typename _Graph>
1.151 + class PathProxy {
1.152 + public:
1.153 + typedef False RevPathTag;
1.154 +
1.155 + typedef _Graph Graph;
1.156 + typedef typename Graph::Edge Edge;
1.157 +
1.158 + PathProxy(const std::vector<Edge>& edges)
1.159 + : _edges(edges) {}
1.160 +
1.161 + int length() const {
1.162 + return _edges.size();
1.163 + }
1.164 +
1.165 + bool empty() const {
1.166 + return _edges.size() == 0;
1.167 + }
1.168 +
1.169 + class EdgeIt {
1.170 + public:
1.171 + EdgeIt() {}
1.172 + EdgeIt(const PathProxy& path)
1.173 + : _path(&path), _index(0) {}
1.174 +
1.175 + operator const Edge() const {
1.176 + return _path->_edges[_index];
1.177 + }
1.178 +
1.179 + EdgeIt& operator++() {
1.180 + ++_index;
1.181 + return *this;
1.182 + }
1.183 +
1.184 + bool operator==(Invalid) const {
1.185 + return int(_path->_edges.size()) == _index;
1.186 + }
1.187 + bool operator!=(Invalid) const {
1.188 + return int(_path->_edges.size()) != _index;
1.189 + }
1.190 +
1.191 + private:
1.192 + const PathProxy* _path;
1.193 + int _index;
1.194 + };
1.195 +
1.196 + private:
1.197 + const std::vector<Edge>& _edges;
1.198 +
1.199 + };
1.200 +
1.201 + }
1.202 +
1.203 + /// \brief Item reader for paths
1.204 + ///
1.205 + /// This class can read paths from files. You can store paths in
1.206 + /// distinict mapset or in attributes section.
1.207 + ///
1.208 + ///\code
1.209 + /// GraphReader<SmartGraph> gr(std::cout, g);
1.210 + /// NodeMapReader<SmartGraph> nmr(gr, g, gr);
1.211 + ///
1.212 + /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
1.213 + /// nmr.readNodeMap("pnm", pnm, PathReader<Path<SmartGraph> >(gr));
1.214 + ///
1.215 + /// gr.run();
1.216 + ///\endcode
1.217 + ///
1.218 + /// \warning Do not use this class to read node or edge map values
1.219 + /// from nodesets or edgesets. The edges are not surely constructed
1.220 + /// when the edge list should be read. Rather use NodeMapReader,
1.221 + /// EdgeSetReader or UEdgeSetReader to read distinict map sets from file.
1.222 + template <typename Path>
1.223 + class PathReader {
1.224 + private:
1.225 +
1.226 + typedef typename Path::Edge Edge;
1.227 + std::auto_ptr<_reader_bits::LabelReaderBase<Edge> > edgeLabelReader;
1.228 +
1.229 + public:
1.230 +
1.231 + typedef Path Value;
1.232 +
1.233 + PathReader(const PathReader& pw) {
1.234 + edgeLabelReader.reset(pw.edgeLabelReader->clone());
1.235 + }
1.236 +
1.237 + /// \brief Constructor
1.238 + ///
1.239 + /// The paramter shold be an edge label reader which could
1.240 + /// be a GraphReader or an EdgeSetReader.
1.241 + template <typename EdgeLabelReader>
1.242 + explicit PathReader(const EdgeLabelReader& _edgeLabelReader) {
1.243 + edgeLabelReader.reset(new _reader_bits::
1.244 + LabelReader<Edge, EdgeLabelReader>(_edgeLabelReader));
1.245 + }
1.246 +
1.247 +
1.248 + /// \brief Reader function
1.249 + ///
1.250 + /// Reads the path from the current stream. The representation
1.251 + /// is the edge labels beetween parentheses.
1.252 + void read(std::istream& is, Value& value) const {
1.253 + if (!edgeLabelReader->isLabelReader()) {
1.254 + throw DataFormatError("Cannot find edgeset or label map");
1.255 + }
1.256 + char c;
1.257 + if (!(is >> c) || c != '(')
1.258 + throw DataFormatError("PathReader format error");
1.259 + std::vector<typename Path::Edge> v;
1.260 + while (is >> c && c != ')') {
1.261 + is.putback(c);
1.262 + Edge edge = edgeLabelReader->read(is);
1.263 + v.push_back(edge);
1.264 + }
1.265 + if (!is) throw DataFormatError("PathReader format error");
1.266 + copyPath(value, _path_bits::PathProxy<typename Path::Edge>(v));
1.267 + }
1.268 +
1.269 + };
1.270 +
1.271 }
1.272
1.273 #endif