00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00020 #ifndef RM3_DIRE_GRAPH_H
00021 #define RM3_DIRE_GRAPH_H
00022
00023 #if !defined(ROOT_INCL_ID)
00024 #define ROOT_INCL_ID 34004
00025 #endif
00026
00027 #include <GDT/rm3_undi_graph.h>
00028 #include <GDT/gdtnode_pq.h>
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00048 class GDT_NONSTANDARD_DECL
00049 dire_graph
00050 : public undi_graph
00051 {
00052 private:
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063 void local_new ();
00064 void local_del ();
00065 void local_renew();
00066 void local_init ();
00067
00068 void make_undirected ();
00069
00070
00071 public:
00072
00073
00074
00075
00076
00077
00078
00079
00084 dire_graph
00085 (
00086 );
00087
00088
00089
00095 dire_graph
00096 (
00097 const undi_graph&
00098 );
00099
00100
00101
00102
00103
00104
00105
00106
00112 dire_graph&
00113 operator=
00114 (
00115 const undi_graph&
00116 );
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00132 gdtnode
00133 find_source
00134 (
00135 );
00136
00137
00138
00144 gdtnode
00145 find_sink
00146 (
00147 );
00148
00149
00150
00160 void
00161 find_shortest_path
00162 (
00163 gdtnode s,
00164 gdt::gdtedge_array<int>& length,
00165 gdt::gdtnode_array<int>& distance,
00166 gdt::gdtnode_array<gdtedge>& pred_edge
00167 );
00168
00169
00170
00180 void
00181 find_longest_path
00182 (
00183 gdtnode s,
00184 gdt::gdtedge_array<int>& length,
00185 gdt::gdtnode_array<int>& distance,
00186 gdt::gdtnode_array<gdtedge>& pred_edge
00187 );
00188
00189
00190
00201 void
00202 find_path_with_minimum_switches
00203 (
00204 gdtnode s,
00205 gdt::gdtnode_array<int>& switches,
00206 gdt::gdtnode_array<gdtedge>& pred_edge,
00207 visit_direction_type dir
00208 );
00209
00210
00211
00221 void
00222 find_path_with_minimum_switches
00223 (
00224 gdtnode s,
00225 gdtnode t,
00226 gdt::gdtnode_array<int>& switches,
00227 gdt::gdtnode_array<gdtedge>& pred_edge
00228 );
00229
00230
00231
00240 void
00241 Dijkstra
00242 (
00243 gdtnode s,
00244 gdt::gdtedge_array<int>& length,
00245 gdt::gdtnode_array<int>& distance,
00246 gdt::gdtnode_array<gdtedge>& pred_edge
00247 );
00248
00249
00250
00260 gdt::gdtlist<gdtedge>
00261 simple_DFS
00262 (
00263 gdtnode v,
00264 gdt::gdtnode_array<bool>& reached,
00265 gdt::gdtnode_array<gdtedge>& father,
00266 gdt::gdtlist<gdtnode>& order,
00267 visit_direction_type dt = OUTGOING
00268 );
00269
00270
00271
00276 bool
00277 is_acyclic
00278 (
00279 );
00280
00281
00288 gdt::gdtlist<gdtedge>
00289 make_acyclic
00290 (
00291 );
00292
00293
00301 bool
00302 topological_sort
00303 (
00304 gdtnode v,
00305 gdt::gdtnode_array<bool>& reached,
00306 gdt::gdtlist<gdtnode>& order
00307 );
00308
00309
00310
00311
00312
00313
00314
00315
00321 gdtedge
00322 new_edge
00323 (
00324 gdtnode v1,
00325 gdtnode v2,
00326 int new_id=AUTO_ID
00327 );
00328
00329
00330
00337 gdtedge
00338 new_edge
00339 (
00340 gdtnode v1,
00341 gdtedge e1,
00342 gdtnode v2,
00343 int new_id=AUTO_ID,
00344 int dir=gdt::after
00345 );
00346
00347
00348
00357 gdtedge
00358 new_edge
00359 (
00360 gdtnode v1,
00361 gdtnode v2,
00362 gdtedge e2,
00363 int new_id=AUTO_ID,
00364 int dir=gdt::after
00365 );
00366
00367
00368
00376 gdtedge
00377 new_edge
00378 (
00379 gdtnode v,
00380 gdtedge ev,
00381 gdtnode w,
00382 gdtedge ew,
00383 int new_id=AUTO_ID,
00384 int dir=gdt::after
00385 );
00386
00387
00388
00393 void
00394 clear
00395 (
00396 );
00397
00398
00408 void
00409 steal_from
00410 (
00411 undi_graph& ug
00412 );
00413 };
00414
00415
00416
00417 #endif