23 ///algorithm using read-in functions \ref readNMapNode, \ref |
23 ///algorithm using read-in functions \ref readNMapNode, \ref |
24 ///readNMapEdge or \ref readEMapBool depending on the container. The |
24 ///readNMapEdge or \ref readEMapBool depending on the container. The |
25 ///resulting maximum matching can be attained by write-out functions |
25 ///resulting maximum matching can be attained by write-out functions |
26 ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool |
26 ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool |
27 ///depending on the preferred container. |
27 ///depending on the preferred container. |
28 |
28 /// |
29 ///The dual side of a mathcing is a map of the nodes to |
29 ///The dual side of a mathcing is a map of the nodes to |
30 ///MaxMatching::pos_enum, having values D, A and C showing the |
30 ///MaxMatching::pos_enum, having values D, A and C showing the |
31 ///Gallai-Edmonds decomposition of the graph. The nodes in D induce |
31 ///Gallai-Edmonds decomposition of the graph. The nodes in D induce |
32 ///a graph with factor-critical components, the nodes in A form the |
32 ///a graph with factor-critical components, the nodes in A form the |
33 ///barrier, and the nodes in C induce a graph having a perfect |
33 ///barrier, and the nodes in C induce a graph having a perfect |
34 ///matching. This decomposition can be attained by calling \ref |
34 ///matching. This decomposition can be attained by calling \ref |
35 ///writePos after running the algorithm. Before subsequent runs, |
35 ///writePos after running the algorithm. Before subsequent runs, |
36 ///the function \ref resetPos() must be called. |
36 ///the function \ref resetPos() must be called. |
37 |
37 /// |
38 ///\param Graph The undirected graph type the algorithm runs on. |
38 ///\param Graph The undirected graph type the algorithm runs on. |
39 |
39 /// |
40 ///\author Jacint Szabo |
40 ///\author Jacint Szabo |
41 template <typename Graph> |
41 template <typename Graph> |
42 class MaxMatching { |
42 class MaxMatching { |
43 typedef typename Graph::Node Node; |
43 typedef typename Graph::Node Node; |
44 typedef typename Graph::Edge Edge; |
44 typedef typename Graph::Edge Edge; |
237 ///Writes the canonical decomposition of the graph after running |
237 ///Writes the canonical decomposition of the graph after running |
238 ///the algorithm. |
238 ///the algorithm. |
239 |
239 |
240 ///After calling any run methods of the class, and before calling |
240 ///After calling any run methods of the class, and before calling |
241 ///\ref resetPos(), it writes the Gallai-Edmonds canonical |
241 ///\ref resetPos(), it writes the Gallai-Edmonds canonical |
242 ///decomposition of the graph. \c map must be a node map of \ref pos_enum 's. |
242 ///decomposition of the graph. \c map must be a node map |
|
243 ///of \ref pos_enum 's. |
243 template<typename NMapEnum> |
244 template<typename NMapEnum> |
244 void writePos (NMapEnum& map) const { |
245 void writePos (NMapEnum& map) const { |
245 NodeIt v; |
246 NodeIt v; |
246 for( G.first(v); G.valid(v); G.next(v)) map.set(v,position[v]); |
247 for( G.first(v); G.valid(v); G.next(v)) map.set(v,position[v]); |
247 } |
248 } |