Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
maxflow_ff.cpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file maxflow_ff.cpp
1 /* This software is distributed under the GNU Lesser General Public License */
2 //==========================================================================
3 //
4 // maxflow_ff.cpp
5 //
6 //==========================================================================
7 // $Id: maxflow_ff.cpp,v 1.7 2001/11/07 13:58:10 pick Exp $
8 
9 #include <GTL/maxflow_ff.h>
10 
11 #include <cstdlib>
12 #include <iostream>
13 #include <cassert>
14 
15 #ifdef __GTL_MSVCC
16 # ifdef _DEBUG
17 # ifndef SEARCH_MEMORY_LEAKS_ENABLED
18 # error SEARCH NOT ENABLED
19 # endif
20 # define new DEBUG_NEW
21 # undef THIS_FILE
22  static char THIS_FILE[] = __FILE__;
23 # endif // _DEBUG
24 #endif // __GTL_MSVCC
25 
27 
29 {
30  max_graph_flow = 0.0;
31  set_vars_executed = false;
32 }
33 
34 
36 {
37 }
38 
39 
40 void maxflow_ff::set_vars(const edge_map<double>& edge_capacity)
41 {
42  this->edge_capacity = edge_capacity;
43  artif_source_target = true;
44  max_graph_flow = 0.0;
45  set_vars_executed = true;
46 }
47 
48 
49 void maxflow_ff::set_vars(const edge_map<double>& edge_capacity,
50  const node& net_source, const node& net_target)
51 {
52  this->edge_capacity = edge_capacity;
53  this->net_source = net_source;
54  this->net_target = net_target;
55  artif_source_target = false;
56  max_graph_flow = 0.0;
57  set_vars_executed = true;
58 }
59 
60 
62 {
63  if (!set_vars_executed)
64  {
65  return(GTL_ERROR);
66  }
67  graph::edge_iterator edge_it = G.edges_begin();
68  graph::edge_iterator edges_end = G.edges_end();
69  while (edge_it != edges_end)
70  {
71  if (edge_capacity[*edge_it] < 0)
72  {
73  return(GTL_ERROR);
74  }
75  ++edge_it;
76  }
77  // G.is_acyclic may be false
78  if ((G.number_of_nodes() <= 1) || (!G.is_connected()) || (G.is_undirected()))
79  {
80  return(GTL_ERROR);
81  }
83  {
84  bool source_found = false;
85  bool target_found = false;
86  graph::node_iterator node_it = G.nodes_begin();
87  graph::node_iterator nodes_end = G.nodes_end();
88  while (node_it != nodes_end)
89  {
90  if ((*node_it).indeg() == 0)
91  {
92  source_found = true;
93  }
94  if ((*node_it).outdeg() == 0)
95  {
96  target_found = true;
97  }
98  ++node_it;
99  }
100  if (!(source_found && target_found))
101  {
102  return(GTL_ERROR);
103  }
104  }
105  else
106  {
107  if (net_source == net_target)
108  {
109  return(GTL_ERROR);
110  }
111  }
112  return(GTL_OK); // ok
113 }
114 
115 
117 {
118  // init
120  {
122  }
123  prepare_run(G);
124 
125  node_map<edge> last_edge(G);
126 
127  while (get_sp(G, last_edge) == SP_FOUND)
128  {
129  comp_single_flow(G, last_edge);
130  }
131 
132  restore_graph(G);
133  return(GTL_OK);
134 }
135 
136 
137 double maxflow_ff::get_max_flow(const edge& e) const
138 {
139  return(edge_max_flow[e]);
140 }
141 
142 
144 {
145  return(max_graph_flow);
146 }
147 
148 
149 double maxflow_ff::get_rem_cap(const edge& e) const
150 {
151  return(edge_capacity[e] - edge_max_flow[e]);
152 }
153 
154 
156 {
157 }
158 
159 
161 {
162  net_source = G.new_node();
163  net_target = G.new_node();
164  edge e;
165  graph::node_iterator node_it = G.nodes_begin();
166  graph::node_iterator nodes_end = G.nodes_end();
167  while (node_it != nodes_end)
168  {
169  if (*node_it != net_source && (*node_it).indeg() == 0)
170  {
171  e = G.new_edge(net_source, *node_it);
172  edge_capacity[e] = 1.0; // 1.0 prevents e from hiding
173  node::out_edges_iterator out_edge_it = (*node_it).out_edges_begin();
174  node::out_edges_iterator out_edges_end = (*node_it).out_edges_end();
175  while (out_edge_it != out_edges_end)
176  {
177  edge_capacity[e] += edge_capacity[*out_edge_it];
178  ++out_edge_it;
179  }
180  }
181  if (*node_it != net_target && (*node_it).outdeg() == 0)
182  {
183  e = G.new_edge(*node_it, net_target);
184  edge_capacity[e] = 1.0; // 1.0 prevents e from hiding
185  node::in_edges_iterator in_edge_it = (*node_it).in_edges_begin();
186  node::in_edges_iterator in_edges_end = (*node_it).in_edges_end();
187  while (in_edge_it != in_edges_end)
188  {
189  edge_capacity[e] += edge_capacity[*in_edge_it];
190  ++in_edge_it;
191  }
192  }
193  ++node_it;
194  }
195 }
196 
197 
199 {
200  edge_max_flow.init(G, 0.0);
201  edge_org.init(G, true);
202  back_edge_exists.init(G, false);
203  max_graph_flow = 0.0;
204 }
205 
206 
208 {
209  double min_value = extra_charge(last_edge);
210 
211  node cur_node = net_target;
212  do
213  {
214  if (edge_org[last_edge[cur_node]]) // shortest path runs over a org. edge
215  {
216  if (!back_edge_exists[last_edge[cur_node]]) // create back edge
217  {
218  create_back_edge(G, last_edge[cur_node]);
219  }
220  edge_max_flow[last_edge[cur_node]] += min_value;
221  G.restore_edge(back_edge[last_edge[cur_node]]);
222  edge_capacity[back_edge[last_edge[cur_node]]] += min_value;
223  }
224  else // shortest path runs over a inserted back edge
225  {
226  edge oe = back_edge[last_edge[cur_node]];
227  G.restore_edge(oe);
228  edge_max_flow[oe] -= min_value;
229  edge_capacity[last_edge[cur_node]] -= min_value;
230  }
231  if (edge_capacity[last_edge[cur_node]] <= edge_max_flow[last_edge[cur_node]])
232  {
233  G.hide_edge(last_edge[cur_node]);
234  }
235  cur_node = last_edge[cur_node].source();
236  }
237  while (cur_node != net_source);
238 }
239 
240 
241 int maxflow_ff::get_sp(const graph& G, node_map<edge>& last_edge)
242 {
243  queue<node> next_nodes;
244  node_map<bool> visited(G, false);
245  next_nodes.push(net_source);
246  visited[net_source] = true;
247 
248  if (comp_sp(G, next_nodes, visited, last_edge) == SP_FOUND)
249  {
250  return(SP_FOUND);
251  }
252  else
253  {
254  return(NO_SP_FOUND);
255  }
256 }
257 
258 
259 int maxflow_ff::comp_sp(const graph& G, queue<node>& next_nodes,
260  node_map<bool>& visited, node_map<edge>& last_edge)
261 {
262  node cur_node;
263 
264  while (!next_nodes.empty())
265  {
266  cur_node = next_nodes.front();
267  next_nodes.pop();
268 
269  node::out_edges_iterator out_edge_it = cur_node.out_edges_begin();
270  node::out_edges_iterator out_edges_end = cur_node.out_edges_end();
271  while (out_edge_it != out_edges_end)
272  {
273  node next = (*out_edge_it).target();
274  if (!visited[next])
275  {
276  last_edge[next] = *out_edge_it;
277  if (next == net_target)
278  {
279  return(SP_FOUND);
280  }
281  else
282  {
283  next_nodes.push(next);
284  visited[next] = true;
285  }
286  }
287  ++out_edge_it;
288  }
289  }
290  return(NO_SP_FOUND);
291 }
292 
293 
294 double maxflow_ff::extra_charge(const node_map<edge>& last_edge) const
295 {
296  node cur_node = net_target;
297  double min_value =
298  edge_capacity[last_edge[cur_node]] - edge_max_flow[last_edge[cur_node]];
299  double cur_capacity;
300 
301  do
302  {
303  cur_capacity =
304  edge_capacity[last_edge[cur_node]] - edge_max_flow[last_edge[cur_node]];
305 
306  if (cur_capacity < min_value) min_value = cur_capacity;
307  cur_node = last_edge[cur_node].source();
308  }
309  while (cur_node != net_source);
310  return(min_value);
311 }
312 
313 
314 void maxflow_ff::create_back_edge(graph& G, const edge& org_edge)
315 {
316  edge be = G.new_edge(org_edge.target(), org_edge.source());
317  edge_org[be] = false;
318  edges_not_org.push_back(be);
319  back_edge[org_edge] = be;
320  back_edge[be] = org_edge;
321  edge_max_flow[be] = 0.0;
322  edge_capacity[be] = 0.0;
323  back_edge_exists[org_edge] = true;
324  back_edge_exists[be] = true; // a back edge always has a org. edge ;-)
325 }
326 
327 
329 {
330  max_graph_flow = 0.0;
331 
334  while (out_edge_it != out_edges_end)
335  {
336  max_graph_flow += edge_max_flow[*out_edge_it];
337  ++out_edge_it;
338  }
339 }
340 
341 
343 {
344  G.restore_graph(); // hidden edges can not be deleted!
345  while (!edges_not_org.empty())
346  {
347  G.del_edge(edges_not_org.front());
348  edges_not_org.pop_front();
349  }
350  comp_max_flow(G);
352  {
353  G.del_node(net_source);
354  G.del_node(net_target);
355  }
356 }
357 
359 
360 //--------------------------------------------------------------------------
361 // end of file
362 //--------------------------------------------------------------------------