1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2010 |
5 * Copyright (C) 2003-2013 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
252 inline int countNodes(const Graph& g) { |
252 inline int countNodes(const Graph& g) { |
253 return _core_bits::CountNodesSelector<Graph>::count(g); |
253 return _core_bits::CountNodesSelector<Graph>::count(g); |
254 } |
254 } |
255 |
255 |
256 namespace _graph_utils_bits { |
256 namespace _graph_utils_bits { |
257 |
257 |
258 template <typename Graph, typename Enable = void> |
258 template <typename Graph, typename Enable = void> |
259 struct CountRedNodesSelector { |
259 struct CountRedNodesSelector { |
260 static int count(const Graph &g) { |
260 static int count(const Graph &g) { |
261 return countItems<Graph, typename Graph::RedNode>(g); |
261 return countItems<Graph, typename Graph::RedNode>(g); |
262 } |
262 } |
263 }; |
263 }; |
264 |
264 |
265 template <typename Graph> |
265 template <typename Graph> |
266 struct CountRedNodesSelector< |
266 struct CountRedNodesSelector< |
267 Graph, typename |
267 Graph, typename |
268 enable_if<typename Graph::NodeNumTag, void>::type> |
268 enable_if<typename Graph::NodeNumTag, void>::type> |
269 { |
269 { |
270 static int count(const Graph &g) { |
270 static int count(const Graph &g) { |
271 return g.redNum(); |
271 return g.redNum(); |
272 } |
272 } |
273 }; |
273 }; |
274 } |
274 } |
275 |
275 |
276 /// \brief Function to count the red nodes in the graph. |
276 /// \brief Function to count the red nodes in the graph. |
277 /// |
277 /// |
278 /// This function counts the red nodes in the graph. |
278 /// This function counts the red nodes in the graph. |
279 /// The complexity of the function is O(n) but for some |
279 /// The complexity of the function is O(n) but for some |
280 /// graph structures it is specialized to run in O(1). |
280 /// graph structures it is specialized to run in O(1). |
281 /// |
281 /// |
282 /// If the graph contains a \e redNum() member function and a |
282 /// If the graph contains a \e redNum() member function and a |
283 /// \e NodeNumTag tag then this function calls directly the member |
283 /// \e NodeNumTag tag then this function calls directly the member |
284 /// function to query the cardinality of the node set. |
284 /// function to query the cardinality of the node set. |
285 template <typename Graph> |
285 template <typename Graph> |
286 inline int countRedNodes(const Graph& g) { |
286 inline int countRedNodes(const Graph& g) { |
287 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g); |
287 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g); |
288 } |
288 } |
289 |
289 |
290 namespace _graph_utils_bits { |
290 namespace _graph_utils_bits { |
291 |
291 |
292 template <typename Graph, typename Enable = void> |
292 template <typename Graph, typename Enable = void> |
293 struct CountBlueNodesSelector { |
293 struct CountBlueNodesSelector { |
294 static int count(const Graph &g) { |
294 static int count(const Graph &g) { |
295 return countItems<Graph, typename Graph::BlueNode>(g); |
295 return countItems<Graph, typename Graph::BlueNode>(g); |
296 } |
296 } |
297 }; |
297 }; |
298 |
298 |
299 template <typename Graph> |
299 template <typename Graph> |
300 struct CountBlueNodesSelector< |
300 struct CountBlueNodesSelector< |
301 Graph, typename |
301 Graph, typename |
302 enable_if<typename Graph::NodeNumTag, void>::type> |
302 enable_if<typename Graph::NodeNumTag, void>::type> |
303 { |
303 { |
304 static int count(const Graph &g) { |
304 static int count(const Graph &g) { |
305 return g.blueNum(); |
305 return g.blueNum(); |
306 } |
306 } |
307 }; |
307 }; |
308 } |
308 } |
309 |
309 |
310 /// \brief Function to count the blue nodes in the graph. |
310 /// \brief Function to count the blue nodes in the graph. |
311 /// |
311 /// |
312 /// This function counts the blue nodes in the graph. |
312 /// This function counts the blue nodes in the graph. |
313 /// The complexity of the function is O(n) but for some |
313 /// The complexity of the function is O(n) but for some |
314 /// graph structures it is specialized to run in O(1). |
314 /// graph structures it is specialized to run in O(1). |
315 /// |
315 /// |
316 /// If the graph contains a \e blueNum() member function and a |
316 /// If the graph contains a \e blueNum() member function and a |
317 /// \e NodeNumTag tag then this function calls directly the member |
317 /// \e NodeNumTag tag then this function calls directly the member |
318 /// function to query the cardinality of the node set. |
318 /// function to query the cardinality of the node set. |
319 template <typename Graph> |
319 template <typename Graph> |
320 inline int countBlueNodes(const Graph& g) { |
320 inline int countBlueNodes(const Graph& g) { |
321 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g); |
321 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g); |