COIN-OR::LEMON - Graph Library

Changeset 2205:c20b0eb92a33 in lemon-0.x for lemon/kruskal.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/kruskal.h

    r2111 r2205  
    2525#include <lemon/bits/utility.h>
    2626#include <lemon/bits/traits.h>
     27#include <lemon/time_measure.h>
     28#include <iostream>
    2729
    2830///\ingroup spantree
     
    118120    typedef typename GR::Node Node;
    119121
    120     NodeIntMap comp(g, -1);
    121     UnionFind<Node,NodeIntMap> uf(comp);
     122    Timer timer;
     123    NodeIntMap comp(g);
     124    UnionFind<Node,NodeIntMap> uf(comp);
     125    for (typename GR::NodeIt it(g); it != INVALID; ++it) {
     126      uf.insert(it);
     127    }
    122128     
    123129    EdgeCost tot_cost = 0;
     
    133139      }
    134140    }
     141    std::cout << timer << std::endl;
    135142    return tot_cost;
    136143  }
Note: See TracChangeset for help on using the changeset viewer.