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