# HG changeset patch # User alpar # Date 1094490720 0 # Node ID e9fbc747ca478f676ca4fc12771d0955d0c933ad # Parent ea5ae5266285f2235ff1e6ad1a95f28dfd1044c9 Kruskal alg. (src/hugo/kruskal.h, src/test/kruskal_test.cc) is (almost) done. - Some input adaptor is still missing. - The class and function names should be revised. - Docs still needs some improvement. diff -r ea5ae5266285 -r e9fbc747ca47 src/hugo/Makefile.am --- a/src/hugo/Makefile.am Mon Sep 06 13:47:54 2004 +0000 +++ b/src/hugo/Makefile.am Mon Sep 06 17:12:00 2004 +0000 @@ -11,6 +11,7 @@ full_graph.h \ graph_wrapper.h \ invalid.h \ + kruskal.h \ list_graph.h \ map_defines.h \ map_registry.h \ diff -r ea5ae5266285 -r e9fbc747ca47 src/hugo/kruskal.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/kruskal.h Mon Sep 06 17:12:00 2004 +0000 @@ -0,0 +1,304 @@ +// -*- c++ -*- // +#ifndef HUGO_KRUSKAL_H +#define HUGO_KRUSKAL_H + +#include +#include + +/** +@defgroup spantree Minimum Cost Spanning Tree Algorithms +@ingroup galgs +\brief This group containes the algorithms for finding a minimum cost spanning +tree in a graph + +This group containes the algorithms for finding a minimum cost spanning +tree in a graph +*/ + +///\ingroup spantree +///\file +///\brief Kruskal's algorithm to compute a minimum cost tree +/// +///Kruskal's algorithm to compute a minimum cost tree. + +namespace hugo { + + /// \addtogroup spantree + /// @{ + + /// Kruskal's algorithm to find a minimum cost tree of a graph. + + /// This function runs Kruskal's algorithm to find a minimum cost tree. + /// \param G The graph the algorithm runs on. The algorithm considers the + /// graph to be undirected, the direction of the edges are not used. + /// + /// \param in This object is used to describe the edge costs. It must + /// be an STL compatible 'Forward Container' + /// with std::pair as its value_type, + /// where X is the type of the costs. It must contain every edge in + /// cost-ascending order. + ///\par + /// For the sake of simplicity, there is a helper class KruskalMapInput, + /// which converts a + /// simple edge map to an input of this form. Alternatively, you can use + /// the function \ref kruskalEdgeMap to compute the minimum cost tree if + /// the edge costs are given by an edge map. + /// + /// \retval out This must be a writable \c bool edge map. + /// After running the algorithm + /// this will contain the found minimum cost spanning tree: the value of an + /// edge will be set to \c true if it belongs to the tree, otherwise it will + /// be set to \c false. The value of each edge will be set exactly once. + /// + /// \return The cost of the found tree. + + template + typename InputEdgeOrder::value_type::second_type + kruskal(Graph const& G, InputEdgeOrder const& in, + OutBoolMap& out) + { + typedef typename InputEdgeOrder::value_type::second_type EdgeCost; + typedef typename Graph::template NodeMap NodeIntMap; + typedef typename Graph::Node Node; + + NodeIntMap comp(G, -1); + UnionFind uf(comp); + + EdgeCost tot_cost = 0; + for (typename InputEdgeOrder::const_iterator p = in.begin(); + p!=in.end(); ++p ) { + if ( uf.join(G.head((*p).first), + G.tail((*p).first)) ) { + out.set((*p).first, true); + tot_cost += (*p).second; + } + else { + out.set((*p).first, false); + } + } + return tot_cost; + } + + /* A work-around for running Kruskal with const-reference bool maps... */ + + ///\bug What is this? Or why doesn't it works? + /// + template + class NonConstMapWr { + const Map &m; + public: + typedef typename Map::ValueType ValueType; + + NonConstMapWr(const Map &_m) : m(_m) {} + + template + void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } + }; + + template + inline + typename InputEdgeOrder::ValueType + kruskal(Graph const& G, InputEdgeOrder const& edges, + OutBoolMap const& out_map) + { + NonConstMapWr map_wr(out_map); + return kruskal(G, edges, map_wr); + } + + /* ** ** Input-objects ** ** */ + + /// Kruskal input source. + + /// Kruskal input source. + /// + /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead. + /// + /// \sa makeKruskalMapInput() + /// + ///\param Graph The type of the graph the algorithm runs on. + ///\param Map An edge map containing the cost of the edges. + ///\par + ///The cost type can be any type satisfying + ///the STL 'LessThan comparable' + ///concept if it also has an operator+() implemented. (It is necessary for + ///computing the total cost of the tree). + /// + template + class KruskalMapInput + : public std::vector< std::pair > { + + public: + typedef std::vector< std::pair > Parent; + typedef typename Parent::value_type value_type; + + private: + class comparePair { + public: + bool operator()(const value_type& a, + const value_type& b) { + return a.second < b.second; + } + }; + + public: + + void sort() { + std::sort(this->begin(), this->end(), comparePair()); + } + + KruskalMapInput(Graph const& G, Map const& m) { + typedef typename Graph::EdgeIt EdgeIt; + + this->clear(); + for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e])); + sort(); + } + }; + + /// Creates a KruskalMapInput object for \ref kruskal() + + /// It makes is easier to use + /// \ref KruskalMapInput by making it unnecessary + /// to explicitly give the type of the parameters. + /// + /// In most cases you possibly + /// want to use the function kruskalEdgeMap() instead. + /// + ///\param G The type of the graph the algorithm runs on. + ///\param m An edge map containing the cost of the edges. + ///\par + ///The cost type can be any type satisfying the + ///STL 'LessThan Comparable' + ///concept if it also has an operator+() implemented. (It is necessary for + ///computing the total cost of the tree). + /// + ///\return An appropriate input source for \ref kruskal(). + /// + template + inline + KruskalMapInput makeKruskalMapInput(const Graph &G,const Map &m) + { + return KruskalMapInput(G,m); + } + + + /* ** ** Output-objects: simple writable bool maps** ** */ + + /// A writable bool-map that makes a sequence of "true" keys + + /// A writable bool-map that creates a sequence out of keys that receives + /// the value "true". + /// \warning Not a regular property map, as it doesn't know its KeyType + /// \bug Missing documentation. + /// \todo This class may be of wider usage, therefore it could move to + /// maps.h + template + class SequenceOutput { + mutable Iterator it; + + public: + typedef bool ValueType; + + SequenceOutput(Iterator const &_it) : it(_it) {} + + template + void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } + }; + + template + inline + SequenceOutput + makeSequenceOutput(Iterator it) { + return SequenceOutput(it); + } + + /* ** ** Wrapper funtions ** ** */ + + + /// \brief Wrapper function to kruskal(). + /// Input is from an edge map, output is a plain bool map. + /// + /// Wrapper function to kruskal(). + /// Input is from an edge map, output is a plain bool map. + /// + ///\param G The type of the graph the algorithm runs on. + ///\param in An edge map containing the cost of the edges. + ///\par + ///The cost type can be any type satisfying the + ///STL 'LessThan Comparable' + ///concept if it also has an operator+() implemented. (It is necessary for + ///computing the total cost of the tree). + /// + /// \retval out This must be a writable \c bool edge map. + /// After running the algorithm + /// this will contain the found minimum cost spanning tree: the value of an + /// edge will be set to \c true if it belongs to the tree, otherwise it will + /// be set to \c false. The value of each edge will be set exactly once. + /// + /// \return The cost of the found tree. + + + template + inline + typename EdgeCostMap::ValueType + kruskalEdgeMap(Graph const& G, + EdgeCostMap const& in, + RetEdgeBoolMap &out) { + return kruskal(G, + KruskalMapInput(G,in), + out); + } + + /// \brief Wrapper function to kruskal(). + /// Input is from an edge map, output is an STL Sequence. + /// + /// Wrapper function to kruskal(). + /// Input is from an edge map, output is an STL Sequence. + /// + ///\param G The type of the graph the algorithm runs on. + ///\param in An edge map containing the cost of the edges. + ///\par + ///The cost type can be any type satisfying the + ///STL 'LessThan Comparable' + ///concept if it also has an operator+() implemented. (It is necessary for + ///computing the total cost of the tree). + /// + /// \retval out This must be an iteraror of an STL Container with + /// Graph::Edge as its value_type. + /// The algorithm copies the elements of the found tree into this sequence. + /// For example, if we know that the spanning tree of the graph \c G has + /// say 53 edges then + /// we can put its edges into a vector \c tree with a code like this. + /// \code + /// std::vector tree(53); + /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin()); + /// \endcode + /// Or if we don't know in advance the size of the tree, we can write this. + /// \code + /// std::vector tree; + /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree)); + /// \endcode + /// + /// \return The cost of the found tree. + /// + /// \bug its name does not follow the coding style. + template + inline + typename EdgeCostMap::ValueType + kruskalEdgeMap_IteratorOut(const Graph& G, + const EdgeCostMap& in, + RetIterator out) + { + SequenceOutput _out(out); + return kruskal(G, + KruskalMapInput(G, in), + _out); + } + + /// @} + +} //namespace hugo + +#endif //HUGO_KRUSKAL_H diff -r ea5ae5266285 -r e9fbc747ca47 src/hugo/unionfind.h --- a/src/hugo/unionfind.h Mon Sep 06 13:47:54 2004 +0000 +++ b/src/hugo/unionfind.h Mon Sep 06 17:12:00 2004 +0000 @@ -32,9 +32,14 @@ * only four methods: join (union), find, insert and size. * For more features see the \ref UnionFindEnum class. * + * It is primarily used in Kruskal algorithm for finding minimal + * cost spanning tree in a graph. + * \sa kruskal() + * * \pre The elements are automatically added only if the map * given to the constructor was filled with -1's. Otherwise you * need to add all the elements by the \ref insert() method. + * \bug It is not clear what the constructor parameter is used for. */ template diff -r ea5ae5266285 -r e9fbc747ca47 src/test/Makefile.am --- a/src/test/Makefile.am Mon Sep 06 13:47:54 2004 +0000 +++ b/src/test/Makefile.am Mon Sep 06 17:12:00 2004 +0000 @@ -2,13 +2,20 @@ noinst_HEADERS = test_tools.h graph_test.h -check_PROGRAMS = test_tools_pass test_tools_fail \ +check_PROGRAMS = \ + bfs_test \ + dfs_test \ + dijkstra_test \ + error_test \ graph_test \ - dijkstra_test bfs_test dfs_test \ - minlengthpaths_test mincostflows_test \ - unionfind_test xy_test \ + kruskal_test \ + mincostflows_test \ + minlengthpaths_test \ + test_tools_fail \ + test_tools_pass \ time_measure_test \ - error_test + unionfind_test \ + xy_test TESTS = $(check_PROGRAMS) @@ -19,6 +26,7 @@ dijkstra_test_SOURCES = dijkstra_test.cc error_test_SOURCES = error_test.cc graph_test_SOURCES = graph_test.cc +kruskal_test_SOURCES = kruskal_test.cc mincostflows_test_SOURCES = mincostflows_test.cc minlengthpaths_test_SOURCES = minlengthpaths_test.cc time_measure_test_SOURCES = time_measure_test.cc diff -r ea5ae5266285 -r e9fbc747ca47 src/test/kruskal_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/kruskal_test.cc Mon Sep 06 17:12:00 2004 +0000 @@ -0,0 +1,94 @@ +#include +#include + +#include "test_tools.h" +#include +#include +#include +#include +#include + + +using namespace std; +using namespace hugo; + +void checkCompileKruskal() +{ + skeleton::WriteMap w; + + kruskalEdgeMap(skeleton::StaticGraphSkeleton(), + skeleton::ReadMap(), + w); +} + +int main() { + + typedef ListGraph::Node Node; + typedef ListGraph::Edge Edge; + typedef ListGraph::NodeIt NodeIt; + typedef ListGraph::EdgeIt EdgeIt; + + ListGraph G; + + Node s=G.addNode(); + Node v1=G.addNode(); + Node v2=G.addNode(); + Node v3=G.addNode(); + Node v4=G.addNode(); + Node t=G.addNode(); + + Edge e1 = G.addEdge(s, v1); + Edge e2 = G.addEdge(s, v2); + Edge e3 = G.addEdge(v1, v2); + Edge e4 = G.addEdge(v2, v1); + Edge e5 = G.addEdge(v1, v3); + Edge e6 = G.addEdge(v3, v2); + Edge e7 = G.addEdge(v2, v4); + Edge e8 = G.addEdge(v4, v3); + Edge e9 = G.addEdge(v3, t); + Edge e10 = G.addEdge(v4, t); + + typedef ListGraph::EdgeMap ECostMap; + typedef ListGraph::EdgeMap EBoolMap; + + ECostMap edge_cost_map(G, 2); + EBoolMap tree_map(G); + + + //Test with const map. + check(kruskalEdgeMap(G, ConstMap(2), tree_map)==10, + "Total cost should be 10"); + //Test with a edge map (filled with uniform costs). + check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10, + "Total cost should be 10"); + + edge_cost_map.set(e1, -10); + edge_cost_map.set(e2, -9); + edge_cost_map.set(e3, -8); + edge_cost_map.set(e4, -7); + edge_cost_map.set(e5, -6); + edge_cost_map.set(e6, -5); + edge_cost_map.set(e7, -4); + edge_cost_map.set(e8, -3); + edge_cost_map.set(e9, -2); + edge_cost_map.set(e10, -1); + + vector tree_edge_vec; + + //Test with a edge map and inserter. + check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, + back_inserter(tree_edge_vec)) + ==-31, + "Total cost should be -31."); + + check(tree_edge_vec.size()==5,"The tree should have 5 edges."); + + check(tree_edge_vec[0]==e1 && + tree_edge_vec[1]==e2 && + tree_edge_vec[2]==e5 && + tree_edge_vec[3]==e7 && + tree_edge_vec[4]==e9, + "Wrong tree."); + + return 0; +} diff -r ea5ae5266285 -r e9fbc747ca47 src/work/johanna/kruskal.h --- a/src/work/johanna/kruskal.h Mon Sep 06 13:47:54 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,311 +0,0 @@ -// -*- c++ -*- // -#ifndef HUGO_KRUSKAL_H -#define HUGO_KRUSKAL_H - -#include -#include - -/** -@defgroup spantree Minimum Cost Spanning Tree Algorithms -\brief This group containes the algorithms for finding a minimum cost spanning -tree in a graph -@ingroup galgs -*/ - -///\ingroup spantree -///\file -///\brief Kruskal's algorithm to compute a minimum cost tree - -namespace hugo { - - /// \addtogroup spantree - /// @{ - - /// Kruskal's algorithm to find a minimum cost tree of a graph. - - /// This function runs Kruskal's algorithm to find a minimum cost tree. - /// \param G The graph the algorithm runs on. - /// \param in This object is used to describe the edge costs. It must - /// be an STL 'forward container' - /// with value_type std::pair , - /// where X is the type of the costs. It must contain every edge in - /// cost-ascending order. - /// \retval out This must be a writeable EdgeMap. After running the algorithm - /// this will contain the found minimum cost spanning tree: the value of an - /// edge will be set to \c true if it belongs to the tree, otherwise it will - /// be set to \c false. The value of each edge will be set exactly once.\n - /// For the sake of simplicity, there is a helper class KruskalPairVec, - /// which converts a - /// simple EdgeMap to an input of this form. Alternatively, you can use - /// the function \ref kruskalEdgeMap to compute the minimum cost tree if - /// the edge costs are given by an EdgeMap. - /// \return The cost of the found tree. - - template - typename InputEdgeOrder::value_type::second_type - kruskal(Graph const& G, InputEdgeOrder const& in, - OutBoolMap& out) - { - typedef typename InputEdgeOrder::value_type::second_type EdgeCost; - typedef typename Graph::template NodeMap NodeIntMap; - typedef typename Graph::Node Node; - - NodeIntMap comp(G, -1); - UnionFind uf(comp); - - EdgeCost tot_cost = 0; - for (typename InputEdgeOrder::const_iterator p = in.begin(); - p!=in.end(); ++p ) { - if ( uf.join(G.head((*p).first), - G.tail((*p).first)) ) { - out.set((*p).first, true); - tot_cost += (*p).second; - } - else { - out.set((*p).first, false); - } - } - return tot_cost; - } - - /* A work-around for running Kruskal with const-reference bool maps... */ - - template - class NonConstMapWr { - const Map &m; - public: - typedef typename Map::ValueType ValueType; - - NonConstMapWr(const Map &_m) : m(_m) {} - - template - void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } - }; - - template - inline - typename InputEdgeOrder::ValueType - kruskal(Graph const& G, InputEdgeOrder const& edges, - OutBoolMap const& out_map) - { - NonConstMapWr map_wr(out_map); - return kruskal(G, edges, map_wr); - } - - - /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */ - - /// A writable bool-map that makes a sequence of "true" keys - - /// A writable bool-map that creates a sequence out of keys that receives - /// the value "true". - /// \warning Not a regular property map, as it doesn't know its KeyType - - template - class SequenceOutput { - mutable Iterator it; - - public: - typedef bool ValueType; - - SequenceOutput(Iterator const &_it) : it(_it) {} - - template - void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } - }; - - template - inline - SequenceOutput - makeSequenceOutput(Iterator it) { - return SequenceOutput(it); - } - - /* ** ** InputSource -ok ** ** */ - - /// Kruskal input source. - - /// Kruskal input source. - /// - template - class KruskalMapInput - : public std::vector< std::pair > { - - public: - typedef std::vector< std::pair > Parent; - typedef typename Parent::value_type value_type; -// typedef Key KeyType; -// typedef Val ValueType; -// typedef std::pair PairType; -// typedef typename Parent::iterator iterator; -// typedef typename Parent::const_iterator const_iterator; - - private: - class comparePair { - public: - bool operator()(const value_type& a, - const value_type& b) { - return a.second < b.second; - } - }; - - public: - - // FIXME: kell ez? - // KruskalMapInput(Parent const& p) : Parent(p) {} - - void sort() { - std::sort(this->begin(), this->end(), comparePair()); - } - - // FIXME: nem nagyon illik ez ide... - KruskalMapInput(Graph const& G, Map const& m) { - typedef typename Graph::EdgeIt EdgeIt; - - this->clear(); - for(EdgeIt e(G);G.valid(e);G.next(e)) { - // for (EdgeIt e=G.template first(); G.valid(e); G.next(e)) { - push_back(make_pair(e, m[e])); - } - sort(); - } - -// Key const& first(const_iterator i) const { return i->first; } -// Key& first(iterator i) { return i->first; } - -// Val const& second(const_iterator i) const { return i->second; } -// Val& second(iterator i) { return i->second; } - }; - - -// template -// class KruskalMapVec { -// public: - -// typedef std::pair value_type; - -// typedef std::vector Container; -// Container container; -// std::vector container -// const Map &m; - - -// class iterator -// { -// Container::iterator i; -// public: -// iterator &operator ++() {++i;return *this;} -// valuetype operator *() {return value_type(container(i),m[container(i)]);} -// bool operator==(iterator b) {return i==b.i;} -// iterator() {} -// iterator(Container::iterator _i) i(_i) {} -// }; -// class const_iterator -// { -// Container::const_iterator i; -// public: -// iterator &operator ++() {++i;return *this;} -// valuetype operator *() {return value_type(container(i),m[container(i)]);} -// bool operator==(iterator b) {return i==b.i;} -// const_iterator() {} -// const_iterator(Container::iterator _i) i(_i) {} -// }; - -// iterator begin() { return iterator(container.begin());} -// const_iterator begin() const { return iterator(container.begin());} -// iterator end() { return iterator(container.end());} -// const_iterator end() const { return iterator(container.end());} - -// private: - -// class compareKeys { -// const Map &m; -// public: -// compareKeys(Map const &_m) : m(_m) {} -// bool operator()(KeyType const& a, KeyType const& b) { -// return m[a] < m[b]; -// } -// }; - -// public: - -// KruskalMapVec(Map const& _m) : m(_m) {} - -// void sort() { -// std::sort(begin(), end(), compareKeys(m)); -// } - -// // FIXME: nem nagyon illik ez ide... -// template -// KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { -// typedef typename Graph::EdgeIt EdgeIt; - -// clear(); -// for(EdgeIt e(G);G.valid(e);G.next(e)) { -// // for (EdgeIt e=G.template first(); G.valid(e); G.next(e)) -// push_back(e); -// } -// sort(); -// } - -// KeyType const& first(const_iterator i) const { return *i; } -// KeyType& first(iterator i) { return *i; } - -// ValueType const& second(const_iterator i) const { return m[*i]; } -// ValueType& second(iterator i) { return m[*i]; } -// }; - - - /* ** ** Wrapper fuggvenyek ** ** */ - - - /// \brief Wrapper to Kruskal(). - /// Input is from an EdgeMap, output is a plain boolmap. - - ///\todo some more words would be nice here. - /// - template - inline - typename EdgeCostMap::ValueType - kruskalEdgeMap(Graph const& G, - EdgeCostMap const& edge_costs, - RetEdgeBoolMap &ret_bool_map) { - - typedef KruskalMapInput InputVec; - - InputVec iv(G, edge_costs); - return kruskal(G, iv, ret_bool_map); - } - - - /// \brief Wrapper to Kruskal(). - /// Input is from an EdgeMap, output is to a sequence. - - ///\todo it does not follow the naming convention. - /// - template - inline - typename EdgeCostMap::ValueType - kruskalEdgeMap_IteratorOut(const Graph& G, - const EdgeCostMap& edge_costs, - RetIterator ret_iterator) - { - typedef typename EdgeCostMap::ValueType ValueType; - - typedef SequenceOutput OutMap; - OutMap out(ret_iterator); - - typedef KruskalMapInput InputVec; - - InputVec iv(G, edge_costs); - - return kruskal(G, iv, out); - } - - /// @} - -} //namespace hugo - -#endif //HUGO_KRUSKAL_H