Graph Drawing Toolkit
00001 /******************************************************************************* 00002 + 00003 + rm3_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 + All rights reserved. 00013 + 00014 *******************************************************************************/ 00017 #ifndef RM3_TREE_H 00018 #define RM3_TREE_H 00019 00020 00021 #include <GDT/rm3_undi_graph.h> 00022 00023 /* 00024 SOURCEFILE rm3_tree.h 00025 To be defined. 00026 */ 00027 00028 //----------------------------------------------------------------------------- 00029 // tree: base class for embedded trees. 00030 // 00031 // W.Didimo e A.Leonforte (1996) 00032 //----------------------------------------------------------------------------- 00033 00034 00035 00041 class GDT_NONSTANDARD_DECL 00042 struct_tree_node_info 00043 { 00044 friend class tree; 00045 // 00046 gdtedge father; //father gdtedge of gdtnode in rooted tree 00047 int level; //depth level of gdtnode in rooted tree 00048 }; 00049 00050 00051 00061 class GDT_NONSTANDARD_DECL 00062 tree: public undi_graph 00063 { 00064 private: 00065 gdtnode root; // root of tree 00066 gdt::gdtnode_map<struct_tree_node_info>* node_info; 00067 00068 // -------------- 00069 // private metods 00070 // -------------- 00071 00072 void local_new (); // create a new set of pointers for the not-inherited class-part 00073 void local_del (); // delete all the not-inherited class-part 00074 void local_renew (); // utility function : just local_del(), then local_new() 00075 00076 void local_init(gdtnode=NULL_NODE); // init the not-inherited class-part 00077 00078 void local_set // set all private variables 00079 ( 00080 gdtnode, 00081 gdt::gdtnode_map<struct_tree_node_info>* 00082 ); 00083 00084 void set_father_edge (gdtnode v, gdtedge e); // make e the father gdtedge of gdtnode v 00085 void set_level (gdtnode v, int i); // make i the level of gdtnode v 00086 00087 void set_levels_in_subtree (gdtnode v = NULL_NODE, int i = 0); // compute and set the gdtnode-levels in subtree rooted at v, 00088 // assuming level(v)=0. 00089 // NOTE: if v = NULL_NODE set v as root 00090 00091 00092 00093 // --------------------------------------------------- 00094 // These methods are needed to hide undi_graph methods 00095 // --------------------------------------------------- 00096 00097 void new_node () {}; 00098 void new_edge () {}; 00099 00100 00101 protected: 00102 //void compute_tree_dimension (gdt::gdtnode_array<int>& width_of_subtree, gdt::gdtnode_array<int>& lev, gdt::gdtnode_array<int> width_of_node); 00103 //void compute_node_coordinates (gdt::gdtnode_array<double>& x,gdt::gdtnode_array<double>& y, gdt::gdtnode_array<int> width_of_subtree, gdt::gdtnode_array<int>& lev); 00104 //void normalize_node_coordinates (gdt::gdtnode_array<double>& x,gdt::gdtnode_array<double>& y, double scale, double xinit, double yinit); 00105 00106 public: 00107 00108 /* 00109 CATEGORY constructors_destructors 00110 Constructors and destructors. 00111 */ 00112 00113 00118 tree 00119 ( 00120 ); 00121 00122 00127 ~tree 00128 ( 00129 ); 00130 00131 00137 tree 00138 ( 00139 const undi_graph& ug, 00140 gdtnode v 00141 ); 00142 00143 00148 tree 00149 ( 00150 const tree& tr 00151 ); 00152 00153 /* 00154 CATEGORY operators 00155 Operators. 00156 */ 00157 00158 00164 tree& 00165 operator = 00166 ( 00167 const undi_graph& 00168 ); 00169 00170 00175 tree& 00176 operator = 00177 ( 00178 const tree& 00179 ); 00180 00181 /* 00182 CATEGORY access 00183 Access operations. 00184 */ 00185 00186 00191 void 00192 local_get 00193 ( 00194 gdtnode p1, 00195 gdt::gdtnode_map<struct_tree_node_info>* p2 00196 ); 00197 00198 00203 gdtnode 00204 root_of_tree 00205 ( 00206 ) const; 00207 00208 00213 gdtnode 00214 father_node 00215 ( 00216 gdtnode v 00217 ) const; 00218 00219 00224 gdtnode 00225 father_node 00226 ( 00227 gdtedge e 00228 ) const; 00229 00230 00235 gdtnode 00236 first_son_node 00237 ( 00238 gdtnode v 00239 ) const; 00240 00241 00246 gdtnode 00247 last_son_node 00248 ( 00249 gdtnode v 00250 ) const; 00251 00252 00257 gdtnode 00258 son_succ 00259 ( 00260 gdtnode w, 00261 gdtnode v 00262 ) const; 00263 00264 00269 gdtnode 00270 son_pred 00271 ( 00272 gdtnode w, 00273 gdtnode v 00274 ) const; 00275 00276 00281 gdtedge 00282 father_edge 00283 ( 00284 gdtnode v 00285 ) const; 00286 00287 00292 gdtedge 00293 father_edge 00294 ( 00295 gdtedge e 00296 ) const; 00297 00298 00303 gdtedge 00304 first_son_edge 00305 ( 00306 gdtnode v 00307 ) const; 00308 00309 00314 gdtedge 00315 last_son_edge 00316 ( 00317 gdtnode v 00318 ) const; 00319 00320 00325 gdtedge 00326 son_succ 00327 ( 00328 gdtedge e, 00329 gdtnode v 00330 ) const; 00331 00332 00337 gdtedge 00338 son_pred 00339 ( 00340 gdtedge e, 00341 gdtnode v 00342 ) const; 00343 00344 00349 int 00350 get_level 00351 ( 00352 gdtnode v 00353 ) const; 00354 00355 00360 int 00361 number_of_sons 00362 ( 00363 gdtnode v 00364 ) const; 00365 00366 00373 int 00374 depth_of_subtree 00375 ( 00376 gdtnode v = NULL_NODE, 00377 int i = 0 00378 ) const; 00379 00380 00392 int 00393 BFS_of_subtree 00394 ( 00395 gdt::gdtnode_array<int>& lev, 00396 gdt::gdtlist<gdtnode>& order, 00397 gdtnode v = NULL_NODE, 00398 int i = 0 00399 ) const; 00400 00401 00413 int 00414 DFS_of_subtree 00415 ( 00416 gdt::gdtnode_array<int>& lev, 00417 gdt::gdtlist<gdtnode>& order, 00418 gdtnode v = NULL_NODE, 00419 int i = 0 00420 ) const; 00421 00422 00434 int 00435 post_order_of_subtree 00436 ( 00437 gdt::gdtnode_array<int>& lev, 00438 gdt::gdtlist<gdtnode>& order, 00439 gdtnode v = NULL_NODE, 00440 int i = 0 00441 ) const; 00442 00443 /* 00444 CATEGORY update 00445 Update operations. 00446 */ 00447 00448 00455 gdtnode 00456 new_son_of_node 00457 ( 00458 gdtnode v, 00459 int new_node_id = AUTO_ID, 00460 int new_edge_id = AUTO_ID 00461 ); 00462 00463 00471 gdtnode 00472 new_son_of_node 00473 ( 00474 gdtnode v, 00475 gdtnode w, 00476 int new_node_id = AUTO_ID, 00477 int new_edge_id = AUTO_ID, 00478 int dir = gdt::after 00479 ); 00480 00485 void 00486 make_root 00487 ( 00488 gdtnode v 00489 ); 00490 00491 00496 void 00497 del_subtree 00498 ( 00499 gdtnode v 00500 ); 00501 00502 00507 void 00508 clear 00509 ( 00510 ); 00511 00512 00522 void 00523 steal_from 00524 ( 00525 undi_graph& ug, 00526 gdtnode 00527 ); 00528 00529 00534 void 00535 mirror 00536 ( 00537 tree& 00538 ); 00539 00540 00545 void 00546 forget 00547 ( 00548 ); 00549 00550 /* 00551 CATEGORY io_operations 00552 Input / output operations. 00553 */ 00554 00559 void 00560 print_tree 00561 ( 00562 std::ostream& os=std::cout 00563 ); 00564 00565 //void graphic_print_tree (window&); 00566 00567 00568 /* 00569 CATEGORY LCA 00570 Lowest Common Ancestor in O(1) time 00571 */ 00572 00573 00574 private: 00575 gdt::gdtnode_map<unsigned int> PREORDER; 00576 gdt::gdtnode_map<unsigned int> SIZE; 00577 gdt::gdtnode_map<unsigned int> INLABEL; 00578 gdt::gdtnode_map<unsigned int> ASCENDANT; 00579 gdt::gdtmap<unsigned int, gdtnode> HEAD; 00580 00581 void 00582 preorder_visit 00583 ( 00584 gdtnode current, 00585 gdt::gdtlist<gdtnode>& visited 00586 ); 00587 00588 00589 public: 00590 00595 void 00596 preprocessing_lca(); 00597 00602 gdtnode 00603 LCA 00604 ( 00605 gdtnode n1, 00606 gdtnode n2 00607 ); 00608 00609 }; 00610 00611 00612 // -------------------------------------------- 00613 // Macro for ordered son gdtedge and gdtnode scanning 00614 // -------------------------------------------- 00615 00616 00617 #define forall_son_nodes(w,v,G)\ 00618 for(w=(G).first_son_node(v);w;w=(G).son_succ(w,v)) 00619 00620 #define forall_son_edges(e,v,G)\ 00621 for(e=(G).first_son_edge(v);e;e=(G).son_succ(e,v)) 00622 00623 #endif
1.5.3