53 /// |
53 /// |
54 /// You can assume that all undirected bipartite graph can be handled |
54 /// You can assume that all undirected bipartite graph can be handled |
55 /// as an undirected graph and consequently as a static graph. |
55 /// as an undirected graph and consequently as a static graph. |
56 /// |
56 /// |
57 /// The bipartite graph stores two types of nodes which are named |
57 /// The bipartite graph stores two types of nodes which are named |
58 /// ANode and BNode. The graph type contains two types ANode and BNode |
58 /// ANode and BNode. The graph type contains two types ANode and |
59 /// which are inherited from Node type. Moreover they have |
59 /// BNode which are inherited from Node type. Moreover they have |
60 /// constructor which converts Node to either ANode or BNode when it is |
60 /// constructor which converts Node to either ANode or BNode when |
61 /// possible. Therefor everywhere the Node type can be used instead of |
61 /// it is possible. Therefor everywhere the Node type can be used |
62 /// ANode and BNode. So the usage of the ANode and BNode is suggested. |
62 /// instead of ANode and BNode. So the usage of the ANode and |
|
63 /// BNode is not suggested. |
63 /// |
64 /// |
64 /// The iteration on the partition can be done with the ANodeIt and |
65 /// The iteration on the partition can be done with the ANodeIt and |
65 /// BNodeIt classes. The node map can be used to map values to the nodes |
66 /// BNodeIt classes. The node map can be used to map values to the nodes |
66 /// and similarly we can use to map values for just the ANodes and |
67 /// and similarly we can use to map values for just the ANodes and |
67 /// BNodes the ANodeMap and BNodeMap template classes. |
68 /// BNodes the ANodeMap and BNodeMap template classes. |
68 |
69 |
69 class BpUGraph { |
70 class BpUGraph { |
70 public: |
71 public: |
71 /// \todo undocumented |
72 /// \brief The undirected graph should be tagged by the |
72 /// |
73 /// UndirectedTag. |
|
74 /// |
|
75 /// The undirected graph should be tagged by the UndirectedTag. This |
|
76 /// tag helps the enable_if technics to make compile time |
|
77 /// specializations for undirected graphs. |
73 typedef True UndirectedTag; |
78 typedef True UndirectedTag; |
74 |
79 |
75 /// \brief The base type of node iterators, |
80 /// \brief The base type of node iterators, |
76 /// or in other words, the trivial node iterator. |
81 /// or in other words, the trivial node iterator. |
77 /// |
82 /// |
120 /// ordering of the items. |
125 /// ordering of the items. |
121 bool operator<(Node) const { return false; } |
126 bool operator<(Node) const { return false; } |
122 |
127 |
123 }; |
128 }; |
124 |
129 |
125 /// \brief The base type of anode iterators, |
130 /// \brief Helper class for ANodes. |
126 /// or in other words, the trivial anode iterator. |
131 /// |
127 /// |
132 /// This class is just a helper class for ANodes, it is not |
128 /// This is the base type of each anode iterator, |
133 /// suggested to use it directly. It can be converted easily to |
129 /// thus each kind of anode iterator converts to this. |
134 /// node and vice versa. The usage of this class is limited |
130 /// More precisely each kind of node iterator should be inherited |
135 /// two use just as template parameters for special map types. |
131 /// from the trivial anode iterator. The ANode class should be used |
|
132 /// only in special cases. Usually the Node type should be used insted |
|
133 /// of it. |
|
134 class ANode { |
136 class ANode { |
135 public: |
137 public: |
136 /// Default constructor |
138 /// Default constructor |
137 |
139 |
138 /// @warning The default constructor sets the iterator |
140 /// @warning The default constructor sets the iterator |
177 /// ordering of the items. |
179 /// ordering of the items. |
178 bool operator<(ANode) const { return false; } |
180 bool operator<(ANode) const { return false; } |
179 |
181 |
180 }; |
182 }; |
181 |
183 |
182 /// \brief The base type of bnode iterators, |
184 /// \brief Helper class for BNodes. |
183 /// or in other words, the trivial bnode iterator. |
185 /// |
184 /// |
186 /// This class is just a helper class for BNodes, it is not |
185 /// This is the base type of each anode iterator, |
187 /// suggested to use it directly. It can be converted easily to |
186 /// thus each kind of anode iterator converts to this. |
188 /// node and vice versa. The usage of this class is limited |
187 /// More precisely each kind of node iterator should be inherited |
189 /// two use just as template parameters for special map types. |
188 /// from the trivial anode iterator. The BNode class should be used |
|
189 /// only in special cases. Usually the Node type should be used insted |
|
190 /// of it. |
|
191 class BNode { |
190 class BNode { |
192 public: |
191 public: |
193 /// Default constructor |
192 /// Default constructor |
194 |
193 |
195 /// @warning The default constructor sets the iterator |
194 /// @warning The default constructor sets the iterator |
288 /// of nodes in graph \c g of type \c Graph like this: |
287 /// of nodes in graph \c g of type \c Graph like this: |
289 ///\code |
288 ///\code |
290 /// int count=0; |
289 /// int count=0; |
291 /// for (Graph::ANodeIt n(g); n!=INVALID; ++n) ++count; |
290 /// for (Graph::ANodeIt n(g); n!=INVALID; ++n) ++count; |
292 ///\endcode |
291 ///\endcode |
293 class ANodeIt : public ANode { |
292 class ANodeIt : public Node { |
294 public: |
293 public: |
295 /// Default constructor |
294 /// Default constructor |
296 |
295 |
297 /// @warning The default constructor sets the iterator |
296 /// @warning The default constructor sets the iterator |
298 /// to an undefined value. |
297 /// to an undefined value. |
333 /// of nodes in graph \c g of type \c Graph like this: |
332 /// of nodes in graph \c g of type \c Graph like this: |
334 ///\code |
333 ///\code |
335 /// int count=0; |
334 /// int count=0; |
336 /// for (Graph::BNodeIt n(g); n!=INVALID; ++n) ++count; |
335 /// for (Graph::BNodeIt n(g); n!=INVALID; ++n) ++count; |
337 ///\endcode |
336 ///\endcode |
338 class BNodeIt : public BNode { |
337 class BNodeIt : public Node { |
339 public: |
338 public: |
340 /// Default constructor |
339 /// Default constructor |
341 |
340 |
342 /// @warning The default constructor sets the iterator |
341 /// @warning The default constructor sets the iterator |
343 /// to an undefined value. |
342 /// to an undefined value. |
816 }; |
815 }; |
817 |
816 |
818 /// \brief Direct the given undirected edge. |
817 /// \brief Direct the given undirected edge. |
819 /// |
818 /// |
820 /// Direct the given undirected edge. The returned edge source |
819 /// Direct the given undirected edge. The returned edge source |
821 /// will be the given edge. |
820 /// will be the given node. |
822 Edge direct(const UEdge&, const Node&) const { |
821 Edge direct(const UEdge&, const Node&) const { |
823 return INVALID; |
822 return INVALID; |
824 } |
823 } |
825 |
824 |
826 /// \brief Direct the given undirected edge. |
825 /// \brief Direct the given undirected edge. |
827 /// |
826 /// |
828 /// Direct the given undirected edge. The returned edge source |
827 /// Direct the given undirected edge. The returned edge |
829 /// will be the source of the undirected edge if the given bool |
828 /// represents the given undireted edge and the direction comes |
830 /// is true. |
829 /// from the given bool. The source of the undirected edge and |
|
830 /// the directed edge is the same when the given bool is true. |
831 Edge direct(const UEdge&, bool) const { |
831 Edge direct(const UEdge&, bool) const { |
832 return INVALID; |
832 return INVALID; |
833 } |
833 } |
834 |
834 |
835 /// \brief Returns true when the given node is an ANode. |
835 /// \brief Returns true when the given node is an ANode. |
853 Node bNode(UEdge) const { return INVALID;} |
853 Node bNode(UEdge) const { return INVALID;} |
854 |
854 |
855 /// \brief Returns true if the edge has default orientation. |
855 /// \brief Returns true if the edge has default orientation. |
856 /// |
856 /// |
857 /// Returns whether the given directed edge is same orientation as |
857 /// Returns whether the given directed edge is same orientation as |
858 /// the corresponding undirected edge. |
858 /// the corresponding undirected edge's default orientation. |
859 bool direction(Edge) const { return true; } |
859 bool direction(Edge) const { return true; } |
860 |
860 |
861 /// \brief Returns the opposite directed edge. |
861 /// \brief Returns the opposite directed edge. |
862 /// |
862 /// |
863 /// Returns the opposite directed edge. |
863 /// Returns the opposite directed edge. |
864 Edge oppositeEdge(Edge) const { return INVALID; } |
864 Edge oppositeEdge(Edge) const { return INVALID; } |
865 |
865 |
866 /// \brief Opposite node on an edge |
866 /// \brief Opposite node on an edge |
867 /// |
867 /// |
868 /// \return the opposite of the given Node on the given Edge |
868 /// \return the opposite of the given Node on the given UEdge |
869 Node oppositeNode(Node, UEdge) const { return INVALID; } |
869 Node oppositeNode(Node, UEdge) const { return INVALID; } |
870 |
870 |
871 /// \brief First node of the undirected edge. |
871 /// \brief First node of the undirected edge. |
872 /// |
872 /// |
873 /// \return the first node of the given UEdge. |
873 /// \return the first node of the given UEdge. |
874 /// |
874 /// |
875 /// Naturally uectected edges don't have direction and thus |
875 /// Naturally undirected edges don't have direction and thus |
876 /// don't have source and target node. But we use these two methods |
876 /// don't have source and target node. But we use these two methods |
877 /// to query the two endnodes of the edge. The direction of the edge |
877 /// to query the two endnodes of the edge. The direction of the edge |
878 /// which arises this way is called the inherent direction of the |
878 /// which arises this way is called the inherent direction of the |
879 /// undirected edge, and is used to define the "default" direction |
879 /// undirected edge, and is used to define the "default" direction |
880 /// of the directed versions of the edges. |
880 /// of the directed versions of the edges. |