title
Graph Drawing Toolkit

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

rm3_upwa_plan_undi_graph.h

Go to the documentation of this file.
00001 /*******************************************************************************
00002 +
00003 +  rm3_upwa_plan_undi_graph.h
00004 +
00005 +  This file is part of GDToolkit. It can be 
00006 +  used free of charge in academic research and teaching. 
00007 +  Any direct or indirect commercial use of this software is illegal 
00008 +  without a written authorization of
00009 +  the Dipartimento di Informatica e Automazione
00010 +  Universita' di Roma Tre, Roma, ITALIA
00011 +    
00012 +  All rights reserved.
00013 + 
00014 *******************************************************************************/
00018 #ifndef RM3_UPWA_PLAN_UNDI_GRAPH_H
00019 #define RM3_UPWA_PLAN_UNDI_GRAPH_H
00020 
00021 #include <GDT/gdtlist.h>
00022 #include <GDT/gdtmap.h>
00023 #include <GDT/rm3_plan_undi_graph.h>
00024 #include <GDT/rm3_global.h>
00025 
00026 
00027 
00028 //-----------------------------------------------------------------------------
00029 // upwa_plan_undi_graph: base class for handling upward representations of
00030 //                       directed planar graphs
00031 //
00032 // W.Didimo, A.Leonforte (1997)
00033 //-----------------------------------------------------------------------------
00034 
00035         class 
00036 upwa_plan_undi_graph;           // forward declaration
00037 
00043         class 
00044 struct_upwa_node_info
00045         {
00046         friend class upwa_plan_undi_graph;
00047         
00048         private:
00049                 gdtedge first_in_cand;                  // first in-edges in candidate lists of gdtnode
00050                 gdtedge first_out_cand;                 // first out-edges in candidate lists of gdtnode
00051                 bool in_cand_edges_are_ordered;         // true when the in-edges candidate list is ordered
00052                 bool out_cand_edges_are_ordered;        // true when the out-edges candidate list is ordered
00053                 
00054         public:
00055                 
00056                 struct_upwa_node_info
00057                         (
00058                         );
00059         };
00060 
00098         class GDT_NONSTANDARD_DECL
00099 upwa_plan_undi_graph
00100         : public plan_undi_graph
00101         {
00102                 
00103         private:
00104                 // -----------------
00105                 // private variables
00106                 // -----------------
00107                 
00108                 face                             ext_face;                      // external face 
00109                 algorithm_type                   layout_algorithm;              // layout algorithm (PLAN_UPWARD_OPTIMAL, PLAN_UPWARD_SLOW)
00110                 gdt::gdtedge_map<bend_constraint>        constraint_on_bends_of_edge;   // mapping of bend_constraint on edges
00111                 gdt::gdtnode_map<struct_upwa_node_info>* node_info;                     // correspondence gdtnode -> upwa_node structure
00112                 int                              last_cost;                     // cost of the last flow-algorithm applied
00113                 
00114                 // ---------------
00115                 // private methods
00116                 // ---------------
00117                 
00118                 void local_new  ();                                                     // create a new set of pointers for the not-inherited class-part
00119                 void local_del  ();                                                     // delete all the not-inherited class-part
00120                 void local_renew();                                                     // utility function : just local_del(), then local_new()
00121                 void local_init (face,algorithm_type, bool err_mess);                   // init the not-inherited class-part
00122                 
00123                 void local_set                                                          // set all private variables  
00124                         (
00125                         face, 
00126                         algorithm_type, 
00127                         gdt::gdtedge_map<bend_constraint>, 
00128                         gdt::gdtnode_map<struct_upwa_node_info>*,
00129                         int
00130                         );                                                                      
00131 
00132                 void set_first_in_cand   (gdtnode,gdtedge);                                     // set the first in-gdtedge in the candidate lists of gdtnode with gdtedge
00133                 void set_first_out_cand  (gdtnode,gdtedge);                                     // set the first out-gdtedge in the candidate lists of gdtnode with gdtedge
00134                 
00135                 void set_in_cand_edges_are_ordered  (gdtnode,bool);                     // set the in_edges candidate list of gdtnode as ordered(bool = true)/unordered(bool = false)
00136                 void set_out_cand_edges_are_ordered (gdtnode,bool);                     // set the out_edges candidate list of gdtnode as ordered(bool = true)/unordered(bool = false)
00137                 
00138                 
00139                 void update_constraint_internal_structures ();                          // update all constraint internal structures, based on contraint list
00140                 void set_bend_constraints   (gdtedge, bend_constraint);                 // set bend_constarint for gdtedge
00141                 void set_bend_constraints   (gdt::gdtedge_array<bend_constraint>);              // set bend constraints for all edges
00142                 void reset_bend_constraints ();                                         // reset all bend constraints on gdtedge
00143 
00144                 void order_in_cand  (gdtnode);                                          // update the first_in_edge of gdtnode to have a candidate list
00145                 void order_out_cand (gdtnode);                                          // update the first_out_edge of gdtnode to have a candidate list             
00146                 void order_cand     (gdtnode);                                          // update the first_in_edge and the first_out_edge of gdtnode to have candidate lists
00147                 void order_cand     ();                                                 // execute the update_cand(v) method for each gdtnode v.
00148                 
00149                 gdt::list_item find_BSS  (gdt::gdtlist<gdtnode>& ext, gdt::gdtmap<gdt::list_item,bool>& is_big);        // look for a sequence BSS (big/small angles) into the estremals list ext.
00150                                                                                         // If there exists one, return the item of the gdtnode with angle B in ext.
00151                 
00152                 
00153                 
00154                 int make_upward_with_constraints ();                                    // kernel of the optimal_upward_for_fixed_embedding_with_constraints() method
00155                                                                  
00156                 int optimal_upward_for_fixed_embedding_with_constraints ();             // compute an upward representation of the graph, preserving the planar embedding and
00157                                                                                         // introducing, when it is needed, a minimum number of dummy nodes and edges.
00158                                                                                         // The function returns the number of dummy nodes added on edges with no zero cost (flow cost)
00159                                                                  
00160                 int slow_upward ();                                                     // compute an upward representation of the graph, searching over all the
00161                                                                                         // possible planar embedding of the graph and introducing, when it is needed, a minimum number 
00162                                                                                         // of dummy nodes and egdes.
00163                                                                                         // The function returns the number of dummy nodes added on edges with no zero cost (flow cost)
00164                                                                                         // PRECONDITION: graph must be biconnected.
00165                                                                  
00166                 
00167                 gdtnode new_node (gdtedge,int new_id=AUTO_ID );                         // add a new gdtnode splitting an gdtedge e into two new edges with same direction of e
00168                 
00169                 gdtedge new_edge (gdtnode v1, gdtnode v2, face f, int new_id=AUTO_ID);          // add a new directed gdtedge from v1 to v2 into the face f;
00170                 gdtedge new_edge (gdtnode v1, gdtedge e1, gdtnode v2, gdtedge e2, int new_id=AUTO_ID);  // add a new directed gdtedge from v1 to v2 and put it after gdtedge e1 around v1 and after gdtedge e2 around v2 
00171                 
00172                 void del_edge (gdtedge);                                                        // delete gdtedge;
00173                 
00174                 void reverse (gdtedge);                                                 // reverese direction of gdtedge
00175                 void make_directed (gdtedge,gdtnode);                                           // make gdtedge directed from gdtnode
00176         
00177                 void make_big_angle     (gdtnode v, face f);                            // make a big angle on gdtnode v into face f
00178          
00179                 gdt::gdtlist<gdtedge> decompose (face& f);                                              // add and return a set of dummy edges on sequences of extremals BSS.
00180                                                                                         // Also, it puts in f the pointer to the last face of the recursive decomposition.
00181                                                                                         // NOTE: if f was the external face, after the decomposition f will be the new external face
00182                                                                  
00183                 gdt::gdtlist<gdtedge> decompose ();                                             // apply decompose to all faces and return all dummy edges added
00184                 
00185                 bool is_upward();                                                       // return true if the internal data structure really describe an upward representation
00186         
00187         
00188         
00189         public:
00190                 
00191                 /*
00192                 CATEGORY constructors_destructors
00193                 Constructors and destructors.
00194                 */
00195                 
00196                         
00201                 upwa_plan_undi_graph  
00202                         (
00203                         );                                                              
00204                                 
00205                         
00210                 ~upwa_plan_undi_graph 
00211                         (
00212                         );                                                              
00213                                         
00214                         
00222                 upwa_plan_undi_graph 
00223                         (
00224                         const undi_graph& ug, 
00225                         algorithm_type alg = PLAN_UPWARD_OPTIMAL,
00226                         bool err_mess = true
00227                         );              
00228                         
00229                         
00237                 upwa_plan_undi_graph 
00238                         (
00239                         const plan_undi_graph& pug, 
00240                         algorithm_type alg = PLAN_UPWARD_OPTIMAL,
00241                         bool err_mess = true
00242                         );      
00243                         
00244                         
00253                 upwa_plan_undi_graph 
00254                         (
00255                         const plan_undi_graph& pug, 
00256                         face ef, 
00257                         algorithm_type alg = PLAN_UPWARD_OPTIMAL,
00258                         bool err_mess = true
00259                         );                                                                              
00260                         
00261                         
00262                         
00272                 upwa_plan_undi_graph
00273                         (
00274                         const plan_undi_graph& pug,
00275                         gdt::gdtnode_array<gdtedge>& first_edge
00276                         );
00277                         
00278                         
00279                         
00284                 upwa_plan_undi_graph 
00285                         (
00286                         const upwa_plan_undi_graph& upug
00287                         );                                      
00288                 
00289                        
00290                 /*
00291                 CATEGORY operators
00292                 Operators.
00293                 */
00294                                 
00295                         
00301                         upwa_plan_undi_graph& 
00302                 operator = 
00303                         (
00304                         const undi_graph& ug
00305                         );                                      
00306                                         
00307                         
00313                         upwa_plan_undi_graph& 
00314                 operator = 
00315                         (
00316                         const plan_undi_graph& pug
00317                         );                              
00318                                         
00319                         
00324                         upwa_plan_undi_graph& 
00325                 operator = 
00326                         (
00327                         const upwa_plan_undi_graph& upug
00328                         );                              
00329                 
00330                 /*
00331                 CATEGORY access
00332                 Access operations.
00333                 */
00334                 
00335                         
00340                         void 
00341                 local_get                                                
00342                         (
00343                         face& p1, 
00344                         algorithm_type& p2, 
00345                         gdt::gdtedge_map<bend_constraint>& p3, 
00346                         gdt::gdtnode_map<struct_upwa_node_info>*& p4,
00347                         int& p5
00348                         );                                                                              
00349                 
00350                 // DO NOT LIST IN PUBLIC METHODS
00351                 // ---------------------------------------
00352                 bool get_in_cand_edges_are_ordered  (gdtnode)           const;  // get the internal variable in_cand_edges_are_ordered  
00353                 bool get_out_cand_edges_are_ordered (gdtnode)           const;  // get the internal variable out_cand_edges_are_ordered
00354                 gdtedge get_first_in_cand (gdtnode)                             const;  // get the internal variable first_in_cand of gdtnode
00355                 gdtedge get_first_out_cand(gdtnode)                             const;  // get the internal variable frist_out_cand of gdtnode
00356                 // ---------------------------------------      
00357                                         
00358                         
00363                         gdtedge 
00364                 first_in_cand_edge  
00365                         (
00366                         gdtnode v
00367                         );                              
00368                                 
00369                         
00374                         gdtedge 
00375                 first_out_cand_edge 
00376                         (
00377                         gdtnode v
00378                         );                              
00379                                 
00380                         
00385                         gdtedge 
00386                 cand_edge_succ      
00387                         (
00388                         gdtedge e, 
00389                         gdtnode v
00390                         );                      
00391                                 
00392                         
00397                         gdtedge 
00398                 cand_edge_pred      
00399                         (
00400                         gdtedge e, 
00401                         gdtnode v
00402                         );                      
00403                                 
00404                         
00409                         face            
00410                 external_face  
00411                         (
00412                         ) const;        
00413                                 
00414                         
00419                         algorithm_type  
00420                 get_layout_algorithm 
00421                         (
00422                         ) const;        
00423                                 
00424                         
00429                         bend_constraint 
00430                 get_constraint_on_bends_of_edge 
00431                         (
00432                         gdtedge e
00433                         ) const;        
00434                 
00435                         
00440                         bool 
00441                 is_source                
00442                         (
00443                         gdtnode v
00444                         ) const;        
00445                                 
00446                         
00451                         bool 
00452                 is_target                
00453                         (
00454                         gdtnode v
00455                         ) const;        
00456                                         
00457                         
00462                         bool 
00463                 is_extremal      
00464                         (
00465                         gdtnode v
00466                         ) const;        
00467                                 
00468                         
00473                         bool 
00474                 is_internal      
00475                         (
00476                         gdtnode v
00477                         ) const;        
00478                                         
00479                         
00485                         bool 
00486                 is_extremal      
00487                         (
00488                         gdtnode v, 
00489                         gdtedge e
00490                         ) const;        
00491                         
00492                         
00498                         bool 
00499                 is_internal      
00500                         (
00501                         gdtnode v, 
00502                         gdtedge e
00503                         ) const;        
00504                         
00505                         
00510                         bool 
00511                 is_source                
00512                         (
00513                         gdtnode v, 
00514                         face f
00515                         ) const;  
00516                                 
00517                         
00522                         bool 
00523                 is_target           
00524                         (
00525                         gdtnode v,
00526                         face f
00527                         ) const;        
00528                                 
00529                         
00535                         bool 
00536                 is_extremal      
00537                         (
00538                         gdtnode v, 
00539                         face f
00540                         ) const;        
00541                         
00542                         
00548                         bool 
00549                 is_internal      
00550                         (
00551                         gdtnode v, 
00552                         face f
00553                         ) const;        
00554                         
00555                         
00561                         bool 
00562                 is_big_angle        
00563                         (
00564                         gdtnode v, 
00565                         face f
00566                         );                      
00567                         
00568                         
00574                         bool 
00575                 is_big_angle     
00576                         (
00577                         gdtnode v, 
00578                         gdtedge e
00579                         );                      
00580                         
00581                         
00587                         gdt::gdtlist<gdtedge> 
00588                 in_cand_edges 
00589                         (
00590                         gdtnode v
00591                         );                              
00592                                 
00593                         
00599                         gdt::gdtlist<gdtedge> 
00600                 out_cand_edges
00601                         (
00602                         gdtnode v
00603                         );                              
00604                                 
00605                         
00611                         int  
00612                 number_of_extremals 
00613                         (
00614                         ) const;        
00615                                 
00616                         
00623                         int  
00624                 number_of_extremals 
00625                         (
00626                         face f
00627                         ) const;         
00628                                         
00629                         
00634                         int  
00635                 number_of_bends 
00636                         (
00637                         ) const;                                                                
00638                                         
00639                         
00644                         int  
00645                 max_bends_on_edge 
00646                         (
00647                         ) const;        
00648                                 
00649                         
00656                         int  
00657                 capacity 
00658                         (
00659                         face f
00660                         ) const;        
00661                         
00662                         
00668                         int  
00669                 cost_of_last_algorithm
00670                         (
00671                         ) const;        
00672                 
00673                                         
00674                         
00681                         gdt::gdtlist<gdtnode>  
00682                 extremals  
00683                         (
00684                         face f
00685                         ) const;        
00686                         
00687                         
00693                         void        
00694                 extremals  
00695                         (
00696                         face f,
00697                         gdt::gdtlist<gdtnode>& ext, 
00698                         gdt::gdtmap<gdt::list_item,bool>& is_big
00699                         );                              
00700                         
00701                         
00706                         gdt::gdtlist<gdtnode>  
00707                 big_angles 
00708                         (
00709                         face f
00710                         );
00711                         
00712                         
00722                         bool
00723                 face_is_regular
00724                         (
00725                         face f, 
00726                         border_step& r1, 
00727                         border_step& r2
00728                         );      
00729                         
00741                         angle_type
00742                 angle_of_border_step
00743                         (
00744                         border_step bs 
00745                         );      
00746                         
00747                 
00756                         face
00757                 find_external_face
00758                         ();
00759                 
00760                                         
00761                         
00762                 /*
00763                 CATEGORY update
00764                 Update operations.
00765                 */
00766                                                                 
00767                         
00772                         void 
00773                 clear
00774                         (
00775                         );                              
00776                         
00777                         
00789                         void 
00790                 steal_from 
00791                         (
00792                         undi_graph& ug, 
00793                         algorithm_type alg = PLAN_UPWARD_OPTIMAL,
00794                         bool err_mess = true
00795                         );                      
00796                         
00797                         
00808                         void 
00809                 steal_from 
00810                         (
00811                         plan_undi_graph& pug, 
00812                         algorithm_type alg = PLAN_ORTH_OPTIMAL,
00813                         bool err_mess = true
00814                         );              
00815                         
00816                         
00828                         void 
00829                 steal_from 
00830                         (
00831                         plan_undi_graph& pug, 
00832                         face ef, 
00833                         algorithm_type alg = PLAN_ORTH_OPTIMAL,
00834                         bool err_mess = true
00835                         );                                      
00836                         
00837                         
00842                         void 
00843                 mirror  
00844                         (
00845                         upwa_plan_undi_graph& upug
00846                         );                                              
00847                                 
00848                         
00853                         void 
00854                 forget  
00855                         (
00856                         );                                                                      
00857                                 
00858                         
00863                         void 
00864                 set_external_face    
00865                         (
00866                         face ef
00867                         );                                                      
00868                                 
00869                         
00874                         void 
00875                 set_layout_algorithm 
00876                         (
00877                         algorithm_type alg
00878                         );                                              
00879 
00880                         
00887                         gdt::gdtlist<gdtedge> 
00888                 make_st
00889                         (
00890                         gdtnode& s, 
00891                         gdtnode& t
00892                         );                                                                      
00893                                         
00894         
00901                         gdt::gdtlist<gdtedge> 
00902                 make_st_with_regularity
00903                         (
00904                         gdtnode& s, 
00905                         gdtnode& t
00906                         );
00907 
00908         
00909                         
00915                         int 
00916                 apply_layout_algorithm 
00917                         (
00918                         bool err_mess = true
00919                         );       
00920                         
00927                         bool 
00928                 regularize_face
00929                         (
00930                         face f, 
00931                         gdt::gdtlist<gdtedge>& dummy_edges
00932                         );                              
00933                         
00940                         int
00941                 regularize_all_faces    
00942                         (
00943                         gdt::gdtlist<gdtedge>& dummy_edges
00944                         );
00945                         
00946                         
00947                         
00948                 /*
00949                 CATEGORY io_operations
00950                 Input / output operations.
00951                 */
00952                 
00953                         
00959                         void 
00960                 print 
00961                         (
00962                         print_mode mode=BY_FACES, 
00963                         bool candidate = false, 
00964                         std::ostream& os=std::cout
00965                         );      
00966                         
00967                         
00973                         void 
00974                 print 
00975                         (
00976                         gdtnode v, 
00977                         bool candidate = false, 
00978                         std::ostream& os=std::cout
00979                         );                              
00980                         
00981                         
00986                         void 
00987                 print 
00988                         (
00989                         gdtedge e,      
00990                         std::ostream& os=std::cout
00991                         ) const;                                        
00992                                 
00993                         
00998                         void 
00999                 print 
01000                         (
01001                         face f, 
01002                         std::ostream& os=std::cout
01003                         ) const;                                        
01004                                         
01005                         
01010                         void 
01011                 print 
01012                         (
01013                         separation_pair sp, 
01014                         std::ostream& os=std::cout
01015                         ) const;                                                                        
01016                                         
01017                         
01022                         void 
01023                 print 
01024                         (
01025                         constraint c, 
01026                         std::ostream& os = std::cout
01027                         ) const;                                        
01028 
01029 
01030         };
01031 
01032 
01033 
01034 #define forall_candidate_edges_entering_node(e,v,G)\
01035 for(e=(G).first_in_cand_edge(v);e;e=(G).cand_edge_succ(e,v))
01036 
01037 #define forall_candidate_edges_leaving_node(e,v,G)\
01038 for(e=(G).first_out_cand_edge(v);e;e=(G).cand_edge_succ(e,v))
01039 
01040 
01041 #endif

Generated on Thu Jan 10 14:48:02 2008 for GDToolkit GAPI by  doxygen 1.5.3