Graph Drawing Toolkit
00001 /******************************************************************************* 00002 + 00003 + rm3_SPQR_tree.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 + 00013 *******************************************************************************/ 00017 #ifndef RM3_SPQR_TREE_H 00018 #define RM3_SPQR_TREE_H 00019 00020 00021 #include <GDT/gdtmap.h> 00022 #include <GDT/gdtarray.h> 00023 #include <GDT/gdtnode_matrix.h> 00024 #include <GDT/gdt_graph_array.h> 00025 00026 #include <GDT/rm3_tree.h> 00027 #include <GDT/rm3_plan_undi_graph.h> 00028 00029 //----------------------------------------------------------------------------- 00030 // SPQR_tree: base class for SPQR trees. 00031 // 00032 // W.Didimo e A.Leonforte (1996) 00033 //----------------------------------------------------------------------------- 00034 00035 // --------------------------------------- 00036 // This file contains three classes. 00037 // Comments can be found just before each 00038 // one of them. 00039 // --------------------------------------- 00040 00041 00042 // ----------------------------------------- 00043 // enumerate types for split_component class 00044 // ----------------------------------------- 00045 00046 /* 00047 GLOBALTYPE split_component_edge_type 00048 Type of gdtedge in a split_component object. 00049 */ 00050 00051 typedef enum 00052 { 00053 REAL, 00054 VIRTUAL 00055 } 00056 split_component_edge_type; 00057 00058 00059 /* 00060 GLOBALTYPE split_component_type 00061 Type of split_component. 00062 */ 00063 00064 typedef enum 00065 { 00066 POLYGON, 00067 MAXIMAL_BOND, 00068 TRICONNECTED, 00069 NOT_COMPLETE 00070 } 00071 split_component_type; 00072 00073 00074 // ----------------------------------- 00075 // enumerate types for SPQR_tree class 00076 // ----------------------------------- 00077 00078 /* 00079 GLOBALTYPE SPQR_node_type 00080 Type of gdtnode in an SPQR_tree object. 00081 */ 00082 00083 typedef enum 00084 { 00085 S_NODE, 00086 P_NODE, 00087 Q_NODE, 00088 R_NODE 00089 } 00090 SPQR_node_type; 00091 00092 /* 00093 GLOBALTYPE rotation_type 00094 Useful rotation type. 00095 */ 00096 00097 typedef enum 00098 { 00099 CLOCKWISE, 00100 COUNTER_CLOCKWISE 00101 } 00102 rotation_type; 00103 00104 00105 // --------------------------------------------------- 00106 // useful types for B&B algorithms based on SPQR_trees 00107 // --------------------------------------------------- 00108 00109 00110 typedef gdt::gdtlist<int> 00111 BB_assignment; 00112 00113 00114 const int 00115 BB_NULL_STATUS = -1; 00116 00117 const int 00118 BB_NULL_EDGE = -1; 00119 00120 const int 00121 BB_CURRENT = 0, 00122 BB_RANDOM = 1, 00123 BB_NON_REP = 0, 00124 BB_INF = 0; 00125 00126 00127 typedef enum 00128 { 00129 BB_BFS, 00130 BB_DFS 00131 } 00132 BB_visit_type; 00133 00134 00135 typedef struct 00136 { 00137 int init_ref_edge; // initial reference gdtedge 00138 bool all_computations; // if true, execute all computations, one for each possible choice of reference gdtedge 00139 bool text_interface; // text interface switch (on/off) 00140 bool rppl; // replace with path in preprocessing lower bounds 00141 bool rpdl; // replace with path in dynamc lower bounds 00142 int fub; // first upper bound computation 00143 int sub; // successive upper bounds computations 00144 int niu; // number of initial upper bounds 00145 int ncs; // number of consecutive steps 00146 int ubf; // computation frequence of upper bound 00147 } 00148 BB_options; 00149 00150 00151 const BB_options STANDARD_BB_OPTIONS = 00152 { 00153 BB_NULL_EDGE, 00154 true, 00155 false, 00156 true, 00157 true, 00158 BB_CURRENT, 00159 BB_NON_REP, 00160 25, 00161 BB_INF, 00162 0 00163 }; 00164 00165 // SPLIT COMPONENTS 00166 // 00167 // ------------------------------------------------------------------------------------------------ 00168 // Here, a split_component object is a biconnected subgraph of a plan_undi_graph (owner graph), 00169 // with possibly virtual edges added. 00170 // Each virtual gdtedge has a pointer (link) to a corresponding gdtedge in another split component, and 00171 // each real gdtedge has a pointer to the corresponding gdtedge in the owner graph. 00172 // Also each gdtedge has a pointer to the split component that contains it. 00173 // In this context a split_component can be one among the following types: 00174 // - POLYGON : it is a polygon; 00175 // - MAXIMAL_BOND : it is a maximal series of multiple edges between two nodes; 00176 // - TRICONNECTED : it is a triconnected graph 00177 // - NOT_COMPLETE : no of the above cases is verified 00178 // Also, at each step, a split_component contains the list of its separation_pairs. 00179 // ------------------------------------------------------------------------------------------------ 00180 00181 class skeleton; //forward declaration 00182 class split_component; //forward declaration 00183 00184 /* 00185 GLOBALTYPE struct_split_node_info 00186 Local split_node structure for split_component. 00187 */ 00188 00189 class GDT_NONSTANDARD_DECL 00190 struct_split_node_info 00191 { 00192 friend class split_component; 00193 // 00194 gdtnode twin_node; // corresponding gdtnode in the decomposed graph (owner graph) 00195 }; 00196 00197 00198 /* 00199 GLOBALTYPE struct_split_edge_info 00200 Local split_edge structure for split_component. 00201 */ 00202 00203 00204 00205 00206 class GDT_NONSTANDARD_DECL 00207 struct_split_edge_info 00208 { 00209 friend class split_component; 00210 // 00211 split_component_edge_type type; // Real or virtual gdtedge. 00212 gdtedge twin_edge; // Edge corresponding in another split component if type = VIRTUAL; 00213 // if type = REAL, twin_edge = gdtedge into the owner graph. 00214 split_component* twin_edge_owner_split_component; // Pointer to the split_component that contains twin_edge if the gdtedge is 00215 // virtual, else null pointer. 00216 }; 00217 00218 00219 /* 00220 CLASS split_component 00221 A split_component object is a biconnected subgraph of a plan_undi_graph (owner graph), 00222 with possibly virtual edges added. 00223 Each virtual gdtedge has a pointer (link) to a corresponding gdtedge in another split component, and 00224 each real gdtedge has a pointer to the corresponding gdtedge in the owner graph. 00225 Also each gdtedge has a pointer to the split component that contains it. 00226 In this context a split_component can be one among the following types: 00227 - POLYGON : it is a polygon; 00228 - MAXIMAL_BOND : it is a maximal series of multiple edges between two nodes; 00229 - TRICONNECTED : it is a triconnected graph 00230 - NOT_COMPLETE : no of the above cases is verified 00231 Also, at each step, a split_component contains the list of its separation_pairs. 00232 */ 00233 00234 class GDT_NONSTANDARD_DECL 00235 split_component: public plan_undi_graph 00236 { 00237 friend class skeleton; 00238 00239 private: 00240 // ----------------- 00241 // private variables 00242 // ----------------- 00243 00244 plan_undi_graph* owner_graph; // owner graph of the split_component 00245 split_component_type type; // type of the split_component 00246 gdt::gdtnode_map<bool>* node_is_present; // node_is_present[v] = true if the gdtnode v of the owner graph belongs to the split_component: 00247 // (gdt::gdtnode_map is initializated on owner_graph.nodes_and_edges()). 00248 gdt::gdtlist<separation_pair>* separation_pairs; // list of all separation pairs of the split component 00249 00250 gdt::gdtnode_map<struct_split_node_info>* node_info; // correspondence gdtnode --> split_node-structure 00251 gdt::gdtedge_map<struct_split_edge_info>* edge_info; // correspondence gdtedge --> split_edge-structure 00252 00253 // --------------- 00254 // private methods 00255 // --------------- 00256 00257 void local_new (); // create a new set of pointers for the not-inherited class-part 00258 void local_del (); // delete all the not-inherited class-part 00259 void local_renew (); // utility function : just local_del(), then local_new() 00260 void local_init (plan_undi_graph&); // init the not-inherited class-part 00261 00262 void local_set // set all private variables 00263 ( 00264 plan_undi_graph*, 00265 split_component_type, 00266 gdt::gdtnode_map<bool>*, 00267 gdt::gdtlist<separation_pair>*, 00268 gdt::gdtnode_map<struct_split_node_info>*, 00269 gdt::gdtedge_map<struct_split_edge_info>* 00270 ); 00271 00272 void set_owner_graph (plan_undi_graph& pug); // set the split_component owner graph with pug pointer 00273 void set_type (split_component_type t); // set the split_component type with t 00274 void set_node_is_present (gdtnode v, bool flag); // set gdtnode v as present(true)/no-present(false) (v is a gdtnode of the owner_graph) 00275 void set_separation_pairs (const gdt::gdtlist<separation_pair>& sp_list); // set the split_component separation_pairs list with sp_list 00276 void set_twin_node (gdtnode v, gdtnode v1); // makes v1 as twin gdtnode of gdtnode v 00277 void set_twin_edge (gdtedge e, gdtedge e1); // makes e1 as twin gdtedge of gdtedge e 00278 void set_type_of_edge (gdtedge e, split_component_edge_type t); // set gdtedge type with t 00279 void set_twin_edge_owner_split_component (gdtedge e, split_component* sc_pointer); // set twin gdtedge's owner split component of gdtedge e with sc_pointer 00280 00281 protected: 00282 00283 // ------------------------- 00284 // Constructor and Operators 00285 // ------------------------- 00286 00287 split_component (); // empty constructor 00288 split_component (const split_component&); // copy construtor 00289 split_component& operator= (const split_component&); // copy equality operator 00290 00291 // ---------------------------------- 00292 // --------------------------------------------------- 00293 // These methods are needed to hide the corresponding 00294 // plan_undi_graph public methods. 00295 // --------------------------------------------------- 00296 00297 gdtnode new_node (gdtedge, int new_id=AUTO_ID); 00298 gdtedge new_edge (gdtnode, gdtnode, face, int new_id=AUTO_ID); 00299 00300 void del_node (gdtnode); 00301 void del_edge (gdtedge); 00302 00303 // 00304 00305 gdt::gdtlist<split_component*> decomposition_in_triconnected_components(); // kernel of method decompose_into_triconnected_components 00306 00307 public: 00308 00309 /* 00310 CATEGORY constructors_destructors 00311 Constructors and destructors 00312 */ 00313 00314 00315 /* 00316 METHOD ~split_component 00317 Destructor. 00318 */ 00319 00320 ~split_component(); 00321 00322 00323 /* 00324 METHOD split_component 00325 Constructor from the plan_undi_graph class: 00326 the new split component is initialized with pug plan_undi_graph; 00327 pug will be made as the owner graph of the split component, and the 00328 separation pairs of the split component will be all the separation 00329 pairs of pug. The new split_component has only real edges (i.e. all the edges of pug). 00330 */ 00331 00332 split_component 00333 ( 00334 plan_undi_graph& pug 00335 ); 00336 00337 00338 /* 00339 CATEGORY operators 00340 Operators. 00341 */ 00342 00343 00344 /* 00345 METHOD operator= 00346 Equality operator from the plan_undi_graph class: 00347 the new split component is initialized with pug plan_undi_graph; 00348 pug will be made as the owner graph of the split component, and the 00349 separation pairs of the split component will be all the separation 00350 pairs of pug. The new split_component has only real edges (i.e. all the edges of pug). 00351 */ 00352 00353 split_component& 00354 operator= 00355 ( 00356 plan_undi_graph& 00357 ); 00358 00359 /* 00360 CATEGORY access 00361 Access operations. 00362 */ 00363 00364 00365 /* 00366 METHOD local_get 00367 Get all private variables. 00368 */ 00369 00370 void 00371 local_get 00372 ( 00373 plan_undi_graph*&, 00374 split_component_type&, 00375 gdt::gdtnode_map<bool>*&, 00376 gdt::gdtlist<separation_pair>*&, 00377 gdt::gdtnode_map<struct_split_node_info>*&, 00378 gdt::gdtedge_map<struct_split_edge_info>*& 00379 ); 00380 00381 00382 /* 00383 METHOD get_owner_graph 00384 Return a reference to the owner graph of the split_component. 00385 */ 00386 00387 plan_undi_graph& 00388 get_owner_graph 00389 ( 00390 )const; 00391 00392 00393 /* 00394 METHOD get_type 00395 Return the type of the split_component. 00396 */ 00397 00398 split_component_type 00399 get_type 00400 ( 00401 )const; 00402 00403 00404 /* 00405 METHOD get_type_of_edge 00406 Return the type of gdtedge e of the split_component. 00407 */ 00408 00409 split_component_edge_type 00410 get_type_of_edge 00411 ( 00412 gdtedge e 00413 )const; 00414 00415 00416 /* 00417 METHOD get_twin_edge_owner_split_component 00418 Return a pointer to the twin gdtedge's owner split component of gdtedge e 00419 if e is virtual gdtedge, else return NULL. 00420 */ 00421 00422 split_component* 00423 get_twin_edge_owner_split_component 00424 ( 00425 gdtedge e 00426 )const; 00427 00428 00429 /* 00430 METHOD getseparation_pairs 00431 Return the list of separation_pairs of the split_component 00432 */ 00433 00434 gdt::gdtlist<separation_pair> 00435 get_separation_pairs 00436 ( 00437 )const; 00438 00439 00440 /* 00441 METHOD get_node_is_present 00442 Return true if gdtnode v of the owner_graph is present in the split component. 00443 */ 00444 00445 bool 00446 get_node_is_present 00447 ( 00448 gdtnode v 00449 )const; 00450 00451 00452 /* 00453 METHOD contain_separation_pair 00454 Return true if sp is a separation pair of the split component. 00455 */ 00456 00457 bool 00458 contain_separation_pair 00459 ( 00460 separation_pair sp 00461 ) const; 00462 00463 00464 /* 00465 METHOD get_twin_node 00466 Return the twin gdtnode of gdtnode v. 00467 */ 00468 00469 gdtnode 00470 get_twin_node 00471 ( 00472 gdtnode v 00473 )const; 00474 00475 00476 /* 00477 METHOD get_twin_edge 00478 Return the twin gdtedge of gdtedge e. 00479 */ 00480 00481 gdtedge 00482 get_twin_edge 00483 ( 00484 gdtedge e 00485 )const; 00486 00487 00488 /* 00489 METHOD edge_associated_to_owner_graph_edge 00490 If the owner_graph gdtedge e is present in the separation_pair return it, 00491 else return NULL_EDGE. 00492 */ 00493 00494 gdtedge 00495 edge_associated_to_owner_graph_edge 00496 ( 00497 gdtedge e 00498 )const; 00499 00500 00501 /* 00502 CATEGORY update 00503 Update operations. 00504 */ 00505 00506 00507 /* 00508 METHOD clear 00509 Clear all nodes and edges. 00510 */ 00511 00512 void 00513 clear 00514 ( 00515 ); 00516 00517 00518 00519 /* 00520 METHOD mirror 00521 Copy all private variables of SPQR_tree in *this. 00522 */ 00523 00524 void 00525 mirror 00526 ( 00527 split_component& 00528 ); 00529 00530 00531 00532 /* 00533 METHOD forget 00534 Cut all private variables in *this. 00535 */ 00536 00537 void 00538 forget 00539 ( 00540 ); 00541 00542 00543 00544 /* 00545 METHOD split_on_separation_pair 00546 Split the current split component into 00547 two new split components, (*this) and 00548 (*sc1_pointer). 00549 Return true if the splitting is really 00550 executed. 00551 PRECONDITIONS: sp is a separation pair 00552 of the current split component. 00553 */ 00554 00555 bool 00556 split_on_separation_pair 00557 ( 00558 separation_pair sp, 00559 split_component*& sc1_pointer, 00560 int new_id = AUTO_ID 00561 ); 00562 00563 00564 /* 00565 METHOD merge_with_polygon_on_edge 00566 Merge the current split component with 00567 the split component (*sc1_pointer). 00568 Return true if the merging is really 00569 executed. 00570 PRECONDITION: (*this) and (*sc1_pointer) 00571 are POLYGON type, and e is 00572 a virtual gdtedge present in both. 00573 */ 00574 00575 bool 00576 merge_with_polygon_on_edge 00577 ( 00578 split_component*& sc1_pointer, 00579 gdtedge e 00580 ); 00581 00582 00583 /* 00584 METHOD decompose_into_triconnected_components 00585 Compute the decomposition of the split 00586 component into its triconnected 00587 components,and return the 00588 list of such split components (that are 00589 all different from NOT_COMPLETE type). 00590 */ 00591 00592 gdt::gdtlist<split_component*> 00593 decompose_into_triconnected_components 00594 ( 00595 ); 00596 00597 00598 /* 00599 CATEGORY io_operations 00600 Input / output operations. 00601 */ 00602 00603 00604 /* 00605 METHOD print 00606 Print the graph on ostream os; print_mode can 00607 be BY_NODES, BY_EDGE, BY_FACES, COMPLETE. 00608 If split_component_information is true, 00609 useful information are printed about the 00610 structure of the split_component. 00611 */ 00612 00613 void 00614 print 00615 ( 00616 print_mode mode = BY_FACES, 00617 bool split_component_information = true, 00618 std::ostream& os = std::cout 00619 ); 00620 00621 }; 00622 00623 00624 00625 // SKELETON 00626 // A skeleton is a complete split component (triconnected component) with a fixed 00627 // reference gdtedge e=(v,w). The extremal vertices v and w are called "POLES" of the skeleton. 00628 // 00629 00630 00631 00632 class SPQR_tree; // forward declaration 00633 00634 /* 00635 CLASS skeleton 00636 A skeleton is a complete split component (triconnected component) with a fixed 00637 reference gdtedge e=(v,w). The extremal vertices v and w are called "POLES" of the skeleton. 00638 */ 00639 00640 class GDT_NONSTANDARD_DECL 00641 skeleton: public split_component 00642 { 00643 friend class SPQR_tree; 00644 00645 private: 00646 // ----------------- 00647 // private variables 00648 // ----------------- 00649 00650 gdtedge ref_edge; // reference gdtedge 00651 00652 // --------------- 00653 // private methods 00654 // --------------- 00655 00656 void local_new (); // create a new set of pointers for the not-inherited class-part 00657 void local_del (); // delete all the not-inherited class-part 00658 void local_renew (); // utility function : just local_del(), then local_new() 00659 void local_init (const split_component&, gdtedge); // init the not-inherited class-part 00660 00661 public: 00662 00663 00664 /* 00665 CATEGORY constructors_destructors 00666 Constructors and destructors. 00667 */ 00668 00669 00670 /* 00671 METHOD ~skeleton 00672 Destructor. 00673 */ 00674 00675 ~skeleton 00676 ( 00677 ); 00678 00679 00680 /* 00681 METHOD skeleton 00682 Empty constructor. 00683 */ 00684 00685 skeleton 00686 ( 00687 ); 00688 00689 00690 /* 00691 METHOD skeleton 00692 Constructor from the split_component class: 00693 make a new skeleton, initializing it with sc 00694 and make e as its reference gdtedge. 00695 PRECONDITIONS: e is an gdtedge of sc. 00696 */ 00697 00698 skeleton 00699 ( 00700 const split_component& sc, 00701 gdtedge e 00702 ); 00703 00704 00705 /* 00706 CATEGORY access 00707 Access operations. 00708 */ 00709 00710 00711 /* 00712 METHOD get_pole1 00713 Return the pole 1 of the skeleton. 00714 */ 00715 00716 gdtnode 00717 get_pole1 00718 ( 00719 ) const; 00720 00721 00722 00723 /* 00724 METHOD get_pole2 00725 Return the pole 2 of the skeleton. 00726 */ 00727 00728 gdtnode 00729 get_pole2 00730 ( 00731 ) const; 00732 00733 00734 /* 00735 METHOD get_reference_edge 00736 Return the reference gdtedge of the skeleton. 00737 */ 00738 00739 gdtedge 00740 get_reference_edge 00741 ( 00742 ) const; 00743 00744 00745 /* 00746 CATEGORY update 00747 Update operations. 00748 */ 00749 00750 00751 /* 00752 METHOD clear 00753 Delete all nodes and edges. 00754 */ 00755 00756 void 00757 clear 00758 ( 00759 ); 00760 00761 00762 /* 00763 METHOD steal_from 00764 Make *this with the split_component sc internal variables 00765 and cut these variables from sc. 00766 This method is used to make a split_component as a skeleton, manteining the same internal variables. 00767 WARNING: sc has an empty body after this method is applied 00768 */ 00769 00770 void 00771 steal_from 00772 ( 00773 split_component& sc, 00774 gdtedge e 00775 ); 00776 00777 00778 /* 00779 METHOD set_reference_edge 00780 Set the reference gdtedge with the gdtedge e. 00781 */ 00782 00783 void 00784 set_reference_edge 00785 ( 00786 gdtedge e 00787 ); 00788 00789 /* 00790 CATEGORY io_operations 00791 Input / output operations. 00792 */ 00793 00794 00795 /* 00796 METHOD print 00797 Print the graph on ostream os; print_mode can 00798 be BY_NODES, BY_EDGE, BY_FACES, COMPLETE. 00799 If skeletont_information is true, 00800 useful information are printed about the 00801 structure of the skeleton. 00802 */ 00803 00804 void 00805 print 00806 ( 00807 print_mode mode = BY_FACES, 00808 bool skeleton_information = true, 00809 std::ostream& os = std::cout 00810 ); 00811 00812 00813 }; 00814 00815 00816 00817 // ----------------------------------------------------------------------------------------------------- 00818 // Classes for SPQR_tree. An SPQR tree represents all embeddings of a plan_undi_graph such that they 00819 // have a reference gdtedge on the external face. Each gdtnode of the SPQR_tree has an associated skeleton. 00820 // ----------------------------------------------------------------------------------------------------- 00821 00822 00823 typedef enum 00824 { 00825 MSP12, 00826 MSP21, 00827 SP, 00828 NULL_PATH 00829 } 00830 path_type; 00831 00832 00833 struct 00834 path_info 00835 { 00836 gdt::gdtlist<gdtedge> msp12; // minimum switches path from pole1 to pole2, leaving from pole1 00837 gdt::gdtlist<gdtedge> msp21; // minimum switches path from pole1 to pole2, entering in pole1 00838 gdt::gdtlist<gdtedge> sp; // shortest path from pole1 to pole2 (undirected) 00839 int sw12; // number of switches in path msp12; 00840 int sw21; // number of switches in path msp21; 00841 path_type current_path; // keep a reference to one of the above paths or NULL_PATH; 00842 }; 00843 00844 00845 00846 struct 00847 R_node_info 00848 { 00849 rotation_type rotation; // specify the adjacency lists rotation order. 00850 // if rotation = COUNTER_CLOCKWISE the order in adjacency lists 00851 // of the skeleton is kept; 00852 // if rotation = CLOCKWISE this order is reversed. 00853 }; 00854 00855 00856 struct 00857 P_node_info 00858 { 00859 gdt::gdtlist<gdtedge> permutation; // specific the edges permutation order starting from the reference gdtedge. 00860 // NOTE: the reference gdtedge is not insert into the permutation list; 00861 // moreover, it and the last gdtedge into the permutation list are the edges 00862 // on the external face. 00863 }; 00864 00865 00866 /* 00867 GLOBALTYPE struct_SPQR_node_info 00868 Local-SPQR structure for gdtnode. 00869 */ 00870 00871 class GDT_NONSTANDARD_DECL 00872 struct_SPQR_node_info 00873 { 00874 friend class SPQR_tree; 00875 // 00876 SPQR_node_type type; // Type SPQR gdtnode 00877 // (S = series, P = parallel, Q = single gdtedge, R = rigid). 00878 skeleton* skel; // Skeleton pointer. 00879 // NOTE: if type = Q_node, skel = NULL. 00880 gdt::gdtedge_map<gdtedge> tree_edge; // Each gdtedge of the skeleton has a corresponding gdtedge of the SPQR_tree. 00881 gdt::gdtmap<int,R_node_info> R_status; // An R_node has two status, (*R_status[0]) and (*R_status[1]), 00882 // containing all the information on the current embedding of the skeleton. 00883 // NOTE: if (type != R_node), R_status = NULL. 00884 gdt::gdtmap<int,P_node_info> P_status; // A P_node has (n-1)! status, with n = number of edges into the skeleton. 00885 // NOTE: if (type != P_node), P_status = NULL. 00886 int maximum_status; // indicate the maximum status of the gdtnode. 00887 00888 public: 00889 struct_SPQR_node_info(skeleton*); 00890 00891 }; 00892 00893 00894 /* 00895 GLOBALTYPE struct_SPQR_edge_info 00896 Local-SPQR structure for gdtedge. 00897 */ 00898 00899 class GDT_NONSTANDARD_DECL 00900 struct_SPQR_edge_info 00901 { 00902 friend class SPQR_tree; 00903 // 00904 gdtedge edge_corr_in_father_skeleton; // corresponding gdtedge into the skeleton of the father_node. 00905 }; 00906 00907 00908 00909 class GDT_NONSTANDARD_DECL 00910 SPQR_tree: public tree 00911 { 00912 private: 00913 gdt::gdtnode_map<struct_SPQR_node_info*>* node_info; 00914 gdt::gdtedge_map<struct_SPQR_edge_info>* edge_info; 00915 bool simpl_node_status; // simplify for gdtnode-status 00916 00917 // --------------- 00918 // private methods 00919 // --------------- 00920 00921 void local_new (); 00922 void local_del (); 00923 void local_renew (); 00924 void local_init (plan_undi_graph& pug, gdtedge e, bool simpl); 00925 00926 void set_type_of_node (gdtnode v, SPQR_node_type t); // sets the v node_type with t. 00927 void set_skeleton_of_node (gdtnode v, skeleton* skp); // sets the v skeleton pointer with skp. 00928 void set_tree_edge_of_skeleton_edge_in_node (gdtedge es, gdtedge et, gdtnode v); // sets the tree's gdtedge corresponding to 00929 // skeleton's gdtedge e in gdtnode v with te. 00930 void set_skeleton_edge_of_tree_edge (gdtedge et, gdtedge es); // sets with e the skeleton's gdtedge corresponding to 00931 // tree's gdtedge et in its father gdtnode. 00932 00933 void create_node_status (gdtnode v); // create all gdtnode status, i.e. make the mapping 00934 // int --> R/P_node_info. 00935 // if semplificate==true, the real edges with same direction 00936 // are grouped into an equivalence class 00937 00938 00939 00940 SPQR_node_type from_split_component_type_to_SPQR_node_type (split_component_type t) const; // ------------------------------------------- 00941 // return the SPQR_node_type corresponding to 00942 // split_component_type. 00943 // ------------------------------------------- 00944 00945 00946 std::string from_SPQR_node_type_to_string (SPQR_node_type) const; // return 'S', 'P', 'Q' or 'R' char. 00947 00948 gdtnode new_son_of_node (gdtnode v, skeleton* skp); // make a new SPQR_son_node of gdtnode v, 00949 // and associate it the skeleton (*skp). 00950 00951 00952 00953 00954 void BB_build_base_code_vector (gdt::gdtarray<gdtnode>&, BB_visit_type); 00955 void BB_compute_number_of_nodes_into_BB_subtrees (gdt::gdtarray<gdtnode>&, gdt::gdtmap<int,int>&); 00956 void BB_compute_status_of_node_vector (gdt::gdtarray<gdtnode>&, BB_assignment, gdt::gdtnode_array<int>&); 00957 void BB_compute_first_total_upper_bound (gdtedge&, const plan_undi_graph& , plan_undi_graph&, face&, int&, int&, BB_options&, algorithm_type&); 00958 00959 00960 BB_assignment BB_generate_complete_assignment (gdt::gdtarray<gdtnode>&, BB_assignment, gdt::gdtnode_array<int>&, BB_options&); 00961 00962 int BB_compute_upper_bound (gdt::gdtarray<gdtnode>&, BB_assignment, gdt::gdtnode_array<int>&, int, int, gdt::gdtnode_array<int>&, BB_options&, algorithm_type = PLAN_ORTH_SLOW); 00963 //int BB_compute_lower_bound (gdt::gdtarray<gdtnode>&, BB_assignment, gdt::gdtnode_matrix<int>&, gdt::gdtnode_matrix<path_info>&, int, int, BB_options&, set<int>&, bool = true, algorithm_type = PLAN_ORTH_SLOW); 00964 00965 // modified by W.D. on April 17, 2003. Use gdt mapping instead of leda sets. 00966 int BB_compute_lower_bound (gdt::gdtarray<gdtnode>&, BB_assignment, gdt::gdtnode_matrix<int>&, gdt::gdtnode_matrix<path_info>&, int, int, BB_options&, gdt::gdtmap<int,bool>&, bool = true, algorithm_type = PLAN_ORTH_SLOW); 00967 00968 00969 protected: 00970 void compute_tree_dimensions (gdt::gdtnode_array<int>& width_of_subtree, 00971 gdt::gdtnode_array<int>& lev, gdt::gdtnode_array<int> width_of_node, 00972 bool print_Q_node); 00973 00974 00975 00976 00977 public: 00978 ~SPQR_tree (); 00979 SPQR_tree (plan_undi_graph&, gdtedge=NULL_EDGE, bool simpl = false); 00980 00981 00982 // ----------------- 00983 // Access operations 00984 // ----------------- 00985 00986 SPQR_node_type get_type_of_node (gdtnode v) const; // return the type of gdtnode v 00987 skeleton* get_skeleton_of_node (gdtnode v) const; // return the pointer of the skeleton of gdtnode v (NULL if v is a Q_node) 00988 00989 bool get_simpl_node_status () const; // return the value of simpl_node_status (simplificate gdtnode status) 00990 00991 gdtedge tree_edge_of_skeleton_edge_in_node (gdtedge e, gdtnode v) const; // return the tree gdtedge corresponding to the 00992 // skeleton gdtedge e in gdtnode v. 00993 00994 gdtedge skeleton_edge_of_tree_edge (gdtedge e) const; // return the skeleton gdtedge corresponding to the 00995 // tree gdtedge e 00996 00997 gdtnode Q_node_of_edge_with_id (int ide) const; // return the Q_node corresponding to the gdtedge with id ide 00998 // if it doesn't exist, return NULL_NODE. 00999 01000 01001 rotation_type get_status_R_node_rotation (int i, gdtnode v) const; // return the rotation_type (CLOCKWISE, COUNTERCLOCKWISE) of status i in the R-gdtnode v 01002 gdt::gdtlist<gdtedge> get_status_P_node_permutation (int i, gdtnode v) const; // return the gdtedge-list permutation of status i in P-gdtnode v 01003 01004 int number_of_nodes_type (SPQR_node_type nt) const; // return the number of the nodes of type nt. 01005 int max_status_of_node (gdtnode v) const; // return the maximum status number of gdtnode v. 01006 01007 bool tree_edge_is_virtual (gdtedge te) const; // return true if skeleton_edge of tree_edge e is virtual. 01008 01009 01010 // ------------------------------- 01011 // DO NOT LIST IN PUBLIC METHODS 01012 // (see src code for more details) 01013 // ------------------------------- 01014 // 01015 void compute_pre_lower_bound_type_l (gdt::gdtnode_matrix<int>& l, algorithm_type = PLAN_ORTH_SLOW); 01016 void compute_pre_lower_bound_type_L (gdt::gdtnode_matrix<int>& L, gdt::gdtnode_matrix<int>& l, gdt::gdtnode_matrix<path_info>& P, bool = true, algorithm_type = PLAN_ORTH_SLOW); 01017 // 01018 01019 01020 bool merge_undi_graph_with_skeleton_of_node ( 01021 undi_graph& ug, 01022 gdtnode v, 01023 int i, 01024 gdtedge& start_edge, 01025 gdtnode& start_node, 01026 gdt::gdtedge_map<gdtedge>& tree_edge 01027 ); // see below.. 01028 01029 // ------------------------------------------------------ 01030 // replace the ug gdtedge,corresponding to the reference 01031 // gdtedge of skeleton(v), with skeleton(v) itself; 01032 // merging is computed with respect to the status i 01033 // of the gdtnode v (embedding of the skeleton); 01034 // tree_edge[e] will be the gdtedge of the SPQR_tree 01035 // corresponding to the gdtedge e of ug; 01036 // start_edge will be the reference gdtedge that must 01037 // belong to the external face. Because there are 01038 // two faces containing start_edge, it needs 01039 // to specify the start_node of start_edge, in order 01040 // to correctly rebuild the external face. 01041 // If v is an S_NODE, the status i is ignored. 01042 // If ug is empty, it is inizialized with the skeleton 01043 // of the gdtnode v. 01044 // The function returns true if the merging is correctly 01045 // executed. 01046 // 01047 // PRECONDITIONS: there exists an gdtedge e of ug such that 01048 // id(e) = id(ref_edge) in skeleton 01049 // of gdtnode v, or ug is empty. 01050 // Therefore, v is not a Q_NODE. 01051 // ------------------------------------------------------ 01052 01053 01054 01055 bool build_undi_graph_starting_from_node ( 01056 undi_graph& ug, 01057 gdtnode v, 01058 gdt::gdtnode_array<int>& status_of_node, 01059 gdtedge& start_edge, 01060 gdtnode& start_node, 01061 gdt::gdtedge_map<gdtedge>& tree_edge 01062 ); // see below.. 01063 01064 // ------------------------------------------------- 01065 // build the undi_graph ug, merging all nodes of the 01066 // subtree rooted at v, according to the 01067 // status_of_node array. 01068 // tree_edge[e] will be the gdtedge of the SPQR_tree 01069 // corresponding to the gdtedge e of ug; 01070 // start_edge will be the reference gdtedge that must 01071 // belong to the external face. Because there are 01072 // two faces containing start_edge, it needs 01073 // to specify the start_node of start_edge, in order 01074 // to correctly rebuild the external face. 01075 // The function returns true if the building is 01076 // correctly executed. 01077 // ------------------------------------------------- 01078 01079 01080 void pertinent_graph_of_node (undi_graph& ug, gdtnode v); 01081 01082 // -------------------------------------------------- 01083 // compute the pertinent graph of gdtnode v, 01084 // i.e., the graph obtained merging all the skeletons 01085 // of nodes into the subtree rooted at v. 01086 // vector. 01087 // The function returns true if the building is 01088 // correctly executed. 01089 // -------------------------------------------------- 01090 01091 01092 01093 01094 gdt::gdtlist<int> find_shortest_path_into_pertinent_graph_of_node ( 01095 gdtnode w, 01096 int id_v1, 01097 int id_v2, 01098 gdt::gdtlist<int>& edge_id_path 01099 ); // see below.. 01100 01101 // -------------------------------------------------- 01102 // find and return a list of gdtnode-id, representing a 01103 // shortest path from gdtnode with id_v1 and gdtnode with 01104 // id_v2 into the pertinent graph of gdtnode w. 01105 // Also return in edge_id_path the ordered list of 01106 // the gdtedge in the shortest path. 01107 // -------------------------------------------------- 01108 01109 01110 gdt::gdtlist<gdtedge> find_shortest_path_into_pertinent_graph_of_node ( 01111 gdtnode w, 01112 int id_v1, 01113 int id_v2 01114 ); // see below.. 01115 01116 // -------------------------------------------------- 01117 // find and return a list of edges, representing a 01118 // shortest path from gdtnode with id_v1 and gdtnode with 01119 // id_v2 into the pertinent graph of gdtnode w. 01120 // -------------------------------------------------- 01121 01122 01123 01124 gdt::gdtlist<gdtedge> find_minimum_switches_path_into_pertinent_graph_of_node ( 01125 gdtnode w, 01126 int id_v1, 01127 int id_v2, 01128 int& switches, 01129 visit_direction_type 01130 ); // see below.. 01131 01132 // --------------------------------------------------- 01133 // find and return a list of edges, representing a 01134 // path with minimum number of switches from gdtnode 01135 // with id_v1 and gdtnode with id_v2 into the pertinent 01136 // graph of gdtnode w, and following the 01137 // visit_direction_type specified. 01138 // switches will be the number of swithces of the path 01139 // --------------------------------------------------- 01140 01141 01142 01143 int find_best_embedding_with_external_face 01144 ( 01145 plan_undi_graph& pug, 01146 face& ext_face, 01147 BB_options Op = STANDARD_BB_OPTIONS, 01148 algorithm_type=PLAN_ORTH_SLOW, 01149 BB_tree_parameters* BBp=NULL 01150 ); // see below.. 01151 01152 // --------------------------------- Kernel of Slow Algorithms --------------------------------- 01153 // ------------------------------------------------------------------------------------------------- 01154 // search the plan_undi_graph pug and its face ext_face in such a way that: 01155 // 01156 // 1) pug has the same nodes and edges as the owner graph of Tp; 01157 // 2) the embedding of pug with external face ext_face produces the orth_plan_undi_graph 01158 // or upwa_plan_undi with the minimum number of bends over all the possible drawings. 01159 // 01160 // The function returns the total number of (non-zero cost) bends in an optimal drawing 01161 // of pug with external face ext_face. 01162 // 01163 // NOTE: This is an NP-HARD problem and thus this is a non polynomial function in general. 01164 // Also, this function uses a Branch and Bound technique. 01165 // 01166 // NOTICE: This function may requir a very long time if the graph has a high number of nodes and/or 01167 // a high number of triconnected components. 01168 // 01169 // PRECONDITIONS: The graph must be biconnected 01170 // 01171 // ------------------------------------------------------------------------------------------------- 01172 01173 01174 // ----------------- 01175 // Update operations 01176 // ----------------- 01177 01178 void clear (); // delete all nodes and edges 01179 01180 void make_root (gdtnode v); // make v as root of tree, updating all the pointers and reference edges 01181 // PRECONDITIONS: v must be a Q_NODE. 01182 01183 01184 void set_simpl_node_status (bool); // set simpl_node_status with bool (simplificate gdtnode status); 01185 01186 // -------------------------- 01187 // Input / Output opearations 01188 // -------------------------- 01189 01190 void print (SPQR_node_type, std::ostream& os = std::cout); 01191 void print_node_status (gdtnode v,std::ostream& os = std::cout); 01192 01193 }; 01194 01195 01196 #endif
1.5.3