Analysis Software
Documentation for sPHENIX simulation software
|
Maximum flow algorithm (Malhotra, Kumar, Maheshwari). More...
#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/maxflow_pp.h>
Public Member Functions | |
maxflow_pp () | |
virtual | ~maxflow_pp () |
void | set_vars (const edge_map< double > &edge_capacity) |
void | set_vars (const edge_map< double > &edge_capacity, const node &net_source, const node &net_target) |
virtual int | check (graph &G) |
int | run (graph &G) |
double | get_max_flow (const edge &e) const |
double | get_max_flow () const |
double | get_rem_cap (const edge &e) const |
virtual void | reset () |
Public Member Functions inherited from algorithm | |
algorithm () | |
Creates an algorithm object. | |
virtual | ~algorithm () |
Destroys the algorithm object. | |
Protected Types | |
enum | { TARGET_FROM_SOURCE_REACHABLE = 2, TARGET_FROM_SOURCE_NOT_REACHABLE = 3 } |
Protected Member Functions | |
void | create_artif_source_target (graph &G) |
void | prepare_run (const graph &G) |
int | leveling (graph &G) |
void | hide_unreachable_nodes (graph &G) |
void | store_temp_unvisible_edges (const node &cur_node) |
void | min_throughput_node (const graph &G, node &min_tp_node, double &min_value) |
double | comp_min_throughput (const node cur_node) const |
void | get_sp_ahead (const graph &G, const node &start_node, node_map< edge > &last_edge) |
void | get_sp_backwards (const graph &G, const node &start_node, node_map< edge > &prev_edge) |
void | push (graph &G, const node &start_node, const double flow_value) |
void | pull (graph &G, const node &start_node, const double flow_value) |
void | comp_rem_net (graph &G) |
void | single_edge_update (graph &G, edge cur_edge) |
double | extra_charge_ahead (const node &start_node, const node_map< edge > &last_edge) const |
double | extra_charge_backwards (const node &start_node, const node_map< edge > &prev_edge) const |
void | create_back_edge (graph &G, const edge &org_edge) |
void | comp_max_flow (const graph &G) |
void | restore_graph (graph &G) |
Protected Attributes | |
bool | artif_source_target |
bool | set_vars_executed |
double | max_graph_flow |
node | net_source |
node | net_target |
list< edge > | edges_not_org |
edge_map< bool > | edge_org |
edge_map< bool > | back_edge_exists |
edge_map< edge > | back_edge |
edge_map< double > | edge_capacity |
edge_map< double > | edge_max_flow |
edge_map< double > | flow_update |
list< edge > | full_edges |
list< node > | temp_unvisible_nodes |
list< edge > | temp_unvisible_edges |
Additional Inherited Members | |
Public Types inherited from algorithm | |
enum | { GTL_OK = 1, GTL_ERROR = 0 } |
Return values for algorithm::check and algorithm::run. More... | |
Maximum flow algorithm (Malhotra, Kumar, Maheshwari).
Definition at line 25 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 25 of file maxflow_pp.h
|
protected |
Definition at line 126 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 126 of file maxflow_pp.h
__GTL_BEGIN_NAMESPACE maxflow_pp::maxflow_pp | ( | ) |
Default constructor. Enables only the calculation of maximum flow.
Definition at line 28 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 28 of file maxflow_pp.cpp
References max_graph_flow, and set_vars_executed.
|
virtual |
Destructor.
Definition at line 35 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 35 of file maxflow_pp.cpp
|
virtual |
Checks whether following preconditions are satisfied:
G
is directed. G
is connected. G
has at least one edge and two nodes. G | graph |
algorithm::GTL_OK
on success algorithm::GTL_ERROR
otherwise Implements algorithm.
Definition at line 61 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 61 of file maxflow_pp.cpp
References artif_source_target, edge_capacity, graph::edges_begin(), graph::edges_end(), algorithm::GTL_ERROR, algorithm::GTL_OK, graph::is_connected(), graph::is_undirected(), net_source, net_target, graph::nodes_begin(), graph::nodes_end(), graph::number_of_nodes(), and set_vars_executed.
|
protected |
Definition at line 714 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 714 of file maxflow_pp.cpp
References edge_max_flow, max_graph_flow, net_source, node::out_edges_begin(), and node::out_edges_end().
Referenced by restore_graph().
Definition at line 374 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 374 of file maxflow_pp.cpp
References edge_capacity, edge_max_flow, node::in_edges_begin(), node::in_edges_end(), net_source, net_target, node::out_edges_begin(), and node::out_edges_end().
Referenced by min_throughput_node().
|
protected |
Definition at line 578 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 578 of file maxflow_pp.cpp
References back_edge, back_edge_exists, create_back_edge(), edge_capacity, edge_max_flow, graph::edges_begin(), graph::edges_end(), flow_update, full_edges, graph::hide_edge(), graph::restore_edge(), graph::restore_node(), single_edge_update(), temp_unvisible_edges, and temp_unvisible_nodes.
Referenced by run().
|
protected |
Definition at line 164 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 164 of file maxflow_pp.cpp
References Acts::UnitConstants::e, edge_capacity, node::indeg(), net_source, net_target, graph::new_edge(), graph::new_node(), graph::nodes_begin(), graph::nodes_end(), and node::outdeg().
Referenced by run().
Definition at line 699 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 699 of file maxflow_pp.cpp
References back_edge, back_edge_exists, edge_capacity, edge_max_flow, edge_org, edges_not_org, flow_update, graph::new_edge(), edge::source(), and edge::target().
Referenced by comp_rem_net(), and single_edge_update().
|
protected |
Definition at line 660 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 660 of file maxflow_pp.cpp
References edge_capacity, edge_max_flow, and net_target.
Referenced by push().
|
protected |
Definition at line 680 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 680 of file maxflow_pp.cpp
References edge_capacity, edge_max_flow, and net_source.
Referenced by pull().
Returns the maximum flow of an edge.
e | edge of a graph G |
Definition at line 141 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 141 of file maxflow_pp.cpp
References edge_max_flow.
double maxflow_pp::get_max_flow | ( | ) | const |
Returns the maximum flow of the whole graph G
.
Definition at line 147 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 147 of file maxflow_pp.cpp
References max_graph_flow.
Returns the remaining free capacity of an edge.
e | edge of a graph G |
Definition at line 153 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 153 of file maxflow_pp.cpp
References edge_capacity, and edge_max_flow.
|
protected |
Definition at line 404 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 404 of file maxflow_pp.cpp
References net_target, next, node::out_edges_begin(), and node::out_edges_end().
Referenced by push().
|
protected |
Definition at line 439 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 439 of file maxflow_pp.cpp
References node::in_edges_begin(), node::in_edges_end(), net_source, and next.
Referenced by pull().
|
protected |
Definition at line 265 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 265 of file maxflow_pp.cpp
References graph::hide_node(), node::in_edges_begin(), node::in_edges_end(), net_source, net_target, next, graph::nodes_begin(), graph::nodes_end(), node::out_edges_begin(), node::out_edges_end(), store_temp_unvisible_edges(), and temp_unvisible_nodes.
Referenced by run().
|
protected |
Definition at line 215 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 215 of file maxflow_pp.cpp
References graph::hide_edge(), physmon_simulation::level, net_source, net_target, node::out_edges_begin(), node::out_edges_end(), TARGET_FROM_SOURCE_NOT_REACHABLE, TARGET_FROM_SOURCE_REACHABLE, and temp_unvisible_edges.
Referenced by run().
|
protected |
Definition at line 352 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 352 of file maxflow_pp.cpp
References comp_min_throughput(), net_source, graph::nodes_begin(), and graph::nodes_end().
Referenced by run().
|
protected |
Definition at line 202 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 202 of file maxflow_pp.cpp
References back_edge_exists, edge_max_flow, edge_org, flow_update, full_edges, ne_map< Key, Value, Graph, Alloc >::init(), max_graph_flow, temp_unvisible_edges, and temp_unvisible_nodes.
Referenced by run().
Definition at line 526 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 526 of file maxflow_pp.cpp
References back_edge, back_edge_exists, Acts::UnitConstants::e, edge_capacity, edge_max_flow, edge_org, extra_charge_backwards(), flow_update, full_edges, get_sp_backwards(), graph::hide_edge(), and net_source.
Referenced by run().
Definition at line 474 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 474 of file maxflow_pp.cpp
References back_edge, back_edge_exists, Acts::UnitConstants::e, edge_capacity, edge_max_flow, edge_org, extra_charge_ahead(), flow_update, full_edges, get_sp_ahead(), graph::hide_edge(), and net_target.
Referenced by run().
|
virtual |
Resets maximum flow algorithm, i.e. prepares the algorithm to be applied to another graph.
Implements algorithm.
Definition at line 159 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 159 of file maxflow_pp.cpp
|
protected |
Definition at line 728 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 728 of file maxflow_pp.cpp
References artif_source_target, comp_max_flow(), graph::del_edge(), graph::del_node(), edges_not_org, net_source, net_target, and graph::restore_graph().
Referenced by run().
|
virtual |
Computes maximum flow of graph G
.
G | graph |
algorithm::GTL_OK
on success algorithm::GTL_ERROR
otherwise Implements algorithm.
Definition at line 116 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 116 of file maxflow_pp.cpp
References artif_source_target, comp_rem_net(), create_artif_source_target(), algorithm::GTL_OK, hide_unreachable_nodes(), leveling(), min_throughput_node(), prepare_run(), pull(), push(), restore_graph(), and TARGET_FROM_SOURCE_REACHABLE.
Sets capacity of every edge for maximum flow calculation where artificial start-node and end_node will be computed automatically.
edge_capacity | capacity of every edge |
Definition at line 40 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 40 of file maxflow_pp.cpp
References artif_source_target, edge_capacity, max_graph_flow, and set_vars_executed.
void maxflow_pp::set_vars | ( | const edge_map< double > & | edge_capacity, |
const node & | net_source, | ||
const node & | net_target | ||
) |
Sets capacity of every edge for maximum flow calculation
edge_capacity | capacity of every edge |
net_source | start-node |
net_target | end-node |
Definition at line 49 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 49 of file maxflow_pp.cpp
References artif_source_target, edge_capacity, max_graph_flow, net_source, net_target, and set_vars_executed.
Definition at line 637 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 637 of file maxflow_pp.cpp
References back_edge, back_edge_exists, create_back_edge(), edge_capacity, edge_max_flow, edge_org, and flow_update.
Referenced by comp_rem_net().
|
protected |
Definition at line 333 of file maxflow_pp.cpp.
View newest version in sPHENIX GitHub at line 333 of file maxflow_pp.cpp
References node::in_edges_begin(), node::in_edges_end(), node::out_edges_begin(), node::out_edges_end(), and temp_unvisible_edges.
Referenced by hide_unreachable_nodes().
|
protected |
Definition at line 131 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 131 of file maxflow_pp.h
Referenced by check(), restore_graph(), run(), and set_vars().
Definition at line 171 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 171 of file maxflow_pp.h
Referenced by comp_rem_net(), create_back_edge(), pull(), push(), and single_edge_update().
|
protected |
Definition at line 166 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 166 of file maxflow_pp.h
Referenced by comp_rem_net(), create_back_edge(), prepare_run(), pull(), push(), and single_edge_update().
Definition at line 176 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 176 of file maxflow_pp.h
Referenced by check(), comp_min_throughput(), comp_rem_net(), create_artif_source_target(), create_back_edge(), extra_charge_ahead(), extra_charge_backwards(), get_rem_cap(), pull(), push(), set_vars(), and single_edge_update().
Definition at line 181 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 181 of file maxflow_pp.h
Referenced by comp_max_flow(), comp_min_throughput(), comp_rem_net(), create_back_edge(), extra_charge_ahead(), extra_charge_backwards(), get_max_flow(), get_rem_cap(), prepare_run(), pull(), push(), and single_edge_update().
|
protected |
Definition at line 161 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 161 of file maxflow_pp.h
Referenced by create_back_edge(), prepare_run(), pull(), push(), and single_edge_update().
|
protected |
Definition at line 156 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 156 of file maxflow_pp.h
Referenced by create_back_edge(), and restore_graph().
Definition at line 186 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 186 of file maxflow_pp.h
Referenced by comp_rem_net(), create_back_edge(), prepare_run(), pull(), push(), and single_edge_update().
|
protected |
Definition at line 191 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 191 of file maxflow_pp.h
Referenced by comp_rem_net(), prepare_run(), pull(), and push().
|
protected |
Definition at line 141 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 141 of file maxflow_pp.h
Referenced by comp_max_flow(), get_max_flow(), maxflow_pp(), prepare_run(), and set_vars().
|
protected |
Definition at line 146 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 146 of file maxflow_pp.h
Referenced by check(), comp_max_flow(), comp_min_throughput(), create_artif_source_target(), extra_charge_backwards(), get_sp_backwards(), hide_unreachable_nodes(), leveling(), min_throughput_node(), pull(), restore_graph(), and set_vars().
|
protected |
Definition at line 151 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 151 of file maxflow_pp.h
Referenced by check(), comp_min_throughput(), create_artif_source_target(), extra_charge_ahead(), get_sp_ahead(), hide_unreachable_nodes(), leveling(), push(), restore_graph(), and set_vars().
|
protected |
Definition at line 136 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 136 of file maxflow_pp.h
Referenced by check(), maxflow_pp(), and set_vars().
|
protected |
Definition at line 201 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 201 of file maxflow_pp.h
Referenced by comp_rem_net(), leveling(), prepare_run(), and store_temp_unvisible_edges().
|
protected |
Definition at line 196 of file maxflow_pp.h.
View newest version in sPHENIX GitHub at line 196 of file maxflow_pp.h
Referenced by comp_rem_net(), hide_unreachable_nodes(), and prepare_run().