lemon-main: comparison lemon/edmonds

equal deleted inserted replaced

-:9208189a86fa
+:5a870c40bfd8
 ///
 /// The type of the map that stores the arc capacities.
 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 typedef CAP CapacityMap;
-/// \brief The type of the length of the arcs.
+/// \brief The type of the flow values.
 typedef typename CapacityMap::Value Value;
-/// \brief The map type that stores the flow values.
+/// \brief The type of the map that stores the flow values.
 ///
-/// The map type that stores the flow values.
+/// The type of the map that stores the flow values.
 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+#ifdef DOXYGEN
+typedef GR::ArcMap<Value> FlowMap;
+#else
 typedef typename Digraph::template ArcMap<Value> FlowMap;
+#endif
 /// \brief Instantiates a FlowMap.
 ///
 /// This function instantiates a \ref FlowMap.
-/// \param digraph The digraph, to which we would like to define the flow map.
+/// \param digraph The digraph for which we would like to define
+/// the flow map.
 static FlowMap* createFlowMap(const Digraph& digraph) {
 return new FlowMap(digraph);
 }
 /// \brief The tolerance used by the algorithm
 /// \ingroup max_flow
 ///
 /// \brief Edmonds-Karp algorithms class.
 ///
 /// This class provides an implementation of the \e Edmonds-Karp \e
-/// algorithm producing a flow of maximum value in directed
+/// algorithm producing a \ref max_flow "flow of maximum value" in a
-/// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
+/// digraph \ref clrs01algorithms, \ref amo93networkflows,
-/// algorithm but it has an advantage of the step-by-step execution
+/// \ref edmondskarp72theoretical.
+/// The Edmonds-Karp algorithm is slower than the Preflow
+/// algorithm, but it has an advantage of the step-by-step execution
 /// control with feasible flow solutions. The \e source node, the \e
 /// target node, the \e capacity of the arcs and the \e starting \e
 /// flow value of the arcs should be passed to the algorithm
 /// through the constructor.
 ///
 /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
-/// worst case.  Always try the preflow algorithm instead of this if
+/// worst case. Always try the Preflow algorithm instead of this if
 /// you just want to compute the optimal flow.
 ///
-/// \param GR The digraph type the algorithm runs on.
+/// \tparam GR The type of the digraph the algorithm runs on.
-/// \param CAP The capacity map type.
+/// \tparam CAP The type of the capacity map. The default map
-/// \param TR Traits class to set various data types used by
+/// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
-/// the algorithm.  The default traits class is \ref
+/// \tparam TR The traits class that defines various types used by the
-/// EdmondsKarpDefaultTraits.  See \ref EdmondsKarpDefaultTraits for the
+/// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
-/// documentation of a Edmonds-Karp traits class.
+/// "EdmondsKarpDefaultTraits<GR, CAP>".
+/// In most cases, this parameter should not be set directly,
+/// consider to use the named template parameters instead.
 #ifdef DOXYGEN
 template <typename GR, typename CAP, typename TR>
 #else
 template <typename GR,
 typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
 #endif
 class EdmondsKarp {
 public:
+/// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
 typedef TR Traits;
+/// The type of the digraph the algorithm runs on.
 typedef typename Traits::Digraph Digraph;
+/// The type of the capacity map.
 typedef typename Traits::CapacityMap CapacityMap;
+/// The type of the flow values.
 typedef typename Traits::Value Value;
+/// The type of the flow map.
 typedef typename Traits::FlowMap FlowMap;
+/// The type of the tolerance.
 typedef typename Traits::Tolerance Tolerance;
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 template <typename T>
 struct DefFlowMapTraits : public Traits {
 typedef T FlowMap;
 static FlowMap *createFlowMap(const Digraph&) {
-	LEMON_ASSERT(false,"Uninitialized parameter.");
+	LEMON_ASSERT(false, "FlowMap is not initialized");
 return 0;
 }
 };
 /// \brief \ref named-templ-param "Named parameter" for setting
 /// \ref named-templ-param "Named parameter" for setting FlowMap
 /// type
 template <typename T>
 struct DefFlowMap
 : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
 typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
 Create;
 };
 /// @}
 protected:
 EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
 		Node source, Node target)
 : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
 	_flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
 {
-LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes.");
+LEMON_ASSERT(_source != _target,
+"Flow source and target are the same nodes.");
 }
 /// \brief Destructor.
 ///
 /// Destructor.
 }
 /// \brief Sets the capacity map.
 ///
 /// Sets the capacity map.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 EdmondsKarp& capacityMap(const CapacityMap& map) {
 _capacity = &map;
 return *this;
 }
 /// \brief Sets the flow map.
 ///
 /// Sets the flow map.
-/// \return \c (*this)
+/// If you don't use this function before calling \ref run() or
+/// \ref init(), an instance will be allocated automatically.
+/// The destructor deallocates this automatically allocated map,
+/// of course.
+/// \return <tt>(*this)</tt>
 EdmondsKarp& flowMap(FlowMap& map) {
 if (_local_flow) {
 	delete _flow;
 	_local_flow = false;
 }
 _flow = &map;
 return *this;
 }
-/// \brief Returns the flow map.
-///
-/// \return The flow map.
-const FlowMap& flowMap() const {
-return *_flow;
-}
 /// \brief Sets the source node.
 ///
 /// Sets the source node.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 EdmondsKarp& source(const Node& node) {
 _source = node;
 return *this;
 }
 /// \brief Sets the target node.
 ///
 /// Sets the target node.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 EdmondsKarp& target(const Node& node) {
 _target = node;
 return *this;
 }
 /// \brief Sets the tolerance used by algorithm.
 ///
 /// Sets the tolerance used by algorithm.
+/// \return <tt>(*this)</tt>
 EdmondsKarp& tolerance(const Tolerance& tolerance) {
 _tolerance = tolerance;
 return *this;
 }
-/// \brief Returns the tolerance used by algorithm.
+/// \brief Returns a const reference to the tolerance.
 ///
-/// Returns the tolerance used by algorithm.
+/// Returns a const reference to the tolerance object used by
+/// the algorithm.
 const Tolerance& tolerance() const {
 return _tolerance;
 }
 /// \name Execution control
-/// The simplest way to execute the
+/// The simplest way to execute the algorithm is to use \ref run().\n
-/// algorithm is to use the \c run() member functions.
+/// If you need better control on the initial solution or the execution,
-/// \n
+/// you have to call one of the \ref init() functions first, then
-/// If you need more control on initial solution or
+/// \ref start() or multiple times the \ref augment() function.
-/// execution then you have to call one \ref init() function and then
-/// the start() or multiple times the \c augment() member function.
 ///@{
-/// \brief Initializes the algorithm
+/// \brief Initializes the algorithm.
 ///
-/// Sets the flow to empty flow.
+/// Initializes the internal data structures and sets the initial
+/// flow to zero on each arc.
 void init() {
 createStructures();
 for (ArcIt it(_graph); it != INVALID; ++it) {
 _flow->set(it, 0);
 }
 _flow_value = 0;
 }
-/// \brief Initializes the algorithm
+/// \brief Initializes the algorithm using the given flow map.
 ///
-/// Initializes the flow to the \c flowMap. The \c flowMap should
+/// Initializes the internal data structures and sets the initial
-/// contain a feasible flow, ie. in each node excluding the source
+/// flow to the given \c flowMap. The \c flowMap should
-/// and the target the incoming flow should be equal to the
+/// contain a feasible flow, i.e. at each node excluding the source
+/// and the target, the incoming flow should be equal to the
 /// outgoing flow.
 template <typename FlowMap>
 void flowInit(const FlowMap& flowMap) {
 createStructures();
 for (ArcIt e(_graph); e != INVALID; ++e) {
 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
 _flow_value -= (*_flow)[jt];
 }
 }
-/// \brief Initializes the algorithm
+/// \brief Initializes the algorithm using the given flow map.
 ///
-/// Initializes the flow to the \c flowMap. The \c flowMap should
+/// Initializes the internal data structures and sets the initial
-/// contain a feasible flow, ie. in each node excluding the source
+/// flow to the given \c flowMap. The \c flowMap should
-/// and the target the incoming flow should be equal to the
+/// contain a feasible flow, i.e. at each node excluding the source
-/// outgoing flow.
+/// and the target, the incoming flow should be equal to the
-/// \return %False when the given flowMap does not contain
+/// outgoing flow.
+/// \return \c false when the given \c flowMap does not contain a
 /// feasible flow.
 template <typename FlowMap>
 bool checkedFlowInit(const FlowMap& flowMap) {
 createStructures();
 for (ArcIt e(_graph); e != INVALID; ++e) {
 _flow_value -= (*_flow)[jt];
 }
 return true;
 }
-/// \brief Augment the solution on an arc shortest path.
+/// \brief Augments the solution along a shortest path.
 ///
-/// Augment the solution on an arc shortest path. It searches an
+/// Augments the solution along a shortest path. This function searches a
-/// arc shortest path between the source and the target
+/// shortest path between the source and the target
-/// in the residual digraph by the bfs algoritm.
+/// in the residual digraph by the Bfs algoritm.
 /// Then it increases the flow on this path with the minimal residual
-/// capacity on the path. If there is no such path it gives back
+/// capacity on the path. If there is no such path, it gives back
 /// false.
-/// \return %False when the augmenting didn't success so the
+/// \return \c false when the augmenting did not success, i.e. the
 /// current flow is a feasible and optimal solution.
 bool augment() {
 for (NodeIt n(_graph); n != INVALID; ++n) {
 	_pred->set(n, INVALID);
 }
 }
 }
 /// \brief Executes the algorithm
 ///
-/// It runs augmenting phases until the optimal solution is reached.
+/// Executes the algorithm by performing augmenting phases until the
+/// optimal solution is reached.
+/// \pre One of the \ref init() functions must be called before
+/// using this function.
 void start() {
 while (augment()) {}
 }
 /// \brief Runs the algorithm.
 ///
-/// It is just a shorthand for:
+/// Runs the Edmonds-Karp algorithm.
-///
+/// \note ek.run() is just a shortcut of the following code.
 ///\code
 /// ek.init();
 /// ek.start();
 ///\endcode
 void run() {
 /// @}
 /// \name Query Functions
 /// The result of the Edmonds-Karp algorithm can be obtained using these
 /// functions.\n
-/// Before the use of these functions,
+/// Either \ref run() or \ref start() should be called before using them.
-/// either run() or start() must be called.
 ///@{
 /// \brief Returns the value of the maximum flow.
 ///
-/// Returns the value of the maximum flow by returning the excess
+/// Returns the value of the maximum flow found by the algorithm.
-/// of the target node \c t.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 Value flowValue() const {
 return _flow_value;
 }
+/// \brief Returns the flow value on the given arc.
-/// \brief Returns the flow on the arc.
+///
-///
+/// Returns the flow value on the given arc.
-/// Sets the \c flowMap to the flow on the arcs.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 Value flow(const Arc& arc) const {
 return (*_flow)[arc];
 }
-/// \brief Returns true when the node is on the source side of minimum cut.
+/// \brief Returns a const reference to the flow map.
 ///
+/// Returns a const reference to the arc map storing the found flow.
-/// Returns true when the node is on the source side of minimum
+///
-/// cut.
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
+const FlowMap& flowMap() const {
+return *_flow;
+}
+/// \brief Returns \c true when the node is on the source side of the
+/// minimum cut.
+///
+/// Returns true when the node is on the source side of the found
+/// minimum cut.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 bool minCut(const Node& node) const {
 return ((*_pred)[node] != INVALID) or node == _source;
 }
-/// \brief Returns a minimum value cut.
+/// \brief Gives back a minimum value cut.
 ///
-/// Sets \c cutMap to the characteristic vector of a minimum value cut.
+/// Sets \c cutMap to the characteristic vector of a minimum value
+/// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
+/// node map with \c bool (or convertible) value type.
+///
+/// \note This function calls \ref minCut() for each node, so it runs in
+/// O(n) time.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 template <typename CutMap>
 void minCutMap(CutMap& cutMap) const {
 for (NodeIt n(_graph); n != INVALID; ++n) {
 	cutMap.set(n, (*_pred)[n] != INVALID);
 }

changeset 1057	6a8a688eacf6
parent 1056	92a884824429
child 1058	2f00ef323c2e