lemon-0.x: comparison lemon/hao

equal deleted inserted replaced

-:05e17bc2435d
+:26bac530db45
 */
 #ifndef LEMON_HAO_ORLIN_H
 #define LEMON_HAO_ORLIN_H
+#include <cassert>
 #include <vector>
 #include <queue>
+#include <list>
 #include <limits>
 #include <lemon/maps.h>
 #include <lemon/graph_utils.h>
 #include <lemon/graph_adaptor.h>
 #include <lemon/iterable_maps.h>
 /// \file
 /// \ingroup flowalgs
 /// \brief Implementation of the Hao-Orlin algorithm.
 ///
 FlowMap, Tolerance> OutResGraph;
 typedef typename OutResGraph::Edge OutResEdge;
 OutResGraph* _out_res_graph;
-typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
-OutCurrentEdgeMap* _out_current_edge;
 typedef RevGraphAdaptor<const Graph> RevGraph;
 RevGraph* _rev_graph;
 typedef ResGraphAdaptor<const RevGraph, Value, CapacityMap,
 FlowMap, Tolerance> InResGraph;
 typedef typename InResGraph::Edge InResEdge;
 InResGraph* _in_res_graph;
-typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
-InCurrentEdgeMap* _in_current_edge;
 typedef IterableBoolMap<Graph, Node> WakeMap;
 WakeMap* _wake;
 typedef typename Graph::template NodeMap<int> DistMap;
 /// Constructor of the algorithm class.
 HaoOrlin(const Graph& graph, const CapacityMap& capacity,
 const Tolerance& tolerance = Tolerance()) :
 _graph(&graph), _capacity(&capacity),
 _preflow(0), _source(), _target(),
-_out_res_graph(0), _out_current_edge(0),
+_out_res_graph(0), _rev_graph(0), _in_res_graph(0),
-_rev_graph(0), _in_res_graph(0), _in_current_edge(0),
 _wake(0),_dist(0), _excess(0), _source_set(0),
 _highest_active(), _active_nodes(), _dormant_max(), _dormant(),
 _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}
 ~HaoOrlin() {
 if (_min_cut_map) {
 delete _min_cut_map;
 }
-if (_in_current_edge) {
-delete _in_current_edge;
-}
 if (_in_res_graph) {
 delete _in_res_graph;
 }
 if (_rev_graph) {
 delete _rev_graph;
 }
-if (_out_current_edge) {
-delete _out_current_edge;
-}
 if (_out_res_graph) {
 delete _out_res_graph;
 }
 if (_source_set) {
 delete _source_set;
 }
 }
 private:
-template <typename ResGraph, typename EdgeMap>
+template <typename ResGraph>
-void findMinCut(const Node& target, bool out,
+void findMinCut(const Node& target, bool out, ResGraph& res_graph) {
-ResGraph& res_graph, EdgeMap& current_edge) {
+typedef typename Graph::Node Node;
 typedef typename ResGraph::Edge ResEdge;
 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
 for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
 (*_preflow)[it] = 0;
 for (NodeIt it(*_graph); it != INVALID; ++it) {
 (*_wake)[it] = true;
 (*_dist)[it] = 1;
 (*_excess)[it] = 0;
 (*_source_set)[it] = false;
+}
-res_graph.firstOut(current_edge[it], it);
-}
+_dormant[0].push_front(_source);
+(*_source_set)[_source] = true;
+_dormant_max = 0;
+(*_wake)[_source] = false;
+_level_size[0] = 1;
+_level_size[1] = _node_num - 1;
 _target = target;
 (*_dist)[target] = 0;
 for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
 Value delta = res_graph.rescap(it);
-if (!_tolerance.positive(delta)) continue;
+(*_excess)[_source] -= delta;
-(*_excess)[res_graph.source(it)] -= delta;
 res_graph.augment(it, delta);
 Node a = res_graph.target(it);
-if (!_tolerance.positive((*_excess)[a]) &&
+if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
-(*_wake)[a] && a != _target) {
 _active_nodes[(*_dist)[a]].push_front(a);
 if (_highest_active < (*_dist)[a]) {
 _highest_active = (*_dist)[a];
 }
 }
 (*_excess)[a] += delta;
 }
-_dormant[0].push_front(_source);
-(*_source_set)[_source] = true;
-_dormant_max = 0;
-(*_wake)[_source] = false;
-_level_size[0] = 1;
-_level_size[1] = _node_num - 1;
 do {
 	Node n;
 	while ((n = findActiveNode()) != INVALID) {
-	  ResEdge e;
+	  for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
-	  while (_tolerance.positive((*_excess)[n]) &&
+Node a = res_graph.target(e);
-(e = findAdmissibleEdge(n, res_graph, current_edge))
+if ((*_dist)[a] >= (*_dist)[n] || !(*_wake)[a]) continue;
-!= INVALID){
+	    Value delta = res_graph.rescap(e);
-	    Value delta;
+	    if (_tolerance.positive((*_excess)[n] - delta)) {
-	    if ((*_excess)[n] < res_graph.rescap(e)) {
+(*_excess)[n] -= delta;
+	    } else {
 	      delta = (*_excess)[n];
-	    } else {
+(*_excess)[n] = 0;
-	      delta = res_graph.rescap(e);
-	      res_graph.nextOut(current_edge[n]);
 	    }
-if (!_tolerance.positive(delta)) continue;
 	    res_graph.augment(e, delta);
-	    (*_excess)[res_graph.source(e)] -= delta;
+	    if ((*_excess)[a] == 0 && a != _target) {
-	    Node a = res_graph.target(e);
-	    if (!_tolerance.positive((*_excess)[a]) && a != _target) {
 	      _active_nodes[(*_dist)[a]].push_front(a);
 	    }
 	    (*_excess)[a] += delta;
+if ((*_excess)[n] == 0) break;
 	  }
-	  if (_tolerance.positive((*_excess)[n])) {
+	  if ((*_excess)[n] != 0) {
-	    relabel(n, res_graph, current_edge);
+	    relabel(n, res_graph);
 }
 	}
 	Value current_value = cutValue(out);
 	if (_min_cut > current_value){
 	}
 } while (selectNewSink(res_graph));
 }
-template <typename ResGraph, typename EdgeMap>
+template <typename ResGraph>
-void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
+void relabel(const Node& n, ResGraph& res_graph) {
 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
 int k = (*_dist)[n];
 if (_level_size[k] == 1) {
 	++_dormant_max;
 	    (*_wake)[it] = false;
 	    _dormant[_dormant_max].push_front(it);
 	    --_level_size[(*_dist)[it]];
 	  }
 	}
-	--_highest_active;
+--_highest_active;
 } else {
 int new_dist = _node_num;
 for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
 Node t = res_graph.target(e);
 if ((*_wake)[t] && new_dist > (*_dist)[t]) {
 	  --_level_size[(*_dist)[n]];
 	  (*_dist)[n] = new_dist + 1;
 	  _highest_active = (*_dist)[n];
 	  _active_nodes[_highest_active].push_front(n);
 	  ++_level_size[(*_dist)[n]];
-	  res_graph.firstOut(current_edge[n], n);
 	}
 }
 }
 template <typename ResGraph>
 	}
 }
 if (wake_was_empty){
 	for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
-if (_tolerance.positive((*_excess)[it])) {
+if ((*_excess)[it] != 0 && it != _target) {
-	    if ((*_wake)[it] && it != _target) {
+_active_nodes[(*_dist)[it]].push_front(it);
-	      _active_nodes[(*_dist)[it]].push_front(it);
+if (_highest_active < (*_dist)[it]) {
-}
+_highest_active = (*_dist)[it];
-	    if (_highest_active < (*_dist)[it]) {
-	      _highest_active = (*_dist)[it];
 }
 	  }
 	}
 }
-for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
+Node n = old_target;
-	if (!(*_source_set)[res_graph.target(e)]) {
+for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e){
-Value delta = res_graph.rescap(e);
+Node a = res_graph.target(e);
-if (!_tolerance.positive(delta)) continue;
+	if (!(*_wake)[a]) continue;
-res_graph.augment(e, delta);
+Value delta = res_graph.rescap(e);
-(*_excess)[res_graph.source(e)] -= delta;
+res_graph.augment(e, delta);
-Node a = res_graph.target(e);
+(*_excess)[n] -= delta;
-if (!_tolerance.positive((*_excess)[a]) &&
+if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
-(*_wake)[a] && a != _target) {
+_active_nodes[(*_dist)[a]].push_front(a);
-_active_nodes[(*_dist)[a]].push_front(a);
+if (_highest_active < (*_dist)[a]) {
-if (_highest_active < (*_dist)[a]) {
+_highest_active = (*_dist)[a];
-_highest_active = (*_dist)[a];
-}
 }
-(*_excess)[a] += delta;
+}
-	}
+(*_excess)[a] += delta;
 }
 return true;
 }
 Node findActiveNode() {
 while (_highest_active > 0 && _active_nodes[_highest_active].empty()){
 	--_highest_active;
 }
 if( _highest_active > 0) {
 	Node n = _active_nodes[_highest_active].front();
 	_active_nodes[_highest_active].pop_front();
 	return n;
-} else {
-	return INVALID;
-}
-}
-template <typename ResGraph, typename EdgeMap>
-typename ResGraph::Edge findAdmissibleEdge(const Node& n,
-ResGraph& res_graph,
-EdgeMap& current_edge) {
-typedef typename ResGraph::Edge ResEdge;
-ResEdge e = current_edge[n];
-while (e != INVALID &&
-((*_dist)[n] <= (*_dist)[res_graph.target(e)] ||
-!(*_wake)[res_graph.target(e)])) {
-	res_graph.nextOut(e);
-}
-if (e != INVALID) {
-	current_edge[n] = e;
-	return e;
 } else {
 	return INVALID;
 }
 }
 _source_set = new SourceSetMap(*_graph);
 }
 if (!_out_res_graph) {
 _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
 }
-if (!_out_current_edge) {
-_out_current_edge = new OutCurrentEdgeMap(*_graph);
-}
 if (!_rev_graph) {
 _rev_graph = new RevGraph(*_graph);
 }
 if (!_in_res_graph) {
 _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
-}
-if (!_in_current_edge) {
-_in_current_edge = new InCurrentEdgeMap(*_graph);
 }
 if (!_min_cut_map) {
 _min_cut_map = new MinCutMap(*_graph);
 }
 /// \brief Calculates a minimum cut with \f$ source \f$ on the
 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X \f$
 ///  and minimal out-degree). The \c target is the initial target
 /// for the push-relabel algorithm.
 void calculateOut(const Node& target) {
-findMinCut(target, true, *_out_res_graph, *_out_current_edge);
+findMinCut(target, true, *_out_res_graph);
 }
 /// \brief Calculates a minimum cut with \f$ source \f$ on the
 /// sink-side.
 ///
 /// sink-side (i.e. a set \f$ X\subsetneq V
 /// \f$ with \f$ source \notin X \f$ and minimal out-degree).
 /// The \c target is the initial
 /// target for the push-relabel algorithm.
 void calculateIn(const Node& target) {
-findMinCut(target, false, *_in_res_graph, *_in_current_edge);
+findMinCut(target, false, *_in_res_graph);
 }
 /// \brief Runs the algorithm.
 ///
 /// Runs the algorithm. It finds nodes \c source and \c target

changeset 2360	72c7075ad5ba
parent 2275	ff46747676ed
child 2376	0ed45a6c74b1