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