gtl/src/fm_partition.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //  fm_partition.cpp
0005 //
0006 //==========================================================================
0007 // $Id: fm_partition.cpp,v 1.8 2001/11/07 13:58:10 pick Exp $
0008
0009 #include <GTL/debug.h>
0010 #include <GTL/fm_partition.h>
0011
0012 #include <iostream>
0013
0014 #include <cstdlib>
0015 #include <cassert>
0016 #include <cmath>
0017 #include <ctime>
0018
0019 #ifdef __GTL_MSVCC
0020 #   ifdef _DEBUG
0021 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0022 #   error SEARCH NOT ENABLED
0023 #   endif
0024 #   define new DEBUG_NEW
0025 #   undef THIS_FILE
0026     static char THIS_FILE[] = __FILE__;
0027 #   endif   // _DEBUG
0028 #endif  // __GTL_MSVCC
0029
0030 __GTL_BEGIN_NAMESPACE
0031
0032
0033 const fm_partition::side_type fm_partition::A = 0;
0034 const fm_partition::side_type fm_partition::B = 1;
0035
0036
0037 const fm_partition::fix_type fm_partition::FIXA = 0;
0038 const fm_partition::fix_type fm_partition::FIXB = 1;
0039 const fm_partition::fix_type fm_partition::UNFIXED = 2;
0040
0041
0042 fm_partition::fm_partition()
0043 {
0044     set_vars_executed = false;
0045     enable_cut_edges_storing = false;
0046     enable_nodesAB_storing = false;
0047 }
0048
0049
0050 fm_partition::~fm_partition()
0051 {
0052 }
0053
0054
0055 void fm_partition::set_vars(const graph& G,
0056     const node_map<int>& node_weight, const edge_map<int>& edge_weight)
0057 {
0058     this->node_weight = node_weight;
0059     this->edge_weight = edge_weight;
0060     set_vars_executed = true;
0061     provided_initial_part = false;
0062     this->fixed.init(G, UNFIXED);
0063     provided_fix = false;
0064     side.init(G);
0065 }
0066
0067
0068 void fm_partition::set_vars(const graph& G,
0069     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0070     const node_map<side_type>& init_side)
0071 {
0072     this->node_weight = node_weight;
0073     this->edge_weight = edge_weight;
0074     this->side = init_side;
0075     set_vars_executed = true;
0076     provided_initial_part = true;
0077     this->fixed.init(G, UNFIXED);
0078     provided_fix = false;
0079 }
0080
0081
0082 void fm_partition::set_vars(const graph& G,
0083     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0084     const node_map<fix_type>& fixed)
0085 {
0086     this->node_weight = node_weight;
0087     this->edge_weight = edge_weight;
0088     set_vars_executed = true;
0089     provided_initial_part = false;
0090     this->fixed = fixed;
0091     provided_fix = true;
0092     side.init(G);
0093 }
0094
0095
0096 void fm_partition::set_vars(const graph& G,
0097     const node_map<int>& node_weight, const edge_map<int>& edge_weight,
0098     const node_map<side_type>& init_side,
0099     const node_map<fix_type>& fixed)
0100 {
0101     this->node_weight = node_weight;
0102     this->edge_weight = edge_weight;
0103     this->side = init_side;
0104     set_vars_executed = true;
0105     provided_initial_part = true;
0106     this->fixed = fixed;
0107     provided_fix = true;
0108 }
0109
0110
0111 void fm_partition::store_cut_edges(const bool set)
0112 {
0113     enable_cut_edges_storing = set;
0114 }
0115
0116
0117 void fm_partition::store_nodesAB(const bool set)
0118 {
0119     enable_nodesAB_storing = set;
0120 }
0121
0122
0123 int fm_partition::check(graph& G)
0124 {
0125     if ((!set_vars_executed) || (!G.is_undirected()))
0126     {
0127     return GTL_ERROR;
0128     }
0129
0130     graph::edge_iterator edge_it = G.edges_begin();
0131     graph::edge_iterator edges_end = G.edges_end();
0132     while (edge_it != edges_end)
0133     {
0134     if (edge_weight[*edge_it] < 0)
0135     {
0136         return GTL_ERROR;
0137     }
0138     ++edge_it;
0139     }
0140     graph::node_iterator node_it = G.nodes_begin();
0141     graph::node_iterator nodes_end = G.nodes_end();
0142     while (node_it != nodes_end)
0143     {
0144     if (node_weight[*node_it] < 0)
0145     {
0146         return GTL_ERROR;
0147     }
0148     ++node_it;
0149     }
0150
0151     return GTL_OK;
0152 }
0153
0154
0155 int fm_partition::run(graph& G)
0156 {
0157     init_variables(G);
0158     if ((provided_initial_part) && (provided_fix))
0159     {
0160     divide_up(G);
0161     }
0162     if (!provided_initial_part)
0163     {
0164     create_initial_bipart(G);
0165     }
0166
0167     hide_self_loops(G);
0168     compute_max_vertex_degree(G);
0169
0170     pass_manager(G);
0171
0172     if (enable_cut_edges_storing)
0173     {
0174     compute_cut_edges(G);
0175     }
0176     if (enable_nodesAB_storing)
0177     {
0178     compute_nodesAB(G);
0179     }
0180     G.restore_graph();
0181
0182     return GTL_OK;
0183 }
0184
0185
0186 int fm_partition::get_cutsize()
0187 {
0188     return cur_cutsize;
0189 }
0190
0191
0192 int fm_partition::get_needed_passes()
0193 {
0194     return no_passes;
0195 }
0196
0197
0198 fm_partition::side_type fm_partition::get_side_of_node(const node& n) const
0199 {
0200     return side[n];
0201 }
0202
0203
0204 fm_partition::side_type fm_partition::operator [](const node& n) const
0205 {
0206     return side[n];
0207 }
0208
0209
0210 int fm_partition::get_weight_on_sideA(const graph& G) const
0211 {
0212     int nwA = 0;
0213     graph::node_iterator node_it = G.nodes_begin();
0214     graph::node_iterator nodes_end = G.nodes_end();
0215     while (node_it != nodes_end)
0216     {
0217     if (side[*node_it] == A)
0218     {
0219         nwA += node_weight[*node_it];
0220     }
0221     ++node_it;
0222     }
0223     return nwA;
0224 }
0225
0226
0227 int fm_partition::get_weight_on_sideB(const graph& G) const
0228 {
0229     int nwB = 0;
0230     graph::node_iterator node_it = G.nodes_begin();
0231     graph::node_iterator nodes_end = G.nodes_end();
0232     while (node_it != nodes_end)
0233     {
0234     if (side[*node_it] == B)
0235     {
0236         nwB += node_weight[*node_it];
0237     }
0238     ++node_it;
0239     }
0240     return nwB;
0241 }
0242
0243
0244 fm_partition::cut_edges_iterator fm_partition::cut_edges_begin() const
0245 {
0246     return cut_edges.begin();
0247 }
0248
0249
0250 fm_partition::cut_edges_iterator fm_partition::cut_edges_end() const
0251 {
0252     return cut_edges.end();
0253 }
0254
0255
0256 fm_partition::nodes_of_one_side_iterator
0257 fm_partition::nodes_of_sideA_begin() const
0258 {
0259     return nodesA.begin();
0260 }
0261
0262
0263 fm_partition::nodes_of_one_side_iterator
0264 fm_partition::nodes_of_sideA_end() const
0265 {
0266     return nodesA.end();
0267 }
0268
0269
0270 fm_partition::nodes_of_one_side_iterator
0271 fm_partition::nodes_of_sideB_begin() const
0272 {
0273     return nodesB.begin();
0274 }
0275
0276
0277 fm_partition::nodes_of_one_side_iterator
0278 fm_partition::nodes_of_sideB_end() const
0279 {
0280     return nodesB.end();
0281 }
0282
0283
0284 void fm_partition::reset()
0285 {
0286     set_vars_executed = false;
0287     cut_edges.clear();
0288     nodesA.clear();
0289     nodesB.clear();
0290 }
0291
0292
0293 void fm_partition::divide_up(const graph& G)
0294 {
0295     graph::node_iterator node_it = G.nodes_begin();
0296     graph::node_iterator nodes_end = G.nodes_end();
0297     while (node_it != nodes_end)
0298     {
0299     if (fixed[*node_it] == FIXA)
0300     {
0301         side[*node_it] = A;
0302     }
0303     else if (fixed[*node_it] == FIXB)
0304     {
0305         side[*node_it] = B;
0306     }
0307     ++node_it;
0308     }
0309 }
0310
0311
0312 void fm_partition::hide_self_loops(graph& G)
0313 {
0314     graph::edge_iterator temp_it;
0315     graph::edge_iterator edge_it = G.edges_begin();
0316     graph::edge_iterator edges_end = G.edges_end();
0317     while (edge_it != edges_end)
0318     {
0319     if ((*edge_it).source() == (*edge_it).target())
0320     {
0321         temp_it = edge_it;
0322         ++edge_it;
0323         G.hide_edge(*temp_it);
0324     }
0325     else
0326     {
0327         ++edge_it;
0328     }
0329     }
0330 }
0331
0332
0333 void fm_partition::init_variables(const graph& G)
0334 {
0335     bool first_edge_found = true;
0336     bool first_node_found = true;
0337     max_edge_weight = 0;
0338     max_node_weight = 0;
0339     graph::edge_iterator edge_it = G.edges_begin();
0340     graph::edge_iterator edges_end = G.edges_end();
0341     while (edge_it != edges_end)
0342     {
0343     if (first_edge_found)
0344     {
0345         max_edge_weight = edge_weight[*edge_it];
0346         first_edge_found = false;
0347     }
0348     else if (edge_weight[*edge_it] > max_edge_weight)
0349     {
0350         max_edge_weight = edge_weight[*edge_it];
0351     }
0352     ++edge_it;
0353     }
0354     graph::node_iterator node_it = G.nodes_begin();
0355     graph::node_iterator nodes_end = G.nodes_end();
0356     total_node_weight = 0;
0357     while (node_it != nodes_end)
0358     {
0359     total_node_weight += node_weight[*node_it];
0360     if (first_node_found)
0361     {
0362         max_node_weight = node_weight[*node_it];
0363         first_node_found = false;
0364     }
0365     else if (node_weight[*node_it] > max_node_weight)
0366     {
0367         max_node_weight = node_weight[*node_it];
0368     }
0369     ++node_it;
0370     }
0371 }
0372
0373
0374 void fm_partition::create_initial_bipart(const graph& G)
0375 {
0376     int i = 0;  // counter
0377     int no_nodes = G.number_of_nodes();
0378     node_weight_on_sideA = 0;
0379     node_weight_on_sideB = 0;
0380
0381     graph::node_iterator node_it = G.nodes_begin();
0382     graph::node_iterator nodes_end = G.nodes_end();
0383     vector<graph::node_iterator> node_vector(G.number_of_nodes());
0384     while (node_it != nodes_end)
0385     {
0386     node_vector[i] = node_it;
0387     if (fixed[*node_it] == FIXA)
0388     {
0389         side[*node_it] = A;
0390         node_weight_on_sideA += node_weight[*node_it];
0391     }
0392     else if (fixed[*node_it] == FIXB)
0393     {
0394         side[*node_it] = B;
0395         node_weight_on_sideB += node_weight[*node_it];
0396     }
0397     else    // fixed[*node_it] == UNFIXED
0398     {
0399         node_weight_on_sideB += node_weight[*node_it];
0400         side[*node_it] = B;
0401     }
0402     ++i;
0403     ++node_it;
0404     }
0405     shuffle_vector(no_nodes, node_vector);
0406
0407     // compute best balance
0408     int best_bal = node_weight_on_sideA * node_weight_on_sideB;
0409     int best_pos = -1;
0410     for (i = 0; i < no_nodes; i++)
0411     {
0412     if (fixed[*node_vector[i]] == UNFIXED)
0413     {
0414         node_weight_on_sideA += node_weight[*node_vector[i]];
0415         node_weight_on_sideB -= node_weight[*node_vector[i]];
0416         if (node_weight_on_sideA * node_weight_on_sideB > best_bal)
0417         {
0418         best_bal = node_weight_on_sideA * node_weight_on_sideB;
0419         best_pos = i;
0420         }
0421     }
0422     }
0423
0424     // create partition with best balance
0425     for (i = 0; i <= best_pos; i++)
0426     {
0427     if (fixed[*node_vector[i]] == UNFIXED)
0428     {
0429         side[*node_vector[i]] = A;
0430     }
0431     }
0432 }
0433
0434
0435 void fm_partition::shuffle_vector(const int vector_size,
0436     vector<graph::node_iterator>& node_vector)
0437 {
0438     srand((unsigned)time(NULL));
0439     rand(); // necessary, otherwise the next rand() returns always 0 ?-)
0440     for (int i = 1; i <= vector_size; i++)
0441     {
0442     int pos_1 = (int)floor((((double)rand() / (double)RAND_MAX) *
0443         (double)(vector_size - 1)) + 0.5);
0444     int pos_2 = (int)floor((((double)rand() / (double)RAND_MAX) *
0445         (double)(vector_size - 1)) + 0.5);
0446     graph::node_iterator temp_it;
0447     temp_it = node_vector[pos_1];
0448     node_vector[pos_1] = node_vector[pos_2];
0449     node_vector[pos_2] = temp_it;
0450     }
0451 }
0452
0453
0454 void fm_partition::compute_max_vertex_degree(const graph& G)
0455 {
0456     max_vertex_degree = 0;
0457     graph::node_iterator node_it = G.nodes_begin();
0458     graph::node_iterator nodes_end = G.nodes_end();
0459     while (node_it != nodes_end)
0460     {
0461     if (max_vertex_degree < (*node_it).degree())
0462     {
0463         max_vertex_degree = (*node_it).degree();
0464     }
0465     ++node_it;
0466     }
0467 }
0468
0469
0470 void fm_partition::pass_manager(const graph& G)
0471 {
0472     // final pass which doesn't improve cur_cutsize is not counted
0473     no_passes = -1;
0474     int best_cutsize = -1;  // = -1 to avoid warning
0475     node_map<side_type> best_side(G);
0476     bool improved_cutsize;
0477
0478     do
0479     {
0480     init_data_structure(G);
0481     if (no_passes == -1)
0482     {
0483         best_cutsize = cur_cutsize;
0484         copy_side_node_map(G, best_side, side);
0485     }
0486     move_manager(G);
0487     clean_pass(G);
0488     improved_cutsize = false;
0489     if (best_cutsize > cur_cutsize)
0490     {
0491         best_cutsize = cur_cutsize;
0492         copy_side_node_map(G, best_side, side);
0493         improved_cutsize = true;
0494     }
0495     ++no_passes;
0496     }
0497     while (improved_cutsize);
0498     cur_cutsize = best_cutsize;
0499     copy_side_node_map(G, side, best_side);
0500 }
0501
0502
0503 void fm_partition::copy_side_node_map(const graph& G,
0504     node_map<side_type>& dest, const node_map<side_type> source) const
0505 {
0506     graph::node_iterator node_it = G.nodes_begin();
0507     graph::node_iterator nodes_end = G.nodes_end();
0508     while (node_it != nodes_end)
0509     {
0510     dest[*node_it] = source[*node_it];
0511     ++node_it;
0512     }
0513 }
0514
0515
0516 void fm_partition::init_data_structure(const graph& G)
0517 {
0518     aside.init(G);
0519     bside.init(G);
0520     unlockedA.init(G);
0521     unlockedB.init(G);
0522     cur_cutsize = 0;
0523     graph::edge_iterator edge_it = G.edges_begin();
0524     graph::edge_iterator edges_end = G.edges_end();
0525     while (edge_it != edges_end)
0526     {
0527     if ((side[(*edge_it).source()] == A) &&
0528         (side[(*edge_it).target()] == A))
0529     {
0530         aside[*edge_it] = 2;
0531         bside[*edge_it] = 0;
0532         unlockedA[*edge_it].push_back((*edge_it).source());
0533         unlockedA[*edge_it].push_back((*edge_it).target());
0534     }
0535     else if ((side[(*edge_it).source()] == B) &&
0536         (side[(*edge_it).target()] == B))
0537     {
0538         aside[*edge_it] = 0;
0539         bside[*edge_it] = 2;
0540         unlockedB[*edge_it].push_back((*edge_it).source());
0541         unlockedB[*edge_it].push_back((*edge_it).target());
0542     }
0543     else if ((side[(*edge_it).source()] == A) &&
0544         (side[(*edge_it).target()] == B))
0545     {
0546         aside[*edge_it] = 1;
0547         bside[*edge_it] = 1;
0548         cur_cutsize += edge_weight[*edge_it];
0549         unlockedA[*edge_it].push_back((*edge_it).source());
0550         unlockedB[*edge_it].push_back((*edge_it).target());
0551     }
0552     else if ((side[(*edge_it).source()] == B) &&
0553         (side[(*edge_it).target()] == A))
0554     {
0555         aside[*edge_it] = 1;
0556         bside[*edge_it] = 1;
0557         cur_cutsize += edge_weight[*edge_it];
0558         unlockedA[*edge_it].push_back((*edge_it).target());
0559         unlockedB[*edge_it].push_back((*edge_it).source());
0560     }
0561     ++edge_it;
0562     }
0563
0564     bucketA.resize(2 * max_vertex_degree * max_edge_weight + 1);
0565     bucketB.resize(2 * max_vertex_degree * max_edge_weight + 1);
0566
0567     init_filling_buckets(G);
0568 }
0569
0570
0571 void fm_partition::init_filling_buckets(const graph &G)
0572 {
0573     node_weight_on_sideA = 0;
0574     node_weight_on_sideB = 0;
0575     bucketA_empty = true;
0576     bucketB_empty = true;
0577     bool first_A_node = true;
0578     bool first_B_node = true;
0579     int index;
0580     // position_in_bucket.init(G);
0581     gain_value.init(G);
0582
0583     graph::node_iterator node_it = G.nodes_begin();
0584     graph::node_iterator nodes_end = G.nodes_end();
0585     while (node_it != nodes_end)
0586     {
0587     if (side[*node_it] == A)
0588     {
0589         node_weight_on_sideA += node_weight[*node_it];
0590         gain_value[*node_it] = inital_gain_of_node_on_sideA(*node_it);
0591         if (fixed[*node_it] == UNFIXED)
0592         {
0593         if (first_A_node)
0594         {
0595             bucketA_empty = false;
0596             max_gainA = gain_value[*node_it];
0597             first_A_node = false;
0598         }
0599         else
0600         {
0601             if (max_gainA < gain_value[*node_it])
0602             {
0603             max_gainA = gain_value[*node_it];
0604             }
0605         }
0606         index = range_up(gain_value[*node_it]);
0607         position_in_bucket[*node_it] = bucketA[index].insert(
0608             bucketA[index].end(), *node_it);
0609         }
0610     }
0611     else    // side[*node_it] == B
0612     {
0613         node_weight_on_sideB += node_weight[*node_it];
0614         gain_value[*node_it] = inital_gain_of_node_on_sideB(*node_it);
0615         if (fixed[*node_it] == UNFIXED)
0616         {
0617         if (first_B_node)
0618         {
0619             bucketB_empty = false;
0620             max_gainB = gain_value[*node_it];
0621             first_B_node = false;
0622         }
0623         else
0624         {
0625             if (max_gainB < gain_value[*node_it])
0626             {
0627             max_gainB = gain_value[*node_it];
0628             }
0629         }
0630         index = range_up(gain_value[*node_it]);
0631         position_in_bucket[*node_it] = bucketB[index].insert(
0632             bucketB[index].end(), *node_it);
0633         }
0634     }
0635     ++node_it;
0636     }
0637 }
0638
0639
0640 int fm_partition::inital_gain_of_node_on_sideA(const node cur_node)
0641 {
0642     int node_gain = 0;
0643     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0644     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0645     while (adj_edge_it != adj_edges_end)
0646     {
0647     if (aside[*adj_edge_it] == 1)
0648     {
0649         node_gain += edge_weight[*adj_edge_it];
0650     }
0651     if (bside[*adj_edge_it] == 0)
0652     {
0653         node_gain -= edge_weight[*adj_edge_it];
0654     }
0655     ++adj_edge_it;
0656     }
0657     return node_gain;
0658 }
0659
0660
0661 int fm_partition::inital_gain_of_node_on_sideB(const node cur_node)
0662 {
0663     int node_gain = 0;
0664     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0665     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0666     while (adj_edge_it != adj_edges_end)
0667     {
0668     if (bside[*adj_edge_it] == 1)
0669     {
0670         node_gain += edge_weight[*adj_edge_it];
0671     }
0672     if (aside[*adj_edge_it] == 0)
0673     {
0674         node_gain -= edge_weight[*adj_edge_it];
0675     }
0676     ++adj_edge_it;
0677     }
0678     return node_gain;
0679 }
0680
0681
0682 void fm_partition::move_manager(const graph& G)
0683 {
0684     int step_number = 0;
0685     int best_tentative_move = 0;
0686     int best_bal = node_weight_on_sideA * node_weight_on_sideB;
0687     vector<node> tentative_moves(G.number_of_nodes() + 1);
0688     vector<int> tentative_cutsize(G.number_of_nodes() + 1);
0689     node moved_node;
0690     tentative_cutsize[0] = cur_cutsize;
0691
0692     while (move_vertex(G, moved_node))
0693     {
0694     ++step_number;
0695     tentative_cutsize[step_number] = cur_cutsize;
0696     tentative_moves[step_number] = moved_node;
0697     if (tentative_cutsize[best_tentative_move] > cur_cutsize)
0698     {
0699         best_tentative_move = step_number;
0700         best_bal = node_weight_on_sideA * node_weight_on_sideB;
0701     }
0702     else if (tentative_cutsize[best_tentative_move] == cur_cutsize)
0703     {
0704         if (node_weight_on_sideA * node_weight_on_sideB > best_bal)
0705         {
0706         best_tentative_move = step_number;
0707         best_bal = node_weight_on_sideA * node_weight_on_sideB;
0708         }
0709     }
0710     }
0711
0712     for (int i = 1; i <= best_tentative_move; i++)
0713     {
0714     if (side[tentative_moves[i]] == A)
0715     {
0716         side[tentative_moves[i]] = B;
0717     }
0718     else    // side[tentative_moves[i]] == B
0719     {
0720         side[tentative_moves[i]] = A;
0721     }
0722     }
0723     cur_cutsize = tentative_cutsize[best_tentative_move];
0724 }
0725
0726
0727 bool fm_partition::move_vertex(const graph& G, node& moved_node)
0728 {
0729     node cons_nodeA;
0730     if (!bucketA_empty)
0731     {
0732     cons_nodeA = bucketA[range_up(max_gainA)].back();
0733     }
0734     node cons_nodeB;
0735     if (!bucketB_empty)
0736     {
0737     cons_nodeB = bucketB[range_up(max_gainB)].back();
0738     }
0739     if ((!bucketA_empty) && (!bucketB_empty) &&
0740     (balance_holds(G, cons_nodeA)) && (balance_holds(G, cons_nodeB)))
0741     {
0742     if (gain_value[cons_nodeA] > gain_value[cons_nodeB])
0743     {
0744         update_data_structure_A2B(cons_nodeA);
0745         moved_node = cons_nodeA;
0746     }
0747     else if (gain_value[cons_nodeB] > gain_value[cons_nodeA])
0748     {
0749         update_data_structure_B2A(cons_nodeB);
0750         moved_node = cons_nodeB;
0751     }
0752     else    // gain_value[cons_nodeB] == gain_value[cons_nodeA]
0753     {
0754         int bal_diff_A2B = abs(node_weight_on_sideA - 2 *
0755         node_weight[cons_nodeA] - node_weight_on_sideB);
0756         int bal_diff_B2A = abs(node_weight_on_sideB - 2 *
0757         node_weight[cons_nodeB] - node_weight_on_sideA);
0758         if (bal_diff_A2B < bal_diff_B2A)
0759         {
0760         update_data_structure_A2B(cons_nodeA);
0761         moved_node = cons_nodeA;
0762         }
0763         else if (bal_diff_B2A < bal_diff_A2B)
0764         {
0765         update_data_structure_B2A(cons_nodeB);
0766         moved_node = cons_nodeB;
0767         }
0768         else    // break remaining ties as desired [FidMat82]
0769         {
0770         update_data_structure_A2B(cons_nodeA);
0771         moved_node = cons_nodeA;
0772         }
0773     }
0774     }
0775     else if ((!bucketA_empty) && (balance_holds(G, cons_nodeA)))
0776     {
0777     update_data_structure_A2B(cons_nodeA);
0778     moved_node = cons_nodeA;
0779     }
0780     else if ((!bucketB_empty) && (balance_holds(G, cons_nodeB)))
0781     {
0782     update_data_structure_B2A(cons_nodeB);
0783     moved_node = cons_nodeB;
0784     }
0785     else
0786     {
0787     return false;   // no more vertices can be moved
0788     }
0789     update_max_gain(A);
0790     update_max_gain(B);
0791     return true;
0792 }
0793
0794
0795 bool fm_partition::balance_holds(const graph& G, const node cur_node)
0796 {
0797     if (side[cur_node] == A)
0798     {
0799     if ((double)node_weight_on_sideB + (double)node_weight[cur_node]
0800         <= ((double)total_node_weight / 2.0) + (double)max_node_weight)
0801     {
0802         return true;
0803     }
0804     }
0805     else    // side[cur_node] == B
0806     {
0807     if ((double)node_weight_on_sideA + (double)node_weight[cur_node]
0808         <= ((double)total_node_weight / 2.0) + (double)max_node_weight)
0809     {
0810         return true;
0811     }
0812     }
0813     return false;
0814 }
0815
0816
0817 void fm_partition::update_data_structure_A2B(const node cur_node)
0818 {
0819     bucketA[range_up(max_gainA)].pop_back();
0820     node_weight_on_sideA -= node_weight[cur_node];
0821     node_weight_on_sideB += node_weight[cur_node];
0822     cur_cutsize -= gain_value[cur_node];
0823
0824     // updating gain values
0825     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0826     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0827     while (adj_edge_it != adj_edges_end)
0828     {
0829     // delete cur_node from side A
0830     unlockedA[*adj_edge_it].remove(cur_node);
0831     --aside[*adj_edge_it];
0832     if (aside[*adj_edge_it] == 0)
0833     {
0834         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
0835         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
0836         while (node_it != nodes_end)
0837         {
0838         update_bucketB(*node_it, gain_value[*node_it],
0839             gain_value[*node_it] - edge_weight[*adj_edge_it]);
0840         gain_value[*node_it] -= edge_weight[*adj_edge_it];
0841         ++node_it;
0842         }
0843     }
0844     else if (aside[*adj_edge_it] == 1)
0845     {
0846         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
0847         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
0848         while (node_it != nodes_end)
0849         {
0850         update_bucketA(*node_it, gain_value[*node_it],
0851             gain_value[*node_it] + edge_weight[*adj_edge_it]);
0852         gain_value[*node_it] += edge_weight[*adj_edge_it];
0853         ++node_it;
0854         }
0855     }
0856     // add cur_node to side B
0857     ++bside[*adj_edge_it];
0858     if (bside[*adj_edge_it] == 1)
0859     {
0860         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
0861         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
0862         while (node_it != nodes_end)
0863         {
0864         update_bucketA(*node_it, gain_value[*node_it],
0865             gain_value[*node_it] + edge_weight[*adj_edge_it]);
0866         gain_value[*node_it] += edge_weight[*adj_edge_it];
0867         ++node_it;
0868         }
0869     }
0870     else if (bside[*adj_edge_it] == 2)
0871     {
0872         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
0873         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
0874         while (node_it != nodes_end)
0875         {
0876         update_bucketB(*node_it, gain_value[*node_it],
0877             gain_value[*node_it] - edge_weight[*adj_edge_it]);
0878         gain_value[*node_it] -= edge_weight[*adj_edge_it];
0879         ++node_it;
0880         }
0881     }
0882     ++adj_edge_it;
0883     }
0884 }
0885
0886
0887 void fm_partition::update_data_structure_B2A(const node cur_node)
0888 {
0889     bucketB[range_up(max_gainB)].pop_back();
0890     node_weight_on_sideA += node_weight[cur_node];
0891     node_weight_on_sideB -= node_weight[cur_node];
0892     cur_cutsize -= gain_value[cur_node];
0893
0894     // updating gain values
0895     node::adj_edges_iterator adj_edge_it = cur_node.adj_edges_begin();
0896     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0897     while (adj_edge_it != adj_edges_end)
0898     {
0899     // delete cur_node from side B
0900     unlockedB[*adj_edge_it].remove(cur_node);
0901     bside[*adj_edge_it] -= 1;
0902     if (bside[*adj_edge_it] == 0)
0903     {
0904         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
0905         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
0906         while (node_it != nodes_end)
0907         {
0908         update_bucketA(*node_it, gain_value[*node_it],
0909             gain_value[*node_it] - edge_weight[*adj_edge_it]);
0910         gain_value[*node_it] -= edge_weight[*adj_edge_it];
0911         ++node_it;
0912         }
0913     }
0914     else if (bside[*adj_edge_it] == 1)
0915     {
0916         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
0917         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
0918         while (node_it != nodes_end)
0919         {
0920         update_bucketB(*node_it, gain_value[*node_it],
0921             gain_value[*node_it] + edge_weight[*adj_edge_it]);
0922         gain_value[*node_it] += edge_weight[*adj_edge_it];
0923         ++node_it;
0924         }
0925     }
0926     // add cur_node to side A
0927     aside[*adj_edge_it] += 1;
0928     if (aside[*adj_edge_it] == 1)
0929     {
0930         list<node>::iterator node_it = unlockedB[*adj_edge_it].begin();
0931         list<node>::iterator nodes_end = unlockedB[*adj_edge_it].end();
0932         while (node_it != nodes_end)
0933         {
0934         update_bucketB(*node_it, gain_value[*node_it],
0935             gain_value[*node_it] + edge_weight[*adj_edge_it]);
0936         gain_value[*node_it] += edge_weight[*adj_edge_it];
0937         ++node_it;
0938         }
0939     }
0940     else if (aside[*adj_edge_it] == 2)
0941     {
0942         list<node>::iterator node_it = unlockedA[*adj_edge_it].begin();
0943         list<node>::iterator nodes_end = unlockedA[*adj_edge_it].end();
0944         while (node_it != nodes_end)
0945         {
0946         update_bucketA(*node_it, gain_value[*node_it],
0947             gain_value[*node_it] - edge_weight[*adj_edge_it]);
0948         gain_value[*node_it] -= edge_weight[*adj_edge_it];
0949         ++node_it;
0950         }
0951     }
0952     ++adj_edge_it;
0953     }
0954 }
0955
0956
0957 void fm_partition::update_bucketA(const node cur_node, const int old_gain,
0958     const int new_gain)
0959 {
0960     if (fixed[cur_node] != UNFIXED)
0961     {
0962     return; // fixed nodes need no update
0963     }
0964
0965     bucketA[range_up(old_gain)].erase(position_in_bucket[cur_node]);
0966     position_in_bucket[cur_node] = bucketA[range_up(new_gain)].insert(
0967     bucketA[range_up(new_gain)].end(), cur_node);
0968
0969     if (max_gainA < new_gain)
0970     {
0971     max_gainA = new_gain;
0972     }
0973 }
0974
0975
0976 void fm_partition::update_bucketB(const node cur_node, const int old_gain,
0977     const int new_gain)
0978 {
0979     if (fixed[cur_node] != UNFIXED)
0980     {
0981     return; // fixed nodes need no update
0982     }
0983
0984     bucketB[range_up(old_gain)].erase(position_in_bucket[cur_node]);
0985     position_in_bucket[cur_node] = bucketB[range_up(new_gain)].insert(
0986     bucketB[range_up(new_gain)].end(), cur_node);
0987
0988     if (max_gainB < new_gain)
0989     {
0990     max_gainB = new_gain;
0991     }
0992 }
0993
0994
0995 void fm_partition::update_max_gain(const side_type side)
0996 {
0997     if ((side == A) && (!bucketA_empty))
0998     {
0999     while (bucketA[range_up(max_gainA)].empty())
1000     {
1001         --max_gainA;
1002         if (range_up(max_gainA) < 0)
1003         {
1004         bucketA_empty = true;
1005         return;
1006         }
1007     }
1008     bucketA_empty = false;
1009     }
1010     if ((side == B) && (!bucketB_empty))
1011     {
1012     while (bucketB[range_up(max_gainB)].empty())
1013     {
1014         --max_gainB;
1015         if (range_up(max_gainB) < 0)
1016         {
1017         bucketB_empty = true;
1018         return;
1019         }
1020     }
1021     bucketB_empty = false;
1022     }
1023 }
1024
1025
1026 inline int fm_partition::range_up(const int gain_value) const
1027 {
1028     return gain_value + (max_vertex_degree * max_edge_weight);
1029 }
1030
1031
1032 inline int fm_partition::range_down(const int index) const
1033 {
1034     return index - (max_vertex_degree * max_edge_weight);
1035 }
1036
1037
1038 void fm_partition::clean_pass(const graph& G)
1039 {
1040     // clean unlocked* lists
1041     graph::edge_iterator edge_it = G.edges_begin();
1042     graph::edge_iterator edges_end = G.edges_end();
1043     while (edge_it != edges_end)
1044     {
1045     unlockedA[*edge_it].clear();
1046     unlockedB[*edge_it].clear();
1047     ++edge_it;
1048     }
1049
1050     // clean buckets
1051     for (int i = 0; i <= 2 * max_vertex_degree * max_edge_weight; i++)
1052     {
1053     bucketA[i].clear();
1054     bucketB[i].clear();
1055     }
1056     bucketA.clear();
1057     bucketB.clear();
1058 }
1059
1060
1061 void fm_partition::compute_cut_edges(const graph& G)
1062 {
1063     cut_edges.clear();
1064     graph::edge_iterator edge_it = G.edges_begin();
1065     graph::edge_iterator edges_end = G.edges_end();
1066     while (edge_it != edges_end)
1067     {
1068     if (side[(*edge_it).source()] != side[(*edge_it).target()])
1069     {
1070         cut_edges.push_back(*edge_it);
1071     }
1072     ++edge_it;
1073     }
1074 }
1075
1076
1077 void fm_partition::compute_nodesAB(const graph& G)
1078 {
1079     nodesA.clear();
1080     nodesB.clear();
1081     graph::node_iterator node_it = G.nodes_begin();
1082     graph::node_iterator nodes_end = G.nodes_end();
1083     while (node_it != nodes_end)
1084     {
1085     if (side[*node_it] == A)
1086     {
1087         nodesA.push_back(*node_it);
1088     }
1089     else    // side[*node_it] == B
1090     {
1091         nodesB.push_back(*node_it);
1092     }
1093     ++node_it;
1094     }
1095 }
1096
1097
1098 #ifdef _DEBUG
1099 void fm_partition::print_bucketA()
1100 {
1101     GTL_debug::init_debug();
1102     GTL_debug::os() << endl << "bucketA:" << endl;
1103     for (int i = 0; i <= 2 * max_vertex_degree * max_edge_weight; i++)
1104     {
1105     GTL_debug::os() << range_down(i) << ": ";
1106     list<node>::iterator node_it = bucketA[i].begin();
1107     list<node>::iterator nodes_end = bucketA[i].end();
1108     while (node_it != nodes_end)
1109     {
1110         GTL_debug::os() << *node_it << "  ";
1111         ++node_it;
1112     }
1113     GTL_debug::os() << endl;
1114     }
1115     GTL_debug::os() << endl;
1116     GTL_debug::close_debug();
1117 }
1118
1119
1120 void fm_partition::print_bucketB()
1121 {
1122     GTL_debug::init_debug();
1123     GTL_debug::os() << endl << "bucketB:" << endl;
1124     for (int i = 0; i <= 2 * max_vertex_degree * max_edge_weight; i++)
1125     {
1126     GTL_debug::os() << range_down(i) << ": ";
1127     list<node>::iterator node_it = bucketB[i].begin();
1128     list<node>::iterator nodes_end = bucketB[i].end();
1129     while (node_it != nodes_end)
1130     {
1131         GTL_debug::os() << *node_it << "  ";
1132         ++node_it;
1133     }
1134     GTL_debug::os() << endl;
1135     }
1136     GTL_debug::os() << endl;
1137     GTL_debug::close_debug();
1138 }
1139 #endif  // _DEBUG
1140
1141
1142 __GTL_END_NAMESPACE
1143
1144 //--------------------------------------------------------------------------
1145 //   end of file
1146 //--------------------------------------------------------------------------