Changeset 1975:64db671eda28 in lemon0.x
 Timestamp:
 02/20/06 10:40:07 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2560
 Location:
 lemon
 Files:

 1 edited
 1 moved
Legend:
 Unmodified
 Added
 Removed

lemon/Makefile.am
r1971 r1975 62 62 max_matching.h \ 63 63 min_cost_flow.h \ 64 min imum_cut.h \64 min_cut.h \ 65 65 suurballe.h \ 66 66 preflow.h \ 
lemon/min_cut.h
r1973 r1975 1 1 /* * C++ * 2 * lemon/min imum_cut.h  Part of LEMON, a generic C++ optimization library2 * lemon/min_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_MIN IMUM_CUT_H18 #define LEMON_MIN IMUM_CUT_H17 #ifndef LEMON_MIN_CUT_H 18 #define LEMON_MIN_CUT_H 19 19 20 20 21 21 /// \ingroup topology 22 22 /// \file 23 /// \brief Maximum cardinality search and min imumcut in undirected graphs.23 /// \brief Maximum cardinality search and min cut in undirected graphs. 24 24 25 25 #include <lemon/list_graph.h> … … 35 35 namespace lemon { 36 36 37 namespace _min imum_cut_bits {37 namespace _min_cut_bits { 38 38 39 39 template <typename CapacityMap> … … 98 98 /// 99 99 /// \sa MaxCardinalitySearch 100 typedef typename _min imum_cut_bits100 typedef typename _min_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 Min imumCut class.691 /// \brief Default traits class of MinCut class. 692 692 /// 693 /// Default traits class of Min imumCut class.693 /// Default traits class of MinCut class. 694 694 /// \param Graph Graph type. 695 695 /// \param CapacityMap Type of length map. 696 696 template <typename _Graph, typename _CapacityMap> 697 struct Min imumCutDefaultTraits {697 struct MinCutDefaultTraits { 698 698 /// \brief The type of the capacity of the edges. 699 699 typedef typename _CapacityMap::Value Value; … … 702 702 typedef _Graph Graph; 703 703 704 /// The WorkGraph type which is an EraseableGraph705 typedef ListUGraph WorkGraph;706 707 /// \brief Instantiates a WorkGraph.708 /// 709 /// This function instantiates a \ref WorkGraph.710 static WorkGraph *createWorkGraph() {711 return new WorkGraph();704 /// The AuxGraph type which is an EraseableGraph 705 typedef ListUGraph AuxGraph; 706 707 /// \brief Instantiates a AuxGraph. 708 /// 709 /// This function instantiates a \ref AuxGraph. 710 static AuxGraph *createAuxGraph() { 711 return new AuxGraph(); 712 712 } 713 713 … … 730 730 } 731 731 732 /// \brief The WorkCapacityMap type733 /// 734 /// The type of the map that stores the working edge capacities.735 typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;736 737 /// \brief Instantiates a WorkCapacityMap.738 /// 739 /// This function instantiates a \ref WorkCapacityMap.740 static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {741 return new WorkCapacityMap(graph);732 /// \brief The AuxCapacityMap type 733 /// 734 /// The type of the map that stores the auxing edge capacities. 735 typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap; 736 737 /// \brief Instantiates a AuxCapacityMap. 738 /// 739 /// This function instantiates a \ref AuxCapacityMap. 740 static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) { 741 return new AuxCapacityMap(graph); 742 742 } 743 743 … … 746 746 /// The cross reference type used by heap. 747 747 /// Usually it is \c Graph::NodeMap<int>. 748 typedef WorkGraph::NodeMap<int> HeapCrossRef;748 typedef AuxGraph::NodeMap<int> HeapCrossRef; 749 749 750 750 /// \brief Instantiates a HeapCrossRef. … … 753 753 /// \param graph is the graph, to which we would like to define the 754 754 /// HeapCrossRef. 755 static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {755 static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) { 756 756 return new HeapCrossRef(graph); 757 757 } 758 758 759 /// \brief The heap type used by Min imumCut algorithm.760 /// 761 /// The heap type used by Min imumCut algorithm. It should759 /// \brief The heap type used by MinCut algorithm. 760 /// 761 /// The heap type used by MinCut algorithm. It should 762 762 /// maximalize the priorities and the heap's key type is 763 /// the workgraph's node.763 /// the aux graph's node. 764 764 /// 765 765 /// \sa BinHeap 766 /// \sa Min imumCut767 typedef typename _min imum_cut_bits766 /// \sa MinCut 767 typedef typename _min_cut_bits 768 768 ::HeapSelector<CapacityMap> 769 ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>769 ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef> 770 770 ::Heap Heap; 771 771 … … 778 778 } 779 779 780 /// \brief Map from the WorkGraph's node type to the Graph's node type.781 /// 782 /// Map from the WorkGraph's node type to the Graph's node type.783 typedef typename WorkGraph780 /// \brief Map from the AuxGraph's node type to the Graph's node type. 781 /// 782 /// Map from the AuxGraph's node type to the Graph's node type. 783 typedef typename AuxGraph 784 784 ::template NodeMap<typename Graph::Node> NodeRefMap; 785 785 … … 787 787 /// 788 788 /// This function instantiates a \ref NodeRefMap. 789 static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {789 static NodeRefMap *createNodeRefMap(const AuxGraph& graph) { 790 790 return new NodeRefMap(graph); 791 791 } … … 807 807 }; 808 808 809 namespace _min imum_cut_bits {809 namespace _min_cut_bits { 810 810 template <typename _Key> 811 811 class LastTwoMap { … … 831 831 /// \ingroup topology 832 832 /// 833 /// \brief Calculates the min imumcut in an undirected graph.833 /// \brief Calculates the min cut in an undirected graph. 834 834 /// 835 /// Calculates the min imumcut in an undirected graph.835 /// Calculates the min cut in an undirected graph. 836 836 /// The algorithm separates the graph's nodes to two partitions with the 837 /// min imumsum of edge capacities between the two partitions. The838 /// algorithm can be used to test the net workreliability specifically839 /// to test how many links have to be destroyed in the net workto split it840 /// at least two distinict subnet work.837 /// min sum of edge capacities between the two partitions. The 838 /// algorithm can be used to test the netaux reliability specifically 839 /// to test how many links have to be destroyed in the netaux to split it 840 /// at least two distinict subnetaux. 841 841 /// 842 842 /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci … … 848 848 template <typename _Graph = ListUGraph, 849 849 typename _CapacityMap = typename _Graph::template UEdgeMap<int>, 850 typename _Traits = Min imumCutDefaultTraits<_Graph, _CapacityMap> >850 typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> > 851 851 #endif 852 class Min imumCut {852 class MinCut { 853 853 public: 854 854 /// \brief \ref Exception for uninitialized parameters. … … 859 859 public: 860 860 virtual const char* exceptionName() const { 861 return "lemon::Min imumCut::UninitializedParameter";861 return "lemon::MinCut::UninitializedParameter"; 862 862 } 863 863 }; … … 874 874 /// The type of the map that stores the edge capacities. 875 875 typedef typename Traits::CapacityMap CapacityMap; 876 /// The type of the workgraph877 typedef typename Traits:: WorkGraph WorkGraph;878 /// The type of the workcapacity map879 typedef typename Traits:: WorkCapacityMap WorkCapacityMap;876 /// The type of the aux graph 877 typedef typename Traits::AuxGraph AuxGraph; 878 /// The type of the aux capacity map 879 typedef typename Traits::AuxCapacityMap AuxCapacityMap; 880 880 /// The cross reference type used for the current heap. 881 881 typedef typename Traits::HeapCrossRef HeapCrossRef; 882 882 /// The heap type used by the max cardinality algorithm. 883 883 typedef typename Traits::Heap Heap; 884 /// The node refrefernces between the original and workgraph type.884 /// The node refrefernces between the original and aux graph type. 885 885 typedef typename Traits::NodeRefMap NodeRefMap; 886 886 /// The list node refrefernces in the original graph type. … … 905 905 /// the capacity type to constMap<UEdge, int, 1>() 906 906 struct DefNeutralCapacity 907 : public Min imumCut<Graph, CapacityMap, DefNeutralCapacityTraits> {908 typedef Min imumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;907 : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 908 typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create; 909 909 }; 910 910 … … 914 914 typedef CR HeapCrossRef; 915 915 typedef H Heap; 916 static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {916 static HeapCrossRef *createHeapCrossRef(const AuxGraph &) { 917 917 throw UninitializedParameter(); 918 918 } … … 928 928 template <class H, class CR = typename Graph::template NodeMap<int> > 929 929 struct DefHeap 930 : public Min imumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > {931 typedef Min imumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;930 : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 931 typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create; 932 932 }; 933 933 … … 936 936 typedef CR HeapCrossRef; 937 937 typedef H Heap; 938 static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {938 static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) { 939 939 return new HeapCrossRef(graph); 940 940 } … … 953 953 template <class H, class CR = typename Graph::template NodeMap<int> > 954 954 struct DefStandardHeap 955 : public Min imumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > {956 typedef Min imumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> >955 : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 956 typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 957 957 Create; 958 958 }; … … 970 970 bool local_capacity; 971 971 972 /// Pointer to the workgraph.973 WorkGraph *_work_graph;974 /// \brief Indicates if \ref _ work_graph is locally allocated972 /// Pointer to the aux graph. 973 AuxGraph *_aux_graph; 974 /// \brief Indicates if \ref _aux_graph is locally allocated 975 975 /// (\c true) or not. 976 bool local_ work_graph;977 /// Pointer to the workcapacity map978 WorkCapacityMap *_work_capacity;979 /// \brief Indicates if \ref _ work_capacity is locally allocated976 bool local_aux_graph; 977 /// Pointer to the aux capacity map 978 AuxCapacityMap *_aux_capacity; 979 /// \brief Indicates if \ref _aux_capacity is locally allocated 980 980 /// (\c true) or not. 981 bool local_ work_capacity;981 bool local_aux_capacity; 982 982 /// Pointer to the heap cross references. 983 983 HeapCrossRef *_heap_cross_ref; … … 990 990 bool local_heap; 991 991 992 /// The min imumcut value.993 Value _min imum_cut;994 /// The number of the nodes of the workgraph.992 /// The min cut value. 993 Value _min_cut; 994 /// The number of the nodes of the aux graph. 995 995 int _node_num; 996 996 /// The first and last node of the min cut in the next list; … … 998 998 999 999 /// \brief The first and last element in the list associated 1000 /// to the workgraph node.1000 /// to the aux graph node. 1001 1001 NodeRefMap *_first, *_last; 1002 1002 /// \brief The next node in the node lists. … … 1008 1008 _capacity = Traits::createCapacityMap(*_graph); 1009 1009 } 1010 if(!_ work_graph) {1011 local_ work_graph = true;1012 _ work_graph = Traits::createWorkGraph();1013 } 1014 if(!_ work_capacity) {1015 local_ work_capacity = true;1016 _ work_capacity = Traits::createWorkCapacityMap(*_work_graph);1017 } 1018 1019 _first = Traits::createNodeRefMap(*_ work_graph);1020 _last = Traits::createNodeRefMap(*_ work_graph);1010 if(!_aux_graph) { 1011 local_aux_graph = true; 1012 _aux_graph = Traits::createAuxGraph(); 1013 } 1014 if(!_aux_capacity) { 1015 local_aux_capacity = true; 1016 _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph); 1017 } 1018 1019 _first = Traits::createNodeRefMap(*_aux_graph); 1020 _last = Traits::createNodeRefMap(*_aux_graph); 1021 1021 1022 1022 _next = Traits::createListRefMap(*_graph); 1023 1023 1024 typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);1024 typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph); 1025 1025 1026 1026 for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) { 1027 1027 _next>set(it, INVALID); 1028 typename WorkGraph::Node node = _work_graph>addNode();1028 typename AuxGraph::Node node = _aux_graph>addNode(); 1029 1029 _first>set(node, it); 1030 1030 _last>set(node, it); … … 1034 1034 for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) { 1035 1035 if (_graph>source(it) == _graph>target(it)) continue; 1036 typename WorkGraph::UEdge uedge =1037 _ work_graph>addEdge(ref[_graph>source(it)],1036 typename AuxGraph::UEdge uedge = 1037 _aux_graph>addEdge(ref[_graph>source(it)], 1038 1038 ref[_graph>target(it)]); 1039 _ work_capacity>set(uedge, (*_capacity)[it]);1039 _aux_capacity>set(uedge, (*_capacity)[it]); 1040 1040 1041 1041 } … … 1043 1043 if (!_heap_cross_ref) { 1044 1044 local_heap_cross_ref = true; 1045 _heap_cross_ref = Traits::createHeapCrossRef(*_ work_graph);1045 _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph); 1046 1046 } 1047 1047 if (!_heap) { … … 1053 1053 public : 1054 1054 1055 typedef Min imumCut Create;1055 typedef MinCut 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 Min imumCut(const Graph& graph, const CapacityMap& capacity)1062 MinCut(const Graph& graph, const CapacityMap& capacity) 1063 1063 : _graph(&graph), 1064 1064 _capacity(&capacity), local_capacity(false), 1065 _ work_graph(0), local_work_graph(false),1066 _ work_capacity(0), local_work_capacity(false),1065 _aux_graph(0), local_aux_graph(false), 1066 _aux_capacity(0), local_aux_capacity(false), 1067 1067 _heap_cross_ref(0), local_heap_cross_ref(false), 1068 1068 _heap(0), local_heap(false), … … 1077 1077 /// 1078 1078 ///\param graph the graph the algorithm will run on. 1079 Min imumCut(const Graph& graph)1079 MinCut(const Graph& graph) 1080 1080 : _graph(&graph), 1081 1081 _capacity(0), local_capacity(false), 1082 _ work_graph(0), local_work_graph(false),1083 _ work_capacity(0), local_work_capacity(false),1082 _aux_graph(0), local_aux_graph(false), 1083 _aux_capacity(0), local_aux_capacity(false), 1084 1084 _heap_cross_ref(0), local_heap_cross_ref(false), 1085 1085 _heap(0), local_heap(false), … … 1089 1089 /// 1090 1090 /// Destructor. 1091 ~Min imumCut() {1091 ~MinCut() { 1092 1092 if (local_heap) delete _heap; 1093 1093 if (local_heap_cross_ref) delete _heap_cross_ref; … … 1095 1095 if (_last) delete _last; 1096 1096 if (_next) delete _next; 1097 if (local_ work_capacity) delete _work_capacity;1098 if (local_ work_graph) delete _work_graph;1097 if (local_aux_capacity) delete _aux_capacity; 1098 if (local_aux_graph) delete _aux_graph; 1099 1099 if (local_capacity) delete _capacity; 1100 1100 } … … 1107 1107 /// automatically allocated heap and cross reference, of course. 1108 1108 /// \return <tt> (*this) </tt> 1109 Min imumCut &heap(Heap& heap, HeapCrossRef &crossRef)1109 MinCut &heap(Heap& heap, HeapCrossRef &crossRef) 1110 1110 { 1111 1111 if (local_heap_cross_ref) { … … 1122 1122 } 1123 1123 1124 /// \brief Sets the workgraph.1125 /// 1126 /// Sets the workgraph used by algorithm.1124 /// \brief Sets the aux graph. 1125 /// 1126 /// Sets the aux graph used by algorithm. 1127 1127 /// If you don't use this function before calling \ref run(), 1128 1128 /// it will allocate one. The destuctor deallocates this 1129 1129 /// automatically allocated graph, of course. 1130 1130 /// \return <tt> (*this) </tt> 1131 Min imumCut &workGraph(WorkGraph& work_graph)1131 MinCut &auxGraph(AuxGraph& aux_graph) 1132 1132 { 1133 if(local_ work_graph) {1134 delete _ work_graph;1135 local_ work_graph=false;1136 } 1137 _ work_graph = &work_graph;1133 if(local_aux_graph) { 1134 delete _aux_graph; 1135 local_aux_graph=false; 1136 } 1137 _aux_graph = &aux_graph; 1138 1138 return *this; 1139 1139 } 1140 1140 1141 /// \brief Sets the workcapacity map.1142 /// 1143 /// Sets the workcapacity map used by algorithm.1141 /// \brief Sets the aux capacity map. 1142 /// 1143 /// Sets the aux capacity map used by algorithm. 1144 1144 /// If you don't use this function before calling \ref run(), 1145 1145 /// it will allocate one. The destuctor deallocates this 1146 1146 /// automatically allocated graph, of course. 1147 1147 /// \return <tt> (*this) </tt> 1148 Min imumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)1148 MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map) 1149 1149 { 1150 if(local_ work_capacity) {1151 delete _ work_capacity;1152 local_ work_capacity=false;1153 } 1154 _ work_capacity = &work_capacity_map;1150 if(local_aux_capacity) { 1151 delete _aux_capacity; 1152 local_aux_capacity=false; 1153 } 1154 _aux_capacity = &aux_capacity_map; 1155 1155 return *this; 1156 1156 } … … 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 min imumcut in the graph. The1181 /// surely the min 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 _min imum_cut_bits;1187 1188 typedef typename WorkGraph::Node Node;1189 typedef typename WorkGraph::NodeIt NodeIt;1190 typedef typename WorkGraph::UEdge UEdge;1191 typedef typename WorkGraph::IncEdgeIt IncEdgeIt;1186 using namespace _min_cut_bits; 1187 1188 typedef typename AuxGraph::Node Node; 1189 typedef typename AuxGraph::NodeIt NodeIt; 1190 typedef typename AuxGraph::UEdge UEdge; 1191 typedef typename AuxGraph::IncEdgeIt IncEdgeIt; 1192 1192 1193 typedef typename MaxCardinalitySearch< WorkGraph, WorkCapacityMap>::1193 typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>:: 1194 1194 template DefHeap<Heap, HeapCrossRef>:: 1195 1195 template DefCardinalityMap<NullMap<Node, Value> >:: … … 1197 1197 Create MaxCardinalitySearch; 1198 1198 1199 MaxCardinalitySearch mcs(*_ work_graph, *_work_capacity);1200 for (NodeIt it(*_ work_graph); it != INVALID; ++it) {1199 MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity); 1200 for (NodeIt it(*_aux_graph); it != INVALID; ++it) { 1201 1201 _heap_cross_ref>set(it, Heap::PRE_HEAP); 1202 1202 } … … 1211 1211 mcs.run(); 1212 1212 1213 Node new_node = _ work_graph>addNode();1214 1215 typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);1213 Node new_node = _aux_graph>addNode(); 1214 1215 typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID); 1216 1216 1217 1217 Node first_node = last_two_nodes[0]; … … 1223 1223 1224 1224 Value current_cut = 0; 1225 for (IncEdgeIt it(*_ work_graph, first_node); it != INVALID; ++it) {1226 Node node = _ work_graph>runningNode(it);1227 current_cut += (*_ work_capacity)[it];1225 for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) { 1226 Node node = _aux_graph>runningNode(it); 1227 current_cut += (*_aux_capacity)[it]; 1228 1228 if (node == second_node) continue; 1229 1229 if (edges[node] == INVALID) { 1230 edges[node] = _ work_graph>addEdge(new_node, node);1231 (*_ work_capacity)[edges[node]] = (*_work_capacity)[it];1230 edges[node] = _aux_graph>addEdge(new_node, node); 1231 (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; 1232 1232 } else { 1233 (*_ work_capacity)[edges[node]] += (*_work_capacity)[it];1233 (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; 1234 1234 } 1235 1235 } 1236 1236 1237 if (_first_node == INVALID  current_cut < _min imum_cut) {1237 if (_first_node == INVALID  current_cut < _min_cut) { 1238 1238 _first_node = (*_first)[first_node]; 1239 1239 _last_node = (*_last)[first_node]; 1240 _min imum_cut = current_cut;1241 } 1242 1243 _ work_graph>erase(first_node);1244 1245 for (IncEdgeIt it(*_ work_graph, second_node); it != INVALID; ++it) {1246 Node node = _ work_graph>runningNode(it);1240 _min_cut = current_cut; 1241 } 1242 1243 _aux_graph>erase(first_node); 1244 1245 for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) { 1246 Node node = _aux_graph>runningNode(it); 1247 1247 if (edges[node] == INVALID) { 1248 edges[node] = _ work_graph>addEdge(new_node, node);1249 (*_ work_capacity)[edges[node]] = (*_work_capacity)[it];1248 edges[node] = _aux_graph>addEdge(new_node, node); 1249 (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; 1250 1250 } else { 1251 (*_ work_capacity)[edges[node]] += (*_work_capacity)[it];1251 (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; 1252 1252 } 1253 1253 } 1254 _ work_graph>erase(second_node);1254 _aux_graph>erase(second_node); 1255 1255 1256 1256 _node_num; … … 1268 1268 1269 1269 1270 /// \brief Runs %Min imumCut algorithm.1271 /// 1272 /// This method runs the %Min imumcut algorithm1270 /// \brief Runs %MinCut algorithm. 1271 /// 1272 /// This method runs the %Min 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 %Min imumCut algorithm can be obtained using these1287 /// The result of the %MinCut 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 min imumcut value.1295 /// 1296 /// Returns the min imumcut value if the algorithm finished.1294 /// \brief Returns the min cut value. 1295 /// 1296 /// Returns the min 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 _min imum_cut;1301 } 1302 1303 /// \brief Returns a min imumcut in a NodeMap.1300 return _min_cut; 1301 } 1302 1303 /// \brief Returns a min 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 min imumcut in a NodeMap.1318 /// \brief Returns a min 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 min imumcut in an EdgeMap.1333 /// 1334 /// If an undirected edge is in a min imumcut then it will be1332 /// \brief Returns a min cut in an EdgeMap. 1333 /// 1334 /// If an undirected edge is in a min cut then it will be 1335 1335 /// set to true and the others will be set to false in the given map. 1336 1336 template <typename EdgeMap>
Note: See TracChangeset
for help on using the changeset viewer.