equal
deleted
inserted
replaced
152 /// |
152 /// |
153 /// \brief Maximum Cardinality Search algorithm class. |
153 /// \brief Maximum Cardinality Search algorithm class. |
154 /// |
154 /// |
155 /// This class provides an efficient implementation of Maximum Cardinality |
155 /// This class provides an efficient implementation of Maximum Cardinality |
156 /// Search algorithm. The maximum cardinality search chooses first time any |
156 /// Search algorithm. The maximum cardinality search chooses first time any |
157 /// node of the graph. Then every time chooses that node which connected |
157 /// node of the graph. Then every time it chooses the node which is connected |
158 /// to the processed nodes at most in the sum of capacities on the out |
158 /// to the processed nodes at most in the sum of capacities on the out |
159 /// edges. If there is a cut in the graph the algorithm should choose |
159 /// edges. If there is a cut in the graph the algorithm should choose |
160 /// again any unprocessed node of the graph. Each nodes cardinality is |
160 /// again any unprocessed node of the graph. Each node cardinality is |
161 /// the sum of capacities on the out edges to the nodes which are processed |
161 /// the sum of capacities on the out edges to the nodes which are processed |
162 /// before the given node. |
162 /// before the given node. |
163 /// |
163 /// |
164 /// The edge capacities are passed to the algorithm using a |
164 /// The edge capacities are passed to the algorithm using a |
165 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
165 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
1302 |
1302 |
1303 /// \brief Returns a minimum cut in a NodeMap. |
1303 /// \brief Returns a minimum cut in a NodeMap. |
1304 /// |
1304 /// |
1305 /// It sets the nodes of one of the two partitions to true in |
1305 /// It sets the nodes of one of the two partitions to true in |
1306 /// the given BoolNodeMap. The map contains a valid cut if the |
1306 /// the given BoolNodeMap. The map contains a valid cut if the |
1307 /// map have been setted false previously. |
1307 /// map have been set false previously. |
1308 template <typename NodeMap> |
1308 template <typename NodeMap> |
1309 Value quickMinCut(NodeMap& nodeMap) const { |
1309 Value quickMinCut(NodeMap& nodeMap) const { |
1310 for (typename Graph::Node it = _first_node; |
1310 for (typename Graph::Node it = _first_node; |
1311 it != _last_node; it = (*_next)[it]) { |
1311 it != _last_node; it = (*_next)[it]) { |
1312 nodeMap.set(it, true); |
1312 nodeMap.set(it, true); |
1329 return minCut(); |
1329 return minCut(); |
1330 } |
1330 } |
1331 |
1331 |
1332 /// \brief Returns a minimum cut in an EdgeMap. |
1332 /// \brief Returns a minimum cut in an EdgeMap. |
1333 /// |
1333 /// |
1334 /// If an undirected edge is cut edge then it will be |
1334 /// If an undirected edge is in a minimum cut then it will be |
1335 /// setted to true and the others will be setted to false in the given map. |
1335 /// set to true and the others will be set to false in the given map. |
1336 template <typename EdgeMap> |
1336 template <typename EdgeMap> |
1337 Value cutEdges(EdgeMap& edgeMap) const { |
1337 Value cutEdges(EdgeMap& edgeMap) const { |
1338 typename Graph::template NodeMap<bool> cut(*_graph, false); |
1338 typename Graph::template NodeMap<bool> cut(*_graph, false); |
1339 quickMinCut(cut); |
1339 quickMinCut(cut); |
1340 for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) { |
1340 for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) { |