Description

Base class for all algorithms, containing generic routines and in particular the logic for index classification.

Also contains static algorithms acting on Ex objects which require property information and can therefore not be a member of Ex.

In order to implement a new algorithm, subclass Algorithm and implement the abstract members Algorithm::can_apply and Algorithm::apply (see there for further documentation). The general logic is that the implementation of Algorithm::apply(iterator&) is not allowed to make the node pointed at by the iterator invalid. If the algorithm makes the node vanish, it should indicate so by setting its multiplier to zero; the calling logic will then take care of cleaning up the subtree at the node.

The algorithm is, however, allowed to change the node itself or replace it with another one, as long as it updates the iterator.

#include <Algorithm.hh>

Inheritance diagram for cadabra::Algorithm:

Public Types
typedef Ex::iterator	iterator

typedef Ex::post_order_iterator	post_order_iterator

typedef Ex::sibling_iterator	sibling_iterator

typedef Ex::result_t	result_t

typedef std::multimap< Ex, Ex::iterator, tree_exact_less_for_indexmap_obj >	index_map_t
	A map from a pattern to the position where it occurs in the tree. More...

typedef std::map< Ex::iterator, int, Ex::iterator_base_less >	index_position_map_t
	A map from the position of each index to the sequential index. More...

Public Member Functions
	Algorithm (const Kernel &, Ex &)
	Initialise the algorithm with a reference to the expression tree, but do not yet do anything with this tree. More...

virtual	~Algorithm ()

void	set_progress_monitor (ProgressMonitor *)
	Provide the algorithm with a ProgressMonitor object on which to register (nested) progress information, to be reported out-of-band to a client. More...

result_t	apply_generic (bool deep=true, bool repeat=false, unsigned int depth=0)
	The main entry points for running algorithms, which traverse the tree post-order ('child before parent'). More...

result_t	apply_generic (iterator &, bool deep, bool repeat, unsigned int depth)

result_t	apply_pre_order (bool repeat=false)
	Apply algorithm with alternative traversal: starting from the top node, traverse the tree pre-order ('parent before child') and once the algorithm acts at a given node, do not traverse the subtree below anymore. More...

bool	check_consistency (iterator) const
	Given an expression top node, check index consistency. More...

bool	check_index_consistency (iterator) const

bool	check_degree_consistency (iterator) const
	Given an expression top node, check differential form degree consistency. More...

void	report_progress (const std::string &, int todo, int done, int count=2)

index_iterator	begin_index (iterator it) const

index_iterator	end_index (iterator it) const

unsigned int	number_of_indices (iterator it)

bool	rename_replacement_dummies (iterator, bool still_inside_algo=false)

Static Public Member Functions
static unsigned int	number_of_indices (const Properties &, iterator it)

static unsigned int	number_of_direct_indices (iterator it)

Public Attributes
bool	interrupted

unsigned int	number_of_calls

unsigned int	number_of_modifications

bool	suppress_normal_output

bool	discard_command_node

Stopwatch	index_sw

Stopwatch	get_dummy_sw

Stopwatch	report_progress_stopwatch

Protected Types
typedef std::pair < sibling_iterator, sibling_iterator >	range_t
	Finding objects in sets. More...

typedef std::vector< range_t >	range_vector_t

Protected Member Functions
virtual bool	can_apply (iterator)=0

virtual result_t	apply (iterator &)=0

int	index_parity (iterator) const

bool	contains (sibling_iterator from, sibling_iterator to, sibling_iterator arg)

void	find_argument_lists (range_vector_t &, bool only_comma_lists=true) const

template<class Iter >
range_vector_t::iterator	find_arg_superset (range_vector_t &, Iter st, Iter nd)

range_vector_t::iterator	find_arg_superset (range_vector_t &, sibling_iterator it)

unsigned int	locate_single_object (Ex::iterator obj_to_find, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)

bool	locate_object_set (const Ex &objs, Ex::iterator st, Ex::iterator nd, std::vector< unsigned int > &store)

bool	is_termlike (iterator)
	Determine structure (version-2) More...

bool	is_factorlike (iterator)

bool	is_single_term (iterator)
	Take a single non-product node in a sum and wrap it in a product node, so it can be handled on the same footing as a proper product. More...

bool	is_nonprod_factor_in_prod (iterator)

bool	prod_wrap_single_term (iterator &)

bool	prod_unwrap_single_term (iterator &)

void	force_prod_wrap (iterator &)
	Wrap a term in a product, irrespective of its parent (it usually makes more sense to call the safer prod_wrap_single_term above). More...

bool	separated_by_derivative (iterator, iterator, iterator check_dependence) const
	Figure out whether two objects (commonly indices) are separated by a derivative operator, as in \[ \partial_{a}{A_{b}} C^{b} \] . More...

void	pushup_multiplier (iterator)

template<class BinaryPredicate >
unsigned int	intersection_number (sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, BinaryPredicate) const
	Determine the number of elements in the first range which also occur in the second range. More...

void	node_zero (iterator)

void	node_one (iterator)

void	node_integer (iterator, int)

void	fill_index_position_map (iterator, const index_map_t &, index_position_map_t &) const
	Index manipulation and classification. More...

void	fill_map (index_map_t &, sibling_iterator, sibling_iterator) const

void	print_classify_indices (std::ostream &, iterator) const

void	determine_intersection (index_map_t &one, index_map_t &two, index_map_t &target, bool move_out=false) const

void	classify_add_index (iterator it, index_map_t &ind_free, index_map_t &ind_dummy) const

void	classify_indices_up (iterator, index_map_t &ind_free, index_map_t &ind_dummy) const

void	classify_indices (iterator, index_map_t &ind_free, index_map_t &ind_dummy) const

int	max_numbered_name_one (const std::string &nm, const index_map_t *one) const

int	max_numbered_name (const std::string &, const index_map_t m1, const index_map_t m2=0, const index_map_t m3=0, const index_map_t m4=0, const index_map_t *m5=0) const

Ex	get_dummy (const list_property , const index_map_t m1, const index_map_t m2=0, const index_map_t m3=0, const index_map_t m4=0, const index_map_t m5=0) const

Ex	get_dummy (const list_property *, iterator) const

Ex	get_dummy (const list_property *, iterator, iterator) const

bool	index_in_set (Ex, const index_map_t *) const

index_map_t::iterator	find_modulo_parent_rel (iterator it, index_map_t &imap) const
	Find an index in the set, not taking into account index position. More...

Static Protected Member Functions
static bool	less_without_numbers (nset_t::iterator, nset_t::iterator)

static bool	equal_without_numbers (nset_t::iterator, nset_t::iterator)

static bool	compare_ (const str_node &, const str_node &)

Protected Attributes
const Kernel &	kernel

Ex &	tr

ProgressMonitor *	pm

Private Member Functions
result_t	apply_once (Ex::iterator &it)

result_t	apply_deep (Ex::iterator &it)

void	propagate_zeroes (post_order_iterator &, const iterator &)
	Given a node with zero multiplier, propagate this zero upwards in the tree. More...

void	dumpmap (std::ostream &, const index_map_t &) const

Member Typedef Documentation

typedef std::multimap<Ex, Ex::iterator, tree_exact_less_for_indexmap_obj> cadabra::Algorithm::index_map_t

A map from a pattern to the position where it occurs in the tree.

The comparator is such that we store indices exactly, apart from their multiplicative factor. This means that the index in A_{n} and in A_{-n} are stored in the same way, and one needs to lookup the expression in the tree to find this multiplier. See basic.cdb test 26 for an example that uses this.

typedef std::map<Ex::iterator, int, Ex::iterator_base_less> cadabra::Algorithm::index_position_map_t

A map from the position of each index to the sequential index.

typedef Ex::iterator cadabra::Algorithm::iterator

typedef Ex::post_order_iterator cadabra::Algorithm::post_order_iterator

typedef std::pair<sibling_iterator, sibling_iterator> cadabra::Algorithm::range_t

protected

Finding objects in sets.

typedef std::vector<range_t> cadabra::Algorithm::range_vector_t

protected

typedef Ex::result_t cadabra::Algorithm::result_t

typedef Ex::sibling_iterator cadabra::Algorithm::sibling_iterator

Constructor & Destructor Documentation

Algorithm::Algorithm	(	const Kernel &	k,
		Ex &	tr_
	)

Initialise the algorithm with a reference to the expression tree, but do not yet do anything with this tree.

Algorithms are not typically allowed to mess with the settings in the Kernel, so it is passed const.

Algorithm::~Algorithm ( )

virtual

Member Function Documentation

virtual result_t cadabra::Algorithm::apply ( iterator & )

protectedpure virtual

Implemented in cadabra::evaluate, cadabra::keep_weight, cadabra::substitute, cadabra::drop_weight, cadabra::complete, cadabra::decompose_product, cadabra::distribute, cadabra::integrate_by_parts, cadabra::map_mma, cadabra::map_sympy, cadabra::vary, cadabra::canonicalise, cadabra::collect_components, cadabra::collect_factors, cadabra::collect_terms, cadabra::einsteinify, cadabra::factor_in, cadabra::factor_out, cadabra::fierz, cadabra::split_index, cadabra::young_project, cadabra::epsilon_to_delta, cadabra::split_gamma, cadabra::young_project_tensor, cadabra::combine, cadabra::eliminate_kronecker, cadabra::eliminate_converter, cadabra::expand, cadabra::expand_delta, cadabra::expand_diracbar, cadabra::expand_power, cadabra::flatten_product, cadabra::join_gamma, cadabra::keep_terms, cadabra::order, cadabra::reduce_delta, cadabra::rename_dummies, cadabra::replace_match, cadabra::rewrite_indices, cadabra::sort_product, cadabra::sort_spinors, cadabra::sort_sum, cadabra::sym, cadabra::take_match, cadabra::young_project_product, cadabra::indexsort, cadabra::lr_tensor, cadabra::flatten_sum, cadabra::product_rule, and cadabra::unwrap.

Algorithm::result_t Algorithm::apply_deep ( Ex::iterator & it )

private

Algorithm::result_t Algorithm::apply_generic	(	bool	deep = `true`,
		bool	repeat = `false`,
		unsigned int	depth = `0`
	)

The main entry points for running algorithms, which traverse the tree post-order ('child before parent').

The 'deep' flag indicates whether sub-expressions should be acted on too. The 'repeat' flag indicates whether the algorithm should be applied until the expression no longer changes. The 'depth' flag, if not equal to -1, indicates the depth in the tree where the algorithm should start applying.

Algorithm::result_t Algorithm::apply_generic	(	Ex::iterator &	it,
		bool	deep,
		bool	repeat,
		unsigned int	depth
	)

Algorithm::result_t Algorithm::apply_once ( Ex::iterator & it )

private

Algorithm::result_t Algorithm::apply_pre_order ( bool repeat = false )

Apply algorithm with alternative traversal: starting from the top node, traverse the tree pre-order ('parent before child') and once the algorithm acts at a given node, do not traverse the subtree below anymore.

index_iterator Algorithm::begin_index ( iterator it ) const

virtual bool cadabra::Algorithm::can_apply ( iterator )

protectedpure virtual

Implemented in cadabra::evaluate, cadabra::substitute, cadabra::complete, cadabra::decompose_product, cadabra::distribute, cadabra::integrate_by_parts, cadabra::map_mma, cadabra::map_sympy, cadabra::vary, cadabra::canonicalise, cadabra::collect_components, cadabra::collect_factors, cadabra::collect_terms, cadabra::drop_keep_weight, cadabra::einsteinify, cadabra::factor_in, cadabra::factor_out, cadabra::fierz, cadabra::split_index, cadabra::young_project, cadabra::epsilon_to_delta, cadabra::split_gamma, cadabra::young_project_tensor, cadabra::combine, cadabra::eliminate_kronecker, cadabra::eliminate_converter, cadabra::expand, cadabra::expand_delta, cadabra::expand_diracbar, cadabra::expand_power, cadabra::flatten_product, cadabra::join_gamma, cadabra::keep_terms, cadabra::order, cadabra::reduce_delta, cadabra::rename_dummies, cadabra::replace_match, cadabra::rewrite_indices, cadabra::sort_product, cadabra::sort_spinors, cadabra::sort_sum, cadabra::sym, cadabra::take_match, cadabra::young_project_product, cadabra::indexsort, cadabra::lr_tensor, cadabra::flatten_sum, cadabra::product_rule, and cadabra::unwrap.

bool Algorithm::check_consistency ( iterator it ) const

Given an expression top node, check index consistency.

bool Algorithm::check_degree_consistency ( iterator it ) const

Given an expression top node, check differential form degree consistency.

bool Algorithm::check_index_consistency ( iterator it ) const

void Algorithm::classify_add_index	(	iterator	it,
		index_map_t &	ind_free,
		index_map_t &	ind_dummy
	)		const

protected

void Algorithm::classify_indices	(	iterator	it,
		index_map_t &	ind_free,
		index_map_t &	ind_dummy
	)		const

protected

void Algorithm::classify_indices_up	(	iterator	it,
		index_map_t &	ind_free,
		index_map_t &	ind_dummy
	)		const

protected

bool Algorithm::compare_	(	const str_node &	one,
		const str_node &	two
	)

staticprotected

bool Algorithm::contains	(	sibling_iterator	from,
		sibling_iterator	to,
		sibling_iterator	arg
	)

protected

void Algorithm::determine_intersection	(	index_map_t &	one,
		index_map_t &	two,
		index_map_t &	target,
		bool	move_out = `false`
	)		const

protected

void Algorithm::dumpmap	(	std::ostream &	str,
		const index_map_t &	mp
	)		const

private

index_iterator Algorithm::end_index ( iterator it ) const

bool Algorithm::equal_without_numbers	(	nset_t::iterator	it1,
		nset_t::iterator	it2
	)

staticprotected

void Algorithm::fill_index_position_map	(	iterator	prodnode,
		const index_map_t &	im,
		index_position_map_t &	ipm
	)		const

protected

Index manipulation and classification.

Routines to find and classify all indices in an expression, taking into account sums and products. Note that dummy indices do not always come in pairs, for instance in expressions like a_{m n} ( b^{n p} + q^{n p} ) . Similarly, free indices can appear multiple times, as in a_{m} + b_{m} .

void Algorithm::fill_map	(	index_map_t &	mp,
		sibling_iterator	st,
		sibling_iterator	nd
	)		const

protected

template<class Iter >

Algorithm::range_vector_t::iterator Algorithm::find_arg_superset	(	range_vector_t &	ran,
		Iter	st,
		Iter	nd
	)

protected

Algorithm::range_vector_t::iterator Algorithm::find_arg_superset	(	range_vector_t &	ran,
		sibling_iterator	it
	)

protected

void cadabra::Algorithm::find_argument_lists	(	range_vector_t &	,
		bool	only_comma_lists = `true`
	)		const

protected

Algorithm::index_map_t::iterator Algorithm::find_modulo_parent_rel	(	iterator	it,
		index_map_t &	imap
	)		const

protected

Find an index in the set, not taking into account index position.

void Algorithm::force_prod_wrap ( iterator & it )

protected

Wrap a term in a product, irrespective of its parent (it usually makes more sense to call the safer prod_wrap_single_term above).

Ex Algorithm::get_dummy	(	const list_property *	dums,
		const index_map_t *	m1,
		const index_map_t *	m2 = `0`,
		const index_map_t *	m3 = `0`,
		const index_map_t *	m4 = `0`,
		const index_map_t *	m5 = `0`
	)		const

protected

Ex Algorithm::get_dummy	(	const list_property *	dums,
		iterator	it
	)		const

protected

Ex Algorithm::get_dummy	(	const list_property *	dums,
		iterator	it1,
		iterator	it2
	)		const

protected

bool Algorithm::index_in_set	(	Ex	ex,
		const index_map_t *	im
	)		const

protected

int Algorithm::index_parity ( iterator it ) const

protected

template<class BinaryPredicate >

unsigned int Algorithm::intersection_number	(	sibling_iterator	from1,
		sibling_iterator	to1,
		sibling_iterator	from2,
		sibling_iterator	to2,
		BinaryPredicate	fun
	)		const

protected

Determine the number of elements in the first range which also occur in the second range.

bool Algorithm::is_factorlike ( iterator it )

protected

bool Algorithm::is_nonprod_factor_in_prod ( iterator it )

protected

bool Algorithm::is_single_term ( iterator it )

protected

Take a single non-product node in a sum and wrap it in a product node, so it can be handled on the same footing as a proper product.

bool Algorithm::is_termlike ( iterator it )

protected

Determine structure (version-2)

bool Algorithm::less_without_numbers	(	nset_t::iterator	it1,
		nset_t::iterator	it2
	)

staticprotected

bool Algorithm::locate_object_set	(	const Ex &	objs,
		Ex::iterator	st,
		Ex::iterator	nd,
		std::vector< unsigned int > &	store
	)

protected

unsigned int Algorithm::locate_single_object	(	Ex::iterator	obj_to_find,
		Ex::iterator	st,
		Ex::iterator	nd,
		std::vector< unsigned int > &	store
	)

protected

int Algorithm::max_numbered_name	(	const std::string &	nm,
		const index_map_t *	m1,
		const index_map_t *	m2 = `0`,
		const index_map_t *	m3 = `0`,
		const index_map_t *	m4 = `0`,
		const index_map_t *	m5 = `0`
	)		const

protected

int Algorithm::max_numbered_name_one	(	const std::string &	nm,
		const index_map_t *	one
	)		const

protected

void Algorithm::node_integer	(	iterator	it,
		int	num
	)

protected

void Algorithm::node_one ( iterator it )

protected

void Algorithm::node_zero ( iterator it )

protected

unsigned int Algorithm::number_of_direct_indices ( iterator it )

static

unsigned int Algorithm::number_of_indices ( iterator it )

unsigned int Algorithm::number_of_indices	(	const Properties &	pr,
		iterator	it
	)

static

void Algorithm::print_classify_indices	(	std::ostream &	str,
		iterator	st
	)		const

protected

bool Algorithm::prod_unwrap_single_term ( iterator & it )

protected

bool Algorithm::prod_wrap_single_term ( iterator & it )

protected

void Algorithm::propagate_zeroes	(	post_order_iterator &	it,
		const iterator &	topnode
	)

private

Given a node with zero multiplier, propagate this zero upwards in the tree.

Changes the iterator so that it points to the next node in a post_order traversal (post_order: children first, then node). The second node is the topmost node, beyond which this routine is not allowed to touch the tree (i.e. the 2nd iterator will always remain valid).

void Algorithm::pushup_multiplier ( iterator it )

protected

bool Algorithm::rename_replacement_dummies	(	iterator	two,
		bool	still_inside_algo = `false`
	)

void Algorithm::report_progress	(	const std::string &	str,
		int	todo,
		int	done,
		int	count = `2`
	)

bool Algorithm::separated_by_derivative	(	iterator	i1,
		iterator	i2,
		iterator	check_dependence
	)		const

protected

Figure out whether two objects (commonly indices) are separated by a derivative operator, as in

\[ \partial_{a}{A_{b}} C^{b} \]

.

If the last iterator is pointing to a valid node, check whether it is independent of the derivative (using the Depends property).

void Algorithm::set_progress_monitor ( ProgressMonitor * pm_ )

Provide the algorithm with a ProgressMonitor object on which to register (nested) progress information, to be reported out-of-band to a client.

Member Data Documentation

bool cadabra::Algorithm::discard_command_node

Stopwatch cadabra::Algorithm::get_dummy_sw

mutable

Stopwatch cadabra::Algorithm::index_sw

mutable

bool cadabra::Algorithm::interrupted

const Kernel& cadabra::Algorithm::kernel

protected

unsigned int cadabra::Algorithm::number_of_calls

unsigned int cadabra::Algorithm::number_of_modifications

ProgressMonitor* cadabra::Algorithm::pm

protected

Stopwatch cadabra::Algorithm::report_progress_stopwatch

mutable

bool cadabra::Algorithm::suppress_normal_output

Ex& cadabra::Algorithm::tr

protected

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

core/Algorithm.hh
core/Algorithm.cc

Description

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Member Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation