ck-ldb/tm_tree.C File Reference

Go to the source code of this file.

Functions

void free_list_child (tree_t *tree)

void free_tab_child (tree_t *tree)

void free_tree (tree_t *tree)

long int choose (long n, long k)

void set_node (tree_t *node, tree_t **child, int arity, tree_t *parent, int id, double val, tree_t *tab_child)

void display_node (tree_t *node)

void clone_tree (tree_t *newptr, tree_t *oldptr)

double * aggregate_obj_weight (tree_t *new_tab_node, double *tab, int M)

double ** aggregate_com_mat (tree_t *new_tab_node, double **tab, int M)

void free_tab_double (double **tab, int N)

void free_tab_int (int **tab, int N)

void display_tab (double **tab, int N)

double eval_grouping (double **tab, tree_t **cur_group, int arity, int N)

group_list_t * new_group_list (tree_t **tab, double val, group_list_t *next)

void add_to_list (group_list_t *list, tree_t **cur_group, int arity, double val)

void list_all_possible_groups (double **tab, tree_t *tab_node, int id, int arity, int depth, tree_t **cur_group, int N, group_list_t *list)

void update_val (double **tab, tree_t *parent, int N)

int independent_groups (group_list_t **selection, int d, group_list_t *elem, int arity)

void display_selection (group_list_t **selection, int M, int arity, double val)

void display_grouping (tree_t *father, int M, int arity, double val)

int recurs_select_independent_groups (group_list_t **tab, int i, int n, int arity, int d, int M, double val, double *best_val, group_list_t **selection, group_list_t **best_selection)

int test_independent_groups (group_list_t **tab, int i, int n, int arity, int d, int M, double val, double *best_val, group_list_t **selection, group_list_t **best_selection)

void delete_group_list (group_list_t *list)

int group_list_id (const void *x1, const void *x2)

int group_list_asc (const void *x1, const void *x2)

int group_list_dsc (const void *x1, const void *x2)

int weighted_degree_asc (const void *x1, const void *x2)

int weighted_degree_dsc (const void *x1, const void *x2)

int select_independent_groups (group_list_t **tab_group, int n, int arity, int M, double *best_val, group_list_t **best_selection, int bound, double max_duration)

int select_independent_groups_by_largest_index (group_list_t **tab_group, int n, int arity, int M, double *best_val, group_list_t **best_selection, int bound, double max_duration)

void list_to_tab (group_list_t *list, group_list_t **tab, int n)

void display_tab_group (group_list_t **tab, int n, int arity)

int independent_tab (tree_t **tab1, tree_t **tab2, int n)

void compute_weighted_degree (group_list_t **tab, int n, int arity)

void group (double **tab, tree_t *tab_node, tree_t *parent, int id, int arity, int n, double *best_val, tree_t **cur_group, int N)

void fast_group (double **tab, tree_t *tab_node, tree_t *parent, int id, int arity, int n, double *best_val, tree_t **cur_group, int N, int *nb_groups, int max_groups)

void fast_grouping (double **tab, tree_t *tab_node, tree_t *new_tab_node, int arity, int N, int M, long int k)

int adjacency_asc (const void *x1, const void *x2)

int adjacency_dsc (const void *x1, const void *x2)

void super_fast_grouping (double **tab, tree_t *tab_node, tree_t *new_tab_node, int arity, int N, int M, int k)

double ** build_cost_matrix (double **comm_matrix, double *obj_weight, double comm_speed, int N)

void group_nodes (double **comm_matrix, tree_t *tab_node, tree_t *new_tab_node, int depth, int arity, int N, int M, double *obj_weigth, double comm_speed)

void complete_com_mat (double ***tab, int N, int K)

void complete_obj_weight (double **tab, int N, int K)

void create_dumb_tree (tree_t *node, int depth, tm_topology_t *topology)

void complete_tab_node (tree_t **tab, int N, int K, int depth, tm_topology_t *topology)

void set_deb_tab_child (tree_t *tree, tree_t *child, int depth)

tree_t * build_level_topology (tree_t *tab_node, double **com_mat, int N, int arity, int depth, tm_topology_t *topology, double *obj_weight, double *comm_speed)

double speed (int depth)

tree_t * build_tree_from_topology (tm_topology_t *topology, double **tab, int N, double *obj_weight, double *comm_speed)

Function Documentation

void free_list_child ( tree_t * tree )

Definition at line 21 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, _tree_t::dumb, and free().

Referenced by free_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

void free_tab_child ( tree_t * tree )

Definition at line 36 of file tm_tree.C.

References free(), and _tree_t::tab_child.

Referenced by free_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

void free_tree ( tree_t * tree )

Definition at line 45 of file tm_tree.C.

References free(), free_list_child(), and free_tab_child().

Referenced by parse_dup_op(), and TreeMatchMapping().

Here is the call graph for this function:

Here is the caller graph for this function:

long int choose	(	long	n,
		long	k
	)

Definition at line 52 of file tm_tree.C.

Referenced by group_nodes().

Here is the caller graph for this function:

void set_node	(	tree_t *	node,
		tree_t **	child,
		int	arity,
		tree_t *	parent,
		int	id,
		double	val,
		tree_t *	tab_child
	)

Definition at line 62 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, _tree_t::dumb, _tree_t::id, _tree_t::parent, _tree_t::tab_child, _tree_t::uniq, and _tree_t::val.

Referenced by build_level_topology(), build_synthetic_topology_old(), build_tree_from_topology(), and create_dumb_tree().

Here is the caller graph for this function:

void display_node ( tree_t * node )

Definition at line 74 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, _tree_t::id, _tree_t::parent, _tree_t::uniq, and _tree_t::val.

void clone_tree	(	tree_t *	newptr,
		tree_t *	oldptr
	)

Definition at line 78 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, _tree_t::dumb, _tree_t::id, _tree_t::parent, _tree_t::uniq, and _tree_t::val.

Referenced by complete_tab_node().

Here is the caller graph for this function:

double* aggregate_obj_weight	(	tree_t *	new_tab_node,
		double *	tab,
		int	M
	)

Definition at line 94 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, _tree_t::id, and malloc().

Referenced by build_level_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

double** aggregate_com_mat	(	tree_t *	new_tab_node,
		double **	tab,
		int	M
	)

Definition at line 116 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, _tree_t::id, and malloc().

Referenced by build_level_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

void free_tab_double	(	double **	tab,
		int	N
	)

Definition at line 148 of file tm_tree.C.

References free().

Referenced by build_level_topology(), and group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

void free_tab_int	(	int **	tab,
		int	N
	)

Definition at line 156 of file tm_tree.C.

References free().

Here is the call graph for this function:

void display_tab	(	double **	tab,
		int	N
	)

Definition at line 164 of file tm_tree.C.

double eval_grouping	(	double **	tab,
		tree_t **	cur_group,
		int	arity,
		int	N
	)

Definition at line 181 of file tm_tree.C.

References _tree_t::id.

Referenced by fast_group(), group(), list_all_possible_groups(), and update_val().

Here is the caller graph for this function:

group_list_t* new_group_list	(	tree_t **	tab,
		double	val,
		group_list_t *	next
	)

Definition at line 210 of file tm_tree.C.

References malloc(), _group_list_t::next, _group_list_t::sum_neighbour, _group_list_t::tab, and _group_list_t::val.

Referenced by add_to_list().

Here is the call graph for this function:

Here is the caller graph for this function:

void add_to_list	(	group_list_t *	list,
		tree_t **	cur_group,
		int	arity,
		double	val
	)

Definition at line 221 of file tm_tree.C.

References elem, malloc(), new_group_list(), _group_list_t::next, and _group_list_t::val.

Referenced by list_all_possible_groups().

Here is the call graph for this function:

Here is the caller graph for this function:

void list_all_possible_groups	(	double **	tab,
		tree_t *	tab_node,
		int	id,
		int	arity,
		int	depth,
		tree_t **	cur_group,
		int	N,
		group_list_t *	list
	)

Definition at line 243 of file tm_tree.C.

References add_to_list(), eval_grouping(), and parent().

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

void update_val	(	double **	tab,
		tree_t *	parent,
		int	N
	)

Definition at line 267 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, eval_grouping(), and _tree_t::val.

Referenced by bucket_grouping(), fast_grouping(), group_nodes(), and super_fast_grouping().

Here is the call graph for this function:

Here is the caller graph for this function:

int independent_groups	(	group_list_t **	selection,
		int	d,
		group_list_t *	elem,
		int	arity
	)

Definition at line 287 of file tm_tree.C.

References _tree_t::id, and _group_list_t::tab.

Referenced by recurs_select_independent_groups(), and test_independent_groups().

Here is the caller graph for this function:

void display_selection	(	group_list_t **	selection,
		int	M,
		int	arity,
		double	val
	)

Definition at line 307 of file tm_tree.C.

Referenced by select_independent_groups().

Here is the caller graph for this function:

void display_grouping	(	tree_t *	father,
		int	M,
		int	arity,
		double	val
	)

Definition at line 318 of file tm_tree.C.

Referenced by fast_grouping(), and super_fast_grouping().

Here is the caller graph for this function:

int recurs_select_independent_groups	(	group_list_t **	tab,
		int	i,
		int	n,
		int	arity,
		int	d,
		int	M,
		double	val,
		double *	best_val,
		group_list_t **	selection,
		group_list_t **	best_selection
	)

Definition at line 330 of file tm_tree.C.

References elem, independent_groups(), and _group_list_t::val.

Referenced by select_independent_groups(), and test_independent_groups().

Here is the call graph for this function:

Here is the caller graph for this function:

int test_independent_groups	(	group_list_t **	tab,
		int	i,
		int	n,
		int	arity,
		int	d,
		int	M,
		double	val,
		double *	best_val,
		group_list_t **	selection,
		group_list_t **	best_selection
	)

Definition at line 361 of file tm_tree.C.

References elem, independent_groups(), recurs_select_independent_groups(), and _group_list_t::val.

Referenced by select_independent_groups_by_largest_index().

Here is the call graph for this function:

Here is the caller graph for this function:

void delete_group_list ( group_list_t * list )

Definition at line 382 of file tm_tree.C.

References free(), _group_list_t::next, and _group_list_t::tab.

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

int group_list_id	(	const void *	x1,
		const void *	x2
	)

Definition at line 392 of file tm_tree.C.

References e1, _tree_t::id, and _group_list_t::tab.

Referenced by group_nodes().

Here is the caller graph for this function:

int group_list_asc	(	const void *	x1,
		const void *	x2
	)

Definition at line 403 of file tm_tree.C.

References e1, and _group_list_t::val.

Referenced by group_nodes().

Here is the caller graph for this function:

int group_list_dsc	(	const void *	x1,
		const void *	x2
	)

Definition at line 415 of file tm_tree.C.

References e1, and _group_list_t::val.

Referenced by group_nodes().

Here is the caller graph for this function:

int weighted_degree_asc	(	const void *	x1,
		const void *	x2
	)

Definition at line 427 of file tm_tree.C.

References e1, and _group_list_t::wg.

int weighted_degree_dsc	(	const void *	x1,
		const void *	x2
	)

Definition at line 439 of file tm_tree.C.

References e1, and _group_list_t::wg.

Referenced by group_nodes().

Here is the caller graph for this function:

int select_independent_groups	(	group_list_t **	tab_group,
		int	n,
		int	arity,
		int	M,
		double *	best_val,
		group_list_t **	best_selection,
		int	bound,
		double	max_duration
	)

Definition at line 450 of file tm_tree.C.

References display_selection(), free(), malloc(), recurs_select_independent_groups(), and _group_list_t::val.

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

int select_independent_groups_by_largest_index	(	group_list_t **	tab_group,
		int	n,
		int	arity,
		int	M,
		double *	best_val,
		group_list_t **	best_selection,
		int	bound,
		double	max_duration
	)

Definition at line 481 of file tm_tree.C.

References free(), malloc(), MAX(), test_independent_groups(), and _group_list_t::val.

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

void list_to_tab	(	group_list_t *	list,
		group_list_t **	tab,
		int	n
	)

Definition at line 515 of file tm_tree.C.

References _group_list_t::next.

Referenced by group_nodes().

Here is the caller graph for this function:

void display_tab_group	(	group_list_t **	tab,
		int	n,
		int	arity
	)

Definition at line 531 of file tm_tree.C.

int independent_tab	(	tree_t **	tab1,
		tree_t **	tab2,
		int	n
	)

Definition at line 540 of file tm_tree.C.

Referenced by compute_weighted_degree().

Here is the caller graph for this function:

void compute_weighted_degree	(	group_list_t **	tab,
		int	n,
		int	arity
	)

Definition at line 556 of file tm_tree.C.

References independent_tab(), _group_list_t::sum_neighbour, _group_list_t::val, and _group_list_t::wg.

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

void group	(	double **	tab,
		tree_t *	tab_node,
		tree_t *	parent,
		int	id,
		int	arity,
		int	n,
		double *	best_val,
		tree_t **	cur_group,
		int	N
	)

Definition at line 588 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, eval_grouping(), and group.

Here is the call graph for this function:

void fast_group	(	double **	tab,
		tree_t *	tab_node,
		tree_t *	parent,
		int	id,
		int	arity,
		int	n,
		double *	best_val,
		tree_t **	cur_group,
		int	N,
		int *	nb_groups,
		int	max_groups
	)

Definition at line 634 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, and eval_grouping().

Referenced by fast_grouping().

Here is the call graph for this function:

Here is the caller graph for this function:

void fast_grouping	(	double **	tab,
		tree_t *	tab_node,
		tree_t *	new_tab_node,
		int	arity,
		int	N,
		int	M,
		long int	k
	)

Definition at line 679 of file tm_tree.C.

References _tree_t::arity, _tree_t::child, CmiLog2(), display_grouping(), fast_group(), free(), PUP::l, malloc(), MAX(), _tree_t::parent, and update_val().

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

int adjacency_asc	(	const void *	x1,
		const void *	x2
	)

Definition at line 713 of file tm_tree.C.

References e1, and adjacency_t::val.

int adjacency_dsc	(	const void *	x1,
		const void *	x2
	)

Definition at line 725 of file tm_tree.C.

References e1, and adjacency_t::val.

Referenced by super_fast_grouping().

Here is the caller graph for this function:

void super_fast_grouping	(	double **	tab,
		tree_t *	tab_node,
		tree_t *	new_tab_node,
		int	arity,
		int	N,
		int	M,
		int	k
	)

Definition at line 735 of file tm_tree.C.

References adjacency_dsc(), assert, display_grouping(), free(), adjacency_t::i, adjacency_t::j, PUP::l, malloc(), qsort(), try_add_edge(), update_val(), _tree_t::val, and adjacency_t::val.

Here is the call graph for this function:

double** build_cost_matrix	(	double **	comm_matrix,
		double *	obj_weight,
		double	comm_speed,
		int	N
	)

Definition at line 795 of file tm_tree.C.

References malloc().

Referenced by group_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

void group_nodes	(	double **	comm_matrix,
		tree_t *	tab_node,
		tree_t *	new_tab_node,
		int	depth,
		int	arity,
		int	N,
		int	M,
		double *	obj_weigth,
		double	comm_speed
	)

Definition at line 834 of file tm_tree.C.

References _tree_t::arity, assert, bucket_grouping(), build_cost_matrix(), _tree_t::child, choose(), compute_weighted_degree(), delete_group_list(), fast_grouping(), free(), free_tab_double(), group_list_asc(), group_list_dsc(), group_list_id(), int, PUP::l, list, list_all_possible_groups(), list_to_tab(), malloc(), n, _group_list_t::next, _tree_t::parent, qsort(), select_independent_groups(), select_independent_groups_by_largest_index(), _group_list_t::tab, update_val(), _group_list_t::val, and weighted_degree_dsc().

Referenced by build_level_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

void complete_com_mat	(	double ***	tab,
		int	N,
		int	K
	)

Definition at line 979 of file tm_tree.C.

References malloc().

Referenced by build_level_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

void complete_obj_weight	(	double **	tab,
		int	N,
		int	K
	)

Definition at line 1002 of file tm_tree.C.

References malloc().

Referenced by build_level_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

void create_dumb_tree	(	tree_t *	node,
		int	depth,
		tm_topology_t *	topology
	)

Definition at line 1033 of file tm_tree.C.

References tm_topology_t::arity, assert, calloc(), _tree_t::dumb, malloc(), tm_topology_t::nb_levels, _tree_t::parent, and set_node().

Referenced by complete_tab_node().

Here is the call graph for this function:

Here is the caller graph for this function:

void complete_tab_node	(	tree_t **	tab,
		int	N,
		int	K,
		int	depth,
		tm_topology_t *	topology
	)

Definition at line 1057 of file tm_tree.C.

References clone_tree(), create_dumb_tree(), free(), _tree_t::id, and malloc().

Referenced by build_level_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

void set_deb_tab_child	(	tree_t *	tree,
		tree_t *	child,
		int	depth
	)

Definition at line 1084 of file tm_tree.C.

References _tree_t::tab_child.

Referenced by build_level_topology().

Here is the caller graph for this function:

tree_t* build_level_topology	(	tree_t *	tab_node,
		double **	com_mat,
		int	N,
		int	arity,
		int	depth,
		tm_topology_t *	topology,
		double *	obj_weight,
		double *	comm_speed
	)

Definition at line 1106 of file tm_tree.C.

References aggregate_com_mat(), aggregate_obj_weight(), tm_topology_t::arity, calloc(), complete_com_mat(), complete_obj_weight(), complete_tab_node(), free(), free_tab_double(), group_nodes(), malloc(), set_deb_tab_child(), set_node(), and speed().

Referenced by build_tree_from_topology().

Here is the call graph for this function:

Here is the caller graph for this function:

double speed ( int depth )

Definition at line 1200 of file tm_tree.C.

Referenced by arg_init(), build_level_topology(), build_synthetic_topology_old(), and GreedyRefineLB::fillData().

Here is the caller graph for this function:

tree_t* build_tree_from_topology	(	tm_topology_t *	topology,
		double **	tab,
		int	N,
		double *	obj_weight,
		double *	comm_speed
	)

Definition at line 1213 of file tm_tree.C.

References tm_topology_t::arity, build_level_topology(), malloc(), tm_topology_t::nb_levels, and set_node().

Referenced by TreeMatchMapping(), and TreeMatchLB::work().

Here is the call graph for this function:

Here is the caller graph for this function:


Functions
void	free_list_child (tree_t *tree)
void	free_tab_child (tree_t *tree)
void	free_tree (tree_t *tree)
long int	choose (long n, long k)
void	set_node (tree_t node, tree_t child, int arity, tree_t parent, int id, double val, tree_t *tab_child)
void	display_node (tree_t *node)
void	clone_tree (tree_t newptr, tree_t oldptr)
double *	aggregate_obj_weight (tree_t new_tab_node, double tab, int M)
double **	aggregate_com_mat (tree_t new_tab_node, double *tab, int M)
void	free_tab_double (double **tab, int N)
void	free_tab_int (int **tab, int N)
void	display_tab (double **tab, int N)
double	eval_grouping (double tab, tree_t cur_group, int arity, int N)
group_list_t *	new_group_list (tree_t *tab, double val, group_list_t next)
void	add_to_list (group_list_t list, tree_t *cur_group, int arity, double val)
void	list_all_possible_groups (double *tab, tree_t tab_node, int id, int arity, int depth, tree_t *cur_group, int N, group_list_t list)
void	update_val (double *tab, tree_t parent, int N)
int	independent_groups (group_list_t *selection, int d, group_list_t elem, int arity)
void	display_selection (group_list_t **selection, int M, int arity, double val)
void	display_grouping (tree_t *father, int M, int arity, double val)
int	recurs_select_independent_groups (group_list_t *tab, int i, int n, int arity, int d, int M, double val, double best_val, group_list_t selection, group_list_t best_selection)
int	test_independent_groups (group_list_t *tab, int i, int n, int arity, int d, int M, double val, double best_val, group_list_t selection, group_list_t best_selection)
void	delete_group_list (group_list_t *list)
int	group_list_id (const void x1, const void x2)
int	group_list_asc (const void x1, const void x2)
int	group_list_dsc (const void x1, const void x2)
int	weighted_degree_asc (const void x1, const void x2)
int	weighted_degree_dsc (const void x1, const void x2)
int	select_independent_groups (group_list_t *tab_group, int n, int arity, int M, double best_val, group_list_t **best_selection, int bound, double max_duration)
int	select_independent_groups_by_largest_index (group_list_t *tab_group, int n, int arity, int M, double best_val, group_list_t **best_selection, int bound, double max_duration)
void	list_to_tab (group_list_t list, group_list_t *tab, int n)
void	display_tab_group (group_list_t **tab, int n, int arity)
int	independent_tab (tree_t tab1, tree_t tab2, int n)
void	compute_weighted_degree (group_list_t **tab, int n, int arity)
void	group (double *tab, tree_t tab_node, tree_t parent, int id, int arity, int n, double best_val, tree_t **cur_group, int N)
void	fast_group (double *tab, tree_t tab_node, tree_t parent, int id, int arity, int n, double best_val, tree_t *cur_group, int N, int nb_groups, int max_groups)
void	fast_grouping (double *tab, tree_t tab_node, tree_t *new_tab_node, int arity, int N, int M, long int k)
int	adjacency_asc (const void x1, const void x2)
int	adjacency_dsc (const void x1, const void x2)
void	super_fast_grouping (double *tab, tree_t tab_node, tree_t *new_tab_node, int arity, int N, int M, int k)
double **	build_cost_matrix (double *comm_matrix, double obj_weight, double comm_speed, int N)
void	group_nodes (double *comm_matrix, tree_t tab_node, tree_t new_tab_node, int depth, int arity, int N, int M, double obj_weigth, double comm_speed)
void	complete_com_mat (double ***tab, int N, int K)
void	complete_obj_weight (double **tab, int N, int K)
void	create_dumb_tree (tree_t node, int depth, tm_topology_t topology)
void	complete_tab_node (tree_t *tab, int N, int K, int depth, tm_topology_t topology)
void	set_deb_tab_child (tree_t tree, tree_t child, int depth)
tree_t *	build_level_topology (tree_t tab_node, double com_mat, int N, int arity, int depth, tm_topology_t topology, double obj_weight, double comm_speed)
double	speed (int depth)
tree_t *	build_tree_from_topology (tm_topology_t topology, double tab, int N, double obj_weight, double *comm_speed)