Changeset 218:5964f1c64ca1 in lemon-0.x for src/work/johanna
- Timestamp:
- 03/20/04 18:01:45 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@314
- Location:
- src/work/johanna
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/johanna/Makefile
r150 r218 1 1 BINARIES = kruskal_test 2 INCLUDEDIRS= -I. -I.. -I../../include 2 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos} 3 3 include ../makefile 4 4 -
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 -
src/work/johanna/kruskal_test.cc
r150 r218 4 4 5 5 #include <kruskal.h> 6 #include <list_graph.h h>6 #include <list_graph.h> 7 7 8 8 … … 26 26 27 27 28 // Egy olyan "map", ami nem tud semmit, csak a typedef-eket. 29 // Valami elegansabb megoldas kene a Kruskalban... 30 31 template <typename K, typename V> 32 class DummyMap { 33 public: 34 typedef K KeyType; 35 typedef V ValueType; 36 }; 37 28 38 int main() { 29 39 40 typedef ListGraph::Node Node; 41 typedef ListGraph::Edge Edge; 30 42 typedef ListGraph::NodeIt NodeIt; 31 43 typedef ListGraph::EdgeIt EdgeIt; 32 typedef ListGraph::EachNodeIt EachNodeIt;33 typedef ListGraph::EachEdgeIt EachEdgeIt;34 44 35 45 ListGraph G; 36 46 37 Node Its=G.addNode();38 Node Itv1=G.addNode();39 Node Itv2=G.addNode();40 Node Itv3=G.addNode();41 Node Itv4=G.addNode();42 Node Itt=G.addNode();47 Node s=G.addNode(); 48 Node v1=G.addNode(); 49 Node v2=G.addNode(); 50 Node v3=G.addNode(); 51 Node v4=G.addNode(); 52 Node t=G.addNode(); 43 53 44 G.addEdge(s, v1);45 G.addEdge(s, v2);46 G.addEdge(v1, v2);47 G.addEdge(v2, v1);48 G.addEdge(v1, v3);49 G.addEdge(v3, v2);50 G.addEdge(v2, v4);51 G.addEdge(v4, v3);52 G.addEdge(v3, t);53 G.addEdge(v4, t);54 Edge e1 = G.addEdge(s, v1); 55 Edge e2 = G.addEdge(s, v2); 56 Edge e3 = G.addEdge(v1, v2); 57 Edge e4 = G.addEdge(v2, v1); 58 Edge e5 = G.addEdge(v1, v3); 59 Edge e6 = G.addEdge(v3, v2); 60 Edge e7 = G.addEdge(v2, v4); 61 Edge e8 = G.addEdge(v4, v3); 62 Edge e9 = G.addEdge(v3, t); 63 Edge e10 = G.addEdge(v4, t); 54 64 55 ListGraph::EdgeMap<double> edge_cost_map(G, 2); 56 ListGraph::EdgeMap<bool> tree_map(G); 65 typedef ListGraph::EdgeMap<double> ECostMap; 66 typedef ListGraph::EdgeMap<bool> EBoolMap; 67 68 ECostMap edge_cost_map(G, 2); 69 EBoolMap tree_map(G); 57 70 58 double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);71 typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK; 59 72 60 cout << k0lts << endl; 73 MCTK mctk(G, edge_cost_map, tree_map); 74 double k0lts = mctk.run(); 75 76 cout << "Uniform 2-es koltseggel: " << k0lts << endl; 77 78 // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol: 79 typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2; 80 MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map); 81 MCTK2::EdgeCostVector ecv; 82 ecv.push_back(make_pair(e1, 10)); 83 ecv.push_back(make_pair(e2, 9)); 84 ecv.push_back(make_pair(e3, 8)); 85 ecv.push_back(make_pair(e4, 7)); 86 ecv.push_back(make_pair(e5, 6)); 87 ecv.push_back(make_pair(e6, 5)); 88 ecv.push_back(make_pair(e7, 4)); 89 ecv.push_back(make_pair(e8, 3)); 90 ecv.push_back(make_pair(e9, 2)); 91 ecv.push_back(make_pair(e10, 1)); 92 93 k0lts = mctk2.run(ecv); 94 cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = " 95 << k0lts << endl; 96 61 97 62 98 return 0; -
src/work/johanna/unionfind.h
r150 r218 1 1 // -*- c++ -*- // 2 #ifndef UNION_FIND_H3 #define UNION_FIND_H2 #ifndef HUGO_UNION_FIND_H 3 #define HUGO_UNION_FIND_H 4 4 5 5 #include <vector> … … 69 69 } 70 70 71 int componentSize(T a) 72 { 73 int ca = whichComponent(a); 74 return data[ca].second; 75 } 76 71 77 }; 72 78 73 79 } //namespace hugo 74 80 75 #endif // UNION_FIND_H81 #endif //HUGO_UNION_FIND_H
Note: See TracChangeset
for help on using the changeset viewer.