Changeset 643:293551ad254f in lemon for lemon/hao_orlin.h
 Timestamp:
 04/15/09 09:37:51 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/hao_orlin.h
r628 r643 32 32 /// \brief Implementation of the HaoOrlin algorithm. 33 33 /// 34 /// Implementation of the HaoOrlin algorithm class for testing network35 /// reliability.34 /// Implementation of the HaoOrlin algorithm for finding a minimum cut 35 /// in a digraph. 36 36 37 37 namespace lemon { … … 39 39 /// \ingroup min_cut 40 40 /// 41 /// \brief %HaoOrlin algorithm to find a minimum cut in directed graphs.41 /// \brief HaoOrlin algorithm for finding a minimum cut in a digraph. 42 42 /// 43 /// HaoOrlin calculates a minimum cut in a directed graph 44 /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and 43 /// This class implements the HaoOrlin algorithm for finding a minimum 44 /// value cut in a directed graph \f$D=(V,A)\f$. 45 /// It takes a fixed node \f$ source \in V \f$ and 45 46 /// consists of two phases: in the first phase it determines a 46 47 /// minimum cut with \f$ source \f$ on the sourceside (i.e. a set 47 /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal 48 /// outdegree) and in the second phase it determines a minimum cut48 /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing 49 /// capacity) and in the second phase it determines a minimum cut 49 50 /// with \f$ source \f$ on the sinkside (i.e. a set 50 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal 51 /// outdegree). Obviously, the smaller of these two cuts will be a51 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing 52 /// capacity). Obviously, the smaller of these two cuts will be a 52 53 /// minimum cut of \f$ D \f$. The algorithm is a modified 53 /// p ushrelabel preflow algorithm and our implementation calculates54 /// preflow pushrelabel algorithm. Our implementation calculates 54 55 /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the 55 56 /// highestlabel rule), or in \f$O(nm)\f$ for unit capacities. The 56 /// purpose of such algorithm is testing network reliability. For an 57 /// undirected graph you can run just the first phase of the 58 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki 59 /// which solves the undirected problem in 60 /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the 61 /// NagamochiIbaraki algorithm class. 57 /// purpose of such algorithm is e.g. testing network reliability. 62 58 /// 63 /// \param GR The digraph class the algorithm runs on. 64 /// \param CAP An arc map of capacities which can be any numreric type. 65 /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 66 /// \param TOL Tolerance class for handling inexact computations. The 59 /// For an undirected graph you can run just the first phase of the 60 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, 61 /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ 62 /// time. It is implemented in the NagamochiIbaraki algorithm class. 63 /// 64 /// \tparam GR The type of the digraph the algorithm runs on. 65 /// \tparam CAP The type of the arc map containing the capacities, 66 /// which can be any numreric type. The default map type is 67 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 68 /// \tparam TOL Tolerance class for handling inexact computations. The 67 69 /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>". 68 70 #ifdef DOXYGEN … … 74 76 #endif 75 77 class HaoOrlin { 78 public: 79 80 /// The digraph type of the algorithm 81 typedef GR Digraph; 82 /// The capacity map type of the algorithm 83 typedef CAP CapacityMap; 84 /// The tolerance type of the algorithm 85 typedef TOL Tolerance; 86 76 87 private: 77 88 78 typedef GR Digraph;79 typedef CAP CapacityMap;80 typedef TOL Tolerance;81 82 89 typedef typename CapacityMap::Value Value; 83 90 84 TEMPLATE_ GRAPH_TYPEDEFS(Digraph);91 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 85 92 86 93 const Digraph& _graph; … … 816 823 public: 817 824 818 /// \name Execution control825 /// \name Execution Control 819 826 /// The simplest way to execute the algorithm is to use 820 827 /// one of the member functions called \ref run(). 821 828 /// \n 822 /// If you need morecontrol on the execution,823 /// first you must call \ref init(), then the \ref calculateIn() or824 /// \ref calculateOut() functions.829 /// If you need better control on the execution, 830 /// you have to call one of the \ref init() functions first, then 831 /// \ref calculateOut() and/or \ref calculateIn(). 825 832 826 833 /// @{ 827 834 828 /// \brief Initializes the internal data structures. 829 /// 830 /// Initializes the internal data structures. It creates 831 /// the maps, residual graph adaptors and some bucket structures 832 /// for the algorithm. 835 /// \brief Initialize the internal data structures. 836 /// 837 /// This function initializes the internal data structures. It creates 838 /// the maps and some bucket structures for the algorithm. 839 /// The first node is used as the source node for the pushrelabel 840 /// algorithm. 833 841 void init() { 834 842 init(NodeIt(_graph)); 835 843 } 836 844 837 /// \brief Initialize sthe internal data structures.838 /// 839 /// Initializes the internal data structures. It creates840 /// the maps , residual graph adaptor and some bucket structures841 /// for the algorithm. Node \c source is used asthe pushrelabel842 /// algorithm 's source.845 /// \brief Initialize the internal data structures. 846 /// 847 /// This function initializes the internal data structures. It creates 848 /// the maps and some bucket structures for the algorithm. 849 /// The given node is used as the source node for the pushrelabel 850 /// algorithm. 843 851 void init(const Node& source) { 844 852 _source = source; … … 880 888 881 889 882 /// \brief Calculate sa minimum cut with \f$ source \f$ on the890 /// \brief Calculate a minimum cut with \f$ source \f$ on the 883 891 /// sourceside. 884 892 /// 885 /// Calculates a minimum cut with \f$ source \f$ on the893 /// This function calculates a minimum cut with \f$ source \f$ on the 886 894 /// sourceside (i.e. a set \f$ X\subsetneq V \f$ with 887 /// \f$ source \in X \f$ and minimal outdegree). 895 /// \f$ source \in X \f$ and minimal outgoing capacity). 896 /// 897 /// \pre \ref init() must be called before using this function. 888 898 void calculateOut() { 889 899 findMinCutOut(); 890 900 } 891 901 892 /// \brief Calculates a minimum cut with \f$ source \f$ on the 893 /// targetside. 894 /// 895 /// Calculates a minimum cut with \f$ source \f$ on the 896 /// targetside (i.e. a set \f$ X\subsetneq V \f$ with 897 /// \f$ source \in X \f$ and minimal outdegree). 902 /// \brief Calculate a minimum cut with \f$ source \f$ on the 903 /// sinkside. 904 /// 905 /// This function calculates a minimum cut with \f$ source \f$ on the 906 /// sinkside (i.e. a set \f$ X\subsetneq V \f$ with 907 /// \f$ source \notin X \f$ and minimal outgoing capacity). 908 /// 909 /// \pre \ref init() must be called before using this function. 898 910 void calculateIn() { 899 911 findMinCutIn(); … … 901 913 902 914 903 /// \brief Run sthe algorithm.904 /// 905 /// Runs the algorithm. It finds nodes \c source and \c target906 /// arbitrarily and then calls \ref init(), \ref calculateOut()915 /// \brief Run the algorithm. 916 /// 917 /// This function runs the algorithm. It finds nodes \c source and 918 /// \c target arbitrarily and then calls \ref init(), \ref calculateOut() 907 919 /// and \ref calculateIn(). 908 920 void run() { … … 912 924 } 913 925 914 /// \brief Run sthe algorithm.915 /// 916 /// Runs the algorithm. It uses the given \c source node, finds a917 /// proper \c target and then calls the \ref init(), \ref918 /// calculateOut() and \ref calculateIn().926 /// \brief Run the algorithm. 927 /// 928 /// This function runs the algorithm. It uses the given \c source node, 929 /// finds a proper \c target node and then calls the \ref init(), 930 /// \ref calculateOut() and \ref calculateIn(). 919 931 void run(const Node& s) { 920 932 init(s); … … 927 939 /// \name Query Functions 928 940 /// The result of the %HaoOrlin algorithm 929 /// can be obtained using these functions. 930 /// \n 931 /// Before using these functions, either \ref run(), \ref 932 /// calculateOut() or \ref calculateIn() must be called. 941 /// can be obtained using these functions.\n 942 /// \ref run(), \ref calculateOut() or \ref calculateIn() 943 /// should be called before using them. 933 944 934 945 /// @{ 935 946 936 /// \brief Returns the value of the minimum value cut. 937 /// 938 /// Returns the value of the minimum value cut. 947 /// \brief Return the value of the minimum cut. 948 /// 949 /// This function returns the value of the minimum cut. 950 /// 951 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 952 /// must be called before using this function. 939 953 Value minCutValue() const { 940 954 return _min_cut; … … 942 956 943 957 944 /// \brief Returns a minimum cut. 945 /// 946 /// Sets \c nodeMap to the characteristic vector of a minimum 947 /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$ 948 /// with minimal outdegree (i.e. \c nodeMap will be true exactly 949 /// for the nodes of \f$ X \f$). \pre nodeMap should be a 950 /// boolvalued nodemap. 951 template <typename NodeMap> 952 Value minCutMap(NodeMap& nodeMap) const { 958 /// \brief Return a minimum cut. 959 /// 960 /// This function sets \c cutMap to the characteristic vector of a 961 /// minimum value cut: it will give a nonempty set \f$ X\subsetneq V \f$ 962 /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly 963 /// for the nodes of \f$ X \f$). 964 /// 965 /// \param cutMap A \ref concepts::WriteMap "writable" node map with 966 /// \c bool (or convertible) value type. 967 /// 968 /// \return The value of the minimum cut. 969 /// 970 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 971 /// must be called before using this function. 972 template <typename CutMap> 973 Value minCutMap(CutMap& cutMap) const { 953 974 for (NodeIt it(_graph); it != INVALID; ++it) { 954 nodeMap.set(it, (*_min_cut_map)[it]);975 cutMap.set(it, (*_min_cut_map)[it]); 955 976 } 956 977 return _min_cut; … … 961 982 }; //class HaoOrlin 962 983 963 964 984 } //namespace lemon 965 985
Note: See TracChangeset
for help on using the changeset viewer.