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

equal deleted inserted replaced

-:cd6f5a0541cd
+:590638a192ed
 /// @{
 /// 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
+/// \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<GR::Edge,X></tt> as its <tt>value_type</tt>,
 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
 /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
 template <class GR, class IN, class OUT>
 typename IN::value_type::second_type
-kruskal(GR const& G, IN const& in,
+kruskal(GR const& g, IN const& in,
 		 OUT& out)
 {
 typedef typename IN::value_type::second_type EdgeCost;
 typedef typename GR::template NodeMap<int> NodeIntMap;
 typedef typename GR::Node Node;
-NodeIntMap comp(G, -1);
+NodeIntMap comp(g, -1);
 UnionFind<Node,NodeIntMap> uf(comp);
 EdgeCost tot_cost = 0;
 for (typename IN::const_iterator p = in.begin();
 	 p!=in.end(); ++p ) {
-if ( uf.join(G.target((*p).first),
+if ( uf.join(g.target((*p).first),
-		   G.source((*p).first)) ) {
+		   g.source((*p).first)) ) {
 	out.set((*p).first, true);
 	tot_cost += (*p).second;
 }
 else {
 	out.set((*p).first, false);
 /// Helper class for calling kruskal with output maps constructed
 /// on-the-fly.
 ///
 /// A typical examle is the following call:
-/// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
+/// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
 /// Here, the third argument is a temporary object (which wraps around an
 /// iterator with a writable bool map interface), and thus by rules of C++
 /// is a \c const object. To enable call like this exist this class and
 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
 /// third argument.
 };
 template <class GR, class IN, class OUT>
 inline
 typename IN::value_type::second_type
-kruskal(GR const& G, IN const& edges, OUT const& out_map)
+kruskal(GR const& g, IN const& edges, OUT const& out_map)
 {
 NonConstMapWr<OUT> map_wr(out_map);
-return kruskal(G, edges, map_wr);
+return kruskal(g, edges, map_wr);
 }
 /* ** ** Input-objects ** ** */
 /// Kruskal's input source.
 }
 };
 template<class _GR>
 typename enable_if<typename _GR::UndirTag,void>::type
-fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0)
+fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
 {
-for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e)
+for(typename GR::UndirEdgeIt e(g);e!=INVALID;++e)
 	push_back(value_type(typename GR::Edge(e,true), m[e]));
 }
 template<class _GR>
 typename disable_if<typename _GR::UndirTag,void>::type
-fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1)
+fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
 {
-for(typename GR::EdgeIt e(G);e!=INVALID;++e)
+for(typename GR::EdgeIt e(g);e!=INVALID;++e)
 	push_back(value_type(e, m[e]));
 }
 public:
 void sort() {
 std::sort(this->begin(), this->end(), comparePair());
 }
-KruskalMapInput(GR const& G, Map const& m) {
+KruskalMapInput(GR const& g, Map const& m) {
-fillWithEdges(G,m);
+fillWithEdges(g,m);
 sort();
 }
 };
 /// Creates a KruskalMapInput object for \ref kruskal()
 /// 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 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
 ///
 ///\return An appropriate input source for \ref kruskal().
 ///
 template<class GR, class Map>
 inline
-KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
+KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
 {
-return KruskalMapInput<GR,Map>(G,m);
+return KruskalMapInput<GR,Map>(g,m);
 }
 /* ** ** Output-objects: simple writable bool maps ** ** */
 /// 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 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
 /// \return The cost of the found tree.
 template <class GR, class IN, class RET>
 inline
 typename IN::Value
-kruskalEdgeMap(GR const& G,
+kruskalEdgeMap(GR const& g,
 		 IN const& in,
 		 RET &out) {
-return kruskal(G,
+return kruskal(g,
-		   KruskalMapInput<GR,IN>(G,in),
+		   KruskalMapInput<GR,IN>(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 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
 /// <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
+/// 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 STL vector \c tree with a code like this.
 /// \code
 /// std::vector<Edge> tree(53);
-/// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
+/// 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<Edge> tree;
-/// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(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 <class GR, class IN, class RET>
 inline
 typename IN::Value
-kruskalEdgeMap_IteratorOut(const GR& G,
+kruskalEdgeMap_IteratorOut(const GR& g,
 			     const IN& in,
 			     RET out)
 {
 KruskalSequenceOutput<RET> _out(out);
-return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
+return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
 }
 /// @}
 } //namespace lemon

changeset 1549	8bf39d55b1db
parent 1449	ac7e995e47e2
child 1555	48769ac7ec32