Analysis Software
Documentation for sPHENIX simulation software
 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 
21 
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 
141 
146 
151 
156 
161 
165  list<edge> edges_not_org;
166 
171 
176 
181 
186 
191 
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 
263 
264 #endif // GTL_MAXFLOW_SAP_H
265 
266 //--------------------------------------------------------------------------
267 // end of file
268 //--------------------------------------------------------------------------