51 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing |
51 /// \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 /// capacity). Obviously, the smaller of these two cuts will be a |
53 /// minimum cut of \f$ D \f$. The algorithm is a modified |
53 /// minimum cut of \f$ D \f$. The algorithm is a modified |
54 /// preflow push-relabel algorithm. Our implementation calculates |
54 /// preflow push-relabel algorithm. Our implementation calculates |
55 /// 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 |
56 /// 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. A notable |
57 /// purpose of such algorithm is e.g. testing network reliability. |
57 /// use of this algorithm is testing network reliability. |
58 /// |
58 /// |
59 /// For an undirected graph you can run just the first phase of 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, |
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$ |
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. |
62 /// time. It is implemented in the NagamochiIbaraki algorithm class. |
910 /// source-side. |
910 /// source-side. |
911 /// |
911 /// |
912 /// This function calculates a minimum cut with \f$ source \f$ on the |
912 /// This function calculates a minimum cut with \f$ source \f$ on the |
913 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with |
913 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with |
914 /// \f$ source \in X \f$ and minimal outgoing capacity). |
914 /// \f$ source \in X \f$ and minimal outgoing capacity). |
|
915 /// It updates the stored cut if (and only if) the newly found one |
|
916 /// is better. |
915 /// |
917 /// |
916 /// \pre \ref init() must be called before using this function. |
918 /// \pre \ref init() must be called before using this function. |
917 void calculateOut() { |
919 void calculateOut() { |
918 findMinCutOut(); |
920 findMinCutOut(); |
919 } |
921 } |
922 /// sink-side. |
924 /// sink-side. |
923 /// |
925 /// |
924 /// This function calculates a minimum cut with \f$ source \f$ on the |
926 /// This function calculates a minimum cut with \f$ source \f$ on the |
925 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with |
927 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with |
926 /// \f$ source \notin X \f$ and minimal outgoing capacity). |
928 /// \f$ source \notin X \f$ and minimal outgoing capacity). |
|
929 /// It updates the stored cut if (and only if) the newly found one |
|
930 /// is better. |
927 /// |
931 /// |
928 /// \pre \ref init() must be called before using this function. |
932 /// \pre \ref init() must be called before using this function. |
929 void calculateIn() { |
933 void calculateIn() { |
930 findMinCutIn(); |
934 findMinCutIn(); |
931 } |
935 } |
932 |
936 |
933 |
937 |
934 /// \brief Run the algorithm. |
938 /// \brief Run the algorithm. |
935 /// |
939 /// |
936 /// This function runs the algorithm. It finds nodes \c source and |
940 /// This function runs the algorithm. It chooses source node, |
937 /// \c target arbitrarily and then calls \ref init(), \ref calculateOut() |
941 /// then calls \ref init(), \ref calculateOut() |
938 /// and \ref calculateIn(). |
942 /// and \ref calculateIn(). |
939 void run() { |
943 void run() { |
940 init(); |
944 init(); |
941 calculateOut(); |
945 calculateOut(); |
942 calculateIn(); |
946 calculateIn(); |
943 } |
947 } |
944 |
948 |
945 /// \brief Run the algorithm. |
949 /// \brief Run the algorithm. |
946 /// |
950 /// |
947 /// This function runs the algorithm. It uses the given \c source node, |
951 /// This function runs the algorithm. It calls \ref init(), |
948 /// finds a proper \c target node and then calls the \ref init(), |
952 /// \ref calculateOut() and \ref calculateIn() with the given |
949 /// \ref calculateOut() and \ref calculateIn(). |
953 /// source node. |
950 void run(const Node& s) { |
954 void run(const Node& s) { |
951 init(s); |
955 init(s); |
952 calculateOut(); |
956 calculateOut(); |
953 calculateIn(); |
957 calculateIn(); |
954 } |
958 } |
963 |
967 |
964 /// @{ |
968 /// @{ |
965 |
969 |
966 /// \brief Return the value of the minimum cut. |
970 /// \brief Return the value of the minimum cut. |
967 /// |
971 /// |
968 /// This function returns the value of the minimum cut. |
972 /// This function returns the value of the best cut found by the |
|
973 /// previously called \ref run(), \ref calculateOut() or \ref |
|
974 /// calculateIn(). |
969 /// |
975 /// |
970 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() |
976 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() |
971 /// must be called before using this function. |
977 /// must be called before using this function. |
972 Value minCutValue() const { |
978 Value minCutValue() const { |
973 return _min_cut; |
979 return _min_cut; |
974 } |
980 } |
975 |
981 |
976 |
982 |
977 /// \brief Return a minimum cut. |
983 /// \brief Return a minimum cut. |
978 /// |
984 /// |
979 /// This function sets \c cutMap to the characteristic vector of a |
985 /// This function gives the best cut found by the |
980 /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$ |
986 /// previously called \ref run(), \ref calculateOut() or \ref |
981 /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly |
987 /// calculateIn(). |
|
988 /// |
|
989 /// It sets \c cutMap to the characteristic vector of the found |
|
990 /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$ |
|
991 /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly |
982 /// for the nodes of \f$ X \f$). |
992 /// for the nodes of \f$ X \f$). |
983 /// |
993 /// |
984 /// \param cutMap A \ref concepts::WriteMap "writable" node map with |
994 /// \param cutMap A \ref concepts::WriteMap "writable" node map with |
985 /// \c bool (or convertible) value type. |
995 /// \c bool (or convertible) value type. |
986 /// |
996 /// |