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.
1.1 --- a/src/hugo/Makefile.am Mon Sep 06 13:47:54 2004 +0000
1.2 +++ b/src/hugo/Makefile.am Mon Sep 06 17:12:00 2004 +0000
1.3 @@ -11,6 +11,7 @@
1.4 full_graph.h \
1.5 graph_wrapper.h \
1.6 invalid.h \
1.7 + kruskal.h \
1.8 list_graph.h \
1.9 map_defines.h \
1.10 map_registry.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/kruskal.h Mon Sep 06 17:12:00 2004 +0000
2.3 @@ -0,0 +1,304 @@
2.4 +// -*- c++ -*- //
2.5 +#ifndef HUGO_KRUSKAL_H
2.6 +#define HUGO_KRUSKAL_H
2.7 +
2.8 +#include <algorithm>
2.9 +#include <hugo/unionfind.h>
2.10 +
2.11 +/**
2.12 +@defgroup spantree Minimum Cost Spanning Tree Algorithms
2.13 +@ingroup galgs
2.14 +\brief This group containes the algorithms for finding a minimum cost spanning
2.15 +tree in a graph
2.16 +
2.17 +This group containes the algorithms for finding a minimum cost spanning
2.18 +tree in a graph
2.19 +*/
2.20 +
2.21 +///\ingroup spantree
2.22 +///\file
2.23 +///\brief Kruskal's algorithm to compute a minimum cost tree
2.24 +///
2.25 +///Kruskal's algorithm to compute a minimum cost tree.
2.26 +
2.27 +namespace hugo {
2.28 +
2.29 + /// \addtogroup spantree
2.30 + /// @{
2.31 +
2.32 + /// Kruskal's algorithm to find a minimum cost tree of a graph.
2.33 +
2.34 + /// This function runs Kruskal's algorithm to find a minimum cost tree.
2.35 + /// \param G The graph the algorithm runs on. The algorithm considers the
2.36 + /// graph to be undirected, the direction of the edges are not used.
2.37 + ///
2.38 + /// \param in This object is used to describe the edge costs. It must
2.39 + /// be an STL compatible 'Forward Container'
2.40 + /// with <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,
2.41 + /// where X is the type of the costs. It must contain every edge in
2.42 + /// cost-ascending order.
2.43 + ///\par
2.44 + /// For the sake of simplicity, there is a helper class KruskalMapInput,
2.45 + /// which converts a
2.46 + /// simple edge map to an input of this form. Alternatively, you can use
2.47 + /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
2.48 + /// the edge costs are given by an edge map.
2.49 + ///
2.50 + /// \retval out This must be a writable \c bool edge map.
2.51 + /// After running the algorithm
2.52 + /// this will contain the found minimum cost spanning tree: the value of an
2.53 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
2.54 + /// be set to \c false. The value of each edge will be set exactly once.
2.55 + ///
2.56 + /// \return The cost of the found tree.
2.57 +
2.58 + template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
2.59 + typename InputEdgeOrder::value_type::second_type
2.60 + kruskal(Graph const& G, InputEdgeOrder const& in,
2.61 + OutBoolMap& out)
2.62 + {
2.63 + typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
2.64 + typedef typename Graph::template NodeMap<int> NodeIntMap;
2.65 + typedef typename Graph::Node Node;
2.66 +
2.67 + NodeIntMap comp(G, -1);
2.68 + UnionFind<Node,NodeIntMap> uf(comp);
2.69 +
2.70 + EdgeCost tot_cost = 0;
2.71 + for (typename InputEdgeOrder::const_iterator p = in.begin();
2.72 + p!=in.end(); ++p ) {
2.73 + if ( uf.join(G.head((*p).first),
2.74 + G.tail((*p).first)) ) {
2.75 + out.set((*p).first, true);
2.76 + tot_cost += (*p).second;
2.77 + }
2.78 + else {
2.79 + out.set((*p).first, false);
2.80 + }
2.81 + }
2.82 + return tot_cost;
2.83 + }
2.84 +
2.85 + /* A work-around for running Kruskal with const-reference bool maps... */
2.86 +
2.87 + ///\bug What is this? Or why doesn't it works?
2.88 + ///
2.89 + template<typename Map>
2.90 + class NonConstMapWr {
2.91 + const Map &m;
2.92 + public:
2.93 + typedef typename Map::ValueType ValueType;
2.94 +
2.95 + NonConstMapWr(const Map &_m) : m(_m) {}
2.96 +
2.97 + template<typename KeyType>
2.98 + void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
2.99 + };
2.100 +
2.101 + template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
2.102 + inline
2.103 + typename InputEdgeOrder::ValueType
2.104 + kruskal(Graph const& G, InputEdgeOrder const& edges,
2.105 + OutBoolMap const& out_map)
2.106 + {
2.107 + NonConstMapWr<OutBoolMap> map_wr(out_map);
2.108 + return kruskal(G, edges, map_wr);
2.109 + }
2.110 +
2.111 + /* ** ** Input-objects ** ** */
2.112 +
2.113 + /// Kruskal input source.
2.114 +
2.115 + /// Kruskal input source.
2.116 + ///
2.117 + /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
2.118 + ///
2.119 + /// \sa makeKruskalMapInput()
2.120 + ///
2.121 + ///\param Graph The type of the graph the algorithm runs on.
2.122 + ///\param Map An edge map containing the cost of the edges.
2.123 + ///\par
2.124 + ///The cost type can be any type satisfying
2.125 + ///the STL 'LessThan comparable'
2.126 + ///concept if it also has an operator+() implemented. (It is necessary for
2.127 + ///computing the total cost of the tree).
2.128 + ///
2.129 + template<typename Graph, typename Map>
2.130 + class KruskalMapInput
2.131 + : public std::vector< std::pair<typename Graph::Edge,
2.132 + typename Map::ValueType> > {
2.133 +
2.134 + public:
2.135 + typedef std::vector< std::pair<typename Graph::Edge,
2.136 + typename Map::ValueType> > Parent;
2.137 + typedef typename Parent::value_type value_type;
2.138 +
2.139 + private:
2.140 + class comparePair {
2.141 + public:
2.142 + bool operator()(const value_type& a,
2.143 + const value_type& b) {
2.144 + return a.second < b.second;
2.145 + }
2.146 + };
2.147 +
2.148 + public:
2.149 +
2.150 + void sort() {
2.151 + std::sort(this->begin(), this->end(), comparePair());
2.152 + }
2.153 +
2.154 + KruskalMapInput(Graph const& G, Map const& m) {
2.155 + typedef typename Graph::EdgeIt EdgeIt;
2.156 +
2.157 + this->clear();
2.158 + for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
2.159 + sort();
2.160 + }
2.161 + };
2.162 +
2.163 + /// Creates a KruskalMapInput object for \ref kruskal()
2.164 +
2.165 + /// It makes is easier to use
2.166 + /// \ref KruskalMapInput by making it unnecessary
2.167 + /// to explicitly give the type of the parameters.
2.168 + ///
2.169 + /// In most cases you possibly
2.170 + /// want to use the function kruskalEdgeMap() instead.
2.171 + ///
2.172 + ///\param G The type of the graph the algorithm runs on.
2.173 + ///\param m An edge map containing the cost of the edges.
2.174 + ///\par
2.175 + ///The cost type can be any type satisfying the
2.176 + ///STL 'LessThan Comparable'
2.177 + ///concept if it also has an operator+() implemented. (It is necessary for
2.178 + ///computing the total cost of the tree).
2.179 + ///
2.180 + ///\return An appropriate input source for \ref kruskal().
2.181 + ///
2.182 + template<typename Graph, typename Map>
2.183 + inline
2.184 + KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)
2.185 + {
2.186 + return KruskalMapInput<Graph,Map>(G,m);
2.187 + }
2.188 +
2.189 +
2.190 + /* ** ** Output-objects: simple writable bool maps** ** */
2.191 +
2.192 + /// A writable bool-map that makes a sequence of "true" keys
2.193 +
2.194 + /// A writable bool-map that creates a sequence out of keys that receives
2.195 + /// the value "true".
2.196 + /// \warning Not a regular property map, as it doesn't know its KeyType
2.197 + /// \bug Missing documentation.
2.198 + /// \todo This class may be of wider usage, therefore it could move to
2.199 + /// <tt>maps.h</tt>
2.200 + template<typename Iterator>
2.201 + class SequenceOutput {
2.202 + mutable Iterator it;
2.203 +
2.204 + public:
2.205 + typedef bool ValueType;
2.206 +
2.207 + SequenceOutput(Iterator const &_it) : it(_it) {}
2.208 +
2.209 + template<typename KeyType>
2.210 + void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
2.211 + };
2.212 +
2.213 + template<typename Iterator>
2.214 + inline
2.215 + SequenceOutput<Iterator>
2.216 + makeSequenceOutput(Iterator it) {
2.217 + return SequenceOutput<Iterator>(it);
2.218 + }
2.219 +
2.220 + /* ** ** Wrapper funtions ** ** */
2.221 +
2.222 +
2.223 + /// \brief Wrapper function to kruskal().
2.224 + /// Input is from an edge map, output is a plain bool map.
2.225 + ///
2.226 + /// Wrapper function to kruskal().
2.227 + /// Input is from an edge map, output is a plain bool map.
2.228 + ///
2.229 + ///\param G The type of the graph the algorithm runs on.
2.230 + ///\param in An edge map containing the cost of the edges.
2.231 + ///\par
2.232 + ///The cost type can be any type satisfying the
2.233 + ///STL 'LessThan Comparable'
2.234 + ///concept if it also has an operator+() implemented. (It is necessary for
2.235 + ///computing the total cost of the tree).
2.236 + ///
2.237 + /// \retval out This must be a writable \c bool edge map.
2.238 + /// After running the algorithm
2.239 + /// this will contain the found minimum cost spanning tree: the value of an
2.240 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
2.241 + /// be set to \c false. The value of each edge will be set exactly once.
2.242 + ///
2.243 + /// \return The cost of the found tree.
2.244 +
2.245 +
2.246 + template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
2.247 + inline
2.248 + typename EdgeCostMap::ValueType
2.249 + kruskalEdgeMap(Graph const& G,
2.250 + EdgeCostMap const& in,
2.251 + RetEdgeBoolMap &out) {
2.252 + return kruskal(G,
2.253 + KruskalMapInput<Graph,EdgeCostMap>(G,in),
2.254 + out);
2.255 + }
2.256 +
2.257 + /// \brief Wrapper function to kruskal().
2.258 + /// Input is from an edge map, output is an STL Sequence.
2.259 + ///
2.260 + /// Wrapper function to kruskal().
2.261 + /// Input is from an edge map, output is an STL Sequence.
2.262 + ///
2.263 + ///\param G The type of the graph the algorithm runs on.
2.264 + ///\param in An edge map containing the cost of the edges.
2.265 + ///\par
2.266 + ///The cost type can be any type satisfying the
2.267 + ///STL 'LessThan Comparable'
2.268 + ///concept if it also has an operator+() implemented. (It is necessary for
2.269 + ///computing the total cost of the tree).
2.270 + ///
2.271 + /// \retval out This must be an iteraror of an STL Container with
2.272 + /// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.
2.273 + /// The algorithm copies the elements of the found tree into this sequence.
2.274 + /// For example, if we know that the spanning tree of the graph \c G has
2.275 + /// say 53 edges then
2.276 + /// we can put its edges into a vector \c tree with a code like this.
2.277 + /// \code
2.278 + /// std::vector<Edge> tree(53);
2.279 + /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
2.280 + /// \endcode
2.281 + /// Or if we don't know in advance the size of the tree, we can write this.
2.282 + /// \code
2.283 + /// std::vector<Edge> tree;
2.284 + /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
2.285 + /// \endcode
2.286 + ///
2.287 + /// \return The cost of the found tree.
2.288 + ///
2.289 + /// \bug its name does not follow the coding style.
2.290 + template <typename Graph, typename EdgeCostMap, typename RetIterator>
2.291 + inline
2.292 + typename EdgeCostMap::ValueType
2.293 + kruskalEdgeMap_IteratorOut(const Graph& G,
2.294 + const EdgeCostMap& in,
2.295 + RetIterator out)
2.296 + {
2.297 + SequenceOutput<RetIterator> _out(out);
2.298 + return kruskal(G,
2.299 + KruskalMapInput<Graph, EdgeCostMap>(G, in),
2.300 + _out);
2.301 + }
2.302 +
2.303 + /// @}
2.304 +
2.305 +} //namespace hugo
2.306 +
2.307 +#endif //HUGO_KRUSKAL_H
3.1 --- a/src/hugo/unionfind.h Mon Sep 06 13:47:54 2004 +0000
3.2 +++ b/src/hugo/unionfind.h Mon Sep 06 17:12:00 2004 +0000
3.3 @@ -32,9 +32,14 @@
3.4 * only four methods: join (union), find, insert and size.
3.5 * For more features see the \ref UnionFindEnum class.
3.6 *
3.7 + * It is primarily used in Kruskal algorithm for finding minimal
3.8 + * cost spanning tree in a graph.
3.9 + * \sa kruskal()
3.10 + *
3.11 * \pre The elements are automatically added only if the map
3.12 * given to the constructor was filled with -1's. Otherwise you
3.13 * need to add all the elements by the \ref insert() method.
3.14 + * \bug It is not clear what the constructor parameter is used for.
3.15 */
3.16
3.17 template <typename T, typename TIntMap>
4.1 --- a/src/test/Makefile.am Mon Sep 06 13:47:54 2004 +0000
4.2 +++ b/src/test/Makefile.am Mon Sep 06 17:12:00 2004 +0000
4.3 @@ -2,13 +2,20 @@
4.4
4.5 noinst_HEADERS = test_tools.h graph_test.h
4.6
4.7 -check_PROGRAMS = test_tools_pass test_tools_fail \
4.8 +check_PROGRAMS = \
4.9 + bfs_test \
4.10 + dfs_test \
4.11 + dijkstra_test \
4.12 + error_test \
4.13 graph_test \
4.14 - dijkstra_test bfs_test dfs_test \
4.15 - minlengthpaths_test mincostflows_test \
4.16 - unionfind_test xy_test \
4.17 + kruskal_test \
4.18 + mincostflows_test \
4.19 + minlengthpaths_test \
4.20 + test_tools_fail \
4.21 + test_tools_pass \
4.22 time_measure_test \
4.23 - error_test
4.24 + unionfind_test \
4.25 + xy_test
4.26
4.27
4.28 TESTS = $(check_PROGRAMS)
4.29 @@ -19,6 +26,7 @@
4.30 dijkstra_test_SOURCES = dijkstra_test.cc
4.31 error_test_SOURCES = error_test.cc
4.32 graph_test_SOURCES = graph_test.cc
4.33 +kruskal_test_SOURCES = kruskal_test.cc
4.34 mincostflows_test_SOURCES = mincostflows_test.cc
4.35 minlengthpaths_test_SOURCES = minlengthpaths_test.cc
4.36 time_measure_test_SOURCES = time_measure_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/test/kruskal_test.cc Mon Sep 06 17:12:00 2004 +0000
5.3 @@ -0,0 +1,94 @@
5.4 +#include <iostream>
5.5 +#include <vector>
5.6 +
5.7 +#include "test_tools.h"
5.8 +#include <hugo/maps.h>
5.9 +#include <hugo/kruskal.h>
5.10 +#include <hugo/list_graph.h>
5.11 +#include <hugo/skeletons/maps.h>
5.12 +#include <hugo/skeletons/graph.h>
5.13 +
5.14 +
5.15 +using namespace std;
5.16 +using namespace hugo;
5.17 +
5.18 +void checkCompileKruskal()
5.19 +{
5.20 + skeleton::WriteMap<skeleton::StaticGraphSkeleton::Edge,bool> w;
5.21 +
5.22 + kruskalEdgeMap(skeleton::StaticGraphSkeleton(),
5.23 + skeleton::ReadMap<skeleton::StaticGraphSkeleton::Edge,int>(),
5.24 + w);
5.25 +}
5.26 +
5.27 +int main() {
5.28 +
5.29 + typedef ListGraph::Node Node;
5.30 + typedef ListGraph::Edge Edge;
5.31 + typedef ListGraph::NodeIt NodeIt;
5.32 + typedef ListGraph::EdgeIt EdgeIt;
5.33 +
5.34 + ListGraph G;
5.35 +
5.36 + Node s=G.addNode();
5.37 + Node v1=G.addNode();
5.38 + Node v2=G.addNode();
5.39 + Node v3=G.addNode();
5.40 + Node v4=G.addNode();
5.41 + Node t=G.addNode();
5.42 +
5.43 + Edge e1 = G.addEdge(s, v1);
5.44 + Edge e2 = G.addEdge(s, v2);
5.45 + Edge e3 = G.addEdge(v1, v2);
5.46 + Edge e4 = G.addEdge(v2, v1);
5.47 + Edge e5 = G.addEdge(v1, v3);
5.48 + Edge e6 = G.addEdge(v3, v2);
5.49 + Edge e7 = G.addEdge(v2, v4);
5.50 + Edge e8 = G.addEdge(v4, v3);
5.51 + Edge e9 = G.addEdge(v3, t);
5.52 + Edge e10 = G.addEdge(v4, t);
5.53 +
5.54 + typedef ListGraph::EdgeMap<int> ECostMap;
5.55 + typedef ListGraph::EdgeMap<bool> EBoolMap;
5.56 +
5.57 + ECostMap edge_cost_map(G, 2);
5.58 + EBoolMap tree_map(G);
5.59 +
5.60 +
5.61 + //Test with const map.
5.62 + check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
5.63 + "Total cost should be 10");
5.64 + //Test with a edge map (filled with uniform costs).
5.65 + check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
5.66 + "Total cost should be 10");
5.67 +
5.68 + edge_cost_map.set(e1, -10);
5.69 + edge_cost_map.set(e2, -9);
5.70 + edge_cost_map.set(e3, -8);
5.71 + edge_cost_map.set(e4, -7);
5.72 + edge_cost_map.set(e5, -6);
5.73 + edge_cost_map.set(e6, -5);
5.74 + edge_cost_map.set(e7, -4);
5.75 + edge_cost_map.set(e8, -3);
5.76 + edge_cost_map.set(e9, -2);
5.77 + edge_cost_map.set(e10, -1);
5.78 +
5.79 + vector<Edge> tree_edge_vec;
5.80 +
5.81 + //Test with a edge map and inserter.
5.82 + check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
5.83 + back_inserter(tree_edge_vec))
5.84 + ==-31,
5.85 + "Total cost should be -31.");
5.86 +
5.87 + check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
5.88 +
5.89 + check(tree_edge_vec[0]==e1 &&
5.90 + tree_edge_vec[1]==e2 &&
5.91 + tree_edge_vec[2]==e5 &&
5.92 + tree_edge_vec[3]==e7 &&
5.93 + tree_edge_vec[4]==e9,
5.94 + "Wrong tree.");
5.95 +
5.96 + return 0;
5.97 +}
6.1 --- a/src/work/johanna/kruskal.h Mon Sep 06 13:47:54 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,311 +0,0 @@
6.4 -// -*- c++ -*- //
6.5 -#ifndef HUGO_KRUSKAL_H
6.6 -#define HUGO_KRUSKAL_H
6.7 -
6.8 -#include <algorithm>
6.9 -#include <hugo/unionfind.h>
6.10 -
6.11 -/**
6.12 -@defgroup spantree Minimum Cost Spanning Tree Algorithms
6.13 -\brief This group containes the algorithms for finding a minimum cost spanning
6.14 -tree in a graph
6.15 -@ingroup galgs
6.16 -*/
6.17 -
6.18 -///\ingroup spantree
6.19 -///\file
6.20 -///\brief Kruskal's algorithm to compute a minimum cost tree
6.21 -
6.22 -namespace hugo {
6.23 -
6.24 - /// \addtogroup spantree
6.25 - /// @{
6.26 -
6.27 - /// Kruskal's algorithm to find a minimum cost tree of a graph.
6.28 -
6.29 - /// This function runs Kruskal's algorithm to find a minimum cost tree.
6.30 - /// \param G The graph the algorithm runs on.
6.31 - /// \param in This object is used to describe the edge costs. It must
6.32 - /// be an STL 'forward container'
6.33 - /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
6.34 - /// where X is the type of the costs. It must contain every edge in
6.35 - /// cost-ascending order.
6.36 - /// \retval out This must be a writeable EdgeMap. After running the algorithm
6.37 - /// this will contain the found minimum cost spanning tree: the value of an
6.38 - /// edge will be set to \c true if it belongs to the tree, otherwise it will
6.39 - /// be set to \c false. The value of each edge will be set exactly once.\n
6.40 - /// For the sake of simplicity, there is a helper class KruskalPairVec,
6.41 - /// which converts a
6.42 - /// simple EdgeMap to an input of this form. Alternatively, you can use
6.43 - /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
6.44 - /// the edge costs are given by an EdgeMap.
6.45 - /// \return The cost of the found tree.
6.46 -
6.47 - template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
6.48 - typename InputEdgeOrder::value_type::second_type
6.49 - kruskal(Graph const& G, InputEdgeOrder const& in,
6.50 - OutBoolMap& out)
6.51 - {
6.52 - typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
6.53 - typedef typename Graph::template NodeMap<int> NodeIntMap;
6.54 - typedef typename Graph::Node Node;
6.55 -
6.56 - NodeIntMap comp(G, -1);
6.57 - UnionFind<Node,NodeIntMap> uf(comp);
6.58 -
6.59 - EdgeCost tot_cost = 0;
6.60 - for (typename InputEdgeOrder::const_iterator p = in.begin();
6.61 - p!=in.end(); ++p ) {
6.62 - if ( uf.join(G.head((*p).first),
6.63 - G.tail((*p).first)) ) {
6.64 - out.set((*p).first, true);
6.65 - tot_cost += (*p).second;
6.66 - }
6.67 - else {
6.68 - out.set((*p).first, false);
6.69 - }
6.70 - }
6.71 - return tot_cost;
6.72 - }
6.73 -
6.74 - /* A work-around for running Kruskal with const-reference bool maps... */
6.75 -
6.76 - template<typename Map>
6.77 - class NonConstMapWr {
6.78 - const Map &m;
6.79 - public:
6.80 - typedef typename Map::ValueType ValueType;
6.81 -
6.82 - NonConstMapWr(const Map &_m) : m(_m) {}
6.83 -
6.84 - template<typename KeyType>
6.85 - void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
6.86 - };
6.87 -
6.88 - template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
6.89 - inline
6.90 - typename InputEdgeOrder::ValueType
6.91 - kruskal(Graph const& G, InputEdgeOrder const& edges,
6.92 - OutBoolMap const& out_map)
6.93 - {
6.94 - NonConstMapWr<OutBoolMap> map_wr(out_map);
6.95 - return kruskal(G, edges, map_wr);
6.96 - }
6.97 -
6.98 -
6.99 - /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
6.100 -
6.101 - /// A writable bool-map that makes a sequence of "true" keys
6.102 -
6.103 - /// A writable bool-map that creates a sequence out of keys that receives
6.104 - /// the value "true".
6.105 - /// \warning Not a regular property map, as it doesn't know its KeyType
6.106 -
6.107 - template<typename Iterator>
6.108 - class SequenceOutput {
6.109 - mutable Iterator it;
6.110 -
6.111 - public:
6.112 - typedef bool ValueType;
6.113 -
6.114 - SequenceOutput(Iterator const &_it) : it(_it) {}
6.115 -
6.116 - template<typename KeyType>
6.117 - void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
6.118 - };
6.119 -
6.120 - template<typename Iterator>
6.121 - inline
6.122 - SequenceOutput<Iterator>
6.123 - makeSequenceOutput(Iterator it) {
6.124 - return SequenceOutput<Iterator>(it);
6.125 - }
6.126 -
6.127 - /* ** ** InputSource -ok ** ** */
6.128 -
6.129 - /// Kruskal input source.
6.130 -
6.131 - /// Kruskal input source.
6.132 - ///
6.133 - template<typename Graph, typename Map>
6.134 - class KruskalMapInput
6.135 - : public std::vector< std::pair<typename Graph::Edge,
6.136 - typename Map::ValueType> > {
6.137 -
6.138 - public:
6.139 - typedef std::vector< std::pair<typename Graph::Edge,
6.140 - typename Map::ValueType> > Parent;
6.141 - typedef typename Parent::value_type value_type;
6.142 -// typedef Key KeyType;
6.143 -// typedef Val ValueType;
6.144 -// typedef std::pair<Key,Val> PairType;
6.145 -// typedef typename Parent::iterator iterator;
6.146 -// typedef typename Parent::const_iterator const_iterator;
6.147 -
6.148 - private:
6.149 - class comparePair {
6.150 - public:
6.151 - bool operator()(const value_type& a,
6.152 - const value_type& b) {
6.153 - return a.second < b.second;
6.154 - }
6.155 - };
6.156 -
6.157 - public:
6.158 -
6.159 - // FIXME: kell ez?
6.160 - // KruskalMapInput(Parent const& p) : Parent(p) {}
6.161 -
6.162 - void sort() {
6.163 - std::sort(this->begin(), this->end(), comparePair());
6.164 - }
6.165 -
6.166 - // FIXME: nem nagyon illik ez ide...
6.167 - KruskalMapInput(Graph const& G, Map const& m) {
6.168 - typedef typename Graph::EdgeIt EdgeIt;
6.169 -
6.170 - this->clear();
6.171 - for(EdgeIt e(G);G.valid(e);G.next(e)) {
6.172 - // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
6.173 - push_back(make_pair(e, m[e]));
6.174 - }
6.175 - sort();
6.176 - }
6.177 -
6.178 -// Key const& first(const_iterator i) const { return i->first; }
6.179 -// Key& first(iterator i) { return i->first; }
6.180 -
6.181 -// Val const& second(const_iterator i) const { return i->second; }
6.182 -// Val& second(iterator i) { return i->second; }
6.183 - };
6.184 -
6.185 -
6.186 -// template<typename Graph, typename Map>
6.187 -// class KruskalMapVec {
6.188 -// public:
6.189 -
6.190 -// typedef std::pair<typename Map::KeyType, Map::ValueType> value_type;
6.191 -
6.192 -// typedef std::vector<KeyType> Container;
6.193 -// Container container;
6.194 -// std::vector<typename Map::KeyType> container
6.195 -// const Map &m;
6.196 -
6.197 -
6.198 -// class iterator
6.199 -// {
6.200 -// Container::iterator i;
6.201 -// public:
6.202 -// iterator &operator ++() {++i;return *this;}
6.203 -// valuetype operator *() {return value_type(container(i),m[container(i)]);}
6.204 -// bool operator==(iterator b) {return i==b.i;}
6.205 -// iterator() {}
6.206 -// iterator(Container::iterator _i) i(_i) {}
6.207 -// };
6.208 -// class const_iterator
6.209 -// {
6.210 -// Container::const_iterator i;
6.211 -// public:
6.212 -// iterator &operator ++() {++i;return *this;}
6.213 -// valuetype operator *() {return value_type(container(i),m[container(i)]);}
6.214 -// bool operator==(iterator b) {return i==b.i;}
6.215 -// const_iterator() {}
6.216 -// const_iterator(Container::iterator _i) i(_i) {}
6.217 -// };
6.218 -
6.219 -// iterator begin() { return iterator(container.begin());}
6.220 -// const_iterator begin() const { return iterator(container.begin());}
6.221 -// iterator end() { return iterator(container.end());}
6.222 -// const_iterator end() const { return iterator(container.end());}
6.223 -
6.224 -// private:
6.225 -
6.226 -// class compareKeys {
6.227 -// const Map &m;
6.228 -// public:
6.229 -// compareKeys(Map const &_m) : m(_m) {}
6.230 -// bool operator()(KeyType const& a, KeyType const& b) {
6.231 -// return m[a] < m[b];
6.232 -// }
6.233 -// };
6.234 -
6.235 -// public:
6.236 -
6.237 -// KruskalMapVec(Map const& _m) : m(_m) {}
6.238 -
6.239 -// void sort() {
6.240 -// std::sort(begin(), end(), compareKeys(m));
6.241 -// }
6.242 -
6.243 -// // FIXME: nem nagyon illik ez ide...
6.244 -// template<typename Graph>
6.245 -// KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
6.246 -// typedef typename Graph::EdgeIt EdgeIt;
6.247 -
6.248 -// clear();
6.249 -// for(EdgeIt e(G);G.valid(e);G.next(e)) {
6.250 -// // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e))
6.251 -// push_back(e);
6.252 -// }
6.253 -// sort();
6.254 -// }
6.255 -
6.256 -// KeyType const& first(const_iterator i) const { return *i; }
6.257 -// KeyType& first(iterator i) { return *i; }
6.258 -
6.259 -// ValueType const& second(const_iterator i) const { return m[*i]; }
6.260 -// ValueType& second(iterator i) { return m[*i]; }
6.261 -// };
6.262 -
6.263 -
6.264 - /* ** ** Wrapper fuggvenyek ** ** */
6.265 -
6.266 -
6.267 - /// \brief Wrapper to Kruskal().
6.268 - /// Input is from an EdgeMap, output is a plain boolmap.
6.269 -
6.270 - ///\todo some more words would be nice here.
6.271 - ///
6.272 - template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
6.273 - inline
6.274 - typename EdgeCostMap::ValueType
6.275 - kruskalEdgeMap(Graph const& G,
6.276 - EdgeCostMap const& edge_costs,
6.277 - RetEdgeBoolMap &ret_bool_map) {
6.278 -
6.279 - typedef KruskalMapInput<Graph,EdgeCostMap> InputVec;
6.280 -
6.281 - InputVec iv(G, edge_costs);
6.282 - return kruskal(G, iv, ret_bool_map);
6.283 - }
6.284 -
6.285 -
6.286 - /// \brief Wrapper to Kruskal().
6.287 - /// Input is from an EdgeMap, output is to a sequence.
6.288 -
6.289 - ///\todo it does not follow the naming convention.
6.290 - ///
6.291 - template <typename Graph, typename EdgeCostMap, typename RetIterator>
6.292 - inline
6.293 - typename EdgeCostMap::ValueType
6.294 - kruskalEdgeMap_IteratorOut(const Graph& G,
6.295 - const EdgeCostMap& edge_costs,
6.296 - RetIterator ret_iterator)
6.297 - {
6.298 - typedef typename EdgeCostMap::ValueType ValueType;
6.299 -
6.300 - typedef SequenceOutput<RetIterator> OutMap;
6.301 - OutMap out(ret_iterator);
6.302 -
6.303 - typedef KruskalMapInput<Graph, EdgeCostMap> InputVec;
6.304 -
6.305 - InputVec iv(G, edge_costs);
6.306 -
6.307 - return kruskal(G, iv, out);
6.308 - }
6.309 -
6.310 - /// @}
6.311 -
6.312 -} //namespace hugo
6.313 -
6.314 -#endif //HUGO_KRUSKAL_H