lemon/edmonds_karp.h
changeset 2099 eb126f29038c
parent 2037 32e4bebee616
child 2113 48ec8161f9e1
equal deleted inserted replaced
2:c92c07e9345d 3:e1735429c330
    39   /// feasible flow solutions. The \e source node, the \e target node, the \e
    39   /// feasible flow solutions. The \e source node, the \e target node, the \e
    40   /// capacity of the edges and the \e starting \e flow value of the
    40   /// capacity of the edges and the \e starting \e flow value of the
    41   /// edges should be passed to the algorithm through the
    41   /// edges should be passed to the algorithm through the
    42   /// constructor.
    42   /// constructor.
    43   ///
    43   ///
    44   /// The time complexity of the algorithm is O(n * e^2) in worst case. 
    44   /// The time complexity of the algorithm is \f$ O(n * e^2) \f$ in
    45   /// Always try the preflow algorithm instead of this if you does not
    45   /// worst case.  Always try the preflow algorithm instead of this if
    46   /// have some additional reason than to compute the optimal flow which
    46   /// you does not have some additional reason than to compute the
    47   /// has O(n^3) time complexity.
    47   /// optimal flow which has \f$ O(n^3) \f$ time complexity.
    48   ///
    48   ///
    49   /// \param _Graph The directed graph type the algorithm runs on.
    49   /// \param _Graph The directed graph type the algorithm runs on.
    50   /// \param _Number The number type of the capacities and the flow values.
    50   /// \param _Number The number type of the capacities and the flow values.
    51   /// \param _CapacityMap The capacity map type.
    51   /// \param _CapacityMap The capacity map type.
    52   /// \param _FlowMap The flow map type.
    52   /// \param _FlowMap The flow map type.
    53   /// \param _Tolerance The tolerance class to handle computation problems.
    53   /// \param _Tolerance The tolerance class to handle computation problems.
    54   ///
    54   ///
    55   /// \author Balazs Dezso 
    55   /// \author Balazs Dezso 
       
    56 #ifdef DOXYGEN
       
    57   template <typename _Graph, typename _Number,
       
    58 	    typename _CapacityMap, typename _FlowMap, typename _Tolerance>
       
    59 #else
    56   template <typename _Graph, typename _Number,
    60   template <typename _Graph, typename _Number,
    57 	    typename _CapacityMap = typename _Graph::template EdgeMap<_Number>,
    61 	    typename _CapacityMap = typename _Graph::template EdgeMap<_Number>,
    58             typename _FlowMap = typename _Graph::template EdgeMap<_Number>,
    62             typename _FlowMap = typename _Graph::template EdgeMap<_Number>,
    59 	    typename _Tolerance = Tolerance<_Number> >
    63 	    typename _Tolerance = Tolerance<_Number> >
       
    64 #endif
    60   class EdmondsKarp {
    65   class EdmondsKarp {
    61   public:
    66   public:
    62 
    67 
    63     /// \brief \ref Exception for the case when the source equals the target.
    68     /// \brief \ref Exception for the case when the source equals the target.
    64     ///
    69     ///
   105     /// \param source The source node.
   110     /// \param source The source node.
   106     /// \param target The target node.
   111     /// \param target The target node.
   107     /// \param capacity The capacity of the edges. 
   112     /// \param capacity The capacity of the edges. 
   108     /// \param flow The flow of the edges. 
   113     /// \param flow The flow of the edges. 
   109     /// \param tolerance Tolerance class.
   114     /// \param tolerance Tolerance class.
   110     /// Except the graph, all of these parameters can be reset by
       
   111     /// calling \ref source, \ref target, \ref capacityMap and \ref
       
   112     /// flowMap, resp.
       
   113     EdmondsKarp(const Graph& graph, Node source, Node target,
   115     EdmondsKarp(const Graph& graph, Node source, Node target,
   114                 const CapacityMap& capacity, FlowMap& flow, 
   116                 const CapacityMap& capacity, FlowMap& flow, 
   115                 const Tolerance& tolerance = Tolerance())
   117                 const Tolerance& tolerance = Tolerance())
   116       : _graph(graph), _capacity(capacity), _flow(flow), 
   118       : _graph(graph), _capacity(capacity), _flow(flow), 
   117         _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance), 
   119         _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance), 
   237     }
   239     }
   238 
   240 
   239     /// \brief runs the algorithm.
   241     /// \brief runs the algorithm.
   240     /// 
   242     /// 
   241     /// It is just a shorthand for:
   243     /// It is just a shorthand for:
   242     /// \code 
   244     ///
       
   245     ///\code 
   243     /// ek.init();
   246     /// ek.init();
   244     /// ek.start();
   247     /// ek.start();
   245     /// \endcode
   248     ///\endcode
   246     void run() {
   249     void run() {
   247       init();
   250       init();
   248       start();
   251       start();
   249     }
   252     }
   250 
   253