Heuristic graph bi-partitioning algorithm (Fiduccia-Mattheyses). More...

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

Inheritance diagram for fm_partition:

Collaboration diagram for fm_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
	fm_partition ()

virtual	~fm_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_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_map< fix_type > &fixed)

void	set_vars (const graph &G, const node_map< int > &node_weight, const edge_map< int > &edge_weight, 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 ()

int	get_needed_passes ()

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 Member Functions
void	divide_up (const graph &G)

void	hide_self_loops (graph &G)

void	init_variables (const graph &G)

void	create_initial_bipart (const graph &G)

void	shuffle_vector (const int vector_size, vector< graph::node_iterator > &node_vector)

void	compute_max_vertex_degree (const graph &G)

void	pass_manager (const graph &G)

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

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	move_manager (const graph &G)

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

bool	balance_holds (const graph &G, const node cur_node)

void	update_data_structure_A2B (const node cur_node)

void	update_data_structure_B2A (const node cur_node)

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

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

void	update_max_gain (const side_type side)

int	range_up (const int gain_value) const

int	range_down (const int index) const

void	clean_pass (const graph &G)

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

bool	set_vars_executed

bool	provided_initial_part

bool	provided_fix

node_map< fix_type >	fixed

node_map< int >	node_weight

int	max_node_weight

edge_map< int >	edge_weight

int	max_edge_weight

int	total_node_weight

int	node_weight_on_sideA

int	node_weight_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

int	no_passes

Detailed Description

Heuristic graph bi-partitioning algorithm (Fiduccia-Mattheyses).

This class implements a heuristic graph bi-partitioning algorithm, based on iterative movement, proposed by C. M. Fiduccia and R. M. Mattheyses in 1982.

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

See Also: ratio_cut_partition

Definition at line 33 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 33 of file fm_partition.h

Member Typedef Documentation

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

Iterator type for edges which belong to the cut.

Definition at line 269 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 269 of file fm_partition.h

typedef short int fm_partition::fix_type

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

See Also: fm_partition::FIXA; fm_partition::FIXB; fm_partition::UNFIXED

Definition at line 65 of file fm_partition.h.

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

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

Iterator type of nodes of a side.

Definition at line 294 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 294 of file fm_partition.h

typedef int fm_partition::side_type

Return type of fm_partition::get_side_of_node.

See Also: fm_partition::A; fm_partition::B

Definition at line 42 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 42 of file fm_partition.h

Constructor & Destructor Documentation

fm_partition::fm_partition ( )

Default constructor.

See Also: fm_partition::fixe_type

Definition at line 42 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 42 of file fm_partition.cpp

References enable_cut_edges_storing, enable_nodesAB_storing, and set_vars_executed.

fm_partition::~fm_partition ( )

virtual

Destructor.

See Also: algorithm::~algorithm

Definition at line 50 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 50 of file fm_partition.cpp

Member Function Documentation

bool fm_partition::balance_holds	(	const graph &	G,
		const node	cur_node
	)

protected

Definition at line 795 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 795 of file fm_partition.cpp

References A, max_node_weight, node_weight, node_weight_on_sideA, node_weight_on_sideB, side, and total_node_weight.

Referenced by move_vertex().

Here is the caller graph for this function:

int fm_partition::check ( graph & G )

virtual

Checks whether following preconditions are satisfied:

fm_partition::set_vars has been executed before.
graph G is undirected.
only node_weights >= 0 are applied.
only edge_weights >= 0 are applied.

Parameters

G graph

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

See Also: fm_partition::set_vars; algorithm::check

Implements algorithm.

Definition at line 123 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 123 of file fm_partition.cpp

References edge_weight, graph::edges_begin(), graph::edges_end(), algorithm::GTL_ERROR, algorithm::GTL_OK, graph::is_undirected(), node_weight, graph::nodes_begin(), graph::nodes_end(), and set_vars_executed.

Here is the call graph for this function:

void fm_partition::clean_pass ( const graph & G )

protected

Definition at line 1038 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 1038 of file fm_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 pass_manager().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::compute_cut_edges ( const graph & G )

protected

Definition at line 1061 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 1061 of file fm_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:

void fm_partition::compute_max_vertex_degree ( const graph & G )

protected

Definition at line 454 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 454 of file fm_partition.cpp

References max_vertex_degree, 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 fm_partition::compute_nodesAB ( const graph & G )

protected

Definition at line 1077 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 1077 of file fm_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 fm_partition::copy_side_node_map	(	const graph &	G,
		node_map< side_type > &	dest,
		const node_map< side_type >	source
	)		const

protected

Definition at line 503 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 503 of file fm_partition.cpp

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

Referenced by pass_manager().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::create_initial_bipart ( const graph & G )

protected

Definition at line 374 of file fm_partition.cpp.

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

References A, B, FIXA, FIXB, fixed, i, node_weight, node_weight_on_sideA, node_weight_on_sideB, graph::nodes_begin(), graph::nodes_end(), graph::number_of_nodes(), shuffle_vector(), side, and UNFIXED.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

fm_partition::cut_edges_iterator fm_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 fm_partition::store_cut_edges before.

Returns: start for iteration through all cut edges

Definition at line 244 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 244 of file fm_partition.cpp

References cut_edges.

fm_partition::cut_edges_iterator fm_partition::cut_edges_end ( ) const

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

Returns: end for iteration through all cut-edges

Definition at line 250 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 250 of file fm_partition.cpp

References cut_edges.

void fm_partition::divide_up ( const graph & G )

protected

Definition at line 293 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 293 of file fm_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:

int fm_partition::get_cutsize ( )

Gets the size of the cut after bi-partitioning.

Returns: cutsize

Definition at line 186 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 186 of file fm_partition.cpp

References cur_cutsize.

int fm_partition::get_needed_passes ( )

Gets the number of passes needed to create a bi-partition with this heuristic.

Returns: number of passes

Definition at line 192 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 192 of file fm_partition.cpp

References no_passes.

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

Gets side of the node after bi-partitioning.

Parameters

n	node of graph `G`

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

Definition at line 198 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 198 of file fm_partition.cpp

References n, and side.

int fm_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 210 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 210 of file fm_partition.cpp

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

Here is the call graph for this function:

int fm_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 227 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 227 of file fm_partition.cpp

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

Here is the call graph for this function:

void fm_partition::hide_self_loops ( graph & G )

protected

Definition at line 312 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 312 of file fm_partition.cpp

References graph::edges_begin(), graph::edges_end(), and graph::hide_edge().

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::init_data_structure ( const graph & G )

protected

Definition at line 516 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 516 of file fm_partition.cpp

References A, aside, B, bside, bucketA, bucketB, cur_cutsize, 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 pass_manager().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::init_filling_buckets ( const graph & G )

protected

Definition at line 571 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 571 of file fm_partition.cpp

References A, bucketA, bucketA_empty, bucketB, bucketB_empty, end, 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(), 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 fm_partition::init_variables ( const graph & G )

protected

Definition at line 333 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 333 of file fm_partition.cpp

References edge_weight, graph::edges_begin(), graph::edges_end(), max_edge_weight, max_node_weight, node_weight, graph::nodes_begin(), graph::nodes_end(), and total_node_weight.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

int fm_partition::inital_gain_of_node_on_sideA ( const node cur_node )

protected

Definition at line 640 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 640 of file fm_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 fm_partition::inital_gain_of_node_on_sideB ( const node cur_node )

protected

Definition at line 661 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 661 of file fm_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 fm_partition::move_manager ( const graph & G )

protected

Definition at line 682 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 682 of file fm_partition.cpp

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

Referenced by pass_manager().

Here is the call graph for this function:

Here is the caller graph for this function:

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

protected

Definition at line 727 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 727 of file fm_partition.cpp

References A, B, balance_holds(), bucketA, bucketA_empty, bucketB, bucketB_empty, gain_value, max_gainA, max_gainB, node_weight, node_weight_on_sideA, node_weight_on_sideB, range_up(), 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:

fm_partition::nodes_of_one_side_iterator fm_partition::nodes_of_sideA_begin ( ) const

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

Returns: start for iteration through all nodes on A

Definition at line 257 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 257 of file fm_partition.cpp

References nodesA.

fm_partition::nodes_of_one_side_iterator fm_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 fm_partition::store_nodesAB before.

Returns: end for iteration through all nodes on A

Definition at line 264 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 264 of file fm_partition.cpp

References nodesA.

fm_partition::nodes_of_one_side_iterator fm_partition::nodes_of_sideB_begin ( ) const

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

Returns: start for iteration through all nodes on B

Definition at line 271 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 271 of file fm_partition.cpp

References nodesB.

fm_partition::nodes_of_one_side_iterator fm_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 fm_partition::store_nodesAB before.

Returns: end for iteration through all nodes on B

Definition at line 278 of file fm_partition.cpp.

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

References nodesB.

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

Gets side of the node after bi-partitioning.

Parameters

n	node of graph `G`

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

See Also: fm_partition::get_side_of_node

Definition at line 204 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 204 of file fm_partition.cpp

References n, and side.

void fm_partition::pass_manager ( const graph & G )

protected

Definition at line 470 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 470 of file fm_partition.cpp

References clean_pass(), copy_side_node_map(), cur_cutsize, init_data_structure(), move_manager(), no_passes, and side.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

int fm_partition::range_down ( const int index ) const

inlineprotected

Definition at line 1032 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 1032 of file fm_partition.cpp

References max_edge_weight, and max_vertex_degree.

int fm_partition::range_up ( const int gain_value ) const

inlineprotected

Definition at line 1026 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 1026 of file fm_partition.cpp

References max_edge_weight, and max_vertex_degree.

Referenced by init_filling_buckets(), move_vertex(), update_bucketA(), update_bucketB(), update_data_structure_A2B(), update_data_structure_B2A(), and update_max_gain().

Here is the caller graph for this function:

void fm_partition::reset ( )

virtual

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

See Also: algorithm::reset

Implements algorithm.

Definition at line 284 of file fm_partition.cpp.

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

References cut_edges, nodesA, nodesB, and set_vars_executed.

int fm_partition::run ( graph & G )

virtual

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

Parameters

G graph

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

See Also: algorithm::run

Implements algorithm.

Definition at line 155 of file fm_partition.cpp.

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

References compute_cut_edges(), compute_max_vertex_degree(), compute_nodesAB(), create_initial_bipart(), divide_up(), enable_cut_edges_storing, enable_nodesAB_storing, algorithm::GTL_OK, hide_self_loops(), init_variables(), pass_manager(), provided_fix, provided_initial_part, and graph::restore_graph().

Here is the call graph for this function:

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

Sets variables. Must be executed before fm_partition::check!

Parameters

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

See Also: fm_partition::check

Definition at line 55 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 55 of file fm_partition.cpp

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

Here is the call graph for this function:

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

Sets variables. Must be executed before fm_partition::check! In order to get good results, init_side should almost be in balance.

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
init_side	initial bi-partitioning

See Also: fm_partition::check

Definition at line 68 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 68 of file fm_partition.cpp

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

Here is the call graph for this function:

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

Sets variables. Must be executed before fm_partition::check!

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
fixed	fixed nodes

See Also: fm_partition::check

Definition at line 82 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 82 of file fm_partition.cpp

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

Here is the call graph for this function:

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

Sets variables. Must be executed before fm_partition::check! In order to get good results, init_side should almost be in balance. Fixed nodes are on their fix side, their initial side is overwritten then.

Parameters

G	undirected graph
node_weight	weight of each node
edge_weight	weight of each edge
init_side	initial bi-partitioning
fixed	fixed nodes

See Also: fm_partition::check

Definition at line 96 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 96 of file fm_partition.cpp

References edge_weight, fixed, node_weight, provided_fix, provided_initial_part, set_vars_executed, and side.

void fm_partition::shuffle_vector	(	const int	vector_size,
		vector< graph::node_iterator > &	node_vector
	)

protected

Definition at line 435 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 435 of file fm_partition.cpp

References double(), i, and Acts::Test::time.

Referenced by create_initial_bipart().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::store_cut_edges ( const bool set )

Enables the storing of cut-edges. If enabled the list of cut-edges can be traversed using fm_partition::cut_edges_iterator.

Parameters

set	if `true` cut_edges will be stored

See Also: fm_partition::cut_edges_begin; fm_partition::cut_edges_end

Definition at line 111 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 111 of file fm_partition.cpp

References enable_cut_edges_storing.

void fm_partition::store_nodesAB ( const bool set )

Enables the storing of nodes on their side. If enabled the nodes of each side can be traversed using fm_partition::nodes_on_one_side_iterator.

Parameters

set	if `true` nodes will be stored on their sides

See Also: fm_partition::nodes_of_sideA_begin; fm_partition::nodes_of_sideA_end; fm_partition::nodes_of_sideB_begin; fm_partition::nodes_of_sideB_end

Definition at line 117 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 117 of file fm_partition.cpp

References enable_nodesAB_storing.

void fm_partition::update_bucketA	(	const node	cur_node,
		const int	old_gain,
		const int	new_gain
	)

protected

Definition at line 957 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 957 of file fm_partition.cpp

References bucketA, end, fixed, max_gainA, position_in_bucket, range_up(), and UNFIXED.

Referenced by 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 fm_partition::update_bucketB	(	const node	cur_node,
		const int	old_gain,
		const int	new_gain
	)

protected

Definition at line 976 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 976 of file fm_partition.cpp

References bucketB, end, fixed, max_gainB, position_in_bucket, range_up(), and UNFIXED.

Referenced by 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 fm_partition::update_data_structure_A2B ( const node cur_node )

protected

Definition at line 817 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 817 of file fm_partition.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), aside, bside, bucketA, cur_cutsize, edge_weight, gain_value, max_gainA, node_weight, node_weight_on_sideA, node_weight_on_sideB, range_up(), unlockedA, unlockedB, update_bucketA(), and update_bucketB().

Referenced by move_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::update_data_structure_B2A ( const node cur_node )

protected

Definition at line 887 of file fm_partition.cpp.

View newest version in sPHENIX GitHub at line 887 of file fm_partition.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), aside, bside, bucketB, cur_cutsize, edge_weight, gain_value, max_gainB, node_weight, node_weight_on_sideA, node_weight_on_sideB, range_up(), unlockedA, unlockedB, update_bucketA(), and update_bucketB().

Referenced by move_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

void fm_partition::update_max_gain ( const side_type side )

protected

Definition at line 995 of file fm_partition.cpp.

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

References A, B, bucketA, bucketA_empty, bucketB, bucketB_empty, max_gainA, max_gainB, and range_up().

Referenced by move_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

__GTL_BEGIN_NAMESPACE const fm_partition::side_type fm_partition::A = 0

static

A means the node is on side A.

See Also: fm_partition::side_type

Definition at line 49 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 49 of file fm_partition.h

Referenced by balance_holds(), compute_nodesAB(), create_initial_bipart(), divide_up(), get_weight_on_sideA(), init_data_structure(), init_filling_buckets(), move_manager(), move_vertex(), and update_max_gain().

edge_map<int> fm_partition::aside

protected

Definition at line 473 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 473 of file fm_partition.h

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

const fm_partition::side_type fm_partition::B = 1

static

B means the node is on side B.

See Also: fm_partition::side_type

Definition at line 56 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 56 of file fm_partition.h

Referenced by create_initial_bipart(), divide_up(), get_weight_on_sideB(), init_data_structure(), move_manager(), move_vertex(), and update_max_gain().

edge_map<int> fm_partition::bside

protected

Definition at line 479 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 479 of file fm_partition.h

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

vector<list<node> > fm_partition::bucketA

protected

Definition at line 533 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 533 of file fm_partition.h

Referenced by clean_pass(), init_data_structure(), init_filling_buckets(), move_vertex(), update_bucketA(), update_data_structure_A2B(), and update_max_gain().

bool fm_partition::bucketA_empty

protected

Definition at line 505 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 505 of file fm_partition.h

Referenced by init_filling_buckets(), move_vertex(), and update_max_gain().

vector<list<node> > fm_partition::bucketB

protected

Definition at line 541 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 541 of file fm_partition.h

Referenced by clean_pass(), init_data_structure(), init_filling_buckets(), move_vertex(), update_bucketB(), update_data_structure_B2A(), and update_max_gain().

bool fm_partition::bucketB_empty

protected

Definition at line 511 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 511 of file fm_partition.h

Referenced by init_filling_buckets(), move_vertex(), and update_max_gain().

int fm_partition::cur_cutsize

protected

Definition at line 548 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 548 of file fm_partition.h

Referenced by get_cutsize(), init_data_structure(), move_manager(), pass_manager(), update_data_structure_A2B(), and update_data_structure_B2A().

list<edge> fm_partition::cut_edges

protected

Definition at line 353 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 353 of file fm_partition.h

Referenced by compute_cut_edges(), cut_edges_begin(), cut_edges_end(), and reset().

edge_map<int> fm_partition::edge_weight

protected

Definition at line 421 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 421 of file fm_partition.h

Referenced by check(), init_data_structure(), init_variables(), inital_gain_of_node_on_sideA(), inital_gain_of_node_on_sideB(), set_vars(), update_data_structure_A2B(), and update_data_structure_B2A().

bool fm_partition::enable_cut_edges_storing

protected

Definition at line 347 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 347 of file fm_partition.h

Referenced by fm_partition(), run(), and store_cut_edges().

bool fm_partition::enable_nodesAB_storing

protected

Definition at line 360 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 360 of file fm_partition.h

Referenced by fm_partition(), run(), and store_nodesAB().

const fm_partition::fix_type fm_partition::FIXA = 0

static

FIXA means fix node on side A.

See Also: fm_partition::set_vars

Definition at line 72 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 72 of file fm_partition.h

Referenced by create_initial_bipart(), and divide_up().

const fm_partition::fix_type fm_partition::FIXB = 1

static

FIXB means fix node on side B.

See Also: fm_partition::fixe_type

Definition at line 79 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 79 of file fm_partition.h

Referenced by create_initial_bipart(), and divide_up().

node_map<fix_type> fm_partition::fixed

protected

Definition at line 400 of file fm_partition.h.

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

Referenced by create_initial_bipart(), divide_up(), init_filling_buckets(), set_vars(), update_bucketA(), and update_bucketB().

node_map<int> fm_partition::gain_value

protected

Definition at line 499 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 499 of file fm_partition.h

Referenced by init_filling_buckets(), move_vertex(), update_data_structure_A2B(), and update_data_structure_B2A().

int fm_partition::max_edge_weight

protected

Definition at line 428 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 428 of file fm_partition.h

Referenced by clean_pass(), init_data_structure(), init_variables(), range_down(), and range_up().

int fm_partition::max_gainA

protected

Definition at line 518 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 518 of file fm_partition.h

Referenced by init_filling_buckets(), move_vertex(), update_bucketA(), update_data_structure_A2B(), and update_max_gain().

int fm_partition::max_gainB

protected

Definition at line 525 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 525 of file fm_partition.h

Referenced by init_filling_buckets(), move_vertex(), update_bucketB(), update_data_structure_B2A(), and update_max_gain().

int fm_partition::max_node_weight

protected

Definition at line 414 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 414 of file fm_partition.h

Referenced by balance_holds(), and init_variables().

int fm_partition::max_vertex_degree

protected

Definition at line 467 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 467 of file fm_partition.h

Referenced by clean_pass(), compute_max_vertex_degree(), init_data_structure(), range_down(), and range_up().

int fm_partition::no_passes

protected

Definition at line 554 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 554 of file fm_partition.h

Referenced by get_needed_passes(), and pass_manager().

node_map<int> fm_partition::node_weight

protected

Definition at line 407 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 407 of file fm_partition.h

Referenced by balance_holds(), check(), create_initial_bipart(), get_weight_on_sideA(), get_weight_on_sideB(), init_filling_buckets(), init_variables(), move_vertex(), set_vars(), update_data_structure_A2B(), and update_data_structure_B2A().

int fm_partition::node_weight_on_sideA

protected

Definition at line 442 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 442 of file fm_partition.h

Referenced by balance_holds(), create_initial_bipart(), init_filling_buckets(), move_manager(), move_vertex(), update_data_structure_A2B(), and update_data_structure_B2A().

int fm_partition::node_weight_on_sideB

protected

Definition at line 449 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 449 of file fm_partition.h

Referenced by balance_holds(), create_initial_bipart(), init_filling_buckets(), move_manager(), move_vertex(), update_data_structure_A2B(), and update_data_structure_B2A().

list<node> fm_partition::nodesA

protected

Definition at line 366 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 366 of file fm_partition.h

Referenced by compute_nodesAB(), nodes_of_sideA_begin(), nodes_of_sideA_end(), and reset().

list<node> fm_partition::nodesB

protected

Definition at line 372 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 372 of file fm_partition.h

Referenced by compute_nodesAB(), nodes_of_sideB_begin(), nodes_of_sideB_end(), and reset().

node_map<list<node>::iterator> fm_partition::position_in_bucket

protected

Definition at line 461 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 461 of file fm_partition.h

Referenced by init_filling_buckets(), update_bucketA(), and update_bucketB().

bool fm_partition::provided_fix

protected

Definition at line 394 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 394 of file fm_partition.h

Referenced by run(), and set_vars().

bool fm_partition::provided_initial_part

protected

Definition at line 387 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 387 of file fm_partition.h

Referenced by run(), and set_vars().

bool fm_partition::set_vars_executed

protected

Definition at line 380 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 380 of file fm_partition.h

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

node_map<side_type> fm_partition::side

protected

Definition at line 455 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 455 of file fm_partition.h

Referenced by balance_holds(), compute_cut_edges(), compute_nodesAB(), create_initial_bipart(), divide_up(), get_side_of_node(), get_weight_on_sideA(), get_weight_on_sideB(), init_data_structure(), init_filling_buckets(), move_manager(), operator[](), pass_manager(), and set_vars().

int fm_partition::total_node_weight

protected

Definition at line 435 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 435 of file fm_partition.h

Referenced by balance_holds(), and init_variables().

const fm_partition::fix_type fm_partition::UNFIXED = 2

static

UNFIXED means node is free.

See Also: fm_partition::fixe_type

Definition at line 86 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 86 of file fm_partition.h

Referenced by create_initial_bipart(), init_filling_buckets(), set_vars(), update_bucketA(), and update_bucketB().

edge_map<list<node> > fm_partition::unlockedA

protected

Definition at line 486 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 486 of file fm_partition.h

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

edge_map<list<node> > fm_partition::unlockedB

protected

Definition at line 493 of file fm_partition.h.

View newest version in sPHENIX GitHub at line 493 of file fm_partition.h

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

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

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

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation