1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/johanna/.cvsignore Wed Mar 03 19:16:48 2004 +0000
1.3 @@ -0,0 +1,2 @@
1.4 +.depend
1.5 +kruskal_test
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/johanna/Makefile Wed Mar 03 19:16:48 2004 +0000
2.3 @@ -0,0 +1,4 @@
2.4 +BINARIES = kruskal_test
2.5 +INCLUDEDIRS= -I. -I.. -I../../include
2.6 +include ../makefile
2.7 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/johanna/kruskal.h Wed Mar 03 19:16:48 2004 +0000
3.3 @@ -0,0 +1,60 @@
3.4 +// -*- c++ -*- //
3.5 +#ifndef HUGO_KRUSKAL_H
3.6 +#define HUGO_KRUSKAL_H
3.7 +
3.8 +#include "unionfind.h"
3.9 +#include <algorithm>
3.10 +
3.11 +namespace hugo {
3.12 +
3.13 + template <typename EdgeCostPair> static
3.14 + bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
3.15 + return a.second < b.second;
3.16 + }
3.17 +
3.18 +
3.19 + template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
3.20 +
3.21 + typename EdgeDoubleMap::ValueType
3.22 + MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap,
3.23 + EdgeBoolMap& treemap)
3.24 + {
3.25 +
3.26 + typedef typename EdgeDoubleMap::ValueType EDouble;
3.27 + typedef typename Graph::EachEdgeIt EachEdgeIt;
3.28 + typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
3.29 +
3.30 +
3.31 + typedef std::vector<EdgeCostPair> EdgeCostVector;
3.32 + EdgeCostVector rank;
3.33 +
3.34 + for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
3.35 + rank.push_back(make_pair(e, costmap.get(e)));
3.36 + }
3.37 +
3.38 +
3.39 + std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
3.40 +
3.41 + typedef typename Graph::NodeMap<int> NodeIntMap;
3.42 + typedef typename Graph::NodeIt NodeIt;
3.43 + NodeIntMap comp_map(G, -1);
3.44 + UnionFind<NodeIt,NodeIntMap> uf(comp_map);
3.45 +
3.46 + EDouble tot_cost = 0;
3.47 + for (typename EdgeCostVector::iterator p = rank.begin();
3.48 + p!=rank.end(); ++p ) {
3.49 + if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
3.50 + treemap.set(p->first, true);
3.51 + tot_cost += p->second;
3.52 + }
3.53 + else {
3.54 + treemap.set(p->first, false);
3.55 + }
3.56 + }
3.57 + return tot_cost;
3.58 + }
3.59 +
3.60 +
3.61 +} //namespace hugo
3.62 +
3.63 +#endif //HUGO_KRUSKAL_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/johanna/kruskal_test.cc Wed Mar 03 19:16:48 2004 +0000
4.3 @@ -0,0 +1,63 @@
4.4 +#include <string>
4.5 +#include <iostream>
4.6 +#include <map>
4.7 +
4.8 +#include <kruskal.h>
4.9 +#include <list_graph.hh>
4.10 +
4.11 +
4.12 +using namespace std;
4.13 +using namespace hugo;
4.14 +
4.15 +class string_int_map : public map<string,int> {
4.16 +public:
4.17 + int get(const string &s) {
4.18 + // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
4.19 + // hogy is mukodik ez a map :)
4.20 + if( count(s) == 0 ) {
4.21 + operator[](s) = -1;
4.22 + }
4.23 + return operator[](s);
4.24 + }
4.25 + void set(const string &s, int i) {
4.26 + operator[](s) = i;
4.27 + }
4.28 +};
4.29 +
4.30 +
4.31 +int main() {
4.32 +
4.33 + typedef ListGraph::NodeIt NodeIt;
4.34 + typedef ListGraph::EdgeIt EdgeIt;
4.35 + typedef ListGraph::EachNodeIt EachNodeIt;
4.36 + typedef ListGraph::EachEdgeIt EachEdgeIt;
4.37 +
4.38 + ListGraph G;
4.39 +
4.40 + NodeIt s=G.addNode();
4.41 + NodeIt v1=G.addNode();
4.42 + NodeIt v2=G.addNode();
4.43 + NodeIt v3=G.addNode();
4.44 + NodeIt v4=G.addNode();
4.45 + NodeIt t=G.addNode();
4.46 +
4.47 + G.addEdge(s, v1);
4.48 + G.addEdge(s, v2);
4.49 + G.addEdge(v1, v2);
4.50 + G.addEdge(v2, v1);
4.51 + G.addEdge(v1, v3);
4.52 + G.addEdge(v3, v2);
4.53 + G.addEdge(v2, v4);
4.54 + G.addEdge(v4, v3);
4.55 + G.addEdge(v3, t);
4.56 + G.addEdge(v4, t);
4.57 +
4.58 + ListGraph::EdgeMap<double> edge_cost_map(G, 2);
4.59 + ListGraph::EdgeMap<bool> tree_map(G);
4.60 +
4.61 + double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
4.62 +
4.63 + cout << k0lts << endl;
4.64 +
4.65 + return 0;
4.66 +}
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/johanna/unionfind.h Wed Mar 03 19:16:48 2004 +0000
5.3 @@ -0,0 +1,75 @@
5.4 +// -*- c++ -*- //
5.5 +#ifndef UNION_FIND_H
5.6 +#define UNION_FIND_H
5.7 +
5.8 +#include <vector>
5.9 +#include <utility>
5.10 +
5.11 +namespace hugo {
5.12 +
5.13 + template <typename T, typename TIntMap>
5.14 + class UnionFind {
5.15 +
5.16 + public:
5.17 + typedef T ElementType;
5.18 + typedef std::pair<int,int> PairType;
5.19 +
5.20 + private:
5.21 + std::vector<PairType> data;
5.22 + TIntMap& map;
5.23 +
5.24 + public:
5.25 + UnionFind(TIntMap& m) : map(m) {}
5.26 +
5.27 +
5.28 + int whichComponent(T a)
5.29 + {
5.30 + int comp0 = map.get(a);
5.31 + if (comp0 < 0) {
5.32 + return insertNewElement(a);
5.33 + }
5.34 + int comp = comp0;
5.35 + int next;
5.36 + while ( (next = data[comp].first) != comp) {
5.37 + comp = next;
5.38 + }
5.39 + while ( (next = data[comp0].first) != comp) {
5.40 + data[comp0].first = comp;
5.41 + comp0 = next;
5.42 + }
5.43 +
5.44 + return comp;
5.45 + }
5.46 +
5.47 + int insertNewElement(T a)
5.48 + {
5.49 + int n = data.size();
5.50 + data.push_back(make_pair(n, 1));
5.51 + map.set(a,n);
5.52 + return n;
5.53 + }
5.54 +
5.55 + bool joinComponents(T a, T b)
5.56 + {
5.57 + int ca = whichComponent(a);
5.58 + int cb = whichComponent(b);
5.59 +
5.60 + if ( ca == cb )
5.61 + return false;
5.62 +
5.63 + if ( data[ca].second > data[cb].second ) {
5.64 + data[cb].first = ca;
5.65 + data[ca].second += data[cb].second;
5.66 + }
5.67 + else {
5.68 + data[ca].first = cb;
5.69 + data[cb].second += data[ca].second;
5.70 + }
5.71 + return true;
5.72 + }
5.73 +
5.74 + };
5.75 +
5.76 +} //namespace hugo
5.77 +
5.78 +#endif //UNION_FIND_H