1 /*
2 IGraph library.
3 Copyright (C) 2021 The igraph development team <igraph@igraph.org>
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>.
17 */
18
19 #include <igraph.h>
20
21 #include "test_utilities.inc"
22
main()23 int main() {
24 igraph_t g;
25 igraph_vector_t outdeg, indeg, degrees, empty;
26 igraph_bool_t is_simple, is_connected;
27
28 igraph_real_t outarr[] = {2, 3, 2, 3, 3, 3, 3, 1, 4, 4};
29 igraph_real_t inarr[] = {3, 6, 2, 0, 2, 2, 4, 3, 3, 3};
30
31 long int n = sizeof(outarr) / sizeof(igraph_real_t);
32
33 igraph_rng_seed(igraph_rng_default(), 333);
34
35 igraph_vector_view(&outdeg, outarr, n);
36 igraph_vector_view(&indeg, inarr, n);
37
38 igraph_vector_init(&empty, 0);
39
40 /* This vector is used to check that the degrees of the result
41 * match the requested degrees. */
42 igraph_vector_init(°rees, 0);
43
44 /* Configuration model, undirected non-simple graphs */
45
46 igraph_degree_sequence_game(&g, &outdeg, NULL, IGRAPH_DEGSEQ_SIMPLE);
47
48 IGRAPH_ASSERT(! igraph_is_directed(&g));
49 IGRAPH_ASSERT(igraph_vcount(&g) == n);
50
51 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);
52 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
53
54 igraph_destroy(&g);
55
56 igraph_degree_sequence_game(&g, &empty, NULL, IGRAPH_DEGSEQ_SIMPLE);
57 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
58 igraph_destroy(&g);
59
60
61 /* Configuration model, directed non-simple graphs */
62
63 igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_SIMPLE);
64
65 IGRAPH_ASSERT(igraph_is_directed(&g));
66 IGRAPH_ASSERT(igraph_vcount(&g) == n);
67
68 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_OUT, IGRAPH_LOOPS);
69 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
70
71 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_IN, IGRAPH_LOOPS);
72 IGRAPH_ASSERT(igraph_vector_all_e(&indeg, °rees));
73
74 igraph_destroy(&g);
75
76 igraph_degree_sequence_game(&g, &empty, &empty, IGRAPH_DEGSEQ_SIMPLE);
77 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
78 igraph_destroy(&g);
79
80
81 /* Configuration model, undirected simple graphs */
82
83 igraph_degree_sequence_game(&g, &outdeg, NULL, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM);
84
85 IGRAPH_ASSERT(! igraph_is_directed(&g));
86 IGRAPH_ASSERT(igraph_vcount(&g) == n);
87
88 igraph_is_simple(&g, &is_simple);
89 IGRAPH_ASSERT(is_simple);
90
91 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);
92 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
93
94 igraph_destroy(&g);
95
96 igraph_degree_sequence_game(&g, &empty, NULL, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM);
97 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
98 igraph_destroy(&g);
99
100
101 /* Configuration model, directed simple graphs */
102
103 igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM);
104
105 IGRAPH_ASSERT(igraph_is_directed(&g));
106 IGRAPH_ASSERT(igraph_vcount(&g) == n);
107
108 igraph_is_simple(&g, &is_simple);
109 IGRAPH_ASSERT(is_simple);
110
111 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_OUT, IGRAPH_LOOPS);
112 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
113
114 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_IN, IGRAPH_LOOPS);
115 IGRAPH_ASSERT(igraph_vector_all_e(&indeg, °rees));
116
117 igraph_destroy(&g);
118
119 igraph_degree_sequence_game(&g, &empty, &empty, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE_UNIFORM);
120 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
121 igraph_destroy(&g);
122
123
124 /* Fast heuristic method, undirected simple graphs */
125
126 igraph_degree_sequence_game(&g, &outdeg, NULL, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE);
127
128 IGRAPH_ASSERT(! igraph_is_directed(&g));
129 IGRAPH_ASSERT(igraph_vcount(&g) == n);
130
131 igraph_is_simple(&g, &is_simple);
132 IGRAPH_ASSERT(is_simple);
133
134 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);
135 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
136
137 igraph_destroy(&g);
138
139 igraph_degree_sequence_game(&g, &empty, NULL, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE);
140 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
141 igraph_destroy(&g);
142
143
144 /* Fast heuristic method, directed simple graphs */
145
146 igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE);
147
148 IGRAPH_ASSERT(igraph_is_directed(&g));
149 IGRAPH_ASSERT(igraph_vcount(&g) == n);
150
151 igraph_is_simple(&g, &is_simple);
152 IGRAPH_ASSERT(is_simple);
153
154 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_OUT, IGRAPH_LOOPS);
155 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
156
157 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_IN, IGRAPH_LOOPS);
158 IGRAPH_ASSERT(igraph_vector_all_e(&indeg, °rees));
159
160 igraph_destroy(&g);
161
162 igraph_degree_sequence_game(&g, &empty, &empty, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE);
163 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
164 igraph_destroy(&g);
165
166
167 /* Viger-Latapy method, undirected connected simple graphs */
168
169 igraph_degree_sequence_game(&g, &outdeg, NULL, IGRAPH_DEGSEQ_VL);
170
171 IGRAPH_ASSERT(! igraph_is_directed(&g));
172 IGRAPH_ASSERT(igraph_vcount(&g) == n);
173
174 igraph_is_simple(&g, &is_simple);
175 IGRAPH_ASSERT(is_simple);
176
177 igraph_is_connected(&g, &is_connected, IGRAPH_WEAK);
178 IGRAPH_ASSERT(is_connected);
179
180 igraph_degree(&g, °rees, igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);
181 IGRAPH_ASSERT(igraph_vector_all_e(&outdeg, °rees));
182
183 igraph_destroy(&g);
184
185 igraph_degree_sequence_game(&g, &empty, NULL, IGRAPH_DEGSEQ_VL);
186 IGRAPH_ASSERT(! igraph_is_directed(&g));
187 IGRAPH_ASSERT(igraph_vcount(&g) == 0);
188 igraph_destroy(&g);
189
190 VERIFY_FINALLY_STACK();
191
192 /* This degree sequence contains a zero degree, so it cannot be realized by a connected graph. */
193 CHECK_ERROR(igraph_degree_sequence_game(&g, &indeg, NULL, IGRAPH_DEGSEQ_VL), IGRAPH_EINVAL);
194
195 igraph_vector_destroy(°rees);
196 igraph_vector_destroy(&empty);
197
198 VERIFY_FINALLY_STACK();
199
200 return 0;
201 }
202