Changeset 1968:78e6e2d1fd96 in lemon0.x for lemon
 Timestamp:
 02/14/06 11:41:16 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2547
 Location:
 lemon
 Files:

 1 edited
 1 moved
Legend:
 Unmodified
 Added
 Removed

lemon/Makefile.am
r1967 r1968 59 59 max_matching.h \ 60 60 min_cost_flow.h \ 61 minim al_cut.h \61 minimum_cut.h \ 62 62 suurballe.h \ 63 63 preflow.h \ 
lemon/minimum_cut.h
r1967 r1968 1 1 /* * C++ * 2 * lemon/minim al_cut.h  Part of LEMON, a generic C++ optimization library2 * lemon/minimum_cut.h  Part of LEMON, a generic C++ optimization library 3 3 * 4 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport … … 15 15 */ 16 16 17 #ifndef LEMON_MINIM AL_CUT_H18 #define LEMON_MINIM AL_CUT_H17 #ifndef LEMON_MINIMUM_CUT_H 18 #define LEMON_MINIMUM_CUT_H 19 19 20 20 21 21 /// \ingroup topology 22 22 /// \file 23 /// \brief Maximum cardinality search and minim alcut in undirected graphs.23 /// \brief Maximum cardinality search and minimum cut in undirected graphs. 24 24 25 25 #include <lemon/list_graph.h> … … 35 35 namespace lemon { 36 36 37 namespace _minim al_cut_bits {37 namespace _minimum_cut_bits { 38 38 39 39 template <typename CapacityMap> … … 98 98 /// 99 99 /// \sa MaxCardinalitySearch 100 typedef typename _minim al_cut_bits100 typedef typename _minimum_cut_bits 101 101 ::HeapSelector<CapacityMap> 102 102 ::template Selector<typename Graph::Node, Value, HeapCrossRef> … … 689 689 }; 690 690 691 /// \brief Default traits class of Minim alCut class.691 /// \brief Default traits class of MinimumCut class. 692 692 /// 693 /// Default traits class of Minim alCut class.693 /// Default traits class of MinimumCut class. 694 694 /// \param Graph Graph type. 695 695 /// \param CapacityMap Type of length map. 696 696 template <typename _Graph, typename _CapacityMap> 697 struct Minim alCutDefaultTraits {697 struct MinimumCutDefaultTraits { 698 698 /// \brief The type of the capacity of the edges. 699 699 typedef typename _CapacityMap::Value Value; … … 757 757 } 758 758 759 /// \brief The heap type used by Minim alCut algorithm.760 /// 761 /// The heap type used by Minim alCut algorithm. It should759 /// \brief The heap type used by MinimumCut algorithm. 760 /// 761 /// The heap type used by MinimumCut algorithm. It should 762 762 /// maximalize the priorities and the heap's key type is 763 763 /// the work graph's node. 764 764 /// 765 765 /// \sa BinHeap 766 /// \sa Minim alCut767 typedef typename _minim al_cut_bits766 /// \sa MinimumCut 767 typedef typename _minimum_cut_bits 768 768 ::HeapSelector<CapacityMap> 769 769 ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef> … … 807 807 }; 808 808 809 namespace _minim al_cut_bits {809 namespace _minimum_cut_bits { 810 810 template <typename _Key> 811 811 class LastTwoMap { … … 831 831 /// \ingroup topology 832 832 /// 833 /// \brief Calculates the minim alcut in an undirected graph.833 /// \brief Calculates the minimum cut in an undirected graph. 834 834 /// 835 /// Calculates the minim alcut in an undirected graph.835 /// Calculates the minimum cut in an undirected graph. 836 836 /// The algorithm separates the graph's nodes to two partitions with the 837 /// minim alsum of edge capacities between the two partitions. The837 /// minimum sum of edge capacities between the two partitions. The 838 838 /// algorithm can be used to test the network reliability specifically 839 839 /// to test how many links have to be destroyed in the network to split it … … 848 848 template <typename _Graph = ListUGraph, 849 849 typename _CapacityMap = typename _Graph::template UEdgeMap<int>, 850 typename _Traits = Minim alCutDefaultTraits<_Graph, _CapacityMap> >850 typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> > 851 851 #endif 852 class Minim alCut {852 class MinimumCut { 853 853 public: 854 854 /// \brief \ref Exception for uninitialized parameters. … … 859 859 public: 860 860 virtual const char* exceptionName() const { 861 return "lemon::Minim alCut::UninitializedParameter";861 return "lemon::MinimumCut::UninitializedParameter"; 862 862 } 863 863 }; … … 905 905 /// the capacity type to constMap<UEdge, int, 1>() 906 906 struct DefNeutralCapacity 907 : public Minim alCut<Graph, CapacityMap, DefNeutralCapacityTraits> {908 typedef Minim alCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;907 : public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 908 typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create; 909 909 }; 910 910 … … 928 928 template <class H, class CR = typename Graph::template NodeMap<int> > 929 929 struct DefHeap 930 : public Minim alCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {931 typedef Minim alCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;930 : public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 931 typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create; 932 932 }; 933 933 … … 953 953 template <class H, class CR = typename Graph::template NodeMap<int> > 954 954 struct DefStandardHeap 955 : public Minim alCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {956 typedef Minim alCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >955 : public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 956 typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 957 957 Create; 958 958 }; … … 990 990 bool local_heap; 991 991 992 /// The minim alcut value.993 Value _minim al_cut;992 /// The minimum cut value. 993 Value _minimum_cut; 994 994 /// The number of the nodes of the work graph. 995 995 int _node_num; … … 1053 1053 public : 1054 1054 1055 typedef Minim alCut Create;1055 typedef MinimumCut Create; 1056 1056 1057 1057 … … 1060 1060 ///\param graph the graph the algorithm will run on. 1061 1061 ///\param capacity the capacity map used by the algorithm. 1062 Minim alCut(const Graph& graph, const CapacityMap& capacity)1062 MinimumCut(const Graph& graph, const CapacityMap& capacity) 1063 1063 : _graph(&graph), 1064 1064 _capacity(&capacity), local_capacity(false), … … 1077 1077 /// 1078 1078 ///\param graph the graph the algorithm will run on. 1079 Minim alCut(const Graph& graph)1079 MinimumCut(const Graph& graph) 1080 1080 : _graph(&graph), 1081 1081 _capacity(0), local_capacity(false), … … 1089 1089 /// 1090 1090 /// Destructor. 1091 ~Minim alCut() {1091 ~MinimumCut() { 1092 1092 if (local_heap) delete _heap; 1093 1093 if (local_heap_cross_ref) delete _heap_cross_ref; … … 1107 1107 /// automatically allocated heap and cross reference, of course. 1108 1108 /// \return <tt> (*this) </tt> 1109 Minim alCut &heap(Heap& heap, HeapCrossRef &crossRef)1109 MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef) 1110 1110 { 1111 1111 if (local_heap_cross_ref) { … … 1129 1129 /// automatically allocated graph, of course. 1130 1130 /// \return <tt> (*this) </tt> 1131 Minim alCut &workGraph(WorkGraph& work_graph)1131 MinimumCut &workGraph(WorkGraph& work_graph) 1132 1132 { 1133 1133 if(local_work_graph) { … … 1146 1146 /// automatically allocated graph, of course. 1147 1147 /// \return <tt> (*this) </tt> 1148 Minim alCut &workCapacityMap(WorkCapacityMap& work_capacity_map)1148 MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map) 1149 1149 { 1150 1150 if(local_work_capacity) { … … 1179 1179 /// Processes the next phase in the algorithm. The function 1180 1180 /// should be called countNodes(graph)  1 times to get 1181 /// surely the minim alcut in the graph. The1181 /// surely the minimum cut in the graph. The 1182 1182 /// 1183 1183 ///\return %True when the algorithm finished. 1184 1184 bool processNextPhase() { 1185 1185 if (_node_num <= 1) return true; 1186 using namespace _minim al_cut_bits;1186 using namespace _minimum_cut_bits; 1187 1187 1188 1188 typedef typename WorkGraph::Node Node; … … 1235 1235 } 1236 1236 1237 if (_first_node == INVALID  current_cut < _minim al_cut) {1237 if (_first_node == INVALID  current_cut < _minimum_cut) { 1238 1238 _first_node = (*_first)[first_node]; 1239 1239 _last_node = (*_last)[first_node]; 1240 _minim al_cut = current_cut;1240 _minimum_cut = current_cut; 1241 1241 } 1242 1242 … … 1268 1268 1269 1269 1270 /// \brief Runs %Minim alCut algorithm.1271 /// 1272 /// This method runs the %Minim alcut algorithm1270 /// \brief Runs %MinimumCut algorithm. 1271 /// 1272 /// This method runs the %Minimum cut algorithm 1273 1273 /// 1274 1274 /// \note mc.run(s) is just a shortcut of the following code. … … 1285 1285 1286 1286 /// \name Query Functions 1287 /// The result of the %Minim alCut algorithm can be obtained using these1287 /// The result of the %MinimumCut algorithm can be obtained using these 1288 1288 /// functions.\n 1289 1289 /// Before the use of these functions, … … 1292 1292 ///@{ 1293 1293 1294 /// \brief Returns the minim alcut value.1295 /// 1296 /// Returns the minim alcut value if the algorithm finished.1294 /// \brief Returns the minimum cut value. 1295 /// 1296 /// Returns the minimum cut value if the algorithm finished. 1297 1297 /// After the first processNextPhase() it is a value of a 1298 1298 /// valid cut in the graph. 1299 1299 Value minCut() const { 1300 return _minim al_cut;1301 } 1302 1303 /// \brief Returns a minim alcut in a NodeMap.1300 return _minimum_cut; 1301 } 1302 1303 /// \brief Returns a minimum cut in a NodeMap. 1304 1304 /// 1305 1305 /// It sets the nodes of one of the two partitions to true in … … 1316 1316 } 1317 1317 1318 /// \brief Returns a minim alcut in a NodeMap.1318 /// \brief Returns a minimum cut in a NodeMap. 1319 1319 /// 1320 1320 /// It sets the nodes of one of the two partitions to true and … … 1330 1330 } 1331 1331 1332 /// \brief Returns a minim alcut in an EdgeMap.1332 /// \brief Returns a minimum cut in an EdgeMap. 1333 1333 /// 1334 1334 /// If an undirected edge is cut edge then it will be
Note: See TracChangeset
for help on using the changeset viewer.