1.1 --- a/src/lemon/max_matching.h Mon Feb 21 14:59:12 2005 +0000
1.2 +++ b/src/lemon/max_matching.h Mon Feb 21 18:51:11 2005 +0000
1.3 @@ -54,6 +54,9 @@
1.4 ///\author Jacint Szabo
1.5 template <typename Graph>
1.6 class MaxMatching {
1.7 +
1.8 + protected:
1.9 +
1.10 typedef typename Graph::Node Node;
1.11 typedef typename Graph::Edge Edge;
1.12 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
1.13 @@ -77,7 +80,7 @@
1.14 C=2
1.15 };
1.16
1.17 - private:
1.18 + protected:
1.19
1.20 static const int HEUR_density=2;
1.21 const Graph& g;
1.22 @@ -128,11 +131,11 @@
1.23 return _mate[node];
1.24 }
1.25
1.26 - ///Reads a matching from a \c Node map of \c Nodes.
1.27 + ///Reads a matching from a \c Node valued \c Node map.
1.28
1.29 - ///Reads a matching from a \c Node map of \c Nodes. This map must be \e
1.30 - ///symmetric, i.e. if \c map[u]==v then \c map[v]==u must hold, and
1.31 - ///\c uv will be an edge of the matching.
1.32 + ///Reads a matching from a \c Node valued \c Node map. This map
1.33 + ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
1.34 + ///must hold, and \c uv will be an edge of the matching.
1.35 template<typename NMapN>
1.36 void readNMapNode(NMapN& map) {
1.37 for(NodeIt v(g); v!=INVALID; ++v) {
1.38 @@ -140,9 +143,9 @@
1.39 }
1.40 }
1.41
1.42 - ///Writes the stored matching to a \c Node map of \c Nodes.
1.43 + ///Writes the stored matching to a \c Node valued \c Node map.
1.44
1.45 - ///Writes the stored matching to a \c Node map of \c Nodes. The
1.46 + ///Writes the stored matching to a \c Node valued \c Node map. The
1.47 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c
1.48 ///map[v]==u will hold, and now \c uv is an edge of the matching.
1.49 template<typename NMapN>
1.50 @@ -152,27 +155,29 @@
1.51 }
1.52 }
1.53
1.54 - ///Reads a matching from a \c Node map of \c Edges.
1.55 + ///Reads a matching from an \c UndirEdge valued \c Node map.
1.56
1.57 - ///Reads a matching from a \c Node map of incident \c Edges. This
1.58 - ///map must have the property that if \c G.target(map[u])==v then \c
1.59 - ///G.target(map[v])==u must hold, and now this edge is an edge of
1.60 - ///the matching.
1.61 + ///Reads a matching from an \c UndirEdge valued \c Node map. \c
1.62 + ///map[v] must be an \c UndirEdge incident to \c v. This map must
1.63 + ///have the property that if \c g.oppositeNode(u,map[u])==v then
1.64 + ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
1.65 + ///joining \c u to \v will be an edge of the matching.
1.66 template<typename NMapE>
1.67 void readNMapEdge(NMapE& map) {
1.68 for(NodeIt v(g); v!=INVALID; ++v) {
1.69 - Edge e=map[v];
1.70 - if ( g.valid(e) )
1.71 + UndirEdge e=map[v];
1.72 + if ( e!=INVALID )
1.73 g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e));
1.74 }
1.75 }
1.76
1.77 - ///Writes the matching stored to a \c Node map of \c Edges.
1.78 + ///Writes the matching stored to an \c UndirEdge valued \c Node map.
1.79
1.80 - ///Writes the stored matching to a \c Node map of incident \c
1.81 - ///Edges. This map will have the property that if \c
1.82 - ///g.target(map[u])==v then \c g.target(map[v])==u holds, and now this
1.83 - ///edge is an edge of the matching.
1.84 + ///Writes the stored matching to an \c UndirEdge valued \c Node
1.85 + ///map. \c map[v] will be an \c UndirEdge incident to \c v. This
1.86 + ///map will have the property that if \c g.oppositeNode(u,map[u])
1.87 + ///== v then \c map[u]==map[v] holds, and now this edge is an edge
1.88 + ///of the matching.
1.89 template<typename NMapE>
1.90 void writeNMapEdge (NMapE& map) const {
1.91 typename Graph::template NodeMap<bool> todo(g,true);
1.92 @@ -193,11 +198,11 @@
1.93 }
1.94
1.95
1.96 - ///Reads a matching from an \c Edge map of \c bools.
1.97 + ///Reads a matching from a \c bool valued \c Edge map.
1.98
1.99 - ///Reads a matching from an \c Edge map of \c bools. This map must
1.100 - ///have the property that there are no two adjacent edges \c e, \c
1.101 - ///f with \c map[e]==map[f]==true. The edges \c e with \c
1.102 + ///Reads a matching from a \c bool valued \c Edge map. This map
1.103 + ///must have the property that there are no two incident edges \c
1.104 + ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
1.105 ///map[e]==true form the matching.
1.106 template<typename EMapB>
1.107 void readEMapBool(EMapB& map) {
1.108 @@ -212,12 +217,12 @@
1.109 }
1.110
1.111
1.112 - ///Writes the matching stored to an \c Edge map of \c bools.
1.113 + ///Writes the matching stored to a \c bool valued \c Edge map.
1.114
1.115 - ///Writes the matching stored to an \c Edge map of \c bools. This
1.116 - ///map will have the property that there are no two adjacent edges
1.117 - ///\c e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
1.118 - ///map[e]==true form the matching.
1.119 + ///Writes the matching stored to a \c bool valued \c Edge
1.120 + ///map. This map will have the property that there are no two
1.121 + ///incident edges \c e, \c f with \c map[e]==map[f]==true. The
1.122 + ///edges \c e with \c map[e]==true form the matching.
1.123 template<typename EMapB>
1.124 void writeEMapBool (EMapB& map) const {
1.125 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
1.126 @@ -252,6 +257,7 @@
1.127
1.128 private:
1.129
1.130 +
1.131 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
1.132 UFE& blossom, UFE& tree);
1.133
1.134 @@ -292,12 +298,14 @@
1.135
1.136 typename Graph::template NodeMap<Node> ear(g,INVALID);
1.137 //undefined for the base nodes of the blossoms (i.e. for the
1.138 - //representative elements of UFE blossom) and for the nodes in C
1.139 -
1.140 + //representative elements of UFE blossom) and for the nodes in C
1.141 +
1.142 typename UFE::MapType blossom_base(g);
1.143 UFE blossom(blossom_base);
1.144 typename UFE::MapType tree_base(g);
1.145 UFE tree(tree_base);
1.146 + //If these UFE's would be members of the class then also
1.147 + //blossom_base and tree_base should be a member.
1.148
1.149 for(NodeIt v(g); v!=INVALID; ++v) {
1.150 if ( position[v]==C && _mate[v]==INVALID ) {
1.151 @@ -471,7 +479,7 @@
1.152 ++s;
1.153 }
1.154 }
1.155 - return (int)s/2;
1.156 + return s/2;
1.157 }
1.158
1.159 template <typename Graph>
1.160 @@ -562,4 +570,4 @@
1.161
1.162 } //END OF NAMESPACE LEMON
1.163
1.164 -#endif //EDMONDS_H
1.165 +#endif //LEMON_MAX_MATCHING_H