lemon-0.x: lemon/concepts/path.h@d6ec469aa019

     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  */

    19 ///\ingroup concept

    20 ///\file

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

    22 ///

    23 ///\todo Iterators have obsolete style

    25 #ifndef LEMON_CONCEPT_PATH_H

    26 #define LEMON_CONCEPT_PATH_H

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

    29 #include <lemon/concept_check.h>

    31 namespace lemon {

    32   namespace concepts {

    33     /// \addtogroup concept

    34     /// @{

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

    38     //!

    39     //! A skeleton structure for representing directed paths in a graph.

    40     //! \param _Graph The graph type in which the path is.

    41     //!

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

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

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

    45     template<typename _Graph>

    46     class Path {

    47     public:

    49       /// Type of the underlying graph.

    50       typedef _Graph Graph;

    51       /// Edge type of the underlying graph.

    52       typedef typename Graph::Edge Edge;

    53       /// Node type of the underlying graph.

    54       typedef typename Graph::Node Node;

    56       class NodeIt;

    57       class EdgeIt;

    59       /// \param _g The graph in which the path is.

    60       ///

    61       Path(const Graph &_g) {

    62 	ignore_unused_variable_warning(_g);

    63       }

    65       /// Length of the path ie. the number of edges in the path.

    66       int length() const {return 0;}

    68       /// Returns whether the path is empty.

    69       bool empty() const { return true;}

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

    72       void clear() {}

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

    75       ///

    76       /// Starting point of the path.

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

    78       Node target() const {return INVALID;}

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

    80       ///

    81       /// End point of the path.

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

    83       Node source() const {return INVALID;}

    85       /// \brief The target of an edge.

    86       ///

    87       /// Returns node iterator pointing to the target node of the

    88       /// given edge iterator.

    89       NodeIt target(const EdgeIt&) const {return INVALID;}

    91       /// \brief The source of an edge.

    92       ///

    93       /// Returns node iterator pointing to the source node of the

    94       /// given edge iterator.

    95       NodeIt source(const EdgeIt&) const {return INVALID;}

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

    98       ///

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

   100       ///

   101       /// Of course it converts to Graph::Node.

   102       class NodeIt {

   103       public:

   104 	/// Default constructor

   105 	NodeIt() {}

   106 	/// Invalid constructor

   107 	NodeIt(Invalid) {}

   108 	/// Constructor with starting point

   109 	NodeIt(const Path &) {}

   111 	///Conversion to Graph::Node

   112 	operator Node() const { return INVALID; }

   113 	/// Next node

   114 	NodeIt& operator++() {return *this;}

   116 	/// Comparison operator

   117 	bool operator==(const NodeIt&) const {return true;}

   118 	/// Comparison operator

   119 	bool operator!=(const NodeIt&) const {return true;}

   120  	/// Comparison operator

   121  	bool operator<(const NodeIt&) const {return false;}

   123       };

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

   126       ///

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

   128       ///

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

   130       class EdgeIt {

   131       public:

   132 	/// Default constructor

   133 	EdgeIt() {}

   134 	/// Invalid constructor

   135 	EdgeIt(Invalid) {}

   136 	/// Constructor with starting point

   137 	EdgeIt(const Path &) {}

   139 	operator Edge() const { return INVALID; }

   141 	/// Next edge

   142 	EdgeIt& operator++() {return *this;}

   144 	/// Comparison operator

   145 	bool operator==(const EdgeIt&) const {return true;}

   146 	/// Comparison operator

   147 	bool operator!=(const EdgeIt&) const {return true;}

   148  	/// Comparison operator

   149  	bool operator<(const EdgeIt&) const {return false;}

   151       };

   154       friend class Builder;

   156       /// \brief Class to build paths

   157       ///

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

   159       ///

   160       /// You can push new edges to the front and to the back of the path in

   161       /// arbitrary order then you should commit these changes to the graph.

   162       ///

   163       /// While the builder is active (after the first modifying

   164       /// operation and until the call of \ref commit()) the

   165       /// underlining Path is in a "transitional" state (operations on

   166       /// it have undefined result).

   167       class Builder {

   168       public:

   170         /// Constructor

   172         /// Constructor

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

   174 	///

   176 	Builder(Path &_path) { ignore_unused_variable_warning(_path); }

   178 	/// Sets the starting node of the path.

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

   181 	/// afterwards have to be incident to this node.

   182 	/// You \em must start building an empty path with these functions.

   183 	/// (And you \em must \em not use it later).

   184 	/// \sa pushFront()

   185 	/// \sa pushBack()

   186 	void setStartNode(const Node &) {}

   188 	///Push a new edge to the front of the path

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

   191 	///If the path is empty, you \em must call \ref setStartNode() before

   192 	///the first use of \ref pushFront().

   193 	void pushFront(const Edge&) {}

   195 	///Push a new edge to the back of the path

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

   198 	///If the path is empty, you \em must call \ref setStartNode() before

   199 	///the first use of \ref pushBack().

   200 	void pushBack(const Edge&) {}

   202 	///Commit the changes to the path.

   204 	///Commit the changes to the path.

   205         ///

   206 	void commit() {}

   208 	///Reserve (front) storage for the builder in advance.

   210 	///If you know a reasonable upper bound on the number of the edges

   211 	///to add to the front of the path,

   212 	///using this function you may speed up the building.

   213 	void reserveFront(size_t) {}

   214 	///Reserve (back) storage for the builder in advance.

   216 	///If you know a reasonable upper bound on the number of the edges

   217 	///to add to the back of the path,

   218 	///using this function you may speed up the building.

   219 	void reserveBack(size_t) {}

   220       };

   222       template <typename _Path>

   223       struct Constraints {

   224 	void constraints() {

   225           typedef typename _Path::Node Node;

   226           typedef typename _Path::NodeIt NodeIt;

   227           typedef typename Graph::Node GraphNode;

   229           typedef typename _Path::Edge Edge;

   230           typedef typename _Path::EdgeIt EdgeIt;

   231           typedef typename Graph::Edge GraphEdge;

   233           typedef typename _Path::Builder Builder;

   235           path = _Path(graph);

   237           bool b = cpath.empty();

   238           int l = cpath.length();

   240           Node gn;

   241           Edge ge;

   242           gn = cpath.source();

   243           gn = cpath.target();

   245           NodeIt nit;

   246           EdgeIt eit(INVALID);

   247           nit = path.source(eit);

   248           nit = path.target(eit);

   250           nit = NodeIt();

   251           nit = NodeIt(cpath);

   252           nit = INVALID;

   253           gn = nit;

   254           ++nit;

   255           b = nit == nit;

   256           b = nit != nit;

   257           b = nit < nit;

   259           eit = EdgeIt();

   260           eit = EdgeIt(cpath);

   261           eit = INVALID;

   262           ge = eit;

   263           ++eit;

   264           b = eit == eit;

   265           b = eit != eit;

   266           b = eit < eit;

   268           size_t st = 0;

   270           Builder builder(path);

   271           builder.setStartNode(gn);

   272           builder.pushFront(ge);

   273           builder.pushBack(ge);

   274           builder.commit();

   275           builder.reserveFront(st);

   276           builder.reserveBack(st);

   278           ignore_unused_variable_warning(l);

   279           ignore_unused_variable_warning(b);

   280 	}

   282         const Graph& graph;

   283         const _Path& cpath;

   284         _Path& path;

   285       };

   287     };

   289   ///@}

   290   }

   292 } // namespace lemon

   294 #endif // LEMON_CONCEPT_PATH_H

author	athos
	Mon, 04 Dec 2006 16:51:46 +0000
changeset 2325	d6ec469aa019
child 2335	27aa03cd3121
permissions	-rw-r--r--