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 Ex::iterator	iterator
typedef Ex::post_order_iterator	post_order_iterator
typedef Ex::sibling_iterator	sibling_iterator
typedef Ex::result_t	result_t
Public Types inherited from cadabra::IndexClassifier
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)
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. More...
Public Member Functions inherited from cadabra::IndexClassifier
	IndexClassifier (const Kernel &)
void	fill_index_position_map (Ex::iterator, const index_map_t &, index_position_map_t &) const
	Routines to find and classify all indices in an expression, taking into account sums and products. More...
void	fill_map (index_map_t &, Ex::sibling_iterator, Ex::sibling_iterator) const
void	print_classify_indices (std::ostream &, Ex::iterator) const
void	determine_intersection (index_map_t &one, index_map_t &two, index_map_t &target, bool move_out=false) const
	Determine those indices in 'two' which have a name which is identical to an index name occurring in 'one'. More...
void	classify_add_index (Ex::iterator it, index_map_t &ind_free, index_map_t &ind_dummy) const
void	classify_indices_up (Ex::iterator, index_map_t &ind_free, index_map_t &ind_dummy) const
	Classify indices bottom-up, that is, given a node, it goes up the tree to find. More...
void	classify_indices (Ex::iterator, index_map_t &ind_free, index_map_t &ind_dummy) const
	Classify indices top-down, that is, finds the free indices and all dummy index pairs used in the full subtree below a given node. More...
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 *, Ex::iterator) const
Ex	get_dummy (const list_property *, Ex::iterator, Ex::iterator) const
bool	index_in_set (Ex, const index_map_t *) const
void	dumpmap (std::ostream &, const index_map_t &) const
index_map_t::iterator	find_modulo_parent_rel (Ex::iterator it, index_map_t &imap) const
	Find an index in the set, not taking into account index position. More...

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'. More...
static bool	is_factorlike (iterator)
	Determines whether the indicated node is 'like a factor in a product'. More...

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_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 &)
bool	sum_wrap_single_term (iterator &)
bool	sum_unwrap_single_term (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). 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. 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)

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
Ex &	tr
ProgressMonitor *	pm
bool	traverse_ldots
Protected Attributes inherited from cadabra::IndexClassifier
const Kernel &	kernel

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

Member Typedef Documentation

iterator

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

post_order_iterator

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

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

sibling_iterator

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

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

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

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

end_index()

index_iterator Algorithm::end_index

(

iterator

it

)

const

equal_without_numbers()

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

staticprotected

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

force_node_wrap()

void Algorithm::force_node_wrap ( iterator &  it, std::string  nm  )

protected

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

Sets the iterator to the new node.

get_index_set_name()

std::string Algorithm::get_index_set_name

(

iterator

it

)

const

index_parity()

int Algorithm::index_parity ( iterator  it ) const

protected

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

bool Algorithm::is_factorlike ( iterator  it )

static

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

This requires that the parent is a ‘\prod’ node.

is_nonprod_factor_in_prod()

bool Algorithm::is_nonprod_factor_in_prod ( iterator  it )

protected

is_single_term()

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.

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

less_without_numbers()

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

staticprotected

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

)

prod_unwrap_single_term()

bool Algorithm::prod_unwrap_single_term ( iterator &  it )

protected

prod_wrap_single_term()

bool Algorithm::prod_wrap_single_term ( iterator &  it )

protected

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.

sum_unwrap_single_term()

bool Algorithm::sum_unwrap_single_term ( iterator &  it )

protected

sum_wrap_single_term()

bool Algorithm::sum_wrap_single_term ( iterator &  it )

protected

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

tr

Ex& cadabra::Algorithm::tr

protected

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