lemon/concepts/bpgraph.h
changeset 1194 699c7eac2c6d
parent 1193 c8fa41fcc4a7
child 1195 8b2b9e61d8ce
equal deleted inserted replaced
1:fc65f86d7076 2:35b8a059faf7
    46     /// \ref SmartBpGraph may have additional functionality.
    46     /// \ref SmartBpGraph may have additional functionality.
    47     ///
    47     ///
    48     /// The bipartite graphs also fulfill the concept of \ref Graph
    48     /// The bipartite graphs also fulfill the concept of \ref Graph
    49     /// "undirected graphs". Bipartite graphs provide a bipartition of
    49     /// "undirected graphs". Bipartite graphs provide a bipartition of
    50     /// the node set, namely a red and blue set of the nodes. The
    50     /// the node set, namely a red and blue set of the nodes. The
    51     /// nodes can be iterated with the RedIt and BlueIt in the two
    51     /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the
    52     /// node sets. With RedMap and BlueMap values can be assigned to
    52     /// two node sets. With RedNodeMap and BlueNodeMap values can be
    53     /// the nodes in the two sets.
    53     /// assigned to the nodes in the two sets.
    54     ///
    54     ///
    55     /// The edges of the graph cannot connect two nodes of the same
    55     /// The edges of the graph cannot connect two nodes of the same
    56     /// set. The edges inherent orientation is from the red nodes to
    56     /// set. The edges inherent orientation is from the red nodes to
    57     /// the blue nodes.
    57     /// the blue nodes.
    58     ///
    58     ///
   185       /// of red nodes in a graph \c g of type \c %BpGraph like this:
   185       /// of red nodes in a graph \c g of type \c %BpGraph like this:
   186       ///\code
   186       ///\code
   187       /// int count=0;
   187       /// int count=0;
   188       /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
   188       /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
   189       ///\endcode
   189       ///\endcode
   190       class RedIt : public RedNode {
   190       class RedNodeIt : public RedNode {
   191       public:
   191       public:
   192         /// Default constructor
   192         /// Default constructor
   193 
   193 
   194         /// Default constructor.
   194         /// Default constructor.
   195         /// \warning It sets the iterator to an undefined value.
   195         /// \warning It sets the iterator to an undefined value.
   196         RedIt() { }
   196         RedNodeIt() { }
   197         /// Copy constructor.
   197         /// Copy constructor.
   198 
   198 
   199         /// Copy constructor.
   199         /// Copy constructor.
   200         ///
   200         ///
   201         RedIt(const RedIt& n) : RedNode(n) { }
   201         RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
   202         /// %Invalid constructor \& conversion.
   202         /// %Invalid constructor \& conversion.
   203 
   203 
   204         /// Initializes the iterator to be invalid.
   204         /// Initializes the iterator to be invalid.
   205         /// \sa Invalid for more details.
   205         /// \sa Invalid for more details.
   206         RedIt(Invalid) { }
   206         RedNodeIt(Invalid) { }
   207         /// Sets the iterator to the first red node.
   207         /// Sets the iterator to the first red node.
   208 
   208 
   209         /// Sets the iterator to the first red node of the given
   209         /// Sets the iterator to the first red node of the given
   210         /// digraph.
   210         /// digraph.
   211         explicit RedIt(const BpGraph&) { }
   211         explicit RedNodeIt(const BpGraph&) { }
   212         /// Sets the iterator to the given red node.
   212         /// Sets the iterator to the given red node.
   213 
   213 
   214         /// Sets the iterator to the given red node of the given
   214         /// Sets the iterator to the given red node of the given
   215         /// digraph.
   215         /// digraph.
   216         RedIt(const BpGraph&, const RedNode&) { }
   216         RedNodeIt(const BpGraph&, const RedNode&) { }
   217         /// Next node.
   217         /// Next node.
   218 
   218 
   219         /// Assign the iterator to the next red node.
   219         /// Assign the iterator to the next red node.
   220         ///
   220         ///
   221         RedIt& operator++() { return *this; }
   221         RedNodeIt& operator++() { return *this; }
   222       };
   222       };
   223 
   223 
   224       /// Iterator class for the blue nodes.
   224       /// Iterator class for the blue nodes.
   225 
   225 
   226       /// This iterator goes through each blue node of the graph.
   226       /// This iterator goes through each blue node of the graph.
   228       /// of blue nodes in a graph \c g of type \c %BpGraph like this:
   228       /// of blue nodes in a graph \c g of type \c %BpGraph like this:
   229       ///\code
   229       ///\code
   230       /// int count=0;
   230       /// int count=0;
   231       /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
   231       /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
   232       ///\endcode
   232       ///\endcode
   233       class BlueIt : public BlueNode {
   233       class BlueNodeIt : public BlueNode {
   234       public:
   234       public:
   235         /// Default constructor
   235         /// Default constructor
   236 
   236 
   237         /// Default constructor.
   237         /// Default constructor.
   238         /// \warning It sets the iterator to an undefined value.
   238         /// \warning It sets the iterator to an undefined value.
   239         BlueIt() { }
   239         BlueNodeIt() { }
   240         /// Copy constructor.
   240         /// Copy constructor.
   241 
   241 
   242         /// Copy constructor.
   242         /// Copy constructor.
   243         ///
   243         ///
   244         BlueIt(const BlueIt& n) : BlueNode(n) { }
   244         BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
   245         /// %Invalid constructor \& conversion.
   245         /// %Invalid constructor \& conversion.
   246 
   246 
   247         /// Initializes the iterator to be invalid.
   247         /// Initializes the iterator to be invalid.
   248         /// \sa Invalid for more details.
   248         /// \sa Invalid for more details.
   249         BlueIt(Invalid) { }
   249         BlueNodeIt(Invalid) { }
   250         /// Sets the iterator to the first blue node.
   250         /// Sets the iterator to the first blue node.
   251 
   251 
   252         /// Sets the iterator to the first blue node of the given
   252         /// Sets the iterator to the first blue node of the given
   253         /// digraph.
   253         /// digraph.
   254         explicit BlueIt(const BpGraph&) { }
   254         explicit BlueNodeIt(const BpGraph&) { }
   255         /// Sets the iterator to the given blue node.
   255         /// Sets the iterator to the given blue node.
   256 
   256 
   257         /// Sets the iterator to the given blue node of the given
   257         /// Sets the iterator to the given blue node of the given
   258         /// digraph.
   258         /// digraph.
   259         BlueIt(const BpGraph&, const BlueNode&) { }
   259         BlueNodeIt(const BpGraph&, const BlueNode&) { }
   260         /// Next node.
   260         /// Next node.
   261 
   261 
   262         /// Assign the iterator to the next blue node.
   262         /// Assign the iterator to the next blue node.
   263         ///
   263         ///
   264         BlueIt& operator++() { return *this; }
   264         BlueNodeIt& operator++() { return *this; }
   265       };
   265       };
   266 
   266 
   267       /// Iterator class for the nodes.
   267       /// Iterator class for the nodes.
   268 
   268 
   269       /// This iterator goes through each node of the graph.
   269       /// This iterator goes through each node of the graph.
   661       /// \brief Standard graph map type for the red nodes.
   661       /// \brief Standard graph map type for the red nodes.
   662       ///
   662       ///
   663       /// Standard graph map type for the red nodes.
   663       /// Standard graph map type for the red nodes.
   664       /// It conforms to the ReferenceMap concept.
   664       /// It conforms to the ReferenceMap concept.
   665       template<class T>
   665       template<class T>
   666       class RedMap : public ReferenceMap<Node, T, T&, const T&>
   666       class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
   667       {
   667       {
   668       public:
   668       public:
   669 
   669 
   670         /// Constructor
   670         /// Constructor
   671         explicit RedMap(const BpGraph&) { }
   671         explicit RedNodeMap(const BpGraph&) { }
   672         /// Constructor with given initial value
   672         /// Constructor with given initial value
   673         RedMap(const BpGraph&, T) { }
   673         RedNodeMap(const BpGraph&, T) { }
   674 
   674 
   675       private:
   675       private:
   676         ///Copy constructor
   676         ///Copy constructor
   677         RedMap(const RedMap& nm) :
   677         RedNodeMap(const RedNodeMap& nm) :
   678           ReferenceMap<Node, T, T&, const T&>(nm) { }
   678           ReferenceMap<Node, T, T&, const T&>(nm) { }
   679         ///Assignment operator
   679         ///Assignment operator
   680         template <typename CMap>
   680         template <typename CMap>
   681         RedMap& operator=(const CMap&) {
   681         RedNodeMap& operator=(const CMap&) {
   682           checkConcept<ReadMap<Node, T>, CMap>();
   682           checkConcept<ReadMap<Node, T>, CMap>();
   683           return *this;
   683           return *this;
   684         }
   684         }
   685       };
   685       };
   686 
   686 
   687       /// \brief Standard graph map type for the blue nodes.
   687       /// \brief Standard graph map type for the blue nodes.
   688       ///
   688       ///
   689       /// Standard graph map type for the blue nodes.
   689       /// Standard graph map type for the blue nodes.
   690       /// It conforms to the ReferenceMap concept.
   690       /// It conforms to the ReferenceMap concept.
   691       template<class T>
   691       template<class T>
   692       class BlueMap : public ReferenceMap<Node, T, T&, const T&>
   692       class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
   693       {
   693       {
   694       public:
   694       public:
   695 
   695 
   696         /// Constructor
   696         /// Constructor
   697         explicit BlueMap(const BpGraph&) { }
   697         explicit BlueNodeMap(const BpGraph&) { }
   698         /// Constructor with given initial value
   698         /// Constructor with given initial value
   699         BlueMap(const BpGraph&, T) { }
   699         BlueNodeMap(const BpGraph&, T) { }
   700 
   700 
   701       private:
   701       private:
   702         ///Copy constructor
   702         ///Copy constructor
   703         BlueMap(const BlueMap& nm) :
   703         BlueNodeMap(const BlueNodeMap& nm) :
   704           ReferenceMap<Node, T, T&, const T&>(nm) { }
   704           ReferenceMap<Node, T, T&, const T&>(nm) { }
   705         ///Assignment operator
   705         ///Assignment operator
   706         template <typename CMap>
   706         template <typename CMap>
   707         BlueMap& operator=(const CMap&) {
   707         BlueNodeMap& operator=(const CMap&) {
   708           checkConcept<ReadMap<Node, T>, CMap>();
   708           checkConcept<ReadMap<Node, T>, CMap>();
   709           return *this;
   709           return *this;
   710         }
   710         }
   711       };
   711       };
   712 
   712