2 #include <ossia/dataflow/bench_map.hpp>
3 #include <ossia/dataflow/graph/graph_interface.hpp>
4 #include <ossia/dataflow/graph/graph_utils.hpp>
5 #include <ossia/dataflow/graph/node_executors.hpp>
6 #include <ossia/dataflow/graph/transitive_closure.hpp>
7 #include <ossia/detail/flat_map.hpp>
8 #include <ossia/editor/scenario/execution_log.hpp>
10 #include <boost/circular_buffer.hpp>
11 #include <boost/graph/transitive_closure.hpp>
13 #include <ossia-config.hpp>
19 template <
typename UpdateImpl,
typename TickImpl>
20 struct graph_static final
25 UpdateImpl update_fun;
26 TickImpl tick_fun{*
this};
27 std::vector<boost::default_color_type> m_color_map_cache;
28 std::vector<boost::detail::DFSVertexInfo<graph_t>> m_stack_cache;
29 explicit graph_static(
const ossia::graph_setup_options& opt = {})
30 : update_fun{*
this, opt}
32 m_all_nodes.reserve(1024);
33 m_enabled_cache.reserve(1024);
34 m_topo_order_cache.reserve(1024);
35 m_color_map_cache.reserve(1024);
36 m_stack_cache.reserve(1024);
38 ~graph_static()
override { clear(); }
40 void sort_all_nodes(
const graph_t& gr)
46 m_all_nodes.reserve(m_nodes.size());
49 m_topo_order_cache.clear();
50 m_topo_order_cache.reserve(m_nodes.size());
51 custom_topological_sort(
52 gr, std::back_inserter(m_topo_order_cache), m_color_map_cache, m_stack_cache);
55 for(
auto vtx : m_topo_order_cache)
57 auto node = gr[vtx].get();
59 if(node->root_inputs().empty() && node->root_outputs().empty())
61 m_all_nodes.push_back(node);
65 for(
auto vtx : m_topo_order_cache)
67 auto node = gr[vtx].get();
70 if(!(node->root_inputs().empty() && node->root_outputs().empty()))
72 m_all_nodes.push_back(node);
79 std::cout <<
"Error: graph isn't a DAG: ";
80 print_graph(gr, std::cout);
81 std::cout << std::endl;
86 void state(execution_state& e)
override
92 update_fun(*
this, e.exec_devices());
93 m_enabled_cache.clear();
98 m_enabled_cache.reserve(m_nodes.size());
100 for(
auto node : m_all_nodes)
102 ossia::graph_node& ptr = *node;
105 m_enabled_cache.insert(&ptr);
109 auto it = m_enabled_cache.find(&ptr);
110 if(it != m_enabled_cache.end())
111 m_enabled_cache.erase(it);
115 disable_strict_nodes_rec(m_enabled_cache, m_disabled_cache);
117 tick_fun(*
this, update_fun, e, m_all_nodes);
119 #if defined(OSSIA_EXECUTION_LOG)
120 auto log = g_exec_log.log_executed_nodes(m_graph, m_all_nodes);
123 finish_nodes(m_nodes);
125 catch(
const boost::not_a_dag&)
132 [[nodiscard]]
const graph_t& impl()
const {
return m_graph; }
133 graph_t& impl() {
return m_graph; }
134 std::vector<graph_node*> m_all_nodes;
137 void print(std::ostream& stream)
override { print_graph(m_graph, stream); }
140 node_flat_set m_enabled_cache;
141 node_flat_set m_disabled_cache;
142 std::vector<graph_vertex_t> m_topo_order_cache;
144 friend class ::DataflowTest;
149 ossia::graph_t& m_sub_graph;
150 template <
typename Graph_T>
151 simple_update(Graph_T& g,
const ossia::graph_setup_options& opt)
152 : m_sub_graph{g.m_graph}
156 template <
typename Graph_T,
typename DevicesT>
157 void operator()(Graph_T& g,
const DevicesT& devices)
159 g.sort_all_nodes(g.m_graph);
166 template <
typename Graph_T>
167 bfs_update(Graph_T& g,
const ossia::graph_setup_options& opt)
168 : m_color{boost::make_two_bit_color_map_fast(
169 0, boost::get(boost::vertex_index, g.m_graph))}
173 template <
typename Graph_T,
typename DevicesT>
174 void operator()(Graph_T& g,
const DevicesT& devices)
176 auto& m_graph = g.m_graph;
177 auto& m_nodes = g.m_nodes;
178 auto& m_all_nodes = g.m_all_nodes;
179 const auto N = boost::num_vertices(m_graph);
182 m_sub_graph = m_graph;
184 g.sort_all_nodes(m_graph);
187 for(std::size_t i = 0; i < N; i++)
189 ossia::graph_node* n1 = m_all_nodes[i];
190 for(std::size_t j = i + 1; j < N; j++)
192 ossia::graph_node* n2 = m_all_nodes[j];
194 auto source_vtx = m_nodes.find(n1)->second;
195 auto sink_vtx = m_nodes.find(n2)->second;
196 if(find_path(source_vtx, sink_vtx, m_sub_graph))
198 if(find_path(sink_vtx, source_vtx, m_sub_graph))
201 if(graph_util::find_address_connection(*n1, *n2, devices))
203 auto src_it = m_nodes.find(n1);
204 auto sink_it = m_nodes.find(n2);
205 assert(src_it != m_nodes.end());
206 assert(sink_it != m_nodes.end());
207 auto edge = g.allocate_edge(
208 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
209 src_it->first, sink_it->first);
210 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
212 #if defined(OSSIA_GRAPH_DEBUG)
213 auto all_nodes_old = std::move(m_all_nodes);
215 sort_all_nodes(sub_graph);
216 m_all_nodes = std::move(all_nodes_old);
219 else if(graph_util::find_address_connection(*n2, *n1, devices))
221 auto src_it = m_nodes.find(n2);
222 auto sink_it = m_nodes.find(n1);
223 auto edge = g.allocate_edge(
224 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
225 src_it->first, sink_it->first);
226 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
228 #if defined(OSSIA_GRAPH_DEBUG)
229 auto all_nodes_old = std::move(m_all_nodes);
231 sort_all_nodes(sub_graph);
232 m_all_nodes = std::move(all_nodes_old);
238 g.sort_all_nodes(m_sub_graph);
241 bool find_path(graph_vertex_t source, graph_vertex_t sink, graph_t& graph)
244 struct bfs_find_visitor
246 graph_vertex_t node_to_find{};
248 bool discover_vertex(graph_vertex_t u,
const graph_t&)
const noexcept
250 if(u == node_to_find)
258 const auto N = boost::num_vertices(graph);
259 if(m_queue.capacity() <= N)
260 m_queue.set_capacity(N);
264 ossia::bfs::breadth_first_search_simple(graph, source, to_find, m_queue, m_color);
270 boost::circular_buffer<graph_vertex_t> m_queue;
272 using pmap_type = decltype(boost::make_two_bit_color_map_fast(
273 0, get(boost::vertex_index, graph_t{})));
278 template <
typename Impl>
284 template <
typename Graph_T>
285 tc_update(Graph_T& g,
const ossia::graph_setup_options& opt)
288 template <
typename Graph_T,
typename DevicesT>
289 void operator()(Graph_T& g,
const DevicesT& devices)
291 m_sub_graph = g.m_graph;
293 g.sort_all_nodes(m_sub_graph);
295 impl.update(m_sub_graph);
297 tc_add_addresses(g, g.m_graph, m_sub_graph, g.m_nodes, g.m_all_nodes, impl, devices);
299 g.sort_all_nodes(m_sub_graph);
306 typename BaseGraph,
typename TCGraph,
typename NodeMap,
typename AllNodes,
307 typename TC,
typename Devices>
308 static void tc_add_addresses(
309 auto& impl, BaseGraph& m_graph, TCGraph& m_sub_graph, NodeMap& m_nodes,
310 AllNodes& m_all_nodes, TC& tc, Devices& devices)
334 for(std::size_t i = 0; i < m_all_nodes.size(); i++)
336 ossia::graph_node* n1 = m_all_nodes[i];
337 for(std::size_t j = i + 1; j < m_all_nodes.size(); j++)
339 ossia::graph_node* n2 = m_all_nodes[j];
341 auto source_vtx = m_nodes.find(n1)->second;
342 auto sink_vtx = m_nodes.find(n2)->second;
343 if(tc.has_edge(source_vtx, sink_vtx))
345 if(tc.has_edge(sink_vtx, source_vtx))
348 if(graph_util::find_address_connection(*n1, *n2, devices))
350 auto src_it = m_nodes.find(n1);
351 auto sink_it = m_nodes.find(n2);
352 auto edge = impl.allocate_edge(
353 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
354 src_it->first, sink_it->first);
355 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
356 tc.update(m_sub_graph);
358 #if defined(OSSIA_GRAPH_DEBUG)
359 print_graph(transitive_closure, std::cout);
360 auto all_nodes_old = std::move(m_all_nodes);
362 sort_all_nodes(sub_graph);
363 m_all_nodes = std::move(all_nodes_old);
366 else if(graph_util::find_address_connection(*n2, *n1, devices))
368 auto src_it = m_nodes.find(n2);
369 auto sink_it = m_nodes.find(n1);
370 auto edge = impl.allocate_edge(
371 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
372 src_it->first, sink_it->first);
373 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
374 tc.update(m_sub_graph);
376 #if defined(OSSIA_GRAPH_DEBUG)
377 auto all_nodes_old = std::move(m_all_nodes);
379 sort_all_nodes(sub_graph);
380 m_all_nodes = std::move(all_nodes_old);
391 using transitive_closure_t = boost::adjacency_list<
392 boost::vecS, boost::vecS, boost::directedS, ossia::graph_node*, int64_t>;
394 [[nodiscard]]
bool has_edge(
int source_vtx,
int sink_vtx)
const
396 return boost::edge(source_vtx, sink_vtx, m_transitive_closure).second;
398 void update(
const graph_t& sub_graph)
400 m_transitive_closure = transitive_closure_t{};
401 ossia::transitive_closure(sub_graph, m_transitive_closure, m_tcState);
403 #if defined(OSSIA_GRAPH_DEBUG)
404 auto vertices = boost::vertices(sub_graph);
405 for(
auto i = vertices.first; i != vertices.second; i++)
407 tclos[*i] = sub_graph[*i].get();
410 print_graph(tclos, std::cout);
413 transitive_closure_t m_transitive_closure;
414 ossia::TransitiveClosureState<graph_t, transitive_closure_t> m_tcState;
420 using transitive_closure_t = boost::adjacency_list<
421 boost::vecS, boost::vecS, boost::directedS, ossia::graph_node*, int64_t>;
423 [[nodiscard]]
bool has_edge(
int source_vtx,
int sink_vtx)
const
425 return boost::edge(source_vtx, sink_vtx, m_transitive_closure).second;
428 void update(
const graph_t& sub_graph)
430 m_transitive_closure = transitive_closure_t{};
431 boost::transitive_closure(sub_graph, m_transitive_closure);
433 #if defined(OSSIA_GRAPH_DEBUG)
434 auto vertices = boost::vertices(sub_graph);
435 for(
auto i = vertices.first; i != vertices.second; i++)
437 tclos[*i] = sub_graph[*i].get();
440 print_graph(tclos, std::cout);
445 transitive_closure_t m_transitive_closure;
448 using tc_graph = graph_static<tc_update<fast_tc>, static_exec>;
449 using bfs_graph = graph_static<bfs_update, static_exec>;
451 using logged_tc_graph = graph_static<tc_update<fast_tc>, static_exec_logger>;
spdlog::logger & logger() noexcept
Where the errors will be logged. Default is stderr.
Definition: context.cpp:104
std::ostream & print(std::ostream &out, const state_element &e)
print Print a state_element
Definition: state_element.cpp:23