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>
19template <
typename UpdateImpl,
typename TickImpl>
20struct 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#if !defined(OSSIA_FREESTANDING)
33 m_all_nodes.reserve(1024);
34 m_enabled_cache.reserve(1024);
35 m_topo_order_cache.reserve(1024);
36 m_color_map_cache.reserve(1024);
37 m_stack_cache.reserve(1024);
40 ~graph_static()
override { clear(); }
42 void sort_all_nodes(
const graph_t& gr)
48 m_all_nodes.reserve(m_nodes.size());
51 m_topo_order_cache.clear();
52 m_topo_order_cache.reserve(m_nodes.size());
53 custom_topological_sort(
54 gr, std::back_inserter(m_topo_order_cache), m_color_map_cache, m_stack_cache);
57 for(
auto vtx : m_topo_order_cache)
59 auto node = gr[vtx].get();
61 if(node->root_inputs().empty() && node->root_outputs().empty())
63 m_all_nodes.push_back(node);
67 for(
auto vtx : m_topo_order_cache)
69 auto node = gr[vtx].get();
72 if(!(node->root_inputs().empty() && node->root_outputs().empty()))
74 m_all_nodes.push_back(node);
81 std::cout <<
"Error: graph isn't a DAG: ";
82 print_graph(gr, std::cout);
83 std::cout << std::endl;
88 void state(execution_state& e)
override
94 update_fun(*
this, e.exec_devices());
95 m_enabled_cache.clear();
100 m_enabled_cache.reserve(m_nodes.size());
102 for(
auto node : m_all_nodes)
104 ossia::graph_node& ptr = *node;
107 m_enabled_cache.insert(&ptr);
111 auto it = m_enabled_cache.find(&ptr);
112 if(it != m_enabled_cache.end())
113 m_enabled_cache.erase(it);
117 disable_strict_nodes_rec(m_enabled_cache, m_disabled_cache);
119 tick_fun(*
this, update_fun, e, m_all_nodes);
121#if defined(OSSIA_EXECUTION_LOG)
122 auto log = g_exec_log.log_executed_nodes(m_graph, m_all_nodes);
125 finish_nodes(m_nodes);
127 catch(
const boost::not_a_dag&)
134 [[nodiscard]]
const graph_t& impl()
const {
return m_graph; }
135 graph_t& impl() {
return m_graph; }
136 std::vector<graph_node*> m_all_nodes;
139 void print(std::ostream& stream)
override { print_graph(m_graph, stream); }
142 node_flat_set m_enabled_cache;
143 node_flat_set m_disabled_cache;
144 std::vector<graph_vertex_t> m_topo_order_cache;
146 friend class ::DataflowTest;
151 ossia::graph_t& m_sub_graph;
152 template <
typename Graph_T>
153 simple_update(Graph_T& g,
const ossia::graph_setup_options& opt)
154 : m_sub_graph{g.m_graph}
158 template <
typename Graph_T,
typename DevicesT>
159 void operator()(Graph_T& g,
const DevicesT& devices)
161 g.sort_all_nodes(g.m_graph);
168 template <
typename Graph_T>
169 bfs_update(Graph_T& g,
const ossia::graph_setup_options& opt)
170 : m_color{boost::make_two_bit_color_map_fast(
171 0, boost::get(boost::vertex_index, g.m_graph))}
175 template <
typename Graph_T,
typename DevicesT>
176 void operator()(Graph_T& g,
const DevicesT& devices)
178 auto& m_graph = g.m_graph;
179 auto& m_nodes = g.m_nodes;
180 auto& m_all_nodes = g.m_all_nodes;
181 const auto N = boost::num_vertices(m_graph);
184 m_sub_graph = m_graph;
186 g.sort_all_nodes(m_graph);
189 for(std::size_t i = 0; i < N; i++)
191 ossia::graph_node* n1 = m_all_nodes[i];
192 for(std::size_t j = i + 1; j < N; j++)
194 ossia::graph_node* n2 = m_all_nodes[j];
196 auto source_vtx = m_nodes.find(n1)->second;
197 auto sink_vtx = m_nodes.find(n2)->second;
198 if(find_path(source_vtx, sink_vtx, m_sub_graph))
200 if(find_path(sink_vtx, source_vtx, m_sub_graph))
203 if(graph_util::find_address_connection(*n1, *n2, devices))
205 auto src_it = m_nodes.find(n1);
206 auto sink_it = m_nodes.find(n2);
207 assert(src_it != m_nodes.end());
208 assert(sink_it != m_nodes.end());
209 auto edge = g.allocate_edge(
210 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
211 src_it->first, sink_it->first);
212 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
214#if defined(OSSIA_GRAPH_DEBUG)
215 auto all_nodes_old = std::move(m_all_nodes);
217 sort_all_nodes(sub_graph);
218 m_all_nodes = std::move(all_nodes_old);
221 else if(graph_util::find_address_connection(*n2, *n1, devices))
223 auto src_it = m_nodes.find(n2);
224 auto sink_it = m_nodes.find(n1);
225 auto edge = g.allocate_edge(
226 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
227 src_it->first, sink_it->first);
228 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
230#if defined(OSSIA_GRAPH_DEBUG)
231 auto all_nodes_old = std::move(m_all_nodes);
233 sort_all_nodes(sub_graph);
234 m_all_nodes = std::move(all_nodes_old);
240 g.sort_all_nodes(m_sub_graph);
243 bool find_path(graph_vertex_t source, graph_vertex_t sink, graph_t& graph)
246 struct bfs_find_visitor
248 graph_vertex_t node_to_find{};
250 bool discover_vertex(graph_vertex_t u,
const graph_t&)
const noexcept
252 if(u == node_to_find)
260 const auto N = boost::num_vertices(graph);
261 if(m_queue.capacity() <= N)
262 m_queue.set_capacity(N);
266 ossia::bfs::breadth_first_search_simple(graph, source, to_find, m_queue, m_color);
272 boost::circular_buffer<graph_vertex_t> m_queue;
274 using pmap_type =
decltype(boost::make_two_bit_color_map_fast(
275 0, get(boost::vertex_index, graph_t{})));
280template <
typename Impl>
286 template <
typename Graph_T>
287 tc_update(Graph_T& g,
const ossia::graph_setup_options& opt)
290 template <
typename Graph_T,
typename DevicesT>
291 void operator()(Graph_T& g,
const DevicesT& devices)
293 m_sub_graph = g.m_graph;
295 g.sort_all_nodes(m_sub_graph);
297 impl.update(m_sub_graph);
299 tc_add_addresses(g, g.m_graph, m_sub_graph, g.m_nodes, g.m_all_nodes, impl, devices);
301 g.sort_all_nodes(m_sub_graph);
308 typename BaseGraph,
typename TCGraph,
typename NodeMap,
typename AllNodes,
309 typename TC,
typename Devices>
310 static void tc_add_addresses(
311 auto& impl, BaseGraph& m_graph, TCGraph& m_sub_graph, NodeMap& m_nodes,
312 AllNodes& m_all_nodes, TC& tc, Devices& devices)
336 for(std::size_t i = 0; i < m_all_nodes.size(); i++)
338 ossia::graph_node* n1 = m_all_nodes[i];
339 for(std::size_t j = i + 1; j < m_all_nodes.size(); j++)
341 ossia::graph_node* n2 = m_all_nodes[j];
343 auto source_vtx = m_nodes.find(n1)->second;
344 auto sink_vtx = m_nodes.find(n2)->second;
345 if(tc.has_edge(source_vtx, sink_vtx))
347 if(tc.has_edge(sink_vtx, source_vtx))
350 if(graph_util::find_address_connection(*n1, *n2, devices))
352 auto src_it = m_nodes.find(n1);
353 auto sink_it = m_nodes.find(n2);
354 auto edge = impl.allocate_edge(
355 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
356 src_it->first, sink_it->first);
357 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
358 tc.update(m_sub_graph);
360#if defined(OSSIA_GRAPH_DEBUG)
361 print_graph(transitive_closure, std::cout);
362 auto all_nodes_old = std::move(m_all_nodes);
364 sort_all_nodes(sub_graph);
365 m_all_nodes = std::move(all_nodes_old);
368 else if(graph_util::find_address_connection(*n2, *n1, devices))
370 auto src_it = m_nodes.find(n2);
371 auto sink_it = m_nodes.find(n1);
372 auto edge = impl.allocate_edge(
373 ossia::dependency_connection{}, ossia::outlet_ptr{}, ossia::inlet_ptr{},
374 src_it->first, sink_it->first);
375 boost::add_edge(sink_it->second, src_it->second, edge, m_sub_graph);
376 tc.update(m_sub_graph);
378#if defined(OSSIA_GRAPH_DEBUG)
379 auto all_nodes_old = std::move(m_all_nodes);
381 sort_all_nodes(sub_graph);
382 m_all_nodes = std::move(all_nodes_old);
393 using transitive_closure_t = boost::adjacency_list<
394 boost::vecS, boost::vecS, boost::directedS, ossia::graph_node*, int64_t>;
396 [[nodiscard]]
bool has_edge(
int source_vtx,
int sink_vtx)
const
398 return boost::edge(source_vtx, sink_vtx, m_transitive_closure).second;
400 void update(
const graph_t& sub_graph)
402 m_transitive_closure = transitive_closure_t{};
403 ossia::transitive_closure(sub_graph, m_transitive_closure, m_tcState);
405#if defined(OSSIA_GRAPH_DEBUG)
406 auto vertices = boost::vertices(sub_graph);
407 for(
auto i = vertices.first; i != vertices.second; i++)
409 tclos[*i] = sub_graph[*i].get();
412 print_graph(tclos, std::cout);
415 transitive_closure_t m_transitive_closure;
416 ossia::TransitiveClosureState<graph_t, transitive_closure_t> m_tcState;
422 using transitive_closure_t = boost::adjacency_list<
423 boost::vecS, boost::vecS, boost::directedS, ossia::graph_node*, int64_t>;
425 [[nodiscard]]
bool has_edge(
int source_vtx,
int sink_vtx)
const
427 return boost::edge(source_vtx, sink_vtx, m_transitive_closure).second;
430 void update(
const graph_t& sub_graph)
432 m_transitive_closure = transitive_closure_t{};
433 boost::transitive_closure(sub_graph, m_transitive_closure);
435#if defined(OSSIA_GRAPH_DEBUG)
436 auto vertices = boost::vertices(sub_graph);
437 for(
auto i = vertices.first; i != vertices.second; i++)
439 tclos[*i] = sub_graph[*i].get();
442 print_graph(tclos, std::cout);
447 transitive_closure_t m_transitive_closure;
450using tc_graph = graph_static<tc_update<fast_tc>, static_exec>;
451using bfs_graph = graph_static<bfs_update, static_exec>;
453using 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:118
std::ostream & print(std::ostream &out, const state_element &e)
print Print a state_element
Definition state_element.cpp:23