61 /// \tparam CAP type of the EdgeMap describing the Edge capacities. |
61 /// \tparam CAP type of the EdgeMap describing the Edge capacities. |
62 /// it is typename GR::template EdgeMap<int> by default. |
62 /// it is typename GR::template EdgeMap<int> by default. |
63 template <typename GR, |
63 template <typename GR, |
64 typename CAP = typename GR::template EdgeMap<int> |
64 typename CAP = typename GR::template EdgeMap<int> |
65 > |
65 > |
66 class GomoryHuTree { |
66 class GomoryHu { |
67 public: |
67 public: |
68 |
68 |
69 /// The graph type |
69 /// The graph type |
70 typedef GR Graph; |
70 typedef GR Graph; |
71 /// The type if the edge capacity map |
71 /// The type if the edge capacity map |
114 /// \brief Constructor |
114 /// \brief Constructor |
115 /// |
115 /// |
116 /// Constructor |
116 /// Constructor |
117 /// \param graph The graph the algorithm will run on. |
117 /// \param graph The graph the algorithm will run on. |
118 /// \param capacity The capacity map. |
118 /// \param capacity The capacity map. |
119 GomoryHuTree(const Graph& graph, const Capacity& capacity) |
119 GomoryHu(const Graph& graph, const Capacity& capacity) |
120 : _graph(graph), _capacity(capacity), |
120 : _graph(graph), _capacity(capacity), |
121 _pred(0), _weight(0), _order(0) |
121 _pred(0), _weight(0), _order(0) |
122 { |
122 { |
123 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>(); |
123 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>(); |
124 } |
124 } |
125 |
125 |
126 |
126 |
127 /// \brief Destructor |
127 /// \brief Destructor |
128 /// |
128 /// |
129 /// Destructor |
129 /// Destructor |
130 ~GomoryHuTree() { |
130 ~GomoryHu() { |
131 destroyStructures(); |
131 destroyStructures(); |
132 } |
132 } |
133 |
133 |
134 // \brief Initialize the internal data structures. |
134 // \brief Initialize the internal data structures. |
135 // |
135 // |
338 friend class MinCutNodeIt; |
338 friend class MinCutNodeIt; |
339 |
339 |
340 /// Iterate on the nodes of a minimum cut |
340 /// Iterate on the nodes of a minimum cut |
341 |
341 |
342 /// This iterator class lists the nodes of a minimum cut found by |
342 /// This iterator class lists the nodes of a minimum cut found by |
343 /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class, |
343 /// GomoryHu. Before using it, you must allocate a GomoryHu class, |
344 /// and call its \ref GomoryHuTree::run() "run()" method. |
344 /// and call its \ref GomoryHu::run() "run()" method. |
345 /// |
345 /// |
346 /// This example counts the nodes in the minimum cut separating \c s from |
346 /// This example counts the nodes in the minimum cut separating \c s from |
347 /// \c t. |
347 /// \c t. |
348 /// \code |
348 /// \code |
349 /// GomoruHuTree<Graph> gom(g, capacities); |
349 /// GomoruHu<Graph> gom(g, capacities); |
350 /// gom.run(); |
350 /// gom.run(); |
351 /// int sum=0; |
351 /// int sum=0; |
352 /// for(GomoruHuTree<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; |
352 /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t);n!=INVALID;++n) ++sum; |
353 /// \endcode |
353 /// \endcode |
354 class MinCutNodeIt |
354 class MinCutNodeIt |
355 { |
355 { |
356 bool _side; |
356 bool _side; |
357 typename Graph::NodeIt _node_it; |
357 typename Graph::NodeIt _node_it; |
359 public: |
359 public: |
360 /// Constructor |
360 /// Constructor |
361 |
361 |
362 /// Constructor |
362 /// Constructor |
363 /// |
363 /// |
364 MinCutNodeIt(GomoryHuTree const &gomory, |
364 MinCutNodeIt(GomoryHu const &gomory, |
365 ///< The GomoryHuTree class. You must call its |
365 ///< The GomoryHu class. You must call its |
366 /// run() method |
366 /// run() method |
367 /// before initializing this iterator |
367 /// before initializing this iterator |
368 const Node& s, ///< Base node |
368 const Node& s, ///< Base node |
369 const Node& t, |
369 const Node& t, |
370 ///< The node you want to separate from Node s. |
370 ///< The node you want to separate from Node s. |
435 friend class MinCutEdgeIt; |
435 friend class MinCutEdgeIt; |
436 |
436 |
437 /// Iterate on the edges of a minimum cut |
437 /// Iterate on the edges of a minimum cut |
438 |
438 |
439 /// This iterator class lists the edges of a minimum cut found by |
439 /// This iterator class lists the edges of a minimum cut found by |
440 /// GomoryHuTree. Before using it, you must allocate a GomoryHuTree class, |
440 /// GomoryHu. Before using it, you must allocate a GomoryHu class, |
441 /// and call its \ref GomoryHuTree::run() "run()" method. |
441 /// and call its \ref GomoryHu::run() "run()" method. |
442 /// |
442 /// |
443 /// This example computes the value of the minimum cut separating \c s from |
443 /// This example computes the value of the minimum cut separating \c s from |
444 /// \c t. |
444 /// \c t. |
445 /// \code |
445 /// \code |
446 /// GomoruHuTree<Graph> gom(g, capacities); |
446 /// GomoruHu<Graph> gom(g, capacities); |
447 /// gom.run(); |
447 /// gom.run(); |
448 /// int value=0; |
448 /// int value=0; |
449 /// for(GomoruHuTree<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e) |
449 /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t);e!=INVALID;++e) |
450 /// value+=capacities[e]; |
450 /// value+=capacities[e]; |
451 /// \endcode |
451 /// \endcode |
452 /// the result will be the same as it is returned by |
452 /// the result will be the same as it is returned by |
453 /// \ref GomoryHuTree::minCostValue() "gom.minCostValue(s,t)" |
453 /// \ref GomoryHu::minCostValue() "gom.minCostValue(s,t)" |
454 class MinCutEdgeIt |
454 class MinCutEdgeIt |
455 { |
455 { |
456 bool _side; |
456 bool _side; |
457 const Graph &_graph; |
457 const Graph &_graph; |
458 typename Graph::NodeIt _node_it; |
458 typename Graph::NodeIt _node_it; |
468 _arc_it=typename Graph::OutArcIt(_graph,_node_it); |
468 _arc_it=typename Graph::OutArcIt(_graph,_node_it); |
469 } |
469 } |
470 } |
470 } |
471 |
471 |
472 public: |
472 public: |
473 MinCutEdgeIt(GomoryHuTree const &gomory, |
473 MinCutEdgeIt(GomoryHu const &gomory, |
474 ///< The GomoryHuTree class. You must call its |
474 ///< The GomoryHu class. You must call its |
475 /// run() method |
475 /// run() method |
476 /// before initializing this iterator |
476 /// before initializing this iterator |
477 const Node& s, ///< Base node |
477 const Node& s, ///< Base node |
478 const Node& t, |
478 const Node& t, |
479 ///< The node you want to separate from Node s. |
479 ///< The node you want to separate from Node s. |