29 |
29 |
30 /// \file |
30 /// \file |
31 /// \ingroup min_cut |
31 /// \ingroup min_cut |
32 /// \brief Implementation of the Hao-Orlin algorithm. |
32 /// \brief Implementation of the Hao-Orlin algorithm. |
33 /// |
33 /// |
34 /// Implementation of the Hao-Orlin algorithm class for testing network |
34 /// Implementation of the Hao-Orlin algorithm for finding a minimum cut |
35 /// reliability. |
35 /// in a digraph. |
36 |
36 |
37 namespace lemon { |
37 namespace lemon { |
38 |
38 |
39 /// \ingroup min_cut |
39 /// \ingroup min_cut |
40 /// |
40 /// |
41 /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs. |
41 /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph. |
42 /// |
42 /// |
43 /// Hao-Orlin calculates a minimum cut in a directed graph |
43 /// This class implements the Hao-Orlin algorithm for finding a minimum |
44 /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and |
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 /// consists of two phases: in the first phase it determines a |
46 /// consists of two phases: in the first phase it determines a |
46 /// minimum cut with \f$ source \f$ on the source-side (i.e. a set |
47 /// minimum cut with \f$ source \f$ on the source-side (i.e. a set |
47 /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal |
48 /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing |
48 /// out-degree) and in the second phase it determines a minimum cut |
49 /// capacity) and in the second phase it determines a minimum cut |
49 /// with \f$ source \f$ on the sink-side (i.e. a set |
50 /// with \f$ source \f$ on the sink-side (i.e. a set |
50 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal |
51 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing |
51 /// out-degree). Obviously, the smaller of these two cuts will be a |
52 /// capacity). Obviously, the smaller of these two cuts will be a |
52 /// minimum cut of \f$ D \f$. The algorithm is a modified |
53 /// minimum cut of \f$ D \f$. The algorithm is a modified |
53 /// push-relabel preflow algorithm and our implementation calculates |
54 /// preflow push-relabel algorithm. Our implementation calculates |
54 /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the |
55 /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the |
55 /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The |
56 /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The |
56 /// purpose of such algorithm is testing network reliability. For an |
57 /// purpose of such algorithm is e.g. testing network reliability. |
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. |
|
62 /// |
58 /// |
63 /// \param GR The digraph class the algorithm runs on. |
59 /// For an undirected graph you can run just the first phase of the |
64 /// \param CAP An arc map of capacities which can be any numreric type. |
60 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, |
65 /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
61 /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ |
66 /// \param TOL Tolerance class for handling inexact computations. The |
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 /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>". |
69 /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>". |
68 #ifdef DOXYGEN |
70 #ifdef DOXYGEN |
69 template <typename GR, typename CAP, typename TOL> |
71 template <typename GR, typename CAP, typename TOL> |
70 #else |
72 #else |
71 template <typename GR, |
73 template <typename GR, |
72 typename CAP = typename GR::template ArcMap<int>, |
74 typename CAP = typename GR::template ArcMap<int>, |
73 typename TOL = Tolerance<typename CAP::Value> > |
75 typename TOL = Tolerance<typename CAP::Value> > |
74 #endif |
76 #endif |
75 class HaoOrlin { |
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 private: |
87 private: |
77 |
88 |
78 typedef GR Digraph; |
|
79 typedef CAP CapacityMap; |
|
80 typedef TOL Tolerance; |
|
81 |
|
82 typedef typename CapacityMap::Value Value; |
89 typedef typename CapacityMap::Value Value; |
83 |
90 |
84 TEMPLATE_GRAPH_TYPEDEFS(Digraph); |
91 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
85 |
92 |
86 const Digraph& _graph; |
93 const Digraph& _graph; |
87 const CapacityMap* _capacity; |
94 const CapacityMap* _capacity; |
88 |
95 |
89 typedef typename Digraph::template ArcMap<Value> FlowMap; |
96 typedef typename Digraph::template ArcMap<Value> FlowMap; |
813 } |
820 } |
814 } |
821 } |
815 |
822 |
816 public: |
823 public: |
817 |
824 |
818 /// \name Execution control |
825 /// \name Execution Control |
819 /// The simplest way to execute the algorithm is to use |
826 /// The simplest way to execute the algorithm is to use |
820 /// one of the member functions called \ref run(). |
827 /// one of the member functions called \ref run(). |
821 /// \n |
828 /// \n |
822 /// If you need more control on the execution, |
829 /// If you need better control on the execution, |
823 /// first you must call \ref init(), then the \ref calculateIn() or |
830 /// you have to call one of the \ref init() functions first, then |
824 /// \ref calculateOut() functions. |
831 /// \ref calculateOut() and/or \ref calculateIn(). |
825 |
832 |
826 /// @{ |
833 /// @{ |
827 |
834 |
828 /// \brief Initializes the internal data structures. |
835 /// \brief Initialize the internal data structures. |
829 /// |
836 /// |
830 /// Initializes the internal data structures. It creates |
837 /// This function initializes the internal data structures. It creates |
831 /// the maps, residual graph adaptors and some bucket structures |
838 /// the maps and some bucket structures for the algorithm. |
832 /// for the algorithm. |
839 /// The first node is used as the source node for the push-relabel |
|
840 /// algorithm. |
833 void init() { |
841 void init() { |
834 init(NodeIt(_graph)); |
842 init(NodeIt(_graph)); |
835 } |
843 } |
836 |
844 |
837 /// \brief Initializes the internal data structures. |
845 /// \brief Initialize the internal data structures. |
838 /// |
846 /// |
839 /// Initializes the internal data structures. It creates |
847 /// This function initializes the internal data structures. It creates |
840 /// the maps, residual graph adaptor and some bucket structures |
848 /// the maps and some bucket structures for the algorithm. |
841 /// for the algorithm. Node \c source is used as the push-relabel |
849 /// The given node is used as the source node for the push-relabel |
842 /// algorithm's source. |
850 /// algorithm. |
843 void init(const Node& source) { |
851 void init(const Node& source) { |
844 _source = source; |
852 _source = source; |
845 |
853 |
846 _node_num = countNodes(_graph); |
854 _node_num = countNodes(_graph); |
847 |
855 |
877 |
885 |
878 _min_cut = std::numeric_limits<Value>::max(); |
886 _min_cut = std::numeric_limits<Value>::max(); |
879 } |
887 } |
880 |
888 |
881 |
889 |
882 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
890 /// \brief Calculate a minimum cut with \f$ source \f$ on the |
883 /// source-side. |
891 /// source-side. |
884 /// |
892 /// |
885 /// Calculates a minimum cut with \f$ source \f$ on the |
893 /// This function calculates a minimum cut with \f$ source \f$ on the |
886 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with |
894 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with |
887 /// \f$ source \in X \f$ and minimal out-degree). |
895 /// \f$ source \in X \f$ and minimal outgoing capacity). |
|
896 /// |
|
897 /// \pre \ref init() must be called before using this function. |
888 void calculateOut() { |
898 void calculateOut() { |
889 findMinCutOut(); |
899 findMinCutOut(); |
890 } |
900 } |
891 |
901 |
892 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
902 /// \brief Calculate a minimum cut with \f$ source \f$ on the |
893 /// target-side. |
903 /// sink-side. |
894 /// |
904 /// |
895 /// Calculates a minimum cut with \f$ source \f$ on the |
905 /// This function calculates a minimum cut with \f$ source \f$ on the |
896 /// target-side (i.e. a set \f$ X\subsetneq V \f$ with |
906 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with |
897 /// \f$ source \in X \f$ and minimal out-degree). |
907 /// \f$ source \notin X \f$ and minimal outgoing capacity). |
|
908 /// |
|
909 /// \pre \ref init() must be called before using this function. |
898 void calculateIn() { |
910 void calculateIn() { |
899 findMinCutIn(); |
911 findMinCutIn(); |
900 } |
912 } |
901 |
913 |
902 |
914 |
903 /// \brief Runs the algorithm. |
915 /// \brief Run the algorithm. |
904 /// |
916 /// |
905 /// Runs the algorithm. It finds nodes \c source and \c target |
917 /// This function runs the algorithm. It finds nodes \c source and |
906 /// arbitrarily and then calls \ref init(), \ref calculateOut() |
918 /// \c target arbitrarily and then calls \ref init(), \ref calculateOut() |
907 /// and \ref calculateIn(). |
919 /// and \ref calculateIn(). |
908 void run() { |
920 void run() { |
909 init(); |
921 init(); |
910 calculateOut(); |
922 calculateOut(); |
911 calculateIn(); |
923 calculateIn(); |
912 } |
924 } |
913 |
925 |
914 /// \brief Runs the algorithm. |
926 /// \brief Run the algorithm. |
915 /// |
927 /// |
916 /// Runs the algorithm. It uses the given \c source node, finds a |
928 /// This function runs the algorithm. It uses the given \c source node, |
917 /// proper \c target and then calls the \ref init(), \ref |
929 /// finds a proper \c target node and then calls the \ref init(), |
918 /// calculateOut() and \ref calculateIn(). |
930 /// \ref calculateOut() and \ref calculateIn(). |
919 void run(const Node& s) { |
931 void run(const Node& s) { |
920 init(s); |
932 init(s); |
921 calculateOut(); |
933 calculateOut(); |
922 calculateIn(); |
934 calculateIn(); |
923 } |
935 } |
924 |
936 |
925 /// @} |
937 /// @} |
926 |
938 |
927 /// \name Query Functions |
939 /// \name Query Functions |
928 /// The result of the %HaoOrlin algorithm |
940 /// The result of the %HaoOrlin algorithm |
929 /// can be obtained using these functions. |
941 /// can be obtained using these functions.\n |
930 /// \n |
942 /// \ref run(), \ref calculateOut() or \ref calculateIn() |
931 /// Before using these functions, either \ref run(), \ref |
943 /// should be called before using them. |
932 /// calculateOut() or \ref calculateIn() must be called. |
|
933 |
944 |
934 /// @{ |
945 /// @{ |
935 |
946 |
936 /// \brief Returns the value of the minimum value cut. |
947 /// \brief Return the value of the minimum cut. |
937 /// |
948 /// |
938 /// Returns the value of the minimum value cut. |
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 Value minCutValue() const { |
953 Value minCutValue() const { |
940 return _min_cut; |
954 return _min_cut; |
941 } |
955 } |
942 |
956 |
943 |
957 |
944 /// \brief Returns a minimum cut. |
958 /// \brief Return a minimum cut. |
945 /// |
959 /// |
946 /// Sets \c nodeMap to the characteristic vector of a minimum |
960 /// This function sets \c cutMap to the characteristic vector of a |
947 /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$ |
961 /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$ |
948 /// with minimal out-degree (i.e. \c nodeMap will be true exactly |
962 /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly |
949 /// for the nodes of \f$ X \f$). \pre nodeMap should be a |
963 /// for the nodes of \f$ X \f$). |
950 /// bool-valued node-map. |
964 /// |
951 template <typename NodeMap> |
965 /// \param cutMap A \ref concepts::WriteMap "writable" node map with |
952 Value minCutMap(NodeMap& nodeMap) const { |
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 for (NodeIt it(_graph); it != INVALID; ++it) { |
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 return _min_cut; |
977 return _min_cut; |
957 } |
978 } |
958 |
979 |
959 /// @} |
980 /// @} |
960 |
981 |
961 }; //class HaoOrlin |
982 }; //class HaoOrlin |
962 |
983 |
963 |
|
964 } //namespace lemon |
984 } //namespace lemon |
965 |
985 |
966 #endif //LEMON_HAO_ORLIN_H |
986 #endif //LEMON_HAO_ORLIN_H |