8 #include <hugo/graph_wrapper.h> |
8 #include <hugo/graph_wrapper.h> |
9 #include <hugo/invalid.h> |
9 #include <hugo/invalid.h> |
10 #include <hugo/maps.h> |
10 #include <hugo/maps.h> |
11 |
11 |
12 /// \file |
12 /// \file |
13 /// \ingroup galgs |
13 /// \ingroup flowalgs |
14 |
14 |
15 namespace hugo { |
15 namespace hugo { |
16 |
16 |
17 /// \addtogroup galgs |
17 /// \addtogroup flowalgs |
18 /// @{ |
18 /// @{ |
|
19 |
19 ///Maximum flow algorithms class. |
20 ///Maximum flow algorithms class. |
20 |
21 |
21 ///This class provides various algorithms for finding a flow of |
22 ///This class provides various algorithms for finding a flow of |
22 ///maximum value in a directed graph. The \e source node, the \e |
23 ///maximum value in a directed graph. The \e source node, the \e |
23 ///target node, the \e capacity of the edges and the \e starting \e |
24 ///target node, the \e capacity of the edges and the \e starting \e |
24 ///flow value of the edges should be passed to the algorithm through the |
25 ///flow value of the edges should be passed to the algorithm through the |
25 ///constructor. It is possible to change these quantities using the |
26 ///constructor. It is possible to change these quantities using the |
26 ///functions \ref setSource, \ref setTarget, \ref setCap and |
27 ///functions \ref setSource, \ref setTarget, \ref setCap and |
27 ///\ref setFlow. Before any subsequent runs of any algorithm of |
28 ///\ref setFlow. Before any subsequent runs of any algorithm of |
28 ///the class \ref setFlow should be called. |
29 ///the class \ref setFlow should be called. |
29 |
30 /// |
30 ///After running an algorithm of the class, the actual flow value |
31 ///After running an algorithm of the class, the actual flow value |
31 ///can be obtained by calling \ref flowValue(). The minimum |
32 ///can be obtained by calling \ref flowValue(). The minimum |
32 ///value cut can be written into a \c node map of \c bools by |
33 ///value cut can be written into a \c node map of \c bools by |
33 ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes |
34 ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes |
34 ///the inclusionwise minimum and maximum of the minimum value |
35 ///the inclusionwise minimum and maximum of the minimum value |
35 ///cuts, resp.) |
36 ///cuts, resp.) |
|
37 /// |
36 ///\param Graph The directed graph type the algorithm runs on. |
38 ///\param Graph The directed graph type the algorithm runs on. |
37 ///\param Num The number type of the capacities and the flow values. |
39 ///\param Num The number type of the capacities and the flow values. |
38 ///\param CapMap The capacity map type. |
40 ///\param CapMap The capacity map type. |
39 ///\param FlowMap The flow map type. |
41 ///\param FlowMap The flow map type. |
|
42 /// |
40 ///\author Marton Makai, Jacint Szabo |
43 ///\author Marton Makai, Jacint Szabo |
41 template <typename Graph, typename Num, |
44 template <typename Graph, typename Num, |
42 typename CapMap=typename Graph::template EdgeMap<Num>, |
45 typename CapMap=typename Graph::template EdgeMap<Num>, |
43 typename FlowMap=typename Graph::template EdgeMap<Num> > |
46 typename FlowMap=typename Graph::template EdgeMap<Num> > |
44 class MaxFlow { |
47 class MaxFlow { |