deba@2211: /* -*- C++ -*-
deba@2211:  * lemon/hao_orlin.h - Part of LEMON, a generic C++ optimization library
deba@2211:  *
deba@2211:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2211:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2211:  *
deba@2211:  * Permission to use, modify and distribute this software is granted
deba@2211:  * provided that this copyright notice appears in all copies. For
deba@2211:  * precise terms see the accompanying LICENSE file.
deba@2211:  *
deba@2211:  * This software is provided "AS IS" with no warranty of any kind,
deba@2211:  * express or implied, and with no claim as to its suitability for any
deba@2211:  * purpose.
deba@2211:  *
deba@2211:  */
deba@2211: 
deba@2211: #ifndef LEMON_HAO_ORLIN_H
deba@2211: #define LEMON_HAO_ORLIN_H
deba@2211: 
deba@2211: #include <vector>
deba@2211: #include <queue>
deba@2211: #include <limits>
deba@2211: 
deba@2211: #include <lemon/maps.h>
deba@2211: #include <lemon/graph_utils.h>
deba@2211: #include <lemon/graph_adaptor.h>
deba@2211: #include <lemon/iterable_maps.h>
deba@2211:  
deba@2211: 
deba@2211: /// \file
deba@2211: /// \ingroup flowalgs
deba@2211: /// Implementation of the Hao-Orlin algorithms class for testing network 
deba@2211: /// reliability.
deba@2211: 
deba@2211: namespace lemon {
deba@2211: 
deba@2211:   /// \addtogroup flowalgs
deba@2211:   /// @{                                                   
deba@2211: 
deba@2211:   /// %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
deba@2211:   ///
deba@2211:   /// Hao-Orlin calculates the minimum cut in directed graphs. It
deba@2211:   /// separates the nodes of the graph into two disjoint sets and the
deba@2211:   /// summary of the edge capacities go from the first set to the
deba@2211:   /// second set is the minimum.  The algorithm is a modified
deba@2211:   /// push-relabel preflow algorithm and it calculates the minimum cat
deba@2211:   /// in \f$ O(n^3) \f$ time. The purpose of such algorithm is testing
deba@2211:   /// network reliability. For sparse undirected graph you can use the
deba@2211:   /// algorithm of Nagamochi and Ibraki which solves the undirected
deba@2211:   /// problem in \f$ O(n^3) \f$ time. 
deba@2211:   ///
deba@2211:   /// \author Attila Bernath and Balazs Dezso
deba@2211:   template <typename _Graph,
deba@2211: 	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,
deba@2211:             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
deba@2211:   class HaoOrlin {
deba@2211:   protected:
deba@2211: 
deba@2211:     typedef _Graph Graph;
deba@2211:     typedef _CapacityMap CapacityMap;
deba@2211:     typedef _Tolerance Tolerance;
deba@2211: 
deba@2211:     typedef typename CapacityMap::Value Value;
deba@2211: 
deba@2211:     
deba@2211:     typedef typename Graph::Node Node;
deba@2211:     typedef typename Graph::NodeIt NodeIt;
deba@2211:     typedef typename Graph::EdgeIt EdgeIt;
deba@2211:     typedef typename Graph::OutEdgeIt OutEdgeIt;
deba@2211:     typedef typename Graph::InEdgeIt InEdgeIt;
deba@2211: 
deba@2211:     const Graph* _graph;
deba@2211:     const CapacityMap* _capacity;
deba@2211: 
deba@2211:     typedef typename Graph::template EdgeMap<Value> FlowMap;
deba@2211: 
deba@2211:     FlowMap* _preflow;
deba@2211: 
deba@2211:     Node _source, _target;
deba@2211:     int _node_num;
deba@2211: 
deba@2211:     typedef ResGraphAdaptor<const Graph, Value, CapacityMap, 
deba@2211:                             FlowMap, Tolerance> ResGraph;
deba@2211:     typedef typename ResGraph::Node ResNode;
deba@2211:     typedef typename ResGraph::NodeIt ResNodeIt;
deba@2211:     typedef typename ResGraph::EdgeIt ResEdgeIt;
deba@2211:     typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
deba@2211:     typedef typename ResGraph::Edge ResEdge;
deba@2211:     typedef typename ResGraph::InEdgeIt ResInEdgeIt;
deba@2211: 
deba@2211:     ResGraph* _res_graph;
deba@2211: 
deba@2211:     typedef typename Graph::template NodeMap<ResEdge> CurrentArcMap;
deba@2211:     CurrentArcMap* _current_arc;  
deba@2211: 
deba@2211: 
deba@2211:     typedef IterableBoolMap<Graph, Node> WakeMap;
deba@2211:     WakeMap* _wake;
deba@2211: 
deba@2211:     typedef typename Graph::template NodeMap<int> DistMap;
deba@2211:     DistMap* _dist;  
deba@2211:     
deba@2211:     typedef typename Graph::template NodeMap<Value> ExcessMap;
deba@2211:     ExcessMap* _excess;
deba@2211: 
deba@2211:     typedef typename Graph::template NodeMap<bool> SourceSetMap;
deba@2211:     SourceSetMap* _source_set;
deba@2211: 
deba@2211:     std::vector<int> _level_size;
deba@2211: 
deba@2211:     int _highest_active;
deba@2211:     std::vector<std::list<Node> > _active_nodes;
deba@2211: 
deba@2211:     int _dormant_max;
deba@2211:     std::vector<std::list<Node> > _dormant;
deba@2211: 
deba@2211: 
deba@2211:     Value _min_cut;
deba@2211: 
deba@2211:     typedef typename Graph::template NodeMap<bool> MinCutMap;
deba@2211:     MinCutMap* _min_cut_map;
deba@2211: 
deba@2211:     Tolerance _tolerance;
deba@2211: 
deba@2211:   public: 
deba@2211: 
deba@2211:     HaoOrlin(const Graph& graph, const CapacityMap& capacity, 
deba@2211:              const Tolerance& tolerance = Tolerance()) :
deba@2211:       _graph(&graph), _capacity(&capacity), 
deba@2211:       _preflow(0), _source(), _target(), _res_graph(0), _current_arc(0),
deba@2211:       _wake(0),_dist(0), _excess(0), _source_set(0), 
deba@2211:       _highest_active(), _active_nodes(), _dormant_max(), _dormant(), 
deba@2211:       _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}
deba@2211: 
deba@2211:     ~HaoOrlin() {
deba@2211:       if (_res_graph) {
deba@2211:         delete _res_graph;
deba@2211:       }
deba@2211:       if (_min_cut_map) {
deba@2211:         delete _min_cut_map;
deba@2211:       } 
deba@2211:       if (_current_arc) {
deba@2211:         delete _current_arc;
deba@2211:       }
deba@2211:       if (_source_set) {
deba@2211:         delete _source_set;
deba@2211:       }
deba@2211:       if (_excess) {
deba@2211:         delete _excess;
deba@2211:       }
deba@2211:       if (_dist) {
deba@2211:         delete _dist;
deba@2211:       }
deba@2211:       if (_wake) {
deba@2211:         delete _wake;
deba@2211:       }
deba@2211:       if (_preflow) {
deba@2211:         delete _preflow;
deba@2211:       }
deba@2211:     }
deba@2211:     
deba@2211:   private:
deba@2211:     
deba@2211:     void relabel(Node i) {
deba@2211:       int k = (*_dist)[i];
deba@2211:       if (_level_size[k] == 1) {
deba@2211: 	++_dormant_max;
deba@2211: 	for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211: 	  if ((*_wake)[it] && (*_dist)[it] >= k) {
deba@2211: 	    (*_wake)[it] = false;
deba@2211: 	    _dormant[_dormant_max].push_front(it);
deba@2211: 	    --_level_size[(*_dist)[it]];
deba@2211: 	  }
deba@2211: 	}
deba@2211: 	--_highest_active;
deba@2211:       } else {
deba@2211: 	ResOutEdgeIt e(*_res_graph, i);
deba@2211: 	while (e != INVALID && !(*_wake)[_res_graph->target(e)]) {
deba@2211: 	  ++e;
deba@2211: 	}
deba@2211: 
deba@2211: 	if (e == INVALID){
deba@2211: 	  ++_dormant_max;
deba@2211: 	  (*_wake)[i] = false;
deba@2211: 	  _dormant[_dormant_max].push_front(i);
deba@2211: 	  --_level_size[(*_dist)[i]];
deba@2211: 	} else{	    
deba@2211: 	  Node j = _res_graph->target(e);
deba@2211: 	  int new_dist = (*_dist)[j];
deba@2211: 	  ++e;
deba@2211: 	  while (e != INVALID){
deba@2211: 	    Node j = _res_graph->target(e);
deba@2211: 	    if ((*_wake)[j] && new_dist > (*_dist)[j]) {
deba@2211: 	      new_dist = (*_dist)[j];
deba@2211:             }
deba@2211: 	    ++e;
deba@2211: 	  }
deba@2211: 	  --_level_size[(*_dist)[i]];
deba@2211: 	  (*_dist)[i] = new_dist + 1;
deba@2211: 	  _highest_active = (*_dist)[i];
deba@2211: 	  _active_nodes[_highest_active].push_front(i);
deba@2211: 	  ++_level_size[(*_dist)[i]];
deba@2211: 	  _res_graph->firstOut((*_current_arc)[i], i);
deba@2211: 	}
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     bool selectNewSink(){
deba@2211:       Node old_target = _target;
deba@2211:       (*_wake)[_target] = false;
deba@2211:       --_level_size[(*_dist)[_target]];
deba@2211:       _dormant[0].push_front(_target);
deba@2211:       (*_source_set)[_target] = true;
deba@2211:       if ((int)_dormant[0].size() == _node_num){
deba@2211:         _dormant[0].clear();
deba@2211: 	return false;
deba@2211:       }
deba@2211: 
deba@2211:       bool wake_was_empty = false;
deba@2211: 
deba@2211:       if(_wake->trueNum() == 0) {
deba@2211: 	while (!_dormant[_dormant_max].empty()){
deba@2211: 	  (*_wake)[_dormant[_dormant_max].front()] = true;
deba@2211: 	  ++_level_size[(*_dist)[_dormant[_dormant_max].front()]];
deba@2211: 	  _dormant[_dormant_max].pop_front();
deba@2211: 	}
deba@2211: 	--_dormant_max;
deba@2211: 	wake_was_empty = true;
deba@2211:       }
deba@2211: 
deba@2211:       int min_dist = std::numeric_limits<int>::max();
deba@2211:       for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
deba@2211: 	if (min_dist > (*_dist)[it]){
deba@2211: 	  _target = it;
deba@2211: 	  min_dist = (*_dist)[it];
deba@2211: 	}
deba@2211:       }
deba@2211: 
deba@2211:       if (wake_was_empty){
deba@2211: 	for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
deba@2211:           if (_tolerance.positive((*_excess)[it])) {
deba@2211: 	    if ((*_wake)[it] && it != _target) {
deba@2211: 	      _active_nodes[(*_dist)[it]].push_front(it);
deba@2211:             }
deba@2211: 	    if (_highest_active < (*_dist)[it]) {
deba@2211: 	      _highest_active = (*_dist)[it];		    
deba@2211:             }
deba@2211: 	  }
deba@2211: 	}
deba@2211:       }
deba@2211: 
deba@2211:       for (ResOutEdgeIt e(*_res_graph, old_target); e!=INVALID; ++e){
deba@2211: 	if (!(*_source_set)[_res_graph->target(e)]){
deba@2211: 	  push(e, _res_graph->rescap(e));
deba@2211: 	}
deba@2211:       }
deba@2211:       
deba@2211:       return true;
deba@2211:     }
deba@2211:     
deba@2211:     Node findActiveNode() {
deba@2211:       while (_highest_active > 0 && _active_nodes[_highest_active].empty()){ 
deba@2211: 	--_highest_active;
deba@2211:       }
deba@2211:       if( _highest_active > 0) {
deba@2211:        	Node n = _active_nodes[_highest_active].front();
deba@2211: 	_active_nodes[_highest_active].pop_front();
deba@2211: 	return n;
deba@2211:       } else {
deba@2211: 	return INVALID;
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     ResEdge findAdmissibleEdge(const Node& n){
deba@2211:       ResEdge e = (*_current_arc)[n];
deba@2211:       while (e != INVALID && 
deba@2211:              ((*_dist)[n] <= (*_dist)[_res_graph->target(e)] || 
deba@2211:               !(*_wake)[_res_graph->target(e)])) {
deba@2211: 	_res_graph->nextOut(e);
deba@2211:       }
deba@2211:       if (e != INVALID) {
deba@2211: 	(*_current_arc)[n] = e;	
deba@2211: 	return e;
deba@2211:       } else {
deba@2211: 	return INVALID;
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     void push(ResEdge& e,const Value& delta){
deba@2211:       _res_graph->augment(e, delta);
deba@2211:       if (!_tolerance.positive(delta)) return;
deba@2211:       
deba@2211:       (*_excess)[_res_graph->source(e)] -= delta;
deba@2211:       Node a = _res_graph->target(e);
deba@2211:       if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) {
deba@2211: 	_active_nodes[(*_dist)[a]].push_front(a);
deba@2211: 	if (_highest_active < (*_dist)[a]) {
deba@2211: 	  _highest_active = (*_dist)[a];
deba@2211:         }
deba@2211:       }
deba@2211:       (*_excess)[a] += delta;
deba@2211:     }
deba@2211:     
deba@2211:     Value cutValue() {
deba@2211:       Value value = 0;
deba@2211:       for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
deba@2211: 	for (InEdgeIt e(*_graph, it); e != INVALID; ++e) {
deba@2211: 	  if (!(*_wake)[_graph->source(e)]){
deba@2211: 	    value += (*_capacity)[e];
deba@2211: 	  }	
deba@2211: 	}
deba@2211:       }
deba@2211:       return value;
deba@2211:     }    
deba@2211: 
deba@2211:   public:
deba@2211: 
deba@2211:     /// \brief Initializes the internal data structures.
deba@2211:     ///
deba@2211:     /// Initializes the internal data structures. It creates
deba@2211:     /// the maps, residual graph adaptor and some bucket structures
deba@2211:     /// for the algorithm. 
deba@2211:     void init() {
deba@2211:       init(NodeIt(*_graph));
deba@2211:     }
deba@2211: 
deba@2211:     /// \brief Initializes the internal data structures.
deba@2211:     ///
deba@2211:     /// Initializes the internal data structures. It creates
deba@2211:     /// the maps, residual graph adaptor and some bucket structures
deba@2211:     /// for the algorithm. The \c source node is used as the push-relabel
deba@2211:     /// algorithm's source.
deba@2211:     void init(const Node& source) {
deba@2211:       _source = source;
deba@2211:       _node_num = countNodes(*_graph);
deba@2211: 
deba@2211:       _dormant.resize(_node_num);
deba@2211:       _level_size.resize(_node_num, 0);
deba@2211:       _active_nodes.resize(_node_num);
deba@2211: 
deba@2211:       if (!_preflow) {
deba@2211:         _preflow = new FlowMap(*_graph);
deba@2211:       }
deba@2211:       if (!_wake) {
deba@2211:         _wake = new WakeMap(*_graph);
deba@2211:       }
deba@2211:       if (!_dist) {
deba@2211:         _dist = new DistMap(*_graph);
deba@2211:       }
deba@2211:       if (!_excess) {
deba@2211:         _excess = new ExcessMap(*_graph);
deba@2211:       }
deba@2211:       if (!_source_set) {
deba@2211:         _source_set = new SourceSetMap(*_graph);
deba@2211:       }
deba@2211:       if (!_current_arc) {
deba@2211:         _current_arc = new CurrentArcMap(*_graph);
deba@2211:       }
deba@2211:       if (!_min_cut_map) {
deba@2211:         _min_cut_map = new MinCutMap(*_graph);
deba@2211:       }
deba@2211:       if (!_res_graph) {
deba@2211:         _res_graph = new ResGraph(*_graph, *_capacity, *_preflow);
deba@2211:       }
deba@2211: 
deba@2211:       _min_cut = std::numeric_limits<Value>::max();
deba@2211:     }
deba@2211: 
deba@2211: 
deba@2211:     /// \brief Calculates the minimum cut with the \c source node
deba@2211:     /// in the first partition.
deba@2211:     ///
deba@2211:     /// Calculates the minimum cut with the \c source node
deba@2211:     /// in the first partition.
deba@2211:     void calculateOut() {
deba@2211:       for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211:         if (it != _source) {
deba@2211:           calculateOut(it);
deba@2211:           return;
deba@2211:         }
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     /// \brief Calculates the minimum cut with the \c source node
deba@2211:     /// in the first partition.
deba@2211:     ///
deba@2211:     /// Calculates the minimum cut with the \c source node
deba@2211:     /// in the first partition. The \c target is the initial target
deba@2211:     /// for the push-relabel algorithm.
deba@2211:     void calculateOut(const Node& target) {
deba@2211:       for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211:         (*_wake)[it] = true;
deba@2211:         (*_dist)[it] = 1;
deba@2211:         (*_excess)[it] = 0;
deba@2211:         (*_source_set)[it] = false;
deba@2211: 
deba@2211:         _res_graph->firstOut((*_current_arc)[it], it);
deba@2211:       }
deba@2211: 
deba@2211:       _target = target;
deba@2211:       (*_dist)[target] = 0;
deba@2211: 
deba@2211:       for (ResOutEdgeIt it(*_res_graph, _source); it != INVALID; ++it) {
deba@2211: 	push(it, _res_graph->rescap(it));
deba@2211:       }
deba@2211: 
deba@2211:       _dormant[0].push_front(_source);
deba@2211:       (*_source_set)[_source] = true;
deba@2211:       _dormant_max = 0;
deba@2211:       (*_wake)[_source]=false;
deba@2211: 
deba@2211:       _level_size[0] = 1;
deba@2211:       _level_size[1] = _node_num - 1;
deba@2211: 
deba@2211:       do {
deba@2211: 	Node n;
deba@2211: 	while ((n = findActiveNode()) != INVALID) {
deba@2211: 	  ResEdge e;
deba@2211: 	  while (_tolerance.positive((*_excess)[n]) && 
deba@2211:                  (e = findAdmissibleEdge(n)) != INVALID){
deba@2211: 	    Value delta;
deba@2211: 	    if ((*_excess)[n] < _res_graph->rescap(e)) {
deba@2211: 	      delta = (*_excess)[n];
deba@2211: 	    } else {
deba@2211: 	      delta = _res_graph->rescap(e);
deba@2211: 	      _res_graph->nextOut((*_current_arc)[n]);
deba@2211: 	    }
deba@2211:             if (!_tolerance.positive(delta)) continue;
deba@2211: 	    _res_graph->augment(e, delta);
deba@2211: 	    (*_excess)[_res_graph->source(e)] -= delta;
deba@2211: 	    Node a = _res_graph->target(e);
deba@2211: 	    if (!_tolerance.positive((*_excess)[a]) && a != _target) {
deba@2211: 	      _active_nodes[(*_dist)[a]].push_front(a);
deba@2211: 	    }
deba@2211: 	    (*_excess)[a] += delta;
deba@2211: 	  }
deba@2211: 	  if (_tolerance.positive((*_excess)[n])) {
deba@2211: 	    relabel(n);
deba@2211:           }
deba@2211: 	}
deba@2211: 
deba@2211: 	Value current_value = cutValue();
deba@2211:  	if (_min_cut > current_value){
deba@2211: 	  for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211:             _min_cut_map->set(it, !(*_wake)[it]);
deba@2211: 	  }
deba@2211: 
deba@2211: 	  _min_cut = current_value;
deba@2211:  	}
deba@2211: 
deba@2211:       } while (selectNewSink());
deba@2211:     }
deba@2211: 
deba@2211:     void calculateIn() {
deba@2211:       for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211:         if (it != _source) {
deba@2211:           calculateIn(it);
deba@2211:           return;
deba@2211:         }
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     void run() {
deba@2211:       init();
deba@2211:       for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211:         if (it != _source) {
deba@2211:           startOut(it);
deba@2211:           //          startIn(it);
deba@2211:           return;
deba@2211:         }
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     void run(const Node& s) {
deba@2211:       init(s);
deba@2211:       for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211:         if (it != _source) {
deba@2211:           startOut(it);
deba@2211:           //          startIn(it);
deba@2211:           return;
deba@2211:         }
deba@2211:       }
deba@2211:     }
deba@2211: 
deba@2211:     void run(const Node& s, const Node& t) {
deba@2211:       init(s);
deba@2211:       startOut(t);
deba@2211:       startIn(t);
deba@2211:     }
deba@2211:     
deba@2211:     /// \brief Returns the value of the minimum value cut with node \c
deba@2211:     /// source on the source side.
deba@2211:     /// 
deba@2211:     /// Returns the value of the minimum value cut with node \c source
deba@2211:     /// on the source side. This function can be called after running
deba@2211:     /// \ref findMinCut.
deba@2211:     Value minCut() const {
deba@2211:       return _min_cut;
deba@2211:     }
deba@2211: 
deba@2211: 
deba@2211:     /// \brief Returns a minimum value cut.
deba@2211:     ///
deba@2211:     /// Sets \c nodeMap to the characteristic vector of a minimum
deba@2211:     /// value cut with node \c source on the source side. This
deba@2211:     /// function can be called after running \ref findMinCut.  
deba@2211:     /// \pre nodeMap should be a bool-valued node-map.
deba@2211:     template <typename NodeMap>
deba@2211:     Value minCut(NodeMap& nodeMap) const {
deba@2211:       for (NodeIt it(*_graph); it != INVALID; ++it) {
deba@2211: 	nodeMap.set(it, (*_min_cut_map)[it]);
deba@2211:       }
deba@2211:       return minCut();
deba@2211:     }
deba@2211:     
deba@2211:   }; //class HaoOrlin 
deba@2211: 
deba@2211: 
deba@2211: } //namespace lemon
deba@2211: 
deba@2211: #endif //LEMON_HAO_ORLIN_H