00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00015 #ifndef RM3_FLOW_DIRE_GRAPH_H
00016 #define RM3_FLOW_DIRE_GRAPH_H
00017
00018 #if !defined(ROOT_INCL_ID)
00019 #define ROOT_INCL_ID 34013
00020 #endif
00021
00022 #include <GDT/rm3_dire_graph.h>
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00043 class GDT_NONSTANDARD_DECL
00044 struct_flow_dire_node_info
00045 {
00046 friend class flow_dire_graph;
00047
00048 int balance;
00049
00050 public:
00051
00052
00053
00054
00055
00056
00061 struct_flow_dire_node_info
00062 (
00063 );
00064 };
00065
00066
00067
00073 class GDT_NONSTANDARD_DECL
00074 struct_flow_dire_edge_info
00075 {
00076 friend class flow_dire_graph;
00077
00078 int upper_cap;
00079 int lower_cap;
00080 int cost;
00081 int flow;
00082
00083 public:
00084
00085
00086
00087
00088
00089
00094 struct_flow_dire_edge_info
00095 (
00096 );
00097 };
00098
00099
00100
00128 class GDT_NONSTANDARD_DECL
00129 flow_dire_graph
00130 : public dire_graph
00131 {
00132 private:
00133
00134
00135
00136
00137 gdt::gdtnode_map<struct_flow_dire_node_info>* node_info;
00138 gdt::gdtedge_map<struct_flow_dire_edge_info>* edge_info;
00139
00140
00141
00142
00143
00144 void local_new ();
00145 void local_del ();
00146 void local_renew();
00147 void local_init ();
00148
00149 void local_set
00150 (
00151 gdt::gdtnode_map<struct_flow_dire_node_info>*,
00152 gdt::gdtedge_map<struct_flow_dire_edge_info>*
00153 );
00154
00155
00156
00157
00158 public:
00159
00160
00161
00162
00163
00164
00165
00170 flow_dire_graph
00171 (
00172 );
00173
00174
00179 ~flow_dire_graph
00180 (
00181 );
00182
00183
00189 flow_dire_graph
00190 (
00191 const undi_graph&
00192 );
00193
00194
00199 flow_dire_graph
00200 (
00201 const dire_graph&
00202 );
00203
00204
00209 flow_dire_graph
00210 (
00211 const flow_dire_graph&
00212 );
00213
00214
00215
00216
00217
00218
00219
00225 flow_dire_graph&
00226 operator =
00227 (
00228 const undi_graph&
00229 );
00230
00231
00236 flow_dire_graph&
00237 operator =
00238 (
00239 const dire_graph&
00240 );
00241
00242
00247 flow_dire_graph&
00248 operator =
00249 (
00250 const flow_dire_graph&
00251 );
00252
00253
00254
00255
00256
00257
00262 void
00263 local_get
00264 (
00265 gdt::gdtnode_map<struct_flow_dire_node_info>*& p1,
00266 gdt::gdtedge_map<struct_flow_dire_edge_info>*& p2
00267 );
00268
00269
00274 int
00275 get_balance
00276 (
00277 gdtnode v
00278 ) const;
00279
00280
00285 int
00286 get_upper_capacity
00287 (
00288 gdtedge e
00289 ) const;
00290
00291
00296 int
00297 get_lower_capacity
00298 (
00299 gdtedge e
00300 ) const;
00301
00302
00307 int
00308 get_flow
00309 (
00310 gdtedge e
00311 ) const;
00312
00313
00318 int
00319 get_cost
00320 (
00321 gdtedge e
00322 ) const;
00323
00324
00329 int
00330 flow_cost
00331 (
00332 ) const;
00333
00334
00339 int
00340 in_flow
00341 (
00342 gdtnode v
00343 );
00344
00345
00350 int
00351 out_flow
00352 (
00353 gdtnode v
00354 );
00355
00356
00361 int
00362 diff_flow
00363 (
00364 gdtnode v
00365 );
00366
00367
00372 bool
00373 balance_is_consistent
00374 (
00375 ) const;
00376
00377
00384 bool
00385 flow_is_consistent
00386 (
00387 gdtedge e
00388 ) const;
00389
00390
00397 bool
00398 flow_is_consistent
00399 (
00400 gdtnode v
00401 );
00402
00403
00413 bool
00414 flow_is_consistent
00415 (
00416 );
00417
00418
00423 bool
00424 is_consistent
00425 (
00426 );
00427
00428
00429
00430
00431
00432
00433
00438 void
00439 clear
00440 (
00441 );
00442
00443
00448 void
00449 set_balance
00450 (
00451 gdtnode v,
00452 int b
00453 );
00454
00455
00460 void
00461 set_upper_capacity
00462 (
00463 gdtedge e,
00464 int uc
00465 );
00466
00467
00472 void
00473 set_lower_capacity
00474 (
00475 gdtedge e,
00476 int lc
00477 );
00478
00479
00484 void
00485 set_cost
00486 (
00487 gdtedge e,
00488 int c
00489 );
00490
00491
00496 void
00497 set_flow
00498 (
00499 gdtedge e,
00500 int f
00501 );
00502
00503
00509 void
00510 set_edge_info
00511 (
00512 gdtedge e,
00513 int uc,
00514 int lc,
00515 int c,
00516 int f
00517 );
00518
00519
00528 void
00529 steal_from
00530 (
00531 dire_graph& dg
00532 );
00533
00534
00539 void
00540 mirror
00541 (
00542 flow_dire_graph& fdg
00543 );
00544
00545
00550 void
00551 forget
00552 (
00553 );
00554
00555
00562 bool
00563 min_cost_flow
00564 (
00565 );
00566
00567 };
00568
00569 #endif