1 /* -*- mode: C -*- */
2 /* vim:set ts=4 sw=4 sts=4 et: */
3 /*
4 IGraph library.
5 Copyright (C) 2003-2021 The igraph development team
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include "igraph_games.h"
25
26 #include "igraph_constructors.h"
27 #include "igraph_interface.h"
28 #include "igraph_nongraph.h"
29 #include "igraph_random.h"
30
31 /**
32 * \section about_games
33 *
34 * <para>Games are randomized graph generators. Randomization means that
35 * they generate a different graph every time you call them. </para>
36 */
37
igraph_erdos_renyi_game_gnp(igraph_t * graph,igraph_integer_t n,igraph_real_t p,igraph_bool_t directed,igraph_bool_t loops)38 int igraph_erdos_renyi_game_gnp(
39 igraph_t *graph, igraph_integer_t n, igraph_real_t p,
40 igraph_bool_t directed, igraph_bool_t loops
41 ) {
42
43 long int no_of_nodes = n;
44 igraph_vector_t edges = IGRAPH_VECTOR_NULL;
45 igraph_vector_t s = IGRAPH_VECTOR_NULL;
46 int retval = 0;
47 long int vsize;
48
49 if (n < 0) {
50 IGRAPH_ERROR("Invalid number of vertices", IGRAPH_EINVAL);
51 }
52 if (p < 0.0 || p > 1.0) {
53 IGRAPH_ERROR("Invalid probability given", IGRAPH_EINVAL);
54 }
55
56 if (p == 0.0 || no_of_nodes <= 1) {
57 IGRAPH_CHECK(retval = igraph_empty(graph, n, directed));
58 } else if (p == 1.0) {
59 IGRAPH_CHECK(retval = igraph_full(graph, n, directed, loops));
60 } else {
61
62 long int i;
63 double maxedges = n, last;
64 if (directed && loops) {
65 maxedges *= n;
66 } else if (directed && !loops) {
67 maxedges *= (n - 1);
68 } else if (!directed && loops) {
69 maxedges *= (n + 1) / 2.0;
70 } else {
71 maxedges *= (n - 1) / 2.0;
72 }
73
74 IGRAPH_VECTOR_INIT_FINALLY(&s, 0);
75 IGRAPH_CHECK(igraph_vector_reserve(&s, (long int) (maxedges * p * 1.1)));
76
77 RNG_BEGIN();
78
79 last = RNG_GEOM(p);
80 while (last < maxedges) {
81 IGRAPH_CHECK(igraph_vector_push_back(&s, last));
82 last += RNG_GEOM(p);
83 last += 1;
84 }
85
86 RNG_END();
87
88 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
89 IGRAPH_CHECK(igraph_vector_reserve(&edges, igraph_vector_size(&s) * 2));
90
91 vsize = igraph_vector_size(&s);
92 if (directed && loops) {
93 for (i = 0; i < vsize; i++) {
94 long int to = (long int) floor(VECTOR(s)[i] / no_of_nodes);
95 long int from = (long int) (VECTOR(s)[i] - ((igraph_real_t)to) * no_of_nodes);
96 igraph_vector_push_back(&edges, from);
97 igraph_vector_push_back(&edges, to);
98 }
99 } else if (directed && !loops) {
100 for (i = 0; i < vsize; i++) {
101 long int to = (long int) floor(VECTOR(s)[i] / no_of_nodes);
102 long int from = (long int) (VECTOR(s)[i] - ((igraph_real_t)to) * no_of_nodes);
103 if (from == to) {
104 to = no_of_nodes - 1;
105 }
106 igraph_vector_push_back(&edges, from);
107 igraph_vector_push_back(&edges, to);
108 }
109 } else if (!directed && loops) {
110 for (i = 0; i < vsize; i++) {
111 long int to = (long int) floor((sqrt(8 * VECTOR(s)[i] + 1) - 1) / 2);
112 long int from = (long int) (VECTOR(s)[i] - (((igraph_real_t)to) * (to + 1)) / 2);
113 igraph_vector_push_back(&edges, from);
114 igraph_vector_push_back(&edges, to);
115 }
116 } else { /* !directed && !loops */
117 for (i = 0; i < vsize; i++) {
118 long int to = (long int) floor((sqrt(8 * VECTOR(s)[i] + 1) + 1) / 2);
119 long int from = (long int) (VECTOR(s)[i] - (((igraph_real_t)to) * (to - 1)) / 2);
120 igraph_vector_push_back(&edges, from);
121 igraph_vector_push_back(&edges, to);
122 }
123 }
124
125 igraph_vector_destroy(&s);
126 IGRAPH_FINALLY_CLEAN(1);
127 IGRAPH_CHECK(retval = igraph_create(graph, &edges, n, directed));
128 igraph_vector_destroy(&edges);
129 IGRAPH_FINALLY_CLEAN(1);
130 }
131
132 return retval;
133 }
134
igraph_erdos_renyi_game_gnm(igraph_t * graph,igraph_integer_t n,igraph_real_t m,igraph_bool_t directed,igraph_bool_t loops)135 int igraph_erdos_renyi_game_gnm(
136 igraph_t *graph, igraph_integer_t n, igraph_real_t m,
137 igraph_bool_t directed, igraph_bool_t loops
138 ) {
139
140 igraph_integer_t no_of_nodes = n;
141 igraph_integer_t no_of_edges = (igraph_integer_t) m;
142 igraph_vector_t edges = IGRAPH_VECTOR_NULL;
143 igraph_vector_t s = IGRAPH_VECTOR_NULL;
144 int retval = 0;
145
146 if (n < 0) {
147 IGRAPH_ERROR("Invalid number of vertices", IGRAPH_EINVAL);
148 }
149 if (m < 0) {
150 IGRAPH_ERROR("Invalid number of edges", IGRAPH_EINVAL);
151 }
152
153 if (m == 0.0 || no_of_nodes <= 1) {
154 IGRAPH_CHECK(retval = igraph_empty(graph, n, directed));
155 } else {
156
157 long int i;
158 double maxedges = n;
159 if (directed && loops) {
160 maxedges *= n;
161 } else if (directed && !loops) {
162 maxedges *= (n - 1);
163 } else if (!directed && loops) {
164 maxedges *= (n + 1) / 2.0;
165 } else {
166 maxedges *= (n - 1) / 2.0;
167 }
168
169 if (no_of_edges > maxedges) {
170 IGRAPH_ERROR("Invalid number (too large) of edges", IGRAPH_EINVAL);
171 }
172
173 if (maxedges == no_of_edges) {
174 retval = igraph_full(graph, n, directed, loops);
175 } else {
176
177 long int slen;
178
179 IGRAPH_VECTOR_INIT_FINALLY(&s, 0);
180 IGRAPH_CHECK(igraph_random_sample(&s, 0, maxedges - 1,
181 (igraph_integer_t) no_of_edges));
182
183 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
184 IGRAPH_CHECK(igraph_vector_reserve(&edges, igraph_vector_size(&s) * 2));
185
186 slen = igraph_vector_size(&s);
187 if (directed && loops) {
188 for (i = 0; i < slen; i++) {
189 long int to = (long int) floor(VECTOR(s)[i] / no_of_nodes);
190 long int from = (long int) (VECTOR(s)[i] - ((igraph_real_t)to) * no_of_nodes);
191 igraph_vector_push_back(&edges, from);
192 igraph_vector_push_back(&edges, to);
193 }
194 } else if (directed && !loops) {
195 for (i = 0; i < slen; i++) {
196 long int from = (long int) floor(VECTOR(s)[i] / (no_of_nodes - 1));
197 long int to = (long int) (VECTOR(s)[i] - ((igraph_real_t)from) * (no_of_nodes - 1));
198 if (from == to) {
199 to = no_of_nodes - 1;
200 }
201 igraph_vector_push_back(&edges, from);
202 igraph_vector_push_back(&edges, to);
203 }
204 } else if (!directed && loops) {
205 for (i = 0; i < slen; i++) {
206 long int to = (long int) floor((sqrt(8 * VECTOR(s)[i] + 1) - 1) / 2);
207 long int from = (long int) (VECTOR(s)[i] - (((igraph_real_t)to) * (to + 1)) / 2);
208 igraph_vector_push_back(&edges, from);
209 igraph_vector_push_back(&edges, to);
210 }
211 } else { /* !directed && !loops */
212 for (i = 0; i < slen; i++) {
213 long int to = (long int) floor((sqrt(8 * VECTOR(s)[i] + 1) + 1) / 2);
214 long int from = (long int) (VECTOR(s)[i] - (((igraph_real_t)to) * (to - 1)) / 2);
215 igraph_vector_push_back(&edges, from);
216 igraph_vector_push_back(&edges, to);
217 }
218 }
219
220 igraph_vector_destroy(&s);
221 IGRAPH_FINALLY_CLEAN(1);
222 retval = igraph_create(graph, &edges, n, directed);
223 igraph_vector_destroy(&edges);
224 IGRAPH_FINALLY_CLEAN(1);
225 }
226 }
227
228 return retval;
229 }
230
231 /**
232 * \ingroup generators
233 * \function igraph_erdos_renyi_game
234 * \brief Generates a random (Erdős-Rényi) graph.
235 *
236 * \param graph Pointer to an uninitialized graph object.
237 * \param type The type of the random graph, possible values:
238 * \clist
239 * \cli IGRAPH_ERDOS_RENYI_GNM
240 * G(n,m) graph,
241 * m edges are
242 * selected uniformly randomly in a graph with
243 * n vertices.
244 * \cli IGRAPH_ERDOS_RENYI_GNP
245 * G(n,p) graph,
246 * every possible edge is included in the graph with
247 * probability p.
248 * \endclist
249 * \param n The number of vertices in the graph.
250 * \param p_or_m This is the p parameter for
251 * G(n,p) graphs and the
252 * m
253 * parameter for G(n,m) graphs.
254 * \param directed Logical, whether to generate a directed graph.
255 * \param loops Logical, whether to generate loops (self) edges.
256 * \return Error code:
257 * \c IGRAPH_EINVAL: invalid
258 * \p type, \p n,
259 * \p p or \p m
260 * parameter.
261 * \c IGRAPH_ENOMEM: there is not enough
262 * memory for the operation.
263 *
264 * Time complexity: O(|V|+|E|), the
265 * number of vertices plus the number of edges in the graph.
266 *
267 * \sa \ref igraph_barabasi_game(), \ref igraph_growing_random_game()
268 *
269 * \example examples/simple/igraph_erdos_renyi_game.c
270 */
igraph_erdos_renyi_game(igraph_t * graph,igraph_erdos_renyi_t type,igraph_integer_t n,igraph_real_t p_or_m,igraph_bool_t directed,igraph_bool_t loops)271 int igraph_erdos_renyi_game(igraph_t *graph, igraph_erdos_renyi_t type,
272 igraph_integer_t n, igraph_real_t p_or_m,
273 igraph_bool_t directed, igraph_bool_t loops) {
274 int retval = 0;
275
276 if (type == IGRAPH_ERDOS_RENYI_GNP) {
277 retval = igraph_erdos_renyi_game_gnp(graph, n, p_or_m, directed, loops);
278 } else if (type == IGRAPH_ERDOS_RENYI_GNM) {
279 retval = igraph_erdos_renyi_game_gnm(graph, n, p_or_m, directed, loops);
280 } else {
281 IGRAPH_ERROR("Invalid type", IGRAPH_EINVAL);
282 }
283
284 return retval;
285 }
286