lemon-0.x: lemon/path.h@269a0dcee70b

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    20 ///\ingroup paths

    21 ///\file

    22 ///\brief Classes for representing paths in graphs.

    23 ///

    25 #ifndef LEMON_PATH_H

    26 #define LEMON_PATH_H

    28 #include <vector>

    29 #include <algorithm>

    31 #include <lemon/error.h>

    32 #include <lemon/bits/invalid.h>

    34 namespace lemon {

    36   /// \addtogroup paths

    37   /// @{

    40   //! \brief A structure for representing directed paths in a graph.

    41   //!

    42   //! A structure for representing directed path in a graph.

    43   //! \param Graph The graph type in which the path is.

    44   //!

    45   //! In a sense, the path can be treated as a graph, for is has \c NodeIt

    46   //! and \c EdgeIt with the same usage. These types converts to the \c Node

    47   //! and \c Edge of the original graph.

    48   //!

    49   //! \todo Thoroughfully check all the range and consistency tests.

    50   template<typename Graph>

    51   class Path {

    52   public:

    53     /// Edge type of the underlying graph.

    54     typedef typename Graph::Edge Edge;

    55     /// Node type of the underlying graph.

    56     typedef typename Graph::Node Node;

    58     class NodeIt;

    59     class EdgeIt;

    61     struct PathError : public LogicError {

    62       virtual const char* what() const throw() {

    63         return "lemon::PathError";

    64       }

    65     };

    67   public:

    69     /// \brief Constructor

    70     ///

    71     /// Constructor

    72     /// \param _G The graph in which the path is.

    73     Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}

    75     /// \brief Subpath constructor.

    76     ///

    77     /// Subpath defined by two nodes.

    78     /// \warning It is an error if the two edges are not in order!

    79     Path(const Path &other, const NodeIt &a, const NodeIt &b) {

    80       graph = other.graph;

    81       start = a;

    82       edges.insert(edges.end(),

    83                    other.edges.begin() + a.id, other.edges.begin() + b.id);

    84     }

    86     /// \brief Subpath constructor.

    87     ///

    88     /// Subpath defined by two edges. Contains edges in [a,b)

    89     /// \warning It is an error if the two edges are not in order!

    90     Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {

    91       graph = other.graph;

    92       start = graph->source(a);

    93       edges.insert(edges.end(),

    94                    other.edges.begin() + a.id, other.edges.begin() + b.id);

    95     }

    97     /// \brief Length of the path.

    98     ///

    99     /// The number of the edges in the path. It can be zero if the

   100     /// path has only one node or it is empty.

   101     int length() const { return edges.size(); }

   103     /// \brief Returns whether the path is empty.

   104     ///

   105     /// Returns true when the path does not contain neither edge nor

   106     /// node.

   107     bool empty() const { return start == INVALID; }

   109     /// \brief Resets the path to an empty path.

   110     ///

   111     /// Resets the path to an empty path.

   112     void clear() { edges.clear(); start = INVALID; }

   114     /// \brief Starting point of the path.

   115     ///

   116     /// Starting point of the path.

   117     /// Returns INVALID if the path is empty.

   118     Node source() const {

   119       return start;

   120     }

   121     /// \brief End point of the path.

   122     ///

   123     /// End point of the path.

   124     /// Returns INVALID if the path is empty.

   125     Node target() const {

   126       return length() == 0 ? start : graph->target(edges[length()-1]);

   127     }

   129     /// \brief Gives back a node iterator to point to the node of a

   130     /// given index.

   131     ///

   132     /// Gives back a node iterator to point to the node of a given

   133     /// index.

   134     /// \pre n should less or equal to \c length()

   135     NodeIt nthNode(int n) const {

   136       return NodeIt(*this, n);

   137     }

   139     /// \brief Gives back an edge iterator to point to the edge of a

   140     /// given index.

   141     ///

   142     /// Gives back an edge iterator to point to the node of a given

   143     /// index.

   144     /// \pre n should less than \c length()

   145     EdgeIt nthEdge(int n) const {

   146       return EdgeIt(*this, n);

   147     }

   149     /// \brief Returns node iterator pointing to the source node of the

   150     /// given edge iterator.

   151     ///

   152     /// Returns node iterator pointing to the source node of the given

   153     /// edge iterator.

   154     NodeIt source(const EdgeIt& e) const {

   155       return NodeIt(*this, e.id);

   156     }

   158     /// \brief Returns node iterator pointing to the target node of the

   159     /// given edge iterator.

   160     ///

   161     /// Returns node iterator pointing to the target node of the given

   162     /// edge iterator.

   163     NodeIt target(const EdgeIt& e) const {

   164       return NodeIt(*this, e.id + 1);

   165     }

   168     /// \brief Iterator class to iterate on the nodes of the paths

   169     ///

   170     /// This class is used to iterate on the nodes of the paths

   171     ///

   172     /// Of course it converts to Graph::Node

   173     class NodeIt {

   174       friend class Path;

   175     public:

   177       /// \brief Default constructor

   178       ///

   179       /// Default constructor

   180       NodeIt() {}

   182       /// \brief Invalid constructor

   183       ///

   184       /// Invalid constructor

   185       NodeIt(Invalid) : id(-1), path(0) {}

   187       /// \brief Constructor with starting point

   188       ///

   189       /// Constructor with starting point

   190       NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {

   191         if (id > path->length()) id = -1;

   192       }

   194       /// \brief Conversion to Graph::Node

   195       ///

   196       /// Conversion to Graph::Node

   197       operator Node() const {

   198 	if (id > 0) {

   199 	  return path->graph->target(path->edges[id - 1]);

   200 	} else if (id == 0) {

   201 	  return path->start;

   202 	} else {

   203 	  return INVALID;

   204         }

   205       }

   207       /// \brief Steps to the next node

   208       ///

   209       /// Steps to the next node

   210       NodeIt& operator++() {

   211         ++id;

   212         if (id > path->length()) id = -1;

   213         return *this;

   214       }

   216       /// \brief Comparison operator

   217       ///

   218       /// Comparison operator

   219       bool operator==(const NodeIt& n) const { return id == n.id; }

   221       /// \brief Comparison operator

   222       ///

   223       /// Comparison operator

   224       bool operator!=(const NodeIt& n) const { return id != n.id; }

   226       /// \brief Comparison operator

   227       ///

   228       /// Comparison operator

   229       bool operator<(const NodeIt& n) const { return id < n.id; }

   231     private:

   232       int id;

   233       const Path *path;

   234     };

   236     /// \brief Iterator class to iterate on the edges of the paths

   237     ///

   238     /// This class is used to iterate on the edges of the paths

   239     /// Of course it converts to Graph::Edge

   240     class EdgeIt {

   241       friend class Path;

   242     public:

   244       /// \brief Default constructor

   245       ///

   246       /// Default constructor

   247       EdgeIt() {}

   249       /// \brief Invalid constructor

   250       ///

   251       /// Invalid constructor

   252       EdgeIt(Invalid) : id(-1), path(0) {}

   254       /// \brief Constructor with starting point

   255       ///

   256       /// Constructor with starting point

   257       EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {

   258         if (id >= path->length()) id = -1;

   259       }

   261       /// \brief Conversion to Graph::Edge

   262       ///

   263       /// Conversion to Graph::Edge

   264       operator Edge() const {

   265 	return id != -1 ? path->edges[id] : INVALID;

   266       }

   268       /// \brief Steps to the next edge

   269       ///

   270       /// Steps to the next edge

   271       EdgeIt& operator++() {

   272         ++id;

   273         if (id >= path->length()) id = -1;

   274         return *this;

   275       }

   277       /// \brief Comparison operator

   278       ///

   279       /// Comparison operator

   280       bool operator==(const EdgeIt& e) const { return id == e.id; }

   282       /// \brief Comparison operator

   283       ///

   284       /// Comparison operator

   285       bool operator!=(const EdgeIt& e) const { return id != e.id; }

   287       /// \brief Comparison operator

   288       ///

   289       /// Comparison operator

   290       bool operator<(const EdgeIt& e) const { return id < e.id; }

   292     private:

   294       int id;

   295       const Path *path;

   296     };

   298   protected:

   300     const Graph *graph;

   302     typedef std::vector<Edge> Container;

   303     Container edges;

   304     Node start;

   306   public:

   308     friend class Builder;

   310     /// \brief Class to build paths

   311     ///

   312     /// This class is used to fill a path with edges.

   313     ///

   314     /// You can push new edges to the front and to the back of the

   315     /// path in arbitrary order then you should commit these changes

   316     /// to the graph.

   317     ///

   318     /// Fundamentally, for most "Paths" (classes fulfilling the

   319     /// PathConcept) while the builder is active (after the first

   320     /// modifying operation and until the commit()) the original Path

   321     /// is in a "transitional" state (operations on it have undefined

   322     /// result). But in the case of Path the original path remains

   323     /// unchanged until the commit. However we don't recomend that you

   324     /// use this feature.

   325     class Builder {

   326     public:

   327       /// \brief Constructor

   328       ///

   329       /// Constructor

   330       /// \param _path the path you want to fill in.

   331       Builder(Path &_path) : path(_path), start(INVALID) {}

   333       /// \brief Destructor

   334       ///

   335       /// Destructor

   336       ~Builder() {

   337         LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,

   338                      PathError());

   339       }

   341       /// \brief Sets the starting node of the path.

   342       ///

   343       /// Sets the starting node of the path. Edge added to the path

   344       /// afterwards have to be incident to this node.  It should be

   345       /// called if and only if the path is empty and before any call

   346       /// to \ref pushFront() or \ref pushBack()

   347       void setStartNode(const Node &_start) {

   348         LEMON_ASSERT(path.empty() && start == INVALID, PathError());

   349         start = _start;

   350       }

   352       /// \brief Push a new edge to the front of the path

   353       ///

   354       /// Push a new edge to the front of the path.

   355       /// \sa setStartNode

   356       void pushFront(const Edge& e) {

   357         LEMON_ASSERT(front.empty() ||

   358                      (path.graph->source(front.back()) ==

   359                       path.graph->target(e)), PathError());

   360         LEMON_ASSERT(path.empty() ||

   361                      (path.source() == path.graph->target(e)), PathError());

   362         LEMON_ASSERT(!path.empty() || !front.empty() ||

   363                      (start == path.graph->target(e)), PathError());

   364 	front.push_back(e);

   365       }

   367       /// \brief Push a new edge to the back of the path

   368       ///

   369       /// Push a new edge to the back of the path.

   370       /// \sa setStartNode

   371       void pushBack(const Edge& e) {

   372         LEMON_ASSERT(back.empty() ||

   373                      (path.graph->target(back.back()) ==

   374                       path.graph->source(e)), PathError());

   375         LEMON_ASSERT(path.empty() ||

   376                      (path.target() == path.graph->source(e)), PathError());

   377         LEMON_ASSERT(!path.empty() || !back.empty() ||

   378                      (start == path.graph->source(e)), PathError());

   379 	back.push_back(e);

   380       }

   382       /// \brief Commit the changes to the path.

   383       ///

   384       /// Commit the changes to the path.

   385       void commit() {

   386 	if( !front.empty() || !back.empty() || start != INVALID) {

   387 	  Container tmp;

   388 	  tmp.reserve(front.size() + back.size() + path.length());

   389 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());

   390 	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());

   391 	  tmp.insert(tmp.end(), back.begin(), back.end());

   392 	  path.edges.swap(tmp);

   393           if (!front.empty()) {

   394             path.start = path.graph->source(front.back());

   395           } else {

   396             path.start = start;

   397           }

   398           start = INVALID;

   399 	  front.clear();

   400 	  back.clear();

   401 	}

   402       }

   404       /// \brief Reserve storage for the builder in advance.

   405       ///

   406       /// If you know a reasonable upper bound of the number of the

   407       /// edges to add to the front, using this function you can speed

   408       /// up the building.

   409       void reserveFront(size_t r) {front.reserve(r);}

   411       /// \brief Reserve storage for the builder in advance.

   412       ///

   413       /// If you know a reasonable upper bound of the number of the

   414       /// edges to add to the back, using this function you can speed

   415       /// up the building.

   416       void reserveBack(size_t r) {back.reserve(r);}

   418     private:

   420       Path &path;

   421       Container front, back;

   422       Node start;

   424     };

   426   };

   428   ///@}

   430 } // namespace lemon

   432 #endif // LEMON_PATH_H

author	deba
	Tue, 17 Oct 2006 10:50:57 +0000
changeset 2247	269a0dcee70b
parent 2084	59769591eb60
child 2335	27aa03cd3121
permissions	-rw-r--r--