Changeset 2273:507232469f5e in lemon0.x
 Timestamp:
 10/30/06 17:12:44 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3036
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/hao_orlin.h
r2228 r2273 43 43 /// \brief %HaoOrlin algorithm to find a minimum cut in directed graphs. 44 44 /// 45 /// HaoOrlin 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 consists45 /// HaoOrlin calculates a minimum cut in a directed graph 46 /// \f$ D=(V,A) \f$. It takes a fixed node \f$ source \in V \f$ and consists 47 47 /// of two phases: in the first phase it determines a minimum cut 48 /// with \f$ source \f$ on the sourceside (i.e. a set \f$ X\subsetneq V 49 /// \f$with \f$ source \in X \f$ and minimal outdegree) and in the48 /// with \f$ source \f$ on the sourceside (i.e. a set \f$ X\subsetneq V \f$ 49 /// with \f$ source \in X \f$ and minimal outdegree) and in the 50 50 /// second phase it determines a minimum cut with \f$ source \f$ on the 51 51 /// sinkside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ … … 57 57 /// network reliability. For an undirected graph with \f$ n \f$ 58 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 59 /// and Ibaraki which solves the undirected problem in 60 /// \f$ O(ne + n^2 \log(n)) \f$ time: it is implemented in the MinCut 61 /// algorithm 61 62 /// class. 62 63 /// … … 536 537 /// 537 538 /// \brief Calculates a minimum cut with \f$ source \f$ on the 538 /// sourceside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X 539 /// \f$and minimal outdegree).539 /// sourceside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X \f$ 540 /// and minimal outdegree). 540 541 void calculateOut() { 541 542 for (NodeIt it(*_graph); it != INVALID; ++it) { … … 551 552 /// 552 553 /// \brief Calculates a minimum cut with \f$ source \f$ on the 553 /// sourceside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X 554 /// \f$and minimal outdegree). The \c target is the initial target554 /// sourceside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \in X \f$ 555 /// and minimal outdegree). The \c target is the initial target 555 556 /// for the pushrelabel algorithm. 556 557 void calculateOut(const Node& target) { … … 562 563 /// 563 564 /// \brief Calculates a minimum cut with \f$ source \f$ on the 564 /// sinkside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin X 565 /// \f$ and minimal outdegree). 565 /// sinkside (i.e. a set \f$ X\subsetneq V \f$ with 566 /// \f$ source \notin X \f$ 567 /// and minimal outdegree). 566 568 void calculateIn() { 567 569 for (NodeIt it(*_graph); it != INVALID; ++it) { … … 577 579 /// 578 580 /// \brief Calculates a minimum cut with \f$ source \f$ on the 579 /// sinkside (i.e. a set \f$ X\subsetneq V \f$ with \f$ source \notin 580 /// X \f$ and minimal outdegree). The \c target is the initial 581 /// sinkside (i.e. a set \f$ X\subsetneq V 582 /// \f$ with \f$ source \notin X \f$ and minimal outdegree). 583 /// The \c target is the initial 581 584 /// target for the pushrelabel algorithm. 582 585 void calculateIn(const Node& target) {
Note: See TracChangeset
for help on using the changeset viewer.