graph.h

#ifndef __GRAPH_H__
#define __GRAPH_H__
#include "../../data_structures/bm/blockmodel.h"
#include "../../problems/finalpit/fp.h"
#include <deque>

using std::vector;
using std::map;


namespace delphos{ 



class MinCutGraph{
private:

    #ifdef ARCH32
    typedef double value_type; //unsigned int
    #else
    typedef double value_type; //unsigned int
    #endif

    struct node;

    typedef struct arc 
    {
        struct node* _from;
        struct node* _to;
        
        value_type _flow;
        value_type _capacity;
        unsigned short _reversed_status;
    } FlowArc;

    typedef struct node 
    {           
        struct node* _parent;
        struct node* _child_list;
        struct node* _last_scan;
        struct node* _neighbour; // neighbour in strong root list
        struct arc* _arc_to_parent;
        
        vector<FlowArc*> _out_of_tree; // residual graph
            
        value_type _excess; 
        
        BlockIndexType _last_out_of_tree_arc_index; 
        BlockIndexType _index;          
        BlockIndexType _label;  // that label is a distance from the sink
        
        bool _in_min_cut_root_set;      

    } Node;

    
    BlockIndexType _nb_nodes;
    BlockIndexType _nb_arcs;
    BlockIndexType _source;
    BlockIndexType _sink;

    Node* _node_list;       
    FlowArc* _arc_list;
    map<BlockIndexType, deque<BlockIndexType> > _strong_root_buckets;
    BlockIndexType _highest_strong_label_value;
    BlockIndexType* _label_value_count; //for all nodes - {source,sink}
    
    string _value_attr;
    BlockSelection* _min_cut_root_set; 
    BlockIndexType _nb_prec_arcs;
    unsigned int _default_nblevel;
    double _default_ang;    
    
    void InitGraph(const FinalPitInstance& fpi);    
    void InitPseudoFlow();  
    Node* GetHighestStrongRoot();
    void PutBranchInMinCutRootSet(Node* pnode);
    void SetMinCutRootSet();
    FlowArc* FindMergerArc(Node* pnode,bool& to_strong_direction);  
    void AddParentalRelationship(Node* pchild,Node* pnew_parent);
    void CutParentalRelationship(Node* pchild,Node* pold_parent);
    void MergeSubTrees(Node* pparent, Node* pchild, FlowArc* pnew_arc); 
    void PushExcess(Node* pstrong); 
    void AddRootToBucket(const BlockIndexType& index,const BlockIndexType& label);
    void Relabel(Node* pnode);
    void CreateArcs(const FinalPitInstance& fpi);   
            
public:
    MinCutGraph(const FinalPitInstance& fpi,string value_attr);
    
    MinCutGraph(const FinalPitInstance& fpi,string value_attr,const double& angle,const unsigned int& nblevel);
    
    ~MinCutGraph(); 
    
    bool PseudoFlow();
    
    BlockSelection* GetMinCutRootSet();
};

}
#endif