# Changeset 590:b61354458b59 in lemon-1.2

Ignore:
Timestamp:
04/15/09 12:01:14 (12 years ago)
Branch:
default
Phase:
public
Message:

Imporvements for the matching algorithms (#264)

Files:
3 edited

### Legend:

Unmodified
 r581 /// \ingroup matching /// /// \brief Edmonds' alternating forest maximum matching algorithm. /// \brief Maximum cardinality matching in general graphs /// /// This class implements Edmonds' alternating forest matching /// algorithm. The algorithm can be started from an arbitrary initial /// matching (the default is the empty one) /// This class implements Edmonds' alternating forest matching algorithm /// for finding a maximum cardinality matching in a general graph. /// It can be started from an arbitrary initial matching /// (the default is the empty one). /// /// The dual solution of the problem is a map of the nodes to /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c /// MATCHED/C showing the Gallai-Edmonds decomposition of the /// graph. The nodes in \c EVEN/D induce a graph with /// factor-critical components, the nodes in \c ODD/A form the /// barrier, and the nodes in \c MATCHED/C induce a graph having a /// perfect matching. The number of the factor-critical components /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph /// with factor-critical components, the nodes in \c ODD/A form the /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having /// a perfect matching. The number of the factor-critical components /// minus the number of barrier nodes is a lower bound on the /// unmatched nodes, and the matching is optimal if and only if this bound is /// tight. This decomposition can be attained by calling \c /// tight. This decomposition can be obtained by calling \c /// decomposition() after running the algorithm. /// /// \param GR The graph type the algorithm runs on. /// \tparam GR The graph type the algorithm runs on. template class MaxMatching { public: /// The graph type of the algorithm typedef GR Graph; typedef typename Graph::template NodeMap MatchingMap; ///\brief Indicates the Gallai-Edmonds decomposition of the graph. /// ///Indicates the Gallai-Edmonds decomposition of the graph. The ///nodes with Status \c EVEN/D induce a graph with factor-critical ///components, the nodes in \c ODD/A form the canonical barrier, ///and the nodes in \c MATCHED/C induce a graph having a perfect ///matching. ///\brief Status constants for Gallai-Edmonds decomposition. /// ///These constants are used for indicating the Gallai-Edmonds ///decomposition of a graph. The nodes with status \c EVEN (or \c D) ///induce a subgraph with factor-critical components, the nodes with ///status \c ODD (or \c A) form the canonical barrier, and the nodes ///with status \c MATCHED (or \c C) induce a subgraph having a ///perfect matching. enum Status { EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2 EVEN = 1,       ///< = 1. (\c D is an alias for \c EVEN.) D = 1, MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.) C = 0, ODD = -1,       ///< = -1. (\c A is an alias for \c ODD.) A = -1, UNMATCHED = -2  ///< = -2. }; } void extendOnArc(const Arc& a) { Node base = _graph.source(a); } /// \name Execution control /// \name Execution Control /// The simplest way to execute the algorithm is to use the /// \c run() member function. /// \n /// If you need better control on the execution, you must call /// \ref init(), \ref greedyInit() or \ref matchingInit() /// functions first, then you can start the algorithm with the \ref /// startSparse() or startDense() functions. /// \c run() member function.\n /// If you need better control on the execution, you have to call /// one of the functions \ref init(), \ref greedyInit() or /// \ref matchingInit() first, then you can start the algorithm with /// \ref startSparse() or \ref startDense(). ///@{ /// \brief Sets the actual matching to the empty matching. /// /// Sets the actual matching to the empty matching. /// /// \brief Set the initial matching to the empty matching. /// /// This function sets the initial matching to the empty matching. void init() { createStructures(); } ///\brief Finds an initial matching in a greedy way /// ///It finds an initial matching in a greedy way. /// \brief Find an initial matching in a greedy way. /// /// This function finds an initial matching in a greedy way. void greedyInit() { createStructures(); /// \brief Initialize the matching from a map containing. /// /// Initialize the matching from a \c bool valued \c Edge map. This /// map must have the property that there are no two incident edges /// with true value, ie. it contains a matching. /// \brief Initialize the matching from a map. /// /// This function initializes the matching from a \c bool valued edge /// map. This map should have the property that there are no two incident /// edges with \c true value, i.e. it really contains a matching. /// \return \c true if the map contains a matching. template } /// \brief Starts Edmonds' algorithm /// /// If runs the original Edmonds' algorithm. /// \brief Start Edmonds' algorithm /// /// This function runs the original Edmonds' algorithm. /// /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be /// called before using this function. void startSparse() { for(NodeIt n(_graph); n != INVALID; ++n) { } /// \brief Starts Edmonds' algorithm. /// /// It runs Edmonds' algorithm with a heuristic of postponing /// \brief Start Edmonds' algorithm with a heuristic improvement /// for dense graphs /// /// This function runs Edmonds' algorithm with a heuristic of postponing /// shrinks, therefore resulting in a faster algorithm for dense graphs. /// /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be /// called before using this function. void startDense() { for(NodeIt n(_graph); n != INVALID; ++n) { /// \brief Runs Edmonds' algorithm /// /// Runs Edmonds' algorithm for sparse graphs (m<2*n) /// or Edmonds' algorithm with a heuristic of /// postponing shrinks for dense graphs. /// \brief Run Edmonds' algorithm /// /// This function runs Edmonds' algorithm. An additional heuristic of /// postponing shrinks is used for relatively dense graphs /// (for which m>=2*n holds). void run() { if (countEdges(_graph) < 2 * countNodes(_graph)) { /// @} /// \name Primal solution /// Functions to get the primal solution, ie. the matching. /// \name Primal Solution /// Functions to get the primal solution, i.e. the maximum matching. /// @{ ///\brief Returns the size of the current matching. /// ///Returns the size of the current matching. After \ref ///run() it returns the size of the maximum matching in the graph. /// \brief Return the size (cardinality) of the matching. /// /// This function returns the size (cardinality) of the current matching. /// After run() it returns the size of the maximum matching in the graph. int matchingSize() const { int size = 0; } /// \brief Returns true when the edge is in the matching. /// /// Returns true when the edge is in the matching. /// \brief Return \c true if the given edge is in the matching. /// /// This function returns \c true if the given edge is in the current /// matching. bool matching(const Edge& edge) const { return edge == (*_matching)[_graph.u(edge)]; } /// \brief Returns the matching edge incident to the given node. /// /// Returns the matching edge of a \c node in the actual matching or /// INVALID if the \c node is not covered by the actual matching. /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the /// given node in the current matching or \c INVALID if the node is /// not covered by the matching. Arc matching(const Node& n) const { return (*_matching)[n]; } ///\brief Returns the mate of a node in the actual matching. /// ///Returns the mate of a \c node in the actual matching or ///INVALID if the \c node is not covered by the actual matching. /// \brief Return the mate of the given node. /// /// This function returns the mate of the given node in the current /// matching or \c INVALID if the node is not covered by the matching. Node mate(const Node& n) const { return (*_matching)[n] != INVALID ? /// @} /// \name Dual solution /// Functions to get the dual solution, ie. the decomposition. /// \name Dual Solution /// Functions to get the dual solution, i.e. the Gallai-Edmonds /// decomposition. /// @{ /// \brief Returns the class of the node in the Edmonds-Gallai /// \brief Return the status of the given node in the Edmonds-Gallai /// decomposition. /// /// Returns the class of the node in the Edmonds-Gallai /// decomposition. /// This function returns the \ref Status "status" of the given node /// in the Edmonds-Gallai decomposition. Status decomposition(const Node& n) const { return (*_status)[n]; } /// \brief Returns true when the node is in the barrier. /// /// Returns true when the node is in the barrier. /// \brief Return \c true if the given node is in the barrier. /// /// This function returns \c true if the given node is in the barrier. bool barrier(const Node& n) const { return (*_status)[n] == ODD; /// \f$O(nm\log n)\f$ time complexity. /// /// The maximum weighted matching problem is to find undirected /// edges in the graph with maximum overall weight and no two of /// them shares their ends. The problem can be formulated with the /// following linear program. /// The maximum weighted matching problem is to find a subset of the /// edges in an undirected graph with maximum overall weight for which /// each node has at most one incident edge. /// It can be formulated with the following linear program. /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f] /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} /// optimality. The solution of the dual problem can be used to check /// the result of the algorithm. The dual linear problem is the /// following. /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)} z_B \ge w_{uv} \quad \forall uv\in E\f] */ \frac{\vert B \vert - 1}{2}z_B\f] */ /// /// The algorithm can be executed with \c run() or the \c init() and /// then the \c start() member functions. After it the matching can /// be asked with \c matching() or mate() functions. The dual /// solution can be get with \c nodeValue(), \c blossomNum() and \c /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt /// "BlossomIt" nested class, which is able to iterate on the nodes /// of a blossom. If the value type is integral then the dual /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". /// The algorithm can be executed with the run() function. /// After it the matching (the primal solution) and the dual solution /// can be obtained using the query functions and the /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, /// which is able to iterate on the nodes of a blossom. /// If the value type is integer, then the dual solution is multiplied /// by \ref MaxWeightedMatching::dualScale "4". /// /// \tparam GR The graph type the algorithm runs on. /// \tparam WM The type edge weight map. The default type is /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template #else template > #endif class MaxWeightedMatching { public: ///\e /// The graph type of the algorithm typedef GR Graph; ///\e /// The type of the edge weight map typedef WM WeightMap; ///\e /// The value type of the edge weights typedef typename WeightMap::Value Value; typedef typename Graph::template NodeMap MatchingMap; /// \brief Scaling factor for dual solution /// /// Scaling factor for dual solution, it is equal to 4 or 1 /// Scaling factor for dual solution. It is equal to 4 or 1 /// according to the value type. static const int dualScale = std::numeric_limits::is_integer ? 4 : 1; typedef typename Graph::template NodeMap MatchingMap; private: } /// \name Execution control /// \name Execution Control /// The simplest way to execute the algorithm is to use the /// \c run() member function. /// \ref run() member function. ///@{ /// \brief Initialize the algorithm /// /// Initialize the algorithm /// This function initializes the algorithm. void init() { createStructures(); } /// \brief Starts the algorithm /// /// Starts the algorithm /// \brief Start the algorithm /// /// This function starts the algorithm. /// /// \pre \ref init() must be called before using this function. void start() { enum OpType { } /// \brief Runs %MaxWeightedMatching algorithm. /// /// This method runs the %MaxWeightedMatching algorithm. /// \brief Run the algorithm. /// /// This method runs the \c %MaxWeightedMatching algorithm. /// /// \note mwm.run() is just a shortcut of the following code. /// @} /// \name Primal solution /// Functions to get the primal solution, ie. the matching. /// \name Primal Solution /// Functions to get the primal solution, i.e. the maximum weighted /// matching.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the weight of the matching. /// /// Returns the weight of the matching. /// \brief Return the weight of the matching. /// /// This function returns the weight of the found matching. /// /// \pre Either run() or start() must be called before using this function. Value matchingValue() const { Value sum = 0; } /// \brief Returns the cardinality of the matching. /// /// Returns the cardinality of the matching. /// \brief Return the size (cardinality) of the matching. /// /// This function returns the size (cardinality) of the found matching. /// /// \pre Either run() or start() must be called before using this function. int matchingSize() const { int num = 0; } /// \brief Returns true when the edge is in the matching. /// /// Returns true when the edge is in the matching. /// \brief Return \c true if the given edge is in the matching. /// /// This function returns \c true if the given edge is in the found /// matching. /// /// \pre Either run() or start() must be called before using this function. bool matching(const Edge& edge) const { return edge == (*_matching)[_graph.u(edge)]; } /// \brief Returns the incident matching arc. /// /// Returns the incident matching arc from given node. If the /// node is not matched then it gives back \c INVALID. /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the /// given node in the found matching or \c INVALID if the node is /// not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Arc matching(const Node& node) const { return (*_matching)[node]; } /// \brief Returns the mate of the node. /// /// Returns the adjancent node in a mathcing arc. If the node is /// not matched then it gives back \c INVALID. /// \brief Return the mate of the given node. /// /// This function returns the mate of the given node in the found /// matching or \c INVALID if the node is not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Node mate(const Node& node) const { return (*_matching)[node] != INVALID ? /// @} /// \name Dual solution /// Functions to get the dual solution. /// \name Dual Solution /// Functions to get the dual solution.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the value of the dual solution. /// /// Returns the value of the dual solution. It should be equal to /// the primal value scaled by \ref dualScale "dual scale". /// \brief Return the value of the dual solution. /// /// This function returns the value of the dual solution. /// It should be equal to the primal value scaled by \ref dualScale /// "dual scale". /// /// \pre Either run() or start() must be called before using this function. Value dualValue() const { Value sum = 0; } /// \brief Returns the value of the node. /// /// Returns the the value of the node. /// \brief Return the dual value (potential) of the given node. /// /// This function returns the dual value (potential) of the given node. /// /// \pre Either run() or start() must be called before using this function. Value nodeValue(const Node& n) const { return (*_node_potential)[n]; } /// \brief Returns the number of the blossoms in the basis. /// /// Returns the number of the blossoms in the basis. /// \brief Return the number of the blossoms in the basis. /// /// This function returns the number of the blossoms in the basis. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomNum() const { } /// \brief Returns the number of the nodes in the blossom. /// /// Returns the number of the nodes in the blossom. /// \brief Return the number of the nodes in the given blossom. /// /// This function returns the number of the nodes in the given blossom. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomSize(int k) const { return _blossom_potential[k].end - _blossom_potential[k].begin; } /// \brief Returns the value of the blossom. /// /// Returns the the value of the blossom. /// \see BlossomIt /// \brief Return the dual value (ptential) of the given blossom. /// /// This function returns the dual value (ptential) of the given blossom. /// /// \pre Either run() or start() must be called before using this function. Value blossomValue(int k) const { return _blossom_potential[k].value; } /// \brief Iterator for obtaining the nodes of the blossom. /// /// Iterator for obtaining the nodes of the blossom. This class /// provides a common lemon style iterator for listing a /// subset of the nodes. /// \brief Iterator for obtaining the nodes of a blossom. /// /// This class provides an iterator for obtaining the nodes of the /// given blossom. It lists a subset of the nodes. /// Before using this iterator, you must allocate a /// MaxWeightedMatching class and execute it. class BlossomIt { public: /// \brief Constructor. /// /// Constructor to get the nodes of the variable. /// Constructor to get the nodes of the given variable. /// /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or /// \ref MaxWeightedMatching::start() "algorithm.start()" must be /// called before initializing this iterator. BlossomIt(const MaxWeightedMatching& algorithm, int variable) : _algorithm(&algorithm) } /// \brief Conversion to node. /// \brief Conversion to \c Node. /// /// Conversion to node. /// Conversion to \c Node. operator Node() const { return _algorithm->_blossom_node_list[_index]; /// \f$O(nm\log n)\f$ time complexity. /// /// The maximum weighted matching problem is to find undirected /// edges in the graph with maximum overall weight and no two of /// them shares their ends and covers all nodes. The problem can be /// formulated with the following linear program. /// The maximum weighted perfect matching problem is to find a subset of /// the edges in an undirected graph with maximum overall weight for which /// each node has exactly one incident edge. /// It can be formulated with the following linear program. /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f] /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} /// optimality. The solution of the dual problem can be used to check /// the result of the algorithm. The dual linear problem is the /// following. /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge w_{uv} \quad \forall uv\in E\f] */ \frac{\vert B \vert - 1}{2}z_B\f] */ /// /// The algorithm can be executed with \c run() or the \c init() and /// then the \c start() member functions. After it the matching can /// be asked with \c matching() or mate() functions. The dual /// solution can be get with \c nodeValue(), \c blossomNum() and \c /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt /// "BlossomIt" nested class which is able to iterate on the nodes /// of a blossom. If the value type is integral then the dual /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". /// The algorithm can be executed with the run() function. /// After it the matching (the primal solution) and the dual solution /// can be obtained using the query functions and the /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, /// which is able to iterate on the nodes of a blossom. /// If the value type is integer, then the dual solution is multiplied /// by \ref MaxWeightedMatching::dualScale "4". /// /// \tparam GR The graph type the algorithm runs on. /// \tparam WM The type edge weight map. The default type is /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template #else template > #endif class MaxWeightedPerfectMatching { public: /// The graph type of the algorithm typedef GR Graph; /// The type of the edge weight map typedef WM WeightMap; /// The value type of the edge weights typedef typename WeightMap::Value Value; } /// \name Execution control /// \name Execution Control /// The simplest way to execute the algorithm is to use the /// \c run() member function. /// \ref run() member function. ///@{ /// \brief Initialize the algorithm /// /// Initialize the algorithm /// This function initializes the algorithm. void init() { createStructures(); } /// \brief Starts the algorithm /// /// Starts the algorithm /// \brief Start the algorithm /// /// This function starts the algorithm. /// /// \pre \ref init() must be called before using this function. bool start() { enum OpType { } /// \brief Runs %MaxWeightedPerfectMatching algorithm. /// /// This method runs the %MaxWeightedPerfectMatching algorithm. /// /// \note mwm.run() is just a shortcut of the following code. /// \brief Run the algorithm. /// /// This method runs the \c %MaxWeightedPerfectMatching algorithm. /// /// \note mwpm.run() is just a shortcut of the following code. /// \code ///   mwm.init(); ///   mwm.start(); ///   mwpm.init(); ///   mwpm.start(); /// \endcode bool run() { /// @} /// \name Primal solution /// Functions to get the primal solution, ie. the matching. /// \name Primal Solution /// Functions to get the primal solution, i.e. the maximum weighted /// perfect matching.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the matching value. /// /// Returns the matching value. /// \brief Return the weight of the matching. /// /// This function returns the weight of the found matching. /// /// \pre Either run() or start() must be called before using this function. Value matchingValue() const { Value sum = 0; } /// \brief Returns true when the edge is in the matching. /// /// Returns true when the edge is in the matching. /// \brief Return \c true if the given edge is in the matching. /// /// This function returns \c true if the given edge is in the found /// matching. /// /// \pre Either run() or start() must be called before using this function. bool matching(const Edge& edge) const { return static_cast((*_matching)[_graph.u(edge)]) == edge; } /// \brief Returns the incident matching edge. /// /// Returns the incident matching arc from given edge. /// \brief Return the matching arc (or edge) incident to the given node. /// /// This function returns the matching arc (or edge) incident to the /// given node in the found matching or \c INVALID if the node is /// not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Arc matching(const Node& node) const { return (*_matching)[node]; } /// \brief Returns the mate of the node. /// /// Returns the adjancent node in a mathcing arc. /// \brief Return the mate of the given node. /// /// This function returns the mate of the given node in the found /// matching or \c INVALID if the node is not covered by the matching. /// /// \pre Either run() or start() must be called before using this function. Node mate(const Node& node) const { return _graph.target((*_matching)[node]); /// @} /// \name Dual solution /// Functions to get the dual solution. /// \name Dual Solution /// Functions to get the dual solution.\n /// Either \ref run() or \ref start() function should be called before /// using them. /// @{ /// \brief Returns the value of the dual solution. /// /// Returns the value of the dual solution. It should be equal to /// the primal value scaled by \ref dualScale "dual scale". /// \brief Return the value of the dual solution. /// /// This function returns the value of the dual solution. /// It should be equal to the primal value scaled by \ref dualScale /// "dual scale". /// /// \pre Either run() or start() must be called before using this function. Value dualValue() const { Value sum = 0; } /// \brief Returns the value of the node. /// /// Returns the the value of the node. /// \brief Return the dual value (potential) of the given node. /// /// This function returns the dual value (potential) of the given node. /// /// \pre Either run() or start() must be called before using this function. Value nodeValue(const Node& n) const { return (*_node_potential)[n]; } /// \brief Returns the number of the blossoms in the basis. /// /// Returns the number of the blossoms in the basis. /// \brief Return the number of the blossoms in the basis. /// /// This function returns the number of the blossoms in the basis. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomNum() const { } /// \brief Returns the number of the nodes in the blossom. /// /// Returns the number of the nodes in the blossom. /// \brief Return the number of the nodes in the given blossom. /// /// This function returns the number of the nodes in the given blossom. /// /// \pre Either run() or start() must be called before using this function. /// \see BlossomIt int blossomSize(int k) const { return _blossom_potential[k].end - _blossom_potential[k].begin; } /// \brief Returns the value of the blossom. /// /// Returns the the value of the blossom. /// \see BlossomIt /// \brief Return the dual value (ptential) of the given blossom. /// /// This function returns the dual value (ptential) of the given blossom. /// /// \pre Either run() or start() must be called before using this function. Value blossomValue(int k) const { return _blossom_potential[k].value; } /// \brief Iterator for obtaining the nodes of the blossom. /// /// Iterator for obtaining the nodes of the blossom. This class /// provides a common lemon style iterator for listing a /// subset of the nodes. /// \brief Iterator for obtaining the nodes of a blossom. /// /// This class provides an iterator for obtaining the nodes of the /// given blossom. It lists a subset of the nodes. /// Before using this iterator, you must allocate a /// MaxWeightedPerfectMatching class and execute it. class BlossomIt { public: /// \brief Constructor. /// /// Constructor to get the nodes of the variable. /// Constructor to get the nodes of the given variable. /// /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" /// must be called before initializing this iterator. BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) : _algorithm(&algorithm) } /// \brief Conversion to node. /// \brief Conversion to \c Node. /// /// Conversion to node. /// Conversion to \c Node. operator Node() const { return _algorithm->_blossom_node_list[_index]; /// \brief Validity checking /// /// Checks whether the iterator is invalid. /// This function checks whether the iterator is invalid. bool operator==(Invalid) const { return _index == _last; } /// \brief Validity checking /// /// Checks whether the iterator is valid. /// This function checks whether the iterator is valid. bool operator!=(Invalid) const { return _index != _last; } }; } //END OF NAMESPACE LEMON