gtl/src/ratio_cut_partition.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //  ratio_cut_partition.cpp
0005 //
0006 //==========================================================================
0007 // $Id: ratio_cut_partition.cpp,v 1.9 2001/11/07 13:58:11 pick Exp $
0008
0009 #include <GTL/debug.h>
0010 #include <GTL/dfs.h>
0011 #include <GTL/ratio_cut_partition.h>
0012
0013 #include <iostream>
0014 #include <queue>
0015
0016 #include <cstdlib>
0017 #include <cassert>
0018 #include <cmath>
0019 #include <ctime>
0020
0021 #ifdef __GTL_MSVCC
0022 #   ifdef _DEBUG
0023 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0024 #   error SEARCH NOT ENABLED
0025 #   endif
0026 #   define new DEBUG_NEW
0027 #   undef THIS_FILE
0028     static char THIS_FILE[] = __FILE__;
0029 #   endif   // _DEBUG
0030 #endif  // __GTL_MSVCC
0031
0032 __GTL_BEGIN_NAMESPACE
0033
0034
0035 const ratio_cut_partition::side_type ratio_cut_partition::A = 0;
0036 const ratio_cut_partition::side_type ratio_cut_partition::B = 1;
0037
0038
0039 const ratio_cut_partition::fix_type ratio_cut_partition::FIXA = 0;
0040 const ratio_cut_partition::fix_type ratio_cut_partition::FIXB = 1;
0041 const ratio_cut_partition::fix_type ratio_cut_partition::UNFIXED = 2;
0042
0043
0044 ratio_cut_partition::ratio_cut_partition()
0045 {
0046     set_vars_executed = false;
0047     enable_cut_edges_storing = false;
0048     enable_nodesAB_storing = false;
0049 }
0050
0051
0052 ratio_cut_partition::~ratio_cut_partition()
0053 {
0054 }
0055
0056
0057 void ratio_cut_partition::set_vars(const graph& G,
0058     const node_map<int>& node_weight, const edge_map<int>& edge_weight)
0059 {
0060     this->node_weight = node_weight;
0061     this->edge_weight = edge_weight;
0062     set_vars_executed = true;
0063     provided_st = false;
0064     provided_fix = false;
0065     this->fixed.init(G, UNFIXED);
0066     provided_initial_part = false;
0067     side.init(G);
0068 }
0069
0070
0071 void ratio_cut_partition::set_vars(const graph& G,
0072     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0073     const node source_node, const node target_node)
0074 {
0075     this->node_weight = node_weight;
0076     this->edge_weight = edge_weight;
0077     this->source_node = source_node;
0078     this->target_node = target_node;
0079     set_vars_executed = true;
0080     provided_st = true;
0081     provided_fix = false;
0082     this->fixed.init(G, UNFIXED);
0083     provided_initial_part = false;
0084     side.init(G);
0085 }
0086
0087
0088 void ratio_cut_partition::set_vars(const graph& G,
0089     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0090     const node source_node, const node target_node,
0091     const node_map<side_type>& init_side)
0092 {
0093     this->node_weight = node_weight;
0094     this->edge_weight = edge_weight;
0095     this->source_node = source_node;
0096     this->target_node = target_node;
0097     this->side = init_side;
0098     set_vars_executed = true;
0099     provided_st = true;
0100     provided_fix = false;
0101     this->fixed.init(G, UNFIXED);
0102     provided_initial_part = true;
0103 }
0104
0105
0106 void ratio_cut_partition::set_vars(const graph& G,
0107     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0108     const node source_node, const node target_node,
0109     const node_map<fix_type>& fixed)
0110 {
0111     this->node_weight = node_weight;
0112     this->edge_weight = edge_weight;
0113     this->source_node = source_node;
0114     this->target_node = target_node;
0115     this->fixed = fixed;
0116     set_vars_executed = true;
0117     provided_st = true;
0118     provided_fix = true;
0119     provided_initial_part = false;
0120     side.init(G);
0121 }
0122
0123
0124 void ratio_cut_partition::set_vars(const graph& G,
0125     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0126     const node source_node, const node target_node,
0127     const node_map<side_type>& init_side, const node_map<fix_type>& fixed)
0128 {
0129     this->node_weight = node_weight;
0130     this->edge_weight = edge_weight;
0131     this->source_node = source_node;
0132     this->target_node = target_node;
0133     this->side = init_side;
0134     this->fixed = fixed;
0135     set_vars_executed = true;
0136     provided_st = true;
0137     provided_fix = true;
0138     provided_initial_part = true;
0139 }
0140
0141
0142 void ratio_cut_partition::store_cut_edges(const bool set)
0143 {
0144     enable_cut_edges_storing = set;
0145 }
0146
0147
0148 void ratio_cut_partition::store_nodesAB(const bool set)
0149 {
0150     enable_nodesAB_storing = set;
0151 }
0152
0153
0154 int ratio_cut_partition::check(graph& G)
0155 {
0156     if ((!set_vars_executed) || (!G.is_undirected()))
0157     {
0158     return GTL_ERROR;
0159     }
0160
0161     graph::edge_iterator edge_it = G.edges_begin();
0162     graph::edge_iterator edges_end = G.edges_end();
0163     while (edge_it != edges_end)
0164     {
0165     if (edge_weight[*edge_it] < 0)
0166     {
0167         return GTL_ERROR;
0168     }
0169     ++edge_it;
0170     }
0171     int real_node_weights = 0;
0172     graph::node_iterator node_it = G.nodes_begin();
0173     graph::node_iterator nodes_end = G.nodes_end();
0174     while (node_it != nodes_end)
0175     {
0176     if (node_weight[*node_it] > 0)
0177     {
0178         ++real_node_weights;
0179     }
0180     if (node_weight[*node_it] < 0)
0181     {
0182         return GTL_ERROR;
0183     }
0184     ++node_it;
0185     }
0186     if ((G.number_of_nodes() >= 2) && (real_node_weights < 2))
0187     {
0188     return GTL_ERROR;
0189     }
0190
0191     if ((provided_st) && (source_node == target_node) &&
0192     (G.number_of_nodes() > 1))
0193     {
0194     return GTL_ERROR;
0195     }
0196
0197     if ((provided_initial_part) && ((side[source_node] != A) ||
0198     (side[target_node] != B)))
0199     {
0200     return GTL_ERROR;
0201     }
0202
0203     if ((provided_fix) && ((fixed[source_node] == FIXB) ||
0204     (fixed[target_node] == FIXA)))
0205     {
0206     return GTL_ERROR;
0207     }
0208
0209     if ((provided_st) && (node_weight[source_node] == 0 ||
0210     node_weight[target_node] == 0))
0211     {
0212     return GTL_ERROR;
0213     }
0214
0215     return GTL_OK;
0216 }
0217
0218
0219 int ratio_cut_partition::run(graph& G)
0220 {
0221     cur_cutsize = 0;
0222     cur_cutratio = 0.0;
0223     if (G.number_of_nodes() == 0)
0224     {
0225     return GTL_OK;  // nothing to do
0226     }
0227     if (G.number_of_nodes() == 1)
0228     {
0229     side[*G.nodes_begin()] = A;
0230     return GTL_OK;
0231     }
0232
0233     list<edge> artificial_edges;
0234     if (!G.is_connected())
0235     {
0236     make_connected(G, artificial_edges);
0237     }
0238
0239     if (provided_fix)
0240     {
0241     divide_up(G);
0242     }
0243
0244     if (!provided_st)
0245     {
0246     determine_source_node(G);
0247     compute_target_node(G);
0248     }
0249
0250     if (provided_initial_part)
0251     {
0252     init_variables(G);
0253     init_data_structure(G);
0254     direction = LEFT_SHIFT;
0255     clean_step(G);
0256     }
0257     else
0258     {
0259     initialization(G);
0260     }
0261     iterative_shifting(G);
0262     group_swapping(G);
0263
0264     if (enable_cut_edges_storing)
0265     {
0266     compute_cut_edges(G);
0267     }
0268     if (enable_nodesAB_storing)
0269     {
0270     compute_nodesAB(G);
0271     }
0272     restore(G, artificial_edges);
0273
0274     return GTL_OK;
0275 }
0276
0277
0278 int ratio_cut_partition::get_cutsize()
0279 {
0280     return cur_cutsize;
0281 }
0282
0283
0284 double ratio_cut_partition::get_cutratio()
0285 {
0286     return cur_cutratio;
0287 }
0288
0289
0290 ratio_cut_partition::side_type
0291 ratio_cut_partition::get_side_of_node(const node& n) const
0292 {
0293     return side[n];
0294 }
0295
0296
0297 ratio_cut_partition::side_type ratio_cut_partition::operator []
0298 (const node& n) const
0299 {
0300     return side[n];
0301 }
0302
0303
0304 int ratio_cut_partition::get_weight_on_sideA(const graph& G) const
0305 {
0306     int nwA = 0;
0307     graph::node_iterator node_it = G.nodes_begin();
0308     graph::node_iterator nodes_end = G.nodes_end();
0309     while (node_it != nodes_end)
0310     {
0311     if (side[*node_it] == A)
0312     {
0313         nwA += node_weight[*node_it];
0314     }
0315     ++node_it;
0316     }
0317     return nwA;
0318 }
0319
0320
0321 int ratio_cut_partition::get_weight_on_sideB(const graph& G) const
0322 {
0323     int nwB = 0;
0324     graph::node_iterator node_it = G.nodes_begin();
0325     graph::node_iterator nodes_end = G.nodes_end();
0326     while (node_it != nodes_end)
0327     {
0328     if (side[*node_it] == B)
0329     {
0330         nwB += node_weight[*node_it];
0331     }
0332     ++node_it;
0333     }
0334     return nwB;
0335 }
0336
0337
0338 ratio_cut_partition::cut_edges_iterator
0339 ratio_cut_partition::cut_edges_begin() const
0340 {
0341     return cut_edges.begin();
0342 }
0343
0344
0345 ratio_cut_partition::cut_edges_iterator
0346 ratio_cut_partition::cut_edges_end() const
0347 {
0348     return cut_edges.end();
0349 }
0350
0351
0352 ratio_cut_partition::nodes_of_one_side_iterator
0353 ratio_cut_partition::nodes_of_sideA_begin() const
0354 {
0355     return nodesA.begin();
0356 }
0357
0358
0359 ratio_cut_partition::nodes_of_one_side_iterator
0360 ratio_cut_partition::nodes_of_sideA_end() const
0361 {
0362     return nodesA.end();
0363 }
0364
0365
0366 ratio_cut_partition::nodes_of_one_side_iterator
0367 ratio_cut_partition::nodes_of_sideB_begin() const
0368 {
0369     return nodesB.begin();
0370 }
0371
0372
0373 ratio_cut_partition::nodes_of_one_side_iterator
0374 ratio_cut_partition::nodes_of_sideB_end() const
0375 {
0376     return nodesB.end();
0377 }
0378
0379
0380 void ratio_cut_partition::reset()
0381 {
0382     set_vars_executed = false;
0383     cut_edges.clear();
0384     nodesA.clear();
0385     nodesB.clear();
0386 }
0387
0388
0389 void ratio_cut_partition::divide_up(const graph& G)
0390 {
0391     graph::node_iterator node_it = G.nodes_begin();
0392     graph::node_iterator nodes_end = G.nodes_end();
0393     while (node_it != nodes_end)
0394     {
0395     if (fixed[*node_it] == FIXA)
0396     {
0397         side[*node_it] = A;
0398     }
0399     else if (fixed[*node_it] == FIXB)
0400     {
0401         side[*node_it] = B;
0402     }
0403     ++node_it;
0404     }
0405 }
0406
0407
0408 void ratio_cut_partition::make_connected(graph& G,
0409     list<edge>& artificial_edges)
0410 {
0411     dfs conn;
0412     conn.scan_whole_graph(true);
0413     conn.check(G);
0414     conn.run(G);
0415
0416     // connect dfs roots with zero edges
0417     dfs::roots_iterator root_it = conn.roots_begin();
0418     dfs::roots_iterator rootes_end = conn.roots_end();
0419     while (root_it != rootes_end)
0420     {
0421     node edge_start = **root_it;
0422     ++root_it;
0423     if (root_it != rootes_end)
0424     {
0425         edge ne = G.new_edge(edge_start, **root_it);
0426         edge_weight[ne] = 0;    // this edge has no cut costs
0427         artificial_edges.push_back(ne);
0428     }
0429     }
0430 }
0431
0432
0433 void ratio_cut_partition::restore(graph& G, list<edge>& artificial_edges)
0434 {
0435     list<edge>::iterator edge_it = artificial_edges.begin();
0436     list<edge>::iterator edges_end = artificial_edges.end();
0437     while (edge_it != edges_end)
0438     {
0439     G.del_edge(*edge_it);
0440     ++edge_it;
0441     }
0442 }
0443
0444
0445 void ratio_cut_partition::initialization(const graph& G)
0446 {
0447     int cutsize_A2B, cutsize_B2A;
0448     double cutratio_A2B, cutratio_B2A;
0449     node_map<side_type> side_B2A(G);
0450
0451     init_variables(G);
0452
0453     // start with moves from B to A
0454     graph::node_iterator node_it = G.nodes_begin();
0455     graph::node_iterator nodes_end = G.nodes_end();
0456     while (node_it != nodes_end)
0457     {
0458     if (fixed[*node_it] == UNFIXED)
0459     {
0460         side[*node_it] = B;
0461     }
0462     ++node_it;
0463     }
0464     side[source_node] = A;
0465     side[target_node] = B;
0466     init_data_structure(G);
0467     if (fixed[target_node] == UNFIXED)
0468     {
0469     bucketB[range_up(gain_value[target_node])].
0470         erase(position_in_bucket[target_node]);
0471     update_max_gain(B);
0472     }
0473     left_shift_op(G);
0474     clean_step(G);
0475     cutsize_B2A = cur_cutsize;
0476     cutratio_B2A = cur_cutratio;
0477     copy_side_node_map(G, side_B2A, side);
0478
0479     // continue with moves from A to B
0480     node_it = G.nodes_begin();
0481     while (node_it != nodes_end)
0482     {
0483     if (fixed[*node_it] == UNFIXED)
0484     {
0485         side[*node_it] = A;
0486     }
0487     ++node_it;
0488     }
0489     side[source_node] = A;
0490     side[target_node] = B;
0491     init_data_structure(G);
0492     if (fixed[source_node] == UNFIXED)
0493     {
0494     bucketA[range_up(gain_value[source_node])].
0495         erase(position_in_bucket[source_node]);
0496     update_max_gain(A);
0497     }
0498     right_shift_op(G);
0499     clean_step(G);
0500     cutsize_A2B = cur_cutsize;
0501     cutratio_A2B = cur_cutratio;
0502
0503     if (cutratio_B2A < cutratio_A2B)
0504     {
0505     copy_side_node_map(G, side, side_B2A);
0506     cur_cutsize = cutsize_B2A;
0507     cur_cutratio = cutratio_B2A;
0508     direction = LEFT_SHIFT;
0509     }
0510     else
0511     {
0512     // copy_side_node_map(...) not necessary
0513     cur_cutsize = cutsize_A2B;
0514     cur_cutratio = cutratio_A2B;
0515     direction = RIGHT_SHIFT;
0516     }
0517 }
0518
0519
0520 void ratio_cut_partition::init_data_structure(const graph& G)
0521 {
0522     aside.init(G);
0523     bside.init(G);
0524     unlockedA.init(G);
0525     unlockedB.init(G);
0526     cur_cutsize = 0;
0527     graph::edge_iterator edge_it = G.edges_begin();
0528     graph::edge_iterator edges_end = G.edges_end();
0529     while (edge_it != edges_end)
0530     {
0531     if ((side[(*edge_it).source()] == A) &&
0532         (side[(*edge_it).target()] == A))
0533     {
0534         aside[*edge_it] = 2;
0535         bside[*edge_it] = 0;
0536         unlockedA[*edge_it].push_back((*edge_it).source());
0537         unlockedA[*edge_it].push_back((*edge_it).target());
0538     }
0539     else if ((side[(*edge_it).source()] == B) &&
0540         (side[(*edge_it).target()] == B))
0541     {
0542         aside[*edge_it] = 0;
0543         bside[*edge_it] = 2;
0544         unlockedB[*edge_it].push_back((*edge_it).source());
0545         unlockedB[*edge_it].push_back((*edge_it).target());
0546     }
0547     else if ((side[(*edge_it).source()] == A) &&
0548         (side[(*edge_it).target()] == B))
0549     {
0550         aside[*edge_it] = 1;
0551         bside[*edge_it] = 1;
0552         cur_cutsize += edge_weight[*edge_it];
0553         unlockedA[*edge_it].push_back((*edge_it).source());
0554         unlockedB[*edge_it].push_back((*edge_it).target());
0555     }
0556     else if ((side[(*edge_it).source()] == B) &&
0557         (side[(*edge_it).target()] == A))
0558     {
0559         aside[*edge_it] = 1;
0560         bside[*edge_it] = 1;
0561         cur_cutsize += edge_weight[*edge_it];
0562         unlockedA[*edge_it].push_back((*edge_it).target());
0563         unlockedB[*edge_it].push_back((*edge_it).source());
0564     }
0565     ++edge_it;
0566     }
0567
0568     bucketA.resize(2 * max_vertex_degree * max_edge_weight + 1);
0569     bucketB.resize(2 * max_vertex_degree * max_edge_weight + 1);
0570
0571     init_filling_buckets(G);
0572     cur_cutratio = cutratio();
0573 }
0574
0575
0576 void ratio_cut_partition::init_filling_buckets(const graph &G)
0577 {
0578     node_weight_on_sideA = 0;
0579     node_weight_on_sideB = 0;
0580     nodes_on_sideA = 0;
0581     nodes_on_sideB = 0;
0582     bucketA_empty = true;
0583     bucketB_empty = true;
0584     bool first_A_node = true;
0585     bool first_B_node = true;
0586     int index;
0587     //    position_in_bucket.init(G);
0588     gain_value.init(G);
0589
0590     graph::node_iterator node_it = G.nodes_begin();
0591     graph::node_iterator nodes_end = G.nodes_end();
0592     while (node_it != nodes_end)
0593     {
0594     if (side[*node_it] == A)
0595     {
0596         node_weight_on_sideA += node_weight[*node_it];
0597         ++nodes_on_sideA;
0598         gain_value[*node_it] = inital_gain_of_node_on_sideA(*node_it);
0599         if (fixed[*node_it] == UNFIXED)
0600         {
0601         if (first_A_node)
0602         {
0603             bucketA_empty = false;
0604             max_gainA = gain_value[*node_it];
0605             first_A_node = false;
0606         }
0607         else
0608         {
0609             if (max_gainA < gain_value[*node_it])
0610             {
0611             max_gainA = gain_value[*node_it];
0612             }
0613         }
0614         index = range_up(gain_value[*node_it]);
0615         position_in_bucket[*node_it] = bucketA[index].insert(
0616             bucketA[index].begin(), *node_it);
0617         }
0618     }
0619     else    // side[*node_it] == B
0620     {
0621         node_weight_on_sideB += node_weight[*node_it];
0622         ++nodes_on_sideB;
0623         gain_value[*node_it] = inital_gain_of_node_on_sideB(*node_it);
0624         if (fixed[*node_it] == UNFIXED)
0625         {
0626         if (first_B_node)
0627         {
0628             bucketB_empty = false;
0629             max_gainB = gain_value[*node_it];
0630             first_B_node = false;
0631         }
0632         else
0633         {
0634             if (max_gainB < gain_value[*node_it])
0635             {
0636             max_gainB = gain_value[*node_it];
0637             }
0638         }
0639         index = range_up(gain_value[*node_it]);
0640         position_in_bucket[*node_it] = bucketB[index].insert(
0641             bucketB[index].begin(), *node_it);
0642         }
0643     }
0644     ++node_it;
0645     }
0646 }
0647
0648
0649 int ratio_cut_partition::inital_gain_of_node_on_sideA(const node cur_node)
0650 {
0651     int node_gain = 0;
0652     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0653     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0654     while (adj_edge_it != adj_edges_end)
0655     {
0656     if (aside[*adj_edge_it] == 1)
0657     {
0658         node_gain += edge_weight[*adj_edge_it];
0659     }
0660     if (bside[*adj_edge_it] == 0)
0661     {
0662         node_gain -= edge_weight[*adj_edge_it];
0663     }
0664     ++adj_edge_it;
0665     }
0666     return node_gain;
0667 }
0668
0669
0670 int ratio_cut_partition::inital_gain_of_node_on_sideB(const node cur_node)
0671 {
0672     int node_gain = 0;
0673     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0674     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0675     while (adj_edge_it != adj_edges_end)
0676     {
0677     if (bside[*adj_edge_it] == 1)
0678     {
0679         node_gain += edge_weight[*adj_edge_it];
0680     }
0681     if (aside[*adj_edge_it] == 0)
0682     {
0683         node_gain -= edge_weight[*adj_edge_it];
0684     }
0685     ++adj_edge_it;
0686     }
0687     return node_gain;
0688 }
0689
0690
0691 void ratio_cut_partition::init_variables(const graph& G)
0692 {
0693     compute_max_vertex_degree(G);
0694     bool first_edge_found = true;
0695     max_edge_weight = 0;
0696     graph::edge_iterator edge_it = G.edges_begin();
0697     graph::edge_iterator edges_end = G.edges_end();
0698     while (edge_it != edges_end)
0699     {
0700     if (first_edge_found)
0701     {
0702         max_edge_weight = edge_weight[*edge_it];
0703         first_edge_found = false;
0704     }
0705     else if (edge_weight[*edge_it] > max_edge_weight)
0706     {
0707         max_edge_weight = edge_weight[*edge_it];
0708     }
0709     ++edge_it;
0710     }
0711 }
0712
0713
0714 void ratio_cut_partition::compute_max_vertex_degree(const graph& G)
0715 {
0716     max_vertex_degree = 0;
0717     graph::node_iterator node_it = G.nodes_begin();
0718     graph::node_iterator nodes_end = G.nodes_end();
0719     while (node_it != nodes_end)
0720     {
0721     if (max_vertex_degree < (*node_it).degree())
0722     {
0723         max_vertex_degree = (*node_it).degree();
0724     }
0725     ++node_it;
0726     }
0727 }
0728
0729
0730 void ratio_cut_partition::determine_source_node(const graph& G)
0731 {
0732     srand((unsigned)time(NULL));
0733     rand(); // necessary, otherwise the next rand() returns always 0 ?-)
0734     int node_id = (int)floor((((double)rand() / (double)RAND_MAX) *
0735     (double)(G.number_of_nodes() - 1)) + 0.5);
0736     graph::node_iterator node_it = G.nodes_begin();
0737     for (int i = 1; i <= node_id; i++)
0738     {
0739     ++node_it;
0740     }
0741     source_node = *node_it;
0742     if (node_weight[source_node] == 0)
0743     {
0744     node_it = G.nodes_begin();
0745     while (node_weight[*node_it] == 0)
0746     {
0747         ++node_it;
0748     }
0749     source_node = *node_it;
0750     }
0751 }
0752
0753
0754 void ratio_cut_partition::compute_target_node(const graph& G)
0755 {
0756     node cur_node, next;
0757     node_map<bool> visited(G, false);
0758     queue<node> next_nodes;
0759     next_nodes.push(source_node);
0760     visited[source_node] = true;
0761
0762     while (!next_nodes.empty())
0763     {
0764     cur_node = next_nodes.front();
0765     next_nodes.pop();
0766
0767     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0768     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0769     while (adj_edge_it != adj_edges_end)
0770     {
0771         if ((*adj_edge_it).target() != cur_node)
0772         {
0773         next = (*adj_edge_it).target();
0774         }
0775         else
0776         {
0777         next = (*adj_edge_it).source();
0778         }
0779         if (!visited[next])
0780         {
0781         next_nodes.push(next);
0782         visited[next] = true;
0783         }
0784         ++adj_edge_it;
0785     }
0786     }
0787     target_node = cur_node;
0788     if (node_weight[target_node] == 0)
0789     {
0790     graph::node_iterator node_it = G.nodes_begin();
0791     while ((node_weight[*node_it] == 0) || (*node_it == source_node))
0792     {
0793         ++node_it;
0794     }
0795     target_node = *node_it;
0796     }
0797 }
0798
0799
0800 void ratio_cut_partition::right_shift_op(const graph& G)
0801 {
0802     int step_number = 0;
0803     int best_tentative_move = 0;
0804     int best_bal = node_weight_on_sideA * node_weight_on_sideB;
0805     vector<node> tentative_moves(G.number_of_nodes() + 1);
0806     vector<double> tentative_cutratio(G.number_of_nodes() + 1);
0807     node moved_node;
0808     tentative_cutratio[0] = cur_cutratio;
0809     int best_cutsize = cur_cutsize;
0810
0811     while (move_vertex_A2B(G, moved_node))
0812     {
0813     ++step_number;
0814     tentative_cutratio[step_number] = cur_cutratio;
0815     tentative_moves[step_number] = moved_node;
0816     if (tentative_cutratio[best_tentative_move] > cur_cutratio)
0817     {
0818         best_tentative_move = step_number;
0819         best_cutsize = cur_cutsize;
0820         best_bal = node_weight_on_sideA * node_weight_on_sideB;
0821     }
0822     else if (tentative_cutratio[best_tentative_move] == cur_cutratio)
0823     {
0824         if (node_weight_on_sideA * node_weight_on_sideB > best_bal)
0825         {
0826         best_tentative_move = step_number;
0827         best_cutsize = cur_cutsize;
0828         best_bal = node_weight_on_sideA * node_weight_on_sideB;
0829         }
0830     }
0831     }
0832
0833     for (int i = 1; i <= best_tentative_move; i++)
0834     {
0835     if (side[tentative_moves[i]] == A)
0836     {
0837         side[tentative_moves[i]] = B;
0838     }
0839     else    // side[tentative_moves[i]] == B
0840     {
0841         side[tentative_moves[i]] = A;
0842     }
0843     }
0844     cur_cutratio = tentative_cutratio[best_tentative_move];
0845     cur_cutsize = best_cutsize;
0846 }
0847
0848
0849 void ratio_cut_partition::left_shift_op(const graph& G)
0850 {
0851     int step_number = 0;
0852     int best_tentative_move = 0;
0853     int best_bal = node_weight_on_sideA * node_weight_on_sideB;
0854     vector<node> tentative_moves(G.number_of_nodes() + 1);
0855     vector<double> tentative_cutratio(G.number_of_nodes() + 1);
0856     node moved_node;
0857     tentative_cutratio[0] = cur_cutratio;
0858     int best_cutsize = cur_cutsize;
0859
0860     while (move_vertex_B2A(G, moved_node))
0861     {
0862     ++step_number;
0863     tentative_cutratio[step_number] = cur_cutratio;
0864     tentative_moves[step_number] = moved_node;
0865     if (tentative_cutratio[best_tentative_move] > cur_cutratio)
0866     {
0867         best_tentative_move = step_number;
0868         best_cutsize = cur_cutsize;
0869     }
0870     else if (tentative_cutratio[best_tentative_move] == cur_cutratio)
0871     {
0872         if (node_weight_on_sideA * node_weight_on_sideB > best_bal)
0873         {
0874         best_tentative_move = step_number;
0875         best_cutsize = cur_cutsize;
0876         best_bal = node_weight_on_sideA * node_weight_on_sideB;
0877         }
0878     }
0879     }
0880
0881     for (int i = 1; i <= best_tentative_move; i++)
0882     {
0883     if (side[tentative_moves[i]] == A)
0884     {
0885         side[tentative_moves[i]] = B;
0886     }
0887     else    // side[tentative_moves[i]] == B
0888     {
0889         side[tentative_moves[i]] = A;
0890     }
0891     }
0892     cur_cutratio = tentative_cutratio[best_tentative_move];
0893     cur_cutsize = best_cutsize;
0894 }
0895
0896
0897 bool ratio_cut_partition::move_vertex_A2B(const graph &G, node& moved_node)
0898 {
0899     if (!bucketA_empty)
0900     {
0901     node cons_nodeA =
0902         compute_highest_ratio_node(bucketA[range_up(max_gainA)]);
0903     bucketA[range_up(max_gainA)].erase(position_in_bucket[cons_nodeA]);
0904     update_data_structure_A2B(cons_nodeA, true);
0905     moved_node = cons_nodeA;
0906     }
0907     else
0908     {
0909     return false;   // no more vertices can be moved
0910     }
0911     update_max_gain(A);
0912     return true;
0913 }
0914
0915
0916 bool ratio_cut_partition::move_vertex_B2A(const graph &G, node& moved_node)
0917 {
0918     if (!bucketB_empty)
0919     {
0920     node cons_nodeB =
0921         compute_highest_ratio_node(bucketB[range_up(max_gainB)]);
0922     bucketB[range_up(max_gainB)].erase(position_in_bucket[cons_nodeB]);
0923     update_data_structure_B2A(cons_nodeB, true);
0924     moved_node = cons_nodeB;
0925     }
0926     else
0927     {
0928     return false;   // no more vertices can be moved
0929     }
0930     update_max_gain(B);
0931     return true;
0932 }
0933
0934
0935 node ratio_cut_partition::compute_highest_ratio_node(list<node> node_list)
0936 {
0937     node cons_node = node_list.front();
0938     double ratio, best_ratio;
0939     if (side[cons_node] == A)
0940     {
0941     best_ratio = ratio_of_node_A2B(cons_node);
0942     }
0943     else    // side[cons_node] == B
0944     {
0945     best_ratio = ratio_of_node_B2A(cons_node);
0946     }
0947
0948     list<node>::iterator node_it = node_list.begin();
0949     list<node>::iterator nodes_end = node_list.end();
0950     while (node_it != nodes_end)
0951     {
0952     if (side[cons_node] == A)
0953     {
0954         ratio = ratio_of_node_A2B(*node_it);
0955     }
0956     else    // side[cons_node] == B
0957     {
0958         ratio = ratio_of_node_B2A(*node_it);
0959     }
0960     if (ratio > best_ratio) // choose node with highest ratio
0961     {
0962         best_ratio = ratio;
0963         cons_node = *node_it;
0964     }
0965     ++node_it;
0966     }
0967     return cons_node;
0968 }
0969
0970
0971 double ratio_cut_partition::cutratio()
0972 {
0973     double number_of_nodes = (double)(nodes_on_sideA + nodes_on_sideB);
0974     return ((double)cur_cutsize + number_of_nodes) / (double)
0975     (node_weight_on_sideA * node_weight_on_sideB);
0976 }
0977
0978
0979 double ratio_cut_partition::ratio_of_node_A2B(const node cur_node)
0980 {
0981     return (double)gain_value[cur_node] /
0982     ((double)((node_weight_on_sideB + node_weight[cur_node]) *
0983         (node_weight_on_sideA - node_weight[cur_node])));
0984 }
0985
0986
0987 double ratio_cut_partition::ratio_of_node_B2A(const node cur_node)
0988 {
0989     return (double)gain_value[cur_node] /
0990     ((double)((node_weight_on_sideA + node_weight[cur_node]) *
0991         (node_weight_on_sideB - node_weight[cur_node])));
0992 }
0993
0994
0995 inline int ratio_cut_partition::range_up(const int gain_value) const
0996 {
0997     return gain_value + (max_vertex_degree * max_edge_weight);
0998 }
0999
1000
1001 inline int ratio_cut_partition::range_down(const int index) const
1002 {
1003     return index - (max_vertex_degree * max_edge_weight);
1004 }
1005
1006
1007 void ratio_cut_partition::update_data_structure_A2B(const node cur_node,
1008     const bool init_mode)
1009 {
1010     node_weight_on_sideA -= node_weight[cur_node];
1011     node_weight_on_sideB += node_weight[cur_node];
1012     --nodes_on_sideA;
1013     ++nodes_on_sideB;
1014     cur_cutsize -= gain_value[cur_node];
1015     cur_cutratio = cutratio();
1016
1017     // updating gain values
1018     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
1019     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
1020     while (adj_edge_it != adj_edges_end)
1021     {
1022     // delete cur_node from side A
1023     unlockedA[*adj_edge_it].remove(cur_node);
1024     --aside[*adj_edge_it];
1025     if (aside[*adj_edge_it] == 0)
1026     {
1027         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
1028         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
1029         while (node_it != nodes_end)
1030         {
1031         update_bucketB(*node_it, gain_value[*node_it],
1032             gain_value[*node_it] - edge_weight[*adj_edge_it],
1033             init_mode);
1034         gain_value[*node_it] -= edge_weight[*adj_edge_it];
1035         ++node_it;
1036         }
1037     }
1038     else if (aside[*adj_edge_it] == 1)
1039     {
1040         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
1041         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
1042         while (node_it != nodes_end)
1043         {
1044         update_bucketA(*node_it, gain_value[*node_it],
1045             gain_value[*node_it] + edge_weight[*adj_edge_it],
1046             init_mode);
1047         gain_value[*node_it] += edge_weight[*adj_edge_it];
1048         ++node_it;
1049         }
1050     }
1051     // add cur_node to side B
1052     ++bside[*adj_edge_it];
1053     if (bside[*adj_edge_it] == 1)
1054     {
1055         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
1056         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
1057         while (node_it != nodes_end)
1058         {
1059         update_bucketA(*node_it, gain_value[*node_it],
1060             gain_value[*node_it] + edge_weight[*adj_edge_it],
1061             init_mode);
1062         gain_value[*node_it] += edge_weight[*adj_edge_it];
1063         ++node_it;
1064         }
1065     }
1066     else if (bside[*adj_edge_it] == 2)
1067     {
1068         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
1069         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
1070         while (node_it != nodes_end)
1071         {
1072         update_bucketB(*node_it, gain_value[*node_it],
1073             gain_value[*node_it] - edge_weight[*adj_edge_it],
1074             init_mode);
1075         gain_value[*node_it] -= edge_weight[*adj_edge_it];
1076         ++node_it;
1077         }
1078     }
1079     ++adj_edge_it;
1080     }
1081 }
1082
1083
1084 void ratio_cut_partition::update_data_structure_B2A(const node cur_node,
1085     const bool init_mode)
1086 {
1087     node_weight_on_sideA += node_weight[cur_node];
1088     node_weight_on_sideB -= node_weight[cur_node];
1089     ++nodes_on_sideA;
1090     --nodes_on_sideB;
1091     cur_cutsize -= gain_value[cur_node];
1092     cur_cutratio = cutratio();
1093
1094     // updating gain values
1095     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
1096     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
1097     while (adj_edge_it != adj_edges_end)
1098     {
1099     // delete cur_node from side B
1100     unlockedB[*adj_edge_it].remove(cur_node);
1101     bside[*adj_edge_it] -= 1;
1102     if (bside[*adj_edge_it] == 0)
1103     {
1104         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
1105         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
1106         while (node_it != nodes_end)
1107         {
1108         update_bucketA(*node_it, gain_value[*node_it],
1109             gain_value[*node_it] - edge_weight[*adj_edge_it],
1110             init_mode);
1111         gain_value[*node_it] -= edge_weight[*adj_edge_it];
1112         ++node_it;
1113         }
1114     }
1115     else if (bside[*adj_edge_it] == 1)
1116     {
1117         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
1118         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
1119         while (node_it != nodes_end)
1120         {
1121         update_bucketB(*node_it, gain_value[*node_it],
1122             gain_value[*node_it] + edge_weight[*adj_edge_it],
1123             init_mode);
1124         gain_value[*node_it] += edge_weight[*adj_edge_it];
1125         ++node_it;
1126         }
1127     }
1128     // add cur_node to side A
1129     aside[*adj_edge_it] += 1;
1130     if (aside[*adj_edge_it] == 1)
1131     {
1132         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
1133         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
1134         while (node_it != nodes_end)
1135         {
1136         update_bucketB(*node_it, gain_value[*node_it],
1137             gain_value[*node_it] + edge_weight[*adj_edge_it],
1138             init_mode);
1139         gain_value[*node_it] += edge_weight[*adj_edge_it];
1140         ++node_it;
1141         }
1142     }
1143     else if (aside[*adj_edge_it] == 2)
1144     {
1145         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
1146         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
1147         while (node_it != nodes_end)
1148         {
1149         update_bucketA(*node_it, gain_value[*node_it],
1150             gain_value[*node_it] - edge_weight[*adj_edge_it],
1151             init_mode);
1152         gain_value[*node_it] -= edge_weight[*adj_edge_it];
1153         ++node_it;
1154         }
1155     }
1156     ++adj_edge_it;
1157     }
1158 }
1159
1160
1161 void ratio_cut_partition::update_bucketA(const node cur_node,
1162     const int old_gain, const int new_gain, const bool init_mode)
1163 {
1164     if ((init_mode) && (cur_node == source_node))
1165     {
1166     return; // this one needs no update with init_mode
1167     }
1168     if (fixed[cur_node] != UNFIXED)
1169     {
1170     return; // fixed nodes need no update
1171     }
1172     bucketA[range_up(old_gain)].erase(position_in_bucket[cur_node]);
1173     bucketA[range_up(new_gain)].push_front(cur_node);
1174     position_in_bucket[cur_node] = bucketA[range_up(new_gain)].begin();
1175     if (max_gainA < new_gain)
1176     {
1177     max_gainA = new_gain;
1178     }
1179 }
1180
1181
1182 void ratio_cut_partition::update_bucketB(const node cur_node,
1183     const int old_gain, const int new_gain, const bool init_mode)
1184 {
1185     if ((init_mode) && (cur_node == target_node))
1186     {
1187     return; // this one needs no update with init_mode
1188     }
1189     if (fixed[cur_node] != UNFIXED)
1190     {
1191     return; // fixed nodes need no update
1192     }
1193     bucketB[range_up(old_gain)].erase(position_in_bucket[cur_node]);
1194     bucketB[range_up(new_gain)].push_front(cur_node);
1195     position_in_bucket[cur_node] = bucketB[range_up(new_gain)].begin();
1196     if (max_gainB < new_gain)
1197     {
1198     max_gainB = new_gain;
1199     }
1200 }
1201
1202
1203 void ratio_cut_partition::update_max_gain(const side_type side)
1204 {
1205     if ((side == A) && (!bucketA_empty))
1206     {
1207     while (bucketA[range_up(max_gainA)].begin() ==
1208         bucketA[range_up(max_gainA)].end())
1209     {
1210         --max_gainA;
1211         if (range_up(max_gainA) < 0)
1212         {
1213         bucketA_empty = true;
1214         return;
1215         }
1216     }
1217     bucketA_empty = false;
1218     }
1219     if ((side == B) && (!bucketB_empty))
1220     {
1221     while (bucketB[range_up(max_gainB)].begin() ==
1222         bucketB[range_up(max_gainB)].end())
1223     {
1224         --max_gainB;
1225         if (range_up(max_gainB) < 0)
1226         {
1227         bucketB_empty = true;
1228         return;
1229         }
1230     }
1231     bucketB_empty = false;
1232     }
1233 }
1234
1235
1236 void ratio_cut_partition::clean_step(const graph& G)
1237 {
1238     // clean unlocked* lists
1239     graph::edge_iterator edge_it = G.edges_begin();
1240     graph::edge_iterator edges_end = G.edges_end();
1241     while (edge_it != edges_end)
1242     {
1243     unlockedA[*edge_it].clear();
1244     unlockedB[*edge_it].clear();
1245     ++edge_it;
1246     }
1247
1248     // clean buckets
1249     for (int i = 0; i <= 2 * max_vertex_degree * max_edge_weight; i++)
1250     {
1251     bucketA[i].clear();
1252     bucketB[i].clear();
1253     }
1254     bucketA.clear();
1255     bucketB.clear();
1256 }
1257
1258
1259 void ratio_cut_partition::copy_side_node_map(const graph& G,
1260     node_map<side_type>& dest, const node_map<side_type> source) const
1261 {
1262     graph::node_iterator node_it = G.nodes_begin();
1263     graph::node_iterator nodes_end = G.nodes_end();
1264     while (node_it != nodes_end)
1265     {
1266     dest[*node_it] = source[*node_it];
1267     ++node_it;
1268     }
1269 }
1270
1271
1272 void ratio_cut_partition::iterative_shifting(const graph& G)
1273 {
1274     bool continue_loop = true;
1275     int old_cutsize = cur_cutsize;
1276     double old_cutratio = cur_cutratio;
1277
1278     while (continue_loop)
1279     {
1280     if (direction == LEFT_SHIFT)
1281     {
1282         init_data_structure(G);
1283         if (fixed[source_node] == UNFIXED)
1284         {
1285         bucketA[range_up(gain_value[source_node])].
1286             erase(position_in_bucket[source_node]);
1287         update_max_gain(A);
1288         }
1289         right_shift_op(G);
1290         clean_step(G);
1291         if (cur_cutratio < old_cutratio)
1292         {
1293         continue_loop = true;
1294         direction = RIGHT_SHIFT;
1295         old_cutsize = cur_cutsize;
1296         old_cutratio = cur_cutratio;
1297         }
1298         else
1299         {
1300         continue_loop = false;
1301         }
1302     }
1303     else    // direction == RIGHT_SHIFT
1304     {
1305         init_data_structure(G);
1306         if (fixed[target_node] == UNFIXED)
1307         {
1308         bucketB[range_up(gain_value[target_node])].
1309             erase(position_in_bucket[target_node]);
1310         update_max_gain(B);
1311         }
1312         left_shift_op(G);
1313         clean_step(G);
1314         if (cur_cutratio < old_cutratio)
1315         {
1316         continue_loop = true;
1317         direction = LEFT_SHIFT;
1318         old_cutsize = cur_cutsize;
1319         old_cutratio = cur_cutratio;
1320         }
1321         else
1322         {
1323         continue_loop = false;
1324         }
1325     }
1326     }
1327 }
1328
1329
1330 void ratio_cut_partition::group_swapping(const graph& G)
1331 {
1332     bool improved_cutratio;
1333
1334     do
1335     {
1336     init_data_structure(G);
1337     improved_cutratio = move_manager(G);
1338     clean_step(G);
1339     }
1340     while (improved_cutratio);
1341 }
1342
1343
1344 bool ratio_cut_partition::move_manager(const graph& G)
1345 {
1346     int step_number = 0;
1347     int best_tentative_move = 0;
1348     int best_bal = node_weight_on_sideA * node_weight_on_sideB;
1349     vector<node> tentative_moves(G.number_of_nodes() + 1);
1350     vector<double> tentative_cutratio(G.number_of_nodes() + 1);
1351     node moved_node;
1352     tentative_cutratio[0] = cur_cutratio;
1353     int best_cutsize = cur_cutsize;
1354
1355     while (move_vertex(G, moved_node))
1356     {
1357     ++step_number;
1358     tentative_moves[step_number] = moved_node;
1359     tentative_cutratio[step_number] = cur_cutratio;
1360     if (tentative_cutratio[best_tentative_move] > cur_cutratio)
1361     {
1362         best_tentative_move = step_number;
1363         best_cutsize = cur_cutsize;
1364         best_bal = node_weight_on_sideA * node_weight_on_sideB;
1365     }
1366     else if (tentative_cutratio[best_tentative_move] == cur_cutratio)
1367     {
1368         if (node_weight_on_sideA * node_weight_on_sideB > best_bal)
1369         {
1370         best_tentative_move = step_number;
1371         best_cutsize = cur_cutsize;
1372         best_bal = node_weight_on_sideA * node_weight_on_sideB;
1373         }
1374     }
1375     }
1376
1377     for (int i = 1; i <= best_tentative_move; i++)
1378     {
1379     if (side[tentative_moves[i]] == A)
1380     {
1381         side[tentative_moves[i]] = B;
1382     }
1383     else    // side[tentative_moves[i]] == B
1384     {
1385         side[tentative_moves[i]] = A;
1386     }
1387     }
1388     cur_cutratio = tentative_cutratio[best_tentative_move];
1389     cur_cutsize = best_cutsize;
1390     if (best_tentative_move > 0)    // cutratio improved
1391     {
1392     return true;
1393     }
1394     return false;   // best_move == 0  -->  cutratio not improved
1395 }
1396
1397
1398 bool ratio_cut_partition::move_vertex(const graph &G, node& moved_node)
1399 {
1400     bool consA_ok = false, consB_ok = false;
1401     node cons_nodeA, cons_nodeB;
1402
1403     if (!bucketA_empty)
1404     {
1405     cons_nodeA =
1406         compute_highest_ratio_node(bucketA[range_up(max_gainA)]);
1407     consA_ok = true;
1408     if (node_weight_on_sideA - node_weight[cons_nodeA] == 0)
1409     {
1410         node temp_node = cons_nodeA;
1411         bucketA[range_up(gain_value[cons_nodeA])].
1412         erase(position_in_bucket[cons_nodeA]);
1413         update_max_gain(A);
1414         if (!bucketA_empty) // nodes with smaller weight available?
1415         {
1416         cons_nodeA = compute_highest_ratio_node
1417             (bucketA[range_up(max_gainA)]);
1418         }
1419         else
1420         {
1421         consA_ok = false;
1422         }
1423         bucketA_empty = false;
1424         bucketA[range_up(gain_value[temp_node])].push_front(temp_node);
1425         position_in_bucket[temp_node] =
1426         bucketA[range_up(gain_value[temp_node])].begin();
1427         max_gainA = gain_value[temp_node];
1428     }
1429     }
1430     if (!bucketB_empty)
1431     {
1432     cons_nodeB =
1433         compute_highest_ratio_node(bucketB[range_up(max_gainB)]);
1434     consB_ok = true;
1435     if (node_weight_on_sideB - node_weight[cons_nodeB] == 0)
1436     {
1437         node temp_node = cons_nodeB;
1438         bucketB[range_up(gain_value[cons_nodeB])].
1439         erase(position_in_bucket[cons_nodeB]);
1440         update_max_gain(B);
1441         if (!bucketB_empty) // nodes with smaller weight available?
1442         {
1443         cons_nodeB = compute_highest_ratio_node
1444             (bucketB[range_up(max_gainB)]);
1445         }
1446         else
1447         {
1448         consB_ok = false;
1449         }
1450         bucketB_empty = false;
1451         bucketB[range_up(gain_value[temp_node])].push_front(temp_node);
1452         position_in_bucket[temp_node] =
1453         bucketB[range_up(gain_value[temp_node])].begin();
1454         max_gainB = gain_value[temp_node];
1455     }
1456     }
1457
1458     if (consA_ok && consB_ok)
1459     {
1460     double ratio_A2B = ratio_of_node_A2B(cons_nodeA);
1461     double ratio_B2A = ratio_of_node_B2A(cons_nodeB);
1462     if (ratio_A2B > ratio_B2A)
1463     {
1464         moved_node = cons_nodeA;
1465         bucketA[range_up(max_gainA)].
1466         erase(position_in_bucket[cons_nodeA]);
1467         update_data_structure_A2B(cons_nodeA, false);
1468     }
1469     else    // ratio_A2B <= ratio_B2A
1470     {
1471         moved_node = cons_nodeB;
1472         bucketB[range_up(max_gainB)].
1473         erase(position_in_bucket[cons_nodeB]);
1474         update_data_structure_B2A(cons_nodeB, false);
1475     }
1476     }
1477     else if (consA_ok)
1478     {
1479     moved_node = cons_nodeA;
1480     bucketA[range_up(max_gainA)].erase(position_in_bucket[cons_nodeA]);
1481     update_data_structure_A2B(cons_nodeA, false);
1482     }
1483     else if (consB_ok)
1484     {
1485     moved_node = cons_nodeB;
1486     bucketB[range_up(max_gainB)].erase(position_in_bucket[cons_nodeB]);
1487     update_data_structure_B2A(cons_nodeB, false);
1488     }
1489     else
1490     {
1491     return false;   // no more vertices can be moved
1492     }
1493     update_max_gain(A);
1494     update_max_gain(B);
1495     return true;
1496 }
1497
1498
1499 void ratio_cut_partition::compute_cut_edges(const graph& G)
1500 {
1501     cut_edges.clear();
1502     graph::edge_iterator edge_it = G.edges_begin();
1503     graph::edge_iterator edges_end = G.edges_end();
1504     while (edge_it != edges_end)
1505     {
1506     if (side[(*edge_it).source()] != side[(*edge_it).target()])
1507     {
1508         cut_edges.push_back(*edge_it);
1509     }
1510     ++edge_it;
1511     }
1512 }
1513
1514
1515 void ratio_cut_partition::compute_nodesAB(const graph& G)
1516 {
1517     nodesA.clear();
1518     nodesB.clear();
1519     graph::node_iterator node_it = G.nodes_begin();
1520     graph::node_iterator nodes_end = G.nodes_end();
1521     while (node_it != nodes_end)
1522     {
1523     if (side[*node_it] == A)
1524     {
1525         nodesA.push_back(*node_it);
1526     }
1527     else    // side[*node_it] == B
1528     {
1529         nodesB.push_back(*node_it);
1530     }
1531     ++node_it;
1532     }
1533 }
1534
1535
1536 #ifdef _DEBUG
1537 void ratio_cut_partition::print_bucketA()
1538 {
1539     GTL_debug::init_debug();
1540     GTL_debug::os() << endl << "bucketA:" << endl;
1541     for (int i = 0; i <= 2 * max_vertex_degree * max_edge_weight; i++)
1542     {
1543     GTL_debug::os() << range_down(i) << ": ";
1544     list<node>::iterator node_it = bucketA[i].begin();
1545     list<node>::iterator nodes_end = bucketA[i].end();
1546     while (node_it != nodes_end)
1547     {
1548         GTL_debug::os() << *node_it << "  ";
1549         ++node_it;
1550     }
1551     GTL_debug::os() << endl;
1552     }
1553     GTL_debug::os() << endl;
1554     GTL_debug::close_debug();
1555 }
1556
1557
1558 void ratio_cut_partition::print_bucketB()
1559 {
1560     GTL_debug::init_debug();
1561     GTL_debug::os() << endl << "bucketB:" << endl;
1562     for (int i = 0; i <= 2 * max_vertex_degree * max_edge_weight; i++)
1563     {
1564     GTL_debug::os() << range_down(i) << ": ";
1565     list<node>::iterator node_it = bucketB[i].begin();
1566     list<node>::iterator nodes_end = bucketB[i].end();
1567     while (node_it != nodes_end)
1568     {
1569         GTL_debug::os() << *node_it << "  ";
1570         ++node_it;
1571     }
1572     GTL_debug::os() << endl;
1573     }
1574     GTL_debug::os() << endl;
1575     GTL_debug::close_debug();
1576 }
1577 #endif  // _DEBUG
1578
1579
1580 __GTL_END_NAMESPACE
1581
1582 //--------------------------------------------------------------------------
1583 //   end of file
1584 //--------------------------------------------------------------------------