lemon-0.x: comparison src/hugo/kruskal.h

equal deleted inserted replaced

-:b33fc1b92420
+:c3f61cb0ce14
 ///\file
 ///\brief Kruskal's algorithm to compute a minimum cost tree
 ///
 ///Kruskal's algorithm to compute a minimum cost tree.
+///\weakgroup spantree
 namespace hugo {
 /// \addtogroup spantree
 /// @{
 /// \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 <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,
+/// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
 /// 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
 /// 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 Graph, typename InputEdgeOrder, typename OutBoolMap>
+template <class GR, class IN, class OUT>
-typename InputEdgeOrder::value_type::second_type
+typename IN::value_type::second_type
-kruskal(Graph const& G, InputEdgeOrder const& in,
+kruskal(GR const& G, IN const& in,
-		 OutBoolMap& out)
+		 OUT& out)
 {
-typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
+typedef typename IN::value_type::second_type EdgeCost;
-typedef typename Graph::template NodeMap<int> NodeIntMap;
+typedef typename GR::template NodeMap<int> NodeIntMap;
-typedef typename Graph::Node Node;
+typedef typename GR::Node Node;
 NodeIntMap comp(G, -1);
 UnionFind<Node,NodeIntMap> uf(comp);
 EdgeCost tot_cost = 0;
-for (typename InputEdgeOrder::const_iterator p = in.begin();
+for (typename IN::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;
 /* A work-around for running Kruskal with const-reference bool maps... */
 ///\bug What is this? Or why doesn't it work?
 ///
-template<typename Map>
+template<class Map>
 class NonConstMapWr {
 const Map &m;
 public:
 typedef typename Map::ValueType ValueType;
 NonConstMapWr(const Map &_m) : m(_m) {}
-template<typename KeyType>
+template<class KeyType>
 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
 };
-template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
+template <class GR, class IN, class OUT>
 inline
-typename InputEdgeOrder::ValueType
+typename IN::ValueType
-kruskal(Graph const& G, InputEdgeOrder const& edges,
+kruskal(GR const& G, IN const& edges,
-	  OutBoolMap const& out_map)
+	  OUT const& out_map)
 {
-NonConstMapWr<OutBoolMap> map_wr(out_map);
+NonConstMapWr<OUT> map_wr(out_map);
 return kruskal(G, edges, map_wr);
 }
 /* ** ** Input-objects ** ** */
 ///
 /// 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 GR 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<typename Graph, typename Map>
+template<class GR, class Map>
 class KruskalMapInput
-: public std::vector< std::pair<typename Graph::Edge,
+: public std::vector< std::pair<typename GR::Edge,
 				    typename Map::ValueType> > {
 public:
-typedef std::vector< std::pair<typename Graph::Edge,
+typedef std::vector< std::pair<typename GR::Edge,
 				   typename Map::ValueType> > Parent;
 typedef typename Parent::value_type value_type;
 private:
 class comparePair {
 void sort() {
 std::sort(this->begin(), this->end(), comparePair());
 }
-KruskalMapInput(Graph const& G, Map const& m) {
+KruskalMapInput(GR const& G, Map const& m) {
-typedef typename Graph::EdgeIt EdgeIt;
+typedef typename GR::EdgeIt EdgeIt;
 this->clear();
 for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
 sort();
 }
 ///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<typename Graph, typename Map>
+template<class GR, class Map>
 inline
-KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)
+KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
 {
-return KruskalMapInput<Graph,Map>(G,m);
+return KruskalMapInput<GR,Map>(G,m);
 }
 /* ** ** Output-objects: simple writable bool maps** ** */
 /// 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
 /// <tt>maps.h</tt>
-template<typename Iterator>
+template<class Iterator>
 class SequenceOutput {
 mutable Iterator it;
 public:
 typedef bool ValueType;
 template<typename KeyType>
 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
 };
-template<typename Iterator>
+template<class Iterator>
 inline
 SequenceOutput<Iterator>
 makeSequenceOutput(Iterator it) {
 return SequenceOutput<Iterator>(it);
 }
 /// be set to \c false. The value of each edge will be set exactly once.
 ///
 /// \return The cost of the found tree.
-template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
+template <class GR, class IN, class RET>
 inline
-typename EdgeCostMap::ValueType
+typename IN::ValueType
-kruskalEdgeMap(Graph const& G,
+kruskalEdgeMap(GR const& G,
-		 EdgeCostMap const& in,
+		 IN const& in,
-		 RetEdgeBoolMap &out) {
+		 RET &out) {
 return kruskal(G,
-		   KruskalMapInput<Graph,EdgeCostMap>(G,in),
+		   KruskalMapInput<GR,IN>(G,in),
 		   out);
 }
 /// \brief Wrapper function to kruskal().
 /// Input is from an edge map, output is an STL Sequence.
 ///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
-/// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.
+/// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
 /// 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.
+/// we can put its edges into a STL vector \c tree with a code like this.
 /// \code
 /// std::vector<Edge> 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.
 /// \endcode
 ///
 /// \return The cost of the found tree.
 ///
 /// \bug its name does not follow the coding style.
-template <typename Graph, typename EdgeCostMap, typename RetIterator>
+template <class GR, class IN, class RET>
 inline
-typename EdgeCostMap::ValueType
+typename IN::ValueType
-kruskalEdgeMap_IteratorOut(const Graph& G,
+kruskalEdgeMap_IteratorOut(const GR& G,
-			     const EdgeCostMap& in,
+			     const IN& in,
-			     RetIterator out)
+			     RET out)
 {
-SequenceOutput<RetIterator> _out(out);
+SequenceOutput<RET> _out(out);
 return kruskal(G,
-		   KruskalMapInput<Graph, EdgeCostMap>(G, in),
+		   KruskalMapInput<GR,IN>(G, in),
 		   _out);
 }
 /// @}

changeset 874	2195bc090dfe
parent 812	182d3a4d7ddb
child 881	a9f19f38970b