r951:ab21ca093745
Wed, 03 Mar 2010 21:48:29
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -120,96 +120,113 @@ |
| 120 | 120 |
|
| 121 | 121 |
Value _min_cut; |
| 122 | 122 |
|
| 123 | 123 |
typedef typename Digraph::template NodeMap<bool> MinCutMap; |
| 124 | 124 |
MinCutMap* _min_cut_map; |
| 125 | 125 |
|
| 126 | 126 |
Tolerance _tolerance; |
| 127 | 127 |
|
| 128 | 128 |
public: |
| 129 | 129 |
|
| 130 | 130 |
/// \brief Constructor |
| 131 | 131 |
/// |
| 132 | 132 |
/// Constructor of the algorithm class. |
| 133 | 133 |
HaoOrlin(const Digraph& graph, const CapacityMap& capacity, |
| 134 | 134 |
const Tolerance& tolerance = Tolerance()) : |
| 135 | 135 |
_graph(graph), _capacity(&capacity), _flow(0), _source(), |
| 136 | 136 |
_node_num(), _first(), _last(), _next(0), _prev(0), |
| 137 | 137 |
_active(0), _bucket(0), _dormant(), _sets(), _highest(), |
| 138 | 138 |
_excess(0), _source_set(0), _min_cut(), _min_cut_map(0), |
| 139 | 139 |
_tolerance(tolerance) {}
|
| 140 | 140 |
|
| 141 | 141 |
~HaoOrlin() {
|
| 142 | 142 |
if (_min_cut_map) {
|
| 143 | 143 |
delete _min_cut_map; |
| 144 | 144 |
} |
| 145 | 145 |
if (_source_set) {
|
| 146 | 146 |
delete _source_set; |
| 147 | 147 |
} |
| 148 | 148 |
if (_excess) {
|
| 149 | 149 |
delete _excess; |
| 150 | 150 |
} |
| 151 | 151 |
if (_next) {
|
| 152 | 152 |
delete _next; |
| 153 | 153 |
} |
| 154 | 154 |
if (_prev) {
|
| 155 | 155 |
delete _prev; |
| 156 | 156 |
} |
| 157 | 157 |
if (_active) {
|
| 158 | 158 |
delete _active; |
| 159 | 159 |
} |
| 160 | 160 |
if (_bucket) {
|
| 161 | 161 |
delete _bucket; |
| 162 | 162 |
} |
| 163 | 163 |
if (_flow) {
|
| 164 | 164 |
delete _flow; |
| 165 | 165 |
} |
| 166 | 166 |
} |
| 167 | 167 |
|
| 168 |
/// \brief Set the tolerance used by the algorithm. |
|
| 169 |
/// |
|
| 170 |
/// This function sets the tolerance object used by the algorithm. |
|
| 171 |
/// \return <tt>(*this)</tt> |
|
| 172 |
HaoOrlin& tolerance(const Tolerance& tolerance) {
|
|
| 173 |
_tolerance = tolerance; |
|
| 174 |
return *this; |
|
| 175 |
} |
|
| 176 |
|
|
| 177 |
/// \brief Returns a const reference to the tolerance. |
|
| 178 |
/// |
|
| 179 |
/// This function returns a const reference to the tolerance object |
|
| 180 |
/// used by the algorithm. |
|
| 181 |
const Tolerance& tolerance() const {
|
|
| 182 |
return _tolerance; |
|
| 183 |
} |
|
| 184 |
|
|
| 168 | 185 |
private: |
| 169 | 186 |
|
| 170 | 187 |
void activate(const Node& i) {
|
| 171 | 188 |
(*_active)[i] = true; |
| 172 | 189 |
|
| 173 | 190 |
int bucket = (*_bucket)[i]; |
| 174 | 191 |
|
| 175 | 192 |
if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; |
| 176 | 193 |
//unlace |
| 177 | 194 |
(*_next)[(*_prev)[i]] = (*_next)[i]; |
| 178 | 195 |
if ((*_next)[i] != INVALID) {
|
| 179 | 196 |
(*_prev)[(*_next)[i]] = (*_prev)[i]; |
| 180 | 197 |
} else {
|
| 181 | 198 |
_last[bucket] = (*_prev)[i]; |
| 182 | 199 |
} |
| 183 | 200 |
//lace |
| 184 | 201 |
(*_next)[i] = _first[bucket]; |
| 185 | 202 |
(*_prev)[_first[bucket]] = i; |
| 186 | 203 |
(*_prev)[i] = INVALID; |
| 187 | 204 |
_first[bucket] = i; |
| 188 | 205 |
} |
| 189 | 206 |
|
| 190 | 207 |
void deactivate(const Node& i) {
|
| 191 | 208 |
(*_active)[i] = false; |
| 192 | 209 |
int bucket = (*_bucket)[i]; |
| 193 | 210 |
|
| 194 | 211 |
if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; |
| 195 | 212 |
|
| 196 | 213 |
//unlace |
| 197 | 214 |
(*_prev)[(*_next)[i]] = (*_prev)[i]; |
| 198 | 215 |
if ((*_prev)[i] != INVALID) {
|
| 199 | 216 |
(*_next)[(*_prev)[i]] = (*_next)[i]; |
| 200 | 217 |
} else {
|
| 201 | 218 |
_first[bucket] = (*_next)[i]; |
| 202 | 219 |
} |
| 203 | 220 |
//lace |
| 204 | 221 |
(*_prev)[i] = _last[bucket]; |
| 205 | 222 |
(*_next)[_last[bucket]] = i; |
| 206 | 223 |
(*_next)[i] = INVALID; |
| 207 | 224 |
_last[bucket] = i; |
| 208 | 225 |
} |
| 209 | 226 |
|
| 210 | 227 |
void addItem(const Node& i, int bucket) {
|
| 211 | 228 |
(*_bucket)[i] = bucket; |
| 212 | 229 |
if (_last[bucket] != INVALID) {
|
| 213 | 230 |
(*_prev)[i] = _last[bucket]; |
| 214 | 231 |
(*_next)[_last[bucket]] = i; |
| 215 | 232 |
(*_next)[i] = INVALID; |
0 comments (0 inline)