COIN-OR::LEMON - Graph Library

Changeset 2205:c20b0eb92a33 in lemon-0.x for lemon/max_matching.h


Ignore:
Timestamp:
09/06/06 13:17:12 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2930
Message:

UnionFind?
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum?
Changing the interface - more convenient to UnionFind?
Does not based on the stl data structures /it could be disadvantage/

=> does not use singular iterator assignment /not stl conform, but always work/

Just new iterator interface

MaxMatching? + UnionFindTest?
Using new iterator interface instead of the old

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r2042 r2205  
    6666    typedef typename Graph::IncEdgeIt IncEdgeIt;
    6767
    68     typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
     68    typedef typename Graph::template NodeMap<int> UFECrossRef;
     69    typedef UnionFindEnum<Node, UFECrossRef> UFE;
    6970
    7071  public:
     
    122123      //representative elements of UFE blossom) and for the nodes in C
    123124     
    124       typename UFE::MapType blossom_base(g);
     125      UFECrossRef blossom_base(g);
    125126      UFE blossom(blossom_base);
    126       typename UFE::MapType tree_base(g);
     127
     128      UFECrossRef tree_base(g);
    127129      UFE tree(tree_base);
     130
    128131      //If these UFE's would be members of the class then also
    129132      //blossom_base and tree_base should be a member.
     
    550553    }
    551554    Node y=blossom.find(x);
    552     typename UFE::ItemIt it;
    553     for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
    554       if ( position[it] == D ) {
    555         typename UFE::ItemIt b_it;
    556         for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) { 
    557           position.set( b_it ,C);
     555    for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {   
     556      if ( position[tit] == D ) {
     557        for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) { 
     558          position.set( bit ,C);
    558559        }
    559         blossom.eraseClass(it);
    560       } else position.set( it ,C);
     560        blossom.eraseClass(tit);
     561      } else position.set( tit ,C);
    561562    }
    562563    tree.eraseClass(y);
Note: See TracChangeset for help on using the changeset viewer.