828 }; |
828 }; |
829 } |
829 } |
830 |
830 |
831 /// \ingroup topology |
831 /// \ingroup topology |
832 /// |
832 /// |
833 /// \brief Calculates the min cut in an undirected graph. |
833 /// \brief Calculates the minimum cut in an undirected graph. |
834 /// |
834 /// |
835 /// Calculates the min cut in an undirected graph. |
835 /// Calculates the minimum cut in an undirected graph with the |
836 /// The algorithm separates the graph's nodes into two partitions with the |
836 /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's |
837 /// min sum of edge capacities between the two partitions. The |
837 /// nodes into two partitions with the minimum sum of edge capacities |
838 /// algorithm can be used to test the network reliability specifically |
838 /// between the two partitions. The algorithm can be used to test |
839 /// to test how many links have to be destroyed in the network to split it |
839 /// the network reliability specifically to test how many links have |
840 /// at least two distinict subnetwork. |
840 /// to be destroyed in the network to split it at least two |
|
841 /// distinict subnetwork. |
841 /// |
842 /// |
842 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with |
843 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with |
843 /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When |
844 /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) |
844 /// the neutral capacity map is used then it uses BucketHeap which |
845 /// \f$. When capacity map is neutral then it uses BucketHeap which |
845 /// results \f$ O(ne) \f$ time complexity. |
846 /// results \f$ O(ne) \f$ time complexity. |
846 #ifdef DOXYGEN |
847 #ifdef DOXYGEN |
847 template <typename _Graph, typename _CapacityMap, typename _Traits> |
848 template <typename _Graph, typename _CapacityMap, typename _Traits> |
848 #else |
849 #else |
849 template <typename _Graph = ListUGraph, |
850 template <typename _Graph = ListUGraph, |