fm_partition.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file fm_partition.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//      fm_partition.h
//
//==========================================================================
// $Id: fm_partition.h,v 1.8 2003/01/31 08:15:05 chris Exp $

#ifndef GTL_FM_PARTITION_H
#define GTL_FM_PARTITION_H

#include <GTL/GTL.h>
#include <GTL/graph.h>
#include <GTL/node_map.h>
#include <GTL/edge_map.h>
#include <GTL/algorithm.h>

__GTL_BEGIN_NAMESPACE


class GTL_EXTERN fm_partition : public algorithm
{
public:
    typedef int side_type;

    const static side_type A;

    const static side_type B;

    typedef short int fix_type;

    const static fix_type FIXA;

    const static fix_type FIXB;

    const static fix_type UNFIXED;

    fm_partition();

    virtual ~fm_partition();

    void set_vars(const graph& G, const node_map<int>& node_weight,
        const edge_map<int>& edge_weight);

    void set_vars(const graph& G, const node_map<int>& node_weight,
        const edge_map<int>& edge_weight,
        const node_map<side_type>& init_side);

    void set_vars(const graph& G, const node_map<int>& node_weight,
        const edge_map<int>& edge_weight,
        const node_map<fix_type>& fixed);

    void set_vars(const graph& G, const node_map<int>& node_weight,
        const edge_map<int>& edge_weight,
        const node_map<side_type>& init_side,
        const node_map<fix_type>& fixed);

    void store_cut_edges(const bool set);

    void store_nodesAB(const bool set);

    virtual int check(graph& G);

    int run(graph& G);

    int get_cutsize();

    int get_needed_passes();
                
    side_type get_side_of_node(const node& n) const;

    side_type operator [](const node& n) const;
                                
    int get_weight_on_sideA(const graph& G) const;

    int get_weight_on_sideB(const graph& G) const;

    typedef list<edge>::const_iterator cut_edges_iterator;

    cut_edges_iterator cut_edges_begin() const;

    cut_edges_iterator cut_edges_end() const;
                
    typedef list<node>::const_iterator nodes_of_one_side_iterator;

    nodes_of_one_side_iterator nodes_of_sideA_begin() const;

    nodes_of_one_side_iterator nodes_of_sideA_end() const;

    nodes_of_one_side_iterator nodes_of_sideB_begin() const;

    nodes_of_one_side_iterator nodes_of_sideB_end() const;

    virtual void reset();
protected:
    bool enable_cut_edges_storing;
                
    list<edge> cut_edges;

    bool enable_nodesAB_storing;
                
    list<node> nodesA;

    list<node> nodesB;

    bool set_vars_executed;
                
    bool provided_initial_part;
                
    bool provided_fix;
                
    node_map<fix_type> fixed;

    node_map<int> node_weight;

    int max_node_weight;

    edge_map<int> edge_weight;

    int max_edge_weight;

    int total_node_weight;

    int node_weight_on_sideA;

    int node_weight_on_sideB;

    node_map<side_type> side;

    node_map<list<node>::iterator> position_in_bucket;
                
    int max_vertex_degree;

    edge_map<int> aside;

    edge_map<int> bside;

    edge_map<list<node> > unlockedA;

    edge_map<list<node> > unlockedB;

    node_map<int> gain_value;

    bool bucketA_empty;

    bool bucketB_empty;

    int max_gainA;

    int max_gainB;

    vector<list<node> > bucketA;

    vector<list<node> > bucketB;

    int cur_cutsize;

    int no_passes;

    void divide_up(const graph& G);

    void hide_self_loops(graph& G);

    void init_variables(const graph& G);
                
    void create_initial_bipart(const graph& G);

    void shuffle_vector(const int vector_size,
        vector<graph::node_iterator>& node_vector);
                
    void compute_max_vertex_degree(const graph& G);

    void pass_manager(const graph& G);

    void copy_side_node_map(const graph& G, node_map<side_type>& dest,
        const node_map<side_type> source) const;
                        
    void init_data_structure(const graph& G);
                
    void init_filling_buckets(const graph& G);

    int inital_gain_of_node_on_sideA(const node cur_node);

    int inital_gain_of_node_on_sideB(const node cur_node);

    void move_manager(const graph& G);

    bool move_vertex(const graph& G, node& moved_node);

    bool balance_holds(const graph& G, const node cur_node);

    void update_data_structure_A2B(const node cur_node);

    void update_data_structure_B2A(const node cur_node);
                
    void update_bucketA(const node cur_node, const int old_gain,
        const int new_gain);

    void update_bucketB(const node cur_node, const int old_gain,
        const int new_gain);
                
    void update_max_gain(const side_type side);

    inline int range_up(const int gain_value) const;

    inline int range_down(const int index) const;

    void clean_pass(const graph& G);
                
    void compute_cut_edges(const graph& G);

    void compute_nodesAB(const graph& G);
private:
#ifdef _DEBUG

    void print_bucketA();

    void print_bucketB();
#endif  // _DEBUG
};


__GTL_END_NAMESPACE

#endif // GTL_FM_PARTITION_H

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------