47 #include <bfs_iterator.h> |
47 #include <bfs_iterator.h> |
48 #include <invalid.h> |
48 #include <invalid.h> |
49 #include <maps.h> |
49 #include <maps.h> |
50 #include <for_each_macros.h> |
50 #include <for_each_macros.h> |
51 |
51 |
|
52 /// \file |
|
53 /// \brief Dimacs file format reader. |
52 |
54 |
53 namespace hugo { |
55 namespace hugo { |
54 |
56 |
55 ///\author Marton Makai, Jacint Szabo |
57 |
|
58 // ///\author Marton Makai, Jacint Szabo |
|
59 /// A class for computing max flows and related quantities. |
56 template <typename Graph, typename Num, |
60 template <typename Graph, typename Num, |
57 typename CapMap=typename Graph::template EdgeMap<Num>, |
61 typename CapMap=typename Graph::template EdgeMap<Num>, |
58 typename FlowMap=typename Graph::template EdgeMap<Num> > |
62 typename FlowMap=typename Graph::template EdgeMap<Num> > |
59 class MaxFlow { |
63 class MaxFlow { |
60 |
64 |
100 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} |
104 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} |
101 |
105 |
102 /// A max flow algorithm is run. |
106 /// A max flow algorithm is run. |
103 ///\pre the flow have to be 0 at the beginning. |
107 ///\pre the flow have to be 0 at the beginning. |
104 void run() { |
108 void run() { |
105 preflow( ZERO_FLOW ); |
109 preflow(ZERO_FLOW); |
106 } |
110 } |
107 |
111 |
108 /// A preflow algorithm is run. |
112 /// A preflow algorithm is run. |
109 ///\pre The initial edge-map have to be a |
113 ///\pre The initial edge-map have to be a |
110 /// zero flow if \c fe is \c ZERO_FLOW, |
114 /// zero flow if \c fe is \c ZERO_FLOW, |
111 /// a flow if \c fe is \c GEN_FLOW, |
115 /// a flow if \c fe is \c GEN_FLOW, |
112 /// and a pre-flow it is \c PREFLOW. |
116 /// and a pre-flow it is \c PREFLOW. |
113 void preflow( flowEnum fe ) { |
117 void preflow(flowEnum fe) { |
114 preflowPhase0(fe); |
118 preflowPhase0(fe); |
115 preflowPhase1(); |
119 preflowPhase1(); |
116 } |
120 } |
117 |
121 |
118 /// Run the first phase of preflow, starting from a 0 flow, from a flow, |
122 /// Run the first phase of preflow, starting from a 0 flow, from a flow, |