4
Copyright (C) 2003, 2004, 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
28
#include <string.h> /* memset */
31
* \section about_adjlists
32
* <para>Sometimes it is easier to work with a graph which is in
33
* adjacency list format: a list of vectors; each vector contains the
34
* neighbor vertices or adjacent edges of a given vertex. Typically,
35
* this representation is good if we need to iterate over the neigbors
36
* of all vertices many times. E.g. when finding the shortest paths
37
* between every pairs of vertices or calculating closeness centrality
38
* for all the vertices.</para>
40
* <para>The <type>igraph_adjlist_t</type> stores the adjacency lists
41
* of a graph. After creation it is independent of the original graph,
42
* it can be modified freely with the usual vector operations, the
43
* graph is not affected. E.g. the adjacency list can be used to
44
* rewire the edges of a graph efficiently. If one used the
45
* straightforward \ref igraph_delete_edges() and \ref
46
* igraph_add_edges() combination for this that needs O(|V|+|E|) time
47
* for every single deletion and insertion operation, it is thus very
48
* slow if many edges are rewired. Extracting the graph into an
49
* adjacency list, do all the rewiring operations on the vectors of
50
* the adjacency list and then creating a new graph needs (depending
51
* on how exactly the rewiring is done) typically O(|V|+|E|) time for
52
* the whole rewiring process.</para>
54
* <para>Lazy adjacency lists are a bit different. When creating a
55
* lazy adjacency list, the neighbors of the vertices are not queried,
56
* only some memory is allocated for the vectors. When \ref
57
* igraph_lazy_adjlist_get() is called for vertex v the first time,
58
* the neighbors of v are queried and stored in a vector of the
59
* adjacency list, so they don't need to be queried again. Lazy
60
* adjacency lists are handy if you have an at least linear operation
61
* (because initialization is generally linear in terms of number of
62
* vertices), but you don't know how many vertices you will visit
63
* during the computation.
69
* \function igraph_adjlist_init
70
* Initialize an adjacency list of vertices
72
* Create a list of vectors containing the neighbors of all vertices
73
* in a graph. The adjacency list is independent of the graph after
74
* creation, e.g. the graph can be destroyed and modified, the
75
* adjacency list contains the state of the graph at the time of its
77
* \param graph The input graph.
78
* \param al Pointer to an uninitialized <type>igraph_adjlist_t</type> object.
79
* \param mode Constant specifying whether outgoing
80
* (<code>IGRAPH_OUT</code>), incoming (<code>IGRAPH_IN</code>),
81
* or both (<code>IGRAPH_ALL</code>) types of neighbors to include
82
* in the adjacency list. It is ignored for undirected networks.
85
* Time complexity: O(|V|+|E|), linear in the number of vertices and
89
int igraph_adjlist_init(const igraph_t *graph, igraph_adjlist_t *al,
90
igraph_neimode_t mode) {
93
if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
94
IGRAPH_ERROR("Cannot create adjlist view", IGRAPH_EINVMODE);
97
if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }
99
al->length=igraph_vcount(graph);
100
al->adjs=igraph_Calloc(al->length, igraph_vector_t);
102
IGRAPH_ERROR("Cannot create adjlist view", IGRAPH_ENOMEM);
105
IGRAPH_FINALLY(igraph_adjlist_destroy, al);
106
for (i=0; i<al->length; i++) {
107
IGRAPH_ALLOW_INTERRUPTION();
108
IGRAPH_CHECK(igraph_vector_init(&al->adjs[i], 0));
109
IGRAPH_CHECK(igraph_neighbors(graph, &al->adjs[i], i, mode));
112
IGRAPH_FINALLY_CLEAN(1);
117
* \function igraph_adjlist_init_complementer
118
* Adjacency lists for the complementer graph
120
* This function creates adjacency lists for the complementer
121
* of the input graph. In the complementer graph all edges are present
122
* which are not present in the original graph. Multiple edges in the
123
* input graph are ignored.
124
* \param graph The input graph.
125
* \param al Pointer to a not yet initialized adjacency list.
126
* \param mode Constant specifying whether outgoing
127
* (<code>IGRAPH_OUT</code>), incoming (<code>IGRAPH_IN</code>),
128
* or both (<code>IGRAPH_ALL</code>) types of neighbors (in the
129
* complementer graph) to include in the adjacency list. It is
130
* ignored for undirected networks.
131
* \param loops Whether to consider loop edges.
132
* \return Error code.
134
* Time complexity: O(|V|^2+|E|), quadratic in the number of vertices.
137
int igraph_adjlist_init_complementer(const igraph_t *graph,
138
igraph_adjlist_t *al,
139
igraph_neimode_t mode,
140
igraph_bool_t loops) {
145
if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
146
IGRAPH_ERROR("Cannot create complementer adjlist view", IGRAPH_EINVMODE);
149
if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }
151
al->length=igraph_vcount(graph);
152
al->adjs=igraph_Calloc(al->length, igraph_vector_t);
154
IGRAPH_ERROR("Cannot create complementer adjlist view", IGRAPH_ENOMEM);
157
IGRAPH_FINALLY(igraph_adjlist_destroy, al);
160
seen=igraph_Calloc(n, igraph_bool_t);
162
IGRAPH_ERROR("Cannot create complementer adjlist view", IGRAPH_ENOMEM);
164
IGRAPH_FINALLY(igraph_free, seen);
166
IGRAPH_VECTOR_INIT_FINALLY(&vec, 0);
168
for (i=0; i<al->length; i++) {
169
IGRAPH_ALLOW_INTERRUPTION();
170
igraph_neighbors(graph, &vec, i, mode);
171
memset(seen, 0, sizeof(igraph_bool_t)*al->length);
173
if (!loops) { seen[i] = 1; n--; }
174
for (j=0; j<igraph_vector_size(&vec); j++) {
175
if (! seen [ (long int) VECTOR(vec)[j] ] ) {
177
seen[ (long int) VECTOR(vec)[j] ] = 1;
180
IGRAPH_CHECK(igraph_vector_init(&al->adjs[i], n));
181
for (j=0, k=0; k<n; j++) {
183
VECTOR(al->adjs[i])[k++] = j;
189
igraph_vector_destroy(&vec);
190
IGRAPH_FINALLY_CLEAN(3);
195
* \function igraph_adjlist_destroy
198
* Free all memory allocated for an adjacency list.
199
* \param al The adjacency list to destroy.
201
* Time complexity: depends on memory management.
204
void igraph_adjlist_destroy(igraph_adjlist_t *al) {
206
for (i=0; i<al->length; i++) {
207
if (&al->adjs[i]) { igraph_vector_destroy(&al->adjs[i]); }
209
igraph_Free(al->adjs);
213
* \function igraph_adjlist_size
214
* Number of vertices in an adjacency list.
216
* \param al The adjacency list.
217
* \return The number of elements.
219
* Time complexity: O(1).
222
igraph_integer_t igraph_adjlist_size(const igraph_adjlist_t *al) {
226
/* igraph_vector_t *igraph_adjlist_get(igraph_adjlist_t *al, igraph_integer_t no) { */
227
/* return &al->adjs[(long int)no]; */
231
* \function igraph_adjlist_sort
232
* Sort each vector in an adjacency list.
234
* Sorts every vector of the adjacency list.
235
* \param al The adjacency list.
237
* Time complexity: O(n log n), n is the total number of elements in
238
* the adjacency list.
241
void igraph_adjlist_sort(igraph_adjlist_t *al) {
243
for (i=0; i<al->length; i++)
244
igraph_vector_sort(&al->adjs[i]);
248
* \function igraph_adjlist_simplify
251
* Simplify an adjacency list, ie. remove loop and multiple edges.
252
* \param al The adjacency list.
253
* \return Error code.
255
* Time complexity: O(|V|+|E|), linear in the number of edges and
259
int igraph_adjlist_simplify(igraph_adjlist_t *al) {
261
long int n=al->length;
262
igraph_vector_t mark;
263
IGRAPH_VECTOR_INIT_FINALLY(&mark, n);
264
for (i=0; i<n; i++) {
265
igraph_vector_t *v=&al->adjs[i];
266
long int j, l=igraph_vector_size(v);
267
VECTOR(mark)[i] = i+1;
268
for (j=0; j<l; /* nothing */) {
269
long int e=VECTOR(*v)[j];
270
if (VECTOR(mark)[e] != i+1) {
274
VECTOR(*v)[j] = igraph_vector_tail(v);
275
igraph_vector_pop_back(v);
281
igraph_vector_destroy(&mark);
282
IGRAPH_FINALLY_CLEAN(1);
287
* \function igraph_adjedgelist_init
288
* Initialize an adjacency list of edges
290
* Create a list of vectors containing the adjacent edges for all
291
* vertices. The adjacency list is independent of the graph after
292
* creation, subsequent changes of the graph object do not update the
293
* adjacency list, and changes to the adjacency list do no update the
295
* \param graph The input graph.
296
* \param ael Pointer to an uninitialized adjcency list.
297
* \param mode Constant specifying whether incoming edges
298
* (<code>IGRAPH_IN</code>), outgoing edges (<code>IGRAPH_OUT</code>) or
299
* both (<code>IGRAPH_ALL</code>) to include in the adjacency lists
300
* of directed graphs. It is ignored for undirected graphs.
301
* \return Error code.
303
* Time complexity: O(|V|+|E|), linear in the number of vertices and
307
int igraph_adjedgelist_init(const igraph_t *graph,
308
igraph_adjedgelist_t *ael,
309
igraph_neimode_t mode) {
312
if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
313
IGRAPH_ERROR("Cannot create adjedgelist view", IGRAPH_EINVMODE);
316
if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }
318
ael->length=igraph_vcount(graph);
319
ael->adjs=igraph_Calloc(ael->length, igraph_vector_t);
320
if (ael->adjs == 0) {
321
IGRAPH_ERROR("Cannot create adjedgelist view", IGRAPH_ENOMEM);
324
IGRAPH_FINALLY(igraph_adjlist_destroy, ael);
325
for (i=0; i<ael->length; i++) {
326
IGRAPH_ALLOW_INTERRUPTION();
327
IGRAPH_CHECK(igraph_vector_init(&ael->adjs[i], 0));
328
IGRAPH_CHECK(igraph_adjacent(graph, &ael->adjs[i], i, mode));
331
IGRAPH_FINALLY_CLEAN(1);
336
* \function igraph_adjedgelist_destroy
339
* Free all memory allocated for an adjacency list.
340
* \param eal The adjcency list to destroy.
342
* Time complexity: depends on memory management.
345
void igraph_adjedgelist_destroy(igraph_adjedgelist_t *ael) {
347
for (i=0; i<ael->length; i++) {
348
/* This works if some igraph_vector_t's are 0, because igraph_vector_destroy can
350
igraph_vector_destroy(&ael->adjs[i]);
352
igraph_Free(ael->adjs);
356
* \function igraph_lazy_adjlist_init
359
* Create a lazy adjacency list for vertices. This function only
360
* allocates some memory for storing the vectors of an adjacency list,
361
* but the neighbor vertices are not queried, only at the \ref
362
* igraph_lazy_adjlist_get() calls.
363
* \param graph The input graph.
364
* \param al Pointer to an uninitialized adjacency list object.
365
* \param mode Constant, it gives whether incoming edges
366
* (<code>IGRAPH_IN</code>), outgoing edges
367
* (<code>IGRPAH_OUT</code>) or both types of edges
368
* (<code>IGRAPH_ALL</code>) are considered. It is ignored for
370
* \param simplify Constant, it gives whether to simplify the vectors
371
* in the adjacency list (<code>IGRAPH_SIMPLIFY</code>) ot not
372
* (<code>IGRAPH_DONT_SIMPLIFY</code>).
373
* \return Error code.
375
* Time complexity: O(|V|), the number of vertices, possibly, but
376
* depends on the underlying memory management too.
379
int igraph_lazy_adjlist_init(const igraph_t *graph,
380
igraph_lazy_adjlist_t *al,
381
igraph_neimode_t mode,
382
igraph_lazy_adlist_simplify_t simplify) {
383
if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
384
IGRAPH_ERROR("Cannor create adjlist view", IGRAPH_EINVMODE);
387
if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }
389
al->simplify=simplify;
392
al->length=igraph_vcount(graph);
393
al->adjs=igraph_Calloc(al->length, igraph_vector_t*);
395
IGRAPH_ERROR("Cannot create lazy adjlist view", IGRAPH_ENOMEM);
402
* \function igraph_lazy_adjlist_destroy
405
* Free all allocated memory for a lazy adjacency list.
406
* \param al The adjacency list to deallocate.
408
* Time complexity: depends on the memory management.
411
void igraph_lazy_adjlist_destroy(igraph_lazy_adjlist_t *al) {
412
long int i, n=al->length;
413
for (i=0; i<n; i++) {
414
if (al->adjs[i] != 0) {
415
igraph_vector_destroy(al->adjs[i]);
416
igraph_Free(al->adjs[i]);
419
igraph_Free(al->adjs);
422
igraph_vector_t *igraph_lazy_adjlist_get_real(igraph_lazy_adjlist_t *al,
423
igraph_integer_t pno) {
426
if (al->adjs[no] == 0) {
427
al->adjs[no] = igraph_Calloc(1, igraph_vector_t);
428
if (al->adjs[no] == 0) {
429
igraph_error("Lazy adjlist failed", __FILE__, __LINE__,
432
ret=igraph_vector_init(al->adjs[no], 0);
434
igraph_error("", __FILE__, __LINE__, ret);
436
ret=igraph_neighbors(al->graph, al->adjs[no], no, al->mode);
438
igraph_error("", __FILE__, __LINE__, ret);
441
if (al->simplify == IGRAPH_SIMPLIFY) {
442
igraph_vector_t *v=al->adjs[no];
443
long int i, p=0, n=igraph_vector_size(v);
444
for (i=0; i<n; i++) {
445
if (VECTOR(*v)[i] != no &&
446
(i==n-1 || VECTOR(*v)[i+1] != VECTOR(*v)[i])) {
447
VECTOR(*v)[p]=VECTOR(*v)[i];
451
igraph_vector_resize(v, p);
459
* \function igraph_lazy_adjedgelist_init
462
* Create a lazy adjacency list for edges. This function only
463
* allocates some memory for storing the vectors of an adjacency list,
464
* but the adjacent edges are not queried, only when \ref
465
* igraph_lazy_adjedgelist_get() is called.
466
* \param graph The input graph.
467
* \param al Pointer to an uninitialized adjacency list.
468
* \param mode Constant, it gives whether incoming edges
469
* (<code>IGRAPH_IN</code>), outgoing edges
470
* (<code>IGRPAH_OUT</code>) or both types of edges
471
* (<code>IGRAPH_ALL</code>) are considered. It is ignored for
473
* \return Error code.
475
* Time complexity: O(|V|), the number of vertices, possibly. But it
476
* also depends on the underlying memory management too.
479
int igraph_lazy_adjedgelist_init(const igraph_t *graph,
480
igraph_lazy_adjedgelist_t *al,
481
igraph_neimode_t mode) {
483
if (mode != IGRAPH_IN && mode != IGRAPH_OUT && mode != IGRAPH_ALL) {
484
IGRAPH_ERROR("Cannot create adjlist view", IGRAPH_EINVMODE);
487
if (!igraph_is_directed(graph)) { mode=IGRAPH_ALL; }
492
al->length=igraph_vcount(graph);
493
al->adjs=igraph_Calloc(al->length, igraph_vector_t*);
495
IGRAPH_ERROR("Cannot create lazy adjedgelist view", IGRAPH_ENOMEM);
503
* \function igraph_lazy_adjedgelist_destroy
506
* Free all allocated memory for a lazy edge adjacency list.
507
* \param al The adjacency list to deallocate.
509
* Time complexity: depends on memory management.
512
void igraph_lazy_adjedgelist_destroy(igraph_lazy_adjedgelist_t *al) {
513
long int i, n=al->length;
514
for (i=0; i<n; i++) {
515
if (al->adjs[i] != 0) {
516
igraph_vector_destroy(al->adjs[i]);
517
igraph_Free(al->adjs[i]);
520
igraph_Free(al->adjs);
523
igraph_vector_t *igraph_lazy_adjedgelist_get_real(igraph_lazy_adjedgelist_t *al,
524
igraph_integer_t pno) {
527
if (al->adjs[no] == 0) {
528
al->adjs[no] = igraph_Calloc(1, igraph_vector_t);
529
if (al->adjs[no] == 0) {
530
igraph_error("Lazy adjedgelist failed", __FILE__, __LINE__,
533
ret=igraph_vector_init(al->adjs[no], 0);
535
igraph_error("", __FILE__, __LINE__, ret);
537
ret=igraph_adjacent(al->graph, al->adjs[no], no, al->mode);
539
igraph_error("", __FILE__, __LINE__, ret);
added
removed
src/adjlist.c
