845 /// the network reliability specifically to test how many links have |
845 /// the network reliability specifically to test how many links have |
846 /// to be destroyed in the network to split it at least two |
846 /// to be destroyed in the network to split it at least two |
847 /// distinict subnetwork. |
847 /// distinict subnetwork. |
848 /// |
848 /// |
849 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with |
849 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with |
850 /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. |
850 /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. |
851 /// When capacity map is neutral then it uses BucketHeap which |
851 /// When unit capacity minimum cut is computed then it uses |
852 /// results \f$ O(ne) \f$ time complexity. |
852 /// BucketHeap which results \f$ O(ne) \f$ time complexity. |
853 /// |
853 /// |
854 /// \warning The value type of the capacity map should be able to hold |
854 /// \warning The value type of the capacity map should be able to hold |
855 /// any cut value of the graph, otherwise the result can overflow. |
855 /// any cut value of the graph, otherwise the result can overflow. |
856 #ifdef DOXYGEN |
856 #ifdef DOXYGEN |
857 template <typename _Graph, typename _CapacityMap, typename _Traits> |
857 template <typename _Graph, typename _CapacityMap, typename _Traits> |
904 |
904 |
905 ///\name Named template parameters |
905 ///\name Named template parameters |
906 |
906 |
907 ///@{ |
907 ///@{ |
908 |
908 |
909 struct DefNeutralCapacityTraits : public Traits { |
909 struct DefUnitCapacityTraits : public Traits { |
910 typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap; |
910 typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap; |
911 static CapacityMap *createCapacityMap(const Graph&) { |
911 static CapacityMap *createCapacityMap(const Graph&) { |
912 return new CapacityMap(); |
912 return new CapacityMap(); |
913 } |
913 } |
914 }; |
914 }; |
915 /// \brief \ref named-templ-param "Named parameter" for setting |
915 /// \brief \ref named-templ-param "Named parameter" for setting |
916 /// the capacity type to constMap<UEdge, int, 1>() |
916 /// the capacity type to constMap<UEdge, int, 1>() |
917 /// |
917 /// |
918 /// \ref named-templ-param "Named parameter" for setting |
918 /// \ref named-templ-param "Named parameter" for setting |
919 /// the capacity type to constMap<UEdge, int, 1>() |
919 /// the capacity type to constMap<UEdge, int, 1>() |
920 struct DefNeutralCapacity |
920 struct DefUnitCapacity |
921 : public NagamochiIbaraki<Graph, CapacityMap, |
921 : public NagamochiIbaraki<Graph, CapacityMap, |
922 DefNeutralCapacityTraits> { |
922 DefUnitCapacityTraits> { |
923 typedef NagamochiIbaraki<Graph, CapacityMap, |
923 typedef NagamochiIbaraki<Graph, CapacityMap, |
924 DefNeutralCapacityTraits> Create; |
924 DefUnitCapacityTraits> Create; |
925 }; |
925 }; |
926 |
926 |
927 |
927 |
928 template <class H, class CR> |
928 template <class H, class CR> |
929 struct DefHeapTraits : public Traits { |
929 struct DefHeapTraits : public Traits { |
1132 |
1132 |
1133 /// \brief Constructor. |
1133 /// \brief Constructor. |
1134 /// |
1134 /// |
1135 /// This constructor can be used only when the Traits class |
1135 /// This constructor can be used only when the Traits class |
1136 /// defines how can we instantiate a local capacity map. |
1136 /// defines how can we instantiate a local capacity map. |
1137 /// If the DefNeutralCapacity used the algorithm automatically |
1137 /// If the DefUnitCapacity used the algorithm automatically |
1138 /// construct the capacity map. |
1138 /// construct the capacity map. |
1139 /// |
1139 /// |
1140 ///\param graph the graph the algorithm will run on. |
1140 ///\param graph the graph the algorithm will run on. |
1141 NagamochiIbaraki(const Graph& graph) |
1141 NagamochiIbaraki(const Graph& graph) |
1142 : _graph(&graph), |
1142 : _graph(&graph), |