From 8491991a4bbf69d75171558a6f74e3c1ffa20d30 Mon Sep 17 00:00:00 2001 From: Jean-Paul Pelteret Date: Sun, 5 May 2019 17:42:11 +0200 Subject: [PATCH] Add function to resolve explicit and cyclic dependencies in sub. maps --- .../changes/minor/20190505Jean-PaulPelteret-1 | 4 + .../sd/symengine_scalar_operations.h | 98 +++++++++++++++++++ .../sd/symengine_scalar_operations.cc | 55 +++++++++++ ...ubstitution_maps_cyclic_dependencies_01.cc | 61 ++++++++++++ ...itution_maps_cyclic_dependencies_01.output | 3 + ...ubstitution_maps_cyclic_dependencies_02.cc | 53 ++++++++++ ...itution_maps_cyclic_dependencies_02.output | 2 + 7 files changed, 276 insertions(+) create mode 100644 doc/news/changes/minor/20190505Jean-PaulPelteret-1 create mode 100644 tests/symengine/substitution_maps_cyclic_dependencies_01.cc create mode 100644 tests/symengine/substitution_maps_cyclic_dependencies_01.output create mode 100644 tests/symengine/substitution_maps_cyclic_dependencies_02.cc create mode 100644 tests/symengine/substitution_maps_cyclic_dependencies_02.output diff --git a/doc/news/changes/minor/20190505Jean-PaulPelteret-1 b/doc/news/changes/minor/20190505Jean-PaulPelteret-1 new file mode 100644 index 0000000000..740787f95f --- /dev/null +++ b/doc/news/changes/minor/20190505Jean-PaulPelteret-1 @@ -0,0 +1,4 @@ +New: Some utility functions that resolve explicit (and cyclic) dependencies +between entries in symbolic substitution maps. +
+(Jean-Paul Pelteret, 2019/05/05) diff --git a/include/deal.II/differentiation/sd/symengine_scalar_operations.h b/include/deal.II/differentiation/sd/symengine_scalar_operations.h index 02c581c0dc..eff52e923b 100644 --- a/include/deal.II/differentiation/sd/symengine_scalar_operations.h +++ b/include/deal.II/differentiation/sd/symengine_scalar_operations.h @@ -597,6 +597,90 @@ namespace Differentiation //@} + /** + * @name Symbol substitution and evaluation + */ + //@{ + + /** + * Return a substitution map that has any explicit interdependencies between + * the entries of the input @p substitution_map resolved. + * + * The @p force_cyclic_dependency_resolution flag exists to ensure, if + * desired, that no cyclic dependencies can exist in the returned map. + * If a cyclic dependency exists in the input substitution map, + * @p substitution_map, then with this flag set to true the + * dependency cycle is broken by a dictionary-ordered substitution. + * For example, if the substitution map contains two entries + * map["a"] -> "b" and map["b"] -> "a", then the result + * of calling this function would be a map with the elements + * map["a"] -> "a" and map["b"] -> "a". + * + * If one symbol is an explicit function of another, and it is desired that + * all their values are completely resolved, then it may be necessary to + * perform substitution a number of times before the result is finalized. + * This function performs substitution sweeps for a set of symbolic + * variables until all explicit relationships between the symbols in the map + * have been resolved. Whether each entry returns a symbolic or real value + * depends on the nature of the values stored in the substitution map. If + * the values associated with a key are also symbolic then the returned + * result may still be symbolic in nature. The terminal result of using the + * input substitution map, @p symbol_values, is then guaranteed to be + * rendered by a single substitition of the returned dependency-resolved + * map. + * + * Example: If map["a"] -> 1 and + * map["b"] -> "a"+ 2, then then the function $f(a,b(a)) = a+b$ + * will be evaluated and the result $f\vert_{a=1,b=a+2} = 3+a$ is determined + * upon the completion of the first sweep. A second sweep is therefore + * necessary to resolve the final symbol, and the returned value is + * ultimately $f = [3+a]_{a=1} = 4$. By resolving the explicit relationships + * between all symbols in the map, we determine that map["a"] -> 1 + * and map["b"] -> 1 + 2 = 3 and thus, using only one substitution, + * that $f = a+b = 1 + 3 = 4$. + */ + types::substitution_map + resolve_explicit_dependencies( + const types::substitution_map &substitution_map, + const bool force_cyclic_dependency_resolution = false); + + /** + * Return a substitution map that has any explicit interdependencies between + * the entries of the map generated by the paired elements in the + * @p symbol_values vector resolved. + * The @p force_cyclic_dependency_resolution exists to ensure, if desired, + * that no cyclic dependencies can exist in the returned map. + * + * This function performs substitution sweeps for a set of symbolic + * variables until all explicit relationships between the symbols in the map + * have been resolved. Whether each entry returns a symbolic or real value + * depends on the chosen ValueType and the values represented therein. If + * the ValueType is another Expression, and they contain symbols then + * the returned result may still be symbolic in nature. + * + * For an example of what this function does, see the documentation for the + * other @ref resolve_explicit_dependencies(const + * types::substitution_map &) function. + * + * @tparam ExpressionType A type that represents a symbolic expression. + * The Differentiation::SD::Expression class is often suitable for + * this purpose, although if the @p ValueType is not supported + * by this class then a user-defined @p ExpressionType should be + * used. + * @tparam ValueType A type that corresponds to the @p value that the + * @p symbol is to represent. Although it is typically + * arithmetic in nature, it may also represent another symbolic + * expression type or be a special type that a user-defined + * @p ExpressionType can be constructed from. + */ + template + types::substitution_map + resolve_explicit_dependencies( + const std::vector> &symbol_values, + const bool force_cyclic_dependency_resolution = false); + + //@} + } // namespace SD } // namespace Differentiation @@ -859,6 +943,20 @@ namespace Differentiation other_substitution_maps_in...); } + + /* ---------------- Symbol substitution and evaluation --------------*/ + + + template + types::substitution_map + resolve_explicit_dependencies( + const std::vector> &symbol_values, + const bool force_cyclic_dependency_resolution) + { + return resolve_explicit_dependencies(make_substitution_map(symbol_values), + force_cyclic_dependency_resolution); + } + } // namespace SD } // namespace Differentiation diff --git a/source/differentiation/sd/symengine_scalar_operations.cc b/source/differentiation/sd/symengine_scalar_operations.cc index bf24b4b4a5..e2d8d8ca9e 100644 --- a/source/differentiation/sd/symengine_scalar_operations.cc +++ b/source/differentiation/sd/symengine_scalar_operations.cc @@ -156,6 +156,61 @@ namespace Differentiation } } + + /* ---------------- Symbol substitution and evaluation --------------*/ + + + types::substitution_map + resolve_explicit_dependencies(const types::substitution_map &symbol_values, + const bool force_cyclic_dependency_resolution) + { + types::substitution_map symbol_values_resolved = symbol_values; + const std::size_t size = symbol_values.size(); + (void)size; + for (auto &entry : symbol_values_resolved) + { + // Perform dictionary-based substitution to + // resolve all explicit relations in a map. + // Instead of checking by value (and thus having + // to store a temporary value), we check to see + // if the hash of the map entry changes. + Expression & out = entry.second; + SE::hash_t hash_old; + SE::hash_t hash_new = out.get_RCP()->hash(); + unsigned int iter = 0; + do + { + // Write the substituted value straight back + // into the map. + if (force_cyclic_dependency_resolution) + { + // Here we substitute in symbol_values_resolved instead of + // symbol_values, in order to break any cyclic dependencies. + // The earlier entries in the dictionary are in this way + // guarenteed to be resolved before any subsequent entries, + // thereby breaking the dependency loop. + out = out.substitute(symbol_values_resolved); + } + else + { + out = out.substitute(symbol_values); + } + + // Compute and store the hash of the new object + hash_old = std::move(hash_new); + hash_new = out.get_RCP()->hash(); + AssertThrow( + iter < size, + ExcMessage( + "Unresolvable cyclic dependency detected in substitution map.")); + ++iter; + } + while (hash_new != hash_old); + } + + return symbol_values_resolved; + } + } // namespace SD } // namespace Differentiation diff --git a/tests/symengine/substitution_maps_cyclic_dependencies_01.cc b/tests/symengine/substitution_maps_cyclic_dependencies_01.cc new file mode 100644 index 0000000000..100f487cc2 --- /dev/null +++ b/tests/symengine/substitution_maps_cyclic_dependencies_01.cc @@ -0,0 +1,61 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2019 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE at +// the top level of the deal.II distribution. +// +// --------------------------------------------------------------------- + + +// Check that cyclic dependencies in a substitution map are are detected when +// using the resolve_explicit_dependencies() function. + +#include + +#include +#include + +#include "../tests.h" + +using namespace dealii; +namespace SD = Differentiation::SD; + +int +main() +{ + initlog(); + + // Introduce a cyclic dependency into a map. + // Here we set a==b and b==a. + const SD::types::substitution_map sub_vals_unresolved = + SD::make_substitution_map( + std::make_pair(SD::Expression("a"), SD::Expression("b")), + std::make_pair(SD::Expression("b"), SD::Expression("a"))); + std::cout << "Original map:" << std::endl; + SD::Utilities::print_substitution_map(std::cout, sub_vals_unresolved); + + deal_II_exceptions::disable_abort_on_exception(); + try + { + const SD::types::substitution_map sub_vals_resolved = + SD::resolve_explicit_dependencies(sub_vals_unresolved); + std::cout << "Resolved map:" << std::endl; + SD::Utilities::print_substitution_map(std::cout, sub_vals_resolved); + deallog + << "Cyclic dependency in substitution map was unexpectedly resolved." + << std::endl; + } + catch (...) + { + deallog << "Detected cyclic dependency in substitution map." << std::endl; + } + + deallog << "OK" << std::endl; +} diff --git a/tests/symengine/substitution_maps_cyclic_dependencies_01.output b/tests/symengine/substitution_maps_cyclic_dependencies_01.output new file mode 100644 index 0000000000..4d97f5d78b --- /dev/null +++ b/tests/symengine/substitution_maps_cyclic_dependencies_01.output @@ -0,0 +1,3 @@ + +DEAL::Detected cyclic dependency in substitution map. +DEAL::OK diff --git a/tests/symengine/substitution_maps_cyclic_dependencies_02.cc b/tests/symengine/substitution_maps_cyclic_dependencies_02.cc new file mode 100644 index 0000000000..082121336c --- /dev/null +++ b/tests/symengine/substitution_maps_cyclic_dependencies_02.cc @@ -0,0 +1,53 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2019 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE at +// the top level of the deal.II distribution. +// +// --------------------------------------------------------------------- + + +// Check that, when the correct flag is set, cyclic dependencies in a +// substitution map are resolved in dictionary order, and do not cause an +// infinite loop in the resolve_explicit_dependencies() function. + +#include + +#include +#include + +#include "../tests.h" + +using namespace dealii; +namespace SD = Differentiation::SD; + +int +main() +{ + initlog(); + + // Introduce a cyclic dependency into a map. + // Here we set a==b and b==a. + const SD::types::substitution_map sub_vals_unresolved = + SD::make_substitution_map( + std::make_pair(SD::Expression("a"), SD::Expression("b")), + std::make_pair(SD::Expression("b"), SD::Expression("a"))); + std::cout << "Original map:" << std::endl; + SD::Utilities::print_substitution_map(std::cout, sub_vals_unresolved); + + const bool force_cyclic_dependency_resolution = true; + const SD::types::substitution_map sub_vals_resolved = + SD::resolve_explicit_dependencies(sub_vals_unresolved, + force_cyclic_dependency_resolution); + std::cout << "Resolved map:" << std::endl; + SD::Utilities::print_substitution_map(std::cout, sub_vals_resolved); + + deallog << "OK" << std::endl; +} diff --git a/tests/symengine/substitution_maps_cyclic_dependencies_02.output b/tests/symengine/substitution_maps_cyclic_dependencies_02.output new file mode 100644 index 0000000000..0fd8fc12f0 --- /dev/null +++ b/tests/symengine/substitution_maps_cyclic_dependencies_02.output @@ -0,0 +1,2 @@ + +DEAL::OK -- 2.39.5