alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
hegyi@819: 
hegyi@819: 
hegyi@819: ///\ingroup paths
hegyi@819: ///\file
hegyi@819: ///\brief Classes for representing paths in graphs.
alpar@1151: ///
hegyi@819: 
alpar@921: #ifndef LEMON_PATH_H
alpar@921: #define LEMON_PATH_H
hegyi@819: 
hegyi@819: #include <vector>
hegyi@819: #include <algorithm>
hegyi@819: 
deba@2247: #include <lemon/error.h>
deba@1993: #include <lemon/bits/invalid.h>
hegyi@819: 
alpar@921: namespace lemon {
hegyi@819: 
hegyi@819:   /// \addtogroup paths
hegyi@819:   /// @{
hegyi@819: 
hegyi@819: 
hegyi@819:   //! \brief A structure for representing directed paths in a graph.
hegyi@819:   //!
hegyi@819:   //! A structure for representing directed path in a graph.
hegyi@819:   //! \param Graph The graph type in which the path is.
hegyi@837:   //!
hegyi@819:   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
hegyi@819:   //! and \c EdgeIt with the same usage. These types converts to the \c Node
hegyi@819:   //! and \c Edge of the original graph.
hegyi@819:   //!
hegyi@819:   //! \todo Thoroughfully check all the range and consistency tests.
hegyi@831:   template<typename Graph>
deba@2247:   class Path {
hegyi@819:   public:
hegyi@819:     /// Edge type of the underlying graph.
deba@2247:     typedef typename Graph::Edge Edge;
hegyi@819:     /// Node type of the underlying graph.
deba@2247:     typedef typename Graph::Node Node;
deba@2247: 
hegyi@819:     class NodeIt;
hegyi@819:     class EdgeIt;
hegyi@819: 
deba@2247:     struct PathError : public LogicError {
deba@2247:       virtual const char* what() const throw() {
deba@2247:         return "lemon::PathError";
deba@2247:       }      
deba@2247:     };
hegyi@819: 
hegyi@819:   public:
hegyi@819: 
deba@2247:     /// \brief Constructor
deba@2247:     ///
deba@2247:     /// Constructor 
hegyi@819:     /// \param _G The graph in which the path is.
deba@2247:     Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
deba@2247:     
hegyi@819:     /// \brief Subpath constructor.
hegyi@819:     ///
hegyi@819:     /// Subpath defined by two nodes.
hegyi@819:     /// \warning It is an error if the two edges are not in order!
deba@2247:     Path(const Path &other, const NodeIt &a, const NodeIt &b) {
deba@2247:       graph = other.graph; 
deba@2247:       start = a;
deba@2247:       edges.insert(edges.end(), 
deba@2247:                    other.edges.begin() + a.id, other.edges.begin() + b.id);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Subpath constructor.
hegyi@819:     ///
hegyi@819:     /// Subpath defined by two edges. Contains edges in [a,b)
hegyi@819:     /// \warning It is an error if the two edges are not in order!
deba@2247:     Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
deba@2247:       graph = other.graph;
deba@2247:       start = graph->source(a);
deba@2247:       edges.insert(edges.end(), 
deba@2247:                    other.edges.begin() + a.id, other.edges.begin() + b.id);
hegyi@819:     }
hegyi@819: 
deba@2247:     /// \brief Length of the path.
deba@2247:     ///
deba@2247:     /// The number of the edges in the path. It can be zero if the
deba@2247:     /// path has only one node or it is empty.
alpar@1282:     int length() const { return edges.size(); }
hegyi@819: 
deba@2247:     /// \brief Returns whether the path is empty.
deba@2247:     ///
deba@2247:     /// Returns true when the path does not contain neither edge nor
deba@2247:     /// node.
deba@2247:     bool empty() const { return start == INVALID; }
deba@2247: 
deba@2247:     /// \brief Resets the path to an empty path.
deba@2247:     ///
hegyi@819:     /// Resets the path to an empty path.
deba@2247:     void clear() { edges.clear(); start = INVALID; }
hegyi@819: 
hegyi@819:     /// \brief Starting point of the path.
hegyi@819:     ///
hegyi@819:     /// Starting point of the path.
hegyi@819:     /// Returns INVALID if the path is empty.
deba@2247:     Node source() const {
deba@2247:       return start;
hegyi@819:     }
hegyi@819:     /// \brief End point of the path.
hegyi@819:     ///
hegyi@819:     /// End point of the path.
hegyi@819:     /// Returns INVALID if the path is empty.
deba@2247:     Node target() const {
deba@2247:       return length() == 0 ? start : graph->target(edges[length()-1]);
hegyi@819:     }
hegyi@819: 
deba@2247:     /// \brief Gives back a node iterator to point to the node of a
deba@2247:     /// given index.
hegyi@819:     ///
deba@2247:     /// Gives back a node iterator to point to the node of a given
deba@2247:     /// index.
deba@2247:     /// \pre n should less or equal to \c length()
deba@2247:     NodeIt nthNode(int n) const {
deba@2247:       return NodeIt(*this, n);
hegyi@819:     }
hegyi@819: 
deba@2247:     /// \brief Gives back an edge iterator to point to the edge of a
deba@2247:     /// given index.
deba@2247:     ///
deba@2247:     /// Gives back an edge iterator to point to the node of a given
deba@2247:     /// index.  
deba@2247:     /// \pre n should less than \c length()
deba@2247:     EdgeIt nthEdge(int n) const {
deba@2247:       return EdgeIt(*this, n);
deba@2247:     }
deba@2247: 
deba@2247:     /// \brief Returns node iterator pointing to the source node of the
deba@2247:     /// given edge iterator.
deba@2247:     ///
deba@2247:     /// Returns node iterator pointing to the source node of the given
deba@2247:     /// edge iterator.
deba@2247:     NodeIt source(const EdgeIt& e) const {
deba@2247:       return NodeIt(*this, e.id);
hegyi@819:     }
hegyi@819: 
alpar@986:     /// \brief Returns node iterator pointing to the target node of the
hegyi@819:     /// given edge iterator.
deba@2247:     ///
deba@2247:     /// Returns node iterator pointing to the target node of the given
deba@2247:     /// edge iterator.
alpar@986:     NodeIt target(const EdgeIt& e) const {
deba@2247:       return NodeIt(*this, e.id + 1);
hegyi@819:     }
hegyi@819: 
hegyi@819: 
deba@2247:     /// \brief Iterator class to iterate on the nodes of the paths
deba@2247:     ///
deba@2247:     /// This class is used to iterate on the nodes of the paths
deba@2247:     ///
deba@2247:     /// Of course it converts to Graph::Node
deba@2247:     class NodeIt {
deba@2247:       friend class Path;
deba@2247:     public:
hegyi@819: 
deba@2247:       /// \brief Default constructor
deba@2247:       ///
deba@2247:       /// Default constructor
deba@2247:       NodeIt() {}
hegyi@819: 
deba@2247:       /// \brief Invalid constructor
deba@2247:       ///
deba@2247:       /// Invalid constructor
deba@2247:       NodeIt(Invalid) : id(-1), path(0) {}
deba@2247: 
deba@2247:       /// \brief Constructor with starting point
deba@2247:       /// 
deba@2247:       /// Constructor with starting point
deba@2247:       NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
deba@2247:         if (id > path->length()) id = -1; 
deba@2247:       }
deba@2247: 
deba@2247:       /// \brief Conversion to Graph::Node
deba@2247:       ///
deba@2247:       /// Conversion to Graph::Node
deba@2247:       operator Node() const {
deba@2247: 	if (id > 0) {
deba@2247: 	  return path->graph->target(path->edges[id - 1]);
deba@2247: 	} else if (id == 0) {
deba@2247: 	  return path->start;
deba@2247: 	} else {
deba@2247: 	  return INVALID;
deba@2247:         }
deba@2247:       }
deba@2247: 
deba@2247:       /// \brief Steps to the next node
deba@2247:       ///
deba@2247:       /// Steps to the next node
deba@2247:       NodeIt& operator++() { 
deba@2247:         ++id; 
deba@2247:         if (id > path->length()) id = -1; 
deba@2247:         return *this; 
deba@2247:       }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2247:       ///
deba@2247:       /// Comparison operator
deba@2247:       bool operator==(const NodeIt& n) const { return id == n.id; }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2247:       ///
deba@2247:       /// Comparison operator
deba@2247:       bool operator!=(const NodeIt& n) const { return id != n.id; }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2247:       ///
deba@2247:       /// Comparison operator
deba@2247:       bool operator<(const NodeIt& n) const { return id < n.id; }
deba@2247: 
deba@2247:     private:
deba@2247:       int id;
deba@2247:       const Path *path;
deba@2247:     };
deba@2247: 
deba@2247:     /// \brief Iterator class to iterate on the edges of the paths
deba@2247:     ///
deba@2247:     /// This class is used to iterate on the edges of the paths
deba@2247:     /// Of course it converts to Graph::Edge
hegyi@819:     class EdgeIt {
deba@2247:       friend class Path;
deba@2247:     public:
hegyi@819: 
deba@2247:       /// \brief Default constructor
deba@2247:       ///
hegyi@819:       /// Default constructor
hegyi@819:       EdgeIt() {}
deba@2247: 
deba@2247:       /// \brief Invalid constructor
deba@2247:       ///
hegyi@819:       /// Invalid constructor
deba@2247:       EdgeIt(Invalid) : id(-1), path(0) {}
deba@2247: 
deba@2247:       /// \brief Constructor with starting point
deba@2247:       ///
hegyi@819:       /// Constructor with starting point
deba@2247:       EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 
deba@2247:         if (id >= path->length()) id = -1;
hegyi@819:       }
hegyi@819: 
deba@2247:       /// \brief Conversion to Graph::Edge
deba@2247:       ///
deba@2247:       /// Conversion to Graph::Edge
deba@2247:       operator Edge() const {
deba@2247: 	return id != -1 ? path->edges[id] : INVALID;
deba@2247:       }
hegyi@819: 
deba@2247:       /// \brief Steps to the next edge
deba@2247:       ///
deba@2247:       /// Steps to the next edge
deba@2247:       EdgeIt& operator++() { 
deba@2247:         ++id; 
deba@2247:         if (id >= path->length()) id = -1;
deba@2247:         return *this; 
deba@2247:       }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2247:       ///
hegyi@819:       /// Comparison operator
deba@2247:       bool operator==(const EdgeIt& e) const { return id == e.id; }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2247:       ///
hegyi@819:       /// Comparison operator
deba@2247:       bool operator!=(const EdgeIt& e) const { return id != e.id; }
deba@2247: 
deba@2247:       /// \brief Comparison operator
deba@2247:       ///
hegyi@819:       /// Comparison operator
deba@2247:       bool operator<(const EdgeIt& e) const { return id < e.id; }
hegyi@819: 
hegyi@819:     private:
deba@2247: 
deba@2247:       int id;
deba@2247:       const Path *path;
hegyi@819:     };
hegyi@819: 
deba@2247:   protected:
hegyi@819: 
deba@2247:     const Graph *graph;
hegyi@819: 
deba@2247:     typedef std::vector<Edge> Container;
deba@2247:     Container edges;
deba@2247:     Node start;
hegyi@819: 
deba@2247:   public:
hegyi@819: 
hegyi@837:     friend class Builder;
hegyi@819: 
deba@2247:     /// \brief Class to build paths
deba@2247:     ///
deba@2247:     /// This class is used to fill a path with edges.
deba@2247:     ///
deba@2247:     /// You can push new edges to the front and to the back of the
deba@2247:     /// path in arbitrary order then you should commit these changes
deba@2247:     /// to the graph.
deba@2247:     ///
deba@2247:     /// Fundamentally, for most "Paths" (classes fulfilling the
deba@2247:     /// PathConcept) while the builder is active (after the first
deba@2247:     /// modifying operation and until the commit()) the original Path
deba@2247:     /// is in a "transitional" state (operations on it have undefined
deba@2247:     /// result). But in the case of Path the original path remains
deba@2247:     /// unchanged until the commit. However we don't recomend that you
deba@2247:     /// use this feature.
hegyi@819:     class Builder {
deba@2247:     public:
deba@2247:       /// \brief Constructor
deba@2247:       ///
deba@2247:       /// Constructor
deba@2247:       /// \param _path the path you want to fill in.
deba@2247:       Builder(Path &_path) : path(_path), start(INVALID) {}
hegyi@819: 
deba@2247:       /// \brief Destructor
hegyi@819:       ///
deba@2247:       /// Destructor
deba@2247:       ~Builder() {
deba@2247:         LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 
deba@2247:                      PathError());
deba@2247:       }
hegyi@819: 
deba@2247:       /// \brief Sets the starting node of the path.
deba@2247:       ///
deba@2247:       /// Sets the starting node of the path. Edge added to the path
deba@2247:       /// afterwards have to be incident to this node.  It should be
deba@2247:       /// called if and only if the path is empty and before any call
deba@2247:       /// to \ref pushFront() or \ref pushBack()
deba@2247:       void setStartNode(const Node &_start) {
deba@2247:         LEMON_ASSERT(path.empty() && start == INVALID, PathError());
deba@2247:         start = _start;
deba@2247:       }
hegyi@837: 
deba@2247:       /// \brief Push a new edge to the front of the path
deba@2247:       ///
deba@2247:       /// Push a new edge to the front of the path.  
deba@2247:       /// \sa setStartNode
deba@2247:       void pushFront(const Edge& e) {
deba@2247:         LEMON_ASSERT(front.empty() || 
deba@2247:                      (path.graph->source(front.back()) == 
deba@2247:                       path.graph->target(e)), PathError());
deba@2247:         LEMON_ASSERT(path.empty() || 
deba@2247:                      (path.source() == path.graph->target(e)), PathError());
deba@2247:         LEMON_ASSERT(!path.empty() || !front.empty() ||
deba@2247:                      (start == path.graph->target(e)), PathError());
hegyi@819: 	front.push_back(e);
hegyi@819:       }
hegyi@819: 
deba@2247:       /// \brief Push a new edge to the back of the path
deba@2247:       ///
deba@2247:       /// Push a new edge to the back of the path.
deba@2247:       /// \sa setStartNode
deba@2247:       void pushBack(const Edge& e) {
deba@2247:         LEMON_ASSERT(back.empty() || 
deba@2247:                      (path.graph->target(back.back()) == 
deba@2247:                       path.graph->source(e)), PathError());
deba@2247:         LEMON_ASSERT(path.empty() || 
deba@2247:                      (path.target() == path.graph->source(e)), PathError());
deba@2247:         LEMON_ASSERT(!path.empty() || !back.empty() ||
deba@2247:                      (start == path.graph->source(e)), PathError());
hegyi@819: 	back.push_back(e);
hegyi@819:       }
hegyi@819: 
deba@2247:       /// \brief Commit the changes to the path.
deba@2247:       ///
deba@2247:       /// Commit the changes to the path.
hegyi@819:       void commit() {
deba@2247: 	if( !front.empty() || !back.empty() || start != INVALID) {
hegyi@819: 	  Container tmp;
deba@2247: 	  tmp.reserve(front.size() + back.size() + path.length());
hegyi@819: 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
deba@2247: 	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
hegyi@819: 	  tmp.insert(tmp.end(), back.begin(), back.end());
deba@2247: 	  path.edges.swap(tmp);
deba@2247:           if (!front.empty()) {
deba@2247:             path.start = path.graph->source(front.back());
deba@2247:           } else {
deba@2247:             path.start = start;
deba@2247:           }
deba@2247:           start = INVALID;
hegyi@819: 	  front.clear();
hegyi@819: 	  back.clear();
hegyi@819: 	}
hegyi@819:       }
hegyi@819: 
deba@2247:       /// \brief Reserve storage for the builder in advance.
deba@2247:       ///
deba@2247:       /// If you know a reasonable upper bound of the number of the
deba@2247:       /// edges to add to the front, using this function you can speed
deba@2247:       /// up the building.
hegyi@837:       void reserveFront(size_t r) {front.reserve(r);}
hegyi@837: 
deba@2247:       /// \brief Reserve storage for the builder in advance.
deba@2247:       ///
deba@2247:       /// If you know a reasonable upper bound of the number of the
deba@2247:       /// edges to add to the back, using this function you can speed
deba@2247:       /// up the building.
hegyi@837:       void reserveBack(size_t r) {back.reserve(r);}
hegyi@831: 
hegyi@819:     private:
hegyi@819: 
deba@2247:       Path &path;
deba@2247:       Container front, back;
deba@2247:       Node start;
hegyi@819: 
hegyi@819:     };
hegyi@819: 
hegyi@819:   };
hegyi@819: 
hegyi@819:   ///@}
hegyi@819: 
alpar@921: } // namespace lemon
hegyi@819: 
alpar@921: #endif // LEMON_PATH_H