lemon-1.1: lemon/concepts/path.h@660db48f324f

     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     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 digraphs.

    22 ///

    24 #ifndef LEMON_CONCEPT_PATH_H

    25 #define LEMON_CONCEPT_PATH_H

    27 #include <lemon/core.h>

    28 #include <lemon/concept_check.h>

    30 namespace lemon {

    31   namespace concepts {

    33     /// \addtogroup concept

    34     /// @{

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

    37     /// a digraph.

    38     ///

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

    40     /// digraph.

    41     /// \tparam _Digraph The digraph type in which the path is.

    42     ///

    43     /// In a sense, the path can be treated as a list of arcs. The

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

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

    46     /// paths cannot store the source.

    47     ///

    48     template <typename _Digraph>

    49     class Path {

    50     public:

    52       /// Type of the underlying digraph.

    53       typedef _Digraph Digraph;

    54       /// Arc type of the underlying digraph.

    55       typedef typename Digraph::Arc Arc;

    57       class ArcIt;

    59       /// \brief Default constructor

    60       Path() {}

    62       /// \brief Template constructor

    63       template <typename CPath>

    64       Path(const CPath& cpath) {}

    66       /// \brief Template assigment

    67       template <typename CPath>

    68       Path& operator=(const CPath& cpath) {

    69         ignore_unused_variable_warning(cpath);

    70         return *this;

    71       }

    73       /// Length of the path ie. the number of arcs in the path.

    74       int length() const { return 0;}

    76       /// Returns whether the path is empty.

    77       bool empty() const { return true;}

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

    80       void clear() {}

    82       /// \brief LEMON style iterator for path arcs

    83       ///

    84       /// This class is used to iterate on the arcs of the paths.

    85       class ArcIt {

    86       public:

    87         /// Default constructor

    88         ArcIt() {}

    89         /// Invalid constructor

    90         ArcIt(Invalid) {}

    91         /// Constructor for first arc

    92         ArcIt(const Path &) {}

    94         /// Conversion to Arc

    95         operator Arc() const { return INVALID; }

    97         /// Next arc

    98         ArcIt& operator++() {return *this;}

   100         /// Comparison operator

   101         bool operator==(const ArcIt&) const {return true;}

   102         /// Comparison operator

   103         bool operator!=(const ArcIt&) const {return true;}

   104         /// Comparison operator

   105         bool operator<(const ArcIt&) const {return false;}

   107       };

   109       template <typename _Path>

   110       struct Constraints {

   111         void constraints() {

   112           Path<Digraph> pc;

   113           _Path p, pp(pc);

   114           int l = p.length();

   115           int e = p.empty();

   116           p.clear();

   118           p = pc;

   120           typename _Path::ArcIt id, ii(INVALID), i(p);

   122           ++i;

   123           typename Digraph::Arc ed = i;

   125           e = (i == ii);

   126           e = (i != ii);

   127           e = (i < ii);

   129           ignore_unused_variable_warning(l);

   130           ignore_unused_variable_warning(pp);

   131           ignore_unused_variable_warning(e);

   132           ignore_unused_variable_warning(id);

   133           ignore_unused_variable_warning(ii);

   134           ignore_unused_variable_warning(ed);

   135         }

   136       };

   138     };

   140     namespace _path_bits {

   142       template <typename _Digraph, typename _Path, typename RevPathTag = void>

   143       struct PathDumperConstraints {

   144         void constraints() {

   145           int l = p.length();

   146           int e = p.empty();

   148           typename _Path::ArcIt id, i(p);

   150           ++i;

   151           typename _Digraph::Arc ed = i;

   153           e = (i == INVALID);

   154           e = (i != INVALID);

   156           ignore_unused_variable_warning(l);

   157           ignore_unused_variable_warning(e);

   158           ignore_unused_variable_warning(id);

   159           ignore_unused_variable_warning(ed);

   160         }

   161         _Path& p;

   162       };

   164       template <typename _Digraph, typename _Path>

   165       struct PathDumperConstraints<

   166         _Digraph, _Path,

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

   168       > {

   169         void constraints() {

   170           int l = p.length();

   171           int e = p.empty();

   173           typename _Path::RevArcIt id, i(p);

   175           ++i;

   176           typename _Digraph::Arc ed = i;

   178           e = (i == INVALID);

   179           e = (i != INVALID);

   181           ignore_unused_variable_warning(l);

   182           ignore_unused_variable_warning(e);

   183           ignore_unused_variable_warning(id);

   184           ignore_unused_variable_warning(ed);

   185         }

   186         _Path& p;

   187       };

   189     }

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

   193     ///

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

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

   196     /// enumerate the arcs of the path wheter in forward or in

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

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

   199     /// path type.

   200     ///

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

   202     /// algorithms can enumerate easily the arcs in reverse order.

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

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

   205     /// LEMON such algorithms gives back a path dumper what can

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

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

   209     /// \tparam _Digraph  The digraph type in which the path is.

   210     ///

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

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

   213     ///

   214     template <typename _Digraph>

   215     class PathDumper {

   216     public:

   218       /// Type of the underlying digraph.

   219       typedef _Digraph Digraph;

   220       /// Arc type of the underlying digraph.

   221       typedef typename Digraph::Arc Arc;

   223       /// Length of the path ie. the number of arcs in the path.

   224       int length() const { return 0;}

   226       /// Returns whether the path is empty.

   227       bool empty() const { return true;}

   229       /// \brief Forward or reverse dumping

   230       ///

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

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

   233       /// ArcIt the RevArcIt iterator should be implemented in the

   234       /// dumper.

   235       typedef False RevPathTag;

   237       /// \brief LEMON style iterator for path arcs

   238       ///

   239       /// This class is used to iterate on the arcs of the paths.

   240       class ArcIt {

   241       public:

   242         /// Default constructor

   243         ArcIt() {}

   244         /// Invalid constructor

   245         ArcIt(Invalid) {}

   246         /// Constructor for first arc

   247         ArcIt(const PathDumper&) {}

   249         /// Conversion to Arc

   250         operator Arc() const { return INVALID; }

   252         /// Next arc

   253         ArcIt& operator++() {return *this;}

   255         /// Comparison operator

   256         bool operator==(const ArcIt&) const {return true;}

   257         /// Comparison operator

   258         bool operator!=(const ArcIt&) const {return true;}

   259         /// Comparison operator

   260         bool operator<(const ArcIt&) const {return false;}

   262       };

   264       /// \brief LEMON style iterator for path arcs

   265       ///

   266       /// This class is used to iterate on the arcs of the paths in

   267       /// reverse direction.

   268       class RevArcIt {

   269       public:

   270         /// Default constructor

   271         RevArcIt() {}

   272         /// Invalid constructor

   273         RevArcIt(Invalid) {}

   274         /// Constructor for first arc

   275         RevArcIt(const PathDumper &) {}

   277         /// Conversion to Arc

   278         operator Arc() const { return INVALID; }

   280         /// Next arc

   281         RevArcIt& operator++() {return *this;}

   283         /// Comparison operator

   284         bool operator==(const RevArcIt&) const {return true;}

   285         /// Comparison operator

   286         bool operator!=(const RevArcIt&) const {return true;}

   287         /// Comparison operator

   288         bool operator<(const RevArcIt&) const {return false;}

   290       };

   292       template <typename _Path>

   293       struct Constraints {

   294         void constraints() {

   295           function_requires<_path_bits::

   296             PathDumperConstraints<Digraph, _Path> >();

   297         }

   298       };

   300     };

   303     ///@}

   304   }

   306 } // namespace lemon

   308 #endif // LEMON_CONCEPT_PATH_H

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 21 Nov 2008 14:11:29 +0000
changeset 389	660db48f324f
parent 280	e7f8647ce760
parent 278	931190050520
child 440	88ed40ad0d4f
permissions	-rw-r--r--