Graph Drawing Toolkit
00001 /******************************************************************************* 00002 + 00003 + rm3_dime_orth_plan_undi_graph.h 00004 + 00005 + This file is part of GDToolkit. It can be 00006 + used free of charge in academic research and teaching. 00007 + Any direct or indirect commercial use of this software is illegal 00008 + without a written authorization of 00009 + the Dipartimento di Informatica e Automazione 00010 + Universita' di Roma Tre, Roma, ITALIA 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 SOURCEFILE rm3_dime_orth_plan_undi_graph.h 00037 To be defined. 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; // forward declaration 00061 00062 // -------------------------- 00063 // enumerate type for heading 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; // source terminal dime-gdtnode of the dime-gdtedge to be created 00166 gdtnode vt2; // sink terminal dime-gdtnode of the dime-gdtedge to be created 00167 int bend_cost; // bend cost 00168 int cross_cost; // cross cost 00169 int length_unit_cost; // length unit cost 00170 heading_type initial_heading; // heading of the first gdtedge of the minimal-cost path 00171 dire_graph map; // map 00172 gdt::gdtedge_map<gdtedge> edge_of_map_edge; // map-gdtedge -> real or dummy dime-gdtedge 00173 gdt::gdtedge_map<gdtnode> node_of_map_edge; // map_edge -> dummy dime-gdtnode 00174 gdt::gdtedge_map<face> face_of_map_edge; // map-gdtedge -> face crossed by the map-gdtedge 00175 gdt::gdtedge_map<std::string> bends_of_map_edge; // map_edge -> sequence of bends 00176 gdt::gdtedge_map<map_node_set> map_nodes_of_edge; // dime-gdtedge -> set(map-gdtnode) 00177 gdt::gdtnode_map<map_node_set> map_nodes_of_node; // dime-gdtnode -> set(map-gdtnode) 00178 gdt::gdtedge_map<int> map_edge_cost; // map gdtedge -> cost 00179 gdt::gdtlist<gdtedge> map_edge_path; // list of map-edges along the shortest path from mnt1 to mnt2 00180 gdt::gdtlist<gdtedge> edge_path; // sequence of the new dime-edges created between vt1 and vt2 00181 gdtnode mnt1; // map-gdtnode centered on vt1 00182 gdtnode mnt2; // map-gdtnode centered on vt2 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 /* bool map_node_belongs_to_node (gdtnode mn, gdtnode n) 00189 { 00190 map_node_set mns = map_nodes_of_node[n]; 00191 if (!mns.empty()) 00192 if (mns.north_node == mn || mns.east_node == mn || mns.south_node == mn || mns.west_node == mn) return true; 00193 return false; 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; // Ordered from source to target 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 CATEGORYremoved constructors_destructors 00296 Constructors and destructors. 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 //bool node_have_space; 00319 //gdtnode no_space_because_node; 00320 //gdtedge no_space_because_edge; 00321 00322 _solution() 00323 { 00324 score = INFINITE; 00325 eagle_heading = undefined_heading; 00326 number_of_steps = INFINITE; 00327 bend_type = "X"; 00328 //node_have_space = false; 00329 //no_space_because_node = NULL_NODE; 00330 //no_space_because_edge = NULL_EDGE; 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 //node_have_space = s.node_have_space; 00346 //no_space_because_node = s.no_space_because_node; 00347 //no_space_because_edge = s.no_space_because_edge; 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 // private variables 00392 // ----------------- 00393 00394 bool frozen_layout; // is true, the compaction algorithm is not automatically executed after dynamic new gdtedge 00395 heading_type reference_heading; // heading of the reference border_step 00396 00397 gdt::gdtnode_map<struct_dime_node_info>* node_info; // correspondence gdtnode --> dime_orth_plan_undi-gdtnode structure 00398 gdt::gdtedge_map<struct_dime_edge_info>* edge_info; // correspondence gdtedge --> dime_orth_plan_undi-gdtedge structure 00399 gdt::gdtmap<border_step,struct_dime_border_step_info>* border_step_info; // correspondence GDT-border_step --> dime_orth_plan_undi-border_step structure 00400 00401 // --------------- 00402 // private methods 00403 // --------------- 00404 00405 //Added by Marcandalli 16 10 2001 00406 void undefine(gdtnode n); 00407 void undefine(gdtedge e); 00408 // 00409 00410 void local_new(); // create a new set of pointers for the not-inherited class-part 00411 void local_del(); // delete the not-inherited class-part 00412 void local_renew(); // local_del(), then local_new(). 00413 void local_init(algorithm_type = SLOW_COMPACTION); // init the not-inherited class-part 00414 void local_init(algorithm_type, heading_type dir, int& num_irr_faces); // init the not-inherited class-part 00415 00416 void init_headings(); // compute all border_step headings after rectangularization step 00417 00418 00419 void init_headings_and_positions(algorithm_type alg, heading_type dir, int& num_irr_faces); // compute all border_step headings, and gdtnode and bend positions, according to the selected algorithm alg. 00420 // The algorithm alg can be one of the following: 00421 // FAST_COMPACTION, SLOW_COMPACTION, FAST_COMPACTION_REFINED, SLOW_COMPACTION_REFINED, 00422 // FAST_REGULAR_COMPACTION_1, SLOW_REGULAR_COMPACTION_1, FAST_REGULAR_COMPACTION_1_REFINED, SLOW_REGULAR_COMPACTION_1_REFINED, 00423 // FAST_REGULAR_COMPACTION_2, SLOW_REGULAR_COMPACTION_2, FAST_REGULAR_COMPACTION_2_REFINED, SLOW_REGULAR_COMPACTION_2_REFINED. 00424 // num_irr_faces is the number of irregular faces when a method based on regularization is applied. 00425 00426 void init_headings_and_positions_with_rectangularization(algorithm_type alg); // This method executes a standard compaction algorithm and alg can be one of the following: 00427 // FAST_COMPACTION, SLOW_COMPACTION, FAST COMPACTION_REFINED, and SLOW_COMPACTION_REFINED. 00428 // FAST_REGULAR_COMPACTION_1, SLOW_REGULAR_COMPACTION_1, FAST_REGULAR_COMPACTION_1_REFINED, SLOW_REGULAR_COMPACTION_1_REFINED, 00429 // FAST_REGULAR_COMPACTION_2, SLOW_REGULAR_COMPACTION_2, FAST_REGULAR_COMPACTION_2_REFINED, SLOW_REGULAR_COMPACTION_2_REFINED. 00430 00431 int init_headings_and_positions_with_regularity(algorithm_type alg); // This method executes a new compaction algorithm based on the regularity concept, and 00432 // alg can be set to 00433 // FAST_REGULAR_COMPACTION_1, SLOW_REGULAR_COMPACTION_1, FAST_REGULAR_COMPACTION_1_REFINED, SLOW_REGULAR_COMPACTION_1_REFINED, 00434 // FAST_REGULAR_COMPACTION_2, SLOW_REGULAR_COMPACTION_2, FAST_REGULAR_COMPACTION_2_REFINED, SLOW_REGULAR_COMPACTION_2_REFINED. 00435 // The method returns the number of irregular faces 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 ); // set all private variables 00445 00446 00447 void set_initial_heading_of_border_step (border_step, heading_type); // set the initial heading of border_step with heading_type 00448 void set_initial_heading_of_border_step_pair (border_step, heading_type); // set the initial haeding of border_step and its opposite with heading_type and its opposite, respectively 00449 00450 void set_position_of_node (gdtnode,gdt::gdtpoint); // set position of gdtnode with point 00451 void set_position_of_bends_along_edge (gdtedge, gdtnode, gdt::gdtlist<gdt::gdtpoint>); // set position of all bends of gdtedge starting from gdtnode with gdt::gdtlist<point> 00452 00453 void set_source (gdtedge, gdtnode); // set gdtnode as source of gdtnode 00454 00455 border_step find_first_border_step_with_defined_heading_around_face (face) const; // find the first border_step of face that has a defined heading 00456 00457 void propagate_heading (border_step, heading_type); // compute all headings according to the heading_type for border_step 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; // see below.. 00466 00467 // ------------------------------------------------------------------------------------ 00468 // build horizontal/vertical flow network associated to the rectangularized orthogonal 00469 // representation, that is the dual directed graph for computing a compaction algorithm 00470 // based on flow techniques. 00471 // 00472 // fn = flow network associated to the orthogonal representation; 00473 // fn_edge = mapping from orthogonal gdtedge to fn gdtedge; 00474 // L = list of orthogonal edges on a longest path; 00475 // scan_edge_slope = vertical or horizontal 00476 // ------------------------------------------------------------------------------------ 00477 00478 00479 std::string heading_to_string (heading_type h); // return the string corresponding to the heading h 00480 00481 00482 00483 // This method sets the coordinates of the nodes in 00484 // the graphs according to the length provided in 00485 // "len". The length should be specified for all the 00486 // edges with slope equal to "slp". 00487 // The only gdtnode that is not moved is "v". 00488 // REQUIREMENTS: graph must be linearized (bends replaced with dummy vertices). 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, //start point 00512 heading_type h, //along this heading the next position is determined 00513 gdtnode &n, //possible gdtnode that occupies the next position 00514 gdtedge &e //possible gdtedge that occupies the next position 00515 ); 00516 00517 // --------------------------- 00518 // Methods for dynamic drawing 00519 // --------------------------- 00520 00521 00522 00523 00524 00525 // Steps of the attach_vertex dynamic orthogonal algorithm. 00526 // 00527 void 00528 DD_explore_eagle 00529 ( 00530 _solution &tmp, //temporary solution 00531 gdtnode n, //start gdtnode of the eagle 00532 heading_type h //heading of the eagle to explore 00533 ); 00534 00535 gdtnode 00536 //dime_orth_plan_undi_graph:: 00537 DD_build_solution 00538 ( 00539 const _solution &opt, //optimal solution 00540 gdtnode n //gdtnode on which the new vertex must be attached 00541 ); 00542 00543 gdtnode 00544 DD_attach_straigth_vertex_from_free_direction //a direction is free when there is no gdtedge or a dummy gdtedge 00545 ( 00546 gdtnode n, //gdtnode on which the new vertex must be attached 00547 heading_type h //heading of the new vertex respect to n 00548 ); 00549 00550 // Steps of the new_edge dynamic orthogonal algorithm. 00551 // 00552 void DD_verify_preliminary_conditions (DD_struct&); //STEP 1 00553 void DD_init_mappings (DD_struct&); //STEP 2 00554 void DD_create_map (DD_struct&); //STEP 3 00555 void DD_create_map_subnet_for_each_edge (DD_struct&); //STEP 3.1 00556 void DD_create_map_subnet_for_each_crossable_or_terminal_node (DD_struct&); //STEP 3.2 00557 void DD_create_map_nodes_around_each_crossable_or_terminal_node (DD_struct&); //STEP 3.2.1 00558 void DD_complete_map_subnet_for_each_crossable_node (DD_struct&); //STEP 3.2.2 00559 void DD_complete_map_subnet_for_both_terminal_nodes (DD_struct&); //STEP 3.2.3 00560 void DD_connect_map_subnets (DD_struct&); //STEP 3.3 00561 void DD_connect_map_subnets_for_edges_among_them (DD_struct&); //STEP 3.3.1 00562 void DD_connect_map_subnets_for_nodes_among_them (DD_struct&); //STEP 3.3.2 00563 void DD_connect_map_subnets_for_nodes_with_map_subnets_for_edges (DD_struct&); //STEP 3.3.3 00564 void DD_complete_map_subnet_with_particularity_of_terminal_nodes (DD_struct&); //STEP 3.4 added for expansion to >4plan 00565 void DD_find_shortest_path_through_the_map (DD_struct&); //STEP 4 00566 void DD_build_dime_edge_path (DD_struct&); //STEP 5 00567 00568 // Utility functions, 00569 // and subroutines of the algorithm steps 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 // For step 3.3.x 00580 00581 void 00582 DD_create_map_edges_between_start_node_of_border_steps 00583 00584 ( 00585 border_step bs1, // border_step whose start-gdtnode v1 owns the first map_node to be connected 00586 heading_type hmn1, // heading determining which map-gdtnode must be connected, among the map-nodes associated to v1 00587 border_step bs2, // border_step whose start-gdtnode v2 owns the second map_node to be connected 00588 heading_type hmn2, // heading determining which map-gdtnode must be connected, among the map-nodes associated to v2 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 // For step 3.4 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 ); //STEP 3.4.1 00645 00646 bool 00647 DD_node_ends_a_terminal_line 00648 ( 00649 gdtnode n, 00650 heading_type h 00651 ); //STEP 3.4.1.0 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, //this gdtedge is the eagle boundary gdtedge if in the research of the sequence is detected 00660 bool& cross_last_node 00661 ); //STEP 3.4.1.1 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 ); //STEP 3.4.1.2 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 ); //STEP 3.4.1.3 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 ); //STEP 3.4.1.4 00699 00700 00701 00702 // For step 5 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, // map gdtedge 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, // map gdtedge 00721 gdtnode n, // dime gdtnode 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 // PRECONDITION: 00757 // The gdtnode n must have two and only edges and 00758 // these edges must have the opposite nodes respect to n 00759 // on the same horizontal or vertical line. 00760 // This is the tipical situation of an gdtedge splitted by a gdtnode n 00761 // with orth::new_node (the orth class not know the headings) 00762 // 00763 */ 00764 00765 void 00766 set_initial_heading_of_edges_splitted_by_node 00767 ( 00768 gdtnode n 00769 ); 00770 00771 00772 00773 00774 // Auxiliars of the delete_node dynamic orthogonal algorithm. 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 // Auxiliars of the delete_edge dynamic orthogonal algorithm. 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 void 00836 delete_all_dummy_edges_around_node 00837 ( 00838 gdtnode n 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; // see below.. 00893 00894 00895 // --------------------------------------------------------------- 00896 // compute the position of the bottom-left corner of each vertex 00897 // "v" in order to make free space for expanding "v" into a 00898 // super-gdtnode with dimensions (w[v] x h[v]). 00899 // All the edges will leave the corresponding side at the center. 00900 // Also, for each gdtnode "v", the structure pie[v] stores the new 00901 // relative positions of the edges incident with "v" in the 00902 // four directions (north, south, east, west). The relative 00903 // positions are expressed with respect to the bottom-left 00904 // corner of the new super-gdtnode. 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; // see below.. 00915 00916 00917 // --------------------------------------------------------------- 00918 // compute the position of the bottom-left corner of each vertex 00919 // "v" in order to make free space for expanding "v" into a 00920 // super-gdtnode with dimensions (w[v] x h[v]). 00921 // Also, for each gdtnode "v", the structure pie[v] stores the new 00922 // relative positions of the edges incident with "v" in the 00923 // four directions (north, south, east, west). The relative 00924 // positions are expressed with respect to the bottom-left 00925 // corner of the new super-gdtnode. 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; // see below.. 00939 00940 00941 // --------------------------------------------------------------- 00942 // compute the position of the bottom-left corner of each vertex 00943 // "v" according to the constraints expressed by "pos_edge_on_node" 00944 // (see method compute_dime_with_expanded_nodes). 00945 // Also, for each gdtnode "v", the structure pie[v] stores the new 00946 // relative positions of the edges incident with "v" in the 00947 // four directions (north, south, east, west). The relative 00948 // positions are expressed with respect to the bottom-left 00949 // corner of the new super-gdtnode. 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 ); // see below.. 00963 00964 00965 // --------------------------------------------------------------- 00966 // expand nodes into super-nodes, according to the dimensions 00967 // "w,h" of each gdtnode, and by using the informations stored in 00968 // the "pie" data structure, to correctly calculate the 00969 // positions of the edges incident with the new super-nodes. 00970 // The mapping "super-gdtnode" stores which is the representative 00971 // gdtnode (super-gdtnode) in the current graph that corresponds to 00972 // each gdtnode of dopug. 00973 // PRECONDITIONS : the current graph is a copy of dopug, and it 00974 // has been applied the method 00975 // "position_bottom_left_corners_and_incid_edges". 00976 // --------------------------------------------------------------- 00977 00978 00979 // ### Begin import from GDT fork of W. Didimo on June, 18 2004 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 ); // see below.. 00991 00992 00993 // --------------------------------------------------------------- 00994 // expand nodes into super-nodes, according to the dimensions 00995 // "w,h" of each node, and by using the informations stored in 00996 // the "pie" data structure, to correctly calculate the 00997 // positions of the edges incident with the new super-nodes. 00998 // The mapping "super-node" stores which is the representative 00999 // node (super-node) in the current graph that corresponds to 01000 // each node of dopug. 01001 // Mapping "is_removable" informs if a dummy node can be removed before compaction. 01002 // Mapping "removable_edge" informs if an edge can have zero length after compaction. 01003 // PRECONDITIONS : the current graph is a copy of dopug, and it 01004 // has been applied the method 01005 // "position_bottom_left_corners_and_incid_edges". 01006 // --------------------------------------------------------------- 01007 // ### End import 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 ); // see below.. 01020 01021 01022 // ----------------------------------------------------------------- 01023 // expand the gdtnode "v" into a super-gdtnode of width "width" and 01024 // height "height". The super-gdtnode is constructed as follows: 01025 // 01026 // 1 - the bottom-left gdtnode of the super-gdtnode is "v", 01027 // and ("bl_x","bl_y") specify the new coordinates of 01028 // such a gdtnode. 01029 // 01030 // 2 - the two vertical sides of the super nodes are 01031 // composed by two equal vertical chains, each one 01032 // containing a number of nodes equal to ("height"+1). 01033 // Two consecutive nodes of any chain have distance one. 01034 // 01035 // 3 - the two horizontal sides of the super nodes are 01036 // composed by two equal horizontal chains, each one 01037 // containing a number of nodes equal to ("width"+1). 01038 // Two consecutive nodes of any chain have a distance one. 01039 // 01040 // 4 - the edges previously connected to "v" are attached to 01041 // the nodes of the super-gdtnode according to the relative 01042 // position specified by pie_v. 01043 // 01044 // All the nodes of the super-gdtnode are returned in the list "N". 01045 // WARNINGS: "N" is initialized to empty in the method. 01046 // ----------------------------------------------------------------- 01047 01048 // ### Begin import from GDT fork of W. Didimo on June, 18 2004 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 ); // see below.. 01061 01062 01063 // ----------------------------------------------------------------- 01064 // expand the node "v" into a super-node of width "width" and 01065 // height "height". The super-node is constructed as follows: 01066 // 01067 // 1 - the bottom-left node of the super-node is "v", 01068 // and ("bl_x","bl_y") specify the new coordinates of 01069 // such a node. 01070 // 01071 // 2 - the two vertical sides of the super nodes are 01072 // composed by two equal vertical chains, each one 01073 // containing a number of nodes equal to ("height"+1). 01074 // Two consecutive nodes of any chain have distance one. 01075 // 01076 // 3 - the two horizontal sides of the super nodes are 01077 // composed by two equal horizontal chains, each one 01078 // containing a number of nodes equal to ("width"+1). 01079 // Two consecutive nodes of any chain have a distance one. 01080 // 01081 // 4 - the edges previously connected to "v" are attached to 01082 // the nodes of the super-node according to the relative 01083 // position specified by pie_v. 01084 // 01085 // 5 - Mapping "is_removable" inform if a dummy node in the super-node 01086 // can be removed before compaction. 01087 // Mapping "removable_edge" informs if an edge can have zero 01088 // length after compaction. 01089 // 01090 // All the nodes of the super-node are returned in the list "N". 01091 // WARNINGS: "N" is initialized to empty in the method. 01092 // ----------------------------------------------------------------- 01093 // ### End import 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 ); // see below.. 01104 01105 // ------------------------------------------------------------------ 01106 // expand the gdtnode "v" into a chain in the specified direction "dir", 01107 // where "dir" should be in the set {north, south, east, west}. 01108 // The chain has a number of edges equal to "length", and a number of 01109 // nodes equal to "length"+1 ("v" included). 01110 // Two consecutive nodes of the chain have distance one. 01111 // "N" is the ordered list of the nodes added (not including "v"). 01112 // WARNINGS: "N" is not initialized to empty in the method. 01113 // ------------------------------------------------------------------ 01114 01115 01116 01117 gdtedge change_node_of_edge_with_node 01118 ( 01119 gdtnode v1, 01120 gdtedge e1, 01121 gdtnode v2 01122 ); // see below.. 01123 01124 // ------------------------------------------------------------------- 01125 // Suppose that "e1=(v1,w1)". This method creates a new gdtedge 01126 // "e = (v2,w1)", that has the same identifier, direction, constraints 01127 // and markers as "e1". 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 ); // see below.. 01139 01140 // -------------------------------------------------------------------- 01141 // uncompress all the edges as much as possible. This means that, for 01142 // each side of a super-gdtnode an evaluation of the free space is done, 01143 // and the compressed-edges are uncompressed until is not more possible 01144 // attaching an gdtedge to a vertex of the super-gdtnode. 01145 // -------------------------------------------------------------------- 01146 01147 // ### Begin import from GDT fork of W. Didimo on June, 18 2004 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 ); // see below.. 01158 // ### End import 01159 01160 // -------------------------------------------------------------------- 01161 // uncompress all the edges according to constraints expressed by 01162 // "pos_edge_on_node" parameter. 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 ); // see below.. 01173 01174 // -------------------------------------------------------------------- 01175 // expand the horizontal(vertical) chain that has "v" as the most left 01176 // (bottom) gdtnode, and length "length", into a box with height (width) 0. 01177 // The two edges that have zero length are appended to the list 01178 // "zero_edges". Return the nodes added. 01179 // PRECONDITIONS: the gdtnode "v" is the start gdtnode of a chain 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; // return the corners of all super-nodes. 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 ); // to comment 01200 01201 01202 void construct_dime_orth_plan_undi_graph // called by each constructor from the undi_graph class 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 // called by each constructor from the plan_undi_graph class 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 // called by each constructor from the 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 CATEGORY constructors_destructors 01232 Constructors and Operators. 01233 */ 01234 01239 dime_orth_plan_undi_graph 01240 ( 01241 ); 01242 01243 /* 01244 Destructor. 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 CATEGORY operators 01361 Operators. 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 CATEGORY access 01406 Access operations. 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 // Added by F. M. 01595 // as utility in expanding the Dynamic Drawing to >4plan problems 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 // TO COMMENT!!!!! (COMMENTS WILL BE MADE BY ANTONIO LEONFORTE AND SANDRA FOLLARO) 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 CATEGORY update 02085 Update operations. 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 /* CATEGORY global_modifiers 02285 Global Modifiers 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 // please move this in a more appropriate place! (pizzo) 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 CATEGORY dynamic_methods 02437 Dynamic methods. 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 // The following methods are used by draw_undi_graph class, but it 02476 // should be not public here. Future best solution is to move it into the 02477 // draw_undi_graph files. 02478 // PLEASE, DO NOT LIST THIS METHOD IN THE PUBLIC METHODS !!! 02479 // -------------------------------------------------------------------------- 02480 02481 void 02482 remove_all_dummy_nodes_and_edges 02483 ( 02484 ); // remove all dummy nodes and edges 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 CATEGORY io_operations 02562 Input / output operations. 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
1.5.3