RhodeCode

  /// a graph.

  ///

  /// This function runs Kruskal's algorithm to find a minimum cost

  /// spanning tree.

  /// Due to some C++ hacking, it accepts various input and output types.

  ///

  /// \param g The graph the algorithm runs on.

  /// It can be either \ref concepts::Digraph "directed" or

  /// \ref concepts::Graph "undirected".

  /// If the graph is directed, the algorithm consider it to be

  /// undirected by disregarding the direction of the arcs.

  ///

  /// \param in This object is used to describe the arc/edge costs.

  /// It can be one of the following choices.

  /// - An STL compatible 'Forward Container' with

  /// <tt>std::pair<GR::Arc,X></tt> or

  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where

  /// \c X is the type of the costs. The pairs indicates the arcs/edges

  /// along with the assigned cost. <em>They must be in a

  /// cost-ascending order.</em>

  /// - Any readable arc/edge map. The values of the map indicate the

  /// arc/edge costs.

  ///

  /// \retval out Here we also have a choice.

  /// - It can be a writable \c bool arc/edge map. After running the

  /// algorithm it will contain the found minimum cost spanning

  /// tree: the value of an arc/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 arc/edge will be set exactly once.

  /// - It can also be an iteraror of an STL Container with

  /// <tt>GR::Arc</tt> or <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 arcs, then we can

  /// put its arcs into an STL vector \c tree with a code like this.

  ///\code

  /// std::vector<Arc> tree(53);

  /// kruskal(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<Arc> tree;

  /// kruskal(g,cost,std::back_inserter(tree));

  ///\endcode

  ///

  /// \return The total cost of the found spanning tree.

  ///

#ifdef DOXYGEN

  template <class Graph, class In, class Out>

  Value kruskal(GR const& g, const In& in, Out& out)

#else

  template <class Graph, class In, class Out>

  inline typename _kruskal_bits::KruskalValueSelector<In>::Value

  kruskal(const Graph& graph, const In& in, Out& out)

#endif

  {

    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::

      kruskal(graph, in, out);

  }

  template <class Graph, class In, class Out>

  inline typename _kruskal_bits::KruskalValueSelector<In>::Value

  kruskal(const Graph& graph, const In& in, const Out& out)

  {

    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::

      kruskal(graph, in, out);

  }

} //namespace lemon

#endif //LEMON_KRUSKAL_H