![]() |
Cadabra
Computer algebra system for field theory problems
|
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>
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. | |
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. |
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. | |
void | pushup_multiplier (iterator) |
Determines whether the indicated node is 'like a factor in a product'. | |
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) |
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. | |
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'. | |
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. | |
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. | |
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. |
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'. |
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 Attributes | |
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. |
typedef Ex::iterator cadabra::Algorithm::iterator |
typedef Ex::post_order_iterator cadabra::Algorithm::post_order_iterator |
typedef Ex::sibling_iterator cadabra::Algorithm::sibling_iterator |
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.
|
virtual |
|
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 ) |
|
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 |
bool Algorithm::check_consistency | ( | iterator | it | ) | const |
Given an expression top node, check index consistency.
bool Algorithm::check_degree_consistency | ( | iterator | ) | const |
Given an expression top node, check differential form degree consistency.
bool Algorithm::check_index_consistency | ( | iterator | it | ) | const |
index_iterator Algorithm::end_index | ( | iterator | it | ) | const |
std::string Algorithm::get_index_set_name | ( | iterator | it | ) | const |
unsigned int cadabra::Algorithm::intersection_number | ( | sibling_iterator | from1, |
sibling_iterator | to1, | ||
sibling_iterator | from2, | ||
sibling_iterator | to2, | ||
BinaryPredicate | fun ) const |
Determine the number of elements in the first range which also occur in the second range.
|
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).
void Algorithm::node_integer | ( | iterator | it, |
int | num ) |
void Algorithm::node_one | ( | iterator | it | ) |
void Algorithm::node_zero | ( | iterator | it | ) |
|
static |
|
static |
unsigned int Algorithm::number_of_indices | ( | iterator | it | ) |
|
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 | ) |
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. static bool is_noncommuting(const Properties&, iterator);
protected: Ex& tr; ProgressMonitor *pm;
The main entry point which is used by the public entry points listed above. Override these in any subclass.
virtual bool can_apply(iterator)=0; virtual result_t apply(iterator&)=0;
Index stuff int index_parity(iterator) const; static bool less_without_numbers(nset_t::iterator, nset_t::iterator); static bool equal_without_numbers(nset_t::iterator, nset_t::iterator);
/ Finding objects in sets. typedef std::pair<sibling_iterator, sibling_iterator> range_t; typedef std::vector<range_t> range_vector_t;
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);
Locate objects inside the tree (formerly in the 'locate' algorithm). 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); static bool compare_(const str_node&, const str_node&);
bool is_single_term(iterator); bool is_nonprod_factor_in_prod(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_wrap_single_term(iterator&); bool prod_unwrap_single_term(iterator&); bool sum_wrap_single_term(iterator&); bool sum_unwrap_single_term(iterator&);
/ 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. void force_node_wrap(iterator&, std::string);
/ 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). bool separated_by_derivative(iterator, iterator, iterator check_dependence) const;
Given a node with non-zero multiplier, distribute this multiplier up the tree when the node is a \sum node, or push it into the \prod node if that is the parent. Do this recursively
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.
void Algorithm::report_progress | ( | const std::string & | , |
int | todo, | ||
int | done, | ||
int | count = 2 ) |
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.
bool cadabra::Algorithm::discard_command_node |
|
mutable |
|
mutable |
bool cadabra::Algorithm::interrupted |
unsigned int cadabra::Algorithm::number_of_calls |
unsigned int cadabra::Algorithm::number_of_modifications |
|
mutable |
bool cadabra::Algorithm::suppress_normal_output |
|
protected |