r1019:234d635ad721
Mon, 15 Nov 2010 08:45:12
[Not Reviewed]
0 comments (0 inline)
0
1
0
21
11
| ... | ... |
@@ -50,14 +50,14 @@ |
| 50 | 50 |
/// with \f$ source \f$ on the sink-side (i.e. a set |
| 51 | 51 |
/// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing |
| 52 | 52 |
/// capacity). Obviously, the smaller of these two cuts will be a |
| 53 | 53 |
/// minimum cut of \f$ D \f$. The algorithm is a modified |
| 54 | 54 |
/// preflow push-relabel algorithm. Our implementation calculates |
| 55 | 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 |
|
| 57 |
/// purpose of such algorithm is e.g. testing network reliability. |
|
| 56 |
/// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable |
|
| 57 |
/// use of this algorithm is testing network reliability. |
|
| 58 | 58 |
/// |
| 59 | 59 |
/// For an undirected graph you can run just the first phase of the |
| 60 | 60 |
/// algorithm or you can use the algorithm of Nagamochi and Ibaraki, |
| 61 | 61 |
/// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ |
| 62 | 62 |
/// time. It is implemented in the NagamochiIbaraki algorithm class. |
| 63 | 63 |
/// |
| ... | ... |
@@ -909,47 +909,51 @@ |
| 909 | 909 |
/// \brief Calculate a minimum cut with \f$ source \f$ on the |
| 910 | 910 |
/// source-side. |
| 911 | 911 |
/// |
| 912 | 912 |
/// This function calculates a minimum cut with \f$ source \f$ on the |
| 913 | 913 |
/// source-side (i.e. a set \f$ X\subsetneq V \f$ with |
| 914 | 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 | 918 |
/// \pre \ref init() must be called before using this function. |
| 917 | 919 |
void calculateOut() {
|
| 918 | 920 |
findMinCutOut(); |
| 919 | 921 |
} |
| 920 | 922 |
|
| 921 | 923 |
/// \brief Calculate a minimum cut with \f$ source \f$ on the |
| 922 | 924 |
/// sink-side. |
| 923 | 925 |
/// |
| 924 | 926 |
/// This function calculates a minimum cut with \f$ source \f$ on the |
| 925 | 927 |
/// sink-side (i.e. a set \f$ X\subsetneq V \f$ with |
| 926 | 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 | 932 |
/// \pre \ref init() must be called before using this function. |
| 929 | 933 |
void calculateIn() {
|
| 930 | 934 |
findMinCutIn(); |
| 931 | 935 |
} |
| 932 | 936 |
|
| 933 | 937 |
|
| 934 | 938 |
/// \brief Run the algorithm. |
| 935 | 939 |
/// |
| 936 |
/// This function runs the algorithm. It finds nodes \c source and |
|
| 937 |
/// \c target arbitrarily and then calls \ref init(), \ref calculateOut() |
|
| 940 |
/// This function runs the algorithm. It chooses source node, |
|
| 941 |
/// then calls \ref init(), \ref calculateOut() |
|
| 938 | 942 |
/// and \ref calculateIn(). |
| 939 | 943 |
void run() {
|
| 940 | 944 |
init(); |
| 941 | 945 |
calculateOut(); |
| 942 | 946 |
calculateIn(); |
| 943 | 947 |
} |
| 944 | 948 |
|
| 945 | 949 |
/// \brief Run the algorithm. |
| 946 | 950 |
/// |
| 947 |
/// This function runs the algorithm. It uses the given \c source node, |
|
| 948 |
/// finds a proper \c target node and then calls the \ref init(), |
|
| 949 |
/// |
|
| 951 |
/// This function runs the algorithm. It calls \ref init(), |
|
| 952 |
/// \ref calculateOut() and \ref calculateIn() with the given |
|
| 953 |
/// source node. |
|
| 950 | 954 |
void run(const Node& s) {
|
| 951 | 955 |
init(s); |
| 952 | 956 |
calculateOut(); |
| 953 | 957 |
calculateIn(); |
| 954 | 958 |
} |
| 955 | 959 |
|
| ... | ... |
@@ -962,26 +966,32 @@ |
| 962 | 966 |
/// should be called before using them. |
| 963 | 967 |
|
| 964 | 968 |
/// @{
|
| 965 | 969 |
|
| 966 | 970 |
/// \brief Return the value of the minimum cut. |
| 967 | 971 |
/// |
| 968 |
/// This function returns the value of the |
|
| 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 | 976 |
/// \pre \ref run(), \ref calculateOut() or \ref calculateIn() |
| 971 | 977 |
/// must be called before using this function. |
| 972 | 978 |
Value minCutValue() const {
|
| 973 | 979 |
return _min_cut; |
| 974 | 980 |
} |
| 975 | 981 |
|
| 976 | 982 |
|
| 977 | 983 |
/// \brief Return a minimum cut. |
| 978 | 984 |
/// |
| 979 |
/// This function sets \c cutMap to the characteristic vector of a |
|
| 980 |
/// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$ |
|
| 981 |
/// |
|
| 985 |
/// This function gives the best cut found by the |
|
| 986 |
/// previously called \ref run(), \ref calculateOut() or \ref |
|
| 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 | 992 |
/// for the nodes of \f$ X \f$). |
| 983 | 993 |
/// |
| 984 | 994 |
/// \param cutMap A \ref concepts::WriteMap "writable" node map with |
| 985 | 995 |
/// \c bool (or convertible) value type. |
| 986 | 996 |
/// |
| 987 | 997 |
/// \return The value of the minimum cut. |
0 comments (0 inline)