4
Copyright (C) 2005 Gabor Csardi <csardi@rmki.kfki.hu>
5
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
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.
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.
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
30
* \function igraph_get_adjacency
31
* \brief Returns the adjacency matrix of a graph
34
* The result is an incidence matrix, it contains numbers greater
35
* than one if there are multiple edges in the graph.
36
* \param graph Pointer to the graph to convert
37
* \param res Pointer to an initialized matrix object, it will be
39
* \param type Constant giving the type of the adjacency matrix to
40
* create for undirected graphs. It is ignored for directed
41
* graphs. Possible values:
43
* \cli IGRAPH_GET_ADJACENCY_UPPER
44
* the upper right triangle of the matrix is used.
45
* \cli IGRAPH_GET_ADJACENCY_LOWER
46
* the lower left triangle of the matrix is used.
47
* \cli IGRAPH_GET_ADJACENCY_BOTH
48
* the whole matrix is used, a symmetric matrix is returned.
51
* \c IGRAPH_EINVAL invalid type argument.
53
* \sa igraph_get_adjacency_sparse if you want a sparse matrix representation
55
* Time complexity: O(|V||V|),
57
* number of vertices in the graph.
60
int igraph_get_adjacency(const igraph_t *graph, igraph_matrix_t *res,
61
igraph_get_adjacency_t type) {
64
long int no_of_nodes=igraph_vcount(graph);
65
igraph_bool_t directed=igraph_is_directed(graph);
68
igraph_integer_t ffrom, fto;
70
IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, no_of_nodes));
71
igraph_matrix_null(res);
72
IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(0), &edgeit));
73
IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
76
while (!IGRAPH_EIT_END(edgeit)) {
77
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
80
MATRIX(*res, from, to) += 1;
81
IGRAPH_EIT_NEXT(edgeit);
83
} else if (type==IGRAPH_GET_ADJACENCY_UPPER) {
84
while (!IGRAPH_EIT_END(edgeit)) {
85
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
89
MATRIX(*res, to, from) += 1;
91
MATRIX(*res, from, to) += 1;
93
IGRAPH_EIT_NEXT(edgeit);
95
} else if (type==IGRAPH_GET_ADJACENCY_LOWER) {
96
while (!IGRAPH_EIT_END(edgeit)) {
97
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
101
MATRIX(*res, from, to) += 1;
103
MATRIX(*res, to, from) += 1;
105
IGRAPH_EIT_NEXT(edgeit);
107
} else if (type==IGRAPH_GET_ADJACENCY_BOTH) {
108
while (!IGRAPH_EIT_END(edgeit)) {
109
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
112
MATRIX(*res, from, to) += 1;
114
MATRIX(*res, to, from) += 1;
116
IGRAPH_EIT_NEXT(edgeit);
119
IGRAPH_ERROR("Invalid type argument", IGRAPH_EINVAL);
122
igraph_eit_destroy(&edgeit);
123
IGRAPH_FINALLY_CLEAN(1);
128
* \ingroup conversion
129
* \function igraph_get_adjacency_sparse
130
* \brief Returns the adjacency matrix of a graph in sparse matrix format
133
* The result is an incidence matrix, it contains numbers greater
134
* than one if there are multiple edges in the graph.
135
* \param graph Pointer to the graph to convert
136
* \param res Pointer to an initialized sparse matrix object, it will be
138
* \param type Constant giving the type of the adjacency matrix to
139
* create for undirected graphs. It is ignored for directed
140
* graphs. Possible values:
142
* \cli IGRAPH_GET_ADJACENCY_UPPER
143
* the upper right triangle of the matrix is used.
144
* \cli IGRAPH_GET_ADJACENCY_LOWER
145
* the lower left triangle of the matrix is used.
146
* \cli IGRAPH_GET_ADJACENCY_BOTH
147
* the whole matrix is used, a symmetric matrix is returned.
149
* \return Error code:
150
* \c IGRAPH_EINVAL invalid type argument.
152
* \sa igraph_get_adjacency if you would like to get a normal matrix
153
* ( \ref igraph_matrix_t )
155
* Time complexity: O(|V||V|),
157
* number of vertices in the graph.
160
int igraph_get_adjacency_sparse(const igraph_t *graph, igraph_spmatrix_t *res,
161
igraph_get_adjacency_t type) {
164
long int no_of_nodes=igraph_vcount(graph);
165
igraph_bool_t directed=igraph_is_directed(graph);
168
igraph_integer_t ffrom, fto;
170
igraph_spmatrix_null(res);
171
IGRAPH_CHECK(igraph_spmatrix_resize(res, no_of_nodes, no_of_nodes));
172
IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(0), &edgeit));
173
IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
176
while (!IGRAPH_EIT_END(edgeit)) {
177
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
180
igraph_spmatrix_add_e(res, from, to, 1);
181
IGRAPH_EIT_NEXT(edgeit);
183
} else if (type==IGRAPH_GET_ADJACENCY_UPPER) {
184
while (!IGRAPH_EIT_END(edgeit)) {
185
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
189
igraph_spmatrix_add_e(res, to, from, 1);
191
igraph_spmatrix_add_e(res, from, to, 1);
193
IGRAPH_EIT_NEXT(edgeit);
195
} else if (type==IGRAPH_GET_ADJACENCY_LOWER) {
196
while (!IGRAPH_EIT_END(edgeit)) {
197
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
201
igraph_spmatrix_add_e(res, to, from, 1);
203
igraph_spmatrix_add_e(res, from, to, 1);
205
IGRAPH_EIT_NEXT(edgeit);
207
} else if (type==IGRAPH_GET_ADJACENCY_BOTH) {
208
while (!IGRAPH_EIT_END(edgeit)) {
209
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &ffrom, &fto);
212
igraph_spmatrix_add_e(res, from, to, 1);
214
igraph_spmatrix_add_e(res, to, from, 1);
216
IGRAPH_EIT_NEXT(edgeit);
219
IGRAPH_ERROR("Invalid type argument", IGRAPH_EINVAL);
222
igraph_eit_destroy(&edgeit);
223
IGRAPH_FINALLY_CLEAN(1);
228
* \ingroup conversion
229
* \function igraph_get_edgelist
230
* \brief Returns the list of edges in a graph
232
* </para><para>The order of the edges is given by the edge ids.
233
* \param graph Pointer to the graph object
234
* \param res Pointer to an initialized vector object, it will be
236
* \param bycol Logical, if true, the edges will be returned
237
* columnwise, eg. the first edge is
238
* <code>res[0]->res[|E|]</code>, the second is
239
* <code>res[1]->res[|E|+1]</code>, etc.
240
* \return Error code.
242
* Time complexity: O(|E|), the
243
* number of edges in the graph.
246
int igraph_get_edgelist(const igraph_t *graph, igraph_vector_t *res, igraph_bool_t bycol) {
249
long int no_of_edges=igraph_ecount(graph);
251
igraph_integer_t from, to;
253
IGRAPH_CHECK(igraph_vector_resize(res, no_of_edges*2));
254
IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(IGRAPH_EDGEORDER_ID),
256
IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
259
while (!IGRAPH_EIT_END(edgeit)) {
260
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &from, &to);
261
VECTOR(*res)[vptr]=from;
262
VECTOR(*res)[vptr+no_of_edges]=to;
264
IGRAPH_EIT_NEXT(edgeit);
267
while (!IGRAPH_EIT_END(edgeit)) {
268
igraph_edge(graph, IGRAPH_EIT_GET(edgeit), &from, &to);
269
VECTOR(*res)[vptr++]=from;
270
VECTOR(*res)[vptr++]=to;
271
IGRAPH_EIT_NEXT(edgeit);
275
igraph_eit_destroy(&edgeit);
276
IGRAPH_FINALLY_CLEAN(1);
281
* \function igraph_to_directed
282
* \brief Convert an undirected graph to a directed one
285
* If the supplied graph is directed, this function does nothing.
286
* \param graph The graph object to convert.
287
* \param mode Constant, specifies the details of how exactly the
288
* conversion is done. Possible values: \c
289
* IGRAPH_TO_DIRECTED_ARBITRARY: the number of edges in the
290
* graph stays the same, an arbitrarily directed edge is
291
* created for each undirected edge;
292
* \c IGRAPH_TO_DIRECTED_MUTUAL: two directed edges are
293
* created for each undirected edge, one in each direction.
294
* \return Error code.
296
* Time complexity: O(|V|+|E|), the number of vertices plus the number
300
int igraph_to_directed(igraph_t *graph,
301
igraph_to_directed_t mode) {
303
if (mode != IGRAPH_TO_DIRECTED_ARBITRARY &&
304
mode != IGRAPH_TO_DIRECTED_MUTUAL) {
305
IGRAPH_ERROR("Cannot directed graph, invalid mode", IGRAPH_EINVAL);
308
if (igraph_is_directed(graph)) {
312
if (mode==IGRAPH_TO_DIRECTED_ARBITRARY) {
315
igraph_vector_t edges;
316
long int no_of_edges=igraph_ecount(graph);
317
long int no_of_nodes=igraph_vcount(graph);
318
long int size=no_of_edges*2;
319
IGRAPH_VECTOR_INIT_FINALLY(&edges, size);
320
IGRAPH_CHECK(igraph_get_edgelist(graph, &edges, 0));
322
IGRAPH_CHECK(igraph_create(&newgraph, &edges, no_of_nodes,
324
IGRAPH_FINALLY(igraph_destroy, &newgraph);
325
igraph_vector_destroy(&edges);
326
IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
327
IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1,1,1);
328
IGRAPH_FINALLY_CLEAN(2);
329
igraph_destroy(graph);
332
} else if (mode==IGRAPH_TO_DIRECTED_MUTUAL) {
335
igraph_vector_t edges;
336
igraph_vector_t index;
337
long int no_of_edges=igraph_ecount(graph);
338
long int no_of_nodes=igraph_vcount(graph);
339
long int size=no_of_edges*4;
341
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
342
IGRAPH_CHECK(igraph_vector_reserve(&edges, size));
343
IGRAPH_CHECK(igraph_get_edgelist(graph, &edges, 0));
344
IGRAPH_CHECK(igraph_vector_resize(&edges, no_of_edges*4));
345
IGRAPH_VECTOR_INIT_FINALLY(&index, no_of_edges*2);
346
for (i=0; i<no_of_edges; i++) {
347
VECTOR(edges)[no_of_edges*2+i*2] =VECTOR(edges)[i*2+1];
348
VECTOR(edges)[no_of_edges*2+i*2+1]=VECTOR(edges)[i*2];
349
VECTOR(index)[i] = VECTOR(index)[no_of_edges+i] = i+1;
352
IGRAPH_CHECK(igraph_create(&newgraph, &edges, no_of_nodes,
354
IGRAPH_FINALLY(igraph_destroy, &newgraph);
355
IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
356
IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1,1,1);
357
IGRAPH_CHECK(igraph_i_attribute_permute_edges(&newgraph, &index));
359
igraph_vector_destroy(&index);
360
igraph_vector_destroy(&edges);
361
igraph_destroy(graph);
362
IGRAPH_FINALLY_CLEAN(3);
370
* \function igraph_to_undirected
371
* \brief Convert a directed graph to an undirected one.
374
* If the supplied graph is undirected, this function does nothing.
375
* \param graph The graph object to convert.
376
* \param mode Constant, specifies the details of how exactly the
377
* convesion is done. Possible values: \c
378
* IGRAPH_TO_UNDIRECTED_EACH: the number of edges remains
379
* constant, an undirected edge is created for each directed
380
* one, this version might create graphs with multiple edges;
381
* \c IGRAPH_TO_UNDIRECTED_COLLAPSE: one undirected edge will
382
* be created for each pair of vertices which are connected
383
* with at least one directed edge, no multiple edges will be
385
* \return Error code.
387
* Time complexity: O(|V|+|E|), the number of vertices plus the number
391
int igraph_to_undirected(igraph_t *graph,
392
igraph_to_undirected_t mode) {
393
long int no_of_nodes=igraph_vcount(graph);
394
long int no_of_edges=igraph_ecount(graph);
395
igraph_vector_t edges;
398
if (mode != IGRAPH_TO_UNDIRECTED_EACH &&
399
mode != IGRAPH_TO_UNDIRECTED_COLLAPSE) {
400
IGRAPH_ERROR("Cannot undirect graph, invalid mode", IGRAPH_EINVAL);
403
if (!igraph_is_directed(graph)) {
407
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
409
if (mode==IGRAPH_TO_UNDIRECTED_EACH) {
413
IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges*2));
414
IGRAPH_CHECK(igraph_es_all(&es, IGRAPH_EDGEORDER_ID));
415
IGRAPH_FINALLY(igraph_es_destroy, &es);
416
IGRAPH_CHECK(igraph_eit_create(graph, es, &eit));
417
IGRAPH_FINALLY(igraph_eit_destroy, &eit);
419
while (!IGRAPH_EIT_END(eit)) {
420
long int edge=IGRAPH_EIT_GET(eit);
421
igraph_integer_t from, to;
422
igraph_edge(graph, edge, &from, &to);
423
IGRAPH_CHECK(igraph_vector_push_back(&edges, from));
424
IGRAPH_CHECK(igraph_vector_push_back(&edges, to));
425
IGRAPH_EIT_NEXT(eit);
428
igraph_eit_destroy(&eit);
429
igraph_es_destroy(&es);
430
IGRAPH_FINALLY_CLEAN(2);
432
IGRAPH_CHECK(igraph_create(&newgraph, &edges, no_of_nodes, IGRAPH_UNDIRECTED));
433
IGRAPH_FINALLY(igraph_destroy, &newgraph);
434
igraph_vector_destroy(&edges);
435
IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
436
IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1,1,1);
437
IGRAPH_FINALLY_CLEAN(2);
438
igraph_destroy(graph);
441
} else if (mode==IGRAPH_TO_UNDIRECTED_COLLAPSE) {
442
igraph_vector_t seen, nei;
444
IGRAPH_CHECK(igraph_vector_reserve(&edges, no_of_edges*2));
445
IGRAPH_VECTOR_INIT_FINALLY(&seen, no_of_nodes);
446
IGRAPH_VECTOR_INIT_FINALLY(&nei, 0);
448
for (i=0; i<no_of_nodes; i++) {
449
IGRAPH_CHECK(igraph_neighbors(graph, &nei, i, IGRAPH_ALL));
450
for (j=0; j<igraph_vector_size(&nei); j++) {
451
long int node=VECTOR(nei)[j];
452
if (VECTOR(seen)[node] != i+1 && node >= i) {
453
IGRAPH_CHECK(igraph_vector_push_back(&edges, i));
454
IGRAPH_CHECK(igraph_vector_push_back(&edges, node));
455
VECTOR(seen)[node]=i+1;
460
igraph_vector_destroy(&nei);
461
igraph_vector_destroy(&seen);
462
IGRAPH_FINALLY_CLEAN(2);
464
IGRAPH_CHECK(igraph_create(&newgraph, &edges, no_of_nodes, IGRAPH_UNDIRECTED));
465
IGRAPH_FINALLY(igraph_destroy, &newgraph);
466
igraph_vector_destroy(&edges);
467
IGRAPH_I_ATTRIBUTE_DESTROY(&newgraph);
468
IGRAPH_I_ATTRIBUTE_COPY(&newgraph, graph, 1,1,0); /* no edge attributes */
469
IGRAPH_FINALLY_CLEAN(2);
470
igraph_destroy(graph);
added
removed
src/conversion.c
