00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00016 #ifndef RM3_ORTH_PLAN_UNDI_GRAPH_H
00017 #define RM3_ORTH_PLAN_UNDI_GRAPH_H
00018
00019
00020 #include <GDT/gdtlist.h>
00021 #include <GDT/gdtmap.h>
00022 #include <GDT/rm3_global.h>
00023 #include <GDT/rm3_undi_graph.h>
00024 #include <GDT/rm3_dire_graph.h>
00025 #include <GDT/rm3_plan_undi_graph.h>
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 class
00042 orth_plan_undi_graph;
00043
00044
00045 class
00046 upwa_plan_undi_graph;
00047
00048
00049
00050
00051
00052 const int UNDEFINED_PIN_NUMBER = -1;
00053
00054
00055
00056
00057
00064 typedef enum
00065 {
00066 right,
00067 left,
00068 straight
00069 }
00070 bend_type;
00071
00072
00073
00074 inline std::istream& operator >>(std::istream& in,const bend_type& x)
00075 {in >> *((unsigned int *)((void *)&x));return(in); }
00076
00077 inline std::ostream& operator <<(std::ostream& out,const bend_type& x)
00078 {out << *((unsigned int *)((void *)&x));return(out); }
00079
00080
00081
00082
00088 class GDT_NONSTANDARD_DECL
00089 struct_orth_border_step_info
00090 {
00091 friend class orth_plan_undi_graph;
00092
00093 private:
00094 gdt::gdtlist<bend_type> bends;
00095 angle_type angle;
00096 int thickness;
00097 int pin_number;
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120 public:
00121
00122 struct_orth_border_step_info
00123 (
00124 );
00125 };
00126
00157 class GDT_NONSTANDARD_DECL
00158 orth_plan_undi_graph
00159 : public plan_undi_graph
00160 {
00161 friend class dime_orth_plan_undi_graph;
00162 private:
00163
00164
00165
00166
00167 face ext_face;
00168 algorithm_type layout_algorithm;
00169 gdt::gdtedge_map<bend_constraint> constraint_on_bends_of_edge;
00170 gdt::gdtmap<border_step,struct_orth_border_step_info>* border_step_info;
00171 bool local_consistency_is_suspended;
00172 bool diagnostic_printouts_are_enabled;
00173 border_step ref_border_step;
00174 int last_cost;
00175
00176
00177
00178
00179
00180
00181 void undefine(gdtedge e);
00182
00183
00184 void local_new ();
00185 void local_del ();
00186 void local_renew();
00187 void local_init (face, algorithm_type, bool err_mess);
00188 void local_init (const upwa_plan_undi_graph& upug, algorithm_type alg);
00189
00190 void local_set
00191 (
00192 face,
00193 algorithm_type,
00194 gdt::gdtedge_map<bend_constraint>,
00195 gdt::gdtmap<border_step,struct_orth_border_step_info>*,
00196 bool,
00197 bool,
00198 border_step,
00199 int
00200 );
00201
00202 void update_constraint_internal_structures ();
00203 void set_bend_constraints (gdtedge, bend_constraint);
00204 void set_bend_constraints (gdt::gdtedge_array<bend_constraint>);
00205 void reset_bend_constraints ();
00206
00207 gdt::gdtlist<bend_type> invert_bend_list (gdt::gdtlist<bend_type>);
00208
00209 void set_thickness_of_border_step (border_step s, int t);
00210 void set_pin_number_of_border_step (border_step s, int p);
00211 void reset_edge_info (gdtedge);
00212 void reset_border_step_info (border_step);
00213 void set_bends_of_border_step (border_step,gdt::gdtlist<bend_type>);
00214 void set_angle_of_border_step (border_step,angle_type);
00215
00216
00217 int angle_to_int (angle_type alpha) const;
00218 angle_type int_to_angle (int a) const;
00219
00220
00221 void make_border_step_turn_left (border_step);
00222 void make_border_step_turn_right (border_step);
00223 void make_border_step_turn_back (border_step);
00224 void make_border_step_go_straight (border_step);
00225
00226 void set_edge_bends (gdtedge,gdtnode,int,bend_type);
00227 void set_edge_shape (gdtedge,gdtnode,int,bend_type, angle_type,angle_type);
00228 void set_edge_shape (gdtedge,gdtnode,std::string, angle_type,angle_type);
00229 void set_edge_shape (gdtedge,gdtnode,gdt::gdtlist<bend_type>,gdt::gdtlist<bend_type>,angle_type,angle_type);
00230 void set_edge_shape_near_node (gdtedge,gdtnode,std::string,angle_type);
00231
00232 void remove_LRR_sequences_from_border_of_face (face, gdt::gdtlist<gdtnode>&, gdt::gdtlist<gdtedge>&);
00233 void remove_LRL_sequences_from_border_of_external_face (gdt::gdtlist<gdtnode>&, gdt::gdtlist<gdtedge>&);
00234 bool regularize_face (face, gdt::gdtlist<gdtnode>&, gdt::gdtlist<gdtedge>&, algorithm_type alg);
00235
00236
00237 gdtedge split_internal_face (gdtnode v1, gdtedge e1, gdtnode v2, gdtedge e2, int new_id=AUTO_ID);
00238
00239
00240 gdtedge split_external_face (gdtnode v1, gdtedge e1, gdtnode v2, gdtedge e2, int new_id=AUTO_ID);
00241
00242
00243 void change_ref_border_step ();
00244
00245
00246
00247
00248
00249
00250
00251 void quick_orth_for_fixed_embedding ();
00252
00253
00254 int optimal_orth_for_fixed_embedding_with_constraints();
00255
00256
00257
00258
00259 int slow_orth ();
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271 int apply_t1_bend_stretching();
00272 int apply_t2_bend_stretching();
00273 int apply_t3_bend_stretching();
00274
00275
00276
00277
00278 face find_external_face ();
00279
00280 bool is_main_edge_on_node_side (gdtedge e, gdtnode v);
00281
00282
00283 protected:
00284 gdtedge split_face_with_shaped_edge
00285 (
00286 gdtnode v, gdtedge ev, angle_type av,
00287 gdtnode w, gdtedge ew, angle_type aw,
00288 std::string bends_sequence,
00289 int new_id=AUTO_ID
00290 );
00291
00292 void split_list_of_edges_on_side
00293 (
00294 gdt::gdtlist<gdtedge>& L,
00295 gdtnode v,
00296 gdt::gdtlist<gdtedge>& L_left,
00297 gdtedge& ec,
00298 gdt::gdtlist<gdtedge>& L_right
00299 );
00300
00301
00302 void merge_edges_on_same_side (gdtnode v);
00303
00304
00305 public:
00306
00307
00308
00309
00310
00311
00316 orth_plan_undi_graph
00317 (
00318 );
00319
00320
00325 ~orth_plan_undi_graph
00326 (
00327 );
00328
00329
00336 orth_plan_undi_graph
00337 (
00338 const undi_graph& ug,
00339 algorithm_type alg = PLAN_ORTH_OPTIMAL,
00340 bool err_mess = true
00341 );
00342
00343
00350 orth_plan_undi_graph
00351 (
00352 const plan_undi_graph& pug,
00353 algorithm_type alg = PLAN_ORTH_OPTIMAL,
00354 bool err_mess = true
00355 );
00356
00357
00365 orth_plan_undi_graph
00366 (
00367 const plan_undi_graph& pug,
00368 face ef,
00369 algorithm_type alg = PLAN_ORTH_OPTIMAL,
00370 bool err_mess = true
00371 );
00372
00373
00379 orth_plan_undi_graph
00380 (
00381 const upwa_plan_undi_graph& upug,
00382 algorithm_type alg = PLAN_ORTH_UPWA_STRAIGHT_MIDDLE
00383 );
00384
00385
00386
00391 orth_plan_undi_graph
00392 (
00393 const orth_plan_undi_graph& opug
00394 );
00395
00396
00397
00398
00399
00400
00401
00406 orth_plan_undi_graph&
00407 operator =
00408 (
00409 const undi_graph& ug
00410 );
00411
00412
00417 orth_plan_undi_graph&
00418 operator =
00419 (
00420 const plan_undi_graph& pug
00421 );
00422
00423
00428 orth_plan_undi_graph&
00429 operator =
00430 (
00431 const upwa_plan_undi_graph& upug
00432 );
00433
00434
00439 orth_plan_undi_graph&
00440 operator =
00441 (
00442 const orth_plan_undi_graph& opug
00443 );
00444
00445
00446
00447
00448
00449
00450
00455 void
00456 local_get
00457 (
00458 face& p1,
00459 algorithm_type& p2,
00460 gdt::gdtedge_map<bend_constraint>& p3,
00461 gdt::gdtmap<border_step,struct_orth_border_step_info>*& p4,
00462 bool& p5,
00463 bool& p6,
00464 border_step& p7,
00465 int p8
00466 );
00467
00468
00469
00486 border_step
00487 get_ref_border_step
00488 () const;
00489
00490
00495 gdt::gdtlist<bend_type>
00496 bends_of_border_step
00497 (
00498 border_step s
00499 ) const;
00500
00501
00507 angle_type
00508 angle_of_border_step
00509 (
00510 border_step s
00511 ) const;
00512
00513
00528 int
00529 thickness_of_border_step
00530 (
00531 border_step s
00532 ) const;
00533
00534
00562 int
00563 pin_number_of_border_step
00564 (
00565 border_step s
00566 ) const;
00567
00572 int
00573 thickness_of_edge
00574 (
00575 gdtedge e
00576 ) const;
00577
00578
00583 int
00584 right_thickness_of_edge
00585 (
00586 gdtedge e,
00587 gdtnode v
00588 ) const;
00589
00590
00595 int
00596 left_thickness_of_edge
00597 (
00598 gdtedge e,
00599 gdtnode v
00600 ) const;
00601
00602
00607 int
00608 number_of_bends
00609 (
00610 ) const;
00611
00612
00617 int
00618 number_of_bends
00619 (
00620 gdtedge e
00621 ) const;
00622
00623
00628 int
00629 number_of_bends
00630 (
00631 gdt::gdtlist<gdtedge> ls_edge
00632 ) const;
00633
00634
00639 int
00640 number_of_bends
00641 (
00642 border_step s
00643 ) const;
00644
00645
00650 int
00651 number_of_left_bends
00652 (
00653 border_step s
00654 ) const;
00655
00656
00661 int
00662 number_of_right_bends
00663 (
00664 border_step s
00665 ) const;
00666
00667
00672 int
00673 max_number_of_bends_on_edge
00674 (
00675 ) const;
00676
00677
00682 int
00683 number_of_left_turns_around_face
00684 (
00685 face f
00686 ) const;
00687
00688
00693 int
00694 number_of_right_turns_around_face
00695 (
00696 face f
00697 ) const;
00698
00699
00705 int
00706 number_of_left_turns_along_border
00707 (
00708 border_step sv,
00709 border_step sw
00710 ) const;
00711
00712
00718 int
00719 number_of_right_turns_along_border
00720 (
00721 border_step sv,
00722 border_step sw
00723 ) const;
00724
00725
00730 double
00731 mean_number_of_bends_on_edge
00732 (
00733 ) const;
00734
00735
00740 double
00741 bend_standard_deviation
00742 (
00743 ) const;
00744
00745
00750 face
00751 external_face
00752 (
00753 ) const;
00754
00755
00760 bend_constraint
00761 get_constraint_on_bends_of_edge
00762 (
00763 gdtedge e
00764 ) const;
00765
00766
00771 algorithm_type
00772 get_layout_algorithm
00773 (
00774 ) const;
00775
00776
00781 bool
00782 get_local_consistency_is_suspended
00783 (
00784 ) const;
00785
00786
00791 bool
00792 get_diagnostic_printouts_are_enabled
00793 (
00794 ) const;
00795
00796
00801 bool
00802 border_is_closed
00803 (
00804 face f
00805 ) const;
00806
00807
00813 bool
00814 border_step_turns_left
00815 (
00816 border_step s
00817 ) const;
00818
00819
00825 bool
00826 border_step_turns_right
00827 (
00828 border_step s
00829 ) const;
00830
00831
00837 bool
00838 border_step_turns_back
00839 (
00840 border_step s
00841 ) const;
00842
00843
00849 bool
00850 border_step_goes_straight
00851 (
00852 border_step s
00853 ) const;
00854
00855
00861 gdt::list_item
00862 find_border_step_turning_left
00863 (
00864 gdt::gdtlist<border_step>& bsl,
00865 gdt::list_item start_pos = NULL
00866 ) const;
00867
00868
00874 gdt::list_item
00875 find_border_step_turning_right
00876 (
00877 gdt::gdtlist<border_step>& bs,
00878 gdt::list_item start_pos = NULL
00879 ) const;
00880
00881
00887 gdt::list_item
00888 find_border_step_turning_left_or_turning_back
00889 (
00890 gdt::gdtlist<border_step>& bs,
00891 gdt::list_item start_pos = NULL
00892 ) const;
00893
00894
00900 int
00901 cost_of_last_algorithm
00902 (
00903 ) const;
00904
00905
00911 gdt::gdtlist<border_step>
00912 turning_border_steps_of_face
00913 (
00914 face f
00915 ) const;
00916
00917
00923 void
00924 edges_on_each_side_of_node
00925 (
00926 gdtnode v,
00927 gdt::gdtlist<gdtedge>& L1,
00928 gdt::gdtlist<gdtedge>& L2,
00929 gdt::gdtlist<gdtedge>& L3,
00930 gdt::gdtlist<gdtedge>& L4
00931 ) const;
00932
00933
00934
00946 bool
00947 face_is_regular
00948 (
00949 face f,
00950 border_step& r1,
00951 border_step& r2
00952 ) const;
00953
00954
00961 bool
00962 is_orthogonal
00963 ();
00964
00965
00966
00971 bool
00972 node_is_flat
00973 (
00974 gdtnode v
00975 ) const;
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00993 gdtnode
00994 new_node
00995 (
00996 gdtedge e,
00997 int new_id = AUTO_ID
00998 );
00999
01000
01009 gdtnode
01010 new_node
01011 (
01012 gdtedge e,
01013 gdtnode v,
01014 int seg_num,
01015 int new_id = AUTO_ID
01016 );
01017
01018
01030 gdtnode
01031 new_node
01032 (
01033 gdtnode v,
01034 gdtedge e,
01035 angle_type alpha,
01036 int new_node_id = AUTO_ID,
01037 int new_edge_id = AUTO_ID
01038 );
01039
01040
01050 gdtedge
01051 new_edge
01052 (
01053 gdtnode v,
01054 gdtnode w,
01055 face f,
01056 int new_id=AUTO_ID
01057 );
01058
01059
01070 gdtedge
01071 new_edge
01072 (
01073 gdtnode v,
01074 gdtedge ev,
01075 gdtnode w,
01076 gdtedge ew,
01077 int new_id=AUTO_ID
01078 );
01079
01080
01085 face
01086 del_node
01087 (
01088 gdtnode v
01089 );
01090
01091
01096 face
01097 del_edge
01098 (
01099 gdtedge e
01100 );
01101
01102
01109 gdtedge
01110 weld_edges_at_node
01111 (
01112 gdtnode v
01113 );
01114
01120 gdtedge
01121 replace_node_with_bend
01122 (
01123 gdtnode v
01124 );
01125
01126
01134 void
01135 replace_bend_with_node
01136 (
01137 gdtedge e,
01138 gdtnode v,
01139 int pos,
01140 gdt::gdtlist<gdtnode>& N,
01141 gdt::gdtlist<gdtedge>& E
01142 );
01143
01144
01150 void
01151 replace_bends_with_nodes
01152 (
01153 gdtedge e,
01154 gdt::gdtlist<gdtnode>& N,
01155 gdt::gdtlist<gdtedge>& E
01156 );
01157
01158
01164 void
01165 replace_bends_with_nodes
01166 (
01167 face f,
01168 gdt::gdtlist<gdtnode>& N,
01169 gdt::gdtlist<gdtedge>& E
01170 );
01171
01172
01178 void
01179 replace_bends_with_nodes
01180 (
01181 gdt::gdtlist<gdtnode>& N,
01182 gdt::gdtlist<gdtedge>& E
01183 );
01184
01185
01193 void
01194 decompose_all_faces_into_smaller_rectangular_faces
01195 (
01196 gdt::gdtlist<gdtnode>& N,
01197 gdt::gdtlist<gdtedge>& E
01198 );
01199
01200
01201
01209 int
01210 regularize_all_faces
01211 (
01212 gdt::gdtlist<gdtnode>& N,
01213 gdt::gdtlist<gdtedge>& E,
01214 algorithm_type alg
01215 );
01216
01217
01218
01223 void
01224 clear
01225 (
01226 );
01227
01228
01240 void
01241 steal_from
01242 (
01243 undi_graph& ug,
01244 algorithm_type alg = PLAN_ORTH_OPTIMAL,
01245 bool err_mess = true
01246 );
01247
01248
01259 void
01260 steal_from
01261 (
01262 plan_undi_graph& pug,
01263 algorithm_type alg = PLAN_ORTH_OPTIMAL,
01264 bool err_mess = true
01265 );
01266
01267
01279 void
01280 steal_from
01281 (
01282 plan_undi_graph& pug,
01283 face ef,
01284 algorithm_type alg = PLAN_ORTH_OPTIMAL,
01285 bool err_mess = true
01286 );
01287
01288
01293 void
01294 mirror
01295 (
01296 orth_plan_undi_graph& opug
01297 );
01298
01299
01304 void
01305 forget
01306 (
01307 );
01308
01309
01316 void
01317 set_external_face
01318 (
01319 face ef
01320 );
01321
01322
01327 void
01328 set_reference_border_step
01329 (
01330 border_step s
01331 );
01332
01333
01339 void
01340 set_reference_border_step
01341 (
01342 gdtnode v,
01343 gdtedge e
01344 );
01345
01346
01353 void
01354 set_layout_algorithm
01355 (
01356 algorithm_type la
01357 );
01358
01359
01369 int
01370 apply_layout_algorithm
01371 (
01372 bool err_mess = true
01373 );
01374
01375
01380 void
01381 suspend_local_consistency
01382 (
01383 );
01384
01385
01390 void
01391 restore_local_consistency
01392 (
01393 );
01394
01395
01400 void
01401 enable_diagnostic_printouts
01402 (
01403 );
01404
01405
01410 void
01411 disable_diagnostic_printouts
01412 (
01413 );
01414
01415
01416
01417
01418
01419
01420
01426 void
01427 print
01428 (
01429 print_mode mode = BY_FACES,
01430 std::ostream& os = std::cout
01431 ) const;
01432
01433
01438 void
01439 print
01440 (
01441 gdtnode v,
01442 std::ostream& os = std::cout
01443 ) const;
01444
01445
01450 void
01451 print
01452 (
01453 gdtedge e,
01454 std::ostream& os = std::cout
01455 ) const;
01456
01457
01462 void
01463 print
01464 (
01465 face f,
01466 std::ostream& os = std::cout
01467 ) const;
01468
01469
01474 void
01475 print
01476 (
01477 constraint c,
01478 std::ostream& os = std::cout
01479 ) const;
01480
01481
01486 void
01487 print
01488 (
01489 separation_pair sp,
01490 std::ostream& os = std::cout
01491 ) const;
01492 };
01493
01494
01495 #endif