OGS 6.2.1-97-g73d1aeda3
NamedFunctionCaller.cpp
Go to the documentation of this file.
1 
10 #include "NamedFunctionCaller.h"
11 
12 #include <algorithm>
13 #include <limits>
14 
15 #include "BaseLib/Algorithm.h"
16 
27 bool hasTopologicalOrdering(std::vector<std::vector<int>> const& graph)
28 {
29  // Number of incoming edges for each node of the graph
30  std::vector<unsigned> number_incoming_edges(graph.size());
31 
32  // Count all incoming edges (i,j) for each node (i).
33  for (auto const& node_i_adjacencies : graph)
34  {
35  for (int node_j : node_i_adjacencies)
36  {
37  if (node_j >= 0)
38  { // ignore negative indices.
39  ++number_incoming_edges[node_j];
40  }
41  }
42  }
43 
44  // Working queue: a set of nodes with no incoming edges.
45  std::vector<std::size_t> q;
46  for (std::size_t node_i = 0; node_i < number_incoming_edges.size();
47  ++node_i)
48  {
49  if (number_incoming_edges[node_i] == 0)
50  {
51  q.push_back(node_i);
52  }
53  }
54 
55 
56  auto num_dependent = number_incoming_edges.size() - q.size();
57 
58  while (!q.empty())
59  {
60  auto const node_i = q.back();
61  q.pop_back();
62 
63  // Decrement counts for all edges (i,j).
64  for (int node_j : graph[node_i])
65  {
66  if (node_j < 0)
67  {
68  continue; // ignore negative indices
69  }
70  if (--number_incoming_edges[node_j] == 0)
71  { // Add a node without incoming edges to the queue.
72  q.push_back(node_j);
73  --num_dependent;
74  }
75  }
76  }
77 
78  return num_dependent == 0;
79 }
80 
82 
89 template <typename Callback>
90 void traverse(std::vector<std::vector<int>> const& map_sink_source,
91  int sink_fct, Callback&& callback)
92 {
93  assert(sink_fct < static_cast<int>(map_sink_source.size()));
94  callback(sink_fct, TraversePosition::StartNode);
95 
96  if (sink_fct < 0)
97  {
98  return;
99  }
100 
101  auto const& si_so = map_sink_source[sink_fct];
102  std::size_t const num_args = si_so.size();
103  for (std::size_t sink_arg = 0; sink_arg != num_args; ++sink_arg) {
104  if (sink_arg != 0)
105  {
106  callback(sink_fct, TraversePosition::BetweenChildren);
107  }
108  traverse(map_sink_source, si_so[sink_arg], callback);
109  }
110 
111  callback(sink_fct, TraversePosition::EndNode);
112 }
113 
114 namespace NumLib
115 {
116 NamedFunctionCaller::NamedFunctionCaller(
117  std::initializer_list<std::string> unbound_argument_names)
118  : _uninitialized(-1 - static_cast<int>(unbound_argument_names.size()))
119 {
120  assert(unbound_argument_names.size() <
121  static_cast<std::size_t>(std::numeric_limits<int>::max()));
122  int idx = -1;
123  for (auto arg : unbound_argument_names) {
125  _map_name_idx, arg, idx,
126  "The name of the unbound argument is not unique.");
127  --idx;
128  }
129 }
130 
132 {
133  DBUG("Adding named function `%s'", fct.getName().c_str());
134 
136  _map_name_idx, fct.getName(), _named_functions.size(),
137  "The name of the function is not unique.");
138 
139  _map_sink_source.emplace_back(fct.getArgumentNames().size(),
141  _named_functions.push_back(std::move(fct));
142 }
143 
144 void NamedFunctionCaller::plug(const std::string& sink_fct,
145  const std::string& sink_arg,
146  const std::string& source_fct)
147 {
148  _deferred_plugs.push_back({sink_fct, sink_arg, source_fct});
149 }
150 
152 {
153  while (!_deferred_plugs.empty())
154  {
155  auto const& plug = _deferred_plugs.back();
156  auto const& sink_fct = plug.sink_fct;
157  auto const& sink_arg = plug.sink_arg;
158  auto const& source = plug.source;
159 
160  auto const source_it = _map_name_idx.find(source);
161  if (source_it == _map_name_idx.end())
162  {
163  OGS_FATAL("A function with the name `%s' has not been found.",
164  source.c_str());
165  }
166  auto const source_idx = source_it->second;
167 
168  auto const sink_it = _map_name_idx.find(sink_fct);
169  if (sink_it == _map_name_idx.end())
170  {
171  OGS_FATAL("A function with the name `%s' has not been found.",
172  sink_fct.c_str());
173  }
174  auto const sink_fct_idx = sink_it->second;
175 
176  auto const& sink_args =
177  _named_functions[sink_it->second].getArgumentNames();
178  auto const sink_arg_it =
179  std::find(sink_args.begin(), sink_args.end(), sink_arg);
180  if (sink_arg_it == sink_args.end())
181  {
182  OGS_FATAL(
183  "An argument with the name `%s' has not been found for the "
184  "function `%s'.",
185  sink_arg.c_str(), sink_fct.c_str());
186  }
187  std::size_t const sink_arg_idx =
188  std::distance(sink_args.begin(), sink_arg_it);
189 
190  auto& sis_sos = _map_sink_source[sink_fct_idx];
191  if (sis_sos[sink_arg_idx] != _uninitialized)
192  {
193  OGS_FATAL("A dependency for `%s'.`%s' has already been introduced.",
194  sink_fct.c_str(), sink_arg.c_str());
195  }
196  sis_sos[sink_arg_idx] = source_idx;
198  {
199  OGS_FATAL(
200  "The call graph being plugged together must be an acyclic "
201  "graph. The added dependency for `%s'.`%s' introduces a cycle "
202  "into the graph.",
203  sink_fct.c_str(), sink_arg.c_str());
204  }
205 
206  _deferred_plugs.pop_back();
207  }
208 }
209 
211  std::size_t function_idx,
212  const std::vector<double>& unbound_arguments) const
213 {
214  assert(_deferred_plugs.empty() &&
215  "You must call applyPlugs() before this method!");
216 
217  auto const& sis_sos = _map_sink_source[function_idx];
218  assert(sis_sos.size() ==
219  _named_functions[function_idx].getArgumentNames().size());
220  std::vector<double> fct_args(sis_sos.size());
221 
222  for (std::size_t sink=0; sink<sis_sos.size(); ++sink)
223  {
224  auto const source = sis_sos[sink];
225 
226  if (source >= 0) {
227  fct_args[sink] = call(source, unbound_arguments);
228  } else {
229  assert(source != _uninitialized);
230  fct_args[sink] = unbound_arguments[-source-1];
231  }
232  }
233 
234  return _named_functions[function_idx].call(fct_args);
235 }
236 
238  std::string const& function_name) const
239 {
240  auto const fct_it = _map_name_idx.find(function_name);
241  if (fct_it == _map_name_idx.end()) {
242  OGS_FATAL("A function with the name `%s' has not been found.",
243  function_name.c_str());
244  }
245 
246  std::string expr;
247  auto callback = [&](int fct_idx, TraversePosition pos)
248  {
249  switch (pos) {
251  {
252  if (fct_idx < 0) {
253  auto it = std::find_if(
254  _map_name_idx.begin(), _map_name_idx.end(),
255  [fct_idx](std::pair<std::string, int> const& e) {
256  return e.second == fct_idx;
257  });
258  if (it == _map_name_idx.end()) {
259  OGS_FATAL("The function index %i has not been found.", fct_idx);
260  }
261  expr += it->first;
262  } else {
263  expr += _named_functions[fct_idx].getName() + "(";
264  }
265  break;
266  }
268  expr += ", ";
269  break;
271  expr += ")";
272  }
273  };
274 
275  traverse(_map_sink_source, fct_it->second, callback);
276  DBUG("expression: %s", expr.c_str());
277  return expr;
278 }
279 
281 NamedFunctionCaller::getSpecificFunctionCaller(const std::string &function_name)
282 {
283  auto const fct_it = _map_name_idx.find(function_name);
284  if (fct_it == _map_name_idx.end()) {
285  OGS_FATAL("A function with the name `%s' has not been found.",
286  function_name.c_str());
287  }
288  return SpecificFunctionCaller(fct_it->second, *this);
289 }
290 
292 {
293  return -_uninitialized - 1;
294 }
295 
296 SpecificFunctionCaller::SpecificFunctionCaller(const std::size_t function_idx,
297  const NamedFunctionCaller& caller)
298  : _function_idx(function_idx), _caller(caller)
299 {
300 }
301 
303  const std::vector<double>& unbound_arguments) const
304 {
305  return _caller.call(_function_idx, unbound_arguments);
306 }
307 
309 {
311 }
312 
313 } // namespace NumLib
double call(std::size_t function_idx, std::vector< double > const &unbound_arguments) const
NamedFunctionCaller const & _caller
The named function caller used for the evaluation.
void traverse(std::vector< std::vector< int >> const &map_sink_source, int sink_fct, Callback &&callback)
void plug(std::string const &sink_fct, std::string const &sink_arg, std::string const &source_fct)
double call(std::vector< double > const &unbound_arguments) const
Call the function set up with the given unbound arguments.
bool hasTopologicalOrdering(std::vector< std::vector< int >> const &graph)
std::map< std::string, int > _map_name_idx
TraversePosition
std::vector< SinkSource > _deferred_plugs
Saves plugs declared by plug().
Builds expression trees of named functions dynamically at runtime.
SpecificFunctionCaller(std::size_t const function_idx, NamedFunctionCaller const &caller)
Constructs a new instance.
std::size_t getNumberOfUnboundArguments() const
Returns the number of unbound arguments.
std::size_t const _function_idx
Index of the referenced function.
static const double q
void insertIfKeyUniqueElseError(Map &map, Key const &key, Value &&value, std::string const &error_message)
Definition: Algorithm.h:104
void addNamedFunction(NamedFunction &&fct)
Adds the given named function.
std::size_t getNumberOfUnboundArguments() const
Returns the number of unbound arguments.
std::vector< NamedFunction > _named_functions
Contains all named functions.
#define OGS_FATAL(fmt,...)
Definition: Error.h:63
std::vector< std::vector< int > > _map_sink_source
std::string getCallExpression(std::string const &function_name) const
SpecificFunctionCaller getSpecificFunctionCaller(std::string const &function_name)