00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00017 #ifndef RM3_TREE_H
00018 #define RM3_TREE_H
00019
00020
00021 #include <GDT/rm3_undi_graph.h>
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00041 class GDT_NONSTANDARD_DECL
00042 struct_tree_node_info
00043 {
00044 friend class tree;
00045
00046 gdtedge father;
00047 int level;
00048 };
00049
00050
00051
00061 class GDT_NONSTANDARD_DECL
00062 tree: public undi_graph
00063 {
00064 private:
00065 gdtnode root;
00066 gdt::gdtnode_map<struct_tree_node_info>* node_info;
00067
00068
00069
00070
00071
00072 void local_new ();
00073 void local_del ();
00074 void local_renew ();
00075
00076 void local_init(gdtnode=NULL_NODE);
00077
00078 void local_set
00079 (
00080 gdtnode,
00081 gdt::gdtnode_map<struct_tree_node_info>*
00082 );
00083
00084 void set_father_edge (gdtnode v, gdtedge e);
00085 void set_level (gdtnode v, int i);
00086
00087 void set_levels_in_subtree (gdtnode v = NULL_NODE, int i = 0);
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097 void new_node () {};
00098 void new_edge () {};
00099
00100
00101 protected:
00102
00103
00104
00105
00106 public:
00107
00108
00109
00110
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
00155
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
00183
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
00445
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
00552
00553
00554
00559 void
00560 print_tree
00561 (
00562 std::ostream& os=std::cout
00563 );
00564
00565
00566
00567
00568
00569
00570
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
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