cadabra::Algorithm Class Reference

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 std::set< Ex, tree_exact_less_obj >	Ex_set_t
typedef Ex::result_t	result_t
Public Types inherited from cadabra::ExManip
typedef Ex::iterator_base	iterator_base
typedef Ex::iterator	iterator
typedef Ex::post_order_iterator	post_order_iterator
typedef Ex::sibling_iterator	sibling_iterator

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.
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.
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').
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.
bool	check_consistency (iterator) const
	Given an expression top node, check index consistency.
bool	check_index_consistency (iterator) const
bool	check_degree_consistency (iterator) const
	Given an expression top node, check differential form degree consistency.
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)
std::string	get_index_set_name (iterator it) const
bool	rename_replacement_dummies (iterator, bool still_inside_algo=false)
	Rename the dummies in the sub-tree starting with head at the given iterator.
Ex_set_t	dependencies (iterator it, bool include_derivatives_of=true) const
	Determine all the Coordinate dependencies of the object at 'it'.
bool	derivative_acts_on (iterator it) const
	Is this a symbol on which a derivative acts?
Public Member Functions inherited from cadabra::ExManip
	ExManip (const Kernel &, Ex &)
bool	prod_wrap_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.
bool	prod_unwrap_single_term (iterator &)
bool	sum_wrap_single_term (iterator &)
bool	sum_unwrap_single_term (iterator &)
bool	is_single_term (iterator)
	Is the indicated node a single term in an expression?
bool	is_nonprod_factor_in_prod (iterator)
void	force_node_wrap (iterator &, std::string)
	Wrap a term in a product or sum in a node with indicated name, irrespective of its parent (it usually makes more sense to call the safer prod_wrap_single_term or sum_wrap_single_term above).

Static Public Member Functions
static unsigned int	number_of_indices (const Properties &, iterator it)
static unsigned int	number_of_direct_indices (iterator it)
static bool	is_termlike (iterator)
	Determines whether the indicated node is 'like a term in a sum'.
static bool	is_noncommuting (const Properties &, iterator)
	Determines whether the indicated node is 'like a factor in a product'.

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.
typedef std::vector< range_t >	range_vector_t

Protected Member Functions
virtual bool	can_apply (iterator)=0
virtual result_t	apply (iterator &)=0
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	separated_by_derivative (iterator, iterator, iterator check_dependence) const
	Figure out whether two objects (commonly indices) are separated by a derivative operator, as in.
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.
void	node_zero (iterator)
void	node_one (iterator)
void	node_integer (iterator, int)

Static Protected Member Functions
static bool	compare_ (const str_node &, const str_node &)

Protected Attributes
ProgressMonitor *	pm
bool	traverse_ldots
Protected Attributes inherited from cadabra::ExManip
const Kernel &	kernel
Ex &	tr

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.

Member Typedef Documentation

Ex_set_t

typedef std::set<Ex, tree_exact_less_obj> cadabra::Algorithm::Ex_set_t

range_t

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

protected

Finding objects in sets.

range_vector_t

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

protected

result_t

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

Constructor & Destructor Documentation

Algorithm()

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::~Algorithm ( )

virtual

Member Function Documentation

apply()

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

protectedpure virtual

Implemented in cadabra::canonicalise, cadabra::collect_components, cadabra::collect_factors, cadabra::collect_terms, cadabra::combine, cadabra::complete, cadabra::component, cadabra::decompose, cadabra::decompose_product, cadabra::distribute, cadabra::drop_weight, cadabra::einsteinify, cadabra::eliminate_converter, cadabra::eliminate_kronecker, cadabra::epsilon_to_delta, cadabra::evaluate, cadabra::expand, cadabra::expand_delta, cadabra::expand_diracbar, cadabra::expand_dummies, cadabra::expand_power, cadabra::explicit_indices, cadabra::factor_in, cadabra::factor_out, cadabra::fierz, cadabra::first_order_form, cadabra::flatten_product, cadabra::flatten_sum, cadabra::indexsort, cadabra::integrate_by_parts, cadabra::join_gamma, cadabra::keep_terms, cadabra::keep_weight, cadabra::lower_free_indices, cadabra::lr_tensor, cadabra::map_mma, cadabra::map_sympy, cadabra::meld, cadabra::nevaluate, cadabra::nval, cadabra::order, cadabra::product_rule, cadabra::reduce_delta, cadabra::rename_dummies, cadabra::replace_match, cadabra::rewrite_indices, cadabra::simplify, cadabra::sort_product, cadabra::sort_spinors, cadabra::sort_sum, cadabra::split, cadabra::split_gamma, cadabra::split_index, cadabra::substitute, cadabra::sym, cadabra::tabdimension, cadabra::take_match, cadabra::untrace, cadabra::unwrap, cadabra::unzoom, cadabra::vary, cadabra::young_project, cadabra::young_project_product, cadabra::young_project_tensor, and cadabra::zoom.

apply_deep()

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

private

apply_generic() [1/2]

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.

apply_generic() [2/2]

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

apply_once()

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

private

apply_pre_order()

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.

begin_index()

index_iterator Algorithm::begin_index

(

iterator

it

)

const

can_apply()

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

protectedpure virtual

Implemented in cadabra::canonicalise, cadabra::collect_components, cadabra::collect_factors, cadabra::collect_terms, cadabra::combine, cadabra::complete, cadabra::component, cadabra::decompose, cadabra::decompose_product, cadabra::distribute, cadabra::drop_keep_weight, cadabra::einsteinify, cadabra::eliminate_converter, cadabra::eliminate_kronecker, cadabra::epsilon_to_delta, cadabra::evaluate, cadabra::expand, cadabra::expand_delta, cadabra::expand_diracbar, cadabra::expand_dummies, cadabra::expand_power, cadabra::explicit_indices, cadabra::factor_in, cadabra::factor_out, cadabra::fierz, cadabra::first_order_form, cadabra::flatten_product, cadabra::flatten_sum, cadabra::indexsort, cadabra::integrate_by_parts, cadabra::join_gamma, cadabra::keep_terms, cadabra::lower_free_indices, cadabra::lr_tensor, cadabra::map_mma, cadabra::map_sympy, cadabra::meld, cadabra::nevaluate, cadabra::nval, cadabra::order, cadabra::product_rule, cadabra::reduce_delta, cadabra::rename_dummies, cadabra::replace_match, cadabra::rewrite_indices, cadabra::simplify, cadabra::sort_product, cadabra::sort_spinors, cadabra::sort_sum, cadabra::split, cadabra::split_gamma, cadabra::split_index, cadabra::substitute, cadabra::sym, cadabra::tabdimension, cadabra::take_match, cadabra::untrace, cadabra::unwrap, cadabra::unzoom, cadabra::vary, cadabra::young_project, cadabra::young_project_product, cadabra::young_project_tensor, and cadabra::zoom.

check_consistency()

bool Algorithm::check_consistency

(

iterator

it

)

const

Given an expression top node, check index consistency.

check_degree_consistency()

bool Algorithm::check_degree_consistency

(

iterator

)

const

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

check_index_consistency()

bool Algorithm::check_index_consistency

(

iterator

it

)

const

compare_()

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

staticprotected

contains()

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

protected

dependencies()

std::set< Ex, tree_exact_less_obj > Algorithm::dependencies	(	iterator	it,
		bool	include_derivatives_of = true ) const

Determine all the Coordinate dependencies of the object at 'it'.

If the flag is false, do not include derivatives of these coordinates (e.g. when coordinates are dependent on parameters and derivatives wrt. these parameters are present, do not include these as dependencies).

derivative_acts_on()

bool Algorithm::derivative_acts_on

(

iterator

it

)

const

Is this a symbol on which a derivative acts?

end_index()

index_iterator Algorithm::end_index

(

iterator

it

)

const

find_arg_superset() [1/2]

template<class Iter>

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

protected

find_arg_superset() [2/2]

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

protected

find_argument_lists()

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

protected

get_index_set_name()

std::string Algorithm::get_index_set_name

(

iterator

it

)

const

intersection_number()

template<class BinaryPredicate>

unsigned int cadabra::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.

is_noncommuting()

bool Algorithm::is_noncommuting ( const Properties & properties, iterator it )

static

Determines whether the indicated node is 'like a factor in a product'.

This requires that the parent is a `\prod' node. */ static bool is_factorlike(iterator);

/** Generic function to determine if there is any kind of non-commutativity associated to the given object. Useful as quick check for algorithms that do not (yet) handle non-commuting behaviour.

is_termlike()

bool Algorithm::is_termlike ( iterator it )

static

Determines whether the indicated node is 'like a term in a sum'.

This requires that the node is not a \sum node, not a child of a \prod node, and that its parent rel is of argument-type (p_none).

locate_object_set()

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

protected

locate_single_object()

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

protected

node_integer()

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

protected

node_one()

void Algorithm::node_one ( iterator it )

protected

node_zero()

void Algorithm::node_zero ( iterator it )

protected

number_of_direct_indices()

unsigned int cadabra::Algorithm::number_of_direct_indices ( iterator it )

static

number_of_indices() [1/2]

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

static

number_of_indices() [2/2]

unsigned int Algorithm::number_of_indices

(

iterator

it

)

propagate_zeroes()

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

pushup_multiplier()

void Algorithm::pushup_multiplier ( iterator it )

protected

rename_replacement_dummies()

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

Rename the dummies in the sub-tree starting with head at the given iterator.

Ensures that no dummies in this sub-tree overlap with the indices elsewhere in the tree.

report_progress()

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

separated_by_derivative()

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

set_progress_monitor()

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

discard_command_node

bool cadabra::Algorithm::discard_command_node

get_dummy_sw

Stopwatch cadabra::Algorithm::get_dummy_sw

mutable

index_sw

Stopwatch cadabra::Algorithm::index_sw

mutable

interrupted

bool cadabra::Algorithm::interrupted

number_of_calls

unsigned int cadabra::Algorithm::number_of_calls

number_of_modifications

unsigned int cadabra::Algorithm::number_of_modifications

pm

ProgressMonitor* cadabra::Algorithm::pm

protected

report_progress_stopwatch

Stopwatch cadabra::Algorithm::report_progress_stopwatch

mutable

suppress_normal_output

bool cadabra::Algorithm::suppress_normal_output

traverse_ldots

bool cadabra::Algorithm::traverse_ldots

protected

---

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

• core/Algorithm.hh
• core/Algorithm.cc