1.1 --- a/src/work/johanna/Makefile Sat Mar 20 16:13:19 2004 +0000
1.2 +++ b/src/work/johanna/Makefile Sat Mar 20 17:01:45 2004 +0000
1.3 @@ -1,4 +1,4 @@
1.4 BINARIES = kruskal_test
1.5 -INCLUDEDIRS= -I. -I.. -I../../include
1.6 +INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
1.7 include ../makefile
1.8
2.1 --- a/src/work/johanna/kruskal.h Sat Mar 20 16:13:19 2004 +0000
2.2 +++ b/src/work/johanna/kruskal.h Sat Mar 20 17:01:45 2004 +0000
2.3 @@ -7,52 +7,76 @@
2.4
2.5 namespace hugo {
2.6
2.7 - template <typename EdgeCostPair> static
2.8 - bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
2.9 - return a.second < b.second;
2.10 - }
2.11
2.12 + template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
2.13 + class MinCostTreeKruskal
2.14 + {
2.15
2.16 - template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
2.17 + typedef typename Graph::EdgeIt EdgeIt;
2.18 + typedef typename Graph::Edge Edge;
2.19
2.20 - typename EdgeDoubleMap::ValueType
2.21 - MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap,
2.22 - EdgeBoolMap& treemap)
2.23 - {
2.24 + public:
2.25 + typedef typename EdgeCostMap::ValueType EdgeCost;
2.26 + typedef std::pair<Edge, EdgeCost> EdgeCostPair;
2.27 + typedef std::vector<EdgeCostPair> EdgeCostVector;
2.28
2.29 - typedef typename EdgeDoubleMap::ValueType EDouble;
2.30 - typedef typename Graph::EachEdgeIt EachEdgeIt;
2.31 - typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
2.32 + private:
2.33 + Graph const &G;
2.34 + EdgeCostMap const &costmap;
2.35 + EdgeBoolMap& treemap;
2.36 +
2.37 + //template <typename EdgeCostPair>
2.38 + class comparePair {
2.39 + public:
2.40 + bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
2.41 + return a.second < b.second;
2.42 + }
2.43 + };
2.44
2.45 + public:
2.46
2.47 - typedef std::vector<EdgeCostPair> EdgeCostVector;
2.48 - EdgeCostVector rank;
2.49
2.50 - for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
2.51 - rank.push_back(make_pair(e, costmap.get(e)));
2.52 + MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap,
2.53 + EdgeBoolMap& _treemap) : G(_G), costmap(_costmap),
2.54 + treemap(_treemap) {}
2.55 +
2.56 +
2.57 + EdgeCost run()
2.58 + {
2.59 + EdgeCostVector rank;
2.60 + for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
2.61 + rank.push_back(make_pair(e, costmap.get(e)));
2.62 + }
2.63 +
2.64 + std::sort(rank.begin(), rank.end(), comparePair());
2.65 +
2.66 + return run(rank);
2.67 +
2.68 }
2.69
2.70 -
2.71 - std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
2.72 + EdgeCost run(EdgeCostVector const &rank)
2.73 + {
2.74 + typedef typename Graph::NodeMap<int> NodeIntMap;
2.75 + typedef typename Graph::Node Node;
2.76 + NodeIntMap comp_map(G, -1);
2.77 + UnionFind<Node,NodeIntMap> uf(comp_map);
2.78 +
2.79 + EdgeCost tot_cost = 0;
2.80 + for (typename EdgeCostVector::const_iterator p = rank.begin();
2.81 + p!=rank.end(); ++p ) {
2.82 + if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
2.83 + treemap.set(p->first, true);
2.84 + tot_cost += p->second;
2.85 + }
2.86 + else {
2.87 + treemap.set(p->first, false);
2.88 + }
2.89 + }
2.90 + return tot_cost;
2.91
2.92 - typedef typename Graph::NodeMap<int> NodeIntMap;
2.93 - typedef typename Graph::NodeIt NodeIt;
2.94 - NodeIntMap comp_map(G, -1);
2.95 - UnionFind<NodeIt,NodeIntMap> uf(comp_map);
2.96 + }
2.97
2.98 - EDouble tot_cost = 0;
2.99 - for (typename EdgeCostVector::iterator p = rank.begin();
2.100 - p!=rank.end(); ++p ) {
2.101 - if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
2.102 - treemap.set(p->first, true);
2.103 - tot_cost += p->second;
2.104 - }
2.105 - else {
2.106 - treemap.set(p->first, false);
2.107 - }
2.108 - }
2.109 - return tot_cost;
2.110 - }
2.111 + };
2.112
2.113
2.114 } //namespace hugo
3.1 --- a/src/work/johanna/kruskal_test.cc Sat Mar 20 16:13:19 2004 +0000
3.2 +++ b/src/work/johanna/kruskal_test.cc Sat Mar 20 17:01:45 2004 +0000
3.3 @@ -3,7 +3,7 @@
3.4 #include <map>
3.5
3.6 #include <kruskal.h>
3.7 -#include <list_graph.hh>
3.8 +#include <list_graph.h>
3.9
3.10
3.11 using namespace std;
3.12 @@ -25,39 +25,75 @@
3.13 };
3.14
3.15
3.16 +// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
3.17 +// Valami elegansabb megoldas kene a Kruskalban...
3.18 +
3.19 +template <typename K, typename V>
3.20 +class DummyMap {
3.21 +public:
3.22 + typedef K KeyType;
3.23 + typedef V ValueType;
3.24 +};
3.25 +
3.26 int main() {
3.27
3.28 + typedef ListGraph::Node Node;
3.29 + typedef ListGraph::Edge Edge;
3.30 typedef ListGraph::NodeIt NodeIt;
3.31 typedef ListGraph::EdgeIt EdgeIt;
3.32 - typedef ListGraph::EachNodeIt EachNodeIt;
3.33 - typedef ListGraph::EachEdgeIt EachEdgeIt;
3.34
3.35 ListGraph G;
3.36
3.37 - NodeIt s=G.addNode();
3.38 - NodeIt v1=G.addNode();
3.39 - NodeIt v2=G.addNode();
3.40 - NodeIt v3=G.addNode();
3.41 - NodeIt v4=G.addNode();
3.42 - NodeIt t=G.addNode();
3.43 + Node s=G.addNode();
3.44 + Node v1=G.addNode();
3.45 + Node v2=G.addNode();
3.46 + Node v3=G.addNode();
3.47 + Node v4=G.addNode();
3.48 + Node t=G.addNode();
3.49
3.50 - G.addEdge(s, v1);
3.51 - G.addEdge(s, v2);
3.52 - G.addEdge(v1, v2);
3.53 - G.addEdge(v2, v1);
3.54 - G.addEdge(v1, v3);
3.55 - G.addEdge(v3, v2);
3.56 - G.addEdge(v2, v4);
3.57 - G.addEdge(v4, v3);
3.58 - G.addEdge(v3, t);
3.59 - G.addEdge(v4, t);
3.60 + Edge e1 = G.addEdge(s, v1);
3.61 + Edge e2 = G.addEdge(s, v2);
3.62 + Edge e3 = G.addEdge(v1, v2);
3.63 + Edge e4 = G.addEdge(v2, v1);
3.64 + Edge e5 = G.addEdge(v1, v3);
3.65 + Edge e6 = G.addEdge(v3, v2);
3.66 + Edge e7 = G.addEdge(v2, v4);
3.67 + Edge e8 = G.addEdge(v4, v3);
3.68 + Edge e9 = G.addEdge(v3, t);
3.69 + Edge e10 = G.addEdge(v4, t);
3.70
3.71 - ListGraph::EdgeMap<double> edge_cost_map(G, 2);
3.72 - ListGraph::EdgeMap<bool> tree_map(G);
3.73 + typedef ListGraph::EdgeMap<double> ECostMap;
3.74 + typedef ListGraph::EdgeMap<bool> EBoolMap;
3.75 +
3.76 + ECostMap edge_cost_map(G, 2);
3.77 + EBoolMap tree_map(G);
3.78
3.79 - double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
3.80 + typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
3.81
3.82 - cout << k0lts << endl;
3.83 + MCTK mctk(G, edge_cost_map, tree_map);
3.84 + double k0lts = mctk.run();
3.85 +
3.86 + cout << "Uniform 2-es koltseggel: " << k0lts << endl;
3.87 +
3.88 + // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
3.89 + typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
3.90 + MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
3.91 + MCTK2::EdgeCostVector ecv;
3.92 + ecv.push_back(make_pair(e1, 10));
3.93 + ecv.push_back(make_pair(e2, 9));
3.94 + ecv.push_back(make_pair(e3, 8));
3.95 + ecv.push_back(make_pair(e4, 7));
3.96 + ecv.push_back(make_pair(e5, 6));
3.97 + ecv.push_back(make_pair(e6, 5));
3.98 + ecv.push_back(make_pair(e7, 4));
3.99 + ecv.push_back(make_pair(e8, 3));
3.100 + ecv.push_back(make_pair(e9, 2));
3.101 + ecv.push_back(make_pair(e10, 1));
3.102 +
3.103 + k0lts = mctk2.run(ecv);
3.104 + cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
3.105 + << k0lts << endl;
3.106 +
3.107
3.108 return 0;
3.109 }
4.1 --- a/src/work/johanna/unionfind.h Sat Mar 20 16:13:19 2004 +0000
4.2 +++ b/src/work/johanna/unionfind.h Sat Mar 20 17:01:45 2004 +0000
4.3 @@ -1,6 +1,6 @@
4.4 // -*- c++ -*- //
4.5 -#ifndef UNION_FIND_H
4.6 -#define UNION_FIND_H
4.7 +#ifndef HUGO_UNION_FIND_H
4.8 +#define HUGO_UNION_FIND_H
4.9
4.10 #include <vector>
4.11 #include <utility>
4.12 @@ -68,8 +68,14 @@
4.13 return true;
4.14 }
4.15
4.16 + int componentSize(T a)
4.17 + {
4.18 + int ca = whichComponent(a);
4.19 + return data[ca].second;
4.20 + }
4.21 +
4.22 };
4.23
4.24 } //namespace hugo
4.25
4.26 -#endif //UNION_FIND_H
4.27 +#endif //HUGO_UNION_FIND_H