Graph Drawing Toolkit

An object-oriented C++ library for handling and drawing graphs

---

rm3_flow_dire_graph.h

Go to the documentation of this file.

/*******************************************************************************
+
+  rm3_flow_dire_graph.h
+
+  This file is part of GDToolkit. It can be 
+  used free of charge in academic research and teaching. 
+  Any direct or indirect commercial use of this software is illegal 
+  without a written authorization of
+  the Dipartimento di Informatica e Automazione
+  Universita' di Roma Tre, Roma, ITALIA
+  
*******************************************************************************/
#ifndef RM3_FLOW_DIRE_GRAPH_H
#define RM3_FLOW_DIRE_GRAPH_H

#if !defined(ROOT_INCL_ID)
#define ROOT_INCL_ID 34013
#endif

#include <GDT/rm3_dire_graph.h>

        /*
        SOURCEFILE rm3_flow_dire_graph.h
        To be defined.
        */

//-----------------------------------------------------------------------------
// flow_dire_graph:
//      base class for network flow 
//
// W.Didimo, A.Leonforte (1998)
//-----------------------------------------------------------------------------



        class GDT_NONSTANDARD_DECL
struct_flow_dire_node_info
        {
        friend class flow_dire_graph;
        //
        int balance;                            
        
        public:

                /*
                CATEGORYremoved constructors_destructors
                Constructor and Destructors.
                */

        struct_flow_dire_node_info
                (
                );
        };

        

        class GDT_NONSTANDARD_DECL
struct_flow_dire_edge_info
        {
        friend class flow_dire_graph;
        //
        int upper_cap;
        int lower_cap;
        int cost;
        int flow;
        
        public:

                /*
                CATEGORYremoved constructors_destructors
                Constructor and Destructors
                */

        struct_flow_dire_edge_info
                (
                );
        };

        

        class GDT_NONSTANDARD_DECL
flow_dire_graph
        : public dire_graph
        {
        private:
                // -----------------
                // private variables
                // -----------------
                
                gdt::gdtnode_map<struct_flow_dire_node_info>* node_info;
                gdt::gdtedge_map<struct_flow_dire_edge_info>* edge_info;
                
                // ---------------
                // private methods
                // ---------------
                
                void local_new  ();     // create a new set of pointers for the not-inherited class-part
                void local_del  ();     // delete all the not-inherited class-part
                void local_renew();     // utility function : just local_del(), then local_new()
                void local_init ();     // init the not-inherited class-part
                
                void local_set          // set all private variables 
                        (
                        gdt::gdtnode_map<struct_flow_dire_node_info>*, 
                        gdt::gdtedge_map<struct_flow_dire_edge_info>*
                        );
                
                //void update_edge_costs_in_residual (gdtedge, gdtedge, gdtedge, gdt::gdtedge_map<gdtedge>&, gdt::gdtedge_map<bool>&, gdt::gdtedge_array<int>&, gdt::gdtedge_map<int>&);
                
                
        public:
        
                /*
                CATEGORY constructors_destructors
                Constructors and destructors.
                */
                
                        
                flow_dire_graph  
                        (
                        );                                      
                
                        
                ~flow_dire_graph 
                        (
                        );                              
                
                        
                flow_dire_graph 
                        (
                        const undi_graph&
                        );                      

                        
                flow_dire_graph 
                        (
                        const dire_graph&
                        );      
                        
                        
                flow_dire_graph 
                        (
                        const flow_dire_graph&
                        );      
                
                /*
                CATEGORY operators
                Operators.
                */
                
                        
                        flow_dire_graph& 
                operator = 
                        (
                        const undi_graph&
                        );                                                                      
                        
                        
                        flow_dire_graph& 
                operator =
                        (
                        const dire_graph&
                        );      
                        
                        
                        flow_dire_graph& 
                operator = 
                        (
                        const flow_dire_graph&
                        );
                
                /*
                CATEGORY access
                Access operations.
                */                      
                        
                        void 
                local_get                                       
                        (
                        gdt::gdtnode_map<struct_flow_dire_node_info>*& p1, 
                        gdt::gdtedge_map<struct_flow_dire_edge_info>*& p2
                        );

                        
                        int 
                get_balance        
                        (
                        gdtnode v
                        ) const;                

                        
                        int 
                get_upper_capacity 
                        (
                        gdtedge e
                        ) const;                        

                        
                        int 
                get_lower_capacity 
                        (
                        gdtedge e
                        ) const;                

                        
                        int 
                get_flow           
                        (
                        gdtedge e
                        ) const;                        

                        
                        int 
                get_cost               
                        (
                        gdtedge e
                        ) const;                
                        
                        
                        int 
                flow_cost              
                        (
                        ) const;                

                        
                        int 
                in_flow            
                        (
                        gdtnode v
                        );                              

                        
                        int 
                out_flow               
                        (
                        gdtnode v
                        );                              

                        
                        int 
                diff_flow              
                        (
                        gdtnode v
                        );                      

                        
                        bool 
                balance_is_consistent   
                        (
                        ) const;        

                        
                        bool 
                flow_is_consistent              
                        (
                        gdtedge e
                        ) const;                 

                        
                        bool 
                flow_is_consistent              
                        (
                        gdtnode v
                        );              

                        
                        bool 
                flow_is_consistent              
                        (
                        );              

                        
                        bool 
                is_consistent                   
                        (
                        );                       
                
                /*
                CATEGORY update
                Update operations.
                */
                        
                        
                        void 
                clear 
                        (
                        );                                              

                        
                        void 
                set_balance     
                        (
                        gdtnode v,
                        int b
                        );                              

                        
                        void 
                set_upper_capacity 
                        (
                        gdtedge e,
                        int uc
                        );                      
                        
                        
                        void 
                set_lower_capacity      
                        (
                        gdtedge e,
                        int lc
                        );                      
                
                        
                        void 
                set_cost        
                        (
                        gdtedge e,
                        int c
                        );                                              
                        
                        
                        void 
                set_flow        
                        (
                        gdtedge e,
                        int f
                        );              

                        
                        void 
                set_edge_info           
                        (
                        gdtedge e,
                        int uc,
                        int lc,
                        int c,
                        int f
                        );      

                        
                        void 
                steal_from 
                        (
                        dire_graph& dg
                        );              

                        
                        void 
                mirror  
                        (
                        flow_dire_graph& fdg
                        );              

                        
                        void 
                forget  
                        (
                        );                              
                                
                        
                        bool 
                min_cost_flow  
                        (
                        );                                                                                                              
                //bool max_flow     (gdtnode s, gdtnode t);                     // compute a max flow from gdtnode s to gdtnode t. Return false if a fesible flow does not exist.
        };                                                              // STILL TO BE CODED
        
#endif

---