Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
maxflow_pp Class Reference

Maximum flow algorithm (Malhotra, Kumar, Maheshwari). More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/maxflow_pp.h>

+ Inheritance diagram for maxflow_pp:
+ Collaboration diagram for maxflow_pp:

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< edgeedges_not_org
 
edge_map< bool > edge_org
 
edge_map< bool > back_edge_exists
 
edge_map< edgeback_edge
 
edge_map< doubleedge_capacity
 
edge_map< doubleedge_max_flow
 
edge_map< doubleflow_update
 
list< edgefull_edges
 
list< nodetemp_unvisible_nodes
 
list< edgetemp_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...
 

Detailed Description

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

Member Enumeration Documentation

anonymous enum
protected
Enumerator:
TARGET_FROM_SOURCE_REACHABLE 
TARGET_FROM_SOURCE_NOT_REACHABLE 

Definition at line 126 of file maxflow_pp.h.

View newest version in sPHENIX GitHub at line 126 of file maxflow_pp.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE maxflow_pp::maxflow_pp ( )

Default constructor. Enables only the calculation of maximum flow.

See Also
algorithm::algorithm

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.

maxflow_pp::~maxflow_pp ( )
virtual

Destructor.

See Also
algorithm::~algorithm

Definition at line 35 of file maxflow_pp.cpp.

View newest version in sPHENIX GitHub at line 35 of file maxflow_pp.cpp

Member Function Documentation

int maxflow_pp::check ( graph G)
virtual

Checks whether following preconditions are satisfied:

  • maxflow_pp::set_vars has been executed before.
  • only edge_capacities >= 0 are applied.
  • G is directed.
  • G is connected.
  • G has at least one edge and two nodes.
  • if not applied, start-nodes and end-nodes exists.
  • if applied, start-node is not the same node as end-node.
Parameters
Ggraph
Returns
algorithm::GTL_OK on success algorithm::GTL_ERROR otherwise
See Also
algorithm::check

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.

+ Here is the call graph for this function:

void maxflow_pp::comp_max_flow ( const graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

double maxflow_pp::comp_min_throughput ( const node  cur_node) const
protected

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::comp_rem_net ( graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::create_artif_source_target ( graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::create_back_edge ( graph G,
const edge org_edge 
)
protected

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

double maxflow_pp::extra_charge_ahead ( const node start_node,
const node_map< edge > &  last_edge 
) const
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().

+ Here is the caller graph for this function:

double maxflow_pp::extra_charge_backwards ( const node start_node,
const node_map< edge > &  prev_edge 
) const
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().

+ Here is the caller graph for this function:

double maxflow_pp::get_max_flow ( const edge e) const

Returns the maximum flow of an edge.

Parameters
eedge of a graph G
Returns
maximum flow value

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.

Returns
maximum flow value

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.

double maxflow_pp::get_rem_cap ( const edge e) const

Returns the remaining free capacity of an edge.

Parameters
eedge of a graph G
Returns
remaining capacity

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.

void maxflow_pp::get_sp_ahead ( const graph G,
const node start_node,
node_map< edge > &  last_edge 
)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::get_sp_backwards ( const graph G,
const node start_node,
node_map< edge > &  prev_edge 
)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::hide_unreachable_nodes ( graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int maxflow_pp::leveling ( graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::min_throughput_node ( const graph G,
node min_tp_node,
double min_value 
)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::prepare_run ( const graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::pull ( graph G,
const node start_node,
const double  flow_value 
)
protected

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::push ( graph G,
const node start_node,
const double  flow_value 
)
protected

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::reset ( )
virtual

Resets maximum flow algorithm, i.e. prepares the algorithm to be applied to another graph.

See Also
algorithm::reset

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

void maxflow_pp::restore_graph ( graph G)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int maxflow_pp::run ( graph G)
virtual

Computes maximum flow of graph G.

Parameters
Ggraph
Returns
algorithm::GTL_OK on success algorithm::GTL_ERROR otherwise
See Also
algorithm::run

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.

+ Here is the call graph for this function:

void maxflow_pp::set_vars ( const edge_map< double > &  edge_capacity)

Sets capacity of every edge for maximum flow calculation where artificial start-node and end_node will be computed automatically.

Parameters
edge_capacitycapacity 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

Parameters
edge_capacitycapacity of every edge
net_sourcestart-node
net_targetend-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.

void maxflow_pp::single_edge_update ( graph G,
edge  cur_edge 
)
protected

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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void maxflow_pp::store_temp_unvisible_edges ( const node cur_node)
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().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

bool maxflow_pp::artif_source_target
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().

edge_map<edge> maxflow_pp::back_edge
protected

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().

edge_map<bool> maxflow_pp::back_edge_exists
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().

edge_map<double> maxflow_pp::edge_capacity
protected
edge_map<double> maxflow_pp::edge_max_flow
protected
edge_map<bool> maxflow_pp::edge_org
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().

list<edge> maxflow_pp::edges_not_org
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().

edge_map<double> maxflow_pp::flow_update
protected

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().

list<edge> maxflow_pp::full_edges
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().

double maxflow_pp::max_graph_flow
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().

node maxflow_pp::net_source
protected
node maxflow_pp::net_target
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().

bool maxflow_pp::set_vars_executed
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().

list<edge> maxflow_pp::temp_unvisible_edges
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().

list<node> maxflow_pp::temp_unvisible_nodes
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().


The documentation for this class was generated from the following files: