1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif /* HAVE_CONFIG_H */
#include <check.h>
#include "Eina_Graph.h"
static void
_feed_simple_graph(Eina_Graph *g)
{
ck_assert(eina_graph_edge_add(g, 0, 5) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 4, 3) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 0, 1) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 9, 12) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 6, 4) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 5, 4) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 0, 2) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 11, 12) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 9, 10) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 0, 6) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 7, 8) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 9, 11) == EINA_TRUE);
ck_assert(eina_graph_edge_add(g, 5, 3) == EINA_TRUE);
}
START_TEST (test_eina_graph_simple_dfs)
{
Eina_Graph_DFS *dfs;
Eina_List *path, *l;
void *data;
int i;
unsigned int vsr[] = { 0, 5, 4, 3 };
unsigned int vss[] = { 0, 6, 4, 5, 3 };
ck_assert(eina_graph_init() == 1);
Eina_Graph *g = eina_graph_new(13, 2);
ck_assert(g != NULL);
_feed_simple_graph(g);
dfs = eina_graph_dfs_new(g, 0, EINA_TRUE);
ck_assert(eina_graph_dfs_source(dfs) == 0);
ck_assert(eina_graph_dfs_has_path_to(dfs, 12) == EINA_FALSE);
ck_assert(eina_graph_dfs_path_to(dfs, 12) == NULL);
ck_assert(eina_graph_dfs_path_to(dfs, 15) == NULL);
ck_assert(eina_graph_dfs_has_path_to(dfs, 3) == EINA_TRUE);
path = eina_graph_dfs_path_to(dfs, 3);
ck_assert(path != NULL);
ck_assert(eina_list_count(path) == (sizeof(vsr)/sizeof(*vsr)));
i = 0;
EINA_LIST_FOREACH(path, l, data)
{
ck_assert(vsr[i] == (unsigned int) data);
i++;
}
eina_graph_dfs_free(dfs);
dfs = eina_graph_dfs_new(g, 0, EINA_FALSE);
ck_assert(eina_graph_dfs_source(dfs) == 0);
ck_assert(eina_graph_dfs_has_path_to(dfs, 12) == EINA_FALSE);
ck_assert(eina_graph_dfs_path_to(dfs, 12) == NULL);
ck_assert(eina_graph_dfs_path_to(dfs, 15) == NULL);
ck_assert(eina_graph_dfs_has_path_to(dfs, 3) == EINA_TRUE);
path = eina_graph_dfs_path_to(dfs, 3);
ck_assert(path != NULL);
ck_assert(eina_list_count(path) == (sizeof(vss)/sizeof(*vss)));
i = 0;
EINA_LIST_FOREACH(path, l, data)
{
ck_assert(vss[i] == (unsigned int) data);
i++;
}
eina_graph_dfs_free(dfs);
eina_graph_free(g);
ck_assert(eina_graph_shutdown() == 0);
}
END_TEST
START_TEST (test_eina_graph_simple)
{
ck_assert(eina_graph_init() == 1);
ck_assert(eina_graph_init() == 2);
Eina_Graph *g = eina_graph_new(13, 2);
ck_assert(g != NULL);
_feed_simple_graph(g);
ck_assert(eina_graph_edge_add(g, -1, 3) == EINA_FALSE);
ck_assert(eina_graph_edge_add(g, 3, -1) == EINA_FALSE);
ck_assert(eina_graph_edge_add(g, 13, 3) == EINA_FALSE);
ck_assert(eina_graph_edge_add(g, 3, 13) == EINA_FALSE);
ck_assert(eina_graph_vertices_count(g) == 13);
ck_assert(eina_graph_edges_count(g) == 13);
ck_assert(eina_graph_degree(g, 4) == 3);
ck_assert(eina_graph_degree(g, 0) == 4);
ck_assert(eina_graph_degree(g, 15) == 0);
ck_assert(eina_graph_degree_max(g) == 4);
ck_assert(eina_graph_degree_avg(g) == 2.0);
ck_assert(eina_graph_self_loops(g) == 0);
ck_assert(eina_graph_edge_add(g, 0, 0) == EINA_TRUE);
ck_assert(eina_graph_vertices_count(g) == 13);
ck_assert(eina_graph_edges_count(g) == 14);
ck_assert(eina_graph_degree(g, 4) == 3);
ck_assert(eina_graph_degree(g, 0) == 5);
ck_assert(eina_graph_degree_max(g) == 5);
ck_assert(eina_graph_degree_avg(g) > 2.153);
ck_assert(eina_graph_degree_avg(g) < 2.154);
ck_assert(eina_graph_self_loops(g) == 1);
eina_graph_free(g);
ck_assert(eina_graph_shutdown() == 1);
ck_assert(eina_graph_shutdown() == 0);
}
END_TEST
Suite *
eina_graph_suite (void)
{
Suite *s = suite_create ("Eina Graph");
TCase *tc_simple = tcase_create ("Simple Graph");
tcase_add_test (tc_simple, test_eina_graph_simple);
suite_add_tcase (s, tc_simple);
TCase *tc_simple_dfs = tcase_create ("Simple Graph DFS");
tcase_add_test (tc_simple_dfs, test_eina_graph_simple_dfs);
suite_add_tcase (s, tc_simple_dfs);
return s;
}
int
main(int argc EINA_UNUSED, char *argv[] EINA_UNUSED)
{
int number_failed;
Suite *s = eina_graph_suite();
SRunner *sr = srunner_create(s);
srunner_run_all(sr, CK_ENV);
number_failed = srunner_ntests_failed(sr);
srunner_free(sr);
return ((number_failed == 0) ? 0: 1);
}
|
