38 |
38 |
39 namespace lemon { |
39 namespace lemon { |
40 |
40 |
41 /// \ingroup flowalgs |
41 /// \ingroup flowalgs |
42 /// |
42 /// |
43 /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs. |
43 /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs. |
44 /// |
44 /// |
45 /// Hao-Orlin calculates the minimum cut in directed graphs. It |
45 /// Hao-Orlin calculates a minimum cut in a directed graph \f$ |
46 /// separates the nodes of the graph into two disjoint sets, |
46 /// D=(V,A) \f$. It takes a fixed node \f$ source \in V \f$ and consists |
47 /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum |
47 /// of two phases: in the first phase it determines a minimum cut |
48 /// cut if the summary of the edge capacities which source is in |
48 /// with \f$ source \f$ on the source-side (i.e. a set \f$ X\subsetneq V |
49 /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the |
49 /// \f$ with \f$ source \in X \f$ and minimal out-degree) and in the |
50 /// minimum. The algorithm is a modified push-relabel preflow |
50 /// second phase it determines a minimum cut with \f$ source \f$ on the |
51 /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$ |
51 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ |
52 /// time. The purpose of such algorithm is testing network |
52 /// and minimal out-degree). Obviously, the smaller of these two |
53 /// reliability. For sparse undirected graph you can use the |
53 /// cuts will be a minimum cut of \f$ D \f$. The algorithm is a |
54 /// algorithm of Nagamochi and Ibaraki which solves the undirected |
54 /// modified push-relabel preflow algorithm and our implementation |
55 /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the |
55 /// calculates the minimum cut in \f$ O(n^3) \f$ time (we use the |
56 /// MinCut algorithm class. |
56 /// highest-label rule). The purpose of such an algorithm is testing |
|
57 /// network reliability. For an undirected graph with \f$ n \f$ |
|
58 /// nodes and \f$ e \f$ edges you can use the algorithm of Nagamochi |
|
59 /// and Ibaraki which solves the undirected problem in \f$ O(ne + |
|
60 /// n^2 \log(n)) \f$ time: it is implemented in the MinCut algorithm |
|
61 /// class. |
57 /// |
62 /// |
58 /// \param _Graph is the graph type of the algorithm. |
63 /// \param _Graph is the graph type of the algorithm. |
59 /// \param _CapacityMap is an edge map of capacities which should |
64 /// \param _CapacityMap is an edge map of capacities which should |
60 /// be any numreric type. The default type is _Graph::EdgeMap<int>. |
65 /// be any numreric type. The default type is _Graph::EdgeMap<int>. |
61 /// \param _Tolerance is the handler of the inexact computation. The |
66 /// \param _Tolerance is the handler of the inexact computation. The |
62 /// default type for it is Tolerance<typename CapacityMap::Value>. |
67 /// default type for this is Tolerance<typename CapacityMap::Value>. |
63 /// |
68 /// |
64 /// \author Attila Bernath and Balazs Dezso |
69 /// \author Attila Bernath and Balazs Dezso |
65 #ifdef DOXYGEN |
70 #ifdef DOXYGEN |
66 template <typename _Graph, typename _CapacityMap, typename _Tolerance> |
71 template <typename _Graph, typename _CapacityMap, typename _Tolerance> |
67 #else |
72 #else |
476 |
481 |
477 /// \brief Initializes the internal data structures. |
482 /// \brief Initializes the internal data structures. |
478 /// |
483 /// |
479 /// Initializes the internal data structures. It creates |
484 /// Initializes the internal data structures. It creates |
480 /// the maps, residual graph adaptor and some bucket structures |
485 /// the maps, residual graph adaptor and some bucket structures |
481 /// for the algorithm. The \c source node is used as the push-relabel |
486 /// for the algorithm. Node \c source is used as the push-relabel |
482 /// algorithm's source. |
487 /// algorithm's source. |
483 void init(const Node& source) { |
488 void init(const Node& source) { |
484 _source = source; |
489 _source = source; |
485 _node_num = countNodes(*_graph); |
490 _node_num = countNodes(*_graph); |
486 |
491 |
524 |
529 |
525 _min_cut = std::numeric_limits<Value>::max(); |
530 _min_cut = std::numeric_limits<Value>::max(); |
526 } |
531 } |
527 |
532 |
528 |
533 |
529 /// \brief Calculates the minimum cut with the \c source node |
534 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
530 /// in the \f$ V_{out} \f$. |
535 /// source-side. |
531 /// |
536 /// |
532 /// Calculates the minimum cut with the \c source node |
537 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
533 /// in the \f$ V_{out} \f$. |
538 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X |
|
539 /// \f$ and minimal out-degree). |
534 void calculateOut() { |
540 void calculateOut() { |
535 for (NodeIt it(*_graph); it != INVALID; ++it) { |
541 for (NodeIt it(*_graph); it != INVALID; ++it) { |
536 if (it != _source) { |
542 if (it != _source) { |
537 calculateOut(it); |
543 calculateOut(it); |
538 return; |
544 return; |
539 } |
545 } |
540 } |
546 } |
541 } |
547 } |
542 |
548 |
543 /// \brief Calculates the minimum cut with the \c source node |
549 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
544 /// in the \f$ V_{out} \f$. |
550 /// source-side. |
545 /// |
551 /// |
546 /// Calculates the minimum cut with the \c source node |
552 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
547 /// in the \f$ V_{out} \f$. The \c target is the initial target |
553 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X |
|
554 /// \f$ and minimal out-degree). The \c target is the initial target |
548 /// for the push-relabel algorithm. |
555 /// for the push-relabel algorithm. |
549 void calculateOut(const Node& target) { |
556 void calculateOut(const Node& target) { |
550 findMinCut(target, true, *_out_res_graph, *_out_current_edge); |
557 findMinCut(target, true, *_out_res_graph, *_out_current_edge); |
551 } |
558 } |
552 |
559 |
553 /// \brief Calculates the minimum cut with the \c source node |
560 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
554 /// in the \f$ V_{in} \f$. |
561 /// sink-side. |
555 /// |
562 /// |
556 /// Calculates the minimum cut with the \c source node |
563 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
557 /// in the \f$ V_{in} \f$. |
564 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X |
|
565 /// \f$ and minimal out-degree). |
558 void calculateIn() { |
566 void calculateIn() { |
559 for (NodeIt it(*_graph); it != INVALID; ++it) { |
567 for (NodeIt it(*_graph); it != INVALID; ++it) { |
560 if (it != _source) { |
568 if (it != _source) { |
561 calculateIn(it); |
569 calculateIn(it); |
562 return; |
570 return; |
563 } |
571 } |
564 } |
572 } |
565 } |
573 } |
566 |
574 |
567 /// \brief Calculates the minimum cut with the \c source node |
575 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
568 /// in the \f$ V_{in} \f$. |
576 /// sink-side. |
569 /// |
577 /// |
570 /// Calculates the minimum cut with the \c source node |
578 /// \brief Calculates a minimum cut with \f$ source \f$ on the |
571 /// in the \f$ V_{in} \f$. The \c target is the initial target |
579 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin |
572 /// for the push-relabel algorithm. |
580 /// X \f$ and minimal out-degree). The \c target is the initial |
|
581 /// target for the push-relabel algorithm. |
573 void calculateIn(const Node& target) { |
582 void calculateIn(const Node& target) { |
574 findMinCut(target, false, *_in_res_graph, *_in_current_edge); |
583 findMinCut(target, false, *_in_res_graph, *_in_current_edge); |
575 } |
584 } |
576 |
585 |
577 /// \brief Runs the algorithm. |
586 /// \brief Runs the algorithm. |
578 /// |
587 /// |
579 /// Runs the algorithm. It finds a proper \c source and \c target |
588 /// Runs the algorithm. It finds nodes \c source and \c target |
580 /// and then calls the \ref init(), \ref calculateOut() and \ref |
589 /// arbitrarily and then calls \ref init(), \ref calculateOut() |
581 /// calculateIn(). |
590 /// and \ref calculateIn(). |
582 void run() { |
591 void run() { |
583 init(); |
592 init(); |
584 for (NodeIt it(*_graph); it != INVALID; ++it) { |
593 for (NodeIt it(*_graph); it != INVALID; ++it) { |
585 if (it != _source) { |
594 if (it != _source) { |
586 calculateOut(it); |
595 calculateOut(it); |
631 Value minCut() const { |
641 Value minCut() const { |
632 return _min_cut; |
642 return _min_cut; |
633 } |
643 } |
634 |
644 |
635 |
645 |
636 /// \brief Returns a minimum value cut. |
646 /// \brief Returns a minimum cut. |
637 /// |
647 /// |
638 /// Sets \c nodeMap to the characteristic vector of a minimum |
648 /// Sets \c nodeMap to the characteristic vector of a minimum |
639 /// value cut. The nodes in \f$ V_{out} \f$ will be set true and |
649 /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$ |
640 /// the nodes in \f$ V_{in} \f$ will be set false. |
650 /// with minimal out-degree (i.e. \c nodeMap will be true exactly |
641 /// \pre nodeMap should be a bool-valued node-map. |
651 /// for the nodes of \f$ X \f$. \pre nodeMap should be a |
|
652 /// bool-valued node-map. |
642 template <typename NodeMap> |
653 template <typename NodeMap> |
643 Value minCut(NodeMap& nodeMap) const { |
654 Value minCut(NodeMap& nodeMap) const { |
644 for (NodeIt it(*_graph); it != INVALID; ++it) { |
655 for (NodeIt it(*_graph); it != INVALID; ++it) { |
645 nodeMap.set(it, (*_min_cut_map)[it]); |
656 nodeMap.set(it, (*_min_cut_map)[it]); |
646 } |
657 } |