ratio_cut_partition.h

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

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

#ifndef GTL_RATIO_CUT_PARTITION_H
#define GTL_RATIO_CUT_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 ratio_cut_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;

    ratio_cut_partition();

    virtual ~ratio_cut_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 source_node,
        const node target_node);

    void set_vars(const graph& G, const node_map<int>& node_weight,
        const edge_map<int>& edge_weight, const node source_node,
        const node target_node, 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 source_node,
        const node target_node, 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 source_node,
        const node target_node, 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();
                
    double get_cutratio();
                
    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:
    enum direction_type {LEFT_SHIFT = 2, RIGHT_SHIFT = 3};

    bool enable_cut_edges_storing;
                
    list<edge> cut_edges;

    bool enable_nodesAB_storing;
                
    list<node> nodesA;

    list<node> nodesB;

    node source_node;

    node target_node;

    bool set_vars_executed;

    bool provided_st;

    bool provided_initial_part;

    bool provided_fix;
                
    node_map<fix_type> fixed;

    direction_type direction;

    node_map<int> node_weight;

    edge_map<int> edge_weight;

    int max_edge_weight;

    int node_weight_on_sideA;

    int node_weight_on_sideB;
                
    int nodes_on_sideA;
                
    int nodes_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;

    double cur_cutratio;

    void divide_up(const graph& G);

    void make_connected(graph& G, list<edge>& artificial_edges);
                
    void restore(graph& G, list<edge>& artificial_edges);
                
    void initialization(const graph& G);

    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 init_variables(const graph& G);
                
    void compute_max_vertex_degree(const graph& G);

    void determine_source_node(const graph& G);

    void compute_target_node(const graph& G);

    void right_shift_op(const graph& G);

    void left_shift_op(const graph& G);

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

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

    node compute_highest_ratio_node(list<node> node_list);

    double cutratio();
                                
    double ratio_of_node_A2B(const node cur_node);

    double ratio_of_node_B2A(const node cur_node);
                
    inline int range_up(const int gain_value) const;

    inline int range_down(const int index) const;

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

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

    void clean_step(const graph& G);

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

    void group_swapping(const graph& G);

    bool move_manager(const graph& G);

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

    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_RATIO_CUT_PARTITION_H

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