lemon-0.x: comparison src/lemon/max

equal deleted inserted replaced

-:0aded56825bd
+:4c84c7433571
 ///\param Graph The undirected graph type the algorithm runs on.
 ///
 ///\author Jacint Szabo
 template <typename Graph>
 class MaxMatching {
+protected:
 typedef typename Graph::Node Node;
 typedef typename Graph::Edge Edge;
 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::IncEdgeIt IncEdgeIt;
 D=0,
 A=1,
 C=2
 };
-private:
+protected:
 static const int HEUR_density=2;
 const Graph& g;
 typename Graph::template NodeMap<Node> _mate;
 typename Graph::template NodeMap<pos_enum> position;
 ///Returns INVALID if the \c node is not covered by the actual matching.
 Node mate(Node& node) const {
 return _mate[node];
 }
-///Reads a matching from a \c Node map of \c Nodes.
+///Reads a matching from a \c Node valued \c Node map.
-///Reads a matching from a \c Node map of \c Nodes. This map must be \e
+///Reads a matching from a \c Node valued \c Node map. This map
-///symmetric, i.e. if \c map[u]==v then \c map[v]==u must hold, and
+///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
-///\c uv will be an edge of the matching.
+///must hold, and \c uv will be an edge of the matching.
 template<typename NMapN>
 void readNMapNode(NMapN& map) {
 for(NodeIt v(g); v!=INVALID; ++v) {
 	_mate.set(v,map[v]);
 }
 }
-///Writes the stored matching to a \c Node map of \c Nodes.
+///Writes the stored matching to a \c Node valued \c Node map.
-///Writes the stored matching to a \c Node map of \c Nodes. The
+///Writes the stored matching to a \c Node valued \c Node map. The
 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c
 ///map[v]==u will hold, and now \c uv is an edge of the matching.
 template<typename NMapN>
 void writeNMapNode (NMapN& map) const {
 for(NodeIt v(g); v!=INVALID; ++v) {
 	map.set(v,_mate[v]);
 }
 }
-///Reads a matching from a \c Node map of \c Edges.
+///Reads a matching from an \c UndirEdge valued \c Node map.
-///Reads a matching from a \c Node map of incident \c Edges. This
+///Reads a matching from an \c UndirEdge valued \c Node map. \c
-///map must have the property that if \c G.target(map[u])==v then \c
+///map[v] must be an \c UndirEdge incident to \c v. This map must
-///G.target(map[v])==u must hold, and now this edge is an edge of
+///have the property that if \c g.oppositeNode(u,map[u])==v then
-///the matching.
+///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
+///joining \c u to \v will be an edge of the matching.
 template<typename NMapE>
 void readNMapEdge(NMapE& map) {
 for(NodeIt v(g); v!=INVALID; ++v) {
-	Edge e=map[v];
+	UndirEdge e=map[v];
-	if ( g.valid(e) )
+	if ( e!=INVALID )
 	  g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e));
 }
 }
-///Writes the matching stored to a \c Node map of \c Edges.
+///Writes the matching stored to an \c UndirEdge valued \c Node map.
-///Writes the stored matching to a \c Node map of incident \c
+///Writes the stored matching to an \c UndirEdge valued \c Node
-///Edges. This map will have the property that if \c
+///map. \c map[v] will be an \c UndirEdge incident to \c v. This
-///g.target(map[u])==v then \c g.target(map[v])==u holds, and now this
+///map will have the property that if \c g.oppositeNode(u,map[u])
-///edge is an edge of the matching.
+///== v then \c map[u]==map[v] holds, and now this edge is an edge
+///of the matching.
 template<typename NMapE>
 void writeNMapEdge (NMapE& map)  const {
 typename Graph::template NodeMap<bool> todo(g,true);
 for(NodeIt v(g); v!=INVALID; ++v) {
 	if ( todo[v] && _mate[v]!=INVALID ) {
 	}
 }
 }
-///Reads a matching from an \c Edge map of \c bools.
+///Reads a matching from a \c bool valued \c Edge map.
-///Reads a matching from an \c Edge map of \c bools. This map must
+///Reads a matching from a \c bool valued \c Edge map. This map
-///have the property that there are no two adjacent edges \c e, \c
+///must have the property that there are no two incident edges \c
-///f with \c map[e]==map[f]==true. The edges \c e with \c
+///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
 ///map[e]==true form the matching.
 template<typename EMapB>
 void readEMapBool(EMapB& map) {
 for(UndirEdgeIt e(g); e!=INVALID; ++e) {
 	if ( map[e] ) {
 	}
 }
 }
-///Writes the matching stored to an \c Edge map of \c bools.
+///Writes the matching stored to a \c bool valued \c Edge map.
-///Writes the matching stored to an \c Edge map of \c bools. This
+///Writes the matching stored to a \c bool valued \c Edge
-///map will have the property that there are no two adjacent edges
+///map. This map will have the property that there are no two
-///\c e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
+///incident edges \c e, \c f with \c map[e]==map[f]==true. The
-///map[e]==true form the matching.
+///edges \c e with \c map[e]==true form the matching.
 template<typename EMapB>
 void writeEMapBool (EMapB& map) const {
 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
 typename Graph::template NodeMap<bool> todo(g,true);
 for(NodeIt v(g); v!=INVALID; ++v)  map.set(v,position[v]);
 }
 private:
 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
 		    UFE& blossom, UFE& tree);
 void normShrink(Node v, typename Graph::NodeMap<Node>& ear,
 		    UFE& blossom, UFE& tree);
 for(NodeIt v(g); v!=INVALID; ++v)
 position.set(v,C);
 typename Graph::template NodeMap<Node> ear(g,INVALID);
 //undefined for the base nodes of the blossoms (i.e. for the
 //representative elements of UFE blossom) and for the nodes in C
 typename UFE::MapType blossom_base(g);
 UFE blossom(blossom_base);
 typename UFE::MapType tree_base(g);
 UFE tree(tree_base);
+//If these UFE's would be members of the class then also
+//blossom_base and tree_base should be a member.
 for(NodeIt v(g); v!=INVALID; ++v) {
 if ( position[v]==C && _mate[v]==INVALID ) {
 	blossom.insert(v);
 	tree.insert(v);
 for(NodeIt v(g); v!=INVALID; ++v) {
 if ( _mate[v]!=INVALID ) {
 	++s;
 }
 }
-return (int)s/2;
+return s/2;
 }
 template <typename Graph>
 void MaxMatching<Graph>::resetMatching() {
 for(NodeIt v(g); v!=INVALID; ++v)
 /// @}
 } //END OF NAMESPACE LEMON
-#endif //EDMONDS_H
+#endif //LEMON_MAX_MATCHING_H

changeset 1165	c5e56125959a
parent 1164	80bb73097736
child 1166	db3d437560f3