00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00019 #ifndef RM3_DIME_ORTH_PLAN_UNDI_GRAPH_H
00020 #define RM3_DIME_ORTH_PLAN_UNDI_GRAPH_H
00021
00022 #if !defined(ROOT_INCL_ID)
00023 #define ROOT_INCL_ID 34009
00024 #endif
00025
00026
00027 #include <GDT/gdtlist.h>
00028 #include <GDT/gdtmap.h>
00029 #include <GDT/gdtgeometry.h>
00030 #include <GDT/rm3_undi_graph.h>
00031 #include <GDT/rm3_flow_dire_graph.h>
00032 #include <GDT/rm3_plan_undi_graph.h>
00033 #include <GDT/rm3_orth_plan_undi_graph.h>
00034
00035
00036
00037
00038
00039
00040
00041 #define NORTH 0
00042 #define EAST 1
00043 #define SOUTH 2
00044 #define WEST 3
00045
00059 class
00060 dime_orth_plan_undi_graph;
00061
00062
00063
00064
00065
00072 typedef enum
00073 {
00074 north = 0,
00075 east = 1,
00076 south = 2,
00077 west = 3,
00078 undefined_heading = 4
00079 }
00080 heading_type;
00081
00082
00083
00084 inline std::istream& operator >>(std::istream& in,heading_type& x)
00085 {in >> *((int *)((void *)&x));return(in); }
00086
00087
00088
00089
00095 typedef short
00096 heading_index_type;
00097
00098
00099
00105 typedef enum
00106 {
00107 horizontal = 0,
00108 vertical = 1,
00109 undefined_slope = 2
00110 }
00111 slope_type;
00112
00113
00114
00121 typedef struct
00122 {
00123 gdtnode north_node;
00124 gdtnode south_node;
00125 gdtnode east_node;
00126 gdtnode west_node;
00127 bool empty()
00128 {
00129 return (
00130 north_node == NULL_NODE &&
00131 east_node == NULL_NODE &&
00132 south_node == NULL_NODE &&
00133 west_node == NULL_NODE
00134 );
00135 }
00136 }
00137 map_node_set;
00138
00139
00147 typedef struct
00148 {
00149 int north_edge;
00150 int south_edge;
00151 int east_edge;
00152 int west_edge;
00153 }
00154 pos_incid_edges;
00155
00156
00157
00158
00163 typedef struct
00164 {
00165 gdtnode vt1;
00166 gdtnode vt2;
00167 int bend_cost;
00168 int cross_cost;
00169 int length_unit_cost;
00170 heading_type initial_heading;
00171 dire_graph map;
00172 gdt::gdtedge_map<gdtedge> edge_of_map_edge;
00173 gdt::gdtedge_map<gdtnode> node_of_map_edge;
00174 gdt::gdtedge_map<face> face_of_map_edge;
00175 gdt::gdtedge_map<std::string> bends_of_map_edge;
00176 gdt::gdtedge_map<map_node_set> map_nodes_of_edge;
00177 gdt::gdtnode_map<map_node_set> map_nodes_of_node;
00178 gdt::gdtedge_map<int> map_edge_cost;
00179 gdt::gdtlist<gdtedge> map_edge_path;
00180 gdt::gdtlist<gdtedge> edge_path;
00181 gdtnode mnt1;
00182 gdtnode mnt2;
00183 bool is_a_terminal_node (gdtnode n) {return (n == vt1 || n == vt2);}
00184 bool is_the_source_terminal_node (gdtnode n) {return (n == vt1);}
00185 bool is_the_sink_terminal_node (gdtnode n) {return (n == vt2);}
00186 gdtnode source_terminal () {return vt1;}
00187 gdtnode sink_terminal () {return vt2;}
00188
00189
00190
00191
00192
00193
00194
00195 }
00196 DD_struct;
00197
00202 class GDT_NONSTANDARD_DECL
00203 struct_dime_node_info
00204 {
00205 friend class dime_orth_plan_undi_graph;
00206 private:
00207 gdt::gdtpoint position;
00208 };
00209
00214 class GDT_NONSTANDARD_DECL
00215 struct_dime_edge_info
00216 {
00217 friend class dime_orth_plan_undi_graph;
00218 private:
00219 gdt::gdtlist<gdt::gdtpoint> bends_position;
00220 };
00221
00222
00235 typedef enum
00236 {
00237 source_terminal = 0,
00238 sink_terminal = 1
00239 }
00240 DD_terminal_node_type;
00241
00242
00272 typedef enum
00273 {
00274 ONLY_SINK_OR_SOURCE_DIAGONALS = 1,
00275 ONLY_SINK_OR_SOURCE_DIAGONALS_FOR_EAGLE_BOUNDARY_EDGE = 2,
00276 WALK_ALONG_AND_SINK_OR_SOURCE_DIAGONALS = 3
00277 }
00278 DD_edge_completament_type;
00279
00280
00286 class GDT_NONSTANDARD_DECL
00287 struct_dime_border_step_info
00288 {
00289 friend class dime_orth_plan_undi_graph;
00290 private:
00291 heading_type initial_heading;
00292 public:
00293
00294
00295
00296
00297
00298
00303 struct_dime_border_step_info
00304 (
00305 );
00306 };
00307
00308
00309
00310
00311 struct
00312 _solution
00313 {
00314 int score;
00315 heading_type eagle_heading;
00316 int number_of_steps;
00317 std::string bend_type;
00318
00319
00320
00321
00322 _solution()
00323 {
00324 score = INFINITE;
00325 eagle_heading = undefined_heading;
00326 number_of_steps = INFINITE;
00327 bend_type = "X";
00328
00329
00330
00331 }
00332
00333 _solution(const _solution& s)
00334 {
00335 *this = s;
00336 }
00337
00338 _solution&
00339 operator=(const _solution& s)
00340 {
00341 score = s.score;
00342 eagle_heading = s.eagle_heading;
00343 number_of_steps = s.number_of_steps;
00344 bend_type = s.bend_type;
00345
00346
00347
00348 return *this;
00349 }
00350 };
00351
00352
00353
00354
00355
00356
00385 class GDT_NONSTANDARD_DECL
00386 dime_orth_plan_undi_graph
00387 : public orth_plan_undi_graph
00388 {
00389 private:
00390
00391
00392
00393
00394 bool frozen_layout;
00395 heading_type reference_heading;
00396
00397 gdt::gdtnode_map<struct_dime_node_info>* node_info;
00398 gdt::gdtedge_map<struct_dime_edge_info>* edge_info;
00399 gdt::gdtmap<border_step,struct_dime_border_step_info>* border_step_info;
00400
00401
00402
00403
00404
00405
00406 void undefine(gdtnode n);
00407 void undefine(gdtedge e);
00408
00409
00410 void local_new();
00411 void local_del();
00412 void local_renew();
00413 void local_init(algorithm_type = SLOW_COMPACTION);
00414 void local_init(algorithm_type, heading_type dir, int& num_irr_faces);
00415
00416 void init_headings();
00417
00418
00419 void init_headings_and_positions(algorithm_type alg, heading_type dir, int& num_irr_faces);
00420
00421
00422
00423
00424
00425
00426 void init_headings_and_positions_with_rectangularization(algorithm_type alg);
00427
00428
00429
00430
00431 int init_headings_and_positions_with_regularity(algorithm_type alg);
00432
00433
00434
00435
00436
00437 void local_set
00438 (
00439 bool,
00440 heading_type,
00441 gdt::gdtnode_map<struct_dime_node_info>*,
00442 gdt::gdtedge_map<struct_dime_edge_info>*,
00443 gdt::gdtmap<border_step,struct_dime_border_step_info>*
00444 );
00445
00446
00447 void set_initial_heading_of_border_step (border_step, heading_type);
00448 void set_initial_heading_of_border_step_pair (border_step, heading_type);
00449
00450 void set_position_of_node (gdtnode,gdt::gdtpoint);
00451 void set_position_of_bends_along_edge (gdtedge, gdtnode, gdt::gdtlist<gdt::gdtpoint>);
00452
00453 void set_source (gdtedge, gdtnode);
00454
00455 border_step find_first_border_step_with_defined_heading_around_face (face) const;
00456
00457 void propagate_heading (border_step, heading_type);
00458
00459 void build_orthogonal_flow_network
00460 (
00461 flow_dire_graph& fn,
00462 gdt::gdtedge_map<gdtedge>& fn_edge,
00463 gdt::gdtlist<gdtedge>& L,
00464 slope_type scan_edge_slope
00465 ) const;
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479 std::string heading_to_string (heading_type h);
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490 void one_dimensional_metric_propagation( gdtnode v, const gdt::gdtedge_array<int>& len, slope_type slp );
00491
00492
00493
00494 bool
00495 from_node_direction_is_free
00496 (
00497 gdtnode n,
00498 heading_type h
00499 );
00500
00501 gdt::gdtpoint
00502 next_position_along_heading
00503 (
00504 gdt::gdtpoint p_n,
00505 heading_type h
00506 );
00507
00508 bool
00509 the_next_position_along_heading_is_free_from_real_node_and_orthogonal_edge
00510 (
00511 gdt::gdtpoint p_n,
00512 heading_type h,
00513 gdtnode &n,
00514 gdtedge &e
00515 );
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527 void
00528 DD_explore_eagle
00529 (
00530 _solution &tmp,
00531 gdtnode n,
00532 heading_type h
00533 );
00534
00535 gdtnode
00536
00537 DD_build_solution
00538 (
00539 const _solution &opt,
00540 gdtnode n
00541 );
00542
00543 gdtnode
00544 DD_attach_straigth_vertex_from_free_direction
00545 (
00546 gdtnode n,
00547 heading_type h
00548 );
00549
00550
00551
00552 void DD_verify_preliminary_conditions (DD_struct&);
00553 void DD_init_mappings (DD_struct&);
00554 void DD_create_map (DD_struct&);
00555 void DD_create_map_subnet_for_each_edge (DD_struct&);
00556 void DD_create_map_subnet_for_each_crossable_or_terminal_node (DD_struct&);
00557 void DD_create_map_nodes_around_each_crossable_or_terminal_node (DD_struct&);
00558 void DD_complete_map_subnet_for_each_crossable_node (DD_struct&);
00559 void DD_complete_map_subnet_for_both_terminal_nodes (DD_struct&);
00560 void DD_connect_map_subnets (DD_struct&);
00561 void DD_connect_map_subnets_for_edges_among_them (DD_struct&);
00562 void DD_connect_map_subnets_for_nodes_among_them (DD_struct&);
00563 void DD_connect_map_subnets_for_nodes_with_map_subnets_for_edges (DD_struct&);
00564 void DD_complete_map_subnet_with_particularity_of_terminal_nodes (DD_struct&);
00565 void DD_find_shortest_path_through_the_map (DD_struct&);
00566 void DD_build_dime_edge_path (DD_struct&);
00567
00568
00569
00570
00571 void DD_print_map (DD_struct&, std::string = "map.txt");
00572
00573 bool DD_node_can_be_crossed (gdtnode v);
00574 bool DD_from_this_terminal_the_other_one_is_along_heading(gdtnode first_term, DD_struct& DD, heading_type h);
00575 int DD_number_of_real_edges_around_node (gdtnode v);
00576
00577 bool edge_belongs_to_node (gdtedge e, gdtnode v);
00578
00579
00580
00581 void
00582 DD_create_map_edges_between_start_node_of_border_steps
00583
00584 (
00585 border_step bs1,
00586 heading_type hmn1,
00587 border_step bs2,
00588 heading_type hmn2,
00589 DD_struct& DD
00590 );
00591
00592 void
00593 DD_create_map_edges_between_border_steps
00594 (
00595 border_step bs1,
00596 border_step bs2,
00597 DD_struct& DD
00598 );
00599
00600 void
00601 DD_init_map_node_set
00602 (
00603 map_node_set& mns,
00604 gdtnode mn1,
00605 gdtnode mn2,
00606 gdtnode mn3,
00607 gdtnode mn4,
00608 heading_type hmn1
00609 );
00610
00611 void
00612 DD_get_map_node_set
00613 (
00614 map_node_set mns,
00615 gdtnode& mn1,
00616 gdtnode& mn2,
00617 gdtnode& mn3,
00618 gdtnode& mn4,
00619 heading_type hmn1
00620 );
00621
00622 gdtnode&
00623 DD_node_of_map_node_set_with_heading
00624 (
00625 map_node_set& mns,
00626 heading_type hmn
00627 );
00628
00629
00630
00631
00632 heading_type
00633 DD_heading_of_edge_with_max_thickness_around_bend_node
00634 (
00635 gdtnode n
00636 );
00637
00638 void
00639 DD_complete_map_subnet_for_terminal_node
00640 (
00641 DD_struct& DD,
00642 gdtnode tn,
00643 DD_terminal_node_type tnt
00644 );
00645
00646 bool
00647 DD_node_ends_a_terminal_line
00648 (
00649 gdtnode n,
00650 heading_type h
00651 );
00652
00653 gdt::gdtlist<gdtedge>
00654 DD_edge_sequence_along_terminal_line
00655 (
00656 DD_struct& DD,
00657 gdtnode tn,
00658 heading_type h,
00659 gdtedge& eb,
00660 bool& cross_last_node
00661 );
00662
00663 gdtedge
00664 DD_detect_the_eagle_boundary_edge
00665 (
00666 DD_struct& DD,
00667 gdtnode n,
00668 gdtedge e
00669 );
00670
00671 void
00672 DD_complete_map_subnet_of_edge
00673 (
00674 DD_struct& DD,
00675 gdtedge e,
00676 heading_type h,
00677 DD_terminal_node_type tnt,
00678 DD_edge_completament_type ect
00679 );
00680
00681 void
00682 DD_complete_map_subnet_of_dime_node
00683 (
00684 DD_struct& DD,
00685 gdtnode n,
00686 heading_type h,
00687 DD_terminal_node_type tnt
00688 );
00689
00690 void
00691 DD_connect_map_subnets_of_node_and_edge
00692 (
00693 DD_struct& DD,
00694 gdtnode n,
00695 gdtedge e,
00696 heading_type h,
00697 DD_terminal_node_type tnt
00698 );
00699
00700
00701
00702
00703
00704 void
00705 DD_increase_thickness_of_border_step
00706 (
00707 border_step bs
00708 );
00709
00710 angle_type
00711 DD_angle_of_bends_of_map_edge
00712 (
00713 gdtedge me,
00714 DD_struct& DD
00715 );
00716
00717 angle_type
00718 DD_angle_of_bends_of_map_edges_before_list_item_starting_from_node
00719 (
00720 gdt::list_item start_li,
00721 gdtnode n,
00722 DD_struct& DD
00723 );
00724
00725
00726
00727
00728
00729
00735 face
00736 DD_delete_edge
00737 (
00738 gdtedge e
00739 );
00740
00741
00742
00748 face
00749 DD_delete_node
00750 (
00751 gdtnode n
00752 );
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765 void
00766 set_initial_heading_of_edges_splitted_by_node
00767 (
00768 gdtnode n
00769 );
00770
00771
00772
00773
00774
00775
00776 bool
00777 the_graph_will_be_still_connected_after_deletion_of_node
00778 (
00779 gdtnode n
00780 );
00781
00788 gdtedge
00789 DD_find_first_partial_edge_with_unit_thick_on_edge
00790 (
00791 gdtedge e
00792 );
00793
00794
00799 face
00800 DD_delete_eagle_starting_from_node_along_edge
00801 (
00802 gdtnode to_be_deleted,
00803 gdtedge e,
00804 gdtnode connectivity_assurer
00805 );
00806
00807 gdtnode
00808 get_connectivity_assurer_node_when_deleting_node
00809 (
00810 gdtnode to_be_deleted
00811 );
00812
00813 void
00814 delete_connectivity_assurer_eagle_around_node
00815 (
00816 gdtnode connectivity_assurer,
00817 gdtnode to_be_deleted
00818 );
00819
00820
00821
00822 bool
00823 the_graph_will_be_still_connected_after_deletion_of_edge
00824 (
00825 gdtedge e
00826 );
00827
00828 face
00829 DD_delete_edge_without_rectangularization
00830 (
00831 gdtedge e
00832 );
00833
00834
00835
00836
00837
00838
00839
00840
00841
00842 void
00843 delete_all_dummy_paths_around_node
00844 (
00845 gdtnode n
00846 );
00847
00848 void
00849 delete_all_dummy_paths_and_nodes_around_node
00850 (
00851 gdtnode n
00852 );
00853
00854 gdt::gdtlist<gdtedge>
00855 complete_path_from_node_of_edge
00856 (
00857 gdtnode n,
00858 gdtedge e
00859 );
00860
00861 void
00862 DD_decrease_thickness_of_border_step
00863 (
00864 border_step bs
00865 );
00866
00867
00872 gdt::gdtlist<gdtedge>
00873 find_edges_path_corresponding_to_unit_thick_real_edge
00874 (
00875 gdtedge e
00876 );
00877
00878
00879
00880
00881
00882
00883
00884
00885 private:
00886 void position_bottom_left_corners_and_incid_edges
00887 (
00888 const gdt::gdtnode_array<int>& w,
00889 const gdt::gdtnode_array<int>& h,
00890 gdt::gdtnode_array<gdt::gdtpoint>& pos_bottom_left,
00891 gdt::gdtnode_array<pos_incid_edges>& pie
00892 ) const;
00893
00894
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907
00908 void position_bottom_left_corners_and_incid_edges_centered
00909 (
00910 const gdt::gdtnode_array<int>& w,
00911 const gdt::gdtnode_array<int>& h,
00912 gdt::gdtnode_array<gdt::gdtpoint>& pos_bottom_left,
00913 gdt::gdtnode_array<pos_incid_edges>& pie
00914 ) const;
00915
00916
00917
00918
00919
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929
00930
00931
00932 void position_bottom_left_corners_and_incid_edges_with_pins
00933 (
00934 const gdt::gdtnode_array<int>& w,
00935 const gdt::gdtnode_array<int>& h,
00936 gdt::gdtnode_array<gdt::gdtpoint>& pos_bottom_left,
00937 gdt::gdtnode_array<pos_incid_edges>& pie
00938 ) const;
00939
00940
00941
00942
00943
00944
00945
00946
00947
00948
00949
00950
00951
00952
00953
00954 void expand_nodes_into_super_nodes
00955 (
00956 const dime_orth_plan_undi_graph& dopug,
00957 const gdt::gdtnode_array<int>& w,
00958 const gdt::gdtnode_array<int>& h,
00959 const gdt::gdtnode_array<gdt::gdtpoint>& pos_bottom_left,
00960 const gdt::gdtnode_array<pos_incid_edges>& pie,
00961 gdt::gdtnode_map<gdtnode>& super_node
00962 );
00963
00964
00965
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980 void expand_nodes_into_super_nodes_with_pins
00981 (
00982 const dime_orth_plan_undi_graph& dopug,
00983 const gdt::gdtnode_array<int>& w,
00984 const gdt::gdtnode_array<int>& h,
00985 const gdt::gdtnode_array<gdt::gdtpoint>& pos_bottom_left,
00986 const gdt::gdtnode_array<pos_incid_edges>& pie,
00987 gdt::gdtnode_map<gdtnode>& super_node,
00988 gdt::gdtnode_map<bool>& is_removable,
00989 gdt::gdtedge_map<bool>& removable_edge
00990 );
00991
00992
00993
00994
00995
00996
00997
00998
00999
01000
01001
01002
01003
01004
01005
01006
01007
01008
01009
01010 void expand_node_into_super_node
01011 (
01012 gdtnode v,
01013 int width,
01014 int height,
01015 int bl_x,
01016 int bl_y,
01017 pos_incid_edges pie_v,
01018 gdt::gdtlist<gdtnode>& N
01019 );
01020
01021
01022
01023
01024
01025
01026
01027
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044
01045
01046
01047
01048
01049 void expand_node_into_super_node_with_pins
01050 (
01051 gdtnode v,
01052 int width,
01053 int height,
01054 int bl_x,
01055 int bl_y,
01056 pos_incid_edges pie_v,
01057 gdt::gdtlist<gdtnode>& N,
01058 gdt::gdtnode_map<bool>& is_removable,
01059 gdt::gdtedge_map<bool>& removable_edge
01060 );
01061
01062
01063
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088
01089
01090
01091
01092
01093
01094
01095
01096
01097 void expand_node_into_chain
01098 (
01099 gdtnode v,
01100 int length,
01101 heading_type dir,
01102 gdt::gdtlist<gdtnode>& N
01103 );
01104
01105
01106
01107
01108
01109
01110
01111
01112
01113
01114
01115
01116
01117 gdtedge change_node_of_edge_with_node
01118 (
01119 gdtnode v1,
01120 gdtedge e1,
01121 gdtnode v2
01122 );
01123
01124
01125
01126
01127
01128
01129
01130
01131 void uncompress_edges
01132 (
01133 const dime_orth_plan_undi_graph& dopug,
01134 const gdt::gdtnode_array<int>& w,
01135 const gdt::gdtnode_array<int>& h,
01136 const gdt::gdtnode_array<pos_incid_edges>& pie,
01137 gdt::gdtnode_map<gdtnode>& super_node
01138 );
01139
01140
01141
01142
01143
01144
01145
01146
01147
01148 void uncompress_edges_with_pins
01149 (
01150 const dime_orth_plan_undi_graph& dopug,
01151 const gdt::gdtnode_array<int>& w,
01152 const gdt::gdtnode_array<int>& h,
01153 const gdt::gdtnode_array<pos_incid_edges>& pie,
01154 gdt::gdtnode_map<gdtnode>& super_node,
01155 gdt::gdtnode_map<bool>& is_removable,
01156 gdt::gdtedge_map<bool>& removable_edge
01157 );
01158
01159
01160
01161
01162
01163
01164
01165
01166 gdt::gdtlist<gdtnode> expand_chain
01167 (
01168 gdtnode v,
01169 slope_type dir,
01170 int length,
01171 gdt::gdtlist<gdtedge>& zero_edges
01172 );
01173
01174
01175
01176
01177
01178
01179
01180
01181
01182
01183 gdt::gdtlist<gdtnode> corners_of_super_nodes
01184 (
01185 const dime_orth_plan_undi_graph& dopug,
01186 const gdt::gdtnode_map<gdtnode>& super_node,
01187 const gdt::gdtnode_array<int>& w,
01188 const gdt::gdtnode_array<int>& h
01189 ) const;
01190
01191
01192
01193 gdtedge move_edge_close_to_corner_of_super_node
01194 (
01195 gdtedge e,
01196 gdtnode v,
01197 gdt::gdtnode_map<gdtnode>& super_node,
01198 gdt::gdtedge_map<bool>& is_zero_edge
01199 );
01200
01201
01202 void construct_dime_orth_plan_undi_graph
01203 (
01204 const undi_graph& ug,
01205 algorithm_type alg,
01206 int& num_irr_faces
01207 );
01208
01209
01210 void construct_dime_orth_plan_undi_graph
01211 (
01212 const plan_undi_graph& pug,
01213 algorithm_type alg,
01214 int& numm_irr_faces
01215 );
01216
01217
01218 void construct_dime_orth_plan_undi_graph
01219 (
01220 const orth_plan_undi_graph& opug,
01221 algorithm_type alg,
01222 heading_type dir,
01223 int& num_irr_faces
01224 );
01225
01226
01227
01228 public:
01229
01230
01231
01232
01233
01234
01239 dime_orth_plan_undi_graph
01240 (
01241 );
01242
01243
01244
01245
01246
01247 ~dime_orth_plan_undi_graph
01248 (
01249 );
01250
01251
01257 dime_orth_plan_undi_graph
01258 (
01259 const undi_graph& ug,
01260 algorithm_type alg = SLOW_COMPACTION
01261 );
01262
01263
01271 dime_orth_plan_undi_graph
01272 (
01273 const undi_graph& ug,
01274 algorithm_type alg,
01275 int& num_irr_faces
01276 );
01277
01283 dime_orth_plan_undi_graph
01284 (
01285 const plan_undi_graph& pug,
01286 algorithm_type alg = SLOW_COMPACTION
01287 );
01288
01289
01297 dime_orth_plan_undi_graph
01298 (
01299 const plan_undi_graph& pug,
01300 algorithm_type alg,
01301 int& numm_irr_faces
01302 );
01303
01304
01310 dime_orth_plan_undi_graph
01311 (
01312 const orth_plan_undi_graph& opug,
01313 algorithm_type alg = SLOW_COMPACTION
01314 );
01315
01316
01324 dime_orth_plan_undi_graph
01325 (
01326 const orth_plan_undi_graph& opug,
01327 algorithm_type alg,
01328 heading_type dir
01329 );
01330
01331
01341 dime_orth_plan_undi_graph
01342 (
01343 const orth_plan_undi_graph& opug,
01344 algorithm_type alg,
01345 heading_type dir,
01346 int& num_irr_faces
01347 );
01348
01349
01354 dime_orth_plan_undi_graph
01355 (
01356 const dime_orth_plan_undi_graph& dopug
01357 );
01358
01359
01360
01361
01362
01363
01368 dime_orth_plan_undi_graph&
01369 operator =
01370 (
01371 const undi_graph& ug
01372 );
01373
01378 dime_orth_plan_undi_graph&
01379 operator =
01380 (
01381 const plan_undi_graph& pug
01382 );
01383
01388 dime_orth_plan_undi_graph&
01389 operator =
01390 (
01391 const orth_plan_undi_graph& opug
01392 );
01393
01398 dime_orth_plan_undi_graph&
01399 operator =
01400 (
01401 const dime_orth_plan_undi_graph& dopug
01402 );
01403
01404
01405
01406
01407
01408
01413 void
01414 local_get
01415 (
01416 bool& p1,
01417 heading_type& p2,
01418 gdt::gdtnode_map<struct_dime_node_info>*& p3,
01419 gdt::gdtedge_map<struct_dime_edge_info>*& p4,
01420 gdt::gdtmap<border_step,struct_dime_border_step_info>*& p5
01421 );
01422
01427 heading_type
01428 initial_heading_of_border_step
01429 (
01430 border_step s
01431 ) const;
01432
01437 heading_type
01438 heading_after_border_step
01439 (
01440 border_step s
01441 ) const;
01442
01443 static
01449 heading_type
01450 heading_after_rotation
01451 (
01452 heading_type d,
01453 angle_type a
01454 );
01455
01456
01461 heading_type
01462 heading_after_rotation_around_bend
01463 (
01464 heading_type d,
01465 angle_type a
01466 ) const;
01467
01472 heading_type
01473 heading_after_inversion
01474 (
01475 heading_type d
01476 ) const;
01477
01482 heading_type
01483 heading_after_bend
01484 (
01485 heading_type d,
01486 bend_type b
01487 ) const;
01488
01494 heading_type
01495 heading_after_bend_sequence
01496 (
01497 heading_type d,
01498 gdt::gdtlist<bend_type> bl
01499 ) const;
01500
01506 gdt::gdtlist<bend_type>
01507 minimal_bend_sequence_required_to_change_heading
01508 (
01509 heading_type i,
01510 heading_type f
01511 ) const;
01512
01521 heading_type
01522 position_of_node_with_respect_to_edge
01523 (
01524 gdtnode v,
01525 gdtedge e
01526 ) const;
01527
01536 heading_type
01537 position_of_edge_with_respect_to_node
01538 (
01539 gdtedge e,
01540 gdtnode v
01541 ) const;
01542
01548 heading_type
01549 position_of_node_with_respect_to_node
01550 (
01551 gdtnode v1,
01552 gdtnode v2
01553 ) const;
01554
01559 gdtedge
01560 find_edge_leaving_node_with_heading
01561 (
01562 gdtnode v,
01563 heading_type d
01564 ) const;
01565
01571 gdtnode
01572 find_node_reachable_moving_from_node_with_heading
01573 (
01574 gdtnode v,
01575 heading_type d
01576 ) const;
01577
01584 gdtnode
01585 find_node_reachable_moving_from_node_with_heading
01586 (
01587 gdtnode v,
01588 heading_type d,
01589 gdtedge& e
01590 ) const;
01591
01592
01593
01594
01595
01596
01602 gdtnode
01603 find_node_after_edge_along_heading
01604 (
01605 gdtedge e,
01606 heading_type h
01607 );
01608
01614 face
01615 face_visible_from_node_looking_with_heading
01616 (
01617 gdtnode v,
01618 heading_type h
01619 ) const;
01620
01625 gdt::gdtpoint
01626 position_of_node
01627 (
01628 gdtnode v
01629 ) const;
01630
01635 gdt::gdtlist<gdt::gdtpoint>
01636 position_of_bends_along_edge
01637 (
01638 gdtedge e,
01639 gdtnode v
01640 ) const;
01641
01646 slope_type
01647 opposite_slope
01648 (
01649 slope_type s
01650 ) const;
01651
01656 slope_type
01657 slope_along_heading
01658 (
01659 heading_type d
01660 ) const;
01661
01666 slope_type
01667 slope_of_border_step
01668 (
01669 border_step s
01670 ) const;
01671
01676 slope_type
01677 slope_of_edge
01678 (
01679 gdtedge e
01680 ) const;
01681
01689 gdt::gdtlist<gdtnode>
01690 nodes_reachable_moving_from_node_with_slope
01691 (
01692 gdtnode v,
01693 slope_type slope
01694 ) const;
01695
01696
01706 gdt::gdtlist<gdtnode>
01707 nodes_reachable_moving_from_node_with_slope
01708 (
01709 gdtnode v,
01710 slope_type slope,
01711 gdt::gdtlist<gdtedge>& edge_chain
01712 ) const;
01713
01714
01715
01720 int
01721 length_of_edge
01722 (
01723 gdtedge e
01724 ) const;
01725
01731 int
01732 border_distance
01733 (
01734 gdtnode v1,
01735 gdtnode v2,
01736 face f
01737 ) const;
01738
01745 int
01746 border_distance
01747 (
01748 gdtnode v,
01749 gdtedge e,
01750 face f
01751 ) const;
01752
01759 int
01760 border_distance
01761 (
01762 gdtedge e,
01763 gdtnode v,
01764 face f
01765 ) const;
01766
01773 int
01774 border_distance
01775 (
01776 gdtedge e1,
01777 gdtedge e2,
01778 face f
01779 ) const;
01780
01788 int
01789 min_border_distance
01790 (
01791 gdtnode v1,
01792 gdtnode v2,
01793 face f,
01794 bool& ordered
01795 ) const;
01796
01804 int
01805 min_border_distance
01806 (
01807 gdtnode v,
01808 gdtedge e,
01809 face f,
01810 bool& ordered
01811 ) const;
01812
01820 int
01821 min_border_distance
01822 (
01823 gdtedge e1,
01824 gdtedge e2,
01825 face f,
01826 bool& ordered
01827 ) const;
01828
01829
01830
01831
01832
01837 int
01838 inline_distance
01839 (
01840 gdtnode v1,
01841 gdtnode v2,
01842 slope_type slope
01843 ) const;
01844
01849 int
01850 inline_distance
01851 (
01852 gdtnode v,
01853 gdtedge e
01854 ) const;
01855
01860 int
01861 inline_distance
01862 (
01863 gdtedge e1,
01864 gdtedge e2
01865 ) const;
01866
01871 int
01872 traversal_distance
01873 (
01874 gdtnode v1,
01875 gdtnode v2,
01876 slope_type slope
01877 ) const;
01878
01883 int
01884 traversal_distance
01885 (
01886 gdtnode v,
01887 gdtedge e
01888 ) const;
01889
01894 int
01895 traversal_distance
01896 (
01897 gdtedge e1,
01898 gdtedge e2
01899 ) const;
01900
01901
01902
01907 angle_type
01908 angle_on_node
01909 (
01910 gdtnode v,
01911 face f
01912 ) const;
01913
01919 angle_type
01920 rotation_around_bend_required_to_change_heading
01921 (
01922 heading_type initial,
01923 heading_type final
01924 ) const;
01925
01926
01927
01928 static
01935 angle_type
01936 angle_required_to_change_heading
01937 (
01938 heading_type initial,
01939 heading_type final
01940 );
01941
01942
01953 void
01954 compute_dime_with_expanded_nodes
01955 (
01956 gdt::gdtnode_array<int>& w,
01957 gdt::gdtnode_array<int>& h,
01958 dime_orth_plan_undi_graph& dopug,
01959 gdt::gdtnode_map<gdtnode>& super_node
01960 ) const;
01961
01962
01974 void
01975 compute_dime_with_expanded_nodes_and_edges_centered
01976 (
01977 gdt::gdtnode_array<int>& w,
01978 gdt::gdtnode_array<int>& h,
01979 dime_orth_plan_undi_graph& dopug,
01980 gdt::gdtnode_map<gdtnode>& super_node
01981 ) const;
01982
01983
01984
01985
01986
02000 void
02001 compute_dime_with_expanded_nodes_and_pins
02002 (
02003 const gdt::gdtnode_array<int>& w,
02004 const gdt::gdtnode_array<int>& h,
02005 dime_orth_plan_undi_graph& dopug,
02006 gdt::gdtnode_map<gdtnode>& super_node
02007 ) const;
02008
02009
02010
02016 bool
02017 edge_is_dummy
02018 (
02019 gdtedge
02020 ) const;
02021
02022
02027 bool
02028 edge_is_real
02029 (
02030 gdtedge
02031 ) const;
02032
02033
02042 bool
02043 node_is_dummy
02044 (
02045 gdtnode
02046 ) const;
02047
02048
02053 bool
02054 node_is_real
02055 (
02056 gdtnode
02057 ) const;
02058
02059
02060
02072 void
02073 build_embedded_posets
02074 (
02075 plan_undi_graph& pug_v,
02076 plan_undi_graph& pug_h,
02077 gdt::gdtnode_map<gdtnode>& node_in_pug_v,
02078 gdt::gdtnode_map<gdtnode>& node_in_pug_h
02079 );
02080
02081
02082
02083
02084
02085
02086
02087
02097 gdtnode
02098 new_node
02099 (
02100 gdtedge e,
02101 int new_id = AUTO_ID
02102 );
02103
02104
02113 gdtnode
02114 new_node
02115 (
02116 gdtedge e,
02117 gdtnode v,
02118 int dist,
02119 int new_id = AUTO_ID
02120 );
02121
02122
02136 gdtnode
02137 new_node
02138 (
02139 gdtnode v,
02140 heading_type dir,
02141 int dist,
02142 int new_node_id = AUTO_ID,
02143 int new_edge_id = AUTO_ID
02144 );
02145
02146
02147
02156 gdtedge
02157 new_straight_edge
02158 (
02159 gdtnode v,
02160 gdtnode w,
02161 int new_id=AUTO_ID
02162 );
02163
02164
02165
02173 gdtedge
02174 new_edge
02175 (
02176 gdtnode v,
02177 gdtnode w,
02178 face f,
02179 int new_id=AUTO_ID
02180 );
02181
02189 gdtedge
02190 new_edge
02191 (
02192 gdtnode v,
02193 gdtedge ev,
02194 gdtnode w,
02195 gdtedge ew,
02196 int new_id=AUTO_ID
02197 );
02198
02203 face
02204 del_node
02205 (
02206 gdtnode v
02207 );
02208
02213 face
02214 del_edge
02215 (
02216 gdtedge e
02217 );
02218
02219
02230 void
02231 attach_nodes_by_chain
02232 (
02233 gdtnode v1,
02234 gdtnode v2,
02235 gdt::gdtlist<gdtnode>& N
02236 );
02237
02238
02245 gdtedge
02246 weld_edges_at_node
02247 (
02248 gdtnode v
02249 );
02250
02251
02258 gdtedge
02259 replace_node_with_bend
02260 (
02261 gdtnode v
02262 );
02263
02272 void
02273 replace_bend_with_node
02274 (
02275 gdtedge e,
02276 gdtnode v,
02277 int pos,
02278 gdt::gdtlist<gdtnode>& N,
02279 gdt::gdtlist<gdtedge>& E
02280 );
02281
02282
02283
02284
02285
02286
02287
02294 void
02295 replace_bends_with_nodes
02296 (
02297 gdtedge e,
02298 gdt::gdtlist<gdtnode>& N,
02299 gdt::gdtlist<gdtedge>& E
02300 );
02301
02302
02309 void
02310 replace_bends_with_nodes
02311 (
02312 face f,
02313 gdt::gdtlist<gdtnode>& N,
02314 gdt::gdtlist<gdtedge>& E
02315 );
02316
02317
02324 void
02325 replace_bends_with_nodes
02326 (
02327 gdt::gdtlist<gdtnode>& N,
02328 gdt::gdtlist<gdtedge>& E
02329 );
02330
02331
02339 void
02340 update_node_and_bend_positions_according_to
02341 (
02342 dime_orth_plan_undi_graph& dopug
02343 );
02344
02345
02346
02347
02348
02388 void
02389 one_dimensional_tieing ( const gdt::gdtmap<int, int>& min,
02390 const gdt::gdtmap<int, int>& max,
02391 const gdt::gdtmap<int, int>& cost,
02392 slope_type slp,
02393 unsigned int min_tieing_dist=1
02394 );
02395
02396
02397
02398
02421 void
02422 one_dimensional_tieing_for_expanded_nodes
02423 (
02424 const gdt::gdtmap<int, int>& min,
02425 const gdt::gdtmap<int, int>& max,
02426 const gdt::gdtmap<int, int>& cost,
02427 slope_type slp,
02428 const gdt::gdtmap<int, int>& extent,
02429 unsigned int min_tieing_dist=1
02430 );
02431
02432
02433
02434
02435
02436
02437
02438
02439
02449 void
02450 DD_dynamic_new_edge
02451 (
02452 gdtnode v1,
02453 gdtnode v2,
02454 int cross_cost,
02455 int bend_cost,
02456 int length_unit_cost
02457 );
02458
02459
02460
02467 gdtnode
02468 DD_dynamic_attach_vertex
02469 (
02470 gdtnode n
02471 );
02472
02473
02474
02475
02476
02477
02478
02479
02480
02481 void
02482 remove_all_dummy_nodes_and_edges
02483 (
02484 );
02485
02486
02487
02492 void
02493 clear
02494 (
02495 );
02496
02506 void
02507 steal_from
02508 (
02509 undi_graph& ug
02510 );
02511
02520 void
02521 steal_from
02522 (
02523 plan_undi_graph& pug
02524 );
02525
02534 void
02535 steal_from
02536 (
02537 orth_plan_undi_graph& opug
02538 );
02539
02544 void
02545 mirror
02546 (
02547 dime_orth_plan_undi_graph& dopug
02548 );
02549
02554 void
02555 forget
02556 (
02557 );
02558
02559
02560
02561
02562
02563
02564
02569 void
02570 print
02571 (
02572 print_mode mode=BY_FACES,
02573 std::ostream& os=std::cout
02574 ) const;
02575
02580 void
02581 print
02582 (
02583 gdtnode v,
02584 std::ostream& os = std::cout
02585 ) const;
02586
02591 void
02592 print
02593 (
02594 gdtedge e,
02595 bool path = false,
02596 std::ostream& os = std::cout
02597 ) const;
02598
02603 void
02604 print
02605 (
02606 face f,
02607 std::ostream& os = std::cout
02608 ) const;
02609 };
02610
02611
02612 #endif