COIN-OR::LEMON - Graph Library

Changeset 1587:8f1c317ebeb4 in lemon-0.x for lemon


Ignore:
Timestamp:
07/26/05 15:15:13 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2091
Message:

Doc improvements

Location:
lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/alteration_notifier.h

    r1435 r1587  
    2121#include <algorithm>
    2222
    23 ///\ingroup graphmaps
     23///\ingroup graphmapfactory
    2424///\file
    2525///\brief Observer registry for graph alteration observers.
     
    2727namespace lemon {
    2828
    29   /// \addtogroup graphmaps
     29  /// \addtogroup graphmapfactory
    3030  /// @{
    3131
  • lemon/bits/array_map.h

    r1435 r1587  
    2121#include <lemon/bits/map_iterator.h>
    2222
    23 ///\ingroup graphmaps
     23///\ingroup graphmapfactory
    2424///\file
    2525///\brief Graph maps that construates and destruates
     
    2929
    3030
    31   /// \addtogroup graphmaps
     31  /// \addtogroup graphmapfactory
    3232  /// @{
    3333       
  • lemon/bits/default_map.h

    r1435 r1587  
    2222#include <lemon/bits/vector_map.h>
    2323
    24 ///\ingroup graphmaps
     24///\ingroup graphmapfactory
    2525///\file
    2626///\brief Graph maps that construct and destruct
     
    2929namespace lemon {
    3030
    31 /// \addtogroup graphmaps
     31/// \addtogroup graphmapfactory
    3232/// @{
    3333
  • lemon/bits/map_iterator.h

    r1435 r1587  
    2323#include <lemon/graph_utils.h>
    2424
    25 ///\ingroup graphmaps
     25///\ingroup graphmapfactory
    2626///\file
    2727///\brief Iterators on the maps.
     
    2929namespace lemon {
    3030
    31   /// \addtogroup graphmaps
     31  /// \addtogroup graphmapfactory
    3232  /// @{
    3333
  • lemon/bits/vector_map.h

    r1435 r1587  
    2525#include <lemon/bits/alteration_notifier.h>
    2626
    27 ///\ingroup graphmaps
     27///\ingroup graphmapfactory
    2828///\file
    2929///\brief Vector based graph maps.
     
    3131namespace lemon {
    3232 
    33   /// \addtogroup graphmaps
     33  /// \addtogroup graphmapfactory
    3434  /// @{
    3535 
  • lemon/max_matching.h

    r1435 r1587  
    9898    ///2*number of nodes), and a heuristical Edmonds' algorithm with a
    9999    ///heuristic of postponing shrinks for dense graphs.
    100     inline void run();
     100    void run() {
     101      if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
     102        greedyMatching();
     103        runEdmonds(0);
     104      } else runEdmonds(1);
     105    }
     106
    101107
    102108    ///Runs Edmonds' algorithm.
     
    105111    ///Edmonds' algorithm with a heuristic of postponing shrinks,
    106112    ///giving a faster algorithm for dense graphs. 
    107     void runEdmonds( int heur );
     113    void runEdmonds( int heur = 1 ) {
     114     
     115      for(NodeIt v(g); v!=INVALID; ++v)
     116        position.set(v,C);     
     117     
     118      typename Graph::template NodeMap<Node> ear(g,INVALID);
     119      //undefined for the base nodes of the blossoms (i.e. for the
     120      //representative elements of UFE blossom) and for the nodes in C
     121     
     122      typename UFE::MapType blossom_base(g);
     123      UFE blossom(blossom_base);
     124      typename UFE::MapType tree_base(g);
     125      UFE tree(tree_base);
     126      //If these UFE's would be members of the class then also
     127      //blossom_base and tree_base should be a member.
     128     
     129      for(NodeIt v(g); v!=INVALID; ++v) {
     130        if ( position[v]==C && _mate[v]==INVALID ) {
     131          blossom.insert(v);
     132          tree.insert(v);
     133          position.set(v,D);
     134          if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
     135          else normShrink( v, ear, blossom, tree );
     136        }
     137      }
     138    }
     139
    108140
    109141    ///Finds a greedy matching starting from the actual matching.
     
    111143    ///Starting form the actual matching stored, it finds a maximal
    112144    ///greedy matching.
    113     void greedyMatching();
     145    void greedyMatching() {
     146      for(NodeIt v(g); v!=INVALID; ++v)
     147        if ( _mate[v]==INVALID ) {
     148          for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
     149            Node y=g.runningNode(e);
     150            if ( _mate[y]==INVALID && y!=v ) {
     151              _mate.set(v,y);
     152              _mate.set(y,v);
     153              break;
     154            }
     155          }
     156        }
     157    }
    114158
    115159    ///Returns the size of the actual matching stored.
     
    117161    ///Returns the size of the actual matching stored. After \ref
    118162    ///run() it returns the size of a maximum matching in the graph.
    119     int size() const;
     163    int size() const {
     164      int s=0;
     165      for(NodeIt v(g); v!=INVALID; ++v) {
     166        if ( _mate[v]!=INVALID ) {
     167          ++s;
     168        }
     169      }
     170      return s/2;
     171    }
     172
    120173
    121174    ///Resets the actual matching to the empty matching.
     
    123176    ///Resets the actual matching to the empty matching. 
    124177    ///
    125     void resetMatching();
     178    void resetMatching() {
     179      for(NodeIt v(g); v!=INVALID; ++v)
     180        _mate.set(v,INVALID);     
     181    }
    126182
    127183    ///Returns the mate of a node in the actual matching.
     
    285341
    286342  template <typename Graph>
    287   void MaxMatching<Graph>::run() {
    288     if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
    289       greedyMatching();
    290       runEdmonds(0);
    291     } else runEdmonds(1);
    292   }
    293 
    294 
    295   template <typename Graph>
    296   void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
    297 
    298     for(NodeIt v(g); v!=INVALID; ++v)
    299       position.set(v,C);     
    300 
    301     typename Graph::template NodeMap<Node> ear(g,INVALID);
    302     //undefined for the base nodes of the blossoms (i.e. for the
    303     //representative elements of UFE blossom) and for the nodes in C
    304 
    305     typename UFE::MapType blossom_base(g);
    306     UFE blossom(blossom_base);
    307     typename UFE::MapType tree_base(g);
    308     UFE tree(tree_base);
    309     //If these UFE's would be members of the class then also
    310     //blossom_base and tree_base should be a member.
    311 
    312     for(NodeIt v(g); v!=INVALID; ++v) {
    313       if ( position[v]==C && _mate[v]==INVALID ) {
    314         blossom.insert(v);
    315         tree.insert(v);
    316         position.set(v,D);
    317         if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
    318         else normShrink( v, ear, blossom, tree );
    319       }
    320     }
    321   }
    322 
    323    
    324   template <typename Graph>
    325343  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 
    326344                                      UFE& blossom, UFE& tree) {
     
    458476      }
    459477    }
    460   }
    461 
    462   template <typename Graph>
    463   void MaxMatching<Graph>::greedyMatching() {
    464     for(NodeIt v(g); v!=INVALID; ++v)
    465       if ( _mate[v]==INVALID ) {
    466         for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
    467           Node y=g.runningNode(e);
    468           if ( _mate[y]==INVALID && y!=v ) {
    469             _mate.set(v,y);
    470             _mate.set(y,v);
    471             break;
    472           }
    473         }
    474       }
    475   }
    476    
    477   template <typename Graph>
    478   int MaxMatching<Graph>::size() const {
    479     int s=0;
    480     for(NodeIt v(g); v!=INVALID; ++v) {
    481       if ( _mate[v]!=INVALID ) {
    482         ++s;
    483       }
    484     }
    485     return s/2;
    486   }
    487 
    488   template <typename Graph>
    489   void MaxMatching<Graph>::resetMatching() {
    490     for(NodeIt v(g); v!=INVALID; ++v)
    491       _mate.set(v,INVALID);     
    492478  }
    493479
Note: See TracChangeset for help on using the changeset viewer.