Cadabra
Computer algebra system for field theory problems
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 | List of all members
cadabra::Algorithm Class Referenceabstract

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:
cadabra::IndexClassifier cadabra::canonicalise cadabra::collect_components cadabra::collect_factors cadabra::collect_terms cadabra::combine cadabra::complete 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_power cadabra::explicit_indices cadabra::factor_in cadabra::factor_out cadabra::fierz cadabra::flatten_product cadabra::flatten_sum cadabra::indexsort cadabra::integrate_by_parts cadabra::join_gamma cadabra::keep_terms cadabra::lower_free_indices cadabra::map_mma cadabra::map_sympy 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_gamma cadabra::split_index cadabra::substitute cadabra::sym cadabra::tab_basics cadabra::tabdimension cadabra::take_match cadabra::untrace cadabra::unwrap cadabra::unzoom cadabra::vary cadabra::young_project cadabra::young_project_product cadabra::young_project_tensor cadabra::young_reduce cadabra::zoom

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_objindex_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)
 
- 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. 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
 
void classify_indices (Ex::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 *, 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)
 

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_iteratorrange_t
 Finding objects in sets. More...
 
typedef std::vector< range_trange_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)
 Determines whether the indicated node is 'like a term in a sum'. More...
 
bool is_factorlike (iterator)
 Determines whether the indicated node is 'like a factor in a product'. More...
 
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

\[ \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)
 

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

Extr
 
ProgressMonitorpm
 
bool traverse_ldots
 
- Protected Attributes inherited from cadabra::IndexClassifier
const Kernelkernel
 

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

Finding objects in sets.

◆ range_vector_t

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

◆ 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

◆ 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

◆ 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  it) const

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

◆ check_index_consistency()

bool Algorithm::check_index_consistency ( iterator  it) const

◆ compare_()

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

◆ index_parity()

int Algorithm::index_parity ( iterator  it) const
protected

◆ intersection_number()

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.

◆ is_factorlike()

bool Algorithm::is_factorlike ( iterator  it)
protected

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

This requires that the parent is a `' 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)
protected

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 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 Algorithm::number_of_direct_indices ( iterator  it)
static

◆ number_of_indices() [1/2]

unsigned int Algorithm::number_of_indices ( iterator  it)

◆ number_of_indices() [2/2]

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

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

◆ report_progress()

void Algorithm::report_progress ( const std::string &  str,
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: