00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00017 #ifndef RM3_PLAN_UNDI_GRAPH_H
00018 #define RM3_PLAN_UNDI_GRAPH_H
00019
00020
00021 #include <GDT/gdtlist.h>
00022 #include <GDT/gdtmap.h>
00023 #include <GDT/rm3_global.h>
00024 #include <GDT/rm3_undi_graph.h>
00025
00026 #define nil 0
00027
00028
00029
00030 #undef face
00031 #define face GDT_face
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046 class struct_face;
00047
00048 class struct_border_step;
00049
00050 typedef struct_face* face;
00051
00052 typedef struct_border_step* border_step;
00053
00054 const face NULL_FACE = (face)NULL;
00055 const border_step NULL_BORDER_STEP = (border_step)NULL;
00056
00057 inline int compare(const face& x, const face& y)
00058 { if (x < y) return -1;
00059 else if (x > y) return 1;
00060 else return 0;
00061 }
00062
00063 inline int compare(const border_step& x, const border_step& y)
00064 { if (x < y) return -1;
00065 else if (x > y) return 1;
00066 else return 0;
00067 }
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077 struct
00078 vertical_segment
00079 {
00080 int y_min;
00081 int y_max;
00082 int x;
00083 };
00084
00085 struct
00086 horizontal_segment
00087 {
00088 int x_min;
00089 int x_max;
00090 int y;
00091 };
00092
00093
00105 class GDT_NONSTANDARD_DECL
00106 struct_separation_pair
00107 {
00108 friend class struct_face;
00109 friend class struct_border_step;
00110 friend class plan_undi_graph;
00111
00112 private:
00113 gdtnode pole1,
00114 pole2;
00115 gdt::gdtlist<face> shared_faces;
00116
00117 public:
00118
00119 ~struct_separation_pair
00120 (
00121 );
00122 };
00123
00124
00130 typedef struct_separation_pair*
00131 separation_pair;
00132
00133
00154 class GDT_NONSTANDARD_DECL
00155 struct_border_step
00156 {
00157 friend class struct_face;
00158 friend class plan_undi_graph;
00159
00160
00161
00162 private:
00163 gdtedge owner_edge;
00164 face owner_face;
00165 gdtnode start_node;
00166 gdt::list_item pos_in_border_steps;
00167
00168 public:
00169 static int counter;
00170
00171 struct_border_step();
00172 ~struct_border_step();
00173 };
00174
00180 typedef struct_border_step*
00181 border_step;
00182
00183
00197 class GDT_NONSTANDARD_DECL
00198 struct_face
00199 {
00200 friend class plan_undi_graph;
00201
00202 private:
00203 int id;
00204 plan_undi_graph* owner;
00205 gdt::list_item pos_in_f_list;
00206 gdt::gdtlist<gdtedge> edges;
00207 gdt::gdtlist<border_step> border_steps;
00208
00209 public:
00210
00211
00212
00213
00214
00215
00220 ~struct_face
00221 (
00222 );
00227 struct_face
00228 (
00229 );
00234 plan_undi_graph&
00235 get_owner
00236 (
00237 );
00238 };
00239
00240
00247 class
00248 struct_plan_edge_info
00249 {
00250 friend class plan_undi_graph;
00251
00252 private:
00253 face left_face;
00254 face right_face;
00255
00256 border_step left_face_border_step;
00257 border_step right_face_border_step;
00258
00259 gdt::list_item pos_in_left_face_edges;
00260 gdt::list_item pos_in_right_face_edges;
00261 public:
00262
00263
00264
00265
00266
00267
00272 struct_plan_edge_info
00273 (
00274 );
00275 };
00276
00277
00287 class GDT_NONSTANDARD_DECL
00288 plan_undi_graph
00289 : public undi_graph
00290 {
00291 friend class undi_graph;
00292 private:
00293
00294
00295
00296
00297
00298 gdt::gdtlist<face>* f_list;
00299 gdt::gdtedge_map<struct_plan_edge_info>* edge_info;
00300 gdt::gdtmap<int,face>* face_with_id;
00301 int max_face_id;
00302 int last_crosses;
00303
00304 void local_new ();
00305 void local_del ();
00306 void local_renew();
00307 void local_init (planarize_options po, bool err_mess);
00308
00309 bool build_faces();
00310
00311 void local_set
00312 (
00313 gdt::gdtlist<face>*,
00314 gdt::gdtedge_map<struct_plan_edge_info>*,
00315 gdt::gdtmap<int,face>*,
00316 int,
00317 int
00318 );
00319
00320
00321
00322
00323
00324
00325 gdtnode new_node (int new_id=AUTO_ID);
00326 gdtedge new_edge (gdtnode, gdtedge, gdtnode, int new_id=AUTO_ID);
00327 gdtedge new_edge (gdtnode, gdtnode, int new_id=AUTO_ID);
00328
00329
00330
00331
00332
00333 face new_face (int new_id=AUTO_ID);
00334 void del_face (face);
00335
00336 border_step new_border_step (gdtedge, gdtnode, face);
00337
00338
00339 void set_right_face_moving_along_edge (gdtedge e,gdtnode v,face f);
00340
00341
00342
00343 void set_right_face_moving_along_edge (gdtedge e,gdtnode v,gdtedge eref,gdtnode vref,int dir=gdt::after);
00344
00345
00346
00347
00348
00349 void reset_edge_info (gdtedge);
00350
00351 void find_vertical_lengths (gdt::gdtedge_array<int>& len, gdtedge e_st, gdt::gdtedge_array<int>& cost);
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366 protected:
00367
00368 void set_source (gdtedge, gdtnode);
00369 void set_faces_shared_by_separation_pair (const gdt::gdtlist<face>&, separation_pair);
00370 void set_separation_pair_pole1 (gdtnode, separation_pair);
00371 void set_separation_pair_pole2 (gdtnode, separation_pair);
00372
00373 gdtnode first_node_visited_while_moving_on_edge_around_face (gdtedge, face) const;
00374 gdtnode second_node_visited_while_moving_on_edge_around_face (gdtedge, face) const;
00375
00376 void calculate_dual (plan_undi_graph&, gdt::gdtmap<face,gdtnode>&);
00377 void calculate_dual (plan_undi_graph&, gdtedge, gdt::gdtmap<face,gdtnode>&);
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388 public:
00389
00390
00391
00392
00393
00394
00399 plan_undi_graph
00400 (
00401 );
00402
00403
00408 ~plan_undi_graph
00409 (
00410 );
00411
00412
00430 plan_undi_graph
00431 (
00432 const undi_graph& ug,
00433 planarize_options po = DO_NOT_PRESERVE_EMBEDDING,
00434 bool err_mess = true
00435 );
00436
00437
00442 plan_undi_graph
00443 (
00444 const plan_undi_graph& pug
00445 );
00446
00447
00448
00449
00450
00451
00452
00464 plan_undi_graph&
00465 operator =
00466 (
00467 const undi_graph& ug
00468 );
00469
00470
00471
00472
00473
00474 plan_undi_graph&
00475 operator =
00476 (
00477 const plan_undi_graph& pug
00478 );
00479
00490 void
00491 local_get
00492 (
00493 gdt::gdtlist<face>*& p1,
00494 gdt::gdtedge_map<struct_plan_edge_info>*& p2,
00495 gdt::gdtmap<int,face>*& p3,
00496 int& p4,
00497 int& p5
00498 );
00499
00500
00505 int
00506 generate_face_id
00507 (
00508 );
00509
00510
00515 int
00516 id
00517 (
00518 gdtnode v
00519 ) const;
00520
00525 int
00526 id
00527 (
00528 gdtedge e
00529 ) const;
00530
00535 int
00536 id
00537 (
00538 face f
00539 ) const;
00540
00541
00546 inline
00547 int
00548 get_max_face_id
00549 (
00550 ) const;
00551
00552
00557 int
00558 degree
00559 (
00560 gdtnode v
00561 ) const;
00562
00568 int
00569 degree
00570 (
00571 face f,
00572 bool bridge = false
00573 ) const;
00574
00579 int
00580 number_of_faces
00581 (
00582 ) const;
00583
00589 int
00590 number_of_cross_nodes
00591 (
00592 ) const;
00593
00598 bool
00599 node_belongs_to_face
00600 (
00601 gdtnode v,
00602 face f
00603 ) const;
00604
00609 bool
00610 edge_belongs_to_face
00611 (
00612 gdtedge e,
00613 face f
00614 ) const;
00615
00620 gdtnode
00621 separation_pair_pole1
00622 (
00623 separation_pair sp
00624 ) const;
00625
00630 gdtnode
00631 separation_pair_pole2
00632 (
00633 separation_pair sp
00634 ) const;
00635
00641 face
00642 find_face
00643 (
00644 int ref_id
00645 ) const;
00646
00651 face
00652 first_face
00653 (
00654 ) const;
00655
00660 face
00661 last_face
00662 (
00663 ) const;
00664
00669 face
00670 succ_face
00671 (
00672 face f
00673 ) const;
00674
00679 face
00680 pred_face
00681 (
00682 face f
00683 ) const;
00684
00689 face
00690 adj_face
00691 (
00692 face f,
00693 gdtedge e
00694 ) const;
00695
00700 face
00701 right_face_moving_along_edge
00702 (
00703 gdtedge e,
00704 gdtnode v
00705 ) const;
00706
00711 face
00712 left_face_moving_along_edge
00713 (
00714 gdtedge e,
00715 gdtnode v
00716 ) const;
00717
00722 face
00723 face_of_border_step
00724 (
00725 border_step s
00726 ) const;
00727
00732 const gdt::gdtlist<face>&
00733 all_faces
00734 (
00735 ) const;
00736
00741 gdtedge
00742 first_adj_edge
00743 (
00744 gdtnode v
00745 ) const;
00746
00751 gdtedge
00752 first_adj_edge
00753 (
00754 face f
00755 ) const;
00756
00761 gdtedge
00762 last_adj_edge
00763 (
00764 gdtnode v
00765 ) const;
00766
00771 gdtedge
00772 last_adj_edge
00773 (
00774 face f
00775 ) const;
00776
00781 gdtedge
00782 adj_pred
00783 (
00784 gdtedge e,
00785 gdtnode v
00786 ) const;
00787
00792 gdtedge
00793 adj_pred
00794 (
00795 gdtedge e,
00796 face f
00797 ) const;
00798
00803 gdtedge
00804 adj_succ
00805 (
00806 gdtedge e,
00807 gdtnode v
00808 ) const;
00809
00814 gdtedge
00815 adj_succ
00816 (
00817 gdtedge e,
00818 face f
00819 ) const;
00820
00825 gdtedge
00826 cyclic_adj_pred
00827 (
00828 gdtedge e,
00829 gdtnode v
00830 ) const;
00831
00836 gdtedge
00837 cyclic_adj_pred
00838 (
00839 gdtedge e,
00840 face f
00841 ) const;
00842
00847 gdtedge
00848 cyclic_adj_succ
00849 (
00850 gdtedge e,
00851 gdtnode v
00852 ) const;
00853
00858 gdtedge
00859 cyclic_adj_succ
00860 (
00861 gdtedge e,
00862 face f
00863 ) const;
00864
00869 gdtedge
00870 edge_of_border_step
00871 (
00872 border_step s
00873 ) const;
00874
00879 gdt::gdtlist<gdtnode>
00880 nodes_shared_by_faces
00881 (
00882 face f1,
00883 face f2
00884 ) const;
00885
00891 gdt::gdtlist<gdtnode>
00892 adj_nodes
00893 (
00894 face f
00895 ) const;
00896
00901 gdt::gdtlist<gdtedge>
00902 adj_edges
00903 (
00904 gdtnode v
00905 ) const;
00906
00913 gdt::gdtlist<gdtedge>
00914 adj_edges
00915 (
00916 face f,
00917 gdtnode v=NULL_NODE
00918 ) const;
00919
00924 gdt::gdtlist<face>
00925 adj_faces
00926 (
00927 gdtnode v
00928 ) const;
00929
00934 gdt::gdtlist<gdtedge>
00935 edges_shared_by_faces
00936 (
00937 face f1,
00938 face f2
00939 ) const;
00940
00945 gdt::gdtlist<gdtedge>
00946 edges_entering_node_while_moving_around_face
00947 (
00948 gdtnode v,
00949 face f
00950 ) const;
00951
00956 gdt::gdtlist<face>
00957 faces_shared_by_separation_pair
00958 (
00959 separation_pair sp
00960 ) const;
00961
00966 gdt::list_item
00967 pos_in_border
00968 (
00969 gdtedge e,
00970 face f
00971 ) const;
00972
00977 gdt::list_item
00978 pos_in_border
00979 (
00980 border_step s
00981 ) const;
00982
00987 gdtnode
00988 start_of_border_step
00989 (
00990 border_step s
00991 ) const;
00992
00997 gdtnode
00998 stop_of_border_step
00999 (
01000 border_step s
01001 ) const;
01002
01007 border_step
01008 first_border_step
01009 (
01010 face f
01011 ) const;
01012
01017 border_step
01018 last_border_step
01019 (
01020 face f
01021 ) const;
01022
01028 border_step
01029 succ_border_step
01030 (
01031 border_step s
01032 ) const;
01033
01039 border_step
01040 pred_border_step
01041 (
01042 border_step s
01043 ) const;
01044
01050 border_step
01051 cyclic_succ_border_step
01052 (
01053 border_step s
01054 ) const;
01055
01061 border_step
01062 cyclic_pred_border_step
01063 (
01064 border_step s
01065 ) const;
01066
01071 border_step
01072 opposite_border_step
01073 (
01074 border_step s
01075 ) const;
01076
01081 border_step
01082 border_step_moving_along_edge
01083 (
01084 gdtedge e,
01085 gdtnode v
01086 ) const;
01087
01092 gdt::gdtlist<border_step>
01093 adj_border_steps
01094 (
01095 face f
01096 ) const;
01097
01102 gdt::gdtlist<border_step>
01103 border_steps_starting_at_node
01104 (
01105 gdtnode v
01106 ) const;
01107
01112 gdt::gdtlist<border_step>
01113 border_step_sequence
01114 (
01115 border_step s1,
01116 border_step s2
01117 ) const;
01118
01123 void
01124 border_step_sequence
01125 (
01126 border_step s1,
01127 border_step s2,
01128 gdt::gdtlist<border_step>& L
01129 ) const;
01130
01131
01137 gdt::gdtlist<border_step>
01138 border_step_sequence
01139 (
01140 gdtnode v1,
01141 gdtnode v2,
01142 face f
01143 ) const;
01144
01145
01151 void
01152 border_step_sequence
01153 (
01154 gdtnode v1,
01155 gdtnode v2,
01156 face f,
01157 gdt::gdtlist<border_step>& L
01158 ) const;
01159
01166 separation_pair
01167 find_separation_pair
01168 (
01169 int idv1,
01170 int idv2,
01171 const gdt::gdtlist<separation_pair>& sp_list
01172 ) const;
01173
01178 gdt::gdtlist<separation_pair>
01179 find_separation_pairs
01180 (
01181 ) const;
01182
01193 void
01194 make_dual
01195 (
01196 plan_undi_graph& dual_pug,
01197 gdt::gdtmap<face,gdtnode>& primal_face_2_dual_node,
01198 gdt::gdtmap<gdtnode,face>& dual_node_2_primal_face,
01199 gdt::gdtmap<gdtedge,gdtedge>& primal_edge_2_dual_edge,
01200 gdt::gdtmap<gdtedge,gdtedge>& dual_edge_2_primal_edge
01201 ) const;
01202
01231 void
01232 compute_visibility_representation
01233 (
01234 gdt::gdtnode_array<horizontal_segment>& seg_node,
01235 gdt::gdtedge_array<vertical_segment>& seg_edge,
01236 face ext_face,
01237 bool compacted = false,
01238 gdt::gdtedge_array<int>* cp = NULL
01239
01240 );
01241
01270 void
01271 compute_visibility_representation
01272 (
01273 gdt::gdtnode_array<horizontal_segment>& seg_node,
01274 gdt::gdtedge_array<vertical_segment>& seg_edge,
01275 gdtedge e_st,
01276 bool compacted = false,
01277 gdt::gdtedge_array<int>* cp = NULL
01278 );
01279
01280
01281
01282
01283
01284
01290 face
01291 corresponding_face
01292 (
01293 face f,
01294 const plan_undi_graph& pug
01295 );
01296
01302 border_step
01303 corresponding_border_step
01304 (
01305 border_step s,
01306 const plan_undi_graph& pug
01307 );
01308
01309
01310
01311
01312
01313
01319 gdtnode
01320 new_node
01321 (
01322 gdtedge e,
01323 int new_id=AUTO_ID
01324 );
01325
01332 gdtnode
01333 new_node
01334 (
01335 gdtnode n,
01336 gdtedge e,
01337 int node_id=AUTO_ID,
01338 int edge_id=AUTO_ID
01339 );
01340
01345 gdtnode
01346 star_in_face
01347 (
01348 face f
01349 );
01350
01357 gdtedge
01358 new_edge
01359 (
01360 gdtnode v1,
01361 gdtnode v2,
01362 face f,
01363 int new_id=AUTO_ID
01364 );
01365
01374 gdtedge
01375 new_edge
01376 (
01377 gdtnode v1,
01378 gdtedge e1,
01379 gdtnode v2,
01380 gdtedge e2,
01381 int new_id=AUTO_ID
01382 );
01383
01389 face
01390 del_edge
01391 (
01392 gdtedge e
01393 );
01394
01400 face
01401 del_node
01402 (
01403 gdtnode v
01404 );
01405
01412 gdtedge
01413 weld_edges_at_node
01414 (
01415 gdtnode v
01416 );
01417
01422 void
01423 clear
01424 (
01425 );
01426
01438 void
01439 steal_from
01440 (
01441 undi_graph& ug,
01442 planarize_options po=DO_NOT_PRESERVE_EMBEDDING,
01443 bool err_mess = true
01444 );
01445
01450 void
01451 mirror
01452 (
01453 plan_undi_graph& pug
01454 );
01455
01460 void
01461 forget
01462 (
01463 );
01464
01470 void
01471 assign_id
01472 (
01473 gdtnode v,
01474 int new_id = AUTO_ID
01475 );
01476
01482 void
01483 assign_id
01484 (
01485 gdtedge e,
01486 int new_id = AUTO_ID
01487 );
01488
01494 void
01495 assign_id
01496 (
01497 face f,
01498 int new_id = AUTO_ID
01499 );
01500
01501
01506 void
01507 update_max_face_id
01508 (
01509 );
01510
01511
01520 face
01521 plan_with_fixed_face_of_undi_graph
01522 (
01523 undi_graph& ug,
01524 gdtedge start_edge,
01525 gdtnode start_node
01526 );
01527
01532 void
01533 make_embedding_as
01534 (
01535 const plan_undi_graph& pug
01536 );
01537
01545 gdtedge
01546 expand
01547 (
01548 gdtnode v,
01549 gdtedge e_init,
01550 gdtedge e_end
01551 );
01552
01559 gdtnode
01560 contract
01561 (
01562 gdtedge e
01563 );
01564
01569 gdt::gdtlist<gdtnode>
01570 contract
01571 (
01572 );
01573
01580 gdt::gdtlist<gdtnode>
01581 make_simple
01582 (
01583 );
01584
01585
01607 void
01608 make_upward_embedding
01609 (
01610 face ext_face,
01611 gdt::gdtnode_array<gdtedge>& fe,
01612 int minimum_switches = 0
01613 );
01614
01615
01632 void
01633 generate_biconnected
01634 (
01635 int n,
01636 double prob_iv,
01637 int k=INFINITE,
01638 bool multiple = true
01639 );
01640
01641
01642
01643
01644
01645
01650 void
01651 print
01652 (
01653 print_mode mode=BY_FACES,
01654 std::ostream& os=std::cout
01655 ) const;
01656
01661 void
01662 print
01663 (
01664 gdtnode v,
01665 std::ostream& os=std::cout
01666 ) const;
01667
01672 void
01673 print
01674 (
01675 gdtedge e,
01676 std::ostream& os=std::cout
01677 ) const;
01678
01683 void
01684 print
01685 (
01686 face f,
01687 std::ostream& os=std::cout
01688 ) const;
01689
01694 void
01695 print
01696 (
01697 constraint c,
01698 std::ostream& os=std::cout
01699 ) const;
01700
01705 void
01706 print
01707 (
01708 separation_pair sp,
01709 std::ostream& os=std::cout
01710 ) const;
01711
01712
01713
01714
01715
01716
01722 bool
01723 internal_consistency_check
01724 (
01725 ) const;
01726
01727 };
01728
01729
01730
01731
01732
01733
01734
01735
01736 #define forall_GDT_faces(f,G)\
01737 for(f=(G).first_face();f;f=(G).succ_face(f))
01738
01739
01740 #define forall_GDT_face_edges(e,f)\
01741 for(e=f->get_owner().first_adj_edge(f);e;e=f->get_owner().adj_succ(e,f))
01742
01743
01744 #define forall_GDT_face_border_steps(s,f)\
01745 for(s=f->get_owner().first_border_step(f);s;s=f->get_owner().succ_border_step(s))
01746
01747
01748
01749 #ifdef forall_faces
01750 #undef forall_faces
01751 #endif
01752 #define forall_faces forall_GDT_faces
01753
01754 #ifdef forall_face_edges
01755 #undef forall_face_edges
01756 #endif
01757 #define forall_face_edges forall_GDT_face_edges
01758
01759 #ifdef forall_face_border_steps
01760 #undef forall_face_border_steps
01761 #endif
01762 #define forall_face_border_steps forall_GDT_face_border_steps
01763
01764 #endif