Changeset 1165:c5e56125959a in lemon0.x for src/lemon/max_matching.h
 Timestamp:
 02/21/05 19:51:11 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1569
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/max_matching.h
r1164 r1165 55 55 template <typename Graph> 56 56 class MaxMatching { 57 58 protected: 59 57 60 typedef typename Graph::Node Node; 58 61 typedef typename Graph::Edge Edge; … … 78 81 }; 79 82 80 pr ivate:83 protected: 81 84 82 85 static const int HEUR_density=2; … … 129 132 } 130 133 131 ///Reads a matching from a \c Node map of \c Nodes.132 133 ///Reads a matching from a \c Node map of \c Nodes. This map must be \e134 /// symmetric, i.e. if \c map[u]==v then \c map[v]==u must hold, and135 /// \c uv will be an edge of the matching.134 ///Reads a matching from a \c Node valued \c Node map. 135 136 ///Reads a matching from a \c Node valued \c Node map. This map 137 ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u 138 ///must hold, and \c uv will be an edge of the matching. 136 139 template<typename NMapN> 137 140 void readNMapNode(NMapN& map) { … … 141 144 } 142 145 143 ///Writes the stored matching to a \c Node map of \c Nodes.144 145 ///Writes the stored matching to a \c Node map of \c Nodes. The146 ///Writes the stored matching to a \c Node valued \c Node map. 147 148 ///Writes the stored matching to a \c Node valued \c Node map. The 146 149 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c 147 150 ///map[v]==u will hold, and now \c uv is an edge of the matching. … … 153 156 } 154 157 155 ///Reads a matching from a \c Node map of \c Edges. 156 157 ///Reads a matching from a \c Node map of incident \c Edges. This 158 ///map must have the property that if \c G.target(map[u])==v then \c 159 ///G.target(map[v])==u must hold, and now this edge is an edge of 160 ///the matching. 158 ///Reads a matching from an \c UndirEdge valued \c Node map. 159 160 ///Reads a matching from an \c UndirEdge valued \c Node map. \c 161 ///map[v] must be an \c UndirEdge incident to \c v. This map must 162 ///have the property that if \c g.oppositeNode(u,map[u])==v then 163 ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge 164 ///joining \c u to \v will be an edge of the matching. 161 165 template<typename NMapE> 162 166 void readNMapEdge(NMapE& map) { 163 167 for(NodeIt v(g); v!=INVALID; ++v) { 164 Edge e=map[v];165 if ( g.valid(e))168 UndirEdge e=map[v]; 169 if ( e!=INVALID ) 166 170 g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e)); 167 171 } 168 172 } 169 173 170 ///Writes the matching stored to a \c Node map of \c Edges. 171 172 ///Writes the stored matching to a \c Node map of incident \c 173 ///Edges. This map will have the property that if \c 174 ///g.target(map[u])==v then \c g.target(map[v])==u holds, and now this 175 ///edge is an edge of the matching. 174 ///Writes the matching stored to an \c UndirEdge valued \c Node map. 175 176 ///Writes the stored matching to an \c UndirEdge valued \c Node 177 ///map. \c map[v] will be an \c UndirEdge incident to \c v. This 178 ///map will have the property that if \c g.oppositeNode(u,map[u]) 179 ///== v then \c map[u]==map[v] holds, and now this edge is an edge 180 ///of the matching. 176 181 template<typename NMapE> 177 182 void writeNMapEdge (NMapE& map) const { … … 194 199 195 200 196 ///Reads a matching from a n \c Edge map of \c bools.197 198 ///Reads a matching from a n \c Edge map of \c bools. This map must199 /// have the property that there are no two adjacent edges \c e,\c200 /// f with \c map[e]==map[f]==true. The edges \c e with \c201 ///Reads a matching from a \c bool valued \c Edge map. 202 203 ///Reads a matching from a \c bool valued \c Edge map. This map 204 ///must have the property that there are no two incident edges \c 205 ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c 201 206 ///map[e]==true form the matching. 202 207 template<typename EMapB> … … 213 218 214 219 215 ///Writes the matching stored to a n \c Edge map of \c bools.216 217 ///Writes the matching stored to a n \c Edge map of \c bools. This218 ///map will have the property that there are no two adjacent edges219 /// \c e, \c f with \c map[e]==map[f]==true. The edges \c e with \c220 /// map[e]==true form the matching.220 ///Writes the matching stored to a \c bool valued \c Edge map. 221 222 ///Writes the matching stored to a \c bool valued \c Edge 223 ///map. This map will have the property that there are no two 224 ///incident edges \c e, \c f with \c map[e]==map[f]==true. The 225 ///edges \c e with \c map[e]==true form the matching. 221 226 template<typename EMapB> 222 227 void writeEMapBool (EMapB& map) const { … … 253 258 private: 254 259 260 255 261 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 256 262 UFE& blossom, UFE& tree); … … 293 299 typename Graph::template NodeMap<Node> ear(g,INVALID); 294 300 //undefined for the base nodes of the blossoms (i.e. for the 295 //representative elements of UFE blossom) and for the nodes in C 296 301 //representative elements of UFE blossom) and for the nodes in C 302 297 303 typename UFE::MapType blossom_base(g); 298 304 UFE blossom(blossom_base); 299 305 typename UFE::MapType tree_base(g); 300 306 UFE tree(tree_base); 307 //If these UFE's would be members of the class then also 308 //blossom_base and tree_base should be a member. 301 309 302 310 for(NodeIt v(g); v!=INVALID; ++v) { … … 472 480 } 473 481 } 474 return (int)s/2;482 return s/2; 475 483 } 476 484 … … 563 571 } //END OF NAMESPACE LEMON 564 572 565 #endif // EDMONDS_H573 #endif //LEMON_MAX_MATCHING_H
Note: See TracChangeset
for help on using the changeset viewer.