Analysis Software
Documentation for
sPHENIX
simulation software
Home page
Related Pages
Modules
Namespaces
Classes
Files
Examples
External Links
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Groups
Pages
maxflow_sap.h
Go to the documentation of this file.
Or view
the newest version in sPHENIX GitHub for file maxflow_sap.h
1
/* This software is distributed under the GNU Lesser General Public License */
2
//==========================================================================
3
//
4
// maxflow_sap.h
5
//
6
//==========================================================================
7
// $Id: maxflow_sap.h,v 1.4 2003/01/31 08:15:05 chris Exp $
8
9
#ifndef GTL_MAXFLOW_SAP_H
10
#define GTL_MAXFLOW_SAP_H
11
12
#include <
GTL/GTL.h
>
13
#include <
GTL/graph.h
>
14
#include <
GTL/node_map.h
>
15
#include <
GTL/edge_map.h
>
16
#include <
GTL/algorithm.h
>
17
18
#include <queue>
19
20
__GTL_BEGIN_NAMESPACE
21
34
class
GTL_EXTERN
maxflow_sap
:
public
algorithm
35
{
36
public
:
43
maxflow_sap
();
44
50
virtual
~
maxflow_sap
();
51
59
void
set_vars(
const
edge_map<double>
& edge_capacity);
60
68
void
set_vars(
const
edge_map<double>
& edge_capacity,
69
const
node
& net_source,
70
const
node
& net_target);
71
89
virtual
int
check
(
graph
&
G
);
90
99
int
run
(
graph
& G);
100
107
double
get_max_flow(
const
edge
&
e
)
const
;
108
114
double
get_max_flow()
const
;
115
122
double
get_rem_cap(
const
edge
& e)
const
;
123
130
virtual
void
reset
();
131
protected
:
135
enum
{AP_FOUND = 2, NO_AP_FOUND = 3};
136
140
bool
artif_source_target
;
141
145
bool
set_vars_executed
;
146
150
double
max_graph_flow
;
151
155
node
net_source
;
156
160
node
net_target
;
161
165
list<edge>
edges_not_org
;
166
170
node_map<int>
dist_label
;
171
175
edge_map<bool>
edge_org
;
176
180
edge_map<bool>
back_edge_exists
;
181
185
edge_map<edge>
back_edge
;
186
190
edge_map<double>
edge_capacity
;
191
195
edge_map<double>
edge_max_flow
;
196
200
void
create_artif_source_target(
graph
& G);
201
205
void
prepare_run(
const
graph
& G);
206
210
void
comp_dist_labels(
const
graph
& G, vector<int>& numb);
211
215
bool
has_an_admissible_arc(
const
node
cur_node);
216
220
void
advance(
node
& cur_node,
node_map<edge>
& last_edge);
221
225
void
augment(
graph
& G,
const
node_map<edge>
& last_edge);
226
230
bool
retreat(
const
int
number_of_nodes,
231
node
& cur_node,
232
const
node_map<edge>
& last_edge,
233
vector<int>& numb);
234
238
int
min_neighbour_label(
const
int
number_of_nodes,
239
const
node
cur_node)
const
;
240
244
double
free_capacity(
const
node_map<edge>
& last_edge)
const
;
245
249
void
create_back_edge(
graph
& G,
const
edge
& org_edge);
250
254
void
comp_max_flow(
const
graph
& G);
255
259
void
restore_graph(
graph
& G);
260
};
261
262
__GTL_END_NAMESPACE
263
264
#endif // GTL_MAXFLOW_SAP_H
265
266
//--------------------------------------------------------------------------
267
// end of file
268
//--------------------------------------------------------------------------
JETSCAPE
blob
main
external_packages
gtl
include
GTL
maxflow_sap.h
Built by
Jin Huang
. updated:
Sat Feb 17 2024 22:18:23
using
1.8.2 with
sPHENIX GitHub integration