Graph.cc
1 /*
2  * MoMEMta: a modular implementation of the Matrix Element Method
3  * Copyright (C) 2017 Universite catholique de Louvain (UCL), Belgium
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 #include <Graph.h>
20 
21 #include <ModuleUtils.h>
22 #include <Path.h>
23 
24 #include <boost/graph/graphviz.hpp>
25 #include <boost/graph/topological_sort.hpp>
26 
27 #include <array>
28 
29 #ifdef DEBUG_TIMING
30 using namespace std::chrono;
31 #endif
32 
33 using namespace boost::uuids;
34 
35 namespace momemta {
36 
37 typedef boost::graph_traits<Graph>::out_edge_iterator out_edge_iterator_t;
38 typedef boost::graph_traits<Graph>::in_edge_iterator in_edge_iterator_t;
39 
40 class incomplete_looper_path: public std::runtime_error {
41  using std::runtime_error::runtime_error;
42 };
43 
44 class unresolved_input: public std::runtime_error {
45  using std::runtime_error::runtime_error;
46 };
47 
55 bool isConnectedToByOut(Graph& g, vertex_t vertex, vertex_t to) {
56  out_edge_iterator_t o, o_end;
57  std::tie(o, o_end) = boost::out_edges(vertex, g);
58 
59  for (; o != o_end; ++o) {
60  vertex_t target = boost::target(*o, g);
61  if (target == to)
62  return true;
63 
64  if (isConnectedToByOut(g, target, to))
65  return true;
66  }
67 
68  return false;
69 }
70 
78 bool isConnectedToByIn(Graph& g, vertex_t vertex, vertex_t to) {
79  in_edge_iterator_t i, i_end;
80  std::tie(i, i_end) = boost::in_edges(vertex, g);
81 
82  for (; i != i_end; ++i) {
83  vertex_t source = boost::source(*i, g);
84  if (source == to)
85  return true;
86 
87  if (isConnectedToByIn(g, source, to))
88  return true;
89  }
90 
91  return false;
92 }
93 
101 bool isConnectedTo(Graph& g, vertex_t vertex, vertex_t to) {
102  if (isConnectedToByOut(g, vertex, to))
103  return true;
104 
105  return isConnectedToByIn(g, vertex, to);
106 }
107 
115 bool isConnectedDirectlyTo(Graph& g, vertex_t from, vertex_t to) {
116  out_edge_iterator_t o, o_end;
117  std::tie(o, o_end) = boost::out_edges(from, g);
118 
119  for (; o != o_end; ++o) {
120  vertex_t target = boost::target(*o, g);
121  if (target == to)
122  return true;
123  }
124 
125  return false;
126 }
127 
137 bool checkInPath(const Configuration::ModuleDecl& looper_decl, const std::string& module_name) {
138 
139  const auto& looper_path = looper_decl.parameters->get<ExecutionPath>("path");
140 
141  auto it = std::find_if(looper_path.elements.begin(), looper_path.elements.end(),
142  [&module_name](const std::string& m) {
143  return m == module_name;
144  });
145 
146  return it != looper_path.elements.end();
147 }
148 
149 momemta::ModuleList::value_type get_module_def(const std::string& module_type,
150  const momemta::ModuleList& available_modules) {
151 
152  auto it = std::find_if(available_modules.begin(), available_modules.end(),
153  [&module_type](const momemta::ModuleList::value_type& m) {
154  return m.name == module_type;
155  });
156 
157  assert(it != available_modules.end());
158 
159  return *it;
160 }
161 
162 void ComputationGraph::addDecl(const uuid& path, const Configuration::ModuleDecl& decl) {
163 
164  auto& storage = module_decls;
165 
166  // Check if an entry already exists for the execution path.
167  auto map_it = storage.find(path);
168  if (map_it == storage.end()) {
169  // Add the path into the list of know path, keeping track of the order
170  sorted_execution_paths.emplace_back(path);
171 
172  // Add the module into its path
173  storage[path].emplace_back(decl);
174  } else {
175  map_it->second.emplace_back(decl);
176  }
177 }
178 
179 const std::vector<uuid>& ComputationGraph::getPaths() const {
180  return sorted_execution_paths;
181 }
182 
183 const std::vector<Configuration::ModuleDecl>& ComputationGraph::getDecls(const uuid& path) const {
184  return module_decls.at(path);
185 }
186 
187 void ComputationGraph::initialize(PoolPtr pool) {
188  const auto& execution_paths = sorted_execution_paths;
189 
190  // Keep track of the instantiated modules in their own execution path
191  std::map<uuid, std::vector<ModulePtr>> module_instances;
192 
193  // The list of execution path is sorted in the order we must execute the modules (modules from the first path first,
194  // then modules from the second path, etc.)
195  // However, some modules (ie Loopers) except as argument an execution path containing a list of module instances.
196  // Since modules and paths are sorted based on execution order, such dependencies are always in a other execution path.
197  // To solve this, we iterate the execution paths in reverse order, creating first the last execution path, free of
198  // any dependencies. This way, we are sure to find the final list of modules already available when we need it.
199  for (auto it = execution_paths.rbegin(); it != execution_paths.rend(); ++it) {
200 
201  const auto& modules = getDecls(*it);
202  for (auto module_decl_it = modules.begin(); module_decl_it != modules.end(); ++module_decl_it) {
203 
204  std::unique_ptr<ParameterSet> params(module_decl_it->parameters->clone());
205 
206  if (module_decl_it->type == "Looper") {
207  // Switch the "path" parameter to the list of module properly instantiated
208  auto config_path_id = params->get<ExecutionPath>("path").id;
209 
210  // Replace the `path` parameter with the list of modules
211  // Since paths are sorted and we iterate backwards, we are sure to find an existing path.
212  params->raw_set("path", Path(module_instances.at(config_path_id)));
213  }
214 
215  try {
216  module_instances[*it].push_back(ModuleFactory::get().create(module_decl_it->type, pool, *params));
217  } catch (...) {
218  LOG(fatal) << "Exception while trying to create module " << module_decl_it->type
219  << "::" << module_decl_it->name
220  << ". See message above for a (possible) more detailed description of the error.";
221  std::rethrow_exception(std::current_exception());
222  }
223  }
224  }
225 
226  modules = module_instances[DEFAULT_EXECUTION_PATH];
227 }
228 
229 void ComputationGraph::configure() {
230  for (auto& module: modules)
231  module->configure();
232 }
233 
234 void ComputationGraph::finish() {
235  for (auto& module: modules)
236  module->finish();
237 }
238 
239 void ComputationGraph::beginIntegration() {
240  for (auto& module: modules)
241  module->beginIntegration();
242 }
243 
244 void ComputationGraph::endIntegration() {
245  for (auto& module: modules)
246  module->endIntegration();
247 }
248 
249 Module::Status ComputationGraph::execute() {
250  for (auto& module: modules)
251  module->beginPoint();
252 
253  for (auto& module: modules) {
254 #ifdef DEBUG_TIMING
255  auto start = high_resolution_clock::now();
256 #endif
257  auto status = module->work();
258 #ifdef DEBUG_TIMING
259  module_timings[module.get()] += high_resolution_clock::now() - start;
260 #endif
261 
262  if (status == Module::Status::NEXT) {
263  // Stop execution for the current integration step
264  return Module::Status::NEXT;
265  } else if (status == Module::Status::ABORT) {
266  // Abort integration
267  return Module::Status::ABORT;
268  }
269  }
270 
271  for (auto& module: modules)
272  module->endPoint();
273 
274  return Module::Status::OK;
275 }
276 
277 #ifdef DEBUG_TIMING
278 void ComputationGraph::logTimings() const {
279  LOG(info) << "Time spent evaluating modules (more details for loopers below):";
280  for (auto it: module_timings) {
281  LOG(info) << " " << it.first->name() << ": " << duration_cast<duration<double>>(it.second).count() << "s";
282  }
283 }
284 #endif
285 
286 void ComputationGraph::setNDimensions(size_t n) {
287  n_dimensions = n;
288 }
289 
290 size_t ComputationGraph::getNDimensions() const {
291  return n_dimensions;
292 }
293 
294 ComputationGraphBuilder::ComputationGraphBuilder(const momemta::ModuleList& available_modules,
295  const Configuration& configuration):
296  available_modules(available_modules), configuration(configuration) { }
297 
298 std::shared_ptr<ComputationGraph> ComputationGraphBuilder::build() {
299 
300  uint32_t id = 0;
301  const auto& requested_modules = configuration.getModules();
302 
303  // Create graph vertices. Each vertex is a module requested in the configuration file
304  for (const auto& module: requested_modules) {
305  vertex_t v = boost::add_vertex(g);
306 
307  auto& vertex = g[v];
308  vertex.id = id++;
309  vertex.name = module.name;
310  vertex.type = module.type;
311 
312  // Attach module definition to the vertex
313  vertex.def = get_module_def(module.type, available_modules);
314 
315  // Attach module declaration to the vertex
316  vertex.decl = module;
317 
318  vertices.emplace(module.name, v);
319  }
320 
321  graph_exportable = true;
322 
323  // Create edges, connecting modules together. An edge link module's outputs to module's inputs
324  typename boost::graph_traits<Graph>::vertex_iterator vtx_it, vtx_it_end;
325  for (std::tie(vtx_it, vtx_it_end) = boost::vertices(g); vtx_it != vtx_it_end; vtx_it++) {
326 
327  const auto& vertex = g[*vtx_it];
328 
329  // Connect each output of this module to any module needing it
330  for (const auto& output: vertex.def.outputs) {
331 
332  // Find any module using this output (iterate over the graph again)
333  typename boost::graph_traits<Graph>::vertex_iterator test_vtx_it, test_vtx_it_end;
334  for (std::tie(test_vtx_it, test_vtx_it_end) = boost::vertices(g); test_vtx_it != test_vtx_it_end;
335  test_vtx_it++) {
336 
337  const auto& test_module = g[*test_vtx_it];
338 
339  // Skip ourselves
340  if (test_module.name == vertex.name)
341  continue;
342 
343  // Get definition of this new module
344  const auto& test_module_def = test_module.def;
345  for (const auto& input: test_module_def.inputs) {
346  // Grab the InputTag for each input, and see if it points to the vertex
348  momemta::getInputTagsForInput(input, *test_module.decl.parameters);
349 
350  // If the input is optional, we may not have anything
351  if (! inputTags)
352  continue;
353 
354  for (const auto& inputTag: *inputTags) {
355  if (vertex.name == inputTag.module && output.name == inputTag.parameter) {
356  // We have a match, the InputTag points to the vertex output
357  // Create a new edge in the graph
358 
359  edge_t e;
360  bool inserted;
361  std::tie(e, inserted) = boost::add_edge(*vtx_it, vertices.at(test_module.name), g);
362 
363  auto& edge = g[e];
364  edge.virt = false;
365  edge.tag = inputTag;
366  edge.description = inputTag.parameter;
367  if (inputTag.isIndexed()) {
368  edge.description += "[" + std::to_string(inputTag.index) + "]";
369  }
370  }
371  }
372  }
373  }
374  }
375  }
376 
377  // We need to make sure that any dependencies of a module inside a looper
378  // is ran before the looper itself.
379  for (const auto& vertex: vertices) {
380  if (g[vertex.second].type != "Looper")
381  continue;
382 
383  const auto& looper_vtx = vertex.second;
384  const auto& looper_decl = g[looper_vtx].decl;
385 
386  // Retrieve the looper path
387  const auto& looper_path = looper_decl.parameters->get<ExecutionPath>("path");
388 
389  // Add virtual link between the looper and all module inside its execution path
390  for (const auto& m: looper_path.elements) {
391 
392  auto module_it = vertices.find(m);
393  if (module_it == vertices.end()) {
394  LOG(warning) << "Module '" << m << "' present in Looper '" << looper_decl.name
395  << "' execution path does not exists";
396  continue;
397  }
398 
399  auto module_vertex = module_it->second;
400  if (!isConnectedDirectlyTo(g, looper_vtx, module_vertex)) {
401  edge_t e;
402  bool inserted;
403  std::tie(e, inserted) = boost::add_edge(looper_vtx, module_vertex, g);
404  g[e].description = "virtual link (module in path)";
405  g[e].virt = true;
406  }
407  }
408 
409  out_edge_iterator_t e, e_end;
410  std::tie(e, e_end) = boost::out_edges(looper_vtx, g);
411 
412  // Iterator over all edges this Looper vertex is connected to
413  for (; e != e_end; ++e) {
414  auto target = boost::target(*e, g);
415 
416  // Iterate over all edges connected to the module
417  in_edge_iterator_t i, i_end;
418  std::tie(i, i_end) = boost::in_edges(target, g);
419 
420  for (; i != i_end; ++i) {
421  auto source = boost::source(*i, g);
422 
423  if (source == looper_vtx)
424  continue;
425 
426  // Check if the source vertex is connected to the looper in any way
427  if (!isConnectedTo(g, source, looper_vtx)) {
428  edge_t e;
429  bool inserted;
430  std::tie(e, inserted) = boost::add_edge(source, looper_vtx, g);
431  g[e].description = "virtual link";
432  g[e].virt = true;
433  }
434  }
435  }
436  }
437 
438  // Remove unused modules
439  prune_graph();
440 
441  // Sort the modules using their dependencies as constrains
442  sort_graph();
443 
444  // Validate the graph
445  validate();
446 
447  // Count the real number of dimension needed for the integration.
448  // For that, we use the virtual `cuba` module and count the number of out edges
449  // However, we need to be careful here because different modules can share the same dimension, so we need
450  // to explicitly check the index of the InputTag to count unique dimensions
451  out_edge_iterator_t o, o_end;
452  std::tie(o, o_end) = boost::out_edges(vertices.at("cuba"), g);
453 
454  std::set<size_t> unique_cuba_indices;
455  for (; o != o_end; ++o) {
456  const auto& inputTag = g[*o].tag;
457 
458  // We only care about phase-space points, not weights
459  if (inputTag.parameter != "ps_points")
460  continue;
461 
462  assert(inputTag.isIndexed());
463  unique_cuba_indices.emplace(inputTag.index);
464  }
465 
466  size_t n_dimensions = unique_cuba_indices.size();
467 
468  assert(n_dimensions <= configuration.getNDimensions());
469 
470  if (n_dimensions < configuration.getNDimensions()) {
471  // A module requesting a new dimension was removed from the computation graph
472  // Re-index cuba InputTag in order to ensure continuous indexing
473  std::unordered_map<size_t, size_t> new_indices_mapping;
474  size_t current_index = 0;
475  std::tie(o, o_end) = boost::out_edges(vertices.at("cuba"), g);
476  for (; o != o_end; ++o) {
477  const auto& module_vertex = g[boost::target(*o, g)];
478 
479  for (const auto& input: module_vertex.def.inputs) {
480 
481  // Get the inputs tags
483  momemta::getInputTagsForInput(input, *module_vertex.decl.parameters);
484 
485  // If the input is optional, we may not have anything
486  if (! inputTags)
487  continue;
488 
489  bool update_decl = false;
490  std::vector<InputTag> updatedInputTags;
491  for (const auto& inputTag: *inputTags) {
492 
493  auto updatedInputTag = inputTag;
494 
495  // TODO: find a better way than hardcoding the values
496  if (inputTag.module == "cuba" && inputTag.parameter == "ps_points") {
497  update_decl = true;
498  // It's a cuba InputTag, re-index it
499  auto it = new_indices_mapping.find(inputTag.index);
500  if (it == new_indices_mapping.end()) {
501  new_indices_mapping.emplace(inputTag.index, current_index);
502  updatedInputTag.index = current_index;
503  current_index++;
504  } else {
505  updatedInputTag.index = it->second;
506  }
507  updatedInputTag.update();
508  }
509 
510  updatedInputTags.push_back(updatedInputTag);
511  }
512 
513  if (update_decl) {
514  // At least one InputTag has been updated, we need to update the module parameters
515  momemta::setInputTagsForInput(input, *module_vertex.decl.parameters, updatedInputTags);
516  }
517  }
518  }
519  }
520 
521  // Finally, everything is setup. Create the final computation graph
522  const auto& execution_paths = configuration.getPaths();
523 
524  std::shared_ptr<ComputationGraph> computationGraph(new ComputationGraph());
525  computationGraph->setNDimensions(n_dimensions);
526 
527  for (auto vertex: sorted_vertices) {
528  // Find in which execution path this module is. If it's not found inside any execution path
529  // declared in the configuration, then the module is assigned to the default execution path.
530  auto find_module_in_path = [&vertex, this](std::shared_ptr<ExecutionPath> p) -> bool {
531  // Returns true if the module is inside the execution path `p`, False otherwise
532  auto it = std::find_if(p->elements.begin(), p->elements.end(),
533  [&vertex, this](const std::string& element) -> bool {
534  return g[vertex].name == element;
535  }
536  );
537 
538  return it != p->elements.end();
539  };
540 
541  auto execution_path_it = std::find_if(execution_paths.begin(), execution_paths.end(), find_module_in_path);
542  auto execution_path = execution_path_it == execution_paths.end() ? DEFAULT_EXECUTION_PATH :
543  (*execution_path_it)->id;
544 
545  // The first declared path must always be the default one, otherwise we are in trouble
546  assert(!computationGraph->getPaths().empty() || execution_path == DEFAULT_EXECUTION_PATH);
547 
548  computationGraph->addDecl(execution_path, g[vertex].decl);
549  }
550 
551  return computationGraph;
552 }
553 
554 void ComputationGraphBuilder::prune_graph() {
555 
556  // Find all vertices not connected to something and remove them
557  for (auto it = vertices.begin(), ite = vertices.end(); it != ite;) {
558  if (boost::out_degree(it->second, g) == 0) {
559 
560  auto& vertex = g[it->second];
561 
562  // Don't consider internal or sticky modules
563  if (vertex.def.internal || vertex.def.sticky) {
564  ++it;
565  continue;
566  }
567 
568  // Otherwise, remove it
569  LOG(info) << "Module '" << it->first << "' output is not used by any other module. Removing it from the configuration.";
570  boost::clear_vertex(it->second, g);
571  boost::remove_vertex(it->second, g);
572 
573  it = vertices.erase(it);
574  } else
575  ++it;
576  }
577 
578  // Ensure ids are continuous
579  uint32_t id = 0;
580  typename boost::graph_traits<Graph>::vertex_iterator vtx_it, vtx_it_end;
581  for (std::tie(vtx_it, vtx_it_end) = boost::vertices(g); vtx_it != vtx_it_end; vtx_it++) {
582  g[*vtx_it].id = id++;
583  }
584 }
585 
586 void ComputationGraphBuilder::sort_graph() {
587  const std::vector<std::shared_ptr<ExecutionPath>>& execution_paths = configuration.getPaths();
588 
589  try {
590  boost::topological_sort(g, std::front_inserter(sorted_vertices),
591  boost::vertex_index_map(boost::get(&Vertex::id, g)));
592  } catch (...) {
593  exportGraph("graph.debug");
594  LOG(fatal) << "Exception while sorting the graph. Graphviz representation saved as graph.debug";
595  throw;
596  }
597 
598  // Remove vertices corresponding to internal modules
599  sorted_vertices.erase(std::remove_if(sorted_vertices.begin(), sorted_vertices.end(),
600  [this](const vertex_t& vertex) -> bool {
601  return g[vertex].def.internal;
602  }), sorted_vertices.end());
603 }
604 
605 void ComputationGraphBuilder::validate() {
606 
607  auto log_and_throw_unresolved_input = [](const std::string& module_name, const InputTag& input) {
608  LOG(fatal) << "Module '" << module_name << "' requested a non-existing input (" << input.toString() << ")";
609  throw unresolved_input("Module '" + module_name + "' requested a non-existing input (" + input.toString() + ")");
610  };
611 
612  // Find any module whose input point to a non-existing module / parameter
613  for (auto it = vertices.begin(), ite = vertices.end(); it != ite; it++) {
614 
615  const auto& vertex = g[it->second];
616  // Ignore internal module (?)
617  if (vertex.def.internal)
618  continue;
619 
620  const auto& inputs = vertex.def.inputs;
621 
622  for (const auto& input_def: inputs) {
623 
624  // Get the InputTag for this input
626  momemta::getInputTagsForInput(input_def, *vertex.decl.parameters);
627 
628  if (! inputTags)
629  continue;
630 
631  // Ensure that every input tags point to an existing module
632  for (const auto& inputTag: *inputTags) {
633  auto target_it = vertices.find(inputTag.module);
634 
635  if (target_it == vertices.end()) {
636  // Non-existing module
637  log_and_throw_unresolved_input(it->first, inputTag);
638  }
639 
640 
641  // Look for input in module's output
642  const auto& target_module_outputs = g[target_it->second].def.outputs;
643  auto output_it = std::find_if(target_module_outputs.begin(),
644  target_module_outputs.end(),
645  [&inputTag](const ArgDef& output) {
646  return inputTag.parameter == output.name;
647  });
648 
649  if (output_it == target_module_outputs.end()) {
650  // Non-existing parameter
651  log_and_throw_unresolved_input(it->first, inputTag);
652  }
653  }
654  }
655  }
656 
657  // Ensure all the modules using a Looper output are present in the looper path
658  std::map<vertex_t, std::vector<vertex_t>> modules_not_in_path;
659  for (const auto& vertex: sorted_vertices) {
660  if (g[vertex].type == "Looper") {
661 
662  const auto& decl = g[vertex].decl;
663 
664  out_edge_iterator_t e, e_end;
665  std::tie(e, e_end) = boost::out_edges(vertex, g);
666 
667  // Iterator over all edges connected to this Looper vertex
668  for (; e != e_end; ++e) {
669  auto target = boost::target(*e, g);
670 
671  // Check if target is inside the looper path
672  if (! checkInPath(decl, g[target].name)) {
673  auto& loopers = modules_not_in_path[target];
674  auto it = std::find(loopers.begin(), loopers.end(), vertex);
675  if (it == loopers.end())
676  loopers.push_back(vertex);
677  } else {
678  modules_not_in_path.erase(target);
679  }
680  }
681  }
682  }
683 
684  if (modules_not_in_path.size() != 0) {
685  // Only print a message for the first module not in path
686  auto it = modules_not_in_path.begin();
687 
688  auto target = g[it->first];
689 
690  std::stringstream loopers;
691  for (size_t i = 0; i < it->second.size(); i++) {
692  loopers << "'" << g[it->second[i]].name << "'";
693  if (i != it->second.size() - 1)
694  loopers << ", ";
695  }
696 
697  std::string plural = it->second.size() > 1? "s" : "";
698  std::string one_of_the = it->second.size() > 1 ? "one of the" : "the";
699 
700  LOG(fatal) << "Module '" << target.name << "' is configured to use Looper " << loopers.str()
701  << " output" << plural << ", but is not actually part of the Looper" << plural << " execution path. This will lead to undefined "
702  << "behavior. You can fix the issue by adding the module '"
703  << target.name
704  << "' to " << one_of_the << " Looper" << plural << " execution path";
705 
706  throw incomplete_looper_path("A module is using the looper output but not actually part of its "
707  "execution path");
708  }
709 }
710 
711 /*
712  * Graphviz export
713  */
714 
716 public:
717  graph_writer(Graph g,
718  const std::vector<std::shared_ptr<ExecutionPath>>& paths):
719  graph(g), paths(paths) {}
720 
721 
722  // Vertex writer
723  void writeVertex(std::ostream& out, const vertex_t& v) const {
724  std::string shape = "ellipse";
725  std::string color = "black";
726  std::string style = "solid";
727  std::string extra = "";
728 
729  if (graph[v].def.internal) {
730  shape = "rectangle";
731  color = "black";
732  style = "dashed";
733  }
734 
735  if (graph[v].type == "Looper") {
736  style = "filled";
737  extra = "fillcolor=\"" + path_colors.at(graph[v].decl.parameters->get<ExecutionPath>("path").id) + "\"";
738  }
739 
740  out << "[shape=\"" << shape << "\",color=\"" << color << "\",style=\"" << style
741  << "\",label=\"" << graph[v].name << "\"";
742 
743  if (!extra.empty()) {
744  out << "," << extra;
745  }
746 
747  out << "]";
748  }
749 
750  // Edge writer
751  void writeEdge(std::ostream& out, const edge_t& e) const {
752  std::string color = "black";
753  std::string style = "solid";
754  std::string extra = "";
755 
756  if (graph[e].virt) {
757  style = "invis";
758  extra = "constraint=false";
759  }
760 
761  out << "[color=\"" << color << "\",style=\"" << style
762  << "\",label=\"" << graph[e].description << "\"";
763 
764  if (!extra.empty()) {
765  out << "," << extra;
766  }
767 
768  out << "]";
769  }
770 
771  // Graph writer
772  void writeGraph(std::ostream& out) const {
773 
774  size_t index = 0;
775  size_t color_index = 0;
776  for (const auto& path: paths) {
777 
778  out << "subgraph cluster_" << index << " {" << std::endl;
779 
780  out << R"(style=filled; fillcolor=")" << colors[color_index] << R"(";)" << std::endl;
781  path_colors.emplace(path->id, colors[color_index]);
782 
783  auto looper_vertex = find_looper(path->id);
784 
785  if (looper_vertex != boost::graph_traits<Graph>::null_vertex())
786  out << " label=\"" << graph[looper_vertex].name << " execution path\";" << std::endl;
787 
788  out << " ";
789  for (const auto& e: path->elements) {
790  auto vertex = find_vertex(e);
791  if (vertex != boost::graph_traits<Graph>::null_vertex())
792  out << graph[vertex].id << "; ";
793  }
794 
795  out << std::endl;
796  out << "}" << std::endl;
797 
798  index++;
799  color_index++;
800  if (color_index >= colors.size())
801  color_index = 0;
802  }
803  }
804 
805 private:
806  vertex_t find_vertex(const std::string& name) const {
807  typename boost::graph_traits<Graph>::vertex_iterator vtx_it, vtx_it_end;
808 
809  for(boost::tie(vtx_it, vtx_it_end) = boost::vertices(graph); vtx_it != vtx_it_end; ++vtx_it) {
810  if (graph[*vtx_it].name == name)
811  return *vtx_it;
812  }
813 
814  return boost::graph_traits<Graph>::null_vertex();
815  }
816 
817  vertex_t find_looper(const uuid& path) const {
818  typename boost::graph_traits<Graph>::vertex_iterator vtx_it, vtx_it_end;
819 
820  for(boost::tie(vtx_it, vtx_it_end) = boost::vertices(graph); vtx_it != vtx_it_end; ++vtx_it) {
821  if (graph[*vtx_it].type == "Looper") {
822  const auto& looper_path = graph[*vtx_it].decl.parameters->get<ExecutionPath>("path");
823  if (looper_path.id == path)
824  return *vtx_it;
825  }
826  }
827 
828  return boost::graph_traits<Graph>::null_vertex();
829  }
830 
831  Graph graph;
832  const std::vector<std::shared_ptr<ExecutionPath>> paths;
833 
834  mutable std::unordered_map<uuid, std::string,
835  boost::hash<uuid>> path_colors;
836 
837  const std::array<std::string, 5> colors = {{
838  "#BEEB9F",
839  "#ACF0F2",
840  "#F3FFE2",
841  "#79BD8F88",
842  "##EB7F0099"
843  }};
844 };
845 
847 public:
848  graph_writer_wrapper(std::shared_ptr<graph_writer> writer):
849  writer(writer) {}
850 
851  void operator()(std::ostream& out, const vertex_t& v) const {
852  writer->writeVertex(out, v);
853  }
854 
855  void operator()(std::ostream& out, const edge_t& e) const {
856  writer->writeEdge(out, e);
857  }
858 
859  void operator()(std::ostream& out) const {
860  writer->writeGraph(out);
861  }
862 
863 private:
864  std::shared_ptr<graph_writer> writer;
865 };
866 
867 void graphviz_export(const Graph& g,
868  const std::vector<std::shared_ptr<ExecutionPath>>& paths,
869  const std::string& filename) {
870 
871  std::ofstream f(filename.c_str());
872  auto writer = std::make_shared<graph_writer>(g, paths);
873  boost::write_graphviz(f, g, graph_writer_wrapper(writer), graph_writer_wrapper(writer),
874  graph_writer_wrapper(writer), boost::get(&Vertex::id, g));
875 }
876 
877 void ComputationGraphBuilder::exportGraph(const std::string& output) const {
878  if (! graph_exportable)
879  return;
880 
881  graphviz_export(g, configuration.getPaths(), output);
882 }
883 
884 }
size_t getNDimensions() const
std::string name
Name of the module (user-defined from the configuration file)
Definition: Configuration.h:44
std::shared_ptr< ComputationGraph > build()
Build the computation graph.
Definition: Graph.cc:298
std::shared_ptr< ParameterSet > parameters
Module&#39;s parameters, as parsed from the configuration file.
Definition: Configuration.h:47
Definition: Graph.h:21
std::vector< std::shared_ptr< ExecutionPath > > getPaths() const
An execution path.
Definition: Path.h:37
An identifier of a module&#39;s output.
Definition: InputTag_fwd.h:37
Defines an input / output.
Definition: ModuleDef.h:40
void exportGraph(const std::string &output) const
Export a GraphViz representation of the computation graph to a file.
Definition: Graph.cc:877
A frozen snapshot of the configuration file.
Definition: Configuration.h:36
A module declaration, defined from the configuration file.
Definition: Configuration.h:43
const std::vector< ModuleDecl > & getModules() const