COIN-OR::LEMON - Graph Library

Changeset 1090:9e9195331ea6 in lemon-0.x for src


Ignore:
Timestamp:
01/20/05 11:24:38 (15 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1486
Message:

resetPos deleted

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/max_matching.h

    r1077 r1090  
    4848  ///barrier, and the nodes in C induce a graph having a perfect
    4949  ///matching. This decomposition can be attained by calling \ref
    50   ///writePos after running the algorithm. Before subsequent runs,
    51   ///the function \ref resetPos() must be called.
     50  ///writePos after running the algorithm.
    5251  ///
    5352  ///\param Graph The undirected graph type the algorithm runs on.
     
    8887  public:
    8988   
    90     MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g,C) {}
     89    MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {}
    9190
    9291    ///Runs Edmonds' algorithm.
     
    9493    ///Runs Edmonds' algorithm for sparse graphs (number of edges <
    9594    ///2*number of nodes), and a heuristical Edmonds' algorithm with a
    96     ///heuristic of postponing shrinks for dense graphs. \pre Before
    97     ///the subsequent calls \ref resetPos must be called.
     95    ///heuristic of postponing shrinks for dense graphs.
    9896    inline void run();
    9997
     
    102100    ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
    103101    ///Edmonds' algorithm with a heuristic of postponing shrinks,
    104     ///giving a faster algorithm for dense graphs.  \pre Before the
    105     ///subsequent calls \ref resetPos must be called.
     102    ///giving a faster algorithm for dense graphs. 
    106103    void runEdmonds( int heur );
    107104
     
    117114    ///run() it returns the size of a maximum matching in the graph.
    118115    int size() const;
    119 
    120     ///Resets the map storing the Gallai-Edmonds decomposition.
    121    
    122     ///Resets the map storing the Gallai-Edmonds decomposition of the
    123     ///graph, making it possible to run the algorithm. Must be called
    124     ///before all runs of the Edmonds algorithm, except for the first
    125     ///run.
    126     void resetPos();
    127116
    128117    ///Resets the actual matching to the empty matching.
     
    246235    ///the algorithm.
    247236
    248     ///After calling any run methods of the class, and before calling
    249     ///\ref resetPos(), it writes the Gallai-Edmonds canonical
    250     ///decomposition of the graph. \c map must be a node map
    251     ///of \ref pos_enum 's.
     237    ///After calling any run methods of the class, it writes the
     238    ///Gallai-Edmonds canonical decomposition of the graph. \c map
     239    ///must be a node map of \ref pos_enum 's.
    252240    template<typename NMapEnum>
    253241    void writePos (NMapEnum& map) const {
     
    291279  template <typename Graph>
    292280  void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
    293      
     281
     282    for(NodeIt v(g); v!=INVALID; ++v)
     283      position.set(v,C);     
     284
    294285    typename Graph::template NodeMap<Node> ear(g,INVALID);
    295286    //undefined for the base nodes of the blossoms (i.e. for the
     
    474465    }
    475466    return (int)s/2;
    476   }
    477 
    478   template <typename Graph>
    479   void MaxMatching<Graph>::resetPos() {
    480     for(NodeIt v(g); v!=INVALID; ++v)
    481       position.set(v,C);     
    482467  }
    483468
Note: See TracChangeset for help on using the changeset viewer.