Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
maxflow_ff.h
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file maxflow_ff.h
1 /* This software is distributed under the GNU Lesser General Public License */
2 //==========================================================================
3 //
4 // maxflow_ff.h
5 //
6 //==========================================================================
7 // $Id: maxflow_ff.h,v 1.5 2003/01/31 08:15:05 chris Exp $
8 
9 #ifndef GTL_MAXFLOW_FF_H
10 #define GTL_MAXFLOW_FF_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 
26 {
27 public:
34  maxflow_ff();
35 
41  virtual ~maxflow_ff();
42 
50  void set_vars(const edge_map<double>& edge_capacity);
51 
59  void set_vars(
60  const edge_map<double>& edge_capacity,
61  const node& net_source,
62  const node& net_target);
63 
81  virtual int check(graph& G);
82 
91  int run(graph& G);
92 
99  double get_max_flow(const edge& e) const;
100 
106  double get_max_flow() const;
107 
114  double get_rem_cap(const edge& e) const;
115 
122  virtual void reset();
123 protected:
127  enum {SP_FOUND = 2, NO_SP_FOUND = 3};
128 
133 
138 
143 
148 
153 
157  list<edge> edges_not_org;
158 
163 
168 
173 
178 
183 
187  void create_artif_source_target(graph& G);
188 
192  void prepare_run(const graph& G);
193 
197  void comp_single_flow(graph& G, node_map<edge>& last_edge);
198 
202  int get_sp(const graph& G, node_map<edge>& last_edge);
203 
207  int comp_sp(
208  const graph& G,
209  queue<node>& next_nodes,
210  node_map<bool>& visited,
211  node_map<edge>& last_edge);
212 
216  double extra_charge(const node_map<edge>& last_edge) const;
217 
221  void create_back_edge(graph& G, const edge& org_edge);
222 
226  void comp_max_flow(const graph& G);
227 
231  void restore_graph(graph& G);
232 };
233 
235 
236 #endif // GTL_MAXFLOW_FF_H
237 
238 //--------------------------------------------------------------------------
239 // end of file
240 //--------------------------------------------------------------------------