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 *new, tree_t *old)
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().

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

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

long int choose	(	long	n,
		long	k
	)

Definition at line 52 of file tm_tree.c.

Referenced by group_nodes().

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

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, printf(), _tree_t::uniq, and _tree_t::val.

void clone_tree	(	tree_t *	new,
		tree_t *	old
	)

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

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

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

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

void free_tab_int	(	int **	tab,
		int	N
	)

Definition at line 156 of file tm_tree.c.

References free().

void display_tab	(	double **	tab,
		int	N
	)

Definition at line 164 of file tm_tree.c.

References printf().

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

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

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

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 242 of file tm_tree.c.

References add_to_list(), and eval_grouping().

Referenced by group_nodes().

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

Definition at line 266 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().

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

Definition at line 286 of file tm_tree.c.

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

Referenced by recurs_select_independent_groups(), and test_independent_groups().

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

Definition at line 306 of file tm_tree.c.

References printf().

Referenced by select_independent_groups().

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

Definition at line 317 of file tm_tree.c.

References printf().

Referenced by fast_grouping(), and super_fast_grouping().

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 329 of file tm_tree.c.

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

Referenced by select_independent_groups(), and test_independent_groups().

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

void delete_group_list

(

group_list_t *

list

)

Definition at line 381 of file tm_tree.c.

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

Referenced by group_nodes().

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

Definition at line 391 of file tm_tree.c.

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

Referenced by group_nodes().

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

Definition at line 402 of file tm_tree.c.

References e1, and _group_list_t::val.

Referenced by group_nodes().

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

Definition at line 414 of file tm_tree.c.

References e1, and _group_list_t::val.

Referenced by group_nodes().

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

Definition at line 426 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 438 of file tm_tree.c.

References e1, and _group_list_t::wg.

Referenced by group_nodes().

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 449 of file tm_tree.c.

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

Referenced by group_nodes().

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 480 of file tm_tree.c.

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

Referenced by group_nodes().

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

Definition at line 514 of file tm_tree.c.

References _group_list_t::next.

Referenced by group_nodes().

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

Definition at line 530 of file tm_tree.c.

References printf().

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

Definition at line 539 of file tm_tree.c.

Referenced by compute_weighted_degree().

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

Definition at line 555 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().

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 587 of file tm_tree.c.

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

Referenced by CpdList_objectNames::add(), arg_init(), CpdPythonGroup::buildIterator(), CpdPython::CpdPython(), PythonObject::print(), PythonObject::replyIntValue(), and searchResults::unpack().

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 633 of file tm_tree.c.

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

Referenced by fast_grouping().

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 678 of file tm_tree.c.

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

Referenced by group_nodes().

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

Definition at line 712 of file tm_tree.c.

References e1, and adjacency_t::val.

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

Definition at line 724 of file tm_tree.c.

References e1, and adjacency_t::val.

Referenced by super_fast_grouping().

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 734 of file tm_tree.c.

References adjacency_dsc(), display_grouping(), adjacency_t::i, adjacency_t::j, malloc(), printf(), qsort(), try_add_edge(), update_val(), _tree_t::val, and adjacency_t::val.

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

Definition at line 792 of file tm_tree.c.

References malloc(), and printf().

Referenced by group_nodes().

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 831 of file tm_tree.c.

References _tree_t::arity, 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(), list, list_all_possible_groups(), list_to_tab(), malloc(), n, _group_list_t::next, _tree_t::parent, printf(), 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().

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

Definition at line 976 of file tm_tree.c.

References malloc().

Referenced by build_level_topology().

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

Definition at line 999 of file tm_tree.c.

References malloc().

Referenced by build_level_topology().

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

Definition at line 1030 of file tm_tree.c.

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

Referenced by complete_tab_node().

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

Definition at line 1054 of file tm_tree.c.

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

Referenced by build_level_topology().

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

Definition at line 1081 of file tm_tree.c.

References _tree_t::tab_child.

Referenced by build_level_topology().

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 1103 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(), printf(), set_deb_tab_child(), set_node(), and speed().

Referenced by build_tree_from_topology().

double speed

(

int

depth

)

Definition at line 1196 of file tm_tree.c.

Referenced by arg_init(), build_level_topology(), and build_synthetic_topology_old().

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

Definition at line 1209 of file tm_tree.c.

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

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