deba@2335: /* -*- C++ -*-
deba@2335:  *
deba@2335:  * This file is a part of LEMON, a generic C++ optimization library
deba@2335:  *
alpar@2553:  * Copyright (C) 2003-2008
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 <lemon/concepts/path.h>
deba@2467: #include <lemon/lemon_reader.h>
deba@2467: #include <lemon/lemon_writer.h>
deba@2335: 
deba@2335: namespace lemon {
deba@2335: 
deba@2335:   namespace _path_bits {
deba@2335: 
deba@2335:     template <typename Path, typename Enable = void>
deba@2335:     struct RevTagIndicator {
deba@2335:       static const bool value = false;
deba@2335:     };
deba@2335: 
deba@2335:     template <typename Graph>
deba@2335:     struct RevTagIndicator<
deba@2335:       Graph, 
deba@2335:       typename enable_if<typename Graph::RevTag, void>::type
deba@2335:     > {
deba@2335:       static const bool value = true;
deba@2335:     };
deba@2335: 
deba@2335:     template <typename Target, typename Source,
deba@2335:               typename BuildEnable = void, typename RevEnable = void>
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 <typename Target, typename Source, typename BuildEnable>
deba@2335:     struct PathCopySelector<
deba@2335:       Target, Source, BuildEnable, 
deba@2335:       typename enable_if<typename Source::RevPathTag, void>::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 <typename Target, typename Source, typename RevEnable>
deba@2335:     struct PathCopySelector<
deba@2335:       Target, Source, 
deba@2335:       typename enable_if<typename Target::BuildTag, void>::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 <typename Target, typename Source>
deba@2335:     struct PathCopySelector<
deba@2335:       Target, Source, 
deba@2335:       typename enable_if<typename Target::BuildTag, void>::type,
deba@2335:       typename enable_if<typename Source::RevPathTag, void>::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 <typename Target, typename Source>
deba@2335:   void copyPath(Target& target, const Source& source) {
deba@2335:     checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();
deba@2335:     _path_bits::PathCopySelector<Target, Source>::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 <typename Graph, typename Path>
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 <typename Graph, typename Path>
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 <typename Graph, typename Path>
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 <typename Path>
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<SmartGraph> gw(std::cout, g);
deba@2467:   /// NodeMapWriter<SmartGraph> nmw(gw, g, gw);
deba@2467:   ///
deba@2467:   /// SmartGraph::NodeMap<Path<SmartGraph> > 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<Path<SmartGraph> >(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 <typename Path>
deba@2467:   class PathWriter {
deba@2467:   private:
deba@2467: 
deba@2467:     typedef typename Path::Edge Edge;
deba@2467:     std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > 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 <typename EdgeLabelWriter>
deba@2467:     explicit PathWriter(const EdgeLabelWriter& _edgeLabelWriter) {
deba@2467:       edgeLabelWriter.reset(new _writer_bits::
deba@2467: 	LabelWriter<Edge, EdgeLabelWriter>(_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 <typename _Graph>
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<Edge>& 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<Edge>& _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<SmartGraph> gr(std::cout, g);
deba@2467:   /// NodeMapReader<SmartGraph> nmr(gr, g, gr);
deba@2467:   ///
deba@2467:   /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
deba@2467:   /// nmr.readNodeMap("pnm", pnm, PathReader<Path<SmartGraph> >(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 <typename Path>
deba@2467:   class PathReader {
deba@2467:   private:
deba@2467: 
deba@2467:     typedef typename Path::Edge Edge;
deba@2467:     std::auto_ptr<_reader_bits::LabelReaderBase<Edge> > 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 <typename EdgeLabelReader>
deba@2467:     explicit PathReader(const EdgeLabelReader& _edgeLabelReader) {
deba@2467:       edgeLabelReader.reset(new _reader_bits::
deba@2467: 	LabelReader<Edge, EdgeLabelReader>(_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<typename Path::Edge> 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<typename Path::Edge>(v));
deba@2467:     }
deba@2467:     
deba@2467:   };
deba@2467:   
deba@2335: }
deba@2335: 
deba@2335: #endif