1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2005-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
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_conversion.h"
25
26 #include "igraph_iterators.h"
27 #include "igraph_interface.h"
28 #include "igraph_attributes.h"
29 #include "igraph_constructors.h"
30 #include "igraph_structural.h"
31 #include "igraph_sparsemat.h"
32 #include "igraph_random.h"
33
34 #include "core/fixed_vectorlist.h"
35 #include "graph/attributes.h"
36 #include "misc/conversion_internal.h"
37
38 /**
39 * \ingroup conversion
40 * \function igraph_get_adjacency
41 * \brief Returns the adjacency matrix of a graph
42 *
43 * </para><para>
44 * The result is an adjacency matrix. Entry i, j of the matrix
45 * contains the number of edges connecting vertex i to vertex j.
46 * \param graph Pointer to the graph to convert
47 * \param res Pointer to an initialized matrix object, it will be
48 * resized if needed.
49 * \param type Constant giving the type of the adjacency matrix to
50 * create for undirected graphs. It is ignored for directed
51 * graphs. Possible values:
52 * \clist
53 * \cli IGRAPH_GET_ADJACENCY_UPPER
54 * the upper right triangle of the matrix is used.
55 * \cli IGRAPH_GET_ADJACENCY_LOWER
56 * the lower left triangle of the matrix is used.
57 * \cli IGRAPH_GET_ADJACENCY_BOTH
58 * the whole matrix is used, a symmetric matrix is returned
59 * if the graph is undirected.
60 * \endclist
61 * \param type eids Logical, if true, then the edges ids plus one
62 * are stored in the adjacency matrix, instead of the number of
63 * edges between the two vertices. (The plus one is needed, since
64 * edge ids start from zero, and zero means no edge in this case.)
65 * \return Error code:
66 * \c IGRAPH_EINVAL invalid type argument.
67 *
68 * \sa igraph_get_adjacency_sparse if you want a sparse matrix representation
69 *
70 * Time complexity: O(|V||V|),
71 * |V| is the
72 * number of vertices in the graph.
73 */
74
igraph_get_adjacency(const igraph_t * graph,igraph_matrix_t * res,igraph_get_adjacency_t type,igraph_bool_t eids)75 int igraph_get_adjacency(const igraph_t *graph, igraph_matrix_t *res,
76 igraph_get_adjacency_t type, igraph_bool_t eids) {
77
78 igraph_eit_t edgeit;
79 long int no_of_nodes = igraph_vcount(graph);
80 igraph_bool_t directed = igraph_is_directed(graph);
81 int retval = 0;
82 long int from, to;
83 igraph_integer_t ffrom, fto;
84
85 IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, no_of_nodes));
86 igraph_matrix_null(res);
87 IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(0), &edgeit));
88 IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
89
90 if (directed) {
91 while (!IGRAPH_EIT_END(edgeit)) {
92 long int edge = IGRAPH_EIT_GET(edgeit);
93 igraph_edge(graph, (igraph_integer_t) edge, &ffrom, &fto);
94 from = ffrom;
95 to = fto;
96 if (eids) {
97 MATRIX(*res, from, to) = edge + 1;
98 } else {
99 MATRIX(*res, from, to) += 1;
100 }
101 IGRAPH_EIT_NEXT(edgeit);
102 }
103 } else if (type == IGRAPH_GET_ADJACENCY_UPPER) {
104 while (!IGRAPH_EIT_END(edgeit)) {
105 long int edge = IGRAPH_EIT_GET(edgeit);
106 igraph_edge(graph, (igraph_integer_t) edge, &ffrom, &fto);
107 from = ffrom;
108 to = fto;
109 if (to < from) {
110 if (eids) {
111 MATRIX(*res, to, from) = edge + 1;
112 } else {
113 MATRIX(*res, to, from) += 1;
114 }
115 } else {
116 if (eids) {
117 MATRIX(*res, from, to) = edge + 1;
118 } else {
119 MATRIX(*res, from, to) += 1;
120 }
121 }
122 IGRAPH_EIT_NEXT(edgeit);
123 }
124 } else if (type == IGRAPH_GET_ADJACENCY_LOWER) {
125 while (!IGRAPH_EIT_END(edgeit)) {
126 long int edge = IGRAPH_EIT_GET(edgeit);
127 igraph_edge(graph, (igraph_integer_t) edge, &ffrom, &fto);
128 from = ffrom;
129 to = fto;
130 if (to < from) {
131 if (eids) {
132 MATRIX(*res, from, to) = edge + 1;
133 } else {
134 MATRIX(*res, from, to) += 1;
135 }
136 } else {
137 if (eids) {
138 MATRIX(*res, to, from) = edge + 1;
139 } else {
140 MATRIX(*res, to, from) += 1;
141 }
142 }
143 IGRAPH_EIT_NEXT(edgeit);
144 }
145 } else if (type == IGRAPH_GET_ADJACENCY_BOTH) {
146 while (!IGRAPH_EIT_END(edgeit)) {
147 long int edge = IGRAPH_EIT_GET(edgeit);
148 igraph_edge(graph, (igraph_integer_t) edge, &ffrom, &fto);
149 from = ffrom;
150 to = fto;
151 if (eids) {
152 MATRIX(*res, from, to) = edge + 1;
153 } else {
154 MATRIX(*res, from, to) += 1;
155 }
156 if (from != to) {
157 if (eids) {
158 MATRIX(*res, to, from) = edge + 1;
159 } else {
160 MATRIX(*res, to, from) += 1;
161 }
162 }
163 IGRAPH_EIT_NEXT(edgeit);
164 }
165 } else {
166 IGRAPH_ERROR("Invalid type argument", IGRAPH_EINVAL);
167 }
168
169 igraph_eit_destroy(&edgeit);
170 IGRAPH_FINALLY_CLEAN(1);
171 return retval;
172 }
173
174 /**
175 * \ingroup conversion
176 * \function igraph_get_adjacency_sparse
177 * \brief Returns the adjacency matrix of a graph in sparse matrix format.
178 *
179 * </para><para>
180 * The result is an adjacency matrix. Entry i, j of the matrix
181 * contains the number of edges connecting vertex i to vertex j.
182 * \param graph Pointer to the graph to convert.
183 * \param res Pointer to an initialized sparse matrix object, it will be
184 * resized if needed.
185 * \param type Constant giving the type of the adjacency matrix to
186 * create for undirected graphs. It is ignored for directed
187 * graphs. Possible values:
188 * \clist
189 * \cli IGRAPH_GET_ADJACENCY_UPPER
190 * the upper right triangle of the matrix is used.
191 * \cli IGRAPH_GET_ADJACENCY_LOWER
192 * the lower left triangle of the matrix is used.
193 * \cli IGRAPH_GET_ADJACENCY_BOTH
194 * the whole matrix is used, a symmetric matrix is returned.
195 * \endclist
196 * \return Error code:
197 * \c IGRAPH_EINVAL invalid type argument.
198 *
199 * \sa igraph_get_adjacency if you would like to get a normal matrix
200 * ( \type igraph_matrix_t )
201 *
202 * Time complexity: O(|V||V|),
203 * |V| is the
204 * number of vertices in the graph.
205 */
206
igraph_get_adjacency_sparse(const igraph_t * graph,igraph_spmatrix_t * res,igraph_get_adjacency_t type)207 int igraph_get_adjacency_sparse(const igraph_t *graph, igraph_spmatrix_t *res,
208 igraph_get_adjacency_t type) {
209
210 igraph_eit_t edgeit;
211 long int no_of_nodes = igraph_vcount(graph);
212 igraph_bool_t directed = igraph_is_directed(graph);
213 long int from, to;
214 igraph_integer_t ffrom, fto;
215
216 igraph_spmatrix_null(res);
217 IGRAPH_CHECK(igraph_spmatrix_resize(res, no_of_nodes, no_of_nodes));
218 IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(0), &edgeit));
219 IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
220
221 if (directed) {
222 while (!IGRAPH_EIT_END(edgeit)) {
223 igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
224 from = ffrom;
225 to = fto;
226 igraph_spmatrix_add_e(res, from, to, 1);
227 IGRAPH_EIT_NEXT(edgeit);
228 }
229 } else if (type == IGRAPH_GET_ADJACENCY_UPPER) {
230 while (!IGRAPH_EIT_END(edgeit)) {
231 igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
232 from = ffrom;
233 to = fto;
234 if (to < from) {
235 igraph_spmatrix_add_e(res, to, from, 1);
236 } else {
237 igraph_spmatrix_add_e(res, from, to, 1);
238 }
239 IGRAPH_EIT_NEXT(edgeit);
240 }
241 } else if (type == IGRAPH_GET_ADJACENCY_LOWER) {
242 while (!IGRAPH_EIT_END(edgeit)) {
243 igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
244 from = ffrom;
245 to = fto;
246 if (to > from) {
247 igraph_spmatrix_add_e(res, to, from, 1);
248 } else {
249 igraph_spmatrix_add_e(res, from, to, 1);
250 }
251 IGRAPH_EIT_NEXT(edgeit);
252 }
253 } else if (type == IGRAPH_GET_ADJACENCY_BOTH) {
254 while (!IGRAPH_EIT_END(edgeit)) {
255 igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
256 from = ffrom;
257 to = fto;
258 igraph_spmatrix_add_e(res, from, to, 1);
259 if (from != to) {
260 igraph_spmatrix_add_e(res, to, from, 1);
261 }
262 IGRAPH_EIT_NEXT(edgeit);
263 }
264 } else {
265 IGRAPH_ERROR("Invalid type argument.", IGRAPH_EINVAL);
266 }
267
268 igraph_eit_destroy(&edgeit);
269 IGRAPH_FINALLY_CLEAN(1);
270 return IGRAPH_SUCCESS;
271 }
272
273 /**
274 * \ingroup conversion
275 * \function igraph_get_edgelist
276 * \brief Returns the list of edges in a graph
277 *
278 * </para><para>The order of the edges is given by the edge ids.
279 * \param graph Pointer to the graph object
280 * \param res Pointer to an initialized vector object, it will be
281 * resized.
282 * \param bycol Logical, if true, the edges will be returned
283 * columnwise, e.g. the first edge is
284 * <code>res[0]->res[|E|]</code>, the second is
285 * <code>res[1]->res[|E|+1]</code>, etc.
286 * \return Error code.
287 *
288 * \sa \ref igraph_edges() to return the result only for some edge ids.
289 *
290 * Time complexity: O(|E|), the
291 * number of edges in the graph.
292 */
293
igraph_get_edgelist(const igraph_t * graph,igraph_vector_t * res,igraph_bool_t bycol)294 int igraph_get_edgelist(const igraph_t *graph, igraph_vector_t *res, igraph_bool_t bycol) {
295
296 igraph_eit_t edgeit;
297 long int no_of_edges = igraph_ecount(graph);
298 long int vptr = 0;
299 igraph_integer_t from, to;
300
301 IGRAPH_CHECK(igraph_vector_resize(res, no_of_edges * 2));
302 IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_ID),
303 &edgeit));
304 IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
305
306 if (bycol) {
307 while (!IGRAPH_EIT_END(edgeit)) {
308 igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &from, &to);
309 VECTOR(*res)[vptr] = from;
310 VECTOR(*res)[vptr + no_of_edges] = to;
311 vptr++;
312 IGRAPH_EIT_NEXT(edgeit);
313 }
314 } else {
315 while (!IGRAPH_EIT_END(edgeit)) {
316 igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &from, &to);
317 VECTOR(*res)[vptr++] = from;
318 VECTOR(*res)[vptr++] = to;
319 IGRAPH_EIT_NEXT(edgeit);
320 }
321 }
322
323 igraph_eit_destroy(&edgeit);
324 IGRAPH_FINALLY_CLEAN(1);
325 return 0;
326 }
327
328 /**
329 * \function igraph_to_directed
330 * \brief Convert an undirected graph to a directed one
331 *
332 * </para><para>
333 * If the supplied graph is directed, this function does nothing.
334 * \param graph The graph object to convert.
335 * \param mode Constant, specifies the details of how exactly the
336 * conversion is done. Possible values:
337 * \clist
338 * \cli IGRAPH_TO_DIRECTED_ARBITRARY
339 * The number of edges in the
340 * graph stays the same, an arbitrarily directed edge is
341 * created for each undirected edge.
342 * \cli IGRAPH_TO_DIRECTED_MUTUAL
343 * Two directed edges are
344 * created for each undirected edge, one in each direction.
345 * \cli IGRAPH_TO_DIRECTED_RANDOM
346 * Each undirected edge is converted to a randomly oriented
347 * directed one.
348 * \cli IGRAPH_TO_DIRECTED_ACYCLIC
349 * Each undirected edge is converted to a directed edge oriented
350 * from a lower index vertex to a higher index one. If no self-loops
351 * were present, then the result is a directed acyclic graph.
352 * \endclist
353 * \return Error code.
354 *
355 * Time complexity: O(|V|+|E|), the number of vertices plus the number
356 * of edges.
357 */
358
igraph_to_directed(igraph_t * graph,igraph_to_directed_t mode)359 int igraph_to_directed(igraph_t *graph,
360 igraph_to_directed_t mode) {
361 long int no_of_edges = igraph_ecount(graph);
362 long int no_of_nodes = igraph_vcount(graph);
363
364 if (igraph_is_directed(graph)) {
365 return IGRAPH_SUCCESS;
366 }
367
368 switch (mode) {
369 case IGRAPH_TO_DIRECTED_ARBITRARY:
370 case IGRAPH_TO_DIRECTED_RANDOM:
371 case IGRAPH_TO_DIRECTED_ACYCLIC:
372 {
373 igraph_t newgraph;
374 igraph_vector_t edges;
375 long int size = no_of_edges * 2;
376 long int i;
377
378 IGRAPH_VECTOR_INIT_FINALLY(&edges, size);
379 IGRAPH_CHECK(igraph_get_edgelist(graph, &edges, 0));
380
381 if (mode == IGRAPH_TO_DIRECTED_RANDOM) {
382 RNG_BEGIN();
383
384 for (i=0; i < no_of_edges; ++i) {
385 if (RNG_INTEGER(0,1)) {
386 igraph_real_t temp = VECTOR(edges)[2*i];
387 VECTOR(edges)[2*i] = VECTOR(edges)[2*i+1];
388 VECTOR(edges)[2*i+1] = temp;
389 }
390 }
391
392 RNG_END();
393 } else if (mode == IGRAPH_TO_DIRECTED_ACYCLIC) {
394 /* Currently, the endpoints of undirected edges are ordered in the
395 internal graph datastructure, i.e. it is always true that from < to.
396 However, it is not guaranteed that this will not be changed in
397 the future, and this ordering should not be relied on outside of
398 the implementation of the minimal API in type_indexededgelist.c.
399
400 Therefore, we order the edge endpoints anyway in the following loop: */
401 for (i=0; i < no_of_edges; ++i) {
402 if (VECTOR(edges)[2*i] > VECTOR(edges)[2*i+1]) {
403 igraph_real_t temp = VECTOR(edges)[2*i];
404 VECTOR(edges)[2*i] = VECTOR(edges)[2*i+1];
405 VECTOR(edges)[2*i+1] = temp;
406 }
407 }
408 }
409
410 IGRAPH_CHECK(igraph_create(&newgraph, &edges,
411 (igraph_integer_t) no_of_nodes,
412 IGRAPH_DIRECTED));
413 IGRAPH_FINALLY(igraph_destroy, &newgraph);
414 IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
415 IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1, 1, 1);
416 igraph_vector_destroy(&edges);
417 IGRAPH_FINALLY_CLEAN(2);
418
419 igraph_destroy(graph);
420 *graph = newgraph;
421
422 break;
423 }
424 case IGRAPH_TO_DIRECTED_MUTUAL:
425 {
426 igraph_t newgraph;
427 igraph_vector_t edges;
428 igraph_vector_t index;
429 long int size = no_of_edges * 4;
430 long int i;
431 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
432 IGRAPH_CHECK(igraph_vector_reserve(&edges, size));
433 IGRAPH_CHECK(igraph_get_edgelist(graph, &edges, 0));
434 IGRAPH_CHECK(igraph_vector_resize(&edges, no_of_edges * 4));
435 IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_edges * 2);
436 for (i = 0; i < no_of_edges; i++) {
437 VECTOR(edges)[no_of_edges * 2 + i * 2] = VECTOR(edges)[i * 2 + 1];
438 VECTOR(edges)[no_of_edges * 2 + i * 2 + 1] = VECTOR(edges)[i * 2];
439 VECTOR(index)[i] = VECTOR(index)[no_of_edges + i] = i;
440 }
441
442 IGRAPH_CHECK(igraph_create(&newgraph, &edges,
443 (igraph_integer_t) no_of_nodes,
444 IGRAPH_DIRECTED));
445 IGRAPH_FINALLY(igraph_destroy, &newgraph);
446 IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
447 IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1, 1,/*edges=*/0);
448 IGRAPH_CHECK(igraph_i_attribute_permute_edges(graph, &newgraph, &index));
449
450 igraph_vector_destroy(&index);
451 igraph_vector_destroy(&edges);
452 IGRAPH_FINALLY_CLEAN(3);
453
454 igraph_destroy(graph);
455 *graph = newgraph;
456
457 break;
458 }
459 default:
460 IGRAPH_ERROR("Cannot direct graph, invalid mode", IGRAPH_EINVAL);
461 }
462
463 return IGRAPH_SUCCESS;
464 }
465
466 /**
467 * \function igraph_to_undirected
468 * \brief Convert a directed graph to an undirected one.
469 *
470 * </para><para>
471 * If the supplied graph is undirected, this function does nothing.
472 *
473 * \param graph The graph object to convert.
474 * \param mode Constant, specifies the details of how exactly the
475 * conversion is done. Possible values: \c
476 * IGRAPH_TO_UNDIRECTED_EACH: the number of edges remains
477 * constant, an undirected edge is created for each directed
478 * one, this version might create graphs with multiple edges;
479 * \c IGRAPH_TO_UNDIRECTED_COLLAPSE: one undirected edge will
480 * be created for each pair of vertices that are connected
481 * with at least one directed edge, no multiple edges will be
482 * created. \c IGRAPH_TO_UNDIRECTED_MUTUAL creates an undirected
483 * edge for each pair of mutual edges in the directed graph.
484 * Non-mutual edges are lost; loop edges are kept unconditionally.
485 * This mode might create multiple edges.
486 * \param edge_comb What to do with the edge attributes. See the igraph
487 * manual section about attributes for details. \c NULL means that
488 * the edge attributes are lost during the conversion, \em except
489 * when \c mode is \c IGRAPH_TO_UNDIRECTED_EACH, in which case the
490 * edge attributes are kept intact.
491 * \return Error code.
492 *
493 * Time complexity: O(|V|+|E|), the number of vertices plus the number
494 * of edges.
495 *
496 * \example examples/simple/igraph_to_undirected.c
497 */
498
igraph_to_undirected(igraph_t * graph,igraph_to_undirected_t mode,const igraph_attribute_combination_t * edge_comb)499 int igraph_to_undirected(igraph_t *graph,
500 igraph_to_undirected_t mode,
501 const igraph_attribute_combination_t *edge_comb) {
502
503 long int no_of_nodes = igraph_vcount(graph);
504 long int no_of_edges = igraph_ecount(graph);
505 igraph_vector_t edges;
506 igraph_t newgraph;
507 igraph_bool_t attr = edge_comb && igraph_has_attribute_table();
508
509 if (mode != IGRAPH_TO_UNDIRECTED_EACH &&
510 mode != IGRAPH_TO_UNDIRECTED_COLLAPSE &&
511 mode != IGRAPH_TO_UNDIRECTED_MUTUAL) {
512 IGRAPH_ERROR("Cannot undirect graph, invalid mode", IGRAPH_EINVAL);
513 }
514
515 if (!igraph_is_directed(graph)) {
516 return 0;
517 }
518
519 IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
520
521 if (mode == IGRAPH_TO_UNDIRECTED_EACH) {
522 igraph_es_t es;
523 igraph_eit_t eit;
524
525 IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
526 IGRAPH_CHECK(igraph_es_all(&es, IGRAPH_EDGEORDER_ID));
527 IGRAPH_FINALLY(igraph_es_destroy, &es);
528 IGRAPH_CHECK(igraph_eit_create(graph, es, &eit));
529 IGRAPH_FINALLY(igraph_eit_destroy, &eit);
530
531 while (!IGRAPH_EIT_END(eit)) {
532 long int edge = IGRAPH_EIT_GET(eit);
533 igraph_integer_t from, to;
534 igraph_edge(graph, (igraph_integer_t) edge, &from, &to);
535 IGRAPH_CHECK(igraph_vector_push_back(&edges, from));
536 IGRAPH_CHECK(igraph_vector_push_back(&edges, to));
537 IGRAPH_EIT_NEXT(eit);
538 }
539
540 igraph_eit_destroy(&eit);
541 igraph_es_destroy(&es);
542 IGRAPH_FINALLY_CLEAN(2);
543
544 IGRAPH_CHECK(igraph_create(&newgraph, &edges,
545 (igraph_integer_t) no_of_nodes,
546 IGRAPH_UNDIRECTED));
547 IGRAPH_FINALLY(igraph_destroy, &newgraph);
548 igraph_vector_destroy(&edges);
549 IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
550 IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1, 1, 1);
551 IGRAPH_FINALLY_CLEAN(2);
552 igraph_destroy(graph);
553 *graph = newgraph;
554
555 } else if (mode == IGRAPH_TO_UNDIRECTED_COLLAPSE) {
556 igraph_vector_t inadj, outadj;
557 long int i;
558 igraph_vector_t mergeinto;
559 long int actedge = 0;
560
561 if (attr) {
562 IGRAPH_VECTOR_INIT_FINALLY(&mergeinto, no_of_edges);
563 }
564
565 IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
566 IGRAPH_VECTOR_INIT_FINALLY(&inadj, 0);
567 IGRAPH_VECTOR_INIT_FINALLY(&outadj, 0);
568
569 for (i = 0; i < no_of_nodes; i++) {
570 long int n_out, n_in;
571 long int p1 = -1, p2 = -1;
572 long int e1 = 0, e2 = 0, n1 = 0, n2 = 0, last;
573 IGRAPH_CHECK(igraph_incident(graph, &outadj, (igraph_integer_t) i,
574 IGRAPH_OUT));
575 IGRAPH_CHECK(igraph_incident(graph, &inadj, (igraph_integer_t) i,
576 IGRAPH_IN));
577 n_out = igraph_vector_size(&outadj);
578 n_in = igraph_vector_size(&inadj);
579
580 #define STEPOUT() if ( (++p1) < n_out) { \
581 e1 = (long int) VECTOR(outadj)[p1]; \
582 n1 = IGRAPH_TO(graph, e1); \
583 }
584 #define STEPIN() if ( (++p2) < n_in) { \
585 e2 = (long int) VECTOR(inadj )[p2]; \
586 n2 = IGRAPH_FROM(graph, e2); \
587 }
588 #define ADD_NEW_EDGE() { \
589 IGRAPH_CHECK(igraph_vector_push_back(&edges, i)); \
590 IGRAPH_CHECK(igraph_vector_push_back(&edges, last)); \
591 }
592 #define MERGE_INTO_CURRENT_EDGE(which) { \
593 if (attr) { \
594 VECTOR(mergeinto)[which] = actedge; \
595 } \
596 }
597
598 STEPOUT();
599 STEPIN();
600
601 while (p1 < n_out && n1 <= i && p2 < n_in && n2 <= i) {
602 last = (n1 <= n2) ? n1 : n2;
603 ADD_NEW_EDGE();
604 while (p1 < n_out && last == n1) {
605 MERGE_INTO_CURRENT_EDGE(e1);
606 STEPOUT();
607 }
608 while (p2 < n_in && last == n2) {
609 MERGE_INTO_CURRENT_EDGE(e2);
610 STEPIN();
611 }
612 actedge++;
613 }
614
615 while (p1 < n_out && n1 <= i) {
616 last = n1;
617 ADD_NEW_EDGE();
618 while (p1 < n_out && last == n1) {
619 MERGE_INTO_CURRENT_EDGE(e1);
620 STEPOUT();
621 }
622 actedge++;
623 }
624
625 while (p2 < n_in && n2 <= i) {
626 last = n2;
627 ADD_NEW_EDGE();
628 while (p2 < n_in && last == n2) {
629 MERGE_INTO_CURRENT_EDGE(e2);
630 STEPIN();
631 }
632 actedge++;
633 }
634 }
635
636 #undef MERGE_INTO_CURRENT_EDGE
637 #undef ADD_NEW_EDGE
638 #undef STEPOUT
639 #undef STEPIN
640
641 igraph_vector_destroy(&outadj);
642 igraph_vector_destroy(&inadj);
643 IGRAPH_FINALLY_CLEAN(2);
644
645 IGRAPH_CHECK(igraph_create(&newgraph, &edges,
646 (igraph_integer_t) no_of_nodes,
647 IGRAPH_UNDIRECTED));
648 IGRAPH_FINALLY(igraph_destroy, &newgraph);
649 igraph_vector_destroy(&edges);
650 IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
651 IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1, 1, 0); /* no edge attributes */
652
653 if (attr) {
654 igraph_fixed_vectorlist_t vl;
655 IGRAPH_CHECK(igraph_fixed_vectorlist_convert(&vl, &mergeinto,
656 actedge));
657 IGRAPH_FINALLY(igraph_fixed_vectorlist_destroy, &vl);
658
659 IGRAPH_CHECK(igraph_i_attribute_combine_edges(graph, &newgraph, &vl.v,
660 edge_comb));
661
662 igraph_fixed_vectorlist_destroy(&vl);
663 IGRAPH_FINALLY_CLEAN(1);
664 }
665
666 IGRAPH_FINALLY_CLEAN(2);
667 igraph_destroy(graph);
668 *graph = newgraph;
669
670 if (attr) {
671 igraph_vector_destroy(&mergeinto);
672 IGRAPH_FINALLY_CLEAN(1);
673 }
674 } else if (mode == IGRAPH_TO_UNDIRECTED_MUTUAL) {
675 igraph_vector_t inadj, outadj;
676 long int i;
677 igraph_vector_t mergeinto;
678 long int actedge = 0;
679
680 if (attr) {
681 IGRAPH_VECTOR_INIT_FINALLY(&mergeinto, no_of_edges);
682 igraph_vector_fill(&mergeinto, -1);
683 }
684
685 IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges * 2));
686 IGRAPH_VECTOR_INIT_FINALLY(&inadj, 0);
687 IGRAPH_VECTOR_INIT_FINALLY(&outadj, 0);
688
689 for (i = 0; i < no_of_nodes; i++) {
690 long int n_out, n_in;
691 long int p1 = -1, p2 = -1;
692 long int e1 = 0, e2 = 0, n1 = 0, n2 = 0;
693 IGRAPH_CHECK(igraph_incident(graph, &outadj, (igraph_integer_t) i,
694 IGRAPH_OUT));
695 IGRAPH_CHECK(igraph_incident(graph, &inadj, (igraph_integer_t) i,
696 IGRAPH_IN));
697 n_out = igraph_vector_size(&outadj);
698 n_in = igraph_vector_size(&inadj);
699
700 #define STEPOUT() if ( (++p1) < n_out) { \
701 e1 = (long int) VECTOR(outadj)[p1]; \
702 n1 = IGRAPH_TO(graph, e1); \
703 }
704 #define STEPIN() if ( (++p2) < n_in) { \
705 e2 = (long int) VECTOR(inadj )[p2]; \
706 n2 = IGRAPH_FROM(graph, e2); \
707 }
708
709 STEPOUT();
710 STEPIN();
711
712 while (p1 < n_out && n1 <= i && p2 < n_in && n2 <= i) {
713 if (n1 == n2) {
714 IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
715 IGRAPH_CHECK(igraph_vector_push_back(&edges, n1));
716 if (attr) {
717 VECTOR(mergeinto)[e1] = actedge;
718 VECTOR(mergeinto)[e2] = actedge;
719 actedge++;
720 }
721 STEPOUT();
722 STEPIN();
723 } else if (n1 < n2) {
724 STEPOUT();
725 } else { /* n2<n1 */
726 STEPIN();
727 }
728 }
729 }
730
731 #undef STEPOUT
732 #undef STEPIN
733
734 igraph_vector_destroy(&outadj);
735 igraph_vector_destroy(&inadj);
736 IGRAPH_FINALLY_CLEAN(2);
737
738 IGRAPH_CHECK(igraph_create(&newgraph, &edges,
739 (igraph_integer_t) no_of_nodes,
740 IGRAPH_UNDIRECTED));
741 IGRAPH_FINALLY(igraph_destroy, &newgraph);
742 igraph_vector_destroy(&edges);
743 IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
744 IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1, 1, 0); /* no edge attributes */
745
746 if (attr) {
747 igraph_fixed_vectorlist_t vl;
748 IGRAPH_CHECK(igraph_fixed_vectorlist_convert(&vl, &mergeinto,
749 actedge));
750 IGRAPH_FINALLY(igraph_fixed_vectorlist_destroy, &vl);
751
752 IGRAPH_CHECK(igraph_i_attribute_combine_edges(graph, &newgraph, &vl.v,
753 edge_comb));
754
755 igraph_fixed_vectorlist_destroy(&vl);
756 IGRAPH_FINALLY_CLEAN(1);
757 }
758
759 IGRAPH_FINALLY_CLEAN(2);
760 igraph_destroy(graph);
761 *graph = newgraph;
762
763 if (attr) {
764 igraph_vector_destroy(&mergeinto);
765 IGRAPH_FINALLY_CLEAN(1);
766 }
767 }
768
769 return 0;
770 }
771
772 /**
773 * \function igraph_get_stochastic
774 * Stochastic adjacency matrix of a graph
775 *
776 * Stochastic matrix of a graph. The stochastic matrix of a graph is
777 * its adjacency matrix, normalized row-wise or column-wise, such that
778 * the sum of each row (or column) is one.
779 * \param graph The input graph.
780 * \param sparsemat Pointer to an initialized matrix, the
781 * result is stored here.
782 * \param column_wise Whether to normalize column-wise. For undirected
783 * graphs this argument does not have any effect.
784 * \return Error code.
785 *
786 * Time complexity: O(|V||V|), quadratic in the number of vertices.
787 *
788 * \sa igraph_get_stochastic_sparsemat(), the sparse version of this
789 * function.
790 */
791
igraph_get_stochastic(const igraph_t * graph,igraph_matrix_t * matrix,igraph_bool_t column_wise)792 int igraph_get_stochastic(const igraph_t *graph,
793 igraph_matrix_t *matrix,
794 igraph_bool_t column_wise) {
795
796 int no_of_nodes = igraph_vcount(graph);
797 igraph_real_t sum;
798 int i, j;
799
800 IGRAPH_CHECK(igraph_get_adjacency(graph, matrix,
801 IGRAPH_GET_ADJACENCY_BOTH, /*eids=*/ 0));
802
803 if (!column_wise) {
804 for (i = 0; i < no_of_nodes; i++) {
805 sum = 0.0;
806 for (j = 0; j < no_of_nodes; j++) {
807 sum += MATRIX(*matrix, i, j);
808 }
809 for (j = 0; j < no_of_nodes; j++) {
810 MATRIX(*matrix, i, j) /= sum;
811 }
812 }
813 } else {
814 for (i = 0; i < no_of_nodes; i++) {
815 sum = 0.0;
816 for (j = 0; j < no_of_nodes; j++) {
817 sum += MATRIX(*matrix, j, i);
818 }
819 for (j = 0; j < no_of_nodes; j++) {
820 MATRIX(*matrix, j, i) /= sum;
821 }
822 }
823 }
824
825 return 0;
826 }
827
828
igraph_i_normalize_sparsemat(igraph_sparsemat_t * sparsemat,igraph_bool_t column_wise)829 int igraph_i_normalize_sparsemat(igraph_sparsemat_t *sparsemat,
830 igraph_bool_t column_wise) {
831 igraph_vector_t sum;
832 int no_of_nodes = (int) igraph_sparsemat_nrow(sparsemat);
833 int i;
834
835 IGRAPH_VECTOR_INIT_FINALLY(&sum, no_of_nodes);
836
837 if (!column_wise) {
838 IGRAPH_CHECK(igraph_sparsemat_rowsums(sparsemat, &sum));
839 for (i = 0; i < no_of_nodes; i++) {
840 if (VECTOR(sum)[i] == 0.0) {
841 IGRAPH_ERROR("Zero out-degree vertices not allowed",
842 IGRAPH_EINVAL);
843 }
844 VECTOR(sum)[i] = 1.0 / VECTOR(sum)[i];
845 }
846 IGRAPH_CHECK(igraph_sparsemat_scale_rows(sparsemat, &sum));
847 } else {
848 IGRAPH_CHECK(igraph_sparsemat_colsums(sparsemat, &sum));
849 for (i = 0; i < no_of_nodes; i++) {
850 if (VECTOR(sum)[i] == 0.0) {
851 IGRAPH_ERROR("Zero out-degree vertices not allowed",
852 IGRAPH_EINVAL);
853 }
854 VECTOR(sum)[i] = 1.0 / VECTOR(sum)[i];
855 }
856 IGRAPH_CHECK(igraph_sparsemat_scale_cols(sparsemat, &sum));
857 }
858
859 igraph_vector_destroy(&sum);
860 IGRAPH_FINALLY_CLEAN(1);
861
862 return 0;
863 }
864
865 /**
866 * \function igraph_get_stochastic_sparsemat
867 * \brief Stochastic adjacency matrix of a graph
868 *
869 * Stochastic matrix of a graph. The stochastic matrix of a graph is
870 * its adjacency matrix, normalized row-wise or column-wise, such that
871 * the sum of each row (or column) is one.
872 * \param graph The input graph.
873 * \param sparsemat Pointer to an uninitialized sparse matrix, the
874 * result is stored here.
875 * \param column_wise Whether to normalize column-wise. For undirected
876 * graphs this argument does not have any effect.
877 * \return Error code.
878 *
879 * Time complexity: O(|V|+|E|), linear in the number of vertices and
880 * edges.
881 *
882 * \sa igraph_get_stochastic(), the dense version of this function.
883 */
884
igraph_get_stochastic_sparsemat(const igraph_t * graph,igraph_sparsemat_t * sparsemat,igraph_bool_t column_wise)885 int igraph_get_stochastic_sparsemat(const igraph_t *graph,
886 igraph_sparsemat_t *sparsemat,
887 igraph_bool_t column_wise) {
888
889 IGRAPH_CHECK(igraph_get_sparsemat(graph, sparsemat));
890 IGRAPH_FINALLY(igraph_sparsemat_destroy, sparsemat);
891 IGRAPH_CHECK(igraph_i_normalize_sparsemat(sparsemat, column_wise));
892 IGRAPH_FINALLY_CLEAN(1);
893
894 return 0;
895 }
896
897
898 /**
899 * \ingroup conversion
900 * \function igraph_to_prufer
901 * \brief Converts a tree to its Prüfer sequence
902 *
903 * A Prüfer sequence is a unique sequence of integers associated
904 * with a labelled tree. A tree on n >= 2 vertices can be represented by a
905 * sequence of n-2 integers, each between 0 and n-1 (inclusive).
906 *
907 * \param graph Pointer to an initialized graph object which
908 must be a tree on n >= 2 vertices.
909 * \param prufer A pointer to the integer vector that should hold the Prüfer sequence;
910 the vector must be initialized and will be resized to n - 2.
911 * \return Error code:
912 * \clist
913 * \cli IGRAPH_ENOMEM
914 * there is not enough memory to perform the operation.
915 * \cli IGRAPH_EINVAL
916 * the graph is not a tree or it is has less than vertices
917 * \endclist
918 *
919 * \sa \ref igraph_from_prufer()
920 *
921 */
igraph_to_prufer(const igraph_t * graph,igraph_vector_int_t * prufer)922 int igraph_to_prufer(const igraph_t *graph, igraph_vector_int_t* prufer) {
923 /* For generating the Prüfer sequence, we enumerate the vertices u of the tree.
924 We keep track of the degrees of all vertices, treating vertices
925 of degree 0 as removed. We maintain the invariant that all leafs
926 that are still contained in the tree are >= u.
927 If u is a leaf, we remove it and add its unique neighbor to the prüfer
928 sequence. If the removal of u turns the neighbor into a leaf which is < u,
929 we repeat the procedure for the new leaf and so on. */
930 igraph_integer_t u;
931 igraph_vector_t degrees, neighbors;
932 igraph_integer_t prufer_index = 0;
933 igraph_integer_t n = igraph_vcount(graph);
934 igraph_bool_t is_tree = 0;
935
936 IGRAPH_CHECK(igraph_is_tree(graph, &is_tree, NULL, IGRAPH_ALL));
937
938 if (!is_tree) {
939 IGRAPH_ERROR("The graph must be a tree", IGRAPH_EINVAL);
940 }
941
942 if (n < 2) {
943 IGRAPH_ERROR("The tree must have at least 2 vertices", IGRAPH_EINVAL);
944 }
945
946 IGRAPH_CHECK(igraph_vector_int_resize(prufer, n - 2));
947 IGRAPH_VECTOR_INIT_FINALLY(°rees, n);
948 IGRAPH_VECTOR_INIT_FINALLY(&neighbors, 1);
949
950 IGRAPH_CHECK(igraph_degree(graph, °rees, igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS));
951
952 for (u = 0; u < n; ++u) {
953 igraph_integer_t degree = VECTOR(degrees)[u];
954 igraph_integer_t leaf = u;
955
956 while (degree == 1 && leaf <= u) {
957 igraph_integer_t i;
958 igraph_integer_t neighbor = 0;
959 igraph_integer_t neighbor_count = 0;
960
961 VECTOR(degrees)[leaf] = 0; /* mark leaf v as deleted */
962
963 IGRAPH_CHECK(igraph_neighbors(graph, &neighbors, leaf, IGRAPH_ALL));
964
965 /* Find the unique remaining neighbor of the leaf */
966 neighbor_count = igraph_vector_size(&neighbors);
967 for (i = 0; i < neighbor_count; i++) {
968 neighbor = VECTOR(neighbors)[i];
969 if (VECTOR(degrees)[neighbor] > 0) {
970 break;
971 }
972 }
973
974 /* remember that we have removed the leaf */
975 VECTOR(degrees)[neighbor]--;
976 degree = VECTOR(degrees)[neighbor];
977
978 /* Add the neighbor to the prufer sequence unless it is the last vertex
979 (i.e. degree == 0) */
980 if (degree > 0) {
981 VECTOR(*prufer)[prufer_index] = neighbor;
982 prufer_index++;
983 }
984 leaf = neighbor;
985 }
986 }
987
988 igraph_vector_destroy(°rees);
989 igraph_vector_destroy(&neighbors);
990 IGRAPH_FINALLY_CLEAN(2);
991
992 return IGRAPH_SUCCESS;
993 }
994