Changeset 1165:c5e56125959a in lemon-0.x for src/lemon/max_matching.h

Timestamp:

02/21/05 19:51:11 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1569

Message:

some minor changes, docs, etc.

File:

• src/lemon/max_matching.h (modified) (11 diffs)

src/lemon/max_matching.h

@@ -55 +55 @@
   template <typename Graph>
   class MaxMatching {
+
+  protected:
+
     typedef typename Graph::Node Node;
     typedef typename Graph::Edge Edge;
@@ -78 +81 @@
     }; 
 
-  private:
+  protected:
 
     static const int HEUR_density=2;
@@ -129 +132 @@
     } 
 
-    ///Reads a matching from a \c Node map of \c Nodes.
-
-    ///Reads a matching from a \c Node map of \c Nodes. This map must be \e
-    ///symmetric, i.e. if \c map[u]==v then \c map[v]==u must hold, and
-    ///\c uv will be an edge of the matching.
+    ///Reads a matching from a \c Node valued \c Node map.
+
+    ///Reads a matching from a \c Node valued \c Node map. This map
+    ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
+    ///must hold, and \c uv will be an edge of the matching.
     template<typename NMapN>
     void readNMapNode(NMapN& map) {
@@ -141 +144 @@
     } 
     
-    ///Writes the stored matching to a \c Node map of \c Nodes.
-
-    ///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.
+
+    ///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.
@@ -153 +156 @@
     } 
 
-    ///Reads a matching from a \c Node map of \c Edges.
-
-    ///Reads a matching from a \c Node map of incident \c Edges. This
-    ///map must have the property that if \c G.target(map[u])==v then \c
-    ///G.target(map[v])==u must hold, and now this edge is an edge of
-    ///the matching.
+    ///Reads a matching from an \c UndirEdge valued \c Node map.
+
+    ///Reads a matching from an \c UndirEdge valued \c Node map. \c
+    ///map[v] must be an \c UndirEdge incident to \c v. This map must
+    ///have the property that if \c g.oppositeNode(u,map[u])==v then
+    ///\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];
-        if ( g.valid(e) )
+        UndirEdge e=map[v];
+        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 stored matching to a \c Node map of incident \c
-    ///Edges. This map will have the property that if \c
-    ///g.target(map[u])==v then \c g.target(map[v])==u holds, and now this
-    ///edge is an edge of the matching.
+    ///Writes the matching stored to an \c UndirEdge valued \c Node map.
+
+    ///Writes the stored matching to an \c UndirEdge valued \c Node
+    ///map. \c map[v] will be an \c UndirEdge incident to \c v. This
+    ///map will have the property that if \c g.oppositeNode(u,map[u])
+    ///== 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 {
@@ -194 +199 @@
 
 
-    ///Reads a matching from an \c Edge map of \c bools.
-    
-    ///Reads a matching from an \c Edge map of \c bools. This map must
-    ///have the property that there are no two adjacent edges \c e, \c
-    ///f with \c map[e]==map[f]==true. The edges \c e with \c
+    ///Reads a matching from a \c bool valued \c Edge map.
+    
+    ///Reads a matching from a \c bool valued \c Edge map. This map
+    ///must have the property that there are no two incident edges \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>
@@ -213 +218 @@
 
 
-    ///Writes the matching stored to an \c Edge map of \c bools.
-
-    ///Writes the matching stored to an \c Edge map of \c bools. This
-    ///map will have the property that there are no two adjacent edges
-    ///\c e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
-    ///map[e]==true form the matching.
+    ///Writes the matching stored to a \c bool valued \c Edge map.
+
+    ///Writes the matching stored to a \c bool valued \c Edge
+    ///map. This map will have the property that there are no two
+    ///incident edges \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 writeEMapBool (EMapB& map) const {
@@ -253 +258 @@
   private: 
 
+ 
     void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
                     UFE& blossom, UFE& tree);
@@ -293 +299 @@
     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
- 
+    //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) {
@@ -472 +480 @@
       }
     }
-    return (int)s/2;
+    return s/2;
   }
 
@@ -563 +571 @@
 } //END OF NAMESPACE LEMON
 
-#endif //EDMONDS_H
+#endif //LEMON_MAX_MATCHING_H