include/GTL/ratio_cut_partition.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //  ratio_cut_partition.h
0005 //
0006 //==========================================================================
0007 // $Id: ratio_cut_partition.h,v 1.8 2003/01/31 08:15:04 chris Exp $
0008
0009 #ifndef GTL_RATIO_CUT_PARTITION_H
0010 #define GTL_RATIO_CUT_PARTITION_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/graph.h>
0014 #include <GTL/node_map.h>
0015 #include <GTL/edge_map.h>
0016 #include <GTL/algorithm.h>
0017
0018 __GTL_BEGIN_NAMESPACE
0019
0020
0021 /**
0022  * @short Heuristic graph bi-partitioning algorithm (Wei-Cheng).
0023  *
0024  * This class implements a heuristic graph bi-partitioning algorithm using
0025  * the ratio cut method proposed by Y. C. Wei and C. K. Cheng in 1991.
0026  *
0027  * <p> In the case E is the set of edges of the graph, the algorithm needs
0028  * <code>O(|E|)</code> time to proceed.
0029  *
0030  * @see fm_partition
0031  */
0032 class GTL_EXTERN ratio_cut_partition : public algorithm
0033 {
0034 public:
0035     /**
0036      * Return type of @ref ratio_cut_partition#get_side_of_node.
0037      *
0038      * @see ratio_cut_partition#A
0039      * @see ratio_cut_partition#B
0040      */
0041     typedef int side_type;
0042
0043     /**
0044      * <code>A</code> means the node is on side A.
0045      *
0046      * @see ratio_cut_partition#side_type
0047      */
0048     const static side_type A;
0049
0050     /**
0051      * <code>B</code> means the node is on side B.
0052      *
0053      * @see ratio_cut_partition#side_type
0054      */
0055     const static side_type B;
0056
0057     /**
0058      * Fix type of each node (needed with
0059      * @ref ratio_cut_partition#set_vars).
0060      *
0061      * @see ratio_cut_partition#FIXA
0062      * @see ratio_cut_partition#FIXB
0063      * @see ratio_cut_partition#UNFIXED
0064      */
0065     typedef short int fix_type;
0066
0067     /**
0068      * <code>FIXA</code> means fix node on side <code>A</code>.
0069      *
0070      * @see ratio_cut_partition#set_vars
0071      */
0072     const static fix_type FIXA;
0073
0074     /**
0075      * <code>FIXB</code> means fix node on side <code>B</code>.
0076      *
0077      * @see ratio_cut_partition#fixe_type
0078      */
0079     const static fix_type FIXB;
0080
0081     /**
0082      * <code>UNFIXED</code> means node is free.
0083      *
0084      * @see ratio_cut_partition#fixe_type
0085      */
0086     const static fix_type UNFIXED;
0087
0088     /**
0089      * Default constructor.
0090      *
0091      * @see algorithm#algorithm
0092      */
0093     ratio_cut_partition();
0094
0095     /**
0096      * Destructor.
0097      *
0098      * @see algorithm#~algorithm
0099      */
0100     virtual ~ratio_cut_partition();
0101
0102     /**
0103      * Sets variables.
0104      * Must be executed before @ref ratio_cut_partition#check!
0105      * <code>source_node</code> and <code>target_node</code> will be
0106      * determined automatically.
0107      *
0108      * @param G undirected graph
0109      * @param node_weight weight of each node
0110      * @param edge_weight weight of each edge.
0111      * @see ratio_cut_partition#check
0112      */
0113     void set_vars(const graph& G, const node_map<int>& node_weight,
0114     const edge_map<int>& edge_weight);
0115
0116     /**
0117      * Sets variables.
0118      * Must be executed before @ref ratio_cut_partition#check!
0119      * In order to get good results, you should take two graph
0120      * theoretically far away nodes as source and target.
0121      *
0122      * @param G undirected graph
0123      * @param node_weight weight of each node
0124      * @param edge_weight weight of each edge
0125      * @param source_node start-node, remains on side <code>A</code>
0126      * @param target_node end-node, remains on side <code>B</code>
0127      * @see ratio_cut_partition#check
0128      */
0129     void set_vars(const graph& G, const node_map<int>& node_weight,
0130     const edge_map<int>& edge_weight, const node source_node,
0131     const node target_node);
0132
0133     /**
0134      * Sets variables.
0135      * Must be executed before @ref ratio_cut_partition#check!
0136      * In order to get good results, you should take two graph
0137      * theoretically far away nodes as source and target. Additionally
0138      * <code>init_side</code> should nearly be in balance.
0139      * <code>source_node</code> must be on side <code>A</code> in <code>
0140      * init_side</code> and <code>target_node</code> on side <code>B
0141      * </code> respectively.
0142      *
0143      * @param G undirected graph
0144      * @param node_weight weight of each node
0145      * @param edge_weight weight of each edge
0146      * @param source_node start-node, remains on side <code>A</code>
0147      * @param target_node end-node, remains on side <code>B</code>
0148      * @param init_side initial bi-partitioning
0149      * @see ratio_cut_partition#check
0150      */
0151     void set_vars(const graph& G, const node_map<int>& node_weight,
0152     const edge_map<int>& edge_weight, const node source_node,
0153     const node target_node, const node_map<side_type>& init_side);
0154
0155     /**
0156      * Sets variables.
0157      * Must be executed before @ref ratio_cut_partition#check!
0158      * In order to get good results, you should take two graph
0159      * theoretically far away nodes as source and target.
0160      * <code>source_node</code> must not be fixed on side <code>B
0161      * </code>.
0162      * <code>target_node</code> must not be fixed on side <code>A
0163      * </code>.
0164      *
0165      * @param G undirected graph
0166      * @param node_weight weight of each node
0167      * @param edge_weight weight of each edge
0168      * @param source_node start-node, remains on side <code>A</code>
0169      * @param target_node end-node, remains on side <code>B</code>
0170      * @param fixed fixed nodes
0171      * @see ratio_cut_partition#check
0172      */
0173     void set_vars(const graph& G, const node_map<int>& node_weight,
0174     const edge_map<int>& edge_weight, const node source_node,
0175     const node target_node, const node_map<fix_type>& fixed);
0176
0177     /**
0178      * Sets variables.
0179      * Must be executed before @ref ratio_cut_partition#check!
0180      * In order to get good results, you should take two graph
0181      * theoretically far away nodes as source and target. Additionally
0182      * <code>init_side</code> should nearly be in balance. Fixed nodes
0183      * are on their fix side, their initial side is overwritten then.
0184      * <code>source_node</code> must be on side A in <code>init_side
0185      * </code> and <code>target_node</code> on side B respectively.
0186      * <code>source_node</code> must not be fixed on side <code>B
0187      * </code>.
0188      * <code>target_node</code> must not be fixed on side <code>A
0189      * </code>.
0190      *
0191      * @param G undirected graph
0192      * @param node_weight weight of each node
0193      * @param edge_weight weight of each edge
0194      * @param source_node start-node, remains on side <code>A</code>
0195      * @param target_node end-node, remains on side <code>B</code>
0196      * @param init_side initial bi-partitioning
0197      * @param fixed fixed nodes
0198      * @see ratio_cut_partition#check
0199      */
0200     void set_vars(const graph& G, const node_map<int>& node_weight,
0201     const edge_map<int>& edge_weight, const node source_node,
0202     const node target_node, const node_map<side_type>& init_side,
0203     const node_map<fix_type>& fixed);
0204
0205     /**
0206      * Enables the storing of cut-edges. If enabled the list of
0207      * cut-edges can be traversed using @ref
0208      * ratio_cut_partition#cut_edges_iterator.
0209      *
0210      * @param set if <code>true</code> cut_edges will be stored
0211      * @see ratio_cut_partition#cut_edges_begin
0212      * @see ratio_cut_partition#cut_edges_end
0213      */
0214     void store_cut_edges(const bool set);
0215
0216     /**
0217      * Enables the storing of nodes on their side. If enabled the nodes
0218      * of each side can be traversed using
0219      * ratio_cut_partition#nodes_of_one_side_iterator.
0220      *
0221      * @param set if <code>true</code> nodes on their side will be stored
0222      * @see ratio_cut_partition#nodes_of_sideA_begin
0223      * @see ratio_cut_partition#nodes_of_sideA_end
0224      * @see ratio_cut_partition#nodes_of_sideB_begin
0225      * @see ratio_cut_partition#nodes_of_sideB_end
0226      */
0227     void store_nodesAB(const bool set);
0228
0229     /**
0230      * Checks whether following preconditions are satisfied:
0231      * <ul>
0232      * <li> One of the @ref ratio_cut_partition#set_vars procedures has
0233      * been executed before.
0234      * <li> graph <code>G</code> is undirected.
0235      * <li> if applied, <code>source_node</code> and <code>target_node
0236      * </code> are 2 distinct nodes with node weights > 0.
0237      * <li> only node_weights >= 0 are applied.
0238      * <li> only edge_weights >= 0 are applied.
0239      * <li> if <code>G</code> has more than 2 nodes, then at least
0240      * two of them have a weight > 0.
0241      * <li> if applied fixed source node, <code>fixed[source_node]
0242      * </code> is <code>FIXA</code>.
0243      * <li> if applied fixed target node, <code>fixed[target_node]
0244      * </code> is <code>FIXB</code>.
0245      * </ul>
0246      *
0247      * @param G graph
0248      * @return <code>algorithm::GTL_OK</code> on success,
0249      * <code>algorithm::GTL_ERROR</code> otherwise
0250      * @see ratio_cut_partition#set_vars
0251      * @see algorithm#check
0252      */
0253     virtual int check(graph& G);
0254
0255     /**
0256      * Computes a partitioning of <code>G</code>, that means a division
0257      * of its vertices in two sides <code>ratio_cut_partition::A</code>
0258      * and <code>ratio_cut_partition::B</code>.
0259      *
0260      * @param G graph
0261      * @return <code>algorithm::GTL_OK</code> on success,
0262      * <code>algorithm::GTL_ERROR</code> otherwise
0263      * @see algorithm#run
0264      */
0265     int run(graph& G);
0266
0267     /**
0268      * Gets the size of the cut after bi-partitioning.
0269      *
0270      * @return cutsize
0271      */
0272     int get_cutsize();
0273
0274     /**
0275      * Gets the ratio of the cut after bi-partitioning as defined in
0276      * [WeiChe91].
0277      *
0278      * @return cutratio
0279      */
0280     double get_cutratio();
0281
0282     /**
0283      * Gets side of the node after bi-partitioning.
0284      *
0285      * @param n node of graph G
0286      * @return <code>ratio_cut_partition::A</code> if <code>n</code>
0287      * lies on side <code>A</code>, <code>ratio_cut_partition::B</code>
0288      * otherwise
0289      */
0290     side_type get_side_of_node(const node& n) const;
0291
0292     /**
0293      * Gets side of the node after bi-partitioning.
0294      *
0295      * @param n node of graph G
0296      * @return <code>ratio_cut_partition::A</code> if <code>n</code>
0297      * lies on side <code>A</code>, <code>ratio_cut_partition::B</code>
0298      * otherwise
0299      * @see ratio_cut_partition#get_side_of_node
0300      */
0301     side_type operator [](const node& n) const;
0302
0303     /**
0304      * Gets the sum of all node weights from nodes on side <code>A
0305      * </code>.
0306      *
0307      * @param G graph
0308      * @return <code>node_weight_on_sideA</code>
0309      */
0310     int get_weight_on_sideA(const graph& G) const;
0311
0312     /**
0313      * Gets the sum of all node weights from nodes on side <code>B
0314      * </code>.
0315      *
0316      * @param G graph
0317      * @return <code>node_weight_on_sideB</code>
0318      */
0319     int get_weight_on_sideB(const graph& G) const;
0320
0321     /**
0322      * Iterator type for edges which belong to the cut.
0323      */
0324     typedef list<edge>::const_iterator cut_edges_iterator;
0325
0326     /**
0327      * Iterate through all edges which belong to the cut, that means
0328      * all edges with end-nodes on different sides.
0329      * It is only valid if enabled with @ref
0330      * ratio_cut_partition#store_cut_edges before.
0331      *
0332      * @return start for iteration through all cut edges
0333      */
0334     cut_edges_iterator cut_edges_begin() const;
0335
0336     /**
0337      * End-Iterator for iteration through all edges which belong to the
0338      * cut.
0339      * It is only valid if enabled with @ref
0340      * ratio_cut_partition#store_cut_edges before.
0341      *
0342      * @return end for iteration through all cut-edges
0343      */
0344     cut_edges_iterator cut_edges_end() const;
0345
0346     /**
0347      * Iterator type for nodes of a side.
0348      */
0349     typedef list<node>::const_iterator nodes_of_one_side_iterator;
0350
0351     /**
0352      * Iterate through all nodes which belong to side <code>A</code>,
0353      * It is only valid if enabled with @ref
0354      * ratio_cut_partition#store_nodesAB before.
0355      *
0356      * @return start for iteration through all nodes on <code>A</code>
0357      */
0358     nodes_of_one_side_iterator nodes_of_sideA_begin() const;
0359
0360     /**
0361      * End-Iterator for iteration through all nodes which belong to side
0362      * <code>A</code>,
0363      * It is only valid if enabled with @ref
0364      * ratio_cut_partition#store_nodesAB before.
0365      *
0366      * @return end for iteration through all nodes on <code>A</code>
0367      */
0368     nodes_of_one_side_iterator nodes_of_sideA_end() const;
0369
0370     /**
0371      * Iterate through all nodes which belong to side <code>B</code>,
0372      * It is only valid if enabled with @ref
0373      * ratio_cut_partition#store_nodesAB before.
0374      *
0375      * @return start for iteration through all nodes on <code>B</code>
0376      */
0377     nodes_of_one_side_iterator nodes_of_sideB_begin() const;
0378
0379     /**
0380      * End-Iterator for iteration through all nodes which belong to side
0381      * <code>B</code>,
0382      * It is only valid if enabled with @ref
0383      * ratio_cut_partition#store_nodesAB before.
0384      *
0385      * @return end for iteration through all nodes on <code>B</code>
0386      */
0387     nodes_of_one_side_iterator nodes_of_sideB_end() const;
0388
0389     /**
0390      * Resets ratio_cut_partition, i.e. prepares the algorithm to be
0391      * applied to another graph.
0392      *
0393      * @see algorithm#reset
0394      */
0395     virtual void reset();
0396 protected:
0397     /**
0398      * @internal
0399      */
0400     enum direction_type {LEFT_SHIFT = 2, RIGHT_SHIFT = 3};
0401
0402     /**
0403      * @internal
0404      * <code>true</code>, iff user enabled storing of cut-edges with
0405      * @ref ratio_cut_partition#store_cut_edges.
0406      */
0407     bool enable_cut_edges_storing;
0408
0409     /**
0410      * @internal
0411      * List of edges which belong to the cut.
0412      */
0413     list<edge> cut_edges;
0414
0415     /**
0416      * @internal
0417      * <code>true</code>, iff user enabled storing of nodes with @ref
0418      * ratio_cut_partition#store_nodesAB.
0419      */
0420     bool enable_nodesAB_storing;
0421
0422     /**
0423      * @internal
0424      * List of nodes which belong to side <code>A</code>.
0425      */
0426     list<node> nodesA;
0427
0428     /**
0429      * @internal
0430      * List of nodes which belong to side <code>A</code>.
0431      */
0432     list<node> nodesB;
0433
0434     /**
0435      * @internal
0436      * Corresponds to s in [WeiChe91].
0437      */
0438     node source_node;
0439
0440     /**
0441      * @internal
0442      * Corresponds to t in [WeiChe91].
0443      */
0444     node target_node;
0445
0446     /**
0447      * @internal
0448      * <code>true</code>, iff user has executed @ref
0449      * ratio_cut_partition#set_vars before @ref ratio_cut_partition#
0450      * check and @ref ratio_cut_partition#run.
0451      */
0452     bool set_vars_executed;
0453
0454     /**
0455      * @internal
0456      * <code>true</code>, iff user has provided <code>source_node</code>
0457      * and <code>target_node</code>, <code>false</code> else.
0458      */
0459     bool provided_st;
0460
0461     /**
0462      * @internal
0463      * <code>true</code>, iff user has provided <code>init_side</code>
0464      * with @ref ratio_cut_partition#set_vars, <code>false</code>
0465      * otherwise.
0466      */
0467     bool provided_initial_part;
0468
0469     /**
0470      * @internal
0471      * <code>true</code>, iff user has provided <code>fixed</code> with
0472      * @ref ratio_cut_partition#set_vars, <code>false</code> otherwise.
0473      */
0474     bool provided_fix;
0475
0476     /**
0477      * @internal
0478      * Contains information where a node is fixed.
0479      */
0480     node_map<fix_type> fixed;
0481
0482     /**
0483      * @internal
0484      * <code>LEFT</code> if @ref ratio_cut_partition#left_shift_op has
0485      * computed last cut, <code>RIGHT</code> else.
0486      */
0487     direction_type direction;
0488
0489     /**
0490      * @internal
0491      * Contains the weight of each node.
0492      * Corresponds to w(v) in [Leng90].
0493      */
0494     node_map<int> node_weight;
0495
0496     /**
0497      * @internal
0498      * Contains the weight of each edge.
0499      * Corresponds to c(e) in [Leng90].
0500      */
0501     edge_map<int> edge_weight;
0502
0503     /**
0504      * @internal
0505      * Contains the maximum weight of an edge in <code>G</code>.
0506      * (maximum of <code>edge_weight[...]</code>)
0507      */
0508     int max_edge_weight;
0509
0510     /**
0511      * @internal
0512      * Contains the sum over all vertex weights on side <code>A</code>.
0513      * Corresponds to w(A) in [Leng90].
0514      */
0515     int node_weight_on_sideA;
0516
0517     /**
0518      * @internal
0519      * Contains the sum over all vertex weights on side <code>B</code>.
0520      * Corresponds to w(B) in [Leng90].
0521      */
0522     int node_weight_on_sideB;
0523
0524     /**
0525      * @internal
0526      * Counts nodes on side <code>A</code>.
0527      */
0528     int nodes_on_sideA;
0529
0530     /**
0531      * @internal
0532      * Counts nodes on side <code>B</code>.
0533      */
0534     int nodes_on_sideB;
0535
0536     /**
0537      * @internal
0538      * Contains information about the current side of a node.
0539      */
0540     node_map<side_type> side;
0541
0542     /**
0543      * @internal
0544      * Corresponds to CELL array in [FidMat82]
0545      */
0546     node_map<list<node>::iterator> position_in_bucket;
0547
0548     /**
0549      * @internal
0550      * Contains the maximal number of adjacent to a node.
0551      */
0552     int max_vertex_degree;
0553
0554     /**
0555      * @internal
0556      * Contains how many nodes an edge has on side <code>A</code>.
0557      */
0558     edge_map<int> aside;
0559
0560     /**
0561      * @internal
0562      * Contains how many nodes an edge has on side <code>B</code>.
0563      */
0564     edge_map<int> bside;
0565
0566     /**
0567      * @internal
0568      * Contains the unlocked nodes of an edge on side <code>A</code>.
0569      * (max. 2)
0570      */
0571     edge_map<list<node> > unlockedA;
0572
0573     /**
0574      * @internal
0575      * Contains the unlocked nodes of an edge on side <code>B</code>.
0576      * (max. 2)
0577      */
0578     edge_map<list<node> > unlockedB;
0579
0580     /**
0581      * @internal
0582      * Corresponds to D value in Leng[90].
0583      */
0584     node_map<int> gain_value;
0585
0586     /**
0587      * @internal
0588      * <code>true</code>, iff <code>bucketA</code> is empty.
0589      */
0590     bool bucketA_empty;
0591
0592     /**
0593      * @internal
0594      * <code>true</code>, iff <code>bucketB</code> is empty.
0595      */
0596     bool bucketB_empty;
0597
0598     /**
0599      * @internal
0600      * Contains the maximum gain value of a node in
0601      * <code>bucketA</code>.
0602      */
0603     int max_gainA;
0604
0605     /**
0606      * @internal
0607      * Contains the maximum gain value of a node in
0608      * <code>bucketB</code>.
0609      */
0610     int max_gainB;
0611
0612     /**
0613      * @internal
0614      * Like a hash table over the <code>gain_value</code> of each node
0615      * on side <code>A</code>. (open hashing, collisions in gain buckets
0616      * are organized through LIFO lists)
0617      */
0618     vector<list<node> > bucketA;
0619
0620     /**
0621      * @internal
0622      * Like a hash table over the <code>gain_value</code> of each node
0623      * on side <code>B</code>. (open hashing, collisions in gain buckets
0624      * are organized through LIFO lists)
0625      */
0626     vector<list<node> > bucketB;
0627
0628     /**
0629      * @internal
0630      * Sum over all <code>edge_costs[e]</code> where edge e is an
0631      * element of the cut.
0632      */
0633     int cur_cutsize;
0634
0635     /**
0636      * @internal
0637      * Cut ratio as defined in [WeiChe91].
0638      */
0639     double cur_cutratio;
0640
0641     /**
0642      * @internal
0643      * Fix <code>FIXA</code> nodes on side <code>A</code> and <code>FIXB
0644      * </code> nodes on side <code>B</code>.
0645      */
0646     void divide_up(const graph& G);
0647
0648     /**
0649      * @internal
0650      * Makes <code>G</code> connected for the run of this algorithm.
0651      * This is done by introducing edges with weight 0 since Ratio Cut
0652      * works well on connected graphs only.
0653      */
0654     void make_connected(graph& G, list<edge>& artificial_edges);
0655
0656     /**
0657      * @internal
0658      * Deletes the edges introduced in @ref ratio_cut_partition#
0659      * make_connected.
0660      */
0661     void restore(graph& G, list<edge>& artificial_edges);
0662
0663     /**
0664      * @internal
0665      * Corresponds to phase 1 in [WeiChe91].
0666      */
0667     void initialization(const graph& G);
0668
0669     /**
0670      * @internal
0671      * Initialization of the data structure for each step.
0672      */
0673     void init_data_structure(const graph& G);
0674
0675     /**
0676      * @internal
0677      * Computes initial gain_value for each node and inserts it in the
0678      * corresponding bucket data structure.
0679      */
0680     void init_filling_buckets(const graph& G);
0681
0682     /**
0683      * @internal
0684      * Compute initial gain of a node on side <code>A</code>.
0685      * @return initial gain_value of a node on side <code>A</code>
0686      */
0687     int inital_gain_of_node_on_sideA(const node cur_node);
0688
0689     /**
0690      * @internal
0691      * Compute initial gain of a node on side <code>B</code>.
0692      * @return initial gain_value of a node on side <code>B</code>
0693      */
0694     int inital_gain_of_node_on_sideB(const node cur_node);
0695
0696     /**
0697      * @internal
0698      * Computes some maximum variables.
0699      */
0700     void init_variables(const graph& G);
0701
0702     /**
0703      * @internal
0704      * Computes <code>max_vertex_degree</code>.
0705      */
0706     void compute_max_vertex_degree(const graph& G);
0707
0708     /**
0709      * @internal
0710      * Compute source seed [WeiChe91].
0711      */
0712     void determine_source_node(const graph& G);
0713
0714     /**
0715      * @internal
0716      * Compute target seed [WeiChe91].
0717      */
0718     void compute_target_node(const graph& G);
0719
0720     /**
0721      * @internal
0722      * Corresponds to right shifting operation as defined in [WeiChe91].
0723      * Moves nodes from side <code>A</code> to <code>B</code>.
0724      */
0725     void right_shift_op(const graph& G);
0726
0727     /**
0728      * @internal
0729      * Corresponds to left shifting operation as defined in [WeiChe91].
0730      * Moves nodes from side <code>B</code> to <code>A</code>.
0731      */
0732     void left_shift_op(const graph& G);
0733
0734     /**
0735      * @internal
0736      * Moves <code>max_gain</code> node from side <code>A</code> to
0737      * <code>B</code>.
0738      * @return <code>true</code> if vertex stored in parameter <code>
0739      * moved_node</code> has been found
0740      */
0741     bool move_vertex_A2B(const graph& G, node& moved_node);
0742
0743     /**
0744      * @internal
0745      * Moves <code>max_gain node</code> from side B to A.
0746      * @return <code>true</code> if vertex stored in parameter <code>
0747      * moved_node</code> has been found
0748      */
0749     bool move_vertex_B2A(const graph& G, node& moved_node);
0750
0751     /**
0752      * @internal
0753      * Selects node with highest ratio_gain
0754      */
0755     node compute_highest_ratio_node(list<node> node_list);
0756
0757     /**
0758      * @internal
0759      * Computes <code>cut_ratio</code>.
0760      * @return <code>cut_ratio</code> with cutsize <code>cur_cutsize
0761      * </code> and current side weights <code>node_weight_on_sideA
0762      * </code> and <code>node_weight_on_sideB</code>
0763      */
0764     double cutratio();
0765
0766     /**
0767      * @internal
0768      * Corresponds to r(i) in [WeiChe91].
0769      * @return ratio gain of a node <code>cur_node</code> on side <code>
0770      * A</code>
0771      */
0772     double ratio_of_node_A2B(const node cur_node);
0773
0774     /**
0775      * @internal
0776      * Corresponds to r(i) in [WeiChe91].
0777      * @return ratio gain of a node <code>cur_node</code> on side <code>
0778      * B</code>
0779      */
0780     double ratio_of_node_B2A(const node cur_node);
0781
0782     /**
0783      * @internal
0784      * Transform a range from [-a..+a] to [0..2a].
0785      * (reverse to @ref ratio_cut_partition#range_up)
0786      */
0787     inline int range_up(const int gain_value) const;
0788
0789     /**
0790      * @internal
0791      * Transform a range from [0..2a] to [-a..+a].
0792      * (reverse to @ref ratio_cut_partition#range_down)
0793      */
0794     inline int range_down(const int index) const;
0795
0796     /**
0797      * @internal
0798      * Executed, if <code>cur_node</code> is chosen to move from side
0799      * <code>A</code> to <code>B</code>.
0800      */
0801     void update_data_structure_A2B(const node cur_node,
0802     const bool init_mode);
0803
0804     /**
0805      * @internal
0806      * Executed, if <code>cur_node</code> is chosen to move from side
0807      * <code>B</code> to <code>A</code>.
0808      */
0809     void update_data_structure_B2A(const node cur_node,
0810     const bool init_mode);
0811
0812     /**
0813      * @internal
0814      * Reorganizes <code>bucketA</code> if a nodes gain of it has been
0815      * changed.
0816      */
0817     void update_bucketA(const node cur_node, const int old_gain,
0818     const int new_gain, const bool init_mode);
0819
0820     /**
0821      * @internal
0822      * Reorganizes <code>bucketB</code> if a nodes gain of it has been
0823      * changed.
0824      */
0825     void update_bucketB(const node cur_node, const int old_gain,
0826     const int new_gain, const bool init_mode);
0827
0828     /**
0829      * @internal
0830      * Recomputes <code>max_gainA</code> or <code>max_gainB</code>
0831      * respectively.
0832      */
0833     void update_max_gain(const side_type side);
0834
0835     /**
0836      * @internal
0837      * Do some garbage collection.
0838      */
0839     void clean_step(const graph& G);
0840
0841     /**
0842      * @internal
0843      * Copies side node maps.
0844      */
0845     void copy_side_node_map(const graph& G, node_map<side_type>& dest,
0846     const node_map<side_type> source) const;
0847
0848     /**
0849      * @internal
0850      * Corresponds to phase 2 in [WeiChe91].
0851      */
0852     void iterative_shifting(const graph& G);
0853
0854     /**
0855      * @internal
0856      * Corresponds to phase 3 in [WeiChe91].
0857      */
0858     void group_swapping(const graph& G);
0859
0860     /**
0861      * @internal
0862      * Moves nodes in group swapping phase.
0863      * @return <code>true</code> on improvement, <code>false</code>
0864      * else
0865      */
0866     bool move_manager(const graph& G);
0867
0868     /**
0869      * @internal
0870      * Moves a single node.
0871      * @return <code>true</code> if vertex stored in parameter <code>
0872      * moved_node</code> has been found
0873      */
0874     bool move_vertex(const graph& G, node& moved_node);
0875
0876     /**
0877      * @internal
0878      * Computes list <code>cut_edges</code>.
0879      */
0880     void compute_cut_edges(const graph& G);
0881
0882     /**
0883      * @internal
0884      * Computes lists <code>nodesA</code> and <code>nodesB</code>.
0885      */
0886     void compute_nodesAB(const graph& G);
0887 private:
0888 #ifdef _DEBUG
0889     /**
0890      * @internal
0891      * Prints content of bucketA with associated gain values.
0892      */
0893     void print_bucketA();
0894
0895     /**
0896      * @internal
0897      * Prints content of bucketB with associated gain values.
0898      */
0899     void print_bucketB();
0900 #endif  // _DEBUG
0901 };
0902
0903 __GTL_END_NAMESPACE
0904
0905 #endif // GTL_RATIO_CUT_PARTITION_H
0906
0907 //--------------------------------------------------------------------------
0908 //   end of file
0909 //--------------------------------------------------------------------------