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), |