lemon/path.h
changeset 225 c5a40fc54f1a
parent 157 2ccc1afc2c52
child 220 a5d8c039f218
equal deleted inserted replaced
5:c6d8db14a63b 6:6c0e05012e12
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    91       /// \brief Default constructor
    91       /// \brief Default constructor
    92       ArcIt() {}
    92       ArcIt() {}
    93       /// \brief Invalid constructor
    93       /// \brief Invalid constructor
    94       ArcIt(Invalid) : path(0), idx(-1) {}
    94       ArcIt(Invalid) : path(0), idx(-1) {}
    95       /// \brief Initializate the iterator to the first arc of path
    95       /// \brief Initializate the iterator to the first arc of path
    96       ArcIt(const Path &_path) 
    96       ArcIt(const Path &_path)
    97         : path(&_path), idx(_path.empty() ? -1 : 0) {}
    97         : path(&_path), idx(_path.empty() ? -1 : 0) {}
    98 
    98 
    99     private:
    99     private:
   100 
   100 
   101       ArcIt(const Path &_path, int _idx) 
   101       ArcIt(const Path &_path, int _idx)
   102         : path(&_path), idx(_idx) {}
   102         : path(&_path), idx(_idx) {}
   103 
   103 
   104     public:
   104     public:
   105 
   105 
   106       /// \brief Conversion to Arc
   106       /// \brief Conversion to Arc
   107       operator const Arc&() const {
   107       operator const Arc&() const {
   108         return path->nth(idx);
   108         return path->nth(idx);
   109       }
   109       }
   110 
   110 
   111       /// \brief Next arc
   111       /// \brief Next arc
   112       ArcIt& operator++() { 
   112       ArcIt& operator++() {
   113         ++idx;
   113         ++idx;
   114         if (idx >= path->length()) idx = -1; 
   114         if (idx >= path->length()) idx = -1;
   115         return *this; 
   115         return *this;
   116       }
   116       }
   117 
   117 
   118       /// \brief Comparison operator
   118       /// \brief Comparison operator
   119       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   119       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   120       /// \brief Comparison operator
   120       /// \brief Comparison operator
   282       /// Default constructor
   282       /// Default constructor
   283       ArcIt() {}
   283       ArcIt() {}
   284       /// Invalid constructor
   284       /// Invalid constructor
   285       ArcIt(Invalid) : path(0), idx(-1) {}
   285       ArcIt(Invalid) : path(0), idx(-1) {}
   286       /// \brief Initializate the constructor to the first arc of path
   286       /// \brief Initializate the constructor to the first arc of path
   287       ArcIt(const SimplePath &_path) 
   287       ArcIt(const SimplePath &_path)
   288         : path(&_path), idx(_path.empty() ? -1 : 0) {}
   288         : path(&_path), idx(_path.empty() ? -1 : 0) {}
   289 
   289 
   290     private:
   290     private:
   291 
   291 
   292       /// Constructor with starting point
   292       /// Constructor with starting point
   293       ArcIt(const SimplePath &_path, int _idx) 
   293       ArcIt(const SimplePath &_path, int _idx)
   294         : idx(_idx), path(&_path) {}
   294         : idx(_idx), path(&_path) {}
   295 
   295 
   296     public:
   296     public:
   297 
   297 
   298       ///Conversion to Digraph::Arc
   298       ///Conversion to Digraph::Arc
   299       operator const Arc&() const {
   299       operator const Arc&() const {
   300         return path->nth(idx);
   300         return path->nth(idx);
   301       }
   301       }
   302 
   302 
   303       /// Next arc
   303       /// Next arc
   304       ArcIt& operator++() { 
   304       ArcIt& operator++() {
   305         ++idx;
   305         ++idx;
   306         if (idx >= path->length()) idx = -1; 
   306         if (idx >= path->length()) idx = -1;
   307         return *this; 
   307         return *this;
   308       }
   308       }
   309 
   309 
   310       /// Comparison operator
   310       /// Comparison operator
   311       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   311       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   312       /// Comparison operator
   312       /// Comparison operator
   411     typedef _Digraph Digraph;
   411     typedef _Digraph Digraph;
   412     typedef typename Digraph::Arc Arc;
   412     typedef typename Digraph::Arc Arc;
   413 
   413 
   414   protected:
   414   protected:
   415 
   415 
   416     // the std::list<> is incompatible 
   416     // the std::list<> is incompatible
   417     // hard to create invalid iterator
   417     // hard to create invalid iterator
   418     struct Node {
   418     struct Node {
   419       Arc arc;
   419       Arc arc;
   420       Node *next, *prev;
   420       Node *next, *prev;
   421     };
   421     };
   423     Node *first, *last;
   423     Node *first, *last;
   424 
   424 
   425     std::allocator<Node> alloc;
   425     std::allocator<Node> alloc;
   426 
   426 
   427   public:
   427   public:
   428  
   428 
   429     /// \brief Default constructor
   429     /// \brief Default constructor
   430     ///
   430     ///
   431     /// Default constructor
   431     /// Default constructor
   432     ListPath() : first(0), last(0) {}
   432     ListPath() : first(0), last(0) {}
   433 
   433 
   468       /// Default constructor
   468       /// Default constructor
   469       ArcIt() {}
   469       ArcIt() {}
   470       /// Invalid constructor
   470       /// Invalid constructor
   471       ArcIt(Invalid) : path(0), node(0) {}
   471       ArcIt(Invalid) : path(0), node(0) {}
   472       /// \brief Initializate the constructor to the first arc of path
   472       /// \brief Initializate the constructor to the first arc of path
   473       ArcIt(const ListPath &_path) 
   473       ArcIt(const ListPath &_path)
   474         : path(&_path), node(_path.first) {}
   474         : path(&_path), node(_path.first) {}
   475 
   475 
   476     protected:
   476     protected:
   477 
   477 
   478       ArcIt(const ListPath &_path, Node *_node) 
   478       ArcIt(const ListPath &_path, Node *_node)
   479         : path(&_path), node(_node) {}
   479         : path(&_path), node(_node) {}
   480 
   480 
   481 
   481 
   482     public:
   482     public:
   483 
   483 
   485       operator const Arc&() const {
   485       operator const Arc&() const {
   486         return node->arc;
   486         return node->arc;
   487       }
   487       }
   488 
   488 
   489       /// Next arc
   489       /// Next arc
   490       ArcIt& operator++() { 
   490       ArcIt& operator++() {
   491         node = node->next;
   491         node = node->next;
   492         return *this; 
   492         return *this;
   493       }
   493       }
   494 
   494 
   495       /// Comparison operator
   495       /// Comparison operator
   496       bool operator==(const ArcIt& e) const { return node==e.node; }
   496       bool operator==(const ArcIt& e) const { return node==e.node; }
   497       /// Comparison operator
   497       /// Comparison operator
   755 
   755 
   756     /// \brief Default constructor
   756     /// \brief Default constructor
   757     ///
   757     ///
   758     /// Default constructor
   758     /// Default constructor
   759     StaticPath() : len(0), arcs(0) {}
   759     StaticPath() : len(0), arcs(0) {}
   760     
   760 
   761     /// \brief Template copy constructor
   761     /// \brief Template copy constructor
   762     ///
   762     ///
   763     /// This path can be initialized from any other path type.
   763     /// This path can be initialized from any other path type.
   764     template <typename CPath>
   764     template <typename CPath>
   765     StaticPath(const CPath& cpath) : arcs(0) {
   765     StaticPath(const CPath& cpath) : arcs(0) {
   794       /// Default constructor
   794       /// Default constructor
   795       ArcIt() {}
   795       ArcIt() {}
   796       /// Invalid constructor
   796       /// Invalid constructor
   797       ArcIt(Invalid) : path(0), idx(-1) {}
   797       ArcIt(Invalid) : path(0), idx(-1) {}
   798       /// Initializate the constructor to the first arc of path
   798       /// Initializate the constructor to the first arc of path
   799       ArcIt(const StaticPath &_path) 
   799       ArcIt(const StaticPath &_path)
   800         : path(&_path), idx(_path.empty() ? -1 : 0) {}
   800         : path(&_path), idx(_path.empty() ? -1 : 0) {}
   801 
   801 
   802     private:
   802     private:
   803 
   803 
   804       /// Constructor with starting point
   804       /// Constructor with starting point
   805       ArcIt(const StaticPath &_path, int _idx) 
   805       ArcIt(const StaticPath &_path, int _idx)
   806         : idx(_idx), path(&_path) {}
   806         : idx(_idx), path(&_path) {}
   807 
   807 
   808     public:
   808     public:
   809 
   809 
   810       ///Conversion to Digraph::Arc
   810       ///Conversion to Digraph::Arc
   811       operator const Arc&() const {
   811       operator const Arc&() const {
   812         return path->nth(idx);
   812         return path->nth(idx);
   813       }
   813       }
   814 
   814 
   815       /// Next arc
   815       /// Next arc
   816       ArcIt& operator++() { 
   816       ArcIt& operator++() {
   817         ++idx;
   817         ++idx;
   818         if (idx >= path->length()) idx = -1; 
   818         if (idx >= path->length()) idx = -1;
   819         return *this; 
   819         return *this;
   820       }
   820       }
   821 
   821 
   822       /// Comparison operator
   822       /// Comparison operator
   823       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   823       bool operator==(const ArcIt& e) const { return idx==e.idx; }
   824       /// Comparison operator
   824       /// Comparison operator
   907       static const bool value = false;
   907       static const bool value = false;
   908     };
   908     };
   909 
   909 
   910     template <typename Path>
   910     template <typename Path>
   911     struct RevPathTagIndicator<
   911     struct RevPathTagIndicator<
   912       Path, 
   912       Path,
   913       typename enable_if<typename Path::RevPathTag, void>::type
   913       typename enable_if<typename Path::RevPathTag, void>::type
   914       > {
   914       > {
   915       static const bool value = true;
   915       static const bool value = true;
   916     };
   916     };
   917 
   917 
   920       static const bool value = false;
   920       static const bool value = false;
   921     };
   921     };
   922 
   922 
   923     template <typename Path>
   923     template <typename Path>
   924     struct BuildTagIndicator<
   924     struct BuildTagIndicator<
   925       Path, 
   925       Path,
   926       typename enable_if<typename Path::BuildTag, void>::type
   926       typename enable_if<typename Path::BuildTag, void>::type
   927     > {
   927     > {
   928       static const bool value = true;
   928       static const bool value = true;
   929     };
   929     };
   930 
   930 
   931     template <typename Target, typename Source,
   931     template <typename Target, typename Source,
   932 	      bool buildEnable = BuildTagIndicator<Target>::value, 
   932               bool buildEnable = BuildTagIndicator<Target>::value,
   933 	      bool revEnable = RevPathTagIndicator<Source>::value>
   933               bool revEnable = RevPathTagIndicator<Source>::value>
   934     struct PathCopySelector {
   934     struct PathCopySelector {
   935       static void copy(Target& target, const Source& source) {
   935       static void copy(Target& target, const Source& source) {
   936         target.clear();
   936         target.clear();
   937         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
   937         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
   938           target.addBack(it);
   938           target.addBack(it);
   979   }
   979   }
   980 
   980 
   981   /// \brief Check the consistency of a path.
   981   /// \brief Check the consistency of a path.
   982   ///
   982   ///
   983   /// This function checks that the target of each arc is the same
   983   /// This function checks that the target of each arc is the same
   984   /// as the source of the next one. 
   984   /// as the source of the next one.
   985   /// 
   985   ///
   986   template <typename Digraph, typename Path>
   986   template <typename Digraph, typename Path>
   987   bool checkPath(const Digraph& digraph, const Path& path) {
   987   bool checkPath(const Digraph& digraph, const Path& path) {
   988     typename Path::ArcIt it(path);
   988     typename Path::ArcIt it(path);
   989     if (it == INVALID) return true;
   989     if (it == INVALID) return true;
   990     typename Digraph::Node node = digraph.target(it);
   990     typename Digraph::Node node = digraph.target(it);
  1032 
  1032 
  1033   public:
  1033   public:
  1034 
  1034 
  1035     typedef typename Path::Digraph Digraph;
  1035     typedef typename Path::Digraph Digraph;
  1036     typedef typename Digraph::Node Node;
  1036     typedef typename Digraph::Node Node;
  1037     
  1037 
  1038     /// Default constructor
  1038     /// Default constructor
  1039     PathNodeIt() {}
  1039     PathNodeIt() {}
  1040     /// Invalid constructor
  1040     /// Invalid constructor
  1041     PathNodeIt(Invalid) 
  1041     PathNodeIt(Invalid)
  1042       : _digraph(0), _it(INVALID), _nd(INVALID) {}
  1042       : _digraph(0), _it(INVALID), _nd(INVALID) {}
  1043     /// Constructor
  1043     /// Constructor
  1044     PathNodeIt(const Digraph& digraph, const Path& path) 
  1044     PathNodeIt(const Digraph& digraph, const Path& path)
  1045       : _digraph(&digraph), _it(path) {
  1045       : _digraph(&digraph), _it(path) {
  1046       _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
  1046       _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
  1047     }
  1047     }
  1048     /// Constructor
  1048     /// Constructor
  1049     PathNodeIt(const Digraph& digraph, const Path& path, const Node& src) 
  1049     PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
  1050       : _digraph(&digraph), _it(path), _nd(src) {}
  1050       : _digraph(&digraph), _it(path), _nd(src) {}
  1051 
  1051 
  1052     ///Conversion to Digraph::Node
  1052     ///Conversion to Digraph::Node
  1053     operator Node() const {
  1053     operator Node() const {
  1054       return _nd;
  1054       return _nd;
  1056 
  1056 
  1057     /// Next node
  1057     /// Next node
  1058     PathNodeIt& operator++() {
  1058     PathNodeIt& operator++() {
  1059       if (_it == INVALID) _nd = INVALID;
  1059       if (_it == INVALID) _nd = INVALID;
  1060       else {
  1060       else {
  1061 	_nd = _digraph->target(_it);
  1061         _nd = _digraph->target(_it);
  1062 	++_it;
  1062         ++_it;
  1063       }
  1063       }
  1064       return *this;
  1064       return *this;
  1065     }
  1065     }
  1066 
  1066 
  1067     /// Comparison operator
  1067     /// Comparison operator
  1068     bool operator==(const PathNodeIt& n) const { 
  1068     bool operator==(const PathNodeIt& n) const {
  1069       return _it == n._it && _nd == n._nd; 
  1069       return _it == n._it && _nd == n._nd;
  1070     }
  1070     }
  1071     /// Comparison operator
  1071     /// Comparison operator
  1072     bool operator!=(const PathNodeIt& n) const { 
  1072     bool operator!=(const PathNodeIt& n) const {
  1073       return _it != n._it || _nd != n._nd; 
  1073       return _it != n._it || _nd != n._nd;
  1074     }
  1074     }
  1075     /// Comparison operator
  1075     /// Comparison operator
  1076     bool operator<(const PathNodeIt& n) const { 
  1076     bool operator<(const PathNodeIt& n) const {
  1077       return (_it < n._it && _nd != INVALID);
  1077       return (_it < n._it && _nd != INVALID);
  1078     }
  1078     }
  1079     
  1079 
  1080   };
  1080   };
  1081   
  1081 
  1082   ///@}
  1082   ///@}
  1083 
  1083 
  1084 } // namespace lemon
  1084 } // namespace lemon
  1085 
  1085 
  1086 #endif // LEMON_PATH_H
  1086 #endif // LEMON_PATH_H