OpenFPM_pdata  1.1.0
Project that contain the implementation of distributed structures
 All Data Structures Namespaces Functions Variables Typedefs Enumerations Friends Pages
graph_unit_tests.hpp
1 /*
2  * graph_unit_test.hpp
3  *
4  * Created on: Nov 22, 2014
5  * Author: i-bird
6  */
7 
8 #ifndef GRAPH_UNIT_TEST_HPP_
9 #define GRAPH_UNIT_TEST_HPP_
10 
11 #include "config.h"
12 #include "map_graph.hpp"
13 #include "Point_test.hpp"
14 
15 #ifdef TEST_COVERAGE_MODE
16 #define GS_SIZE 8
17 #else
18 #define GS_SIZE 128
19 #endif
20 
21 BOOST_AUTO_TEST_SUITE( graph_test )
22 
23 BOOST_AUTO_TEST_CASE( graph_use)
24 {
25  std::cout << "Graph unit test start" << "\n";
26 
28  typedef Point_test<float> V;
29  typedef Point_test<float> E;
31 
32  // Point
34  p.setx(1.0);
35  p.sety(2.0);
36  p.setz(3.0);
37  p.sets(4.0);
38 
39  p.get<V::v>()[0] = 1.0;
40  p.get<V::v>()[1] = 2.0;
41  p.get<V::v>()[2] = 7.0;
42 
43  p.get<V::t>()[0][0] = 10.0;
44  p.get<V::t>()[0][1] = 13.0;
45  p.get<V::t>()[0][2] = 8.0;
46  p.get<V::t>()[1][0] = 19.0;
47  p.get<V::t>()[1][1] = 23.0;
48  p.get<V::t>()[1][2] = 5.0;
49  p.get<V::t>()[2][0] = 4.0;
50  p.get<V::t>()[2][1] = 3.0;
51  p.get<V::t>()[2][2] = 11.0;
52 
54 
57 
59 
60  // first create the vertex
61 
62  for (size_t i = 0 ; i < GS_SIZE ; i++)
63  {
64  for (size_t j = 0 ; j < GS_SIZE ; j++)
65  {
66  // Add vertex
67 
68  g.addVertex(p);
69  }
70  }
71 
72  // than create the edge
73 
74  // Create a grid, // NOTE this does not produce any memory grid, it retain only the information
75  // and give a set of usefull function
76 
77 
78 /* std::vector<size_t> gs;
79  gs.push_back(GS_SIZE);
80  gs.push_back(GS_SIZE);*/
81 
82  size_t gs[2] = {GS_SIZE,GS_SIZE};
83 
84  grid_sm<2,void> g2(gs);
85 
86  // Create the edge 4 for each vertex
87 
88  for (size_t i = 0 ; i < GS_SIZE ; i++)
89  {
90  for (size_t j = 0 ; j < GS_SIZE ; j++)
91  {
92  // Add 4 edge
93 
94  g.addEdge<CheckExistence>(g2.Lin(i,j),g2.Lin(i+1,j),p);
95  g.addEdge<CheckExistence>(g2.Lin(i,j),g2.Lin(i,j+1),p);
96  g.addEdge<CheckExistence>(g2.Lin(i,j),g2.Lin(i-1,j),p);
97  g.addEdge<CheckExistence>(g2.Lin(i,j),g2.Lin(i,j-1),p);
98  }
99  }
100 
102 
103  // Test if duplicate work
104 
105  Graph_CSR<V,E> g_dup = g.duplicate();
106 
107  // check if the two graph matches
108 
109  for (size_t i = 0 ; i < g.getNVertex() ; i++)
110  {
111  BOOST_REQUIRE_EQUAL(g.vertex(i).template get<V::x>(),g_dup.vertex(i).template get<V::x>());
112  BOOST_REQUIRE_EQUAL(g.vertex(i).template get<V::y>(),g_dup.vertex(i).template get<V::y>());
113  BOOST_REQUIRE_EQUAL(g.vertex(i).template get<V::z>(),g_dup.vertex(i).template get<V::z>());
114  BOOST_REQUIRE_EQUAL(g.vertex(i).template get<V::s>(),g_dup.vertex(i).template get<V::s>());
115 
116  for (int j = 0 ; j < 3 ; j++)
117  {
118  BOOST_REQUIRE_EQUAL(g.vertex(i).template get<V::v>()[j],g_dup.vertex(i).template get<V::v>()[j]);
119  }
120 
121  for (int j = 0 ; j < 3 ; j++)
122  {
123  for (int k = 0 ; k < 3 ; k++)
124  {
125  BOOST_REQUIRE_EQUAL(g.vertex(i).template get<V::t>()[j][k],g_dup.vertex(i).template get<V::t>()[j][k]);
126  }
127  }
128  }
129 
130  // Test the no edge case
131 
133  Graph_CSR<V> g_no_edge;
134 
135  // Create a tree
136 
137  // root
138  g_no_edge.addVertex(p);
139 
140  // 2 leaf
141 
142  g_no_edge.addVertex(p);
143  g_no_edge.addEdge(0,1);
144  g_no_edge.addVertex(p);
145  g_no_edge.addEdge(0,2);
146 
147  // 4 leaf
148 
149  g_no_edge.addVertex(p);
150  g_no_edge.addEdge(1,3);
151  g_no_edge.addVertex(p);
152  g_no_edge.addEdge(1,4);
153  g_no_edge.addVertex(p);
154  g_no_edge.addEdge(2,5);
155  g_no_edge.addVertex(p);
156  g_no_edge.addEdge(2,6);
157 
158  // 8 leaf
159 
160  g_no_edge.addVertex(p);
161  g_no_edge.addEdge(3,7);
162  g_no_edge.addVertex(p);
163  g_no_edge.addEdge(3,8);
164  g_no_edge.addVertex(p);
165  g_no_edge.addEdge(4,9);
166  g_no_edge.addVertex(p);
167  g_no_edge.addEdge(4,10);
168  g_no_edge.addVertex(p);
169  g_no_edge.addEdge(5,11);
170  g_no_edge.addVertex(p);
171  g_no_edge.addEdge(5,12);
172  g_no_edge.addVertex(p);
173  g_no_edge.addEdge(6,13);
174  g_no_edge.addVertex(p);
175  g_no_edge.addEdge(6,14);
176 
178 
179  // Check that each vertex has 2 child
180 
181  for (size_t i = 0 ; i < g_no_edge.getNVertex() ; i++)
182  {
183  if (g_no_edge.getNChilds(i) == 0)
184  continue;
185 
186  size_t s1 = g_no_edge.getChild(i,0);
187  size_t s2 = g_no_edge.getChild(i,1);
188 
189  BOOST_REQUIRE_EQUAL(s1+1,s2);
190 
191  size_t a = log2(i + 1);
192  size_t start = (a == 0)?1:(2 << (a-1));
193  start -= 1;
194  size_t start_p = 2 << a;
195  start_p -= 1;
196 
197  BOOST_REQUIRE_EQUAL(s1,start_p + (i - start)*2);
198  }
199 
200  std::cout << "Graph unit test end" << "\n";
201 }
202 
203 BOOST_AUTO_TEST_SUITE_END()
204 
205 
206 #endif /* GRAPH_UNIT_TEST_HPP_ */
Graph_CSR< V, E, Memory, layout_v, layout_e, layout_v_base, layout_e_base, grow_p > duplicate() const
It duplicate the graph.
Definition: map_graph.hpp:463
void addVertex(const V &vrt)
add vertex
Definition: map_graph.hpp:844
void setz(T z_)
set the z property
Definition: Point_test.hpp:190
size_t getChild(size_t v, size_t i) const
Get the child vertex id.
Definition: map_graph.hpp:796
void setx(T x_)
set the x property
Definition: Point_test.hpp:176
boost::fusion::result_of::at< type, boost::mpl::int_< i > >::type get()
getter method for a general property i
Definition: Point_test.hpp:218
auto addEdge(size_t v1, size_t v2, const E &ed) -> decltype(e.get(0))
add edge on the graph
Definition: map_graph.hpp:884
auto vertex(size_t id) -> decltype(v.get(id))
Function to access the vertex.
Definition: map_graph.hpp:600
size_t getNVertex() const
Return the number of the vertex.
Definition: map_graph.hpp:1029
Declaration grid_sm.
Definition: grid_sm.hpp:71
size_t getNChilds(size_t c) const
Return the number of childs of a vertex.
Definition: map_graph.hpp:752
void sets(T s_)
set the s property
Definition: Point_test.hpp:197
void sety(T y_)
set the y property
Definition: Point_test.hpp:183
Test structure used for several test.
Definition: Point_test.hpp:105
Class to check if the edge can be created or not.
Definition: grid_sm.hpp:51