# Changeset 2225:bb3d5e6f9fcb in lemon-0.x

Ignore:
Timestamp:
09/29/06 13:36:30 (13 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2965
Message:

Doc fix

Location:
lemon
Files:
2 edited

### Legend:

Unmodified
 r2211 /* -*- C++ -*- * lemon/hao_orlin.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2006 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * /// \file /// \ingroup flowalgs /// Implementation of the Hao-Orlin algorithms class for testing network /// \brief Implementation of the Hao-Orlin algorithm. /// /// Implementation of the HaoOrlin algorithms class for testing network /// reliability. namespace lemon { /// \addtogroup flowalgs /// @{ /// %Hao-Orlin algorithm for calculate minimum cut in directed graphs. /// \ingroup flowalgs /// /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs. /// /// Hao-Orlin calculates the minimum cut in directed graphs. It /// separates the nodes of the graph into two disjoint sets and the /// summary of the edge capacities go from the first set to the /// second set is the minimum.  The algorithm is a modified /// push-relabel preflow algorithm and it calculates the minimum cat /// in \f$O(n^3) \f$ time. The purpose of such algorithm is testing /// network reliability. For sparse undirected graph you can use the /// algorithm of Nagamochi and Ibraki which solves the undirected /// problem in \f$O(n^3) \f$ time. /// separates the nodes of the graph into two disjoint sets, /// \f$V_{out} \f$ and \f$V_{in} \f$. This separation is the minimum /// cut if the summary of the edge capacities which source is in /// \f$V_{out} \f$ and the target is in \f$V_{in} \f$ is the /// minimum.  The algorithm is a modified push-relabel preflow /// algorithm and it calculates the minimum cut in \f$O(n^3) \f$ /// time. The purpose of such algorithm is testing network /// reliability. For sparse undirected graph you can use the /// algorithm of Nagamochi and Ibaraki which solves the undirected /// problem in \f$O(ne + n^2 \log(n)) \f$ time and it is implemented in the /// MinCut algorithm class. /// /// \param _Graph is the graph type of the algorithm. /// \param _CapacityMap is an edge map of capacities which should /// be any numreric type. The default type is _Graph::EdgeMap. /// \param _Tolerance is the handler of the inexact computation. The /// default type for it is Tolerance. /// /// \author Attila Bernath and Balazs Dezso #ifdef DOXYGEN template #else template , typename _Tolerance = Tolerance > #endif class HaoOrlin { protected: const Graph* _graph; const CapacityMap* _capacity; typedef ResGraphAdaptor ResGraph; typedef typename ResGraph::Node ResNode; typedef typename ResGraph::NodeIt ResNodeIt; typedef typename ResGraph::EdgeIt ResEdgeIt; typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; typedef typename ResGraph::Edge ResEdge; typedef typename ResGraph::InEdgeIt ResInEdgeIt; ResGraph* _res_graph; typedef typename Graph::template NodeMap CurrentArcMap; CurrentArcMap* _current_arc; FlowMap, Tolerance> OutResGraph; typedef typename OutResGraph::Edge OutResEdge; OutResGraph* _out_res_graph; typedef typename Graph::template NodeMap OutCurrentEdgeMap; OutCurrentEdgeMap* _out_current_edge; typedef RevGraphAdaptor RevGraph; RevGraph* _rev_graph; typedef ResGraphAdaptor InResGraph; typedef typename InResGraph::Edge InResEdge; InResGraph* _in_res_graph; typedef typename Graph::template NodeMap InCurrentEdgeMap; InCurrentEdgeMap* _in_current_edge; public: /// \brief Constructor /// /// Constructor of the algorithm class. HaoOrlin(const Graph& graph, const CapacityMap& capacity, const Tolerance& tolerance = Tolerance()) : _graph(&graph), _capacity(&capacity), _preflow(0), _source(), _target(), _res_graph(0), _current_arc(0), _preflow(0), _source(), _target(), _out_res_graph(0), _out_current_edge(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(), ~HaoOrlin() { if (_res_graph) { delete _res_graph; } if (_min_cut_map) { delete _min_cut_map; } if (_current_arc) { delete _current_arc; 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) { private: void relabel(Node i) { int k = (*_dist)[i]; template void findMinCut(const Node& target, bool out, ResGraph& res_graph, EdgeMap& current_edge) { 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); } _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)[res_graph.source(it)] -= delta; res_graph.augment(it, delta); Node a = res_graph.target(it); if (!_tolerance.positive((*_excess)[a]) && (*_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; while (_tolerance.positive((*_excess)[n]) && (e = findAdmissibleEdge(n, res_graph, current_edge)) != INVALID){ Value delta; if ((*_excess)[n] < res_graph.rescap(e)) { delta = (*_excess)[n]; } else { 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; Node a = res_graph.target(e); if (!_tolerance.positive((*_excess)[a]) && a != _target) { _active_nodes[(*_dist)[a]].push_front(a); } (*_excess)[a] += delta; } if (_tolerance.positive((*_excess)[n])) { relabel(n, res_graph, current_edge); } } Value current_value = cutValue(out); if (_min_cut > current_value){ if (out) { for (NodeIt it(*_graph); it != INVALID; ++it) { _min_cut_map->set(it, !(*_wake)[it]); } } else { for (NodeIt it(*_graph); it != INVALID; ++it) { _min_cut_map->set(it, (*_wake)[it]); } } _min_cut = current_value; } } while (selectNewSink(res_graph)); } template void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) { typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; int k = (*_dist)[n]; if (_level_size[k] == 1) { ++_dormant_max; } --_highest_active; } else { ResOutEdgeIt e(*_res_graph, i); while (e != INVALID && !(*_wake)[_res_graph->target(e)]) { ++e; } 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]) { new_dist = (*_dist)[t]; } } if (new_dist == _node_num) { ++_dormant_max; (*_wake)[n] = false; _dormant[_dormant_max].push_front(n); --_level_size[(*_dist)[n]]; } else { --_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); } if (e == INVALID){ ++_dormant_max; (*_wake)[i] = false; _dormant[_dormant_max].push_front(i); --_level_size[(*_dist)[i]]; } else{ Node j = _res_graph->target(e); int new_dist = (*_dist)[j]; ++e; while (e != INVALID){ Node j = _res_graph->target(e); if ((*_wake)[j] && new_dist > (*_dist)[j]) { new_dist = (*_dist)[j]; } ++e; } --_level_size[(*_dist)[i]]; (*_dist)[i] = new_dist + 1; _highest_active = (*_dist)[i]; _active_nodes[_highest_active].push_front(i); ++_level_size[(*_dist)[i]]; _res_graph->firstOut((*_current_arc)[i], i); } } } bool selectNewSink(){ } } template bool selectNewSink(ResGraph& res_graph) { typedef typename ResGraph::OutEdgeIt ResOutEdgeIt; Node old_target = _target; (*_wake)[_target] = false; } for (ResOutEdgeIt e(*_res_graph, old_target); e!=INVALID; ++e){ if (!(*_source_set)[_res_graph->target(e)]){ push(e, _res_graph->rescap(e)); for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){ if (!(*_source_set)[res_graph.target(e)]) { Value delta = res_graph.rescap(e); if (!_tolerance.positive(delta)) continue; res_graph.augment(e, delta); (*_excess)[res_graph.source(e)] -= delta; Node a = res_graph.target(e); if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) { _active_nodes[(*_dist)[a]].push_front(a); if (_highest_active < (*_dist)[a]) { _highest_active = (*_dist)[a]; } } (*_excess)[a] += delta; } } } ResEdge findAdmissibleEdge(const Node& n){ ResEdge e = (*_current_arc)[n]; template 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); ((*_dist)[n] <= (*_dist)[res_graph.target(e)] || !(*_wake)[res_graph.target(e)])) { res_graph.nextOut(e); } if (e != INVALID) { (*_current_arc)[n] = e; current_edge[n] = e; return e; } else { } void push(ResEdge& e,const Value& delta){ _res_graph->augment(e, delta); if (!_tolerance.positive(delta)) return; (*_excess)[_res_graph->source(e)] -= delta; Node a = _res_graph->target(e); if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) { _active_nodes[(*_dist)[a]].push_front(a); if (_highest_active < (*_dist)[a]) { _highest_active = (*_dist)[a]; } } (*_excess)[a] += delta; } Value cutValue() { Value cutValue(bool out) { Value value = 0; for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) { for (InEdgeIt e(*_graph, it); e != INVALID; ++e) { if (!(*_wake)[_graph->source(e)]){ value += (*_capacity)[e]; } } if (out) { for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) { for (InEdgeIt e(*_graph, it); e != INVALID; ++e) { if (!(*_wake)[_graph->source(e)]){ value += (*_capacity)[e]; } } } } else { for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) { for (OutEdgeIt e(*_graph, it); e != INVALID; ++e) { if (!(*_wake)[_graph->target(e)]){ value += (*_capacity)[e]; } } } } return value; } } public: /// \name Execution control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). /// \n /// If you need more control on the execution, /// first you must call \ref init(), then the \ref calculateIn() or /// \ref calculateIn() functions. /// @{ /// \brief Initializes the internal data structures. /// /// Initializes the internal data structures. It creates /// the maps, residual graph adaptor and some bucket structures /// the maps, residual graph adaptors and some bucket structures /// for the algorithm. void init() { _source_set = new SourceSetMap(*_graph); } if (!_current_arc) { _current_arc = new CurrentArcMap(*_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); } if (!_res_graph) { _res_graph = new ResGraph(*_graph, *_capacity, *_preflow); } _min_cut = std::numeric_limits::max(); /// \brief Calculates the minimum cut with the \c source node /// in the first partition. /// in the \f$V_{out} \f$. /// /// Calculates the minimum cut with the \c source node /// in the first partition. /// in the \f$V_{out} \f$. void calculateOut() { for (NodeIt it(*_graph); it != INVALID; ++it) { /// \brief Calculates the minimum cut with the \c source node /// in the first partition. /// in the \f$V_{out} \f$. /// /// Calculates the minimum cut with the \c source node /// in the first partition. The \c target is the initial target /// in the \f$V_{out} \f$. The \c target is the initial target /// for the push-relabel algorithm. void calculateOut(const Node& target) { for (NodeIt it(*_graph); it != INVALID; ++it) { (*_wake)[it] = true; (*_dist)[it] = 1; (*_excess)[it] = 0; (*_source_set)[it] = false; _res_graph->firstOut((*_current_arc)[it], it); } _target = target; (*_dist)[target] = 0; for (ResOutEdgeIt it(*_res_graph, _source); it != INVALID; ++it) { push(it, _res_graph->rescap(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; do { Node n; while ((n = findActiveNode()) != INVALID) { ResEdge e; while (_tolerance.positive((*_excess)[n]) && (e = findAdmissibleEdge(n)) != INVALID){ Value delta; if ((*_excess)[n] < _res_graph->rescap(e)) { delta = (*_excess)[n]; } else { delta = _res_graph->rescap(e); _res_graph->nextOut((*_current_arc)[n]); } if (!_tolerance.positive(delta)) continue; _res_graph->augment(e, delta); (*_excess)[_res_graph->source(e)] -= delta; Node a = _res_graph->target(e); if (!_tolerance.positive((*_excess)[a]) && a != _target) { _active_nodes[(*_dist)[a]].push_front(a); } (*_excess)[a] += delta; } if (_tolerance.positive((*_excess)[n])) { relabel(n); } } Value current_value = cutValue(); if (_min_cut > current_value){ for (NodeIt it(*_graph); it != INVALID; ++it) { _min_cut_map->set(it, !(*_wake)[it]); } _min_cut = current_value; } } while (selectNewSink()); } findMinCut(target, true, *_out_res_graph, *_out_current_edge); } /// \brief Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. /// /// Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. void calculateIn() { for (NodeIt it(*_graph); it != INVALID; ++it) { } /// \brief Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. /// /// Calculates the minimum cut with the \c source node /// in the \f$V_{in} \f$. 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); } /// \brief Runs the algorithm. /// /// Runs the algorithm. It finds a proper \c source and \c target /// and then calls the \ref init(), \ref calculateOut() and \ref /// calculateIn(). void run() { init(); for (NodeIt it(*_graph); it != INVALID; ++it) { if (it != _source) { startOut(it); //          startIn(it); calculateOut(it); calculateIn(it); return; } } /// \brief Runs the algorithm. /// /// Runs the algorithm. It finds a proper \c target and then calls /// the \ref init(), \ref calculateOut() and \ref calculateIn(). void run(const Node& s) { init(s); for (NodeIt it(*_graph); it != INVALID; ++it) { if (it != _source) { startOut(it); //          startIn(it); calculateOut(it); calculateIn(it); return; } } /// \brief Runs the algorithm. /// /// Runs the algorithm. It just calls the \ref init() and then /// \ref calculateOut() and \ref calculateIn(). void run(const Node& s, const Node& t) { init(s); startOut(t); startIn(t); } /// \brief Returns the value of the minimum value cut with node \c /// source on the source side. init(s); calculateOut(t); calculateIn(t); } /// @} /// \name Query Functions The result of the %HaoOrlin algorithm /// can be obtained using these functions. /// \n /// Before the use of these functions, either \ref run(), \ref /// calculateOut() or \ref calculateIn() must be called. /// @{ /// \brief Returns the value of the minimum value cut. /// /// Returns the value of the minimum value cut with node \c source /// on the source side. This function can be called after running /// \ref findMinCut. /// Returns the value of the minimum value cut. Value minCut() const { return _min_cut; /// /// Sets \c nodeMap to the characteristic vector of a minimum /// value cut with node \c source on the source side. This /// function can be called after running \ref findMinCut. /// value cut. The nodes in \f$V_{out} \f$ will be set true and /// the nodes in \f$V_{in} \f$ will be set false. /// \pre nodeMap should be a bool-valued node-map. template return minCut(); } /// @} }; //class HaoOrlin
 r2176 /// \ingroup topology /// /// \brief Calculates the min cut in an undirected graph. /// \brief Calculates the minimum cut in an undirected graph. /// /// Calculates the min cut in an undirected graph. /// The algorithm separates the graph's nodes into two partitions with the /// min sum of edge capacities between the two partitions. The /// algorithm can be used to test the network reliability specifically /// to test how many links have to be destroyed in the network to split it /// at least two distinict subnetwork. /// Calculates the minimum cut in an undirected graph with the /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's /// nodes into two partitions with the minimum sum of edge capacities /// between the two partitions. The algorithm can be used to test /// the network reliability specifically to test how many links have /// to be destroyed in the network to split it at least two /// distinict subnetwork. /// /// The complexity of the algorithm is \f$O(ne\log(n)) \f$ but with /// Fibonacci heap it can be decreased to \f$O(ne+n^2\log(n)) \f$. When /// the neutral capacity map is used then it uses BucketHeap which /// Fibonacci heap it can be decreased to \f$O(ne+n^2\log(n)) /// \f$. When capacity map is neutral then it uses BucketHeap which /// results \f$O(ne) \f$ time complexity. #ifdef DOXYGEN