00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00017 #include <GDT/rm3_undi_graph.h>
00018 #include <GDT/rm3_PQ_tree.h>
00019 #include <GDT/gdtmap.h>
00020 #include <GDT/rm3_global.h>
00021
00022 #ifndef RM3_LAYERED_UNDI_GRAPH_H
00023 #define RM3_LAYERED_UNDI_GRAPH_H
00024
00025 #define LEAVES_VALUE gdtnode
00026
00031 class
00032 layered_undi_graph
00033 : public undi_graph
00034 {
00035
00036
00037 typedef gdt::PQ_node_struct<LEAVES_VALUE>* PQ_node;
00038
00039 private:
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 gdt::gdtlist<gdtedge>
00060 remove_cycles
00061 (
00062 );
00063
00064
00065 void
00066 assign_level
00067 (
00068 );
00069
00070
00071 void
00072 create_array
00073 (
00074 gdtnode* current_array
00075 );
00076
00077
00078 void
00079 assign_ascissa
00080 (
00081 );
00082
00083
00084 void
00085 restore_original_direction
00086 (
00087 gdt::gdtlist<gdtedge> reversed_edge
00088 );
00089
00090
00091 void
00092 assign_PQ_tree
00093 (
00094 );
00095
00096 protected:
00097
00098
00099
00100
00101 gdt::gdtnode_map<int> levels;
00102 gdt::gdtnode_map<double> ascisse;
00103
00104 gdt::gdtmap< int,gdt::PQ_tree<LEAVES_VALUE>* > map_level_PQ_tree;
00105 gdt::gdtnode_map<bool> is_dummy;
00106 gdt::gdtlist< gdt::gdtlist<gdtnode> > list_of_path_of_dummy;
00107
00108 public:
00109
00110
00111
00112
00113
00118 layered_undi_graph
00119 (
00120 );
00121
00122
00127 layered_undi_graph
00128 (
00129 undi_graph ug
00130 );
00131
00132
00137 layered_undi_graph
00138 (
00139 undi_graph& ug,
00140 gdt::gdtnode_map<int> in_levels
00141 );
00142
00143
00148 layered_undi_graph
00149 (
00150 undi_graph& ug,
00151 gdt::gdtnode_map<double> in_ascisse
00152 );
00153
00154
00158 layered_undi_graph
00159 (
00160 undi_graph& ug,
00161 gdt::gdtnode_map<int> in_levels,
00162 gdt::gdtnode_map<double> in_ascisse
00163 );
00164
00165
00166
00171 ~layered_undi_graph
00172 (
00173 );
00174
00175
00180 int
00181 number_of_levels
00182 (
00183 );
00184
00185
00190 void
00191 set_level
00192 (
00193 gdtnode n,
00194 int level
00195 );
00196
00197
00202 void
00203 set_level
00204 (
00205 int i,
00206 int level
00207 );
00208
00209
00214 void
00215 set_ascissa
00216 (
00217 gdtnode n,
00218 double ascissa
00219 );
00220
00221
00226 void
00227 set_ascissa
00228 (
00229 int i,
00230 double ascissa
00231 );
00232
00233
00238 int
00239 get_level
00240 (
00241 gdtnode n
00242 );
00243
00244
00249 int
00250 get_level
00251 (
00252 int i
00253 );
00254
00255
00260 double
00261 get_ascissa
00262 (
00263 gdtnode n
00264 );
00265
00266
00271 double
00272 get_ascissa
00273 (
00274 int i
00275 );
00276
00277
00282 gdt::PQ_tree<gdtnode>*
00283 get_PQ_tree
00284 (
00285 int level
00286 );
00287
00288
00289
00294 gdt::gdtlist<gdtnode>
00295 get_list_of_dummy
00296 (
00297 );
00298
00299
00300
00305 int
00306 length_of_edge
00307 (
00308 gdtedge e
00309 );
00310
00311
00316 int
00317 length_of_edge
00318 (
00319 int i
00320 );
00321
00322
00327 double
00328 width_of_level
00329 (
00330 int level
00331 );
00332
00333
00338 int
00339 numbers_of_nodes_of_level
00340 (
00341 int level
00342 );
00343
00344
00345
00349 gdt::gdtlist<gdtnode>
00350 create_list_of_node_of_level
00351 (
00352 int level
00353 );
00354
00355
00356
00360 void
00361 make_proper_layered
00362 (
00363 );
00364
00365
00366
00370 int
00371 count_of_crossing_between_two_levels
00372 (
00373 int level1,
00374 int level2
00375 );
00376
00377
00378
00382 int
00383 count_of_crossing
00384 (
00385 );
00386
00387
00388
00392 gdt::gdtlist<gdtnode>
00393 sort_nodes_of_a_level
00394 (
00395 int level
00396 );
00397
00398
00399
00403 double
00404 find_barycenter
00405 (
00406 gdtnode node
00407 );
00408
00409
00410
00415 void
00416 set_ascisse_on_barycenter_of_a_level
00417 (
00418 int level
00419 );
00420
00421
00422
00427 void
00428 set_ascisse_on_barycenter
00429 (
00430 );
00431
00432
00433
00438 void
00439 reduce_PQ_trees_on_barycenter
00440 (
00441 );
00442
00443 };
00444
00445
00446 #endif
00447