00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
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
00030
00031
00032
00033
00034
00035 class
00036 upwa_plan_undi_graph;
00037
00043 class
00044 struct_upwa_node_info
00045 {
00046 friend class upwa_plan_undi_graph;
00047
00048 private:
00049 gdtedge first_in_cand;
00050 gdtedge first_out_cand;
00051 bool in_cand_edges_are_ordered;
00052 bool out_cand_edges_are_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
00106
00107
00108 face ext_face;
00109 algorithm_type layout_algorithm;
00110 gdt::gdtedge_map<bend_constraint> constraint_on_bends_of_edge;
00111 gdt::gdtnode_map<struct_upwa_node_info>* node_info;
00112 int last_cost;
00113
00114
00115
00116
00117
00118 void local_new ();
00119 void local_del ();
00120 void local_renew();
00121 void local_init (face,algorithm_type, bool err_mess);
00122
00123 void local_set
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);
00133 void set_first_out_cand (gdtnode,gdtedge);
00134
00135 void set_in_cand_edges_are_ordered (gdtnode,bool);
00136 void set_out_cand_edges_are_ordered (gdtnode,bool);
00137
00138
00139 void update_constraint_internal_structures ();
00140 void set_bend_constraints (gdtedge, bend_constraint);
00141 void set_bend_constraints (gdt::gdtedge_array<bend_constraint>);
00142 void reset_bend_constraints ();
00143
00144 void order_in_cand (gdtnode);
00145 void order_out_cand (gdtnode);
00146 void order_cand (gdtnode);
00147 void order_cand ();
00148
00149 gdt::list_item find_BSS (gdt::gdtlist<gdtnode>& ext, gdt::gdtmap<gdt::list_item,bool>& is_big);
00150
00151
00152
00153
00154 int make_upward_with_constraints ();
00155
00156 int optimal_upward_for_fixed_embedding_with_constraints ();
00157
00158
00159
00160 int slow_upward ();
00161
00162
00163
00164
00165
00166
00167 gdtnode new_node (gdtedge,int new_id=AUTO_ID );
00168
00169 gdtedge new_edge (gdtnode v1, gdtnode v2, face f, int new_id=AUTO_ID);
00170 gdtedge new_edge (gdtnode v1, gdtedge e1, gdtnode v2, gdtedge e2, int new_id=AUTO_ID);
00171
00172 void del_edge (gdtedge);
00173
00174 void reverse (gdtedge);
00175 void make_directed (gdtedge,gdtnode);
00176
00177 void make_big_angle (gdtnode v, face f);
00178
00179 gdt::gdtlist<gdtedge> decompose (face& f);
00180
00181
00182
00183 gdt::gdtlist<gdtedge> decompose ();
00184
00185 bool is_upward();
00186
00187
00188
00189 public:
00190
00191
00192
00193
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
00292
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
00332
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
00351
00352 bool get_in_cand_edges_are_ordered (gdtnode) const;
00353 bool get_out_cand_edges_are_ordered (gdtnode) const;
00354 gdtedge get_first_in_cand (gdtnode) const;
00355 gdtedge get_first_out_cand(gdtnode) const;
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
00764
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
00950
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