COIN-OR::LEMON - Graph Library

Changeset 218:5964f1c64ca1 in lemon-0.x for src/work/johanna/kruskal.h


Ignore:
Timestamp:
03/20/04 18:01:45 (18 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@314
Message:

unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort

nem tul elegans megoldas...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/johanna/kruskal.h

    r150 r218  
    88namespace hugo {
    99
    10   template <typename EdgeCostPair> static
    11   bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
    12     return a.second < b.second;
    13   }
     10
     11  template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
     12  class MinCostTreeKruskal
     13  {
     14
     15    typedef typename Graph::EdgeIt EdgeIt;
     16    typedef typename Graph::Edge Edge;
     17
     18  public:
     19    typedef typename EdgeCostMap::ValueType EdgeCost;
     20    typedef std::pair<Edge, EdgeCost> EdgeCostPair;
     21    typedef std::vector<EdgeCostPair> EdgeCostVector;
     22   
     23  private:
     24    Graph const &G;
     25    EdgeCostMap const &costmap;
     26    EdgeBoolMap& treemap;
     27   
     28    //template <typename EdgeCostPair>
     29    class comparePair {
     30    public:
     31      bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
     32        return a.second < b.second;
     33      }
     34    };
     35
     36  public:
    1437
    1538
    16   template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
     39    MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap,
     40                       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap),
     41                                                treemap(_treemap) {}
     42 
    1743
    18   typename EdgeDoubleMap::ValueType
    19   MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap,
    20                      EdgeBoolMap& treemap)
    21   {
     44    EdgeCost run()
     45    {
     46     EdgeCostVector rank;
     47     for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
     48        rank.push_back(make_pair(e, costmap.get(e)));
     49      }
     50     
     51      std::sort(rank.begin(), rank.end(), comparePair());
     52
     53      return run(rank);
    2254   
    23     typedef typename EdgeDoubleMap::ValueType EDouble;
    24     typedef typename Graph::EachEdgeIt EachEdgeIt;
    25     typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
    26 
    27 
    28     typedef std::vector<EdgeCostPair> EdgeCostVector;
    29     EdgeCostVector rank;
    30 
    31     for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
    32       rank.push_back(make_pair(e, costmap.get(e)));
    3355    }
    3456
    35    
    36     std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
     57    EdgeCost run(EdgeCostVector const &rank)
     58    {
     59      typedef typename Graph::NodeMap<int> NodeIntMap;
     60      typedef typename Graph::Node Node;
     61      NodeIntMap comp_map(G, -1);
     62      UnionFind<Node,NodeIntMap> uf(comp_map);
     63     
     64      EdgeCost tot_cost = 0;
     65      for (typename EdgeCostVector::const_iterator p = rank.begin();
     66           p!=rank.end(); ++p ) {
     67        if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
     68          treemap.set(p->first, true);
     69          tot_cost += p->second;
     70        }
     71        else {
     72          treemap.set(p->first, false);
     73        }
     74      }
     75      return tot_cost;
    3776
    38     typedef typename Graph::NodeMap<int> NodeIntMap;
    39     typedef typename Graph::NodeIt NodeIt;
    40     NodeIntMap comp_map(G, -1);
    41     UnionFind<NodeIt,NodeIntMap> uf(comp_map);
     77    }
    4278
    43     EDouble tot_cost = 0;
    44     for (typename EdgeCostVector::iterator p = rank.begin();
    45          p!=rank.end(); ++p ) {
    46       if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
    47         treemap.set(p->first, true);
    48         tot_cost += p->second;
    49       }
    50       else {
    51         treemap.set(p->first, false);
    52       }
    53     }
    54     return tot_cost;
    55   }
     79  };
    5680
    5781
Note: See TracChangeset for help on using the changeset viewer.