Changeset 2228:f71b0f9a7c3a in lemon-0.x
- Timestamp:
- 10/02/06 16:41:53 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2968
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/hao_orlin.h
r2225 r2228 41 41 /// \ingroup flowalgs 42 42 /// 43 /// \brief %Hao-Orlin algorithm for calculateminimum 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 46 /// separates the nodes of the graph into two disjoint sets, 47 /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum 48 /// cut if the summary of the edge capacities which source is in 49 /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the 50 /// minimum. The algorithm is a modified push-relabel preflow 51 /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$ 52 /// time. The purpose of such algorithm is testing network 53 /// reliability. For sparse undirected graph you can use the 54 /// algorithm of Nagamochi and Ibaraki which solves the undirected 55 /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the 56 /// MinCut algorithm class. 45 /// Hao-Orlin calculates a minimum cut in a directed graph \f$ 46 /// D=(V,A) \f$. It takes a fixed node \f$ source \in V \f$ and consists 47 /// of two phases: in the first phase it determines a minimum cut 48 /// with \f$ source \f$ on the source-side (i.e. a set \f$ X\subsetneq V 49 /// \f$ with \f$ source \in X \f$ and minimal out-degree) and in the 50 /// second phase it determines a minimum cut with \f$ source \f$ on the 51 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ 52 /// and minimal out-degree). Obviously, the smaller of these two 53 /// cuts will be a minimum cut of \f$ D \f$. The algorithm is a 54 /// modified push-relabel preflow algorithm and our implementation 55 /// calculates the minimum cut in \f$ O(n^3) \f$ time (we use the 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 63 /// \param _Graph is the graph type of the algorithm. … … 60 65 /// be any numreric type. The default type is _Graph::EdgeMap<int>. 61 66 /// \param _Tolerance is the handler of the inexact computation. The 62 /// default type for itis Tolerance<typename CapacityMap::Value>.67 /// default type for this is Tolerance<typename CapacityMap::Value>. 63 68 /// 64 69 /// \author Attila Bernath and Balazs Dezso … … 479 484 /// Initializes the internal data structures. It creates 480 485 /// the maps, residual graph adaptor and some bucket structures 481 /// for the algorithm. The \c source nodeis used as the push-relabel486 /// for the algorithm. Node \c source is used as the push-relabel 482 487 /// algorithm's source. 483 488 void init(const Node& source) { … … 527 532 528 533 529 /// \brief Calculates the minimum cut with the \c source node 530 /// in the \f$ V_{out} \f$. 531 /// 532 /// Calculates the minimum cut with the \c source node 533 /// in the \f$ V_{out} \f$. 534 /// \brief Calculates a minimum cut with \f$ source \f$ on the 535 /// source-side. 536 /// 537 /// \brief Calculates a minimum cut with \f$ source \f$ on the 538 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X 539 /// \f$ and minimal out-degree). 534 540 void calculateOut() { 535 541 for (NodeIt it(*_graph); it != INVALID; ++it) { … … 541 547 } 542 548 543 /// \brief Calculates the minimum cut with the \c source node 544 /// in the \f$ V_{out} \f$. 545 /// 546 /// Calculates the minimum cut with the \c source node 547 /// in the \f$ V_{out} \f$. The \c target is the initial target 549 /// \brief Calculates a minimum cut with \f$ source \f$ on the 550 /// source-side. 551 /// 552 /// \brief Calculates a minimum cut with \f$ source \f$ on the 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 555 /// for the push-relabel algorithm. 549 556 void calculateOut(const Node& target) { … … 551 558 } 552 559 553 /// \brief Calculates the minimum cut with the \c source node 554 /// in the \f$ V_{in} \f$. 555 /// 556 /// Calculates the minimum cut with the \c source node 557 /// in the \f$ V_{in} \f$. 560 /// \brief Calculates a minimum cut with \f$ source \f$ on the 561 /// sink-side. 562 /// 563 /// \brief Calculates a minimum cut with \f$ source \f$ on the 564 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X 565 /// \f$ and minimal out-degree). 558 566 void calculateIn() { 559 567 for (NodeIt it(*_graph); it != INVALID; ++it) { … … 565 573 } 566 574 567 /// \brief Calculates the minimum cut with the \c source node 568 /// in the \f$ V_{in} \f$. 569 /// 570 /// Calculates the minimum cut with the \c source node 571 /// in the \f$ V_{in} \f$. The \c target is the initial target 572 /// for the push-relabel algorithm. 575 /// \brief Calculates a minimum cut with \f$ source \f$ on the 576 /// sink-side. 577 /// 578 /// \brief Calculates a minimum cut with \f$ source \f$ on the 579 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin 580 /// X \f$ and minimal out-degree). The \c target is the initial 581 /// target for the push-relabel algorithm. 573 582 void calculateIn(const Node& target) { 574 583 findMinCut(target, false, *_in_res_graph, *_in_current_edge); … … 577 586 /// \brief Runs the algorithm. 578 587 /// 579 /// Runs the algorithm. It finds a proper\c source and \c target580 /// a nd then calls the \ref init(), \ref calculateOut() and \ref581 /// calculateIn().588 /// Runs the algorithm. It finds nodes \c source and \c target 589 /// arbitrarily and then calls \ref init(), \ref calculateOut() 590 /// and \ref calculateIn(). 582 591 void run() { 583 592 init(); … … 593 602 /// \brief Runs the algorithm. 594 603 /// 595 /// Runs the algorithm. It finds a proper \c target and then calls 596 /// the \ref init(), \ref calculateOut() and \ref calculateIn(). 604 /// Runs the algorithm. It uses the given \c source node, finds a 605 /// proper \c target and then calls the \ref init(), \ref 606 /// calculateOut() and \ref calculateIn(). 597 607 void run(const Node& s) { 598 608 init(s); … … 634 644 635 645 636 /// \brief Returns a minimum valuecut.646 /// \brief Returns a minimum cut. 637 647 /// 638 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 640 /// the nodes in \f$ V_{in} \f$ will be set false. 641 /// \pre nodeMap should be a bool-valued node-map. 649 /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$ 650 /// with minimal out-degree (i.e. \c nodeMap will be true exactly 651 /// for the nodes of \f$ X \f$. \pre nodeMap should be a 652 /// bool-valued node-map. 642 653 template <typename NodeMap> 643 654 Value minCut(NodeMap& nodeMap) const {
Note: See TracChangeset
for help on using the changeset viewer.