1 /*
2     Copyright (c) 2005-2021 Intel Corporation
3 
4     Licensed under the Apache License, Version 2.0 (the "License");
5     you may not use this file except in compliance with the License.
6     You may obtain a copy of the License at
7 
8         http://www.apache.org/licenses/LICENSE-2.0
9 
10     Unless required by applicable law or agreed to in writing, software
11     distributed under the License is distributed on an "AS IS" BASIS,
12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13     See the License for the specific language governing permissions and
14     limitations under the License.
15 */
16 
17 #ifndef TBB_examples_parallel_preorder_graph_H
18 #define TBB_examples_parallel_preorder_graph_H
19 
20 #include <vector>
21 #include <atomic>
22 
23 #include "Matrix.hpp"
24 
25 enum OpKind {
26     // Use Cell's value
27     OP_VALUE,
28     // Unary negation
29     OP_NEGATE,
30     // Addition
31     OP_ADD,
32     // Subtraction
33     OP_SUB,
34     // Multiplication
35     OP_MUL
36 };
37 
38 static const int ArityOfOp[] = { 0, 1, 2, 2, 2 };
39 
40 class Cell {
41 public:
42     //! Operation for this cell
43     OpKind op;
44 
45     //! Inputs to this cell
46     Cell* input[2];
47 
48     //! Type of value stored in a Cell
49     typedef Matrix value_type;
50 
51     //! Value associated with this Cell
52     value_type value;
53 
54     //! Set of cells that use this Cell as an input
55     std::vector<Cell*> successor;
56 
57     //! Reference count of number of inputs that are not yet updated.
58     std::atomic<int> ref_count;
59 
60     //! Update the Cell's value.
61     void update();
62 
63     //! Default constructor
Cell()64     Cell() {}
65 
66     //! Copy constructor
67     Cell(const Cell& other);
68 };
69 
70 //! A directed graph where the vertices are Cells.
71 class Graph {
72     std::vector<Cell> my_vertex_set;
73 
74 public:
75     //! Create a random acyclic directed graph
76     void create_random_dag(std::size_t number_of_nodes);
77 
78     //! Print the graph
79     void print();
80 
81     //! Get set of cells that have no inputs.
82     void get_root_set(std::vector<Cell*>& root_set);
83 };
84 
85 #endif /* TBB_examples_parallel_preorder_graph_H */
86