lemon-0.x: lemon/concepts/path.h@37fb2c384c78

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

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     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/bits/utility.h>

    30 #include <lemon/concept_check.h>

    32 namespace lemon {

    33   namespace concepts {

    35     /// \addtogroup concept

    36     /// @{

    38     /// \brief A skeleton structure for representing directed paths in

    39     /// a graph.

    40     ///

    41     /// A skeleton structure for representing directed paths in a

    42     /// graph.

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

    44     ///

    45     /// In a sense, the path can be treated as a list of edges. The

    46     /// lemon path type stores just this list. As a consequence it

    47     /// cannot enumerate the nodes in the path and the zero length

    48     /// paths cannot store the source.

    49     ///

    50     template <typename _Graph>

    51     class Path {

    52     public:

    54       /// Type of the underlying graph.

    55       typedef _Graph Graph;

    56       /// Edge type of the underlying graph.

    57       typedef typename Graph::Edge Edge;

    59       class EdgeIt;

    61       /// \brief Default constructor

    62       Path() {}

    64       /// \brief Template constructor

    65       template <typename CPath>

    66       Path(const CPath& cpath) {}

    68       /// \brief Template assigment

    69       template <typename CPath>

    70       Path& operator=(const CPath& cpath) {}

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

    73       int length() const { return 0;}

    75       /// Returns whether the path is empty.

    76       bool empty() const { return true;}

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

    79       void clear() {}

    81       /// \brief Lemon style iterator for path edges

    82       ///

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

    84       class EdgeIt {

    85       public:

    86 	/// Default constructor

    87 	EdgeIt() {}

    88 	/// Invalid constructor

    89 	EdgeIt(Invalid) {}

    90 	/// Constructor for first edge

    91 	EdgeIt(const Path &) {}

    93         /// Conversion to Edge

    94 	operator Edge() const { return INVALID; }

    96 	/// Next edge

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

    99 	/// Comparison operator

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

   101 	/// Comparison operator

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

   103  	/// Comparison operator

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

   106       };

   108       template <typename _Path>

   109       struct Constraints {

   110         void constraints() {

   111           Path<Graph> pc;

   112           _Path p, pp(pc);

   113           int l = p.length();

   114           int e = p.empty();

   115           p.clear();

   117           p = pc;

   119           typename _Path::EdgeIt id, ii(INVALID), i(p);

   121           ++i;

   122           typename Graph::Edge ed = i;

   124           e = (i == ii);

   125           e = (i != ii);

   126           e = (i < ii);

   128           ignore_unused_variable_warning(l);

   129           ignore_unused_variable_warning(pp);

   130           ignore_unused_variable_warning(e);

   131           ignore_unused_variable_warning(id);

   132           ignore_unused_variable_warning(ii);

   133           ignore_unused_variable_warning(ed);

   134         }

   135       };

   137     };

   139     namespace _path_bits {

   141       template <typename _Graph, typename _Path, typename RevPathTag = void>

   142       struct PathDumperConstraints {

   143         void constraints() {

   144           int l = p.length();

   145           int e = p.empty();

   147           typename _Path::EdgeIt id, i(p);

   149           ++i;

   150           typename _Graph::Edge ed = i;

   152           e = (i == INVALID);

   153           e = (i != INVALID);

   155           ignore_unused_variable_warning(l);

   156           ignore_unused_variable_warning(e);

   157           ignore_unused_variable_warning(id);

   158           ignore_unused_variable_warning(ed);

   159         }

   160         _Path& p;

   161       };

   163       template <typename _Graph, typename _Path>

   164       struct PathDumperConstraints<

   165         _Graph, _Path,

   166         typename enable_if<typename _Path::RevPathTag, void>::type

   167       > {

   168         void constraints() {

   169           int l = p.length();

   170           int e = p.empty();

   172           typename _Path::RevEdgeIt id, i(p);

   174           ++i;

   175           typename _Graph::Edge ed = i;

   177           e = (i == INVALID);

   178           e = (i != INVALID);

   180           ignore_unused_variable_warning(l);

   181           ignore_unused_variable_warning(e);

   182           ignore_unused_variable_warning(id);

   183           ignore_unused_variable_warning(ed);

   184         }

   185         _Path& p;

   186       };

   188     }

   191     /// \brief A skeleton structure for path dumpers.

   192     ///

   193     /// A skeleton structure for path dumpers. The path dumpers are

   194     /// the generalization of the paths. The path dumpers can

   195     /// enumerate the edges of the path wheter in forward or in

   196     /// backward order.  In most time these classes are not used

   197     /// directly rather it used to assign a dumped class to a real

   198     /// path type.

   199     ///

   200     /// The main purpose of this concept is that the shortest path

   201     /// algorithms can enumerate easily the edges in reverse order.

   202     /// If we would like to give back a real path from these

   203     /// algorithms then we should create a temporarly path object. In

   204     /// Lemon such algorithms gives back a path dumper what can

   205     /// assigned to a real path and the dumpers can be implemented as

   206     /// an adaptor class to the predecessor map.

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

   209     ///

   210     /// The paths can be constructed from any path type by a

   211     /// template constructor or a template assignment operator.

   212     ///

   213     template <typename _Graph>

   214     class PathDumper {

   215     public:

   217       /// Type of the underlying graph.

   218       typedef _Graph Graph;

   219       /// Edge type of the underlying graph.

   220       typedef typename Graph::Edge Edge;

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

   223       int length() const { return 0;}

   225       /// Returns whether the path is empty.

   226       bool empty() const { return true;}

   228       /// \brief Forward or reverse dumping

   229       ///

   230       /// If the RevPathTag is defined and true then reverse dumping

   231       /// is provided in the path dumper. In this case instead of the

   232       /// EdgeIt the RevEdgeIt iterator should be implemented in the

   233       /// dumper.

   234       typedef False RevPathTag;

   236       /// \brief Lemon style iterator for path edges

   237       ///

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

   239       class EdgeIt {

   240       public:

   241 	/// Default constructor

   242 	EdgeIt() {}

   243 	/// Invalid constructor

   244 	EdgeIt(Invalid) {}

   245 	/// Constructor for first edge

   246 	EdgeIt(const PathDumper&) {}

   248         /// Conversion to Edge

   249 	operator Edge() const { return INVALID; }

   251 	/// Next edge

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

   254 	/// Comparison operator

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

   256 	/// Comparison operator

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

   258  	/// Comparison operator

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

   261       };

   263       /// \brief Lemon style iterator for path edges

   264       ///

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

   266       /// reverse direction.

   267       class RevEdgeIt {

   268       public:

   269 	/// Default constructor

   270 	RevEdgeIt() {}

   271 	/// Invalid constructor

   272 	RevEdgeIt(Invalid) {}

   273 	/// Constructor for first edge

   274 	RevEdgeIt(const PathDumper &) {}

   276         /// Conversion to Edge

   277 	operator Edge() const { return INVALID; }

   279 	/// Next edge

   280 	RevEdgeIt& operator++() {return *this;}

   282 	/// Comparison operator

   283 	bool operator==(const RevEdgeIt&) const {return true;}

   284 	/// Comparison operator

   285 	bool operator!=(const RevEdgeIt&) const {return true;}

   286  	/// Comparison operator

   287  	bool operator<(const RevEdgeIt&) const {return false;}

   289       };

   291       template <typename _Path>

   292       struct Constraints {

   293         void constraints() {

   294           function_requires<_path_bits::

   295             PathDumperConstraints<Graph, _Path> >();

   296         }

   297       };

   299     };

   302     ///@}

   303   }

   305 } // namespace lemon

   307 #endif // LEMON_CONCEPT_PATH_H

author	kpeter
	Fri, 29 Feb 2008 15:55:13 +0000
changeset 2586	37fb2c384c78
parent 2468	16615642ac7b
permissions	-rw-r--r--