Maximum flow algorithm with shortest augmenting paths. More...

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

Inheritance diagram for maxflow_sap:

Collaboration diagram for maxflow_sap:

Public Member Functions
	maxflow_sap ()

virtual	~maxflow_sap ()

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	{ AP_FOUND = 2, NO_AP_FOUND = 3 }

Protected Member Functions
void	create_artif_source_target (graph &G)

void	prepare_run (const graph &G)

void	comp_dist_labels (const graph &G, vector< int > &numb)

bool	has_an_admissible_arc (const node cur_node)

void	advance (node &cur_node, node_map< edge > &last_edge)

void	augment (graph &G, const node_map< edge > &last_edge)

bool	retreat (const int number_of_nodes, node &cur_node, const node_map< edge > &last_edge, vector< int > &numb)

int	min_neighbour_label (const int number_of_nodes, const node cur_node) const

double	free_capacity (const node_map< edge > &last_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

node_map< int >	dist_label

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

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 with shortest augmenting paths.

This class implements a maximum flow algorithm with shortest augmenting paths due to Ahuja and Orlin.

In the case V is the set of vertices and E is the set of edges of the graph, the algorithm needs O(|V| * |V| * |E|) time to proceed.

See Also: maxflow_ff; maxflow_pp

Definition at line 34 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 34 of file maxflow_sap.h

Member Enumeration Documentation

anonymous enum

protected

Enumerator:

AP_FOUND
NO_AP_FOUND

Definition at line 135 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 135 of file maxflow_sap.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE maxflow_sap::maxflow_sap ( )

Default constructor. Enables only the calculation of maximum flow.

See Also: algorithm::algorithm

Definition at line 27 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 27 of file maxflow_sap.cpp

References max_graph_flow, and set_vars_executed.

maxflow_sap::~maxflow_sap ( )

virtual

Destructor.

See Also: algorithm::~algorithm

Definition at line 34 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 34 of file maxflow_sap.cpp

Member Function Documentation

void maxflow_sap::advance	(	node &	cur_node,
		node_map< edge > &	last_edge
	)

protected

Definition at line 279 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 279 of file maxflow_sap.cpp

References dist_label, node::out_edges_begin(), and node::out_edges_end().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void maxflow_sap::augment	(	graph &	G,
		const node_map< edge > &	last_edge
	)

protected

Definition at line 295 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 295 of file maxflow_sap.cpp

References back_edge, back_edge_exists, create_back_edge(), edge_capacity, edge_max_flow, edge_org, free_capacity(), graph::hide_edge(), net_source, net_target, and graph::restore_edge().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

int maxflow_sap::check ( graph & G )

virtual

Checks whether following preconditions are satisfied:

maxflow_sap::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

G graph

Returns: algorithm::GTL_OK on success algorithm::GTL_ERROR otherwise

See Also: algorithm::check

Implements algorithm.

Definition at line 60 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 60 of file maxflow_sap.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_sap::comp_dist_labels	(	const graph &	G,
		vector< int > &	numb
	)

protected

Definition at line 231 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 231 of file maxflow_sap.cpp

References dist_label, node::in_edges_begin(), node::in_edges_end(), net_target, and next.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void maxflow_sap::comp_max_flow ( const graph & G )

protected

Definition at line 414 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 414 of file maxflow_sap.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:

void maxflow_sap::create_artif_source_target ( graph & G )

protected

Definition at line 180 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 180 of file maxflow_sap.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_sap::create_back_edge	(	graph &	G,
		const edge &	org_edge
	)

protected

Definition at line 400 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 400 of file maxflow_sap.cpp

References back_edge, back_edge_exists, edge_capacity, edge_max_flow, edge_org, edges_not_org, graph::new_edge(), edge::source(), and edge::target().

Referenced by augment().

Here is the call graph for this function:

Here is the caller graph for this function:

double maxflow_sap::free_capacity ( const node_map< edge > & last_edge ) const

protected

Definition at line 375 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 375 of file maxflow_sap.cpp

References edge_capacity, edge_max_flow, net_source, and net_target.

Referenced by augment().

Here is the caller graph for this function:

double maxflow_sap::get_max_flow ( const edge & e ) const

Returns the maximum flow of an edge.

Parameters

e	edge of a graph `G`

Returns: maximum flow value

Definition at line 155 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 155 of file maxflow_sap.cpp

References edge_max_flow.

double maxflow_sap::get_max_flow ( ) const

Returns the maximum flow of the whole graph G.

Returns: maximum flow value

Definition at line 161 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 161 of file maxflow_sap.cpp

References max_graph_flow.

double maxflow_sap::get_rem_cap ( const edge & e ) const

Returns the remaining free capacity of an edge.

Parameters

e	edge of a graph `G`

Returns: remaining capacity

Definition at line 167 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 167 of file maxflow_sap.cpp

References edge_capacity, and edge_max_flow.

bool maxflow_sap::has_an_admissible_arc ( const node cur_node )

protected

Definition at line 263 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 263 of file maxflow_sap.cpp

References dist_label, node::out_edges_begin(), and node::out_edges_end().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

int maxflow_sap::min_neighbour_label	(	const int	number_of_nodes,
		const node	cur_node
	)		const

protected

Definition at line 356 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 356 of file maxflow_sap.cpp

References dist_label, node::out_edges_begin(), and node::out_edges_end().

Referenced by retreat().

Here is the call graph for this function:

Here is the caller graph for this function:

void maxflow_sap::prepare_run ( const graph & G )

protected

Definition at line 222 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 222 of file maxflow_sap.cpp

References back_edge_exists, edge_max_flow, edge_org, ne_map< Key, Value, Graph, Alloc >::init(), and max_graph_flow.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void maxflow_sap::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 173 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 173 of file maxflow_sap.cpp

References max_graph_flow, and set_vars_executed.

void maxflow_sap::restore_graph ( graph & G )

protected

Definition at line 428 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 428 of file maxflow_sap.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:

bool maxflow_sap::retreat	(	const int	number_of_nodes,
		node &	cur_node,
		const node_map< edge > &	last_edge,
		vector< int > &	numb
	)

protected

Definition at line 332 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 332 of file maxflow_sap.cpp

References dist_label, min_neighbour_label(), and net_source.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

int maxflow_sap::run ( graph & G )

virtual

Computes maximum flow of graph G.

Parameters

G graph

Returns: algorithm::GTL_OK on success algorithm::GTL_ERROR otherwise

See Also: algorithm::run

Implements algorithm.

Definition at line 116 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 116 of file maxflow_sap.cpp

References advance(), artif_source_target, augment(), comp_dist_labels(), create_artif_source_target(), go_on, algorithm::GTL_OK, has_an_admissible_arc(), net_source, net_target, graph::number_of_nodes(), prepare_run(), restore_graph(), and retreat().

Here is the call graph for this function:

void maxflow_sap::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_capacity capacity of every edge

Definition at line 39 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 39 of file maxflow_sap.cpp

References artif_source_target, edge_capacity, max_graph_flow, and set_vars_executed.

void maxflow_sap::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_capacity	capacity of every edge
net_source	start-node
net_target	end-node

Definition at line 48 of file maxflow_sap.cpp.

View newest version in sPHENIX GitHub at line 48 of file maxflow_sap.cpp

References artif_source_target, edge_capacity, max_graph_flow, net_source, net_target, and set_vars_executed.

Member Data Documentation

bool maxflow_sap::artif_source_target

protected

Definition at line 140 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 140 of file maxflow_sap.h

Referenced by check(), restore_graph(), run(), and set_vars().

edge_map<edge> maxflow_sap::back_edge

protected

Definition at line 185 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 185 of file maxflow_sap.h

Referenced by augment(), and create_back_edge().

edge_map<bool> maxflow_sap::back_edge_exists

protected

Definition at line 180 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 180 of file maxflow_sap.h

Referenced by augment(), create_back_edge(), and prepare_run().

node_map<int> maxflow_sap::dist_label

protected

Definition at line 170 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 170 of file maxflow_sap.h

Referenced by advance(), comp_dist_labels(), has_an_admissible_arc(), min_neighbour_label(), and retreat().

edge_map<double> maxflow_sap::edge_capacity

protected

Definition at line 190 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 190 of file maxflow_sap.h

Referenced by augment(), check(), create_artif_source_target(), create_back_edge(), free_capacity(), get_rem_cap(), and set_vars().

edge_map<double> maxflow_sap::edge_max_flow

protected

Definition at line 195 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 195 of file maxflow_sap.h

Referenced by augment(), comp_max_flow(), create_back_edge(), free_capacity(), get_max_flow(), get_rem_cap(), and prepare_run().

edge_map<bool> maxflow_sap::edge_org

protected

Definition at line 175 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 175 of file maxflow_sap.h

Referenced by augment(), create_back_edge(), and prepare_run().

list<edge> maxflow_sap::edges_not_org

protected

Definition at line 165 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 165 of file maxflow_sap.h

Referenced by create_back_edge(), and restore_graph().

double maxflow_sap::max_graph_flow

protected

Definition at line 150 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 150 of file maxflow_sap.h

Referenced by comp_max_flow(), get_max_flow(), maxflow_sap(), prepare_run(), reset(), and set_vars().

node maxflow_sap::net_source

protected

Definition at line 155 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 155 of file maxflow_sap.h

Referenced by augment(), check(), comp_max_flow(), create_artif_source_target(), free_capacity(), restore_graph(), retreat(), run(), and set_vars().

node maxflow_sap::net_target

protected

Definition at line 160 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 160 of file maxflow_sap.h

Referenced by augment(), check(), comp_dist_labels(), create_artif_source_target(), free_capacity(), restore_graph(), run(), and set_vars().

bool maxflow_sap::set_vars_executed

protected

Definition at line 145 of file maxflow_sap.h.

View newest version in sPHENIX GitHub at line 145 of file maxflow_sap.h

Referenced by check(), maxflow_sap(), reset(), and set_vars().

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

JETSCAPE/blob/main/external_packages/gtl/include/GTL/maxflow_sap.h
JETSCAPE/blob/main/external_packages/gtl/src/maxflow_sap.cpp

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation