deba@2335: /* -*- C++ -*- deba@2335: * deba@2335: * This file is a part of LEMON, a generic C++ optimization library deba@2335: * alpar@2391: * Copyright (C) 2003-2007 deba@2335: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2335: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2335: * deba@2335: * Permission to use, modify and distribute this software is granted deba@2335: * provided that this copyright notice appears in all copies. For deba@2335: * precise terms see the accompanying LICENSE file. deba@2335: * deba@2335: * This software is provided "AS IS" with no warranty of any kind, deba@2335: * express or implied, and with no claim as to its suitability for any deba@2335: * purpose. deba@2335: * deba@2335: */ deba@2335: deba@2335: ///\ingroup paths deba@2335: ///\file deba@2335: ///\brief Classes for representing paths in graphs. deba@2335: /// deba@2335: deba@2335: #ifndef LEMON_PATH_UTILS_H deba@2335: #define LEMON_PATH_UTILS_H deba@2335: deba@2335: #include deba@2467: #include deba@2467: #include deba@2335: deba@2335: namespace lemon { deba@2335: deba@2335: namespace _path_bits { deba@2335: deba@2335: template deba@2335: struct RevTagIndicator { deba@2335: static const bool value = false; deba@2335: }; deba@2335: deba@2335: template deba@2335: struct RevTagIndicator< deba@2335: Graph, deba@2335: typename enable_if::type deba@2335: > { deba@2335: static const bool value = true; deba@2335: }; deba@2335: deba@2335: template deba@2335: struct PathCopySelector { deba@2335: static void copy(Target& target, const Source& source) { deba@2357: target.clear(); deba@2335: for (typename Source::EdgeIt it(source); it != INVALID; ++it) { deba@2335: target.addBack(it); deba@2335: } deba@2335: } deba@2335: }; deba@2335: deba@2335: template deba@2335: struct PathCopySelector< deba@2335: Target, Source, BuildEnable, deba@2335: typename enable_if::type> { deba@2335: static void copy(Target& target, const Source& source) { deba@2357: target.clear(); deba@2357: for (typename Source::RevEdgeIt it(source); it != INVALID; ++it) { deba@2335: target.addFront(it); deba@2335: } deba@2335: } deba@2335: }; deba@2335: deba@2335: template deba@2335: struct PathCopySelector< deba@2335: Target, Source, deba@2335: typename enable_if::type, RevEnable> { deba@2335: static void copy(Target& target, const Source& source) { deba@2335: target.clear(); deba@2335: target.build(source); deba@2335: } deba@2335: }; deba@2335: deba@2335: template deba@2335: struct PathCopySelector< deba@2335: Target, Source, deba@2335: typename enable_if::type, deba@2335: typename enable_if::type> { deba@2335: static void copy(Target& target, const Source& source) { deba@2335: target.clear(); deba@2335: target.buildRev(source); deba@2335: } deba@2335: }; deba@2335: deba@2335: } deba@2335: deba@2335: deba@2335: /// \brief Make of copy of a path. deba@2335: /// deba@2335: /// Make of copy of a path. deba@2335: template deba@2335: void copyPath(Target& target, const Source& source) { deba@2335: checkConcept, Source>(); deba@2335: _path_bits::PathCopySelector::copy(target, source); deba@2335: } deba@2335: deba@2335: /// \brief Checks the path's consistency. deba@2335: /// deba@2335: /// Checks that each edge's target is the next's source. alpar@2350: /// deba@2335: template deba@2335: bool checkPath(const Graph& graph, const Path& path) { deba@2335: typename Path::EdgeIt it(path); deba@2335: if (it == INVALID) return true; deba@2335: typename Graph::Node node = graph.target(it); deba@2335: ++it; deba@2335: while (it != INVALID) { deba@2335: if (graph.source(it) != node) return false; deba@2335: node = graph.target(it); deba@2335: ++it; deba@2335: } deba@2335: return true; deba@2335: } deba@2335: deba@2335: /// \brief Gives back the source of the path deba@2335: /// deba@2335: /// Gives back the source of the path. deba@2335: template deba@2335: typename Graph::Node pathSource(const Graph& graph, const Path& path) { deba@2335: return graph.source(path.front()); deba@2335: } deba@2335: deba@2335: /// \brief Gives back the target of the path deba@2335: /// deba@2335: /// Gives back the target of the path. deba@2335: template deba@2335: typename Graph::Node pathTarget(const Graph& graph, const Path& path) { deba@2335: return graph.target(path.back()); deba@2335: } deba@2467: deba@2467: /// \brief Class which helps to iterate the nodes of a path deba@2467: /// deba@2467: /// In a sense, the path can be treated as a list of edges. The deba@2467: /// lemon path type stores just this list. As a consequence it deba@2467: /// cannot enumerate the nodes in the path and the zero length paths deba@2467: /// cannot store the node. deba@2467: /// deba@2467: /// This class implements the node iterator of a path structure. To deba@2467: /// provide this feature, the underlying graph should be given to deba@2467: /// the constructor of the iterator. deba@2467: template deba@2467: class PathNodeIt { deba@2467: private: deba@2467: const typename Path::Graph *_graph; deba@2467: typename Path::EdgeIt _it; deba@2467: typename Path::Graph::Node _nd; deba@2467: deba@2467: public: deba@2467: deba@2467: typedef typename Path::Graph Graph; deba@2467: typedef typename Graph::Node Node; deba@2467: deba@2467: /// Default constructor deba@2467: PathNodeIt() {} deba@2467: /// Invalid constructor deba@2467: PathNodeIt(Invalid) deba@2467: : _graph(0), _it(INVALID), _nd(INVALID) {} deba@2467: /// Constructor deba@2467: PathNodeIt(const Graph& graph, const Path& path) deba@2467: : _graph(&graph), _it(path) { deba@2467: _nd = (_it != INVALID ? _graph->source(_it) : INVALID); deba@2467: } deba@2467: /// Constructor deba@2467: PathNodeIt(const Graph& graph, const Path& path, const Node& src) deba@2467: : _graph(&graph), _it(path), _nd(src) {} deba@2467: deba@2467: ///Conversion to Graph::Node deba@2467: operator Node() const { deba@2467: return _nd; deba@2467: } deba@2467: deba@2467: /// Next node deba@2467: PathNodeIt& operator++() { deba@2467: if (_it == INVALID) _nd = INVALID; deba@2467: else { deba@2467: _nd = _graph->target(_it); deba@2467: ++_it; deba@2467: } deba@2467: return *this; deba@2467: } deba@2467: deba@2467: /// Comparison operator deba@2467: bool operator==(const PathNodeIt& n) const { deba@2467: return _it == n._it && _nd == n._nd; deba@2467: } deba@2467: /// Comparison operator deba@2467: bool operator!=(const PathNodeIt& n) const { deba@2467: return _it != n._it || _nd != n._nd; deba@2467: } deba@2467: /// Comparison operator deba@2467: bool operator<(const PathNodeIt& n) const { deba@2467: return (_it < n._it && _nd != INVALID); deba@2467: } deba@2467: deba@2467: }; deba@2467: deba@2467: /// \brief Item writer for paths deba@2467: /// deba@2467: /// This class can write paths into files. You can store paths in deba@2467: /// distinict mapset or in attributes section. deba@2467: /// deba@2467: ///\code deba@2467: /// GraphWriter gw(std::cout, g); deba@2467: /// NodeMapWriter nmw(gw, g, gw); deba@2467: /// deba@2467: /// SmartGraph::NodeMap > pnm(g); deba@2467: /// for (SmartGraph::NodeIt n(g); n != INVALID; ++n) { deba@2467: /// pnm[n] = bfs.path(n); deba@2467: /// } deba@2467: /// nmw.writeNodeMap("pnm", pnm, PathWriter >(gw)); deba@2467: /// deba@2467: /// gw.run(); deba@2467: ///\endcode deba@2467: /// deba@2467: /// \warning Do not use this class to write node or edge map values deba@2467: /// into usual nodesets or edgesets. You will not be able to read deba@2467: /// back your paths. Rather use NodeMapWriter, EdgeSetWriter or deba@2467: /// UEdgeSetWriter to dump paths from maps to lemon file. deba@2467: template deba@2467: class PathWriter { deba@2467: private: deba@2467: deba@2467: typedef typename Path::Edge Edge; deba@2467: std::auto_ptr<_writer_bits::LabelWriterBase > edgeLabelWriter; deba@2467: deba@2467: public: deba@2467: deba@2467: typedef Path Value; deba@2467: deba@2467: PathWriter(const PathWriter& pw) { deba@2467: edgeLabelWriter.reset(pw.edgeLabelWriter->clone()); deba@2467: } deba@2467: deba@2467: /// \brief Constructor deba@2467: /// deba@2467: /// The paramter shold be an edge label writer which could deba@2467: /// be a GraphWriter or an EdgeSetWriter. deba@2467: template deba@2467: explicit PathWriter(const EdgeLabelWriter& _edgeLabelWriter) { deba@2467: edgeLabelWriter.reset(new _writer_bits:: deba@2467: LabelWriter(_edgeLabelWriter)); deba@2467: } deba@2467: deba@2467: /// \brief Writer function deba@2467: /// deba@2467: /// Writes the path to the current stream. The representation deba@2467: /// is the edge labels beetween parentheses. deba@2467: void write(std::ostream& os, const Value& value) const { deba@2467: if (!edgeLabelWriter->isLabelWriter()) { deba@2467: throw DataFormatError("Cannot find edgeset or label map"); deba@2467: } deba@2467: os << '(' << ' '; deba@2467: for (typename Path::EdgeIt e(value); e != INVALID; ++e) { deba@2467: edgeLabelWriter->write(os, e); deba@2467: os << ' '; deba@2467: } deba@2467: os << ')'; deba@2467: } deba@2467: deba@2467: }; deba@2467: deba@2467: namespace _path_bits { deba@2467: deba@2467: template deba@2467: class PathProxy { deba@2467: public: deba@2467: typedef False RevPathTag; deba@2467: deba@2467: typedef _Graph Graph; deba@2467: typedef typename Graph::Edge Edge; deba@2467: deba@2467: PathProxy(const std::vector& edges) deba@2467: : _edges(edges) {} deba@2467: deba@2467: int length() const { deba@2467: return _edges.size(); deba@2467: } deba@2467: deba@2467: bool empty() const { deba@2467: return _edges.size() == 0; deba@2467: } deba@2467: deba@2467: class EdgeIt { deba@2467: public: deba@2467: EdgeIt() {} deba@2467: EdgeIt(const PathProxy& path) deba@2467: : _path(&path), _index(0) {} deba@2467: deba@2467: operator const Edge() const { deba@2467: return _path->_edges[_index]; deba@2467: } deba@2467: deba@2467: EdgeIt& operator++() { deba@2467: ++_index; deba@2467: return *this; deba@2467: } deba@2467: deba@2467: bool operator==(Invalid) const { deba@2467: return int(_path->_edges.size()) == _index; deba@2467: } deba@2467: bool operator!=(Invalid) const { deba@2467: return int(_path->_edges.size()) != _index; deba@2467: } deba@2467: deba@2467: private: deba@2467: const PathProxy* _path; deba@2467: int _index; deba@2467: }; deba@2467: deba@2467: private: deba@2467: const std::vector& _edges; deba@2467: deba@2467: }; deba@2467: deba@2467: } deba@2467: deba@2467: /// \brief Item reader for paths deba@2467: /// deba@2467: /// This class can read paths from files. You can store paths in deba@2467: /// distinict mapset or in attributes section. deba@2467: /// deba@2467: ///\code deba@2467: /// GraphReader gr(std::cout, g); deba@2467: /// NodeMapReader nmr(gr, g, gr); deba@2467: /// deba@2467: /// SmartGraph::NodeMap > pnm(g); deba@2467: /// nmr.readNodeMap("pnm", pnm, PathReader >(gr)); deba@2467: /// deba@2467: /// gr.run(); deba@2467: ///\endcode deba@2467: /// deba@2467: /// \warning Do not use this class to read node or edge map values deba@2467: /// from nodesets or edgesets. The edges are not surely constructed deba@2467: /// when the edge list should be read. Rather use NodeMapReader, deba@2467: /// EdgeSetReader or UEdgeSetReader to read distinict map sets from file. deba@2467: template deba@2467: class PathReader { deba@2467: private: deba@2467: deba@2467: typedef typename Path::Edge Edge; deba@2467: std::auto_ptr<_reader_bits::LabelReaderBase > edgeLabelReader; deba@2467: deba@2467: public: deba@2467: deba@2467: typedef Path Value; deba@2467: deba@2467: PathReader(const PathReader& pw) { deba@2467: edgeLabelReader.reset(pw.edgeLabelReader->clone()); deba@2467: } deba@2467: deba@2467: /// \brief Constructor deba@2467: /// deba@2467: /// The paramter shold be an edge label reader which could deba@2467: /// be a GraphReader or an EdgeSetReader. deba@2467: template deba@2467: explicit PathReader(const EdgeLabelReader& _edgeLabelReader) { deba@2467: edgeLabelReader.reset(new _reader_bits:: deba@2467: LabelReader(_edgeLabelReader)); deba@2467: } deba@2467: deba@2467: deba@2467: /// \brief Reader function deba@2467: /// deba@2467: /// Reads the path from the current stream. The representation deba@2467: /// is the edge labels beetween parentheses. deba@2467: void read(std::istream& is, Value& value) const { deba@2467: if (!edgeLabelReader->isLabelReader()) { deba@2467: throw DataFormatError("Cannot find edgeset or label map"); deba@2467: } deba@2467: char c; deba@2467: if (!(is >> c) || c != '(') deba@2467: throw DataFormatError("PathReader format error"); deba@2467: std::vector v; deba@2467: while (is >> c && c != ')') { deba@2467: is.putback(c); deba@2467: Edge edge = edgeLabelReader->read(is); deba@2467: v.push_back(edge); deba@2467: } deba@2467: if (!is) throw DataFormatError("PathReader format error"); deba@2467: copyPath(value, _path_bits::PathProxy(v)); deba@2467: } deba@2467: deba@2467: }; deba@2467: deba@2335: } deba@2335: deba@2335: #endif