1 /*
2 Copyright (c) 2008-2018, Benoit AUTHEMAN All rights reserved.
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the above copyright
9 notice, this list of conditions and the following disclaimer in the
10 documentation and/or other materials provided with the distribution.
11 * Neither the name of the author or Destrat.io nor the
12 names of its contributors may be used to endorse or promote products
13 derived from this software without specific prior written permission.
14
15 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY
19 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 //-----------------------------------------------------------------------------
28 // This file is a part of the GTpo software.
29 //
30 // \file gtpo_topology_tests.cpp
31 // \author benoit@qanava.org
32 // \date 2016 01 26
33 //-----------------------------------------------------------------------------
34
35 // STD headers
36 #include <list>
37 #include <memory>
38 #include <iostream>
39
40 // GTpo headers
41 #include <GTpo>
42
43 // Google Test
44 #include <gtest/gtest.h>
45 #include <gmock/gmock.h>
46
47 //-----------------------------------------------------------------------------
48 // Graph node tests
49 //-----------------------------------------------------------------------------
50
TEST(GTpoTopology,nodeBasic)51 TEST(GTpoTopology, nodeBasic)
52 {
53 // A default empty graph should have no nodes nor root nodes
54 gtpo::graph<> g;
55 EXPECT_EQ( g.get_node_count(), 0 );
56 EXPECT_EQ( g.get_root_node_count(), 0 );
57 }
58
TEST(GTpoTopology,nodeInsertCount)59 TEST(GTpoTopology, nodeInsertCount)
60 {
61 // Inserting a node should increase node count and root node count
62 gtpo::graph<> g;
63 auto nc = g.get_node_count();
64 auto rnc = g.get_root_node_count();
65 EXPECT_EQ( nc, 0);
66 EXPECT_EQ( rnc, 0);
67 g.create_node();
68 EXPECT_EQ( g.get_node_count(), nc + 1 );
69 EXPECT_EQ( g.get_root_node_count(), rnc + 1 );
70 g.clear();
71 }
72
TEST(GTpoTopology,remove_nodeCount)73 TEST(GTpoTopology, remove_nodeCount)
74 {
75 gtpo::graph<> g;
76 gtpo::graph<>::weak_node_t n = g.create_node();
77 auto nc = g.get_node_count();
78 auto rnc = g.get_root_node_count();
79 g.install_root_node( n ); // Just a test, it should not be called by the user directly
80 EXPECT_TRUE( g.is_root_node( n ) );
81 EXPECT_TRUE( g.contains( n ) );
82 g.remove_node( n );
83 EXPECT_FALSE( g.contains( n ) );
84 EXPECT_EQ( g.get_node_count(), nc - 1 );
85 EXPECT_EQ( g.get_root_node_count(), rnc - 1 ) ;
86 g.create_node();
87 g.clear();
88 }
89
90 //-----------------------------------------------------------------------------
91 // Graph clear tests
92 //-----------------------------------------------------------------------------
93
TEST(GTpoTopology,graphClear)94 TEST(GTpoTopology, graphClear)
95 {
96 // TEST: clearing an empty graph, expecting no node after clearing an empty graph
97 gtpo::graph<> g;
98 EXPECT_EQ( g.get_node_count(), 0 );
99 g.clear();
100 EXPECT_EQ( g.get_node_count(), 0 );
101 }
102
TEST(GTpoTopo,graphClearNode)103 TEST(GTpoTopo, graphClearNode)
104 {
105 // TEST: clearing a graph with one node should lead to an empty graph
106 gtpo::graph<> g;
107 auto n = g.create_node();
108 EXPECT_TRUE( g.is_root_node( n ) );
109 EXPECT_TRUE( g.contains( n ) );
110 g.clear();
111 EXPECT_FALSE( g.contains( n ) );
112 EXPECT_EQ( g.get_node_count(), 0 );
113 EXPECT_TRUE( n.expired() );
114 }
115
TEST(GTpoTopology,graphClearNodeEdge)116 TEST(GTpoTopology, graphClearNodeEdge)
117 {
118 // TEST: clearing a graph with two nodes linked by an edge should lead to an empty graph
119 gtpo::graph<> g;
120 auto n1 = g.create_node();
121 auto n2 = g.create_node();
122 auto e1 = g.create_edge<gtpo::edge<>>(n1, n2);
123 EXPECT_EQ( g.get_node_count(), 2 );
124 EXPECT_TRUE( g.contains(e1) );
125 g.clear();
126 EXPECT_EQ( g.get_node_count(), 0 );
127 EXPECT_FALSE( g.contains(e1) );
128 EXPECT_TRUE( n1.expired() );
129 EXPECT_TRUE( n2.expired() );
130 EXPECT_TRUE( e1.expired() );
131 EXPECT_EQ( g.get_edge_count(),0 );
132 }
133
134 //-----------------------------------------------------------------------------
135 // Graph edge tests
136 //-----------------------------------------------------------------------------
137
TEST(GTpoTopology,edgeBasic)138 TEST(GTpoTopology, edgeBasic)
139 {
140 // A default empty graph should have no edges
141 gtpo::graph<> g;
142 EXPECT_EQ( g.get_edge_count(), 0 );
143 }
144
TEST(GTpoTopology,edgeCreateBadTopology)145 TEST(GTpoTopology, edgeCreateBadTopology)
146 {
147 // TEST: Creating an edge with no source and/or destination should throw a bad_topology_error
148 gtpo::graph<> g;
149 auto n1 = g.create_node();
150 EXPECT_THROW( g.create_edge(n1, gtpo::graph<>::weak_node_t{}), gtpo::bad_topology_error );
151 EXPECT_THROW( g.create_edge(gtpo::graph<>::weak_node_t{}, gtpo::graph<>::weak_node_t{}), gtpo::bad_topology_error );
152 EXPECT_THROW( g.create_edge(gtpo::graph<>::weak_node_t{}, n1), gtpo::bad_topology_error );
153
154 auto n2 = g.create_node();
155 EXPECT_NO_THROW( g.create_edge(n1, n2) );
156 }
157
TEST(GTpoTopology,edgeCreate)158 TEST(GTpoTopology, edgeCreate)
159 {
160 // TEST: Creating an edge should remove dst from the root node set
161 gtpo::graph<> g;
162 auto n1 = g.create_node();
163 auto n2 = g.create_node();
164 EXPECT_TRUE( ( g.get_root_node_count() == 2 ) );
165 auto e = g.create_edge(n1, n2);
166 EXPECT_TRUE( ( g.get_root_node_count() == 1 ) ); // n2 is no longer a root node
167 }
168
TEST(GTpoTopology,edgeCreateBasicCircuit)169 TEST(GTpoTopology, edgeCreateBasicCircuit)
170 {
171 // TEST: Creating an edge that is a circuit to a root node does not remove destination
172 // from root nodes
173 { // Test with create_edge()
174 gtpo::graph<> g;
175 EXPECT_TRUE( g.get_root_node_count() == 0 );
176 auto n1 = g.create_node();
177 EXPECT_TRUE( g.get_root_node_count() == 1 );
178 g.create_edge( n1, n1 );
179 EXPECT_TRUE( g.get_root_node_count() == 1 );
180 }
181 { // Test with insert_edge()
182 gtpo::graph<> g;
183 EXPECT_TRUE( g.get_root_node_count() == 0 );
184 auto n1 = g.create_node();
185 EXPECT_TRUE( g.get_root_node_count() == 1 );
186 auto e1 = std::make_shared<gtpo::edge<>>(n1, n1);
187 g.insert_edge( e1 );
188 EXPECT_TRUE( g.get_root_node_count() == 1 );
189 }
190 }
191
TEST(GTpoTopology,edgeInsertRootNode)192 TEST(GTpoTopology, edgeInsertRootNode)
193 {
194 // TEST: inserting an existing edge must remove dst from the root node set
195 gtpo::graph<> g;
196 auto n1 = g.create_node();
197 auto n2 = g.create_node();
198 auto e1 = std::make_shared<gtpo::edge<>>(n1, n2);
199 EXPECT_EQ( g.get_root_node_count(), 2 );
200 g.insert_edge(e1);
201 EXPECT_EQ( g.get_root_node_count(), 1 ); // n2 is no longer a root node
202 }
203
TEST(GTpoTopology,edgeCreateRootNode)204 TEST(GTpoTopology, edgeCreateRootNode)
205 {
206 // TEST: inserting an existing edge must remove dst from the root node set
207 gtpo::graph<> g;
208 EXPECT_EQ( g.get_root_node_count(), 0 );
209 auto n1 = g.create_node();
210 auto n2 = g.create_node();
211 EXPECT_EQ( g.get_root_node_count(), 2 );
212 g.create_edge(n1, n2);
213 EXPECT_EQ( g.get_root_node_count(), 1 ); // n2 is no longer a root node
214 }
215
TEST(GTpoTopology,edgeInsertBadTopology)216 TEST(GTpoTopology, edgeInsertBadTopology)
217 {
218 // TEST: Inserting an edge with no source and/or destination should throw a bad_topology_error
219 gtpo::graph<> g;
220 auto n1 = g.create_node();
221 auto n2 = g.create_node();
222 EXPECT_THROW( g.insert_edge(gtpo::graph<>::shared_edge_t{}), gtpo::bad_topology_error );
223 auto e1 = std::make_shared<gtpo::edge<>>(n1, gtpo::graph<>::weak_node_t{});
224 auto e2 = std::make_shared<gtpo::edge<>>(gtpo::graph<>::weak_node_t{}, gtpo::graph<>::weak_node_t{});
225 auto e3 = std::make_shared<gtpo::edge<>>(gtpo::graph<>::weak_node_t{}, n1);
226
227 // Test error with insert_edge()
228 EXPECT_THROW( g.insert_edge(e1), gtpo::bad_topology_error );
229 EXPECT_THROW( g.insert_edge(e2), gtpo::bad_topology_error );
230 EXPECT_THROW( g.insert_edge(e3), gtpo::bad_topology_error );
231
232 // Test error with create_edge()
233 EXPECT_THROW( g.create_edge(n1, gtpo::graph<>::weak_node_t{}), gtpo::bad_topology_error );
234 EXPECT_THROW( g.create_edge(gtpo::graph<>::weak_node_t{}, n1), gtpo::bad_topology_error );
235 EXPECT_THROW( g.create_edge(gtpo::graph<>::weak_node_t{}, gtpo::graph<>::weak_node_t{}), gtpo::bad_topology_error );
236
237 // Test success with insert_edge()
238 auto e4 = std::make_shared<gtpo::edge<>>(n1, n2);
239 EXPECT_NO_THROW( g.insert_edge(e4) );
240
241 // Test success with create_edge()
242 EXPECT_NO_THROW( g.create_edge(n1, n2) );
243 }
244
TEST(GTpoTopology,edgeInsertparallel)245 TEST(GTpoTopology, edgeInsertparallel)
246 {
247 { // Test if create_edge() successfully generate parallel edges
248 gtpo::graph<> g;
249 auto n1 = g.create_node();
250 auto n2 = g.create_node();
251 auto n3 = g.create_node();
252 auto n4 = g.create_node();
253 g.create_edge(n1, n2);
254 EXPECT_EQ( g.get_edge_count(n1, n2), 1 );
255 g.create_edge(n2, n3);
256 g.create_edge(n2, n3);
257 g.create_edge(n2, n3);
258 EXPECT_EQ( g.get_edge_count(n2, n3), 3 ); // Do not require, it depend on selected graph data structure
259 g.remove_edge(n2, n3);
260 EXPECT_EQ( g.get_edge_count(n2, n3), 2 ) ;
261 g.remove_all_edges(n2, n3);
262 EXPECT_EQ( g.get_edge_count(n2, n3), 0 ) ;
263 g.clear();
264 }
265
266 { // Test if insert_edge() successfully generate parallel edges
267 gtpo::graph<> g;
268 auto n1 = g.create_node();
269 auto n2 = g.create_node();
270 auto n3 = g.create_node();
271 auto n4 = g.create_node();
272
273 auto e1 = std::make_shared<gtpo::edge<>>(n1, n2);
274 g.insert_edge(e1);
275 EXPECT_EQ( g.get_edge_count(n1, n2), 1 );
276
277 auto e2 = std::make_shared<gtpo::edge<>>(n2, n3);
278 auto e3 = std::make_shared<gtpo::edge<>>(n2, n3);
279 auto e4 = std::make_shared<gtpo::edge<>>(n2, n3);
280 g.insert_edge(e2);
281 g.insert_edge(e3);
282 g.insert_edge(e3);
283 EXPECT_EQ( g.get_edge_count(n2, n3), 3 ); // Do not require, it depend on selected graph data structure
284 g.remove_edge(n2, n3);
285 EXPECT_EQ( g.get_edge_count(n2, n3), 2 ) ;
286 g.remove_all_edges(n2, n3);
287 EXPECT_EQ( g.get_edge_count(n2, n3), 0 ) ;
288 g.clear();
289 }
290 }
291
TEST(GTpoTopology,edgeRemoveContains)292 TEST(GTpoTopology, edgeRemoveContains)
293 {
294 // Graph must no longer contains() an edge that has been removed
295 gtpo::graph<> g;
296 auto n1 = g.create_node();
297 auto n2 = g.create_node();
298 EXPECT_EQ( g.get_edge_count(), 0 );
299 auto e1 = g.create_edge(n1, n2);
300 EXPECT_EQ( g.get_edge_count(), 1 );
301 EXPECT_TRUE( g.contains(e1) );
302 g.remove_edge(n1, n2);
303 EXPECT_FALSE( g.contains(e1) );
304 EXPECT_FALSE( g.has_edge(n1, n2) );
305 }
306
TEST(GTpoTopology,edgeNodeInOutDegree)307 TEST(GTpoTopology, edgeNodeInOutDegree)
308 {
309 gtpo::graph<> g;
310 auto n1 = g.create_node();
311 auto n2 = g.create_node();
312 auto n3 = g.create_node();
313 auto n4 = g.create_node();
314 EXPECT_EQ( g.get_root_node_count(), 4 );
315 g.create_edge(n1, n2);
316 EXPECT_EQ( g.get_root_node_count(), 3 );
317 g.create_edge(n2, n3);
318 g.create_edge(n2, n4);
319 EXPECT_EQ( g.get_root_node_count(), 1 );
320
321 // Check in/out degree after multiple edge insertion
322 gtpo::graph<>::shared_node_t node2 = n2.lock();
323 EXPECT_TRUE( node2 );
324 EXPECT_EQ( node2->get_in_degree(), 1 );
325 EXPECT_EQ( node2->get_out_degree(), 2 );
326 EXPECT_EQ( node2->get_in_edges().size(), 1 );
327 EXPECT_EQ( node2->get_out_edges().size(), 2 );
328 EXPECT_EQ( node2->get_in_nodes().size(), 1 );
329 EXPECT_EQ( node2->get_out_nodes().size(), 2 );
330
331 // Check in/out degree after multiple edge removal
332 ASSERT_THROW(g.remove_edge(n2, gtpo::graph<>::weak_node_t()), gtpo::bad_topology_error );
333 //INFO( "Incorrect remove_edge() calls successfully throw a gtpo::bad_topology_error" );
334 EXPECT_TRUE( g.has_edge( n2, n4 ) );
335 g.remove_edge(n2, n4);
336 EXPECT_FALSE( g.has_edge( n2, n4 ) );
337 g.remove_edge(n2, n3);
338 EXPECT_EQ( node2->get_out_degree(), 0 );
339 EXPECT_EQ( node2->get_out_edges().size(), 0 );
340 EXPECT_EQ( node2->get_out_nodes().size(), 0 );
341 EXPECT_EQ( g.get_root_node_count(), 3 );
342 EXPECT_TRUE( g.is_root_node( n3 ) );
343 EXPECT_TRUE( g.is_root_node( n4 ) );
344
345 g.clear();
346 }
347
TEST(GTpoTopology,remove_nodeInOutDegree)348 TEST(GTpoTopology, remove_nodeInOutDegree)
349 {
350 // Note: Test GTpo remove_node() method:
351 // - Removing a node must also invalidate (ie remove) all its out/in orphants edges.
352 gtpo::graph<> g;
353 auto wn1 = g.create_node();
354 auto wn2 = g.create_node();
355 auto wn3 = g.create_node();
356 g.create_edge(wn1, wn2);
357 g.create_edge(wn2, wn3);
358 // n1 now has 1 in node and 1 out node
359 auto n2 = wn2.lock();
360 EXPECT_EQ( n2->get_out_degree(), 1 );
361 EXPECT_EQ( n2->get_in_degree(), 1 );
362
363 // Removing node n2 should also remove all edges
364 g.remove_node( wn2 );
365 EXPECT_EQ( g.get_node_count(), 2 );
366 EXPECT_EQ( g.get_edge_count(), 0 );
367 auto n1 = wn1.lock();
368 auto n3 = wn3.lock();
369 EXPECT_EQ( n1->get_out_degree(), 0 );
370 EXPECT_EQ( n3->get_in_degree(), 0 );
371 }
372