include/GTL/fm_partition.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //  fm_partition.h
0005 //
0006 //==========================================================================
0007 // $Id: fm_partition.h,v 1.8 2003/01/31 08:15:05 chris Exp $
0008
0009 #ifndef GTL_FM_PARTITION_H
0010 #define GTL_FM_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 (Fiduccia-Mattheyses).
0023  *
0024  * This class implements a heuristic graph bi-partitioning algorithm, based
0025  * on iterative movement, proposed by C. M. Fiduccia and R. M. Mattheyses
0026  * in 1982.
0027  *
0028  * <p> In the case E is the set of edges of the graph, the algorithm needs
0029  * <code>O(|E|)</code> time to proceed.
0030  *
0031  * @see ratio_cut_partition
0032  */
0033 class GTL_EXTERN fm_partition : public algorithm
0034 {
0035 public:
0036     /**
0037      * Return type of @ref fm_partition#get_side_of_node.
0038      *
0039      * @see fm_partition#A
0040      * @see fm_partition#B
0041      */
0042     typedef int side_type;
0043
0044     /**
0045      * <code>A</code> means the node is on side A.
0046      *
0047      * @see fm_partition#side_type
0048      */
0049     const static side_type A;
0050
0051     /**
0052      * <code>B</code> means the node is on side B.
0053      *
0054      * @see fm_partition#side_type
0055      */
0056     const static side_type B;
0057
0058     /**
0059      * Fix type of each node (needed with @ref fm_partition#set_vars).
0060      *
0061      * @see fm_partition#FIXA
0062      * @see fm_partition#FIXB
0063      * @see fm_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 fm_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 fm_partition#fixe_type
0078      */
0079     const static fix_type FIXB;
0080
0081     /**
0082      * <code>UNFIXED</code> means node is free.
0083      *
0084      * @see fm_partition#fixe_type
0085      */
0086     const static fix_type UNFIXED;
0087
0088     /**
0089      * Default constructor.
0090      *
0091      * @see fm_partition#fixe_type
0092      */
0093     fm_partition();
0094
0095     /**
0096      * Destructor.
0097      *
0098      * @see algorithm#~algorithm
0099      */
0100     virtual ~fm_partition();
0101
0102     /**
0103      * Sets variables.
0104      * Must be executed before @ref fm_partition#check!
0105      *
0106      * @param G undirected graph
0107      * @param node_weight weight of each node
0108      * @param edge_weight weight of each edge
0109      * @see fm_partition#check
0110      */
0111     void set_vars(const graph& G, const node_map<int>& node_weight,
0112     const edge_map<int>& edge_weight);
0113
0114     /**
0115      * Sets variables.
0116      * Must be executed before @ref fm_partition#check!
0117      * In order to get good results, <code>init_side</code> should
0118      * almost be in balance.
0119      *
0120      * @param G undirected graph
0121      * @param node_weight weight of each node
0122      * @param edge_weight weight of each edge
0123      * @param init_side initial bi-partitioning
0124      * @see fm_partition#check
0125      */
0126     void set_vars(const graph& G, const node_map<int>& node_weight,
0127     const edge_map<int>& edge_weight,
0128     const node_map<side_type>& init_side);
0129
0130     /**
0131      * Sets variables.
0132      * Must be executed before @ref fm_partition#check!
0133      *
0134      * @param G undirected graph
0135      * @param node_weight weight of each node
0136      * @param edge_weight weight of each edge
0137      * @param fixed fixed nodes
0138      * @see fm_partition#check
0139      */
0140     void set_vars(const graph& G, const node_map<int>& node_weight,
0141     const edge_map<int>& edge_weight,
0142     const node_map<fix_type>& fixed);
0143
0144     /**
0145      * Sets variables.
0146      * Must be executed before @ref fm_partition#check!
0147      * In order to get good results, <code>init_side</code> should
0148      * almost be in balance. Fixed nodes are on their fix side, their
0149      * initial side is overwritten then.
0150      *
0151      * @param G undirected graph
0152      * @param node_weight weight of each node
0153      * @param edge_weight weight of each edge
0154      * @param init_side initial bi-partitioning
0155      * @param fixed fixed nodes
0156      * @see fm_partition#check
0157      */
0158     void set_vars(const graph& G, const node_map<int>& node_weight,
0159     const edge_map<int>& edge_weight,
0160     const node_map<side_type>& init_side,
0161     const node_map<fix_type>& fixed);
0162
0163     /**
0164      * Enables the storing of cut-edges. If enabled the list of
0165      * cut-edges can be traversed using @ref
0166      * fm_partition#cut_edges_iterator.
0167      *
0168      * @param set if <code>true</code> cut_edges will be stored
0169      * @see fm_partition#cut_edges_begin
0170      * @see fm_partition#cut_edges_end
0171      */
0172     void store_cut_edges(const bool set);
0173
0174     /**
0175      * Enables the storing of nodes on their side. If enabled the nodes
0176      * of each side can be traversed using @ref
0177      * fm_partition#nodes_on_one_side_iterator.
0178      *
0179      * @param set if <code>true</code> nodes will be stored on their sides
0180      * @see fm_partition#nodes_of_sideA_begin
0181      * @see fm_partition#nodes_of_sideA_end
0182      * @see fm_partition#nodes_of_sideB_begin
0183      * @see fm_partition#nodes_of_sideB_end
0184      */
0185     void store_nodesAB(const bool set);
0186
0187     /**
0188      * Checks whether following preconditions are satisfied:
0189      * <ul>
0190      * <li> @ref fm_partition#set_vars has been executed before.
0191      * <li> graph <code>G</code> is undirected.
0192      * <li> only node_weights >= 0 are applied.
0193      * <li> only edge_weights >= 0 are applied.
0194      * </ul>
0195      *
0196      * @param G graph
0197      * @return <code>algorithm::GTL_OK</code> on success,
0198      * <code>algorithm::GTL_ERROR</code> otherwise
0199      * @see fm_partition#set_vars
0200      * @see algorithm#check
0201      */
0202     virtual int check(graph& G);
0203
0204     /**
0205      * Computes a partitioning with <code>G</code>, that means a
0206      * division of its vertices in two sides <code>fm_partition::A
0207      * </code> and <code>fm_partition::B</code>.
0208      *
0209      * @param G graph
0210      * @return <code>algorithm::GTL_OK</code> on success,
0211      * <code>algorithm::GTL_ERROR</code> otherwise
0212      * @see algorithm#run
0213      */
0214     int run(graph& G);
0215
0216     /**
0217      * Gets the size of the cut after bi-partitioning.
0218      *
0219      * @return cutsize
0220      */
0221     int get_cutsize();
0222
0223     /**
0224      * Gets the number of passes needed to create a bi-partition with
0225      * this heuristic.
0226      *
0227      * @return number of passes
0228      */
0229     int get_needed_passes();
0230
0231     /**
0232      * Gets side of the node after bi-partitioning.
0233      *
0234      * @param n node of graph @c G
0235      * @return <code>fm_partition::A</code> if <code>n</code> lies on
0236      * side <code>A</code>, <code>fm_partition::B</code> otherwise
0237      */
0238     side_type get_side_of_node(const node& n) const;
0239
0240     /**
0241      * Gets side of the node after bi-partitioning.
0242      *
0243      * @param n node of graph @c G
0244      * @return <code>fm_partition::A</code> if <code>n</code> lies on
0245      * side <code>A</code>, <code>fm_partition::B</code> otherwise
0246      * @see fm_partition#get_side_of_node
0247      */
0248     side_type operator [](const node& n) const;
0249
0250     /**
0251      * Gets the sum of all node weights from nodes on side A.
0252      *
0253      * @param G graph
0254      * @return <code>node_weight_on_sideA</code>
0255      */
0256     int get_weight_on_sideA(const graph& G) const;
0257
0258     /**
0259      * Gets the sum of all node weights from nodes on side B.
0260      *
0261      * @param G graph
0262      * @return <code>node_weight_on_sideB</code>
0263      */
0264     int get_weight_on_sideB(const graph& G) const;
0265
0266     /**
0267      * Iterator type for edges which belong to the cut.
0268      */
0269     typedef list<edge>::const_iterator cut_edges_iterator;
0270
0271     /**
0272      * Iterate through all edges which belong to the cut, that means
0273      * all edges with end-nodes on different sides.
0274      * It is only valid if enabled with @ref
0275      * fm_partition#store_cut_edges before.
0276      *
0277      * @return start for iteration through all cut edges
0278      */
0279     cut_edges_iterator cut_edges_begin() const;
0280
0281     /**
0282      * End-Iterator for iteration through all edges which belong to the
0283      * cut.
0284      * It is only valid if enabled with @ref
0285      * fm_partition#store_cut_edges before.
0286      *
0287      * @return end for iteration through all cut-edges
0288      */
0289     cut_edges_iterator cut_edges_end() const;
0290
0291     /**
0292      * Iterator type of nodes of a side.
0293      */
0294     typedef list<node>::const_iterator nodes_of_one_side_iterator;
0295
0296     /**
0297      * Iterate through all nodes which belong to side <code>A</code>.
0298      * It is only valid if enabled with @ref
0299      * fm_partition#store_nodesAB before.
0300      *
0301      * @return start for iteration through all nodes on <code>A</code>
0302      */
0303     nodes_of_one_side_iterator nodes_of_sideA_begin() const;
0304
0305     /**
0306      * End-Iterator for iteration through all nodes which belong to side
0307      * <code>A</code>.
0308      * It is only valid if enabled with @ref
0309      * fm_partition#store_nodesAB before.
0310      *
0311      * @return end for iteration through all nodes on <code>A</code>
0312      */
0313     nodes_of_one_side_iterator nodes_of_sideA_end() const;
0314
0315     /**
0316      * Iterate through all nodes which belong to side <code>B</code>,
0317      * It is only valid if enabled with @ref
0318      * fm_partition#store_nodesAB before.
0319      *
0320      * @return start for iteration through all nodes on <code>B</code>
0321      */
0322     nodes_of_one_side_iterator nodes_of_sideB_begin() const;
0323
0324     /**
0325      * End-Iterator for iteration through all nodes which belong to side
0326      * <code>B</code>,
0327      * It is only valid if enabled with @ref
0328      * fm_partition#store_nodesAB before.
0329      *
0330      * @return end for iteration through all nodes on <code>B</code>
0331      */
0332     nodes_of_one_side_iterator nodes_of_sideB_end() const;
0333
0334     /**
0335      * Resets fm_partition, i.e. prepares the algorithm to be applied
0336      * to another graph.
0337      *
0338      * @see algorithm#reset
0339      */
0340     virtual void reset();
0341 protected:
0342     /**
0343      * @internal
0344      * <code>true</code>, iff user enabled storing of cut-edges with
0345      * @ref fm_partition#store_cut_edges.
0346      */
0347     bool enable_cut_edges_storing;
0348
0349     /**
0350      * @internal
0351      * List of edges which belong to the cut.
0352      */
0353     list<edge> cut_edges;
0354
0355     /**
0356      * @internal
0357      * <code>true</code>, iff user enabled storing of nodes with
0358      * @ref fm_partition#store_nodesAB.
0359      */
0360     bool enable_nodesAB_storing;
0361
0362     /**
0363      * @internal
0364      * List of nodes which belong to side <code>A</code>.
0365      */
0366     list<node> nodesA;
0367
0368     /**
0369      * @internal
0370      * List of nodes which belong to side <code>A</code>.
0371      */
0372     list<node> nodesB;
0373
0374     /**
0375      * @internal
0376      * <code>true</code>, iff user has executed @ref fm_partition#
0377      * set_vars before @ref fm_partition#check and @ref fm_partition#
0378      * run.
0379      */
0380     bool set_vars_executed;
0381
0382     /**
0383      * @internal
0384      * <code>true</code>, iff user has provided <code>init_side</code>
0385      * with @ref fm_partition#set_vars, <code>false</code> otherwise.
0386      */
0387     bool provided_initial_part;
0388
0389     /**
0390      * @internal
0391      * <code>true</code>, iff user has provided <code>fixed</code> with
0392      * @ref fm_partition#set_vars, <code>false</code> otherwise.
0393      */
0394     bool provided_fix;
0395
0396     /**
0397      * @internal
0398      * Contains information where a node is fixed.
0399      */
0400     node_map<fix_type> fixed;
0401
0402     /**
0403      * @internal
0404      * Contains the weight of each node.
0405      * Corresponds to w(v) in [Leng90].
0406      */
0407     node_map<int> node_weight;
0408
0409     /**
0410      * @internal
0411      * Contains the maximum weight of a node in <code>G</code>.
0412      * (maximum of <code>node_weight[...]</code>)
0413      */
0414     int max_node_weight;
0415
0416     /**
0417      * @internal
0418      * Contains the weight of each edge.
0419      * Corresponds to c(e) in [Leng90].
0420      */
0421     edge_map<int> edge_weight;
0422
0423     /**
0424      * @internal
0425      * Contains the maximum weight of an edge in <code>G</code>.
0426      * (maximum of <code>edge_weight[...]</code>)
0427      */
0428     int max_edge_weight;
0429
0430     /**
0431      * @internal
0432      * Contains the sum over all vertex weights in <code>G</code>.
0433      * Corresponds to w(V) in [Leng90].
0434      */
0435     int total_node_weight;
0436
0437     /**
0438      * @internal
0439      * Contains the sum over all vertex weights on side <code>A</code>.
0440      * Corresponds to w(A) in [Leng90].
0441      */
0442     int node_weight_on_sideA;
0443
0444     /**
0445      * @internal
0446      * Contains the sum over all vertex weights on side <code>B</code>.
0447      * Corresponds to w(B) in [Leng90].
0448      */
0449     int node_weight_on_sideB;
0450
0451     /**
0452      * @internal
0453      * Contains information about the current side of a node.
0454      */
0455     node_map<side_type> side;
0456
0457     /**
0458      * @internal
0459      * Corresponds to CELL array in [FidMat82]
0460      */
0461     node_map<list<node>::iterator> position_in_bucket;
0462
0463     /**
0464      * @internal
0465      * Contains the maximal number of adjacent to a node.
0466      */
0467     int max_vertex_degree;
0468
0469     /**
0470      * @internal
0471      * Contains how many nodes an edge has on side <code>A</code>.
0472      */
0473     edge_map<int> aside;
0474
0475     /**
0476      * @internal
0477      * Contains how many nodes an edge has on side <code>B</code>.
0478      */
0479     edge_map<int> bside;
0480
0481     /**
0482      * @internal
0483      * Contains the unlocked nodes of an edge on side <code>A</code>.
0484      * (max. 2)
0485      */
0486     edge_map<list<node> > unlockedA;
0487
0488     /**
0489      * @internal
0490      * Contains the unlocked nodes of an edge on side <code>B</code>.
0491      * (max. 2)
0492      */
0493     edge_map<list<node> > unlockedB;
0494
0495     /**
0496      * @internal
0497      * Corresponds to D value in Leng[90].
0498      */
0499     node_map<int> gain_value;
0500
0501     /**
0502      * @internal
0503      * <code>true</code>, iff <code>bucketA</code> is empty.
0504      */
0505     bool bucketA_empty;
0506
0507     /**
0508      * @internal
0509      * <code>true</code>, iff <code>bucketB</code> is empty.
0510      */
0511     bool bucketB_empty;
0512
0513     /**
0514      * @internal
0515      * Contains the maximum gain value of a node in
0516      * <code>bucketA</code>.
0517      */
0518     int max_gainA;
0519
0520     /**
0521      * @internal
0522      * Contains the maximum gain value of a node in
0523      * <code>bucketB</code>.
0524      */
0525     int max_gainB;
0526
0527     /**
0528      * @internal
0529      * Like a hash table over the <code>gain_value</code> of each node
0530      * on side <code>A</code>. (open hashing, collisions in gain buckets
0531      * are organized through LIFO lists)
0532      */
0533     vector<list<node> > bucketA;
0534
0535     /**
0536      * @internal
0537      * Like a hash table over the <code>gain_value</code> of each node
0538      * on side <code>B</code>. (open hashing, collisions in gain buckets
0539      * are organized through LIFO lists)
0540      */
0541     vector<list<node> > bucketB;
0542
0543     /**
0544      * @internal
0545      * Sum over all <code>edge_costs[e]</code> where edge e is an
0546      * element of the cut.
0547      */
0548     int cur_cutsize;
0549
0550     /**
0551      * @internal
0552      * Number of needed passes.
0553      */
0554     int no_passes;
0555
0556     /**
0557      * @internal
0558      * Fix <code>FIXA</code> nodes on side <code>A</code> and <code>FIXB
0559      * </code> nodes on side <code>B</code>.
0560      */
0561     void divide_up(const graph& G);
0562
0563     /**
0564      * @internal
0565      * Hides self loops of <code>G</code>.
0566      */
0567     void hide_self_loops(graph& G);
0568
0569     /**
0570      * @internal
0571      * Computes <code>max_edge_weight</code>, <code>max_node_weight
0572      * </code> and <code>total_node_weight</code>.
0573      */
0574     void init_variables(const graph& G);
0575
0576     /**
0577      * @internal
0578      * Divides nodes of <code>G</code> arbitrary into two sides <code>A
0579      * </code> and <code>B</code>. Here, <code>side</code> will be
0580      * filled with an arbitrary feasible solution.
0581      */
0582     void create_initial_bipart(const graph& G);
0583
0584     /**
0585      * @internal
0586      * Shuffles order of <code>node_vector</code> with size <code>
0587      * vector_size</code>.
0588      */
0589     void shuffle_vector(const int vector_size,
0590     vector<graph::node_iterator>& node_vector);
0591
0592     /**
0593      * @internal
0594      * Computes <code>max_vertex_degree</code>.
0595      */
0596     void compute_max_vertex_degree(const graph& G);
0597
0598     /**
0599      * @internal
0600      * Runs as much passes as needed.
0601      */
0602     void pass_manager(const graph& G);
0603
0604     /**
0605      * @internal
0606      * Copies side node maps.
0607      */
0608     void copy_side_node_map(const graph& G, node_map<side_type>& dest,
0609     const node_map<side_type> source) const;
0610
0611     /**
0612      * @internal
0613      * Initialization of the data structure for each pass.
0614      */
0615     void init_data_structure(const graph& G);
0616
0617     /**
0618      * @internal
0619      * Computes initial gain_value for each node and inserts it in the
0620      * corresponding bucket data structure.
0621      */
0622     void init_filling_buckets(const graph& G);
0623
0624     /**
0625      * @internal
0626      * Compute initial gain of a node on side <code>A</code>.
0627      * @return initial gain_value of a node on side <code>A</code>
0628      */
0629     int inital_gain_of_node_on_sideA(const node cur_node);
0630
0631     /**
0632      * @internal
0633      * Compute initial gain of a node on side <code>B</code>.
0634      * @return initial gain_value of a node on side <code>B</code>
0635      */
0636     int inital_gain_of_node_on_sideB(const node cur_node);
0637
0638     /**
0639      * @internal
0640      * Moves nodes within a pass.
0641      */
0642     void move_manager(const graph& G);
0643
0644     /**
0645      * @internal
0646      * Move a single node
0647      * @return <code>true</code> if vertex stored in parameter <code>
0648      * moved_node</code> has been found
0649      */
0650     bool move_vertex(const graph& G, node& moved_node);
0651
0652     /**
0653      * @internal
0654      * Only valid on unlocked nodes!
0655      * @return <code>true</code> if a certain balance criterion can be
0656      * hold, <code>false</code> otherwise
0657      */
0658     bool balance_holds(const graph& G, const node cur_node);
0659
0660     /**
0661      * @internal
0662      * Executed, if <code>cur_node</code> is chosen to move from side
0663      * <code>A</code> to <code>B</code>.
0664      */
0665     void update_data_structure_A2B(const node cur_node);
0666
0667     /**
0668      * @internal
0669      * Executed, if <code>cur_node</code> is chosen to move from side
0670      * <code>B</code> to <code>A</code>.
0671      */
0672     void update_data_structure_B2A(const node cur_node);
0673
0674     /**
0675      * @internal
0676      * Reorganizes <code>bucketA</code> if a nodes gain of it has been
0677      * changed.
0678      */
0679     void update_bucketA(const node cur_node, const int old_gain,
0680     const int new_gain);
0681
0682     /**
0683      * @internal
0684      * Reorganizes <code>bucketB</code> if a nodes gain of it has been
0685      * changed.
0686      */
0687     void update_bucketB(const node cur_node, const int old_gain,
0688     const int new_gain);
0689
0690     /**
0691      * @internal
0692      * Recomputes <code>max_gainA</code> or <code>max_gainB</code>
0693      * respectively.
0694      */
0695     void update_max_gain(const side_type side);
0696
0697     /**
0698      * @internal
0699      * Transform a range from [-a..+a] to [0..2a].
0700      * (reverse to @ref fm_partition#range_up)
0701      */
0702     inline int range_up(const int gain_value) const;
0703
0704     /**
0705      * @internal
0706      * Transform a range from [0..2a] to [-a..+a].
0707      * (reverse to @ref fm_partition#range_down)
0708      */
0709     inline int range_down(const int index) const;
0710
0711     /**
0712      * @internal
0713      * Do some garbage collection.
0714      */
0715     void clean_pass(const graph& G);
0716
0717     /**
0718      * @internal
0719      * Computes list <code>cut_edges</code>.
0720      */
0721     void compute_cut_edges(const graph& G);
0722
0723     /**
0724      * @internal
0725      * Computes lists <code>nodesA</code> and <code>nodesB</code>.
0726      */
0727     void compute_nodesAB(const graph& G);
0728 private:
0729 #ifdef _DEBUG
0730     /**
0731      * @internal
0732      * Prints content of bucketA with associated gain values.
0733      */
0734     void print_bucketA();
0735
0736     /**
0737      * @internal
0738      * Prints content of bucketB with associated gain values.
0739      */
0740     void print_bucketB();
0741 #endif  // _DEBUG
0742 };
0743
0744
0745 __GTL_END_NAMESPACE
0746
0747 #endif // GTL_FM_PARTITION_H
0748
0749 //--------------------------------------------------------------------------
0750 //   end of file
0751 //--------------------------------------------------------------------------