Heuristic graph bi-partitioning algorithm (Wei-Cheng). More...

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

Inheritance diagram for ratio_cut_partition:

Collaboration diagram for ratio_cut_partition:

Public Types
typedef int	side_type

typedef short int	fix_type

typedef list< edge > ::const_iterator	cut_edges_iterator

typedef list< node > ::const_iterator	nodes_of_one_side_iterator

Public Types inherited from algorithm
enum	{ GTL_OK = 1, GTL_ERROR = 0 }
	Return values for algorithm::check and algorithm::run. More...

Public Member Functions
	ratio_cut_partition ()

virtual	~ratio_cut_partition ()

void	set_vars (const graph &G, const node_map< int > &node_weight, const edge_map< int > &edge_weight)

void	set_vars (const graph &G, const node_map< int > &node_weight, const edge_map< int > &edge_weight, const node source_node, const node target_node)

void	set_vars (const graph &G, const node_map< int > &node_weight, const edge_map< int > &edge_weight, const node source_node, const node target_node, const node_map< side_type > &init_side)

void	set_vars (const graph &G, const node_map< int > &node_weight, const edge_map< int > &edge_weight, const node source_node, const node target_node, const node_map< fix_type > &fixed)

void	set_vars (const graph &G, const node_map< int > &node_weight, const edge_map< int > &edge_weight, const node source_node, const node target_node, const node_map< side_type > &init_side, const node_map< fix_type > &fixed)

void	store_cut_edges (const bool set)

void	store_nodesAB (const bool set)

virtual int	check (graph &G)

int	run (graph &G)

int	get_cutsize ()

double	get_cutratio ()

side_type	get_side_of_node (const node &n) const

side_type	operator[] (const node &n) const

int	get_weight_on_sideA (const graph &G) const

int	get_weight_on_sideB (const graph &G) const

cut_edges_iterator	cut_edges_begin () const

cut_edges_iterator	cut_edges_end () const

nodes_of_one_side_iterator	nodes_of_sideA_begin () const

nodes_of_one_side_iterator	nodes_of_sideA_end () const

nodes_of_one_side_iterator	nodes_of_sideB_begin () const

nodes_of_one_side_iterator	nodes_of_sideB_end () const

virtual void	reset ()

Public Member Functions inherited from algorithm
	algorithm ()
	Creates an algorithm object.

virtual	~algorithm ()
	Destroys the algorithm object.

Static Public Attributes
static const side_type	A = 0

static const side_type	B = 1

static const fix_type	FIXA = 0

static const fix_type	FIXB = 1

static const fix_type	UNFIXED = 2

Protected Types
enum	direction_type { LEFT_SHIFT = 2, RIGHT_SHIFT = 3 }

Protected Member Functions
void	divide_up (const graph &G)

void	make_connected (graph &G, list< edge > &artificial_edges)

void	restore (graph &G, list< edge > &artificial_edges)

void	initialization (const graph &G)

void	init_data_structure (const graph &G)

void	init_filling_buckets (const graph &G)

int	inital_gain_of_node_on_sideA (const node cur_node)

int	inital_gain_of_node_on_sideB (const node cur_node)

void	init_variables (const graph &G)

void	compute_max_vertex_degree (const graph &G)

void	determine_source_node (const graph &G)

void	compute_target_node (const graph &G)

void	right_shift_op (const graph &G)

void	left_shift_op (const graph &G)

bool	move_vertex_A2B (const graph &G, node &moved_node)

bool	move_vertex_B2A (const graph &G, node &moved_node)

node	compute_highest_ratio_node (list< node > node_list)

double	cutratio ()

double	ratio_of_node_A2B (const node cur_node)

double	ratio_of_node_B2A (const node cur_node)

int	range_up (const int gain_value) const

int	range_down (const int index) const

void	update_data_structure_A2B (const node cur_node, const bool init_mode)

void	update_data_structure_B2A (const node cur_node, const bool init_mode)

void	update_bucketA (const node cur_node, const int old_gain, const int new_gain, const bool init_mode)

void	update_bucketB (const node cur_node, const int old_gain, const int new_gain, const bool init_mode)

void	update_max_gain (const side_type side)

void	clean_step (const graph &G)

void	copy_side_node_map (const graph &G, node_map< side_type > &dest, const node_map< side_type > source) const

void	iterative_shifting (const graph &G)

void	group_swapping (const graph &G)

bool	move_manager (const graph &G)

bool	move_vertex (const graph &G, node &moved_node)

void	compute_cut_edges (const graph &G)

void	compute_nodesAB (const graph &G)

Protected Attributes
bool	enable_cut_edges_storing

list< edge >	cut_edges

bool	enable_nodesAB_storing

list< node >	nodesA

list< node >	nodesB

node	source_node

node	target_node

bool	set_vars_executed

bool	provided_st

bool	provided_initial_part

bool	provided_fix

node_map< fix_type >	fixed

direction_type	direction

node_map< int >	node_weight

edge_map< int >	edge_weight

int	max_edge_weight

int	node_weight_on_sideA

int	node_weight_on_sideB

int	nodes_on_sideA

int	nodes_on_sideB

node_map< side_type >	side

node_map< list< node >::iterator >	position_in_bucket

int	max_vertex_degree

edge_map< int >	aside

edge_map< int >	bside

edge_map< list< node > >	unlockedA

edge_map< list< node > >	unlockedB

node_map< int >	gain_value

bool	bucketA_empty

bool	bucketB_empty

int	max_gainA

int	max_gainB

vector< list< node > >	bucketA

vector< list< node > >	bucketB

int	cur_cutsize

double	cur_cutratio

Detailed Description

Heuristic graph bi-partitioning algorithm (Wei-Cheng).

This class implements a heuristic graph bi-partitioning algorithm using the ratio cut method proposed by Y. C. Wei and C. K. Cheng in 1991.

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

See Also: fm_partition

Definition at line 32 of file ratio_cut_partition.h.

View newest version in sPHENIX GitHub at line 32 of file ratio_cut_partition.h

Member Typedef Documentation

typedef list<edge>::const_iterator ratio_cut_partition::cut_edges_iterator

Iterator type for edges which belong to the cut.

Definition at line 324 of file ratio_cut_partition.h.

View newest version in sPHENIX GitHub at line 324 of file ratio_cut_partition.h

typedef short int ratio_cut_partition::fix_type

Fix type of each node (needed with ratio_cut_partition::set_vars).

See Also: ratio_cut_partition::FIXA; ratio_cut_partition::FIXB; ratio_cut_partition::UNFIXED

Definition at line 65 of file ratio_cut_partition.h.

View newest version in sPHENIX GitHub at line 65 of file ratio_cut_partition.h

typedef list<node>::const_iterator ratio_cut_partition::nodes_of_one_side_iterator

Iterator type for nodes of a side.

Definition at line 349 of file ratio_cut_partition.h.

View newest version in sPHENIX GitHub at line 349 of file ratio_cut_partition.h

typedef int ratio_cut_partition::side_type

Return type of ratio_cut_partition::get_side_of_node.

See Also: ratio_cut_partition::A; ratio_cut_partition::B

Definition at line 41 of file ratio_cut_partition.h.

View newest version in sPHENIX GitHub at line 41 of file ratio_cut_partition.h

Member Enumeration Documentation

enum ratio_cut_partition::direction_type

protected

Enumerator:

LEFT_SHIFT
RIGHT_SHIFT

Definition at line 400 of file ratio_cut_partition.h.

View newest version in sPHENIX GitHub at line 400 of file ratio_cut_partition.h

Constructor & Destructor Documentation

ratio_cut_partition::ratio_cut_partition ( )

Default constructor.

See Also: algorithm::algorithm

Definition at line 44 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 44 of file ratio_cut_partition.cpp

References enable_cut_edges_storing, enable_nodesAB_storing, and set_vars_executed.

ratio_cut_partition::~ratio_cut_partition ( )

virtual

Destructor.

See Also: algorithm::~algorithm

Definition at line 52 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 52 of file ratio_cut_partition.cpp

Member Function Documentation

int ratio_cut_partition::check ( graph & G )

virtual

Checks whether following preconditions are satisfied:

One of the ratio_cut_partition::set_vars procedures has been executed before.
graph G is undirected.
if applied, source_node and target_node are 2 distinct nodes with node weights > 0.
only node_weights >= 0 are applied.
only edge_weights >= 0 are applied.
if G has more than 2 nodes, then at least two of them have a weight > 0.
if applied fixed source node, fixed[source_node] is FIXA.
if applied fixed target node, fixed[target_node] is FIXB.

Parameters

G graph

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

See Also: ratio_cut_partition::set_vars; algorithm::check

Implements algorithm.

Definition at line 154 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 154 of file ratio_cut_partition.cpp

References A, B, edge_weight, graph::edges_begin(), graph::edges_end(), FIXA, FIXB, fixed, algorithm::GTL_ERROR, algorithm::GTL_OK, graph::is_undirected(), node_weight, graph::nodes_begin(), graph::nodes_end(), graph::number_of_nodes(), provided_fix, provided_initial_part, provided_st, set_vars_executed, side, source_node, and target_node.

Here is the call graph for this function:

void ratio_cut_partition::clean_step ( const graph & G )

protected

Definition at line 1236 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1236 of file ratio_cut_partition.cpp

References bucketA, bucketB, ne_map< Key, Value, Graph, Alloc >::clear(), graph::edges_begin(), graph::edges_end(), i, max_edge_weight, max_vertex_degree, unlockedA, and unlockedB.

Referenced by group_swapping(), initialization(), iterative_shifting(), and run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::compute_cut_edges ( const graph & G )

protected

Definition at line 1499 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1499 of file ratio_cut_partition.cpp

References cut_edges, graph::edges_begin(), graph::edges_end(), and side.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

node ratio_cut_partition::compute_highest_ratio_node ( list< node > node_list )

protected

Definition at line 935 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 935 of file ratio_cut_partition.cpp

References A, ratio_of_node_A2B(), ratio_of_node_B2A(), and side.

Referenced by move_vertex(), move_vertex_A2B(), and move_vertex_B2A().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::compute_max_vertex_degree ( const graph & G )

protected

Definition at line 714 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 714 of file ratio_cut_partition.cpp

References max_vertex_degree, graph::nodes_begin(), and graph::nodes_end().

Referenced by init_variables().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::compute_nodesAB ( const graph & G )

protected

Definition at line 1515 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1515 of file ratio_cut_partition.cpp

References A, graph::nodes_begin(), graph::nodes_end(), nodesA, nodesB, and side.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::compute_target_node ( const graph & G )

protected

Definition at line 754 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 754 of file ratio_cut_partition.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), next, node_weight, graph::nodes_begin(), source_node, and target_node.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::copy_side_node_map	(	const graph &	G,
		node_map< side_type > &	dest,
		const node_map< side_type >	source
	)		const

protected

Definition at line 1259 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1259 of file ratio_cut_partition.cpp

References graph::nodes_begin(), and graph::nodes_end().

Referenced by initialization().

Here is the call graph for this function:

Here is the caller graph for this function:

ratio_cut_partition::cut_edges_iterator ratio_cut_partition::cut_edges_begin ( ) const

Iterate through all edges which belong to the cut, that means all edges with end-nodes on different sides. It is only valid if enabled with ratio_cut_partition::store_cut_edges before.

Returns: start for iteration through all cut edges

Definition at line 339 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 339 of file ratio_cut_partition.cpp

References cut_edges.

ratio_cut_partition::cut_edges_iterator ratio_cut_partition::cut_edges_end ( ) const

End-Iterator for iteration through all edges which belong to the cut. It is only valid if enabled with ratio_cut_partition::store_cut_edges before.

Returns: end for iteration through all cut-edges

Definition at line 346 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 346 of file ratio_cut_partition.cpp

References cut_edges.

double ratio_cut_partition::cutratio ( )

protected

Definition at line 971 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 971 of file ratio_cut_partition.cpp

References cur_cutsize, double(), node_weight_on_sideA, node_weight_on_sideB, nodes_on_sideA, and nodes_on_sideB.

Referenced by init_data_structure(), update_data_structure_A2B(), and update_data_structure_B2A().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::determine_source_node ( const graph & G )

protected

Definition at line 730 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 730 of file ratio_cut_partition.cpp

References i, node_weight, graph::nodes_begin(), graph::number_of_nodes(), source_node, and Acts::Test::time.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::divide_up ( const graph & G )

protected

Definition at line 389 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 389 of file ratio_cut_partition.cpp

References A, B, FIXA, FIXB, fixed, graph::nodes_begin(), graph::nodes_end(), and side.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

double ratio_cut_partition::get_cutratio ( )

Gets the ratio of the cut after bi-partitioning as defined in [WeiChe91].

Returns: cutratio

Definition at line 284 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 284 of file ratio_cut_partition.cpp

References cur_cutratio.

int ratio_cut_partition::get_cutsize ( )

Gets the size of the cut after bi-partitioning.

Returns: cutsize

Definition at line 278 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 278 of file ratio_cut_partition.cpp

References cur_cutsize.

ratio_cut_partition::side_type ratio_cut_partition::get_side_of_node ( const node & n ) const

Gets side of the node after bi-partitioning.

Parameters

n	node of graph G

Returns: ratio_cut_partition::A if n lies on side A, ratio_cut_partition::B otherwise

Definition at line 291 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 291 of file ratio_cut_partition.cpp

References n, and side.

int ratio_cut_partition::get_weight_on_sideA ( const graph & G ) const

Gets the sum of all node weights from nodes on side A .

Parameters

G graph

Returns: node_weight_on_sideA

Definition at line 304 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 304 of file ratio_cut_partition.cpp

References A, node_weight, graph::nodes_begin(), graph::nodes_end(), and side.

Here is the call graph for this function:

int ratio_cut_partition::get_weight_on_sideB ( const graph & G ) const

Gets the sum of all node weights from nodes on side B .

Parameters

G graph

Returns: node_weight_on_sideB

Definition at line 321 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 321 of file ratio_cut_partition.cpp

References B, node_weight, graph::nodes_begin(), graph::nodes_end(), and side.

Here is the call graph for this function:

void ratio_cut_partition::group_swapping ( const graph & G )

protected

Definition at line 1330 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1330 of file ratio_cut_partition.cpp

References clean_step(), init_data_structure(), and move_manager().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::init_data_structure ( const graph & G )

protected

Definition at line 520 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 520 of file ratio_cut_partition.cpp

References A, aside, B, bside, bucketA, bucketB, cur_cutratio, cur_cutsize, cutratio(), edge_weight, graph::edges_begin(), graph::edges_end(), ne_map< Key, Value, Graph, Alloc >::init(), init_filling_buckets(), max_edge_weight, max_vertex_degree, side, unlockedA, and unlockedB.

Referenced by group_swapping(), initialization(), iterative_shifting(), and run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::init_filling_buckets ( const graph & G )

protected

Definition at line 576 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 576 of file ratio_cut_partition.cpp

References A, parse_cmake_options::begin, bucketA, bucketA_empty, bucketB, bucketB_empty, fixed, gain_value, index, ne_map< Key, Value, Graph, Alloc >::init(), inital_gain_of_node_on_sideA(), inital_gain_of_node_on_sideB(), max_gainA, max_gainB, node_weight, node_weight_on_sideA, node_weight_on_sideB, graph::nodes_begin(), graph::nodes_end(), nodes_on_sideA, nodes_on_sideB, position_in_bucket, range_up(), side, and UNFIXED.

Referenced by init_data_structure().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::init_variables ( const graph & G )

protected

Definition at line 691 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 691 of file ratio_cut_partition.cpp

References compute_max_vertex_degree(), edge_weight, graph::edges_begin(), graph::edges_end(), and max_edge_weight.

Referenced by initialization(), and run().

Here is the call graph for this function:

Here is the caller graph for this function:

int ratio_cut_partition::inital_gain_of_node_on_sideA ( const node cur_node )

protected

Definition at line 649 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 649 of file ratio_cut_partition.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), aside, bside, and edge_weight.

Referenced by init_filling_buckets().

Here is the call graph for this function:

Here is the caller graph for this function:

int ratio_cut_partition::inital_gain_of_node_on_sideB ( const node cur_node )

protected

Definition at line 670 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 670 of file ratio_cut_partition.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), aside, bside, and edge_weight.

Referenced by init_filling_buckets().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::initialization ( const graph & G )

protected

Definition at line 445 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 445 of file ratio_cut_partition.cpp

References A, B, bucketA, bucketB, clean_step(), copy_side_node_map(), cur_cutratio, cur_cutsize, direction, fixed, gain_value, init_data_structure(), init_variables(), LEFT_SHIFT, left_shift_op(), graph::nodes_begin(), graph::nodes_end(), position_in_bucket, range_up(), RIGHT_SHIFT, right_shift_op(), side, source_node, target_node, UNFIXED, and update_max_gain().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::iterative_shifting ( const graph & G )

protected

Definition at line 1272 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1272 of file ratio_cut_partition.cpp

References A, B, bucketA, bucketB, clean_step(), cur_cutratio, cur_cutsize, direction, fixed, gain_value, init_data_structure(), LEFT_SHIFT, left_shift_op(), position_in_bucket, range_up(), RIGHT_SHIFT, right_shift_op(), source_node, target_node, UNFIXED, and update_max_gain().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::left_shift_op ( const graph & G )

protected

Definition at line 849 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 849 of file ratio_cut_partition.cpp

References A, B, cur_cutratio, cur_cutsize, i, move_vertex_B2A(), node_weight_on_sideA, node_weight_on_sideB, graph::number_of_nodes(), and side.

Referenced by initialization(), and iterative_shifting().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::make_connected	(	graph &	G,
		list< edge > &	artificial_edges
	)

protected

Definition at line 408 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 408 of file ratio_cut_partition.cpp

References dfs::check(), edge_weight, graph::new_edge(), dfs::roots_begin(), dfs::roots_end(), dfs::run(), and dfs::scan_whole_graph().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

bool ratio_cut_partition::move_manager ( const graph & G )

protected

Definition at line 1344 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1344 of file ratio_cut_partition.cpp

References A, B, cur_cutratio, cur_cutsize, i, move_vertex(), node_weight_on_sideA, node_weight_on_sideB, graph::number_of_nodes(), and side.

Referenced by group_swapping().

Here is the call graph for this function:

Here is the caller graph for this function:

bool ratio_cut_partition::move_vertex	(	const graph &	G,
		node &	moved_node
	)

protected

Definition at line 1398 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1398 of file ratio_cut_partition.cpp

References A, B, bucketA, bucketA_empty, bucketB, bucketB_empty, compute_highest_ratio_node(), gain_value, max_gainA, max_gainB, node_weight, node_weight_on_sideA, node_weight_on_sideB, position_in_bucket, range_up(), ratio_of_node_A2B(), ratio_of_node_B2A(), update_data_structure_A2B(), update_data_structure_B2A(), and update_max_gain().

Referenced by move_manager().

Here is the call graph for this function:

Here is the caller graph for this function:

bool ratio_cut_partition::move_vertex_A2B	(	const graph &	G,
		node &	moved_node
	)

protected

Definition at line 897 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 897 of file ratio_cut_partition.cpp

References A, bucketA, bucketA_empty, compute_highest_ratio_node(), max_gainA, position_in_bucket, range_up(), update_data_structure_A2B(), and update_max_gain().

Referenced by right_shift_op().

Here is the call graph for this function:

Here is the caller graph for this function:

bool ratio_cut_partition::move_vertex_B2A	(	const graph &	G,
		node &	moved_node
	)

protected

Definition at line 916 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 916 of file ratio_cut_partition.cpp

References B, bucketB, bucketB_empty, compute_highest_ratio_node(), max_gainB, position_in_bucket, range_up(), update_data_structure_B2A(), and update_max_gain().

Referenced by left_shift_op().

Here is the call graph for this function:

Here is the caller graph for this function:

ratio_cut_partition::nodes_of_one_side_iterator ratio_cut_partition::nodes_of_sideA_begin ( ) const

Iterate through all nodes which belong to side A, It is only valid if enabled with ratio_cut_partition::store_nodesAB before.

Returns: start for iteration through all nodes on A

Definition at line 353 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 353 of file ratio_cut_partition.cpp

References nodesA.

ratio_cut_partition::nodes_of_one_side_iterator ratio_cut_partition::nodes_of_sideA_end ( ) const

End-Iterator for iteration through all nodes which belong to side A, It is only valid if enabled with ratio_cut_partition::store_nodesAB before.

Returns: end for iteration through all nodes on A

Definition at line 360 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 360 of file ratio_cut_partition.cpp

References nodesA.

ratio_cut_partition::nodes_of_one_side_iterator ratio_cut_partition::nodes_of_sideB_begin ( ) const

Iterate through all nodes which belong to side B, It is only valid if enabled with ratio_cut_partition::store_nodesAB before.

Returns: start for iteration through all nodes on B

Definition at line 367 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 367 of file ratio_cut_partition.cpp

References nodesB.

ratio_cut_partition::nodes_of_one_side_iterator ratio_cut_partition::nodes_of_sideB_end ( ) const

End-Iterator for iteration through all nodes which belong to side B, It is only valid if enabled with ratio_cut_partition::store_nodesAB before.

Returns: end for iteration through all nodes on B

Definition at line 374 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 374 of file ratio_cut_partition.cpp

References nodesB.

ratio_cut_partition::side_type ratio_cut_partition::operator[] ( const node & n ) const

Gets side of the node after bi-partitioning.

Parameters

n	node of graph G

Returns: ratio_cut_partition::A if n lies on side A, ratio_cut_partition::B otherwise

See Also: ratio_cut_partition::get_side_of_node

Definition at line 298 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 298 of file ratio_cut_partition.cpp

References n.

int ratio_cut_partition::range_down ( const int index ) const

inlineprotected

Definition at line 1001 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 1001 of file ratio_cut_partition.cpp

References max_edge_weight, and max_vertex_degree.

int ratio_cut_partition::range_up ( const int gain_value ) const

inlineprotected

Definition at line 995 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 995 of file ratio_cut_partition.cpp

References max_edge_weight, and max_vertex_degree.

Referenced by init_filling_buckets(), initialization(), iterative_shifting(), move_vertex(), move_vertex_A2B(), move_vertex_B2A(), update_bucketA(), update_bucketB(), and update_max_gain().

Here is the caller graph for this function:

double ratio_cut_partition::ratio_of_node_A2B ( const node cur_node )

protected

Definition at line 979 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 979 of file ratio_cut_partition.cpp

References double(), gain_value, node_weight, node_weight_on_sideA, and node_weight_on_sideB.

Referenced by compute_highest_ratio_node(), and move_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

double ratio_cut_partition::ratio_of_node_B2A ( const node cur_node )

protected

Definition at line 987 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 987 of file ratio_cut_partition.cpp

References double(), gain_value, node_weight, node_weight_on_sideA, and node_weight_on_sideB.

Referenced by compute_highest_ratio_node(), and move_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::reset ( )

virtual

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

See Also: algorithm::reset

Implements algorithm.

Definition at line 380 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 380 of file ratio_cut_partition.cpp

References cut_edges, nodesA, nodesB, and set_vars_executed.

void ratio_cut_partition::restore	(	graph &	G,
		list< edge > &	artificial_edges
	)

protected

Definition at line 433 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 433 of file ratio_cut_partition.cpp

References graph::del_edge().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void ratio_cut_partition::right_shift_op ( const graph & G )

protected

Definition at line 800 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 800 of file ratio_cut_partition.cpp

References A, B, cur_cutratio, cur_cutsize, i, move_vertex_A2B(), node_weight_on_sideA, node_weight_on_sideB, graph::number_of_nodes(), and side.

Referenced by initialization(), and iterative_shifting().

Here is the call graph for this function:

Here is the caller graph for this function:

int ratio_cut_partition::run ( graph & G )

virtual

Computes a partitioning of G, that means a division of its vertices in two sides ratio_cut_partition::A and ratio_cut_partition::B.

Parameters

G graph

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

See Also: algorithm::run

Implements algorithm.

Definition at line 219 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 219 of file ratio_cut_partition.cpp

References A, clean_step(), compute_cut_edges(), compute_nodesAB(), compute_target_node(), cur_cutratio, cur_cutsize, determine_source_node(), direction, divide_up(), enable_cut_edges_storing, enable_nodesAB_storing, group_swapping(), algorithm::GTL_OK, init_data_structure(), init_variables(), initialization(), graph::is_connected(), iterative_shifting(), LEFT_SHIFT, make_connected(), graph::nodes_begin(), graph::number_of_nodes(), provided_fix, provided_initial_part, provided_st, restore(), and side.

Here is the call graph for this function:

void ratio_cut_partition::set_vars	(	const graph &	G,
		const node_map< int > &	node_weight,
		const edge_map< int > &	edge_weight
	)

Sets variables. Must be executed before ratio_cut_partition::check! source_node and target_node will be determined automatically.

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge.

See Also: ratio_cut_partition::check

Definition at line 57 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 57 of file ratio_cut_partition.cpp

References edge_weight, fixed, ne_map< Key, Value, Graph, Alloc >::init(), node_weight, provided_fix, provided_initial_part, provided_st, set_vars_executed, side, and UNFIXED.

Here is the call graph for this function:

void ratio_cut_partition::set_vars	(	const graph &	G,
		const node_map< int > &	node_weight,
		const edge_map< int > &	edge_weight,
		const node	source_node,
		const node	target_node
	)

Sets variables. Must be executed before ratio_cut_partition::check! In order to get good results, you should take two graph theoretically far away nodes as source and target.

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
source_node	start-node, remains on side `A`
target_node	end-node, remains on side `B`

See Also: ratio_cut_partition::check

Definition at line 71 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 71 of file ratio_cut_partition.cpp

References edge_weight, fixed, ne_map< Key, Value, Graph, Alloc >::init(), node_weight, provided_fix, provided_initial_part, provided_st, set_vars_executed, side, source_node, target_node, and UNFIXED.

Here is the call graph for this function:

void ratio_cut_partition::set_vars	(	const graph &	G,
		const node_map< int > &	node_weight,
		const edge_map< int > &	edge_weight,
		const node	source_node,
		const node	target_node,
		const node_map< side_type > &	init_side
	)

Sets variables. Must be executed before ratio_cut_partition::check! In order to get good results, you should take two graph theoretically far away nodes as source and target. Additionally init_side should nearly be in balance. source_node must be on side A in init_side and target_node on side B respectively.

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
source_node	start-node, remains on side `A`
target_node	end-node, remains on side `B`
init_side	initial bi-partitioning

See Also: ratio_cut_partition::check

Definition at line 88 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 88 of file ratio_cut_partition.cpp

References edge_weight, fixed, ne_map< Key, Value, Graph, Alloc >::init(), node_weight, provided_fix, provided_initial_part, provided_st, set_vars_executed, side, source_node, target_node, and UNFIXED.

Here is the call graph for this function:

void ratio_cut_partition::set_vars	(	const graph &	G,
		const node_map< int > &	node_weight,
		const edge_map< int > &	edge_weight,
		const node	source_node,
		const node	target_node,
		const node_map< fix_type > &	fixed
	)

Sets variables. Must be executed before ratio_cut_partition::check! In order to get good results, you should take two graph theoretically far away nodes as source and target. source_node must not be fixed on side B . target_node must not be fixed on side A .

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
source_node	start-node, remains on side `A`
target_node	end-node, remains on side `B`
fixed	fixed nodes

See Also: ratio_cut_partition::check

Definition at line 106 of file ratio_cut_partition.cpp.

View newest version in sPHENIX GitHub at line 106 of file ratio_cut_partition.cpp

References edge_weight, fixed, ne_map< Key, Value, Graph, Alloc >::init(), node_weight, provided_fix, provided_initial_part, provided_st, set_vars_executed, side, source_node, and target_node.

Here is the call graph for this function:

void ratio_cut_partition::set_vars	(	const graph &	G,
		const node_map< int > &	node_weight,
		const edge_map< int > &	edge_weight,
		const node	source_node,
		const node	target_node,
		const node_map< side_type > &	init_side,
		const node_map< fix_type > &	fixed
	)

Sets variables. Must be executed before ratio_cut_partition::check! In order to get good results, you should take two graph theoretically far away nodes as source and target. Additionally init_side should nearly be in balance. Fixed nodes are on their fix side, their initial side is overwritten then. source_node must be on side A in init_side and target_node on side B respectively. source_node must not be fixed on side B . target_node must not be fixed on side A .

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
source_node	start-node, remains on side `A`
target_node	end-node, remains on side `B`
init_side	initial bi-partitioning
fixed	fixed nodes