00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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
00027 #include <GDT/gdtstack.h>
00028 #include <string>
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 class SPQR_tree;
00042 class plan_undi_graph;
00043
00044
00045 #define AUTO_ID -1 // AUTO identifier
00046 #define NULL_ID -1 // NULL identifier
00047
00048 extern const gdtnode NULL_NODE;
00049 extern const gdtedge NULL_EDGE;
00050 extern const 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
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
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
00212
00213 int lowpoint;
00214 gdtedge parent;
00215 gdt::gdtlist<gdtnode> children;
00216 gdt::gdtlist<gdtnode> in_back_edges;
00217
00218 int first_back_edge_dfi;
00219 bool ordered_first_black;
00220
00221 gdt::gdtlist<gdtnode> children_ordered;
00222 gdt::list_item position_in_parent_list;
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
00254
00255
00256
00257
00258
00259
00260
00261 class bic_obj {
00262
00263
00264 protected:
00265 #ifdef OUTPUT
00266 std::string label;
00267 #endif
00268 bool is_node;
00269 bic_obj* twin_link;
00270 bic_obj* black;
00271 bic_obj* white;
00272
00273 gdtnode graph_node;
00274 gdtedge graph_edge;
00275
00276
00277
00278 int marked;
00279
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300 bool
00301 is_active
00302 (
00303 int target,
00304 bm_node_info node_vector[]
00305
00306
00307
00308 );
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324 bool
00325 is_root_externally_active
00326 (
00327 int target,
00328 gdtnode child,
00329 bm_node_info node_vector[]
00330
00331
00332
00333 );
00334
00335 bool
00336 is_internally_active_node
00337 (
00338 int target,
00339 bm_node_info node_vector[]
00340
00341
00342 );
00343
00345
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
00362
00363
00364
00365
00366
00367
00368
00369 bic_obj();
00370
00371
00372
00373
00374
00375 ~bic_obj();
00376
00377
00378
00379
00380
00381
00382 bic_obj(gdtnode n);
00383
00384
00385
00386
00387
00388
00389 bic_obj(gdtedge e);
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419 bool
00420 read_node_embedding
00421 (
00422 undi_graph& ug
00423 );
00424
00425
00426
00427
00428
00429
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
00467
00468
00469
00470
00471
00472
00473
00474
00475 bic_obj_node*
00476 next_node
00477 (
00478 bool black
00479 );
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494 bool
00495 walk_up
00496 (
00497 int target,
00498
00499
00500
00501 bm_node_info node_vector[],
00502 gdt::gdtlist<bic_obj_node*>& secondary,
00503 undi_graph& ug
00504
00505 );
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523 bool
00524 walk_down
00525 (
00526 bm_node_info node_vector[],
00527
00528
00529 gdt::gdtlist<bic_obj_node*>& secondary,
00530 undi_graph* ug,
00531
00532
00533 bool edge_to_be_inserted[],
00534 int flip[],
00535 bic_obj*& bic_obj_actual_pointer
00536 );
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548 bool
00549 extract_embedding
00550 (
00551 gdt::gdtstack<bic_obj*>& embedding_stack,
00552
00553 undi_graph& ug
00554 );
00555
00556
00557 bool
00558 embedding_reporting
00559 (
00560 bm_node_info node_vector[],
00561
00562
00563
00564 undi_graph& ug,
00565 int flip[],
00566 bic_obj_node* IMM[]
00567 );
00568
00569 public:
00570
00571
00572
00573
00574
00575 bool
00576 check_bicomp();
00577
00578
00579
00580 };
00581
00582
00583
00584
00585
00586
00587
00588
00595 class struct_gdtnode {
00596 friend class undi_graph;
00597 friend class bic_obj;
00598 friend class bic_obj_node;
00599
00600
00601 gdt::list_item pos_in_nodes;
00602
00603 int plan_id;
00604 public:
00605 struct_gdtnode() {}
00606
00607 int get_plan_id() {return plan_id;}
00608
00609
00610
00611
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
00627
00628 gdt::list_item pos_in_edges;
00629 int plan_id;
00630
00631 public:
00632 struct_gdtedge() {}
00633
00634
00635
00636
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;
00664 gdt::gdtlist<gdtedge> in_edges;
00665 gdt::gdtlist<gdtedge> out_edges;
00666 gdt::gdtlist<gdtedge> adj_edges;
00667
00668 bool in_edges_are_ordered;
00669 bool out_edges_are_ordered;
00670
00671 gdt::gdtlist<marker_type> markers;
00672 gdt::gdtlist<constraint> constraints;
00673
00674
00675
00676 public:
00677
00678
00679
00680
00681
00682
00683
00684
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;
00718 gdtnode source;
00719 gdtnode target;
00720 gdtnode start;
00721 gdt::list_item pos_into_in_edges;
00722 gdt::list_item pos_into_out_edges;
00723 gdt::list_item pos_into_source_adj_edges;
00724 gdt::list_item pos_into_target_adj_edges;
00725
00726 gdt::gdtlist<marker_type> markers;
00727 gdt::gdtlist<constraint> constraints;
00728
00729
00730
00731
00732 public:
00733
00734
00735
00736
00737
00738
00739
00740
00741
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
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
00804
00805
00806
00807 gdt::gdtlist<gdtnode> *nodes;
00808 gdt::gdtlist<gdtedge> *edges;
00809
00810
00811
00812 gdt::gdtnode_map<struct_undi_node_info>* node_info;
00813 gdt::gdtedge_map<struct_undi_edge_info>* edge_info;
00814
00815 gdt::gdtlist<constraint>* constraints;
00816
00817 gdt::gdtmap<int,gdtnode>* node_with_id;
00818 gdt::gdtmap<int,gdtedge>* edge_with_id;
00819 gdt::gdtmap<int,constraint>* constraint_with_id;
00820
00821 int max_node_id;
00822 int max_edge_id;
00823 int max_constraint_id;
00824 int max_edge_plan_id;
00825 bool keep_ordering_of_directed_edges;
00826
00827
00828
00829
00830
00831
00832
00833
00834
00835
00836 void local_new();
00837 void local_del();
00838 void local_renew();
00839 void local_init();
00840
00841 void local_set
00842 (
00843 gdt::gdtlist<gdtnode>*,
00844 gdt::gdtlist<gdtedge>*,
00845
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);
00859 void order_out_edges (gdtnode);
00860 void mark_in_edges_as_not_ordered (gdtnode);
00861 void mark_out_edges_as_not_ordered (gdtnode);
00862
00863 void remove_from_in_edges (gdtedge);
00864 void remove_from_out_edges (gdtedge);
00865 void remove_from_adj_edges (gdtedge);
00866
00867 bool make_embedding_planar0 ();
00868
00869 gdt::gdtlist<constraint>* get_constraints();
00870
00871 gdt::gdtlist<constraint>& all_constraints(gdtedge);
00872 gdt::gdtlist<constraint>& all_constraints(gdtnode);
00873
00874 bool planarize_kernel
00875 (
00876 gdt::gdtlist<gdtedge>&,
00877 gdt::gdtlist<gdtedge>&,
00878 planarize_options po = DO_NOT_PRESERVE_EMBEDDING
00879 );
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892 public:
00893 bool make_embedding_planar_boyer ();
00894
00895 private:
00896
00897
00898
00899
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
00917
00918
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
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944 protected:
00945
00946 void set_source (gdtedge, gdtnode);
00947
00948
00949
00950
00951
00952 void update_constraints_after_del_edge (gdtedge e);
00953 void update_constraints_after_del_node (gdtnode v);
00954
00955 void update_constraints_after_split_edge (gdtedge e, gdtedge e1, gdtedge e2);
00956 void update_constraints_after_split_node (gdtnode v, gdtnode v1, gdtnode v2);
00957
00958 void update_constraints_after_merge_edges (gdtedge e1, gdtedge e2, gdtedge e);
00959 void update_constraints_after_merge_nodes (gdtnode v1, gdtnode v2, gdtnode v);
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 );
00970
00971
00972 void update_constraints_on_path_replacing_edge
00973 (
00974 gdtedge e,
00975 undi_graph& ug,
00976 gdt::gdtlist<gdtedge> path
00977 );
00978
00979
00980
00981
00982
00983 void copy_constraints_from_subgraph_of_undi_graph
00984 (
00985 gdt::gdtlist<gdtedge>& sub,
00986 undi_graph& ug
00987 );
00988
00989
00990 gdt::gdtlist<gdtedge> path_corresponding_to_edge (gdtedge, undi_graph&) const;
00991
00992
00993
00994
00995
00996
00997 int count_not_dummy_nodes () const;
00998
00999
01000 public:
01001
01002
01003
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
01048
01049
01050
01051
01052
01059 undi_graph&
01060 operator =
01061 (
01062 const undi_graph& ug
01063 );
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088
01089
01090
01091 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
01112
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
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
01578
01579
01580
01581
01582
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
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
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
02808
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
02915
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
03262
03263
03264
03265
03266
03267
03268
03269
03270
03271
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
03309
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
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
04260
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
04503
04504
04505
04510 bool
04511 internal_consistency_check
04512 (
04513 ) const;
04514
04515
04516
04517
04518
04519
04520
04521
04522
04523
04524
04525
04539 bool
04540 bm_spanning_tree
04541 (
04542
04543 bm_node_info node_vector[],
04544
04545
04546
04547
04548
04549
04550 gdt::gdtlist<gdtedge>& added_edges,
04551 bic_obj_node* IMM[],
04552 gdtnode v,
04553 bool reached[],
04554 bool e_reached[],
04555
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
04580
04581
04582
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
04626 bm_node_info node_vector[],
04627
04628
04629
04630
04631
04632
04633
04634
04635 gdt::gdtlist<gdtedge>& added_edges,
04636 gdtnode root,
04637 bic_obj_node* IMM[],
04638 bool reached[],
04639 bool e_reached[],
04640
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
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
04695
04696
04697
04698
04699
04700
04701
04702 bic_obj_node* IMM[],
04703 gdtnode root,
04704
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
04826
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 };
04844
04845
04846
04847
04848
04849
04850
04851
04852
04853
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