Changeset 218:5964f1c64ca1 in lemon0.x for src/work/johanna/kruskal.h
 Timestamp:
 03/20/04 18:01:45 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@314
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/johanna/kruskal.h
r150 r218 8 8 namespace hugo { 9 9 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: 14 37 15 38 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 17 43 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); 22 54 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)));33 55 } 34 56 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; 37 76 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 } 42 78 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 }; 56 80 57 81
Note: See TracChangeset
for help on using the changeset viewer.