1.1 --- a/src/hugo/kruskal.h Wed Sep 08 12:12:16 2004 +0000
1.2 +++ b/src/hugo/kruskal.h Thu Sep 09 07:09:11 2004 +0000
1.3 @@ -21,6 +21,7 @@
1.4 ///
1.5 ///Kruskal's algorithm to compute a minimum cost tree.
1.6
1.7 +///\weakgroup spantree
1.8 namespace hugo {
1.9
1.10 /// \addtogroup spantree
1.11 @@ -34,7 +35,7 @@
1.12 ///
1.13 /// \param in This object is used to describe the edge costs. It must
1.14 /// be an STL compatible 'Forward Container'
1.15 - /// with <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,
1.16 + /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
1.17 /// where X is the type of the costs. It must contain every edge in
1.18 /// cost-ascending order.
1.19 ///\par
1.20 @@ -52,20 +53,20 @@
1.21 ///
1.22 /// \return The cost of the found tree.
1.23
1.24 - template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.25 - typename InputEdgeOrder::value_type::second_type
1.26 - kruskal(Graph const& G, InputEdgeOrder const& in,
1.27 - OutBoolMap& out)
1.28 + template <class GR, class IN, class OUT>
1.29 + typename IN::value_type::second_type
1.30 + kruskal(GR const& G, IN const& in,
1.31 + OUT& out)
1.32 {
1.33 - typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
1.34 - typedef typename Graph::template NodeMap<int> NodeIntMap;
1.35 - typedef typename Graph::Node Node;
1.36 + typedef typename IN::value_type::second_type EdgeCost;
1.37 + typedef typename GR::template NodeMap<int> NodeIntMap;
1.38 + typedef typename GR::Node Node;
1.39
1.40 NodeIntMap comp(G, -1);
1.41 UnionFind<Node,NodeIntMap> uf(comp);
1.42
1.43 EdgeCost tot_cost = 0;
1.44 - for (typename InputEdgeOrder::const_iterator p = in.begin();
1.45 + for (typename IN::const_iterator p = in.begin();
1.46 p!=in.end(); ++p ) {
1.47 if ( uf.join(G.head((*p).first),
1.48 G.tail((*p).first)) ) {
1.49 @@ -83,7 +84,7 @@
1.50
1.51 ///\bug What is this? Or why doesn't it work?
1.52 ///
1.53 - template<typename Map>
1.54 + template<class Map>
1.55 class NonConstMapWr {
1.56 const Map &m;
1.57 public:
1.58 @@ -91,17 +92,17 @@
1.59
1.60 NonConstMapWr(const Map &_m) : m(_m) {}
1.61
1.62 - template<typename KeyType>
1.63 + template<class KeyType>
1.64 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
1.65 };
1.66
1.67 - template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.68 + template <class GR, class IN, class OUT>
1.69 inline
1.70 - typename InputEdgeOrder::ValueType
1.71 - kruskal(Graph const& G, InputEdgeOrder const& edges,
1.72 - OutBoolMap const& out_map)
1.73 + typename IN::ValueType
1.74 + kruskal(GR const& G, IN const& edges,
1.75 + OUT const& out_map)
1.76 {
1.77 - NonConstMapWr<OutBoolMap> map_wr(out_map);
1.78 + NonConstMapWr<OUT> map_wr(out_map);
1.79 return kruskal(G, edges, map_wr);
1.80 }
1.81
1.82 @@ -115,7 +116,7 @@
1.83 ///
1.84 /// \sa makeKruskalMapInput()
1.85 ///
1.86 - ///\param Graph The type of the graph the algorithm runs on.
1.87 + ///\param GR The type of the graph the algorithm runs on.
1.88 ///\param Map An edge map containing the cost of the edges.
1.89 ///\par
1.90 ///The cost type can be any type satisfying
1.91 @@ -123,13 +124,13 @@
1.92 ///concept if it also has an operator+() implemented. (It is necessary for
1.93 ///computing the total cost of the tree).
1.94 ///
1.95 - template<typename Graph, typename Map>
1.96 + template<class GR, class Map>
1.97 class KruskalMapInput
1.98 - : public std::vector< std::pair<typename Graph::Edge,
1.99 + : public std::vector< std::pair<typename GR::Edge,
1.100 typename Map::ValueType> > {
1.101
1.102 public:
1.103 - typedef std::vector< std::pair<typename Graph::Edge,
1.104 + typedef std::vector< std::pair<typename GR::Edge,
1.105 typename Map::ValueType> > Parent;
1.106 typedef typename Parent::value_type value_type;
1.107
1.108 @@ -148,8 +149,8 @@
1.109 std::sort(this->begin(), this->end(), comparePair());
1.110 }
1.111
1.112 - KruskalMapInput(Graph const& G, Map const& m) {
1.113 - typedef typename Graph::EdgeIt EdgeIt;
1.114 + KruskalMapInput(GR const& G, Map const& m) {
1.115 + typedef typename GR::EdgeIt EdgeIt;
1.116
1.117 this->clear();
1.118 for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
1.119 @@ -176,11 +177,11 @@
1.120 ///
1.121 ///\return An appropriate input source for \ref kruskal().
1.122 ///
1.123 - template<typename Graph, typename Map>
1.124 + template<class GR, class Map>
1.125 inline
1.126 - KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)
1.127 + KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
1.128 {
1.129 - return KruskalMapInput<Graph,Map>(G,m);
1.130 + return KruskalMapInput<GR,Map>(G,m);
1.131 }
1.132
1.133
1.134 @@ -194,7 +195,7 @@
1.135 /// \bug Missing documentation.
1.136 /// \todo This class may be of wider usage, therefore it could move to
1.137 /// <tt>maps.h</tt>
1.138 - template<typename Iterator>
1.139 + template<class Iterator>
1.140 class SequenceOutput {
1.141 mutable Iterator it;
1.142
1.143 @@ -207,7 +208,7 @@
1.144 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
1.145 };
1.146
1.147 - template<typename Iterator>
1.148 + template<class Iterator>
1.149 inline
1.150 SequenceOutput<Iterator>
1.151 makeSequenceOutput(Iterator it) {
1.152 @@ -240,14 +241,14 @@
1.153 /// \return The cost of the found tree.
1.154
1.155
1.156 - template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.157 + template <class GR, class IN, class RET>
1.158 inline
1.159 - typename EdgeCostMap::ValueType
1.160 - kruskalEdgeMap(Graph const& G,
1.161 - EdgeCostMap const& in,
1.162 - RetEdgeBoolMap &out) {
1.163 + typename IN::ValueType
1.164 + kruskalEdgeMap(GR const& G,
1.165 + IN const& in,
1.166 + RET &out) {
1.167 return kruskal(G,
1.168 - KruskalMapInput<Graph,EdgeCostMap>(G,in),
1.169 + KruskalMapInput<GR,IN>(G,in),
1.170 out);
1.171 }
1.172
1.173 @@ -266,11 +267,11 @@
1.174 ///computing the total cost of the tree).
1.175 ///
1.176 /// \retval out This must be an iteraror of an STL Container with
1.177 - /// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.
1.178 + /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.179 /// The algorithm copies the elements of the found tree into this sequence.
1.180 /// For example, if we know that the spanning tree of the graph \c G has
1.181 /// say 53 edges then
1.182 - /// we can put its edges into a vector \c tree with a code like this.
1.183 + /// we can put its edges into a STL vector \c tree with a code like this.
1.184 /// \code
1.185 /// std::vector<Edge> tree(53);
1.186 /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
1.187 @@ -284,16 +285,16 @@
1.188 /// \return The cost of the found tree.
1.189 ///
1.190 /// \bug its name does not follow the coding style.
1.191 - template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.192 + template <class GR, class IN, class RET>
1.193 inline
1.194 - typename EdgeCostMap::ValueType
1.195 - kruskalEdgeMap_IteratorOut(const Graph& G,
1.196 - const EdgeCostMap& in,
1.197 - RetIterator out)
1.198 + typename IN::ValueType
1.199 + kruskalEdgeMap_IteratorOut(const GR& G,
1.200 + const IN& in,
1.201 + RET out)
1.202 {
1.203 - SequenceOutput<RetIterator> _out(out);
1.204 + SequenceOutput<RET> _out(out);
1.205 return kruskal(G,
1.206 - KruskalMapInput<Graph, EdgeCostMap>(G, in),
1.207 + KruskalMapInput<GR,IN>(G, in),
1.208 _out);
1.209 }
1.210