Changeset 824:157115b5814a in lemon0.x for src/hugo/kruskal.h
 Timestamp:
 09/09/04 09:09:11 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1120
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/kruskal.h
r812 r824 22 22 ///Kruskal's algorithm to compute a minimum cost tree. 23 23 24 ///\weakgroup spantree 24 25 namespace hugo { 25 26 … … 35 36 /// \param in This object is used to describe the edge costs. It must 36 37 /// be an STL compatible 'Forward Container' 37 /// with <tt>std::pair<G raph::Edge,X></tt> as its <tt>value_type</tt>,38 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, 38 39 /// where X is the type of the costs. It must contain every edge in 39 40 /// costascending order. … … 53 54 /// \return The cost of the found tree. 54 55 55 template < typename Graph, typename InputEdgeOrder, typename OutBoolMap>56 typename I nputEdgeOrder::value_type::second_type57 kruskal(G raph const& G, InputEdgeOrderconst& in,58 O utBoolMap& out)56 template <class GR, class IN, class OUT> 57 typename IN::value_type::second_type 58 kruskal(GR const& G, IN const& in, 59 OUT& out) 59 60 { 60 typedef typename I nputEdgeOrder::value_type::second_type EdgeCost;61 typedef typename G raph::template NodeMap<int> NodeIntMap;62 typedef typename G raph::Node Node;61 typedef typename IN::value_type::second_type EdgeCost; 62 typedef typename GR::template NodeMap<int> NodeIntMap; 63 typedef typename GR::Node Node; 63 64 64 65 NodeIntMap comp(G, 1); … … 66 67 67 68 EdgeCost tot_cost = 0; 68 for (typename I nputEdgeOrder::const_iterator p = in.begin();69 for (typename IN::const_iterator p = in.begin(); 69 70 p!=in.end(); ++p ) { 70 71 if ( uf.join(G.head((*p).first), … … 84 85 ///\bug What is this? Or why doesn't it work? 85 86 /// 86 template< typenameMap>87 template<class Map> 87 88 class NonConstMapWr { 88 89 const Map &m; … … 92 93 NonConstMapWr(const Map &_m) : m(_m) {} 93 94 94 template< typenameKeyType>95 template<class KeyType> 95 96 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } 96 97 }; 97 98 98 template < typename Graph, typename InputEdgeOrder, typename OutBoolMap>99 inline 100 typename I nputEdgeOrder::ValueType101 kruskal(G raph const& G, InputEdgeOrderconst& edges,102 O utBoolMapconst& out_map)99 template <class GR, class IN, class OUT> 100 inline 101 typename IN::ValueType 102 kruskal(GR const& G, IN const& edges, 103 OUT const& out_map) 103 104 { 104 NonConstMapWr<O utBoolMap> map_wr(out_map);105 NonConstMapWr<OUT> map_wr(out_map); 105 106 return kruskal(G, edges, map_wr); 106 107 } … … 116 117 /// \sa makeKruskalMapInput() 117 118 /// 118 ///\param G raphThe type of the graph the algorithm runs on.119 ///\param GR The type of the graph the algorithm runs on. 119 120 ///\param Map An edge map containing the cost of the edges. 120 121 ///\par … … 124 125 ///computing the total cost of the tree). 125 126 /// 126 template< typename Graph, typenameMap>127 template<class GR, class Map> 127 128 class KruskalMapInput 128 : public std::vector< std::pair<typename G raph::Edge,129 : public std::vector< std::pair<typename GR::Edge, 129 130 typename Map::ValueType> > { 130 131 131 132 public: 132 typedef std::vector< std::pair<typename G raph::Edge,133 typedef std::vector< std::pair<typename GR::Edge, 133 134 typename Map::ValueType> > Parent; 134 135 typedef typename Parent::value_type value_type; … … 149 150 } 150 151 151 KruskalMapInput(G raphconst& G, Map const& m) {152 typedef typename G raph::EdgeIt EdgeIt;152 KruskalMapInput(GR const& G, Map const& m) { 153 typedef typename GR::EdgeIt EdgeIt; 153 154 154 155 this>clear(); … … 177 178 ///\return An appropriate input source for \ref kruskal(). 178 179 /// 179 template< typename Graph, typenameMap>180 inline 181 KruskalMapInput<G raph,Map> makeKruskalMapInput(const Graph&G,const Map &m)180 template<class GR, class Map> 181 inline 182 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m) 182 183 { 183 return KruskalMapInput<G raph,Map>(G,m);184 return KruskalMapInput<GR,Map>(G,m); 184 185 } 185 186 … … 195 196 /// \todo This class may be of wider usage, therefore it could move to 196 197 /// <tt>maps.h</tt> 197 template< typenameIterator>198 template<class Iterator> 198 199 class SequenceOutput { 199 200 mutable Iterator it; … … 208 209 }; 209 210 210 template< typenameIterator>211 template<class Iterator> 211 212 inline 212 213 SequenceOutput<Iterator> … … 241 242 242 243 243 template < typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>244 inline 245 typename EdgeCostMap::ValueType246 kruskalEdgeMap(G raphconst& G,247 EdgeCostMapconst& in,248 R etEdgeBoolMap&out) {244 template <class GR, class IN, class RET> 245 inline 246 typename IN::ValueType 247 kruskalEdgeMap(GR const& G, 248 IN const& in, 249 RET &out) { 249 250 return kruskal(G, 250 KruskalMapInput<G raph,EdgeCostMap>(G,in),251 KruskalMapInput<GR,IN>(G,in), 251 252 out); 252 253 } … … 267 268 /// 268 269 /// \retval out This must be an iteraror of an STL Container with 269 /// <tt>G raph::Edge</tt> as its <tt>value_type</tt>.270 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>. 270 271 /// The algorithm copies the elements of the found tree into this sequence. 271 272 /// For example, if we know that the spanning tree of the graph \c G has 272 273 /// say 53 edges then 273 /// we can put its edges into a vector \c tree with a code like this.274 /// we can put its edges into a STL vector \c tree with a code like this. 274 275 /// \code 275 276 /// std::vector<Edge> tree(53); … … 285 286 /// 286 287 /// \bug its name does not follow the coding style. 287 template < typename Graph, typename EdgeCostMap, typename RetIterator>288 inline 289 typename EdgeCostMap::ValueType290 kruskalEdgeMap_IteratorOut(const G raph& G,291 const EdgeCostMap& in,292 R etIteratorout)288 template <class GR, class IN, class RET> 289 inline 290 typename IN::ValueType 291 kruskalEdgeMap_IteratorOut(const GR& G, 292 const IN& in, 293 RET out) 293 294 { 294 SequenceOutput<R etIterator> _out(out);295 SequenceOutput<RET> _out(out); 295 296 return kruskal(G, 296 KruskalMapInput<G raph, EdgeCostMap>(G, in),297 KruskalMapInput<GR,IN>(G, in), 297 298 _out); 298 299 }
Note: See TracChangeset
for help on using the changeset viewer.