A tree of clusters (=variables, functions, constraints) More...

#include <cluster_tree.hpp>

Classes
struct	edge_info_t
	information at an edge of the tree More...

struct	vertex_info_t
	information at a vertex (=cluster/bag) of the tree More...

Public Types
using	feature_network_t = FeatureNetwork< FunValue, EvaluationPolicy >

using	evaluation_policy_t = typename feature_network_t::evaluation_policy_t
	evaluation policy type

using	var_idx_t = typename feature_network_t::var_idx_t

using	cluster_t = typename feature_network_t::cluster_t

using	assignment_t = typename feature_network_t::assignment_t

using	fun_value_t = typename feature_network_t::fun_value_t

using	constraint_t = typename feature_network_t::constraint_t

using	function_t = typename feature_network_t::function_t

using	message_t = MaterializedFunction< fun_value_t >

using	tree_t = graph::adjacency_list< vertex_info_t, edge_info_t >

using	vertex_descriptor_t = typename tree_t::vertex_descriptor_t
	type of identifiers of vertices (typically 'long int')

Public Member Functions
	ClusterTree ()
	construct empty

	ClusterTree (const FiniteDomainVector &domains)
	Construct with variable domains.

	ClusterTree (std::vector< int > domsizes)
	construct from vector of upper bounds

	ClusterTree (int num_vars, const FiniteDomain &domain)
	Construct with uniform domains.

	ClusterTree (int num_vars, int domsize)
	Construct with uniform domains.

	~ClusterTree ()

const auto &	feature_network () const
	read access to constraint network

auto	add_root_cluster (const std::vector< var_idx_t > &vars)
	add new root cluster to the tree

auto	add_child_cluster (vertex_descriptor_t parent, const std::vector< int > &vars)
	add new child cluster to the tree

void	add_constraint (vertex_descriptor_t node, const std::shared_ptr< constraint_t > &x)
	add new constraint to cluster

void	add_function (vertex_descriptor_t node, const std::shared_ptr< function_t > &x)
	add new function to cluster

auto	evaluate ()
	Evaluate the cluster tree (by DP)

bool	is_consistent ()
	Check consistency.

auto	traceback ()
	Generate a traceback.

auto	restricted_traceback (const std::set< var_idx_t > &variables, const assignment_t &assignment)
	Generate a restricted traceback.

Detailed Description

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>
class ired::ClusterTree< FunValue, EvaluationPolicy >

A tree of clusters (=variables, functions, constraints)

A cluster tree belongs to a constraint network and holds it. (The latter simplifies the usage in Infrared; however this means, we do not support several cluster trees for the same constraint network.)

The cluster tree supports evaluation and sampling. For this purpose, the cluster tree must satisfy the cluster tree properties

1) For each variable in the CN, there is one bag that contains the variable.

2) For each variable, the bags that contain this variable form a subtree.

3) For each function, there is exactly one bag that contains the function and its variables.

4) For each constraint, there is at least one bag that contains the function and its variables. Constraints are only assigned to bags that contain all of their variables.

Ensuring those properties is the job of the user of this class!

Member Typedef Documentation

◆ assignment_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::assignment_t = typename feature_network_t::assignment_t

◆ cluster_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::cluster_t = typename feature_network_t::cluster_t

◆ constraint_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::constraint_t = typename feature_network_t::constraint_t

◆ evaluation_policy_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::evaluation_policy_t = typename feature_network_t::evaluation_policy_t

evaluation policy type

◆ feature_network_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::feature_network_t = FeatureNetwork<FunValue, EvaluationPolicy>

◆ fun_value_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::fun_value_t = typename feature_network_t::fun_value_t

◆ function_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::function_t = typename feature_network_t::function_t

◆ message_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::message_t = MaterializedFunction<fun_value_t>

◆ tree_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::tree_t = graph::adjacency_list<vertex_info_t, edge_info_t>

◆ var_idx_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::var_idx_t = typename feature_network_t::var_idx_t

◆ vertex_descriptor_t

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

using ired::ClusterTree< FunValue, EvaluationPolicy >::vertex_descriptor_t = typename tree_t::vertex_descriptor_t

type of identifiers of vertices (typically 'long int')

Constructor & Destructor Documentation

◆ ClusterTree() [1/5]

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

ired::ClusterTree< FunValue, EvaluationPolicy >::ClusterTree ( )

inline

construct empty

◆ ClusterTree() [2/5]

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

ired::ClusterTree< FunValue, EvaluationPolicy >::ClusterTree ( const FiniteDomainVector & domains )

inlineexplicit

Construct with variable domains.

Parameters

domsizes vector of domain sizes for each variable; its length specifies the number of variables

◆ ClusterTree() [3/5]

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

ired::ClusterTree< FunValue, EvaluationPolicy >::ClusterTree ( std::vector< int > domsizes )

inlineexplicit

construct from vector of upper bounds

◆ ClusterTree() [4/5]

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

ired::ClusterTree< FunValue, EvaluationPolicy >::ClusterTree	(	int	num_vars,
		const FiniteDomain &	domain
	)

inline

Construct with uniform domains.

Parameters

num_vars	the number of variables in the underlying constraint network
domsize	uniform domain size of each variable

◆ ClusterTree() [5/5]

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

ired::ClusterTree< FunValue, EvaluationPolicy >::ClusterTree	(	int	num_vars,
		int	domsize
	)

inline

Construct with uniform domains.

Parameters

num_vars	the number of variables in the underlying constraint network
domsize	uniform domain size of each variable

◆ ~ClusterTree()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

ired::ClusterTree< FunValue, EvaluationPolicy >::~ClusterTree ( )

inline

Member Function Documentation

◆ add_child_cluster()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

auto ired::ClusterTree< FunValue, EvaluationPolicy >::add_child_cluster	(	vertex_descriptor_t	parent,
		const std::vector< int > &	vars
	)

inline

add new child cluster to the tree

Parameters

parent	the parent of this child
vars	variables of the new cluster

Returns: bag/cluster id

Typically used when constructing the cluster tree. Typically, one adds functions and constraints to the new cluster that is created by this method (using the returned bag id).

◆ add_constraint()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

void ired::ClusterTree< FunValue, EvaluationPolicy >::add_constraint	(	vertex_descriptor_t	node,
		const std::shared_ptr< constraint_t > &	x
	)

inline

add new constraint to cluster

Parameters

id	identifier of cluster
x	(shared pointer to) constraint

Typically used when constructing the cluster tree.

◆ add_function()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

void ired::ClusterTree< FunValue, EvaluationPolicy >::add_function	(	vertex_descriptor_t	node,
		const std::shared_ptr< function_t > &	x
	)

inline

add new function to cluster

Parameters

id	identifier of cluster
x	(shared pointer to) function

Typically used when constructing the cluster tree.

◆ add_root_cluster()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

auto ired::ClusterTree< FunValue, EvaluationPolicy >::add_root_cluster ( const std::vector< var_idx_t > & vars )

inline

add new root cluster to the tree

Parameters

vars	variables of the new cluster

Returns: bag/cluster id

Typically used when constructing the cluster tree. Typically, one adds functions and constraints to the new cluster that is created by this method (using the returned bag id).

◆ evaluate()

template<class FunValue , class EvaluationPolicy >

auto ired::ClusterTree< FunValue, EvaluationPolicy >::evaluate

Evaluate the cluster tree (by DP)

Returns: evaluation result

Call this once before generating tracebacks with traceback()

Note: multiple calls will not rerun the evaluation algorithm, but return the stored evaluation result

◆ feature_network()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

const auto & ired::ClusterTree< FunValue, EvaluationPolicy >::feature_network ( ) const

inline

read access to constraint network

◆ is_consistent()

template<class FunValue = double, class EvaluationPolicy = StdEvaluationPolicy<FunValue>>

bool ired::ClusterTree< FunValue, EvaluationPolicy >::is_consistent ( )

inline

Check consistency.

Returns: whether the ct is consistent

Note: Implicitely evaluates the cluster tree by calling

See also: evaluate(). Consequently, after this method returned true, valid tracebacks can be produced by; traceback().

◆ restricted_traceback()

template<class FunValue , class EvaluationPolicy >

auto ired::ClusterTree< FunValue, EvaluationPolicy >::restricted_traceback	(	const std::set< var_idx_t > &	variables,
		const assignment_t &	assignment
	)

Generate a restricted traceback.

Parameters

variables	list of variables to which trace is restricted
assignment	assignment of the other variables

Returns: assignment obtained by restricted traceback

See also: traceback

◆ traceback()

template<class FunValue , class EvaluationPolicy >

auto ired::ClusterTree< FunValue, EvaluationPolicy >::traceback

Generate a traceback.

Returns: assignment obtained by traceback

Note: The nature of this traceback depends on the evaluation policy!

Generates one traceback assignment. Requires that the cluster tree was evaluated and is consistent. Arbitrarily many tracebacks can be generated after a single evaluation (which is of course mostly reasonable for non-det tb, like stochastic traceback)

Results are NOT defined if the cluster tree was never evaluated (due to a call to evaluate() or is_consistent()) or is not consistent. Calling traceback on an inconsistent tree may even result in termination.

On evaluated and consistent trees, stochastic traceback, samples from a distribution controlled by the functions and constraints. When the functions return Boltzmann weights, assignments are traced back from a Boltzmann distribution.

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

src/infrared/cluster_tree.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ assignment_t

◆ cluster_t

◆ constraint_t

◆ evaluation_policy_t

◆ feature_network_t

◆ fun_value_t

◆ function_t

◆ message_t

◆ tree_t

◆ var_idx_t

◆ vertex_descriptor_t

Constructor & Destructor Documentation

◆ ClusterTree() [1/5]

◆ ClusterTree() [2/5]

◆ ClusterTree() [3/5]

◆ ClusterTree() [4/5]

◆ ClusterTree() [5/5]

◆ ~ClusterTree()

Member Function Documentation

◆ add_child_cluster()

◆ add_constraint()

◆ add_function()

◆ add_root_cluster()

◆ evaluate()

◆ feature_network()

◆ is_consistent()

◆ restricted_traceback()

◆ traceback()