Graph Drawing Toolkit
00001 /******************************************************************************* 00002 + 00003 + rm3_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 00017 #ifndef RM3_UNDI_GRAPH_H 00018 #define RM3_UNDI_GRAPH_H 00019 00020 00021 #include <fstream> 00022 #include <limits.h> 00023 #include <GDT/rm3_global.h> 00024 #include <GDT/rm3_constraints.h> 00025 #include <GDT/gdtlist.h> 00026 //#include <GDT/gdt_graph_array.h> 00027 #include <GDT/gdtstack.h> 00028 #include <string> 00029 00030 00031 //#define LABEL 00032 //#define OUTPUT 00033 //#define COUNTER 00034 00035 //----------------------------------------------------------------------------- 00036 // undi_graph: base class for all directed and undirected embedded graphs 00037 // 00038 // W.Didimo e A.Leonforte (1996) 00039 //----------------------------------------------------------------------------- 00040 00041 class SPQR_tree; // forward declarations 00042 class plan_undi_graph; // forward declarations 00043 00044 00045 #define AUTO_ID -1 // AUTO identifier 00046 #define NULL_ID -1 // NULL identifier 00047 00048 extern const gdtnode NULL_NODE; // NULL gdtnode 00049 extern const gdtedge NULL_EDGE; // NULL gdtedge 00050 extern const constraint NULL_CONSTRAINT; // NULL constraint 00051 00052 00063 typedef enum 00064 { 00065 OUTGOING, 00066 INCOMING 00067 } 00068 visit_direction_type; 00069 00086 typedef enum 00087 { 00088 BY_NODES, 00089 BY_EDGES, 00090 BY_FACES, 00091 //Debug 00092 FOR_DEBUG, 00093 // 00094 BY_PATHS, 00095 COMPLETE 00096 } 00097 print_mode; 00098 00099 00106 typedef enum 00107 { 00108 MIN, 00109 MAX 00110 } 00111 compare_option; 00112 00113 00114 00124 typedef enum 00125 { 00126 TREE_EDGE, 00127 BACK_EDGE, 00128 FORW_EDGE 00129 } 00130 DFS_edge_type; 00131 00132 00133 00143 typedef enum 00144 { 00145 DO_NOT_PRESERVE_EMBEDDING, 00146 PRESERVE_EMBEDDING 00147 } 00148 planarize_options; 00149 00150 00151 00152 00153 // ---------------------------------------- 00154 // Global classes for the planarity testing 00155 // ---------------------------------------- 00156 00157 00158 00164 class dfs_node_info { 00165 public: 00166 static int counter; 00168 int DFI; 00170 int lowpoint; 00172 gdtedge parent; 00177 dfs_node_info(); 00181 ~dfs_node_info(); 00182 }; 00183 00184 00185 00192 class dfs_edge_info { 00193 public: 00194 static int counter; 00195 int index; 00196 DFS_edge_type type; 00197 dfs_edge_info(); 00198 ~dfs_edge_info(); 00199 00200 }; 00201 00202 00207 class bm_node_info { 00208 public: 00209 00210 static bm_node_info* my_new_bm_node_info(); 00211 //static int counter; 00212 //int DFI; // Depth First Index (root vertex is 0) 00213 int lowpoint; // DFI of the node that is the lowpoint of current node 00214 gdtedge parent; // edge conneting to parent node; 00215 gdt::gdtlist<gdtnode> children; // children in the DFS_TREE 00216 gdt::gdtlist<gdtnode> in_back_edges; // entering back_edges 00217 00218 int first_back_edge_dfi; 00219 bool ordered_first_black; 00220 00221 gdt::gdtlist<gdtnode> children_ordered; // children in the DFS tree ordered by lowpoint values 00222 gdt::list_item position_in_parent_list; // position in the children_ordered list of the parent node 00223 00224 bm_node_info(); 00225 ~bm_node_info(); 00226 }; 00227 00228 00234 class bm_edge_info { 00235 public: 00236 static int counter; 00237 static bm_edge_info* my_new_bm_edge_info(); 00238 DFS_edge_type type; 00239 bool inserted; 00240 00241 bm_edge_info(); 00242 ~bm_edge_info(); 00243 }; 00244 00245 00246 00247 00248 00249 00250 00251 00252 /* 00253 Global class containing information to execute 00254 the Boyer & Myrvold's algorithm. 00255 Each bic_obj may represent a node (node bic_obj) or an edge (edge bic_obj) 00256 in a biconnected component. 00257 */ 00258 00259 00260 00261 class bic_obj { 00262 00263 00264 protected: 00265 #ifdef OUTPUT 00266 std::string label; // the node id in case of a node bic_obj, the catenation of node ids (with a comma in the middle) otherwise 00267 #endif 00268 bool is_node; // true if this bic_obj represents a node, false if it represents an edge 00269 bic_obj* twin_link; // points to related bic_obj in the embedding (see the Boyer and Myrvold paper) 00270 bic_obj* black; // a pointer of the circular adjacency list (see the paper again) 00271 bic_obj* white; // the other pointer of the circular adjacency list 00272 00273 gdtnode graph_node; // if this is a node bic_obj, the this field contains a pointer to the node of the original graph (undi_graph) 00274 gdtedge graph_edge; /* if this is an edge bic_obj, and is not a ficticious edges, pointer 00275 to the edge of the original graph (undi_graph) */ 00276 00277 00278 int marked; /* 0=not marked; 1=marked; 2=marked twice (only edge bic_obj can be marked twice, if they are 00279 in an elementary bicomp) */ 00280 00281 00282 00283 // PROTECTED METHODS 00284 00285 00286 00287 00288 00289 00290 /* 00291 METHOD is_active (and is_active_verbose) 00292 Test if a node is active respect to node target. 00293 A node is active if it has a back edge over target, or it has a child bicomp which has a back edge over target. 00294 <UL> 00295 <LI>target: target node 00296 <LI>node_vector: pre-processing informations on graph nodes 00297 </UL> 00298 */ 00299 00300 bool 00301 is_active 00302 ( 00303 int target, 00304 bm_node_info node_vector[] 00305 //int lowpoint[], 00306 //int first_back_edge_dfi[], 00307 //list<node> children_ordered[] 00308 ); 00309 00310 00311 /* 00312 METHOD is_root_externally_active 00313 Test if a root node is esternally active. 00314 A root is externally active if the correspondig node in its parent bicomp has a back-edge over target, or 00315 it has a child node different from child which lowpoint is less than target. 00316 Node child id the child node in the current bicomp. 00317 This method must be applied to root bic_obj only. 00318 <UL> 00319 <LI>target: target node 00320 <LI>child: first child node in this bicomp 00321 <LI>node_vector: pre-processing informations on graph nodes 00322 </UL> 00323 */ 00324 bool 00325 is_root_externally_active 00326 ( 00327 int target, 00328 gdtnode child, 00329 bm_node_info node_vector[] 00330 //int lowpoint[], 00331 //int first_back_edge_dfi[], 00332 //list<node> children_ordered[] 00333 ); 00334 00335 bool 00336 is_internally_active_node 00337 ( 00338 int target, 00339 bm_node_info node_vector[] 00340 //int first_back_edge_dfi[], 00341 //list<node> children_ordered[] 00342 ); 00343 00345 // public 00347 00348 public: 00349 00350 static int counter; 00351 static bic_obj* my_new_bic_obj(bic_obj*& bic_obj_actual_pointer); 00352 00353 static bic_obj* my_new_bic_obj(gdtedge e,bic_obj*& bic_obj_actual_pointer); 00354 00355 friend class undi_graph; 00356 friend class struct_gdtnode; 00357 friend class bic_obj_node; 00358 00359 00360 /* 00361 CATEGORYremoved constructors_destructors 00362 Constructors and destructors 00363 */ 00364 00365 /* 00366 Bic_obj empty constructor. 00367 This constructor creates bic_obj which may represent ficticious back_edges 00368 */ 00369 bic_obj(); 00370 00371 /* 00372 Bic_obj destructor 00373 */ 00374 00375 ~bic_obj(); 00376 00377 00378 /* 00379 Node bic_obj constructor 00380 */ 00381 00382 bic_obj(gdtnode n); 00383 00384 00385 /* 00386 Edge bic_obj constructor 00387 */ 00388 00389 bic_obj(gdtedge e); 00390 00391 00392 /* 00393 CATEGORY check 00394 Methods to check bicomp structure 00395 */ 00396 00397 00398 00399 /*METHOD check_node 00400 Check the circular adjacency list of the node. Return true if it is correct. 00401 00402 00403 bool 00404 check_node(); 00405 */ 00406 00407 00408 /* 00409 CATEGORY access 00410 Access operations 00411 */ 00412 00413 00414 /*METHOD read_node_embedding 00415 Read the embedding from the bicomp structure and copy it to graph ug 00416 Return true if operations end correctly. 00417 */ 00418 00419 bool 00420 read_node_embedding 00421 ( 00422 undi_graph& ug 00423 ); 00424 00425 00426 00427 /* 00428 METHOD get_label 00429 Return the label of the bic_obj. 00430 */ 00431 00432 std::string 00433 get_label 00434 ( 00435 ); 00436 00437 }; 00438 00439 class 00440 bic_obj_node: public bic_obj 00441 { 00442 protected: 00443 00444 bic_obj_node* twin_link; 00445 gdt::gdtlist <bic_obj_node*> active_bicomp; 00446 gdt::gdtlist <bic_obj_node*> not_active_bicomp; 00447 gdtnode first_child; 00448 int active_passages; 00449 bool actual_previous_connector; 00450 int DFI; 00451 bool can_be_flipped; 00452 bool active_walk_up; 00453 00454 public: 00455 bic_obj_node(); 00456 00457 bic_obj_node(gdtnode n); 00458 static bic_obj_node* my_new_bic_obj(gdtnode n,bic_obj_node*& bic_obj_node_actual_pointer); 00459 00460 friend class undi_graph; 00461 00462 00463 protected: 00464 00465 /* 00466 METHOD next_node 00467 Return the next node on the external side of the bicomp. 00468 It must be applied to a node bic_obj. 00469 <UL> 00470 <LI> black = if true(false), return the next node starting from the black(white) pointer of this node 00471 </UL> 00472 */ 00473 00474 00475 bic_obj_node* 00476 next_node 00477 ( 00478 bool black 00479 ); 00480 00481 00482 00483 /* 00484 METHOD walk_up 00485 Realize the walk_up phase.It must be applied to node bic_obj which are the start nodes of back edges. 00486 This method return true if a back_edge between target and this node can be added to the structure without violate planarity. 00487 <UL> 00488 <LI> target: graph node which is target of back_edge. 00489 <LI> node_vector: pre-processing informations 00490 <LI> secondary: list of the root bic_obj corresponding to target node reached by all walk_up phases on the same target node 00491 <LI> walk_up_stack: this stack contains all the bic_obj visited in walk_up phase 00492 </UL> 00493 */ 00494 bool 00495 walk_up 00496 ( 00497 int target, 00498 //int lowpoint[], 00499 //int first_back_edge_dfi[], 00500 //list<node> children_ordered[], 00501 bm_node_info node_vector[], 00502 gdt::gdtlist<bic_obj_node*>& secondary, 00503 undi_graph& ug 00504 //stack<bic_obj*>& embedding_stack 00505 ); 00506 00507 00508 /* 00509 METHOD walk_down (and walk_down_verbose) 00510 Realize the walk_down phase. It inserts all back edges examinated in the previous walk_up_phases updating the bicomp sructure. 00511 Return true if the structure was updated correctly, otherwise return false. 00512 PRECONDITIONS: this method must be activated only after the correct executions af all walk_up phases. 00513 <UL> 00514 <LI>node_vector: pre-processing informations on graph nodes 00515 <LI>edge_vector: pre-processing informations on graph edges 00516 <LI>secondary: list of root bic_obj which are target nodes of back edges. This list is calculated during the walk_up phases 00517 <LI>ug: original graph (undi_graph) 00518 <LI>embedding_stack: this stack will contain a pointer for each edge bic_obj inserted (it needs to read embedding) 00519 <LI>edges_inserted: for each edge, it became true when it is inserted in bicomp structure 00520 </UL> 00521 */ 00522 00523 bool 00524 walk_down 00525 ( 00526 bm_node_info node_vector[], 00527 //list_item position_in_parent_list[], 00528 //list<node> childen_orderd[], 00529 gdt::gdtlist<bic_obj_node*>& secondary, 00530 undi_graph* ug, 00531 //stack<bic_obj*>& embedding_stack, 00532 //edge_map<bool>& edge_to_be_inserted 00533 bool edge_to_be_inserted[], 00534 int flip[], 00535 bic_obj*& bic_obj_actual_pointer 00536 ); 00537 00538 /* 00539 METHOD extract_embedding 00540 This method visit the final bicomp structure at the end of all walk_up and walk_down phases, and for each node orders its 00541 circular adjacency list. 00542 <UL> 00543 <LI> embedding_stack = stack of pointers to edge_bic_obj inserted during walk_down phases. 00544 <LI> node_vector: pre-processing informations on graph nodes 00545 <LI> edge_vector: pre-processing informations on graph edges 00546 </UL> 00547 */ 00548 bool 00549 extract_embedding 00550 ( 00551 gdt::gdtstack<bic_obj*>& embedding_stack, 00552 //edge_map<bm_edge_info*>& edge_vector, 00553 undi_graph& ug 00554 ); 00555 00556 00557 bool 00558 embedding_reporting 00559 ( 00560 bm_node_info node_vector[], 00561 //bool ordered_first_black[], 00562 //list<node> children[], 00563 //edge parent[], 00564 undi_graph& ug, 00565 int flip[], 00566 bic_obj_node* IMM[] 00567 ); 00568 00569 public: 00570 /* 00571 METHOD check_bicomp 00572 Visit the external side of a bicomp. Return true if the visit is correct. 00573 */ 00574 00575 bool 00576 check_bicomp(); 00577 00578 00579 00580 }; // End class bic_obj_node 00581 00582 00583 00584 // ------------------------------- 00585 // Classes for nodes and edges 00586 // internal structures. 00587 // ------------------------------- 00588 00595 class struct_gdtnode { 00596 friend class undi_graph; 00597 friend class bic_obj; 00598 friend class bic_obj_node; 00599 //Modified by A.M. 10/2002 00600 //gdtnode lnode; 00601 gdt::list_item pos_in_nodes; 00602 00603 int plan_id; // node-identifier used by the planarity test P.F. Cortese 10/11/2003 00604 public: 00605 struct_gdtnode() {} 00606 00607 int get_plan_id() {return plan_id;} 00608 //Removed by A.M. 10/2002 00609 /* 00610 struct_gdtnode(gdtnode _lnode) { 00611 lnode = _lnode; 00612 } 00613 */ 00614 }; 00615 00616 00621 class struct_gdtedge { 00622 friend class undi_graph; 00623 friend class bic_obj; 00624 friend class bic_obj_node; 00625 00626 //Modified by A.M. 10/2002 00627 //gdtedge ledge; 00628 gdt::list_item pos_in_edges; 00629 int plan_id; // edge-identifier used by the planarity test P.F. Cortese 10/11/2003 00630 00631 public: 00632 struct_gdtedge() {} 00633 //Removed by A.M. 10/2002 00634 /* 00635 struct_gdtedge(gdtedge _ledge) { 00636 ledge = _ledge; 00637 } 00638 */ 00639 00640 }; 00641 00642 00654 class GDT_NONSTANDARD_DECL 00655 struct_undi_node_info 00656 { 00657 friend class undi_graph; 00658 friend class struct_constraint; 00659 friend class bic_obj; 00660 friend class bic_obj_node; 00661 // 00662 private: 00663 int id; // gdtnode-identifier 00664 gdt::gdtlist<gdtedge> in_edges; // in_edges list of gdtnode 00665 gdt::gdtlist<gdtedge> out_edges; // out_edges list of gdtnode 00666 gdt::gdtlist<gdtedge> adj_edges; // adj_edges list of gdtnode 00667 // 00668 bool in_edges_are_ordered; // true when in_edges list is ordered 00669 bool out_edges_are_ordered; // true when out_edges list is ordered 00670 // 00671 gdt::gdtlist<marker_type> markers; // list of all markers on gdtnode 00672 gdt::gdtlist<constraint> constraints; // list of all constraints involving gdtnode 00673 //Removed by A.M. 18/10/2002 00674 //gdtnode gnode; 00675 // 00676 public: 00677 /* 00678 CATEGORYremoved constructors_destructors 00679 Constructors and destructors 00680 */ 00681 00682 /* 00683 METHODremoved struct_undi_node_info 00684 Struct-gdtnode constructor. 00685 */ 00686 00687 struct_undi_node_info 00688 ( 00689 ); 00690 }; 00691 00692 00693 00708 class GDT_NONSTANDARD_DECL 00709 struct_undi_edge_info 00710 { 00711 friend class undi_graph; 00712 friend class struct_constraint; 00713 friend class bic_obj; 00714 friend class bic_obj_node; 00715 // 00716 private: 00717 int id; // gdtedge-indentifier 00718 gdtnode source; // source extremal gdtnode (dummy reference) of gdtedge 00719 gdtnode target; // terget extermal gdtnode (dummy reference) of gdtedge 00720 gdtnode start; // start gdtnode if gdtedge is directed (NULL_NODE if gdtedge is undirected) 00721 gdt::list_item pos_into_in_edges; // positions of gdtedge into in_edges list 00722 gdt::list_item pos_into_out_edges; // position of gdtedge into out_edges list 00723 gdt::list_item pos_into_source_adj_edges; // position of gdtedge into source's adjacent gdtedge list 00724 gdt::list_item pos_into_target_adj_edges; // position of gdtedge into target's adjacent gdtedge list 00725 // 00726 gdt::gdtlist<marker_type> markers; // list of all markers on gdtedge 00727 gdt::gdtlist<constraint> constraints; // list of all constraints involving gdtedge 00728 00729 //Removed by A.M. 18/10/2002 00730 //gdtedge gedge; 00731 // 00732 public: 00733 00734 /* 00735 CATEGORYremoved constructors_destructors 00736 Constructors and destructors 00737 */ 00738 00739 /* 00740 METHODremoved struct_undi_edge_info 00741 Struct-gdtedge constructor. 00742 */ 00743 00744 struct_undi_edge_info 00745 ( 00746 ); 00747 }; 00748 00749 00754 typedef struct_gdtnode *gdtnode; 00755 00760 typedef struct_gdtedge *gdtedge; 00761 00762 // ------------------------------------------------------------------------------------------------ 00763 // UNDI_GRAPH 00764 // ------------------------------------------------------------------------------------------------ 00765 00792 class GDT_NONSTANDARD_DECL 00793 undi_graph 00794 { 00795 friend class SPQR_tree; 00796 friend class struct_constraint; 00797 friend class bic_obj; 00798 friend class bic_obj_node; 00799 // 00800 private: 00801 00802 // ----------------- 00803 // private variables 00804 // ----------------- 00805 00806 //Added by A.M. 2/2002 00807 gdt::gdtlist<gdtnode> *nodes; //Node list 00808 gdt::gdtlist<gdtedge> *edges; //Edge list 00809 // 00810 00811 // commented out by pizzo 00812 gdt::gdtnode_map<struct_undi_node_info>* node_info; // correspondence gdtnode --> undi-gdtnode structure 00813 gdt::gdtedge_map<struct_undi_edge_info>* edge_info; // correspondence gdtedge --> undi-gdtedge structure 00814 00815 gdt::gdtlist<constraint>* constraints; // list of constraints for graph 00816 00817 gdt::gdtmap<int,gdtnode>* node_with_id; // correspondence gdtnode-identifier --> gdtnode 00818 gdt::gdtmap<int,gdtedge>* edge_with_id; // correspondence gdtedge-identifier --> gdtedge 00819 gdt::gdtmap<int,constraint>* constraint_with_id; // correspondence constraint-identifier --> constraint 00820 00821 int max_node_id; // maximum value of a gdtnode-identifier 00822 int max_edge_id; // maximum value of an gdtedge-identifier 00823 int max_constraint_id; // maximum value of a constraint-identifier 00824 int max_edge_plan_id; // maximun value of a gdtedge-plan-identifier: this value is used by the planarity testing algorithm 00825 bool keep_ordering_of_directed_edges; // if true, also the embedding of the directed edges is kept 00826 // consistently with the embedding of all underlying edges. 00827 // TRUE is default. You can disable this flag when you do not 00828 // need of knowing the exactly embedding of the directed edges, 00829 // and you want to save computation time. 00830 00831 00832 // --------------- 00833 // private methods 00834 // --------------- 00835 00836 void local_new(); // create a new set of pointers for the not-inherited class-part 00837 void local_del(); // delete all the not-inherited class-part 00838 void local_renew(); // utility function : just local_del(), then local_new() 00839 void local_init(); // init the not-inherited class-part 00840 00841 void local_set // set all private variables 00842 ( 00843 gdt::gdtlist<gdtnode>*, 00844 gdt::gdtlist<gdtedge>*, 00845 //graph*, 00846 gdt::gdtnode_map<struct_undi_node_info>*, 00847 gdt::gdtedge_map<struct_undi_edge_info>*, 00848 gdt::gdtlist<constraint>*, 00849 gdt::gdtmap<int,gdtnode>*, 00850 gdt::gdtmap<int,gdtedge>*, 00851 gdt::gdtmap<int,constraint>*, 00852 int, 00853 int, 00854 int, 00855 bool 00856 ); 00857 00858 void order_in_edges (gdtnode); // make ordered the in-edges adjacent list of gdtnode 00859 void order_out_edges (gdtnode); // make ordered the out-edges adjacent list of gdtnode 00860 void mark_in_edges_as_not_ordered (gdtnode); // mark the in_edges adjacent list of gdtnode as not marked 00861 void mark_out_edges_as_not_ordered (gdtnode); // mark the out_edges adjacent list of gdtnode as not marked 00862 00863 void remove_from_in_edges (gdtedge); // remove the gdtedge from the in_edge adjacent lists 00864 void remove_from_out_edges (gdtedge); // remove the gdtedge from the out_edge adjacent lists 00865 void remove_from_adj_edges (gdtedge); // remove the gdtedge from all adjacent lists 00866 00867 bool make_embedding_planar0 (); // make the embedding planar if there exists one 00868 00869 gdt::gdtlist<constraint>* get_constraints(); // return a pointer to list of all constraints of graph 00870 00871 gdt::gdtlist<constraint>& all_constraints(gdtedge); // return a reference to the list of all constraints involving gdtedge 00872 gdt::gdtlist<constraint>& all_constraints(gdtnode); // return a reference to the list of all constraints involving gdtnode 00873 00874 bool planarize_kernel 00875 ( 00876 gdt::gdtlist<gdtedge>&, 00877 gdt::gdtlist<gdtedge>&, 00878 planarize_options po = DO_NOT_PRESERVE_EMBEDDING 00879 ); // see below... 00880 00881 // --------------------------------------------------------------------- 00882 // method called by undi_graph::planarize() 00883 // planarize the graph with given planarize_options 00884 // without crossing edges in first given gdt::gdtlist<gdtedge> 00885 // and removing edges in the second gdt::gdtlist<gdtedge> after 00886 // the maximal planar graph is found. 00887 // Return false when no solution is found due to constraints. 00888 // --------------------------------------------------------------------- 00889 00890 00891 // these 2 methods should be private in the final version 00892 public: 00893 bool make_embedding_planar_boyer (); // make the embedding planar if there exists one 00894 00895 private: 00896 // ************************************************************************************************* 00897 // -------------------------------------------------------------------- 00898 // THIS METHODS ARE NEEDED FOR IMPLEMENTATING THE ST-NUMBERING METHOD. 00899 // MORE DETAILS ARE PROVIDED IN THE SOURCE FILES. 00900 // -------------------------------------------------------------------- 00901 00902 00903 gdt::gdtlist<gdtedge> find_path 00904 ( 00905 gdtnode v, 00906 bool& exist_path1, 00907 bool& exist_path2, 00908 bool& exist_path3, 00909 gdt::gdtnode_array<gdtedge>& father, 00910 gdt::gdtnode_array<int>& num_visit, 00911 gdt::gdtnode_array<gdtnode>& lowpt1, 00912 gdt::gdtnode_array<bool>& marked 00913 ); 00914 00915 // --------------------------------------------------------------------- 00916 // search a specified type path (v,v1,...,vn,w) in graph, after 00917 // a DFS-visit of it has been made. Nodes v,v1,...,vn are not marked 00918 // and w is marked. 00919 // --------------------------------------------------------------------- 00920 00921 00922 DFS_edge_type DFS_edge 00923 ( 00924 gdtedge e, 00925 gdtnode v, 00926 gdt::gdtnode_array<gdtedge>& father, 00927 gdt::gdtnode_array<int>& num_visit 00928 ) const; 00929 00930 // ------------------------------------------------------------------------ 00931 // return the type of gdtedge in a specified DFS order. 00932 // (e,v) = gdtedge to testing, starting from gdtnode v. 00933 // father[w] = gdtedge father of gdtnode w in the DFS. 00934 // num_visit[w] = number of visit for gdtnode w in the DFS 00935 // (i.e. num_visit[v] < num_visit[w] if v is visited before than w). 00936 // NOTE: it's necessary to specify the num_visit for to have 00937 // a constant time cost. 00938 // ------------------------------------------------------------------------ 00939 00940 // ************************************************************************************************* 00941 00942 00943 00944 protected: 00945 00946 void set_source (gdtedge, gdtnode); // set the source of the gdtedge with gdtnode 00947 00948 // ------------------------------------------------------------ 00949 // protected methods for an intelligent updating of constraints 00950 // ------------------------------------------------------------ 00951 00952 void update_constraints_after_del_edge (gdtedge e); // update constraints involving gdtedge e, when a delete gdtedge operation on e is applied 00953 void update_constraints_after_del_node (gdtnode v); // update constraints involving gdtnode v, when a delete gdtnode operation on v is applied 00954 00955 void update_constraints_after_split_edge (gdtedge e, gdtedge e1, gdtedge e2); // update constraints involving gdtedge e, when a split operation e --> e2,e2 is applied 00956 void update_constraints_after_split_node (gdtnode v, gdtnode v1, gdtnode v2); // update constraints involving gdtnode v, when a split operation v --> v1,v2 is applied 00957 00958 void update_constraints_after_merge_edges (gdtedge e1, gdtedge e2, gdtedge e); // update constraints involving gdtedge e1 and gdtedge e2, when a merge operation e1,e2 --> e is applied 00959 void update_constraints_after_merge_nodes (gdtnode v1, gdtnode v2, gdtnode v); // update constraints involving gdtnode v1 and gdtnode v2, when a merge operation v1,v2 --> v is applied 00960 00961 void update_constraints_after_edge_translation 00962 ( 00963 gdtedge e , 00964 gdtnode ve1, 00965 gdtnode ve2, 00966 gdtedge d , 00967 gdtnode vd1, 00968 gdtnode vd2 00969 ); // modify all constraints involving gdtedge e, replacing this gdtedge with d and, if it is needed, update also the extremal vertices 00970 00971 00972 void update_constraints_on_path_replacing_edge 00973 ( 00974 gdtedge e, 00975 undi_graph& ug, 00976 gdt::gdtlist<gdtedge> path 00977 ); // generate new constraints for path, which replaces gdtedge e , based on constraints involving e 00978 // NOTICE: - path is a sequence of edges of this graph; 00979 // - e is an gdtedge of ug (not necessarily this graph) 00980 // - the extremal nodes of e must have the same id than the extremal gdtnode of path 00981 00982 00983 void copy_constraints_from_subgraph_of_undi_graph 00984 ( 00985 gdt::gdtlist<gdtedge>& sub, 00986 undi_graph& ug 00987 ); // copy on this, as much as possible, all constraints of ug involving edges or nodes of sub. 00988 // PRCONDITIONS: sub is a set of edges of ug 00989 00990 gdt::gdtlist<gdtedge> path_corresponding_to_edge (gdtedge, undi_graph&) const; // finds a path in *this such that: 00991 // 1) two edges of path are adjacent via a vertex marked "RM3_CROSS_ON_REAL_EDGE" 00992 // 2) one of the edges of path has edge_id equal to that of given gdtedge of undi_graph 00993 00994 00995 00996 00997 int count_not_dummy_nodes () const; // return the number of nodes that are not dummy 00998 00999 01000 public: 01001 /* 01002 CATEGORY constructors_destructors 01003 Constructors and destructors. 01004 */ 01005 01012 undi_graph 01013 ( 01014 ); 01015 01016 01017 01018 01024 ~undi_graph 01025 ( 01026 ); 01027 01028 01029 01039 undi_graph 01040 ( 01041 const undi_graph& ug 01042 ); 01043 01044 01045 01046 /* 01047 CATEGORY operators 01048 Operators. 01049 */ 01050 01051 01052 01059 undi_graph& 01060 operator = 01061 ( 01062 const undi_graph& ug 01063 ); 01064 01065 /* 01066 CATEGORY access 01067 Access operations. 01068 */ 01069 01070 01071 /* (Hidden to public users) 01072 Although this method is public, it should be not used by programmers 01073 Get all private variables. 01074 It stores in the "pi" (i=1,..,10) variables all 01075 the private information of the 01076 undi_graph object. Namely: 01077 <UL> 01078 <LI> p2 = pointer to the "gdtnode --> struct_undi_node" mapping; 01079 <LI> p3 = pointer to the "gdtedge --> struct_undi_edge" mapping; 01080 <LI> p4 = pointer to the list of constraints 01081 <LI> p5 = pointer to "gdtnode-identifier --> gdtnode" mapping; 01082 <LI> p6 = pointer to "gdtedge-identifier --> gdtedge" mapping; 01083 <LI> p7 = pointer to "constraint-identifier --> constraint" mapping; 01084 <LI> p8 = maximum value of a gdtnode-identifier; 01085 <LI> p9 = maximum value of an gdtedge-identifier; 01086 <LI> p10= maximum value of a constraint-identifier. 01087 <LI> p11= flag for keeping updated the embedding of directed edges 01088 </UL> 01089 */ 01090 01091 void 01092 local_get 01093 ( 01094 gdt::gdtlist<gdtnode>*& p, 01095 gdt::gdtlist<gdtedge>*& p0, 01096 gdt::gdtnode_map<struct_undi_node_info>*& p2, 01097 gdt::gdtedge_map<struct_undi_edge_info>*& p3, 01098 gdt::gdtlist<constraint>*& p4, 01099 gdt::gdtmap<int,gdtnode>*& p5, 01100 gdt::gdtmap<int,gdtedge>*& p6, 01101 gdt::gdtmap<int,constraint>*& p7, 01102 int& p8, 01103 int& p9, 01104 int& p10, 01105 bool& p11 01106 ); 01107 01108 01109 01110 01111 /* (Hidden to public users) 01112 Returns a constant reference to this undi_graph. 01113 */ 01114 01115 01116 const undi_graph& 01117 nodes_and_edges 01118 ( 01119 ) const; 01120 01121 01122 01123 01133 int 01134 generate_node_id 01135 ( 01136 ); 01137 01138 01139 01148 int 01149 generate_edge_id 01150 ( 01151 ); 01152 01153 01154 01155 01163 int 01164 generate_constraint_id 01165 ( 01166 ); 01167 01168 01169 01170 01178 int 01179 id 01180 ( 01181 gdtnode v 01182 ) const; 01183 01184 01185 01186 01192 int 01193 id 01194 ( 01195 gdtedge e 01196 ) const; 01197 01198 01199 01200 01206 int 01207 id 01208 ( 01209 constraint c 01210 ) const; 01211 01212 01213 01214 01219 int 01220 get_max_node_id 01221 ( 01222 ) const; 01223 01224 01225 01226 01231 int 01232 get_max_edge_id 01233 ( 01234 ) const; 01235 01236 01237 01238 01243 int 01244 get_max_constraint_id 01245 ( 01246 ) const; 01247 01248 01249 01250 01256 int 01257 degree 01258 ( 01259 gdtnode v 01260 ) const; 01261 01262 01263 01264 01270 int 01271 degree_in 01272 ( 01273 gdtnode v 01274 ) const; 01275 01276 01277 01278 01284 int 01285 degree_out 01286 ( 01287 gdtnode v 01288 ) const; 01289 01290 01291 01292 01297 int 01298 number_of_nodes 01299 ( 01300 ) const; 01301 01302 01303 01304 01309 int 01310 number_of_edges 01311 ( 01312 ) const; 01313 01314 01315 01316 01321 int 01322 number_of_constraints 01323 ( 01324 ) const; 01325 01326 01327 01328 01334 constraint_type 01335 type_of_constraint 01336 ( 01337 constraint c 01338 ) const; 01339 01340 01341 01342 01347 int 01348 max_degree 01349 ( 01350 ) const; 01351 01352 01353 01354 01359 int 01360 min_degree 01361 ( 01362 ) const; 01363 01364 01365 01366 01376 int 01377 number_of_extremals 01378 ( 01379 ) const; 01380 01381 01382 01383 01393 int 01394 connected_components 01395 ( 01396 gdt::gdtnode_array<int>& component 01397 ) const; 01398 01399 01400 01413 int 01414 biconnected_components 01415 ( 01416 gdtnode v, 01417 gdt::gdtnode_map<dfs_node_info*>& vettore_nodi, 01418 gdt::gdtlist<undi_graph*>& bic 01419 //list<node>& cut_nodes 01420 ) const; 01421 01422 01429 bool 01430 node_belongs_to_edge 01431 ( 01432 gdtnode v, 01433 gdtedge e 01434 ) const; 01435 01436 01437 01438 01444 bool 01445 edge_is_directed 01446 ( 01447 gdtedge e 01448 ) const; 01449 01450 01451 01452 01457 bool 01458 all_edges_are_directed 01459 ( 01460 ) const; 01461 01462 01463 01464 01473 bool 01474 is_st_digraph 01475 ( 01476 gdtnode& s, 01477 gdtnode& t 01478 ); 01479 01480 01481 01482 01487 bool 01488 is_connected 01489 ( 01490 ) const; 01491 01492 01493 01494 01499 bool 01500 is_biconnected 01501 ( 01502 ) const; 01503 01504 01505 01506 01512 bool 01513 is_acyclic 01514 ( 01515 ) const; 01516 01517 01518 01526 bool 01527 is_candidate 01528 ( 01529 gdtnode v 01530 ) const; 01531 01532 01533 01534 01540 bool 01541 is_candidate 01542 ( 01543 ) const; 01544 01545 01546 01547 01554 bool 01555 is_source 01556 ( 01557 gdtnode v 01558 ) const; 01559 01560 01561 01562 01568 bool 01569 is_target 01570 ( 01571 gdtnode v 01572 ) const; 01573 01574 01575 01576 /* 01577 Checks if a node is extremal, i.e., if it is a source or a sink node. 01578 @param v a gdtnode 01579 @return true if <I>v</I> is extremal, and false otherwise. 01580 @see number_of_extremals () 01581 @see is_source (gdtnode v) 01582 @see is_target (gdtnode v) 01583 */ 01584 bool 01585 is_extremal 01586 ( 01587 gdtnode v 01588 ) const; 01589 01590 01591 01592 01603 bool 01604 is_extremal 01605 ( 01606 gdtnode v, 01607 gdtedge e 01608 ) const; 01609 01610 01611 01612 01619 bool 01620 is_internal 01621 ( 01622 gdtnode v 01623 ) const; 01624 01625 01626 01627 01637 bool 01638 is_internal 01639 ( 01640 gdtnode v, 01641 gdtedge e 01642 ) const; 01643 01644 01645 01646 01653 bool 01654 is_multiple 01655 ( 01656 gdtedge e 01657 ) const; 01658 01659 01660 01661 01668 bool 01669 is_marked 01670 ( 01671 gdtnode v, 01672 marker_type m 01673 ) const; 01674 01675 01676 01677 01684 bool 01685 is_marked 01686 ( 01687 gdtedge e, 01688 marker_type m 01689 ) const; 01690 01691 01692 01693 01699 gdtnode 01700 find_first_node_marked_as 01701 ( 01702 marker_type m 01703 ) const; 01704 01705 01706 01707 01713 gdtedge 01714 find_first_edge_marked_as 01715 ( 01716 marker_type m 01717 ) const; 01718 01719 01720 01721 01727 gdt::gdtlist<gdtnode> 01728 find_nodes_marked_as 01729 ( 01730 marker_type m 01731 ) const; 01732 01733 01734 01735 01741 gdt::gdtlist<gdtedge> 01742 find_edges_marked_as 01743 ( 01744 marker_type m 01745 ) const; 01746 01747 01748 01749 01756 gdt::gdtlist<gdtedge> 01757 find_adj_edges_marked_as 01758 ( 01759 gdtnode v, 01760 marker_type m 01761 ) const; 01762 01763 01764 01765 01773 gdt::gdtlist<gdtedge> 01774 find_adj_edges_not_marked_as 01775 ( 01776 gdtnode v, 01777 marker_type m 01778 ) const; 01779 01780 01781 01789 gdt::gdtlist<gdtedge> 01790 find_in_edges_marked_as 01791 ( 01792 gdtnode v, 01793 marker_type m 01794 ) const; 01795 01796 01797 01798 01805 gdt::gdtlist<gdtedge> 01806 find_out_edges_marked_as 01807 ( 01808 gdtnode v, 01809 marker_type m 01810 ) const; 01811 01812 01813 01822 gdt::gdtlist<gdtedge> 01823 edges_with_extremal_nodes 01824 ( 01825 gdtnode v1, 01826 gdtnode v2 01827 ) const; 01828 01829 01830 01831 01839 gdtnode 01840 node_between_adj_edges 01841 ( 01842 gdtedge e1, 01843 gdtedge e2 01844 ) const; 01845 01846 01847 01848 01861 bool 01862 simple_DFS 01863 ( 01864 gdtnode v, 01865 gdt::gdtnode_array<bool>& reached, 01866 gdt::gdtnode_array<gdtedge>& father, 01867 gdt::gdtlist<gdtnode>& order 01868 ) const; 01869 01870 01871 01872 01885 bool 01886 simple_BFS 01887 ( 01888 gdtnode v, 01889 gdt::gdtnode_array<bool>& reached, 01890 gdt::gdtnode_array<gdtedge>& father, 01891 gdt::gdtnode_array<int>& dist, 01892 gdt::gdtlist<gdtnode>& order 01893 ) const; 01894 01895 01896 01897 01917 bool 01918 complex_DFS 01919 ( 01920 gdtnode v, 01921 gdtedge e, 01922 gdt::gdtnode_array<bool>& reached, 01923 gdt::gdtnode_array<gdtedge>& father, 01924 gdt::gdtlist<gdtnode>& order, 01925 gdt::gdtnode_array<gdtnode>& lowpt1, 01926 gdt::gdtnode_array<gdtnode>& lowpt2, 01927 gdt::gdtnode_array<int>& num_succ, 01928 bool& root_is_articulated 01929 ) const; 01930 01931 01932 01933 01946 bool 01947 spanning_tree 01948 ( 01949 gdt::gdtlist<gdtedge>& spanned_edges, 01950 gdt::gdtlist<gdtedge>& unspanned_edges, 01951 gdtnode start_node = NULL_NODE 01952 ) const; 01953 01954 01955 01956 01970 int 01971 unweighted_unoriented_shortest_path 01972 ( 01973 gdtnode start_node, 01974 gdtnode end_node, 01975 gdt::gdtlist<gdtnode>& nodes, 01976 gdt::gdtlist<gdtedge>& edges 01977 ) const; 01978 01979 01980 01981 01990 void 01991 visit_from_node_through_not_marked_nodes 01992 ( 01993 gdtnode v, 01994 gdt::gdtnode_array<bool>& marked_node, 01995 gdt::gdtlist<gdtedge>& visited_edges 01996 ) const; 01997 01998 02009 gdtnode 02010 compare 02011 ( 02012 gdtnode v, 02013 gdtnode w, 02014 gdt::gdtnode_array<int>& f, 02015 compare_option co = MIN 02016 ) const; 02017 02018 02019 02027 gdtnode 02028 find_node 02029 ( 02030 int id 02031 ) const; 02032 02033 02034 02035 02039 gdtnode 02040 first_node 02041 ( 02042 ) const; 02043 02044 02045 02046 02050 gdtnode 02051 last_node 02052 ( 02053 ) const; 02054 02055 02056 02057 02062 gdtnode 02063 succ_node 02064 ( 02065 gdtnode v 02066 ) const; 02067 02068 02069 02070 02075 gdtnode 02076 pred_node 02077 ( 02078 gdtnode v 02079 ) const; 02080 02081 02082 02083 02088 inline 02089 gdtnode 02090 source 02091 ( 02092 gdtedge e 02093 ) const 02094 { 02095 return (*edge_info)[e].source; 02096 } 02097 02098 02099 02100 02105 inline 02106 gdtnode 02107 target 02108 ( 02109 gdtedge e 02110 ) const 02111 { 02112 return (*edge_info)[e].target; 02113 } 02114 02115 02116 02117 02124 inline 02125 gdtnode 02126 opposite 02127 ( 02128 gdtnode v, 02129 gdtedge e 02130 ) const 02131 { 02132 gdtnode n = NULL_NODE; 02133 if ( v==source(e) ) 02134 n=target(e); 02135 else if (v==target(e)) 02136 n=source(e); 02137 else 02138 assert(!"wrong arguments to undi_graph::opposite()"); 02139 02140 return n; 02141 } 02142 02143 02144 02150 inline 02151 gdtnode 02152 start 02153 ( 02154 gdtedge e 02155 ) const 02156 { 02157 return (*edge_info)[e].start; 02158 } 02159 02160 02161 02162 02168 gdtnode 02169 stop 02170 ( 02171 gdtedge e 02172 ) const; 02173 02174 02175 02180 gdt::gdtlist<gdtnode> 02181 adj_nodes 02182 ( 02183 gdtnode v 02184 ) const; 02185 02186 02187 02188 02192 //Modified by A.M. 10/2002 02193 const 02194 gdt::gdtlist<gdtnode>& 02195 all_nodes 02196 ( 02197 ) const; 02198 02199 02200 02201 02209 gdtedge 02210 find_edge 02211 ( 02212 int id 02213 ) const; 02214 02215 02216 02217 02225 gdtedge 02226 find_edge 02227 ( 02228 gdtnode v1, 02229 gdtnode v2 02230 ) const; 02231 02232 02233 02234 02238 gdtedge 02239 first_edge 02240 ( 02241 ) const; 02242 02243 02244 02248 gdtedge 02249 last_edge 02250 ( 02251 ) const; 02252 02253 02254 02255 02260 gdtedge 02261 succ_edge 02262 ( 02263 gdtedge e 02264 ) const; 02265 02266 02267 02268 02273 gdtedge 02274 pred_edge 02275 ( 02276 gdtedge e 02277 ) const; 02278 02279 02280 02281 02286 gdtedge 02287 first_in_edge 02288 ( 02289 gdtnode v 02290 ); 02291 02292 02293 02294 02299 gdtedge 02300 first_out_edge 02301 ( 02302 gdtnode v 02303 ); 02304 02305 02306 02307 02312 gdtedge 02313 first_adj_edge 02314 ( 02315 gdtnode v 02316 ) const; 02317 02318 02319 02320 02325 gdtedge 02326 last_in_edge 02327 ( 02328 gdtnode v 02329 ); 02330 02331 02332 02333 02338 gdtedge 02339 last_out_edge 02340 ( 02341 gdtnode v 02342 ); 02343 02344 02345 02346 02351 gdtedge 02352 last_adj_edge 02353 ( 02354 gdtnode v 02355 ) const; 02356 02357 02358 02359 02367 gdtedge 02368 in_succ 02369 ( 02370 gdtedge e, 02371 gdtnode v 02372 ); 02373 02374 02375 02376 02384 gdtedge 02385 out_succ 02386 ( 02387 gdtedge e, 02388 gdtnode v 02389 ); 02390 02391 02392 02393 02401 gdtedge 02402 adj_succ 02403 ( 02404 gdtedge e, 02405 gdtnode v 02406 ) const; 02407 02408 02409 02410 02418 gdtedge 02419 in_pred 02420 ( 02421 gdtedge e, 02422 gdtnode v 02423 ); 02424 02425 02426 02427 02435 gdtedge 02436 out_pred 02437 ( 02438 gdtedge e, 02439 gdtnode v 02440 ); 02441 02442 02443 02444 02452 gdtedge 02453 adj_pred 02454 ( 02455 gdtedge e, 02456 gdtnode v 02457 ) const; 02458 02459 02460 02461 02469 gdtedge 02470 cyclic_in_succ 02471 ( 02472 gdtedge e, 02473 gdtnode v 02474 ); 02475 02476 02477 02478 02486 gdtedge 02487 cyclic_out_succ 02488 ( 02489 gdtedge e, 02490 gdtnode v 02491 ); 02492 02493 02494 02495 02503 gdtedge 02504 cyclic_adj_succ 02505 ( 02506 gdtedge e, 02507 gdtnode v 02508 ) const; 02509 02510 02511 02520 gdtedge 02521 cyclic_in_pred 02522 ( 02523 gdtedge e, 02524 gdtnode v 02525 ); 02526 02527 02528 02529 02537 gdtedge 02538 cyclic_out_pred 02539 ( 02540 gdtedge e, 02541 gdtnode v 02542 ); 02543 02544 02545 02546 02554 gdtedge 02555 cyclic_adj_pred 02556 ( 02557 gdtedge e, 02558 gdtnode v 02559 ) const; 02560 02561 02562 02563 02573 gdtedge 02574 find_directed_edge 02575 ( 02576 gdtnode v1, 02577 gdtnode v2 02578 ); 02579 02580 02581 02582 02592 gdtedge 02593 reverse_of_edge 02594 ( 02595 gdtedge e 02596 ); 02597 02598 02599 02600 02606 gdt::gdtlist<gdtedge> 02607 in_edges 02608 ( 02609 gdtnode v 02610 ); 02611 02612 02613 02614 02619 gdt::gdtlist<gdtedge> 02620 out_edges 02621 ( 02622 gdtnode v 02623 ); 02624 02625 02626 02627 02632 gdt::gdtlist<gdtedge> 02633 adj_edges 02634 ( 02635 gdtnode v 02636 ) const; 02637 02638 02639 02640 02644 //Modified by A.M. 10/2002 02645 const 02646 gdt::gdtlist<gdtedge>& 02647 all_edges 02648 ( 02649 ) const; 02650 02651 02652 02653 02664 gdt::list_item 02665 pos_of_edge_in_adj_edges_of_node 02666 ( 02667 gdtedge e, 02668 gdtnode v 02669 ) const; 02670 02671 02672 02673 02682 constraint 02683 find_constraint 02684 ( 02685 int id 02686 ) const; 02687 02688 02689 02690 02694 constraint 02695 first_constraint 02696 ( 02697 ) const; 02698 02699 02700 02701 02705 constraint 02706 last_constraint 02707 ( 02708 ) const; 02709 02710 02711 02712 02718 constraint 02719 succ_constraint 02720 ( 02721 constraint c 02722 ) const; 02723 02724 02725 02726 02732 constraint 02733 pred_constraint 02734 ( 02735 constraint c 02736 ) const; 02737 02738 02739 02740 02745 const 02746 gdt::gdtlist<constraint>& 02747 all_constraints 02748 ( 02749 ) const; 02750 02751 02752 02753 02758 gdt::gdtlist<constraint> 02759 constraints_on_edge 02760 ( 02761 gdtedge e 02762 ); 02763 02764 02765 02766 02771 gdt::gdtlist<constraint> 02772 constraints_on_node 02773 ( 02774 gdtnode v 02775 ); 02776 02777 02778 02779 02784 gdt::gdtlist<marker_type> 02785 markers 02786 ( 02787 gdtnode v 02788 ) const; 02789 02790 02791 02792 02797 gdt::gdtlist<marker_type> 02798 markers 02799 ( 02800 gdtedge e 02801 ) const; 02802 02803 02804 02805 02806 /* 02807 CATEGORY translate 02808 Translate operations. 02809 */ 02810 02811 02823 gdtnode 02824 corresponding_node 02825 ( 02826 gdtnode v, 02827 const undi_graph& ug 02828 ) const; 02829 02830 02831 02832 02844 gdtedge 02845 corresponding_edge 02846 ( 02847 gdtedge e, 02848 const undi_graph& ug 02849 ) const; 02850 02851 02852 02853 02864 constraint 02865 corresponding_constraint 02866 ( 02867 constraint c, 02868 const undi_graph& ug 02869 ) const; 02870 02871 02872 02873 02884 void 02885 build_mapping_node_to_node_with_undi_graph 02886 ( 02887 const undi_graph& ug, 02888 gdt::gdtnode_map<gdtnode>& node_corr_in_ug 02889 ) const; 02890 02891 02892 02893 02904 void 02905 build_mapping_edge_to_edge_with_undi_graph 02906 ( 02907 const undi_graph& ug, 02908 gdt::gdtedge_map<gdtedge>& edge_corr_in_ug 02909 ) const; 02910 02911 02912 02913 /* 02914 CATEGORY update 02915 Update operations. 02916 */ 02917 02918 02931 gdtnode 02932 new_node 02933 ( 02934 int new_id=AUTO_ID 02935 ); 02936 02937 02938 02939 02954 gdtnode 02955 new_node 02956 ( 02957 gdt::gdtlist<gdtnode> L, 02958 int new_id=AUTO_ID 02959 ); 02960 02961 02962 02963 02977 gdtedge 02978 new_edge 02979 ( 02980 gdtnode v1, 02981 gdtnode v2, 02982 int new_id=AUTO_ID 02983 ); 02984 02985 02986 02987 03005 gdtedge 03006 new_edge 03007 ( 03008 gdtnode v1, 03009 gdtedge e1, 03010 gdtnode v2, 03011 int new_id=AUTO_ID, 03012 int dir=gdt::after 03013 ); 03014 03015 03016 03017 03038 gdtedge 03039 new_edge 03040 ( 03041 gdtnode v1, 03042 gdtedge e1, 03043 gdtnode v2, 03044 gdtedge e2, 03045 int new_id=AUTO_ID, 03046 int dir=gdt::after 03047 ); 03048 03049 03050 03051 03061 constraint 03062 new_constraint 03063 ( 03064 constraint c 03065 ); 03066 03067 03068 03069 03085 constraint 03086 new_constraint_uncrossable_edge 03087 ( 03088 gdtedge e, 03089 int new_id=AUTO_ID 03090 ); 03091 03092 03093 03094 03113 constraint 03114 new_constraint_number_of_bends_on_edge 03115 ( 03116 gdtedge e, 03117 bend_constraint b, 03118 int new_id=AUTO_ID 03119 ); 03120 03121 03122 03123 03141 constraint 03142 new_constraint_bend_direction_on_edge 03143 ( 03144 gdtedge e, 03145 gdtnode v, 03146 int new_id=AUTO_ID 03147 ); 03148 03149 03150 03151 03165 constraint 03166 new_constraint_same_face_node 03167 ( 03168 gdtnode v, 03169 int face_label, 03170 int new_id=AUTO_ID 03171 ); 03172 03173 03174 03175 03185 gdt::gdtlist<constraint> 03186 new_constraint_same_face_node 03187 ( 03188 gdt::gdtlist<gdtnode> Ln, 03189 int face_label 03190 ); 03191 03192 03193 03194 03207 constraint 03208 new_constraint_same_face_ordered_nodes 03209 ( 03210 gdt::gdtlist<gdtnode> Ln, 03211 int new_id=AUTO_ID 03212 ); 03213 03214 03215 03228 constraint 03229 new_constraint_node_width 03230 ( 03231 gdtnode n, 03232 double x, 03233 int new_id=AUTO_ID 03234 ); 03235 03236 03237 03250 constraint 03251 new_constraint_node_height 03252 ( 03253 gdtnode n, 03254 double x, 03255 int new_id=AUTO_ID 03256 ); 03257 03258 03259 03260 /* 03261 Adds a new constraint 03262 imposing an angle of <I>alpha</I> degrees 03263 to the right of edge <I>e</I>, starting from 03264 node <I>v</I>, in a drawing of the graph. 03265 @param rn a gdtnode 03266 @param re a gdtedge 03267 @param alpha an angle_type value in the set 03268 {_000,_090, _180, _270, _360} 03269 @return the new constraint.<P> 03270 <B>PRECONDITIONS:</B> if specified, <I>new_id</I> is 03271 non-negative and is unique. <I>e</I> is incident on <I>v</I>. 03272 */ 03273 constraint 03274 new_constraint_angle_sweep 03275 ( 03276 gdtnode rn, 03277 gdtedge re, 03278 angle_type alpha, 03279 int new_id=AUTO_ID 03280 ); 03281 03282 03298 constraint 03299 new_constraint_edge_attachment_wrt_previous_corner 03300 ( 03301 gdtnode rn, 03302 gdtedge re, 03303 int value, 03304 int new_id=AUTO_ID 03305 ); 03306 03307 /* 03308 THIS CONSTRAINT DOES NOT WORK CORRECTLY 03309 METHOD new_constraint_min_tieing 03310 */ 03311 03312 constraint 03313 new_constraint_min_tieing 03314 ( 03315 int value, 03316 int new_id=AUTO_ID 03317 ); 03318 03324 void 03325 del_node 03326 ( 03327 gdtnode v 03328 ); 03329 03330 03331 03332 03338 void 03339 del_edge 03340 ( 03341 gdtedge e 03342 ); 03343 03344 03345 03346 03352 void 03353 del_constraint 03354 ( 03355 constraint c 03356 ); 03357 03358 03359 03360 03366 void 03367 del_constraints_type 03368 ( 03369 constraint_type ct 03370 ); 03371 03372 03373 03374 03379 void 03380 del_all_constraints 03381 ( 03382 ); 03383 03384 03385 03386 03392 void 03393 del_all_constraints_involving_edge 03394 ( 03395 gdtedge e 03396 ); 03397 03398 03399 03400 03407 void 03408 del_all_constraints_involving_node 03409 ( 03410 gdtnode v 03411 ); 03412 03413 03414 03415 03422 void 03423 del_constraints_type_involving_edge 03424 ( 03425 constraint_type ct, 03426 gdtedge e 03427 ); 03428 03429 03430 03431 03438 void 03439 del_constraints_type_involving_node 03440 ( 03441 constraint_type ct, 03442 gdtnode v 03443 ); 03444 03445 03446 03447 03452 void 03453 clear 03454 ( 03455 ); 03456 03457 03458 03459 03470 void 03471 mirror 03472 ( 03473 undi_graph& ug 03474 ); 03475 03476 03477 03478 03484 void 03485 forget 03486 ( 03487 ); 03488 03489 03490 03491 03499 void 03500 assign_id 03501 ( 03502 gdtnode v, 03503 int new_id = AUTO_ID 03504 ); 03505 03506 03507 03508 03515 void 03516 assign_id 03517 ( 03518 gdtedge e, 03519 int new_id = AUTO_ID 03520 ); 03521 03522 03523 03524 03531 void 03532 assign_id 03533 ( 03534 constraint c, 03535 int new_id = AUTO_ID 03536 ); 03537 03538 03539 03540 03545 void 03546 mark 03547 ( 03548 gdtnode v, 03549 marker_type m 03550 ); 03551 03552 03553 03554 03559 void 03560 mark 03561 ( 03562 gdtedge e, 03563 marker_type m 03564 ); 03565 03566 03567 03568 03573 void 03574 mark 03575 ( 03576 gdtnode v, 03577 gdt::gdtlist<marker_type> ml 03578 ); 03579 03580 03581 03582 03587 void 03588 mark 03589 ( 03590 gdtedge e, 03591 gdt::gdtlist<marker_type> ml 03592 ); 03593 03594 03595 03596 03601 void 03602 unmark 03603 ( 03604 gdtnode v, 03605 marker_type m 03606 ); 03607 03608 03609 03610 03615 void 03616 unmark 03617 ( 03618 gdtedge e, 03619 marker_type m 03620 ); 03621 03622 03623 03624 03629 void 03630 unmark_all 03631 ( 03632 gdtnode v 03633 ); 03634 03635 03636 03637 03642 void 03643 unmark_all 03644 ( 03645 gdtedge e 03646 ); 03647 03648 03649 03650 03658 void 03659 make_embedding_as 03660 ( 03661 const undi_graph& ug 03662 ); 03663 03664 03665 03666 03673 void 03674 make_embedding_cand 03675 ( 03676 gdtnode v 03677 ); 03678 03679 03680 03681 03688 void 03689 make_embedding_cand 03690 ( 03691 ); 03692 03693 03694 03695 03704 bool 03705 make_embedding_planar 03706 ( 03707 ); 03708 03709 03710 03711 03718 bool 03719 make_embedding_cand_planar 03720 ( 03721 ); 03722 03723 03724 03725 03738 gdt::gdtlist<gdtedge> 03739 make_embedding_cand_expanded 03740 ( 03741 ); 03742 03743 03744 03745 03753 gdt::gdtlist<gdtnode> 03754 make_simple 03755 ( 03756 ); 03757 03758 03759 03767 gdt::gdtlist<gdtedge> 03768 make_connected 03769 ( 03770 ); 03771 03772 03773 03774 03781 gdt::gdtlist<gdtedge> 03782 make_biconnected 03783 ( 03784 ) ; 03785 03795 int 03796 make_max_degree 03797 ( 03798 int d 03799 ); 03800 03801 03802 03803 03810 void 03811 make_directed 03812 ( 03813 gdtedge e, 03814 gdtnode v 03815 ); 03816 03817 03818 03819 03826 void 03827 make_directed 03828 ( 03829 bool randomly = false 03830 ); 03831 03832 03833 03834 03842 void 03843 make_directed 03844 ( 03845 gdtnode s, 03846 gdtnode t 03847 ); 03848 03849 03850 03851 03856 void 03857 make_undirected 03858 ( 03859 gdtedge e 03860 ); 03861 03862 03863 03864 03869 void 03870 make_undirected 03871 ( 03872 ); 03873 03874 03875 03876 03882 void 03883 make_source 03884 ( 03885 gdtnode v 03886 ); 03887 03888 03889 03890 03896 void 03897 make_sink 03898 ( 03899 gdtnode v 03900 ); 03901 03902 03903 03904 03909 void 03910 reverse 03911 ( 03912 gdtedge e 03913 ); 03914 03915 03916 03917 03926 void 03927 st_number 03928 ( 03929 gdtedge e_st, 03930 gdtnode s, 03931 gdt::gdtnode_array<int>& st_num 03932 ); 03933 03934 03935 // *************************************************************** 03936 // --------------------------------------------------------------- 03937 // THESE FUNCTIONS ARE INTENDED FOR st-ORIENTED BICONNECTED GRAPHS 03938 // --------------------------------------------------------------- 03939 03940 03941 03949 int 03950 calculate_level_of_node 03951 ( 03952 gdtnode v, 03953 gdt::gdtnode_array<int>& levels_buffer 03954 ); 03955 03956 03957 03958 03965 void 03966 calculate_level_of_all_nodes 03967 ( 03968 gdt::gdtnode_array<int>& levels_buffer 03969 ); 03970 03971 // *************************************************************** 03972 03973 03974 03975 03976 03983 gdtedge 03984 weld_edges_at_node 03985 ( 03986 gdtnode v 03987 ); 03988 03989 03990 03991 04001 gdtedge 04002 expand 04003 ( 04004 gdtnode v, 04005 gdtedge e_init, 04006 gdtedge e_end 04007 ); 04008 04009 04010 04018 gdtnode 04019 contract 04020 ( 04021 gdtedge e 04022 ); 04023 04024 04025 04026 04033 gdt::gdtlist<gdtnode> 04034 contract 04035 ( 04036 ); 04037 04038 04039 04040 04046 void 04047 update_max_node_id 04048 ( 04049 ); 04050 04051 04052 04053 04059 void 04060 update_max_edge_id 04061 ( 04062 ); 04063 04064 04065 04066 04072 void 04073 update_max_constraint_id 04074 ( 04075 ); 04076 04077 04078 04079 04087 void 04088 rise_max_node_id 04089 ( 04090 int new_max_node_id 04091 ); 04092 04093 04094 04095 04103 void 04104 rise_max_edge_id 04105 ( 04106 int new_max_edge_id 04107 ); 04108 04109 04110 04111 04119 void 04120 rise_max_constraint_id 04121 ( 04122 int new_max_constraint_id 04123 ); 04124 04125 04126 04127 04152 int 04153 planarize 04154 ( 04155 planarize_options po = DO_NOT_PRESERVE_EMBEDDING 04156 ); 04157 04158 04159 04160 04171 gdt::gdtlist<gdtedge> 04172 replace_edge_with_path 04173 ( 04174 gdtedge e, 04175 gdt::gdtlist<int>& node_id_path, 04176 gdt::gdtlist<int>& edge_id_path 04177 ); 04178 04179 04180 04181 04192 gdt::gdtlist<gdtedge> 04193 replace_edge_with_path_of_graph 04194 ( 04195 gdtedge e, 04196 gdt::gdtlist<gdtedge>& edge_path, 04197 undi_graph& ug 04198 ); 04199 04200 04201 04202 04223 void 04224 generate_plan_biconnected 04225 ( 04226 int n, 04227 double prob_iv, 04228 int k=INFINITE, 04229 bool multiple = true 04230 ); 04231 04232 04240 void 04241 disable_keep_ordering_of_directed_edges 04242 (); 04243 04244 04252 void 04253 enable_keep_ordering_of_directed_edges 04254 (); 04255 04256 04257 04258 /* 04259 CATEGORY io_operations 04260 Input / output operations. 04261 */ 04262 04263 04339 bool 04340 write 04341 ( 04342 std::string file_name 04343 ); 04344 04345 04346 04347 04354 bool 04355 read 04356 ( 04357 std::string file_name 04358 ); 04359 04360 04361 04362 04368 void 04369 append_section_to_fstream 04370 ( 04371 std:: 04372 ofstream& out 04373 ); 04374 04375 04376 04377 04382 void 04383 read_section_from_fstream 04384 ( 04385 std::ifstream& in 04386 ); 04387 04388 04389 04390 04403 void 04404 print 04405 ( 04406 print_mode mode=BY_NODES, 04407 std::ostream& os=std::cout 04408 ) const; 04409 04410 04411 04412 04417 void 04418 print 04419 ( 04420 gdtnode v, 04421 std::ostream& os=std::cout 04422 ) const; 04423 04424 04425 04426 04431 void 04432 print 04433 ( 04434 gdtedge e, 04435 std::ostream& os=std::cout 04436 ) const; 04437 04438 04439 04440 04447 void 04448 print 04449 ( 04450 constraint c, 04451 std::ostream& os=std::cout 04452 ) const; 04453 04454 04455 04456 04462 void 04463 print_constraints_on_node 04464 ( 04465 gdtnode v, 04466 std::ostream& os=std::cout 04467 ); 04468 04469 04470 04471 04477 void 04478 print_constraints_on_edge 04479 ( 04480 gdtedge e, 04481 std::ostream& os=std::cout 04482 ); 04483 04484 04485 04486 04491 void 04492 print_constraints 04493 ( 04494 std::ostream& os=std::cout 04495 ) const; 04496 04497 04498 04499 04500 04501 /* 04502 CATEGORY consistency_check 04503 Consistency check. 04504 */ 04505 04510 bool 04511 internal_consistency_check 04512 ( 04513 ) const; 04514 04515 04516 /***********************************************************************************************************/ 04517 04518 /* 04519 CATEGORY PLANARITY 04520 The following functions compute a planar embedding of a biconnected graph. (algorithm by Boyer % Myrvold) 04521 */ 04522 04523 04524 04525 04539 bool 04540 bm_spanning_tree 04541 ( 04542 //node DFI_vector[], 04543 bm_node_info node_vector[], 04544 //edge_map<bm_edge_info*>& edge_vector, 04545 //int lowpoint[], 04546 //edge parent[], 04547 //list<node> children[], 04548 //list<node> in_back_edge[], 04549 //int first_back_edge_dfi[], 04550 gdt::gdtlist<gdtedge>& added_edges, 04551 bic_obj_node* IMM[], 04552 gdtnode v, 04553 bool reached[], 04554 bool e_reached[], 04555 //edge_map<bool>& e_reached, 04556 gdtedge iterator[], 04557 gdtnode graph_nodes[], 04558 int& nodes_in_component, 04559 bic_obj*& bic_obj_actual_pointer, 04560 bic_obj_node*& bic_obj_node_actual_pointer 04561 ) ; 04562 04563 04575 void 04576 create_children_ordered 04577 ( 04578 bm_node_info node_vector[], 04579 //int lowpoint[], 04580 //edge parent[], 04581 //list<node> children_ordered[], 04582 //list_item position_in_parent_list[], 04583 gdtnode graph_nodes[], 04584 int nodes_in_component 04585 ); 04586 04587 04588 04600 void 04601 create_out_back_edges_ordered 04602 ( 04603 bm_node_info node_vector[] 04604 ); 04605 04606 04622 bool 04623 bm_preprocessing 04624 ( 04625 //node DFI_vector[], 04626 bm_node_info node_vector[], 04627 //int lowpoint[], 04628 //edge parent[], 04629 //list<node> children[], 04630 //list<node> children_ordered[], 04631 //list<node> in_back_edge[], 04632 //int first_back_edge_dfi[], 04633 //list_item position_in_parent_list[], 04634 //edge_map<bm_edge_info*>& edge_vector, 04635 gdt::gdtlist<gdtedge>& added_edges, 04636 gdtnode root, 04637 bic_obj_node* IMM[], 04638 bool reached[], 04639 bool e_reached[], 04640 //edge_map<bool>& e_reached, 04641 gdtedge iterator[], 04642 int& nodes_in_component, 04643 gdtnode graph_nodes[], 04644 bic_obj*& bic_obj_actual_pointer, 04645 bic_obj_node*& bic_obj_node_actual_pointer 04646 ); 04647 04648 04649 04662 int 04663 create_bicomp 04664 ( 04665 gdtnode root, 04666 bm_node_info node_vector[], 04667 //edge_map<bm_edge_info*>& edge_vector, 04668 gdt::gdtnode_map<bic_obj_node*>& IMM 04669 ); 04670 04671 04672 04673 04690 bool 04691 make_planar_embedding 04692 ( 04693 bm_node_info node_vector[], 04694 //int lowpoint[], 04695 //edge parent[], 04696 //list<node> children[], 04697 //list<node> children_ordered[], 04698 //list<node> in_back_edges[], 04699 //int first_back_edge_dfi[], 04700 //list_item position_in_parent_list[], 04701 04702 bic_obj_node* IMM[], 04703 gdtnode root, 04704 //edge_map<bool>& edge_to_be_inserted 04705 bool edge_to_be_inserted[], 04706 int flip[], 04707 bic_obj*& bic_obj_actual_pointer 04708 ); 04709 04710 04711 04723 bool 04724 merge_biconnected 04725 ( 04726 gdt::gdtlist<undi_graph*>& bic 04727 ); 04728 04729 04730 04741 bool 04742 boyer 04743 ( 04744 gdtnode root 04745 ); 04746 04747 04748 bool 04749 is_planar(); 04750 04751 04752 04753 04760 void 04761 destroy_bicomp 04762 ( 04763 gdt::gdtlist<bic_obj*>& bic_obj_created 04764 ); 04765 04766 04767 04768 04775 int 04776 compare_embedding(undi_graph& ug); 04777 04778 04779 04785 void 04786 visible_subgraph(gdtnode n,int k, undi_graph& vg); 04787 04788 04789 04795 int 04796 kplanarity 04797 ( 04798 gdtnode n 04799 ); 04800 04801 04802 int 04803 extended_kplanarity 04804 ( 04805 gdtnode n 04806 ); 04807 04808 04809 04814 void 04815 kplanarity(gdt::gdtnode_map<int>& kplan); 04816 04817 04818 void 04819 extended_kplanarity(gdt::gdtnode_map<int>& kplan); 04820 04821 04822 /***********************************************************************************************************/ 04823 04824 /* 04825 CATEGORY C-PLANARITY 04826 The following functions are needed by the c-planarity testing 04827 */ 04828 04829 04830 04835 bool 04836 quick_minimum_spanning_tree 04837 ( 04838 gdt::gdtedge_map<int> weights, 04839 gdt::gdtlist<gdtedge>& span_edges 04840 ); 04841 04842 04843 }; // end of class undi_graph 04844 04845 04846 04847 /*************************************************************************************/ 04848 04849 // ------------------------------- 04850 // Macro for ordered gdtedge scanning 04851 // ------------------------------- 04852 04853 //Added by A.M. 04854 #undef forall_nodes 04855 #undef forall_edges 04856 #define forall_nodes(v,G)\ 04857 for(v=(G).first_node();v;v=(G).succ_node(v)) 04858 04859 #define forall_edges(e,G)\ 04860 for(e=(G).first_edge();e;e=(G).succ_edge(e)) 04861 // 04862 04863 #define forall_edges_adjacent_node(e,v,G)\ 04864 for(e=(G).first_adj_edge(v);e;e=(G).adj_succ(e,v)) 04865 04866 #define forall_edges_entering_node(e,v,G)\ 04867 for(e=(G).first_in_edge(v);e;e=(G).in_succ(e,v)) 04868 04869 #define forall_edges_leaving_node(e,v,G)\ 04870 for(e=(G).first_out_edge(v);e;e=(G).out_succ(e,v)) 04871 04872 #define forall_constraints(c,G)\ 04873 for(c=(G).first_constraint();c;c=(G).succ_constraint(c)) 04874 04875 04876 #endif
1.5.3