igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 7. Data structure library: vector, matrix, other data types

1. About template types

Some of the container types listed in this section are defined for many base types. This is similar to templates in C++ and generics in Ada, but it is implemented via preprocessor macros since the C language cannot handle it. Here is the list of template types and the all base types they currently support:

vector

Vector is currently defined for igraph_real_t, igraph_integer_t (int), char (char), igraph_bool_t (bool) and igraph_complex_t (complex). The default is igraph_real_t.

matrix

Matrix is currently defined for igraph_real_t, igraph_integer_t (int), char (char), igraph_bool_t (bool) and igraph_complex_t (complex). The default is igraph_real_t.

array3

Array3 is currently defined for igraph_real_t, igraph_integer_t (int), char (char) and igraph_bool_t (bool). The default is igraph_real_t.

stack

Stack is currently defined for igraph_real_t, igraph_integer_t (int), char (char), igraph_bool_t (bool) and void* (ptr). The default is igraph_real_t.

double-ended queue

Dqueue is currently defined for igraph_real_t, igraph_integer_t (int), char (char) and igraph_bool_t (bool). The default is igraph_real_t.

heap

Heap is currently defined for igraph_real_t, igraph_integer_t (int), char (char). In addition both maximum and minimum heaps are available. The default is the igraph_real_t maximum heap.

The name of the base element (in parentheses) is added to the function names, except for the default type.

Some examples:

  • igraph_vector_t is a vector of igraph_real_t elements. Its functions are igraph_vector_init, igraph_vector_destroy, igraph_vector_sort, etc.

  • igraph_vector_bool_t is a vector of igraph_bool_t elements; initialize it with igraph_vector_bool_init, destroy it with igraph_vector_bool_destroy, etc.

  • igraph_heap_t is a maximum heap with igraph_real_t elements. The corresponding functions are igraph_heap_init, igraph_heap_pop, etc.

  • igraph_heap_min_t is a minimum heap with igraph_real_t elements. The corresponding functions are called igraph_heap_min_init, igraph_heap_min_pop, etc.

  • igraph_heap_int_t is a maximum heap with igraph_integer_t elements. Its functions have the igraph_heap_int_ prefix.

  • igraph_heap_min_int_t is a minimum heap containing igraph_integer_t elements. Its functions have the igraph_heap_min_int_ prefix.

Note that the VECTOR and the MATRIX macros can be used on all vector and matrix types.

2. Vectors

2.1.  About igraph_vector_t objects

The igraph_vector_t data type is a simple and efficient interface to arrays containing numbers. It is something similar to (but much simpler than) the vector template in the C++ standard library.

There are multiple variants of igraph_vector_t; the basic variant stores doubles, but there is also igraph_vector_int_t for integers (of type igraph_integer_t), igraph_vector_bool_t for booleans (of type igraph_bool_t) and so on. Vectors are used extensively in igraph; all functions that expect or return a list of numbers use igraph_vector_t or igraph_vector_int_t to achieve this. Integer vectors are typically used when the vector is supposed to hold vertex or edge identifiers, while igraph_vector_t is used when the vector is expected to hold fractional numbers or infinities.

The igraph_vector_t type and its variants usually use O(n) space to store n elements. Sometimes they uses more, this is because vectors can shrink, but even if they shrink, the current implementation does not free a single bit of memory.

The elements in an igraph_vector_t object and its variants are indexed from zero, we follow the usual C convention here.

The elements of a vector always occupy a single block of memory, the starting address of this memory block can be queried with the VECTOR macro. This way, vector objects can be used with standard mathematical libraries, like the GNU Scientific Library.

Almost all of the functions desccribed below for igraph_vector_t also exist for all the other vector type variants. These variants are not documented separately; you can simply replace vector with vector_int, vector_bool or something similar if you need a function for another variant. For instance, to initialize a vector of type igraph_vector_int_t, you need to use igraph_vector_int_init() and not igraph_vector_init().

2.2.  Constructors and Destructors

igraph_vector_t objects have to be initialized before using them, this is analogous to calling a constructor on them. There are a number of igraph_vector_t constructors, for your convenience. igraph_vector_init() is the basic constructor, it creates a vector of the given length, filled with zeros. igraph_vector_copy() creates a new identical copy of an already existing and initialized vector. igraph_vector_init_copy() creates a vector by copying a regular C array. igraph_vector_init_seq() creates a vector containing a regular sequence with increment one.

igraph_vector_view() is a special constructor, it allows you to handle a regular C array as a vector without copying its elements.

If a igraph_vector_t object is not needed any more, it should be destroyed to free its allocated memory by calling the igraph_vector_t destructor, igraph_vector_destroy().

Note that vectors created by igraph_vector_view() are special, you must not call igraph_vector_destroy() on these.

2.2.1. igraph_vector_init — Initializes a vector object (constructor).

igraph_error_t igraph_vector_init(igraph_vector_t* v, igraph_integer_t size);

Every vector needs to be initialized before it can be used, and there are a number of initialization functions or otherwise called constructors. This function constructs a vector of the given size and initializes each entry to 0. Note that igraph_vector_null() can be used to set each element of a vector to zero. However, if you want a vector of zeros, it is much faster to use this function than to create a vector and then invoke igraph_vector_null().

Every vector object initialized by this function should be destroyed (ie. the memory allocated for it should be freed) when it is not needed anymore, the igraph_vector_destroy() function is responsible for this.

Arguments: 

v:

Pointer to a not yet initialized vector object.

size:

The size of the vector.

Returns: 

error code: IGRAPH_ENOMEM if there is not enough memory.

Time complexity: operating system dependent, the amount of time required to allocate O(n) elements, n is the number of elements.

2.2.2. igraph_vector_init_copy — Initializes a vector from an ordinary C array (constructor).

igraph_error_t igraph_vector_init_copy(
    igraph_vector_t *v, const igraph_real_t *data, igraph_integer_t length);

Arguments: 

v:

Pointer to an uninitialized vector object.

data:

A regular C array.

length:

The length of the C array.

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

Time complexity: operating system specific, usually O(length).

2.2.3. igraph_vector_init_seq — Initializes a vector with a sequence.

igraph_error_t igraph_vector_init_seq(igraph_vector_t *v,
                                      igraph_real_t from, igraph_real_t to);

The vector will contain the numbers from, from+1, ..., to.

Arguments: 

v:

Pointer to an uninitialized vector object.

from:

The lower limit in the sequence (inclusive).

to:

The upper limit in the sequence (inclusive).

Returns: 

Error code: IGRAPH_ENOMEM: out of memory.

Time complexity: O(n), the number of elements in the vector.

2.2.4. igraph_vector_copy — Initializes a vector from another vector object (constructor).

igraph_error_t igraph_vector_copy(igraph_vector_t *to,
                                  const igraph_vector_t *from);

The contents of the existing vector object will be copied to the new one.

Arguments: 

to:

Pointer to a not yet initialized vector object.

from:

The original vector object to copy.

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

Time complexity: operating system dependent, usually O(n), n is the size of the vector.

2.2.5. igraph_vector_destroy — Destroys a vector object.

void igraph_vector_destroy(igraph_vector_t* v);

All vectors initialized by igraph_vector_init() should be properly destroyed by this function. A destroyed vector needs to be reinitialized by igraph_vector_init(), igraph_vector_init_copy() or another constructor.

Arguments: 

v:

Pointer to the (previously initialized) vector object to destroy.

Time complexity: operating system dependent.

2.3. Initializing elements

2.3.1. igraph_vector_null — Sets each element in the vector to zero.

void igraph_vector_null(igraph_vector_t* v);

Note that igraph_vector_init() sets the elements to zero as well, so it makes no sense to call this function on a just initialized vector. Thus if you want to construct a vector of zeros, then you should use igraph_vector_init().

Arguments: 

v:

The vector object.

Time complexity: O(n), the size of the vector.

2.3.2. igraph_vector_fill — Fill a vector with a constant element

void igraph_vector_fill(igraph_vector_t* v, igraph_real_t e);

Sets each element of the vector to the supplied constant.

Arguments: 

vector:

The vector to work on.

e:

The element to fill with.

Time complexity: O(n), the size of the vector.

2.4.  Accessing elements

The simplest way to access an element of a vector is to use the VECTOR macro. This macro can be used both for querying and setting igraph_vector_t elements. If you need a function, igraph_vector_e() queries and igraph_vector_set() sets an element of a vector. igraph_vector_e_ptr() returns the address of an element.

igraph_vector_tail() returns the last element of a non-empty vector. There is no igraph_vector_head() function however, as it is easy to write VECTOR(v)[0] instead.

2.4.1. VECTOR — Accessing an element of a vector.

#define VECTOR(v)

Usage:

 VECTOR(v)[0] 

to access the first element of the vector, you can also use this in assignments, like:

 VECTOR(v)[10]=5; 

Note that there are no range checks right now. This functionality might be redefined later as a real function instead of a #define.

Arguments: 

v:

The vector object.

Time complexity: O(1).

2.4.2. igraph_vector_e — Access an element of a vector.

igraph_real_t igraph_vector_e(const igraph_vector_t* v, igraph_integer_t pos);

Arguments: 

v:

The igraph_vector_t object.

pos:

The position of the element, the index of the first element is zero.

Returns: 

The desired element.

See also: 

igraph_vector_e_ptr() and the VECTOR macro.

Time complexity: O(1).

2.4.3. igraph_vector_e_ptr — Get the address of an element of a vector

igraph_real_t* igraph_vector_e_ptr(const igraph_vector_t* v, igraph_integer_t pos);

Arguments: 

v:

The igraph_vector_t object.

pos:

The position of the element, the position of the first element is zero.

Returns: 

Pointer to the desired element.

See also: 

igraph_vector_e() and the VECTOR macro.

Time complexity: O(1).

2.4.4. igraph_vector_set — Assignment to an element of a vector.

void igraph_vector_set(igraph_vector_t* v, igraph_integer_t pos, igraph_real_t value);

Arguments: 

v:

The igraph_vector_t element.

pos:

Position of the element to set.

value:

New value of the element.

See also: 

2.4.5. igraph_vector_tail — Returns the last element in a vector.

igraph_real_t igraph_vector_tail(const igraph_vector_t *v);

It is an error to call this function on an empty vector, the result is undefined.

Arguments: 

v:

The vector object.

Returns: 

The last element.

Time complexity: O(1).

2.5. Vector views

2.5.1. igraph_vector_view — Handle a regular C array as a igraph_vector_t.

const igraph_vector_t*igraph_vector_view(const igraph_vector_t *v,
        const igraph_real_t *data, igraph_integer_t length);

This is a special igraph_vector_t constructor. It allows to handle a regular C array as a igraph_vector_t temporarily. Be sure that you don't ever call the destructor (igraph_vector_destroy()) on objects created by this constructor.

Arguments: 

v:

Pointer to an uninitialized igraph_vector_t object.

data:

Pointer, the C array. It may not be NULL.

length:

The length of the C array.

Returns: 

Pointer to the vector object, the same as the v parameter, for convenience.

Time complexity: O(1)

2.6. Copying vectors

2.6.1. igraph_vector_copy_to — Copies the contents of a vector to a C array.

void igraph_vector_copy_to(const igraph_vector_t *v, igraph_real_t *to);

The C array should have sufficient length.

Arguments: 

v:

The vector object.

to:

The C array.

Time complexity: O(n), n is the size of the vector.

2.6.2. igraph_vector_update — Update a vector from another one.

igraph_error_t igraph_vector_update(igraph_vector_t *to,
                                    const igraph_vector_t *from);

After this operation the contents of to will be exactly the same as that of from. The vector to will be resized if it was originally shorter or longer than from.

Arguments: 

to:

The vector to update.

from:

The vector to update from.

Returns: 

Error code.

Time complexity: O(n), the number of elements in from.

2.6.3. igraph_vector_append — Append a vector to another one.

igraph_error_t igraph_vector_append(igraph_vector_t *to,
                                    const igraph_vector_t *from);

The target vector will be resized (except when from is empty).

Arguments: 

to:

The vector to append to.

from:

The vector to append, it is kept unchanged.

Returns: 

Error code.

Time complexity: O(n), the number of elements in the new vector.

2.6.4. igraph_vector_swap — Swap elements of two vectors.

igraph_error_t igraph_vector_swap(igraph_vector_t *v1, igraph_vector_t *v2);

The two vectors must have the same length, otherwise an error happens.

Arguments: 

v1:

The first vector.

v2:

The second vector.

Returns: 

Error code.

Time complexity: O(n), the length of the vectors.

2.7. Exchanging elements

2.7.1. igraph_vector_swap_elements — Swap two elements in a vector.

igraph_error_t igraph_vector_swap_elements(igraph_vector_t *v,
        igraph_integer_t i, igraph_integer_t j);

Note that currently no range checking is performed.

Arguments: 

v:

The input vector.

i:

Index of the first element.

j:

Index of the second element (may be the same as the first one).

Returns: 

Error code, currently always IGRAPH_SUCCESS.

Time complexity: O(1).

2.7.2. igraph_vector_reverse — Reverse the elements of a vector.

igraph_error_t igraph_vector_reverse(igraph_vector_t *v);

The first element will be last, the last element will be first, etc.

Arguments: 

v:

The input vector.

Returns: 

Error code, currently always IGRAPH_SUCCESS.

Time complexity: O(n), the number of elements.

2.7.3. igraph_vector_shuffle — Shuffles a vector in-place using the Fisher-Yates method

igraph_error_t igraph_vector_shuffle(igraph_vector_t *v);

The Fisher-Yates shuffle ensures that every permutation is equally probable when using a proper randomness source. Of course this does not apply to pseudo-random generators as the cycle of these generators is less than the number of possible permutations of the vector if the vector is long enough.

Arguments: 

v:

The vector object.

Returns: 

Error code, currently always IGRAPH_SUCCESS.

Time complexity: O(n), n is the number of elements in the vector.

References:

(Fisher & Yates 1963)

R. A. Fisher and F. Yates. Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd, 6th edition, 1963, page 37.

(Knuth 1998)

D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 3rd edition, 1998, page 145.

Example 7.1.  File examples/simple/igraph_fisher_yates_shuffle.c

/* -*- mode: C -*-  */
/*
  Test suite for the Fisher-Yates shuffle.
  Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com>

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
  02110-1301 USA
*/

#include <igraph.h>

#define R_INTEGER(a,b) (igraph_rng_get_integer(igraph_rng_default(), (a), (b)))
#define R_UNIF(a,b) (igraph_rng_get_unif(igraph_rng_default(), (a), (b)))

int main() {
    igraph_real_t d;
    igraph_vector_t u, v;
    int ret;
    igraph_integer_t i, k, n;

    /********************************
     * Example usage
     ********************************/

    /* Sequences with one element. Such sequences are trivially permuted.
     * The result of any Fisher-Yates shuffle on a sequence with one element
     * must be the original sequence itself.
     */
    n = 1;
    igraph_vector_init(&v, n);
    igraph_rng_seed(igraph_rng_default(), 42); /* make tests deterministic */
    k = R_INTEGER(-1000, 1000);
    VECTOR(v)[0] = k;
    igraph_vector_shuffle(&v);
    if (VECTOR(v)[0] != k) {
        return 1;
    }
    d = R_UNIF(-1000.0, 1000.0);

    VECTOR(v)[0] = d;
    igraph_vector_shuffle(&v);
    if (VECTOR(v)[0] != d) {
        return 2;
    }
    igraph_vector_destroy(&v);

    /* Sequences with multiple elements. A Fisher-Yates shuffle of a sequence S
     * is a random permutation \pi(S) of S. Thus \pi(S) must have the same
     * length and elements as the original sequence S. A major difference between
     * S and its random permutation \pi(S) is that the order in which elements
     * appear in \pi(S) is probably different from how elements are ordered in S.
     * If S has length n = 1, then both \pi(S) and S are equivalent sequences in
     * that \pi(S) is merely S and no permutation has taken place. If S has
     * length n > 1, then there are n! possible permutations of S. Assume that
     * each such permutation is equally likely to appear as a result of the
     * Fisher-Yates shuffle. As n increases, the probability that S is different
     * from \pi(S) also increases. We have a probability of 1 / n! that S and
     * \pi(S) are equivalent sequences.
     */
    n = 100;
    igraph_vector_init(&u, n);
    igraph_vector_init(&v, n);

    for (i = 0; i < n; i++) {
        k = R_INTEGER(-1000, 1000);
        VECTOR(u)[i] = k;
        VECTOR(v)[i] = k;
    }

    igraph_vector_shuffle(&v);
    /* must have same length */
    if (igraph_vector_size(&v) != n) {
        return 3;
    }
    if (igraph_vector_size(&u) != igraph_vector_size(&v)) {
        return 4;
    }
    /* must have same elements */
    igraph_vector_sort(&u);
    igraph_vector_sort(&v);
    if (!igraph_vector_all_e(&u, &v)) {
        return 5;
    }
    igraph_vector_destroy(&u);
    igraph_vector_destroy(&v);

    /* empty sequence */
    igraph_vector_init(&v, 0);
    ret = igraph_vector_shuffle(&v);
    igraph_vector_destroy(&v);

    return ret == 0 ? 0 : 6;
}


2.7.4. igraph_vector_permute — Permutes the elements of a vector in place according to an index vector.

igraph_error_t igraph_vector_permute(igraph_vector_t* v, const igraph_vector_int_t* index);

This function takes a vector v and a corresponding index vector ind, and permutes the elements of v such that v[ind[i]] is moved to become v[i] after the function is executed.

It is an error to call this function with an index vector that does not represent a valid permutation. Each element in the index vector must be between 0 and the length of the vector minus one (inclusive), and each such element must appear only once. The function does not attempt to validate the index vector.

The index vector that this function takes is compatible with the index vector returned from igraph_vector_qsort_ind(); passing in the index vector from igraph_vector_qsort_ind() will sort the original vector.

As a special case, this function allows the index vector to be shorter than the vector being permuted, in which case the elements whose indices do not occur in the index vector will be removed from the vector.

Arguments: 

v:

the vector to permute

ind:

the index vector

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

Time complexity: O(n), the size of the vector.

2.8. Vector operations

2.8.1. igraph_vector_add_constant — Add a constant to the vector.

void igraph_vector_add_constant(igraph_vector_t *v, igraph_real_t plus);

plus is added to every element of v. Note that overflow might happen.

Arguments: 

v:

The input vector.

plus:

The constant to add.

Time complexity: O(n), the number of elements.

2.8.2. igraph_vector_scale — Multiply all elements of a vector by a constant

void igraph_vector_scale(igraph_vector_t *v, igraph_real_t by);

Arguments: 

v:

The vector.

by:

The constant.

Returns: 

Error code. The current implementation always returns with success.

Added in version 0.2.

Time complexity: O(n), the number of elements in a vector.

2.8.3. igraph_vector_add — Add two vectors.

igraph_error_t igraph_vector_add(igraph_vector_t *v1,
                                 const igraph_vector_t *v2);

Add the elements of v2 to v1, the result is stored in v1. The two vectors must have the same length.

Arguments: 

v1:

The first vector, the result will be stored here.

v2:

The second vector, its contents will be unchanged.

Returns: 

Error code.

Time complexity: O(n), the number of elements.

2.8.4. igraph_vector_sub — Subtract a vector from another one.

igraph_error_t igraph_vector_sub(igraph_vector_t *v1,
                                 const igraph_vector_t *v2);

Subtract the elements of v2 from v1, the result is stored in v1. The two vectors must have the same length.

Arguments: 

v1:

The first vector, to subtract from. The result is stored here.

v2:

The vector to subtract, it will be unchanged.

Returns: 

Error code.

Time complexity: O(n), the length of the vectors.

2.8.5. igraph_vector_mul — Multiply two vectors.

igraph_error_t igraph_vector_mul(igraph_vector_t *v1,
                                 const igraph_vector_t *v2);

v1 will be multiplied by v2, elementwise. The two vectors must have the same length.

Arguments: 

v1:

The first vector, the result will be stored here.

v2:

The second vector, it is left unchanged.

Returns: 

Error code.

Time complexity: O(n), the number of elements.

2.8.6. igraph_vector_div — Divide a vector by another one.

igraph_error_t igraph_vector_div(igraph_vector_t *v1,
                                 const igraph_vector_t *v2);

v1 is divided by v2, elementwise. They must have the same length. If the base type of the vector can generate divide by zero errors then please make sure that v2 contains no zero if you want to avoid trouble.

Arguments: 

v1:

The dividend. The result is also stored here.

v2:

The divisor, it is left unchanged.

Returns: 

Error code.

Time complexity: O(n), the length of the vectors.

2.8.7. igraph_vector_floor — Transform a real vector to an integer vector by flooring each element.

igraph_error_t igraph_vector_floor(const igraph_vector_t *from, igraph_vector_int_t *to);

Flooring means rounding down to the nearest integer.

Arguments: 

from:

The original real vector object.

to:

Pointer to an initialized integer vector. The result will be stored here.

Returns: 

Error code: IGRAPH_ENOMEM: out of memory

Time complexity: O(n), where n is the number of elements in the vector.

2.9. Vector comparisons

2.9.1. igraph_vector_all_e — Are all elements equal?

igraph_bool_t igraph_vector_all_e(const igraph_vector_t *lhs,
        const igraph_vector_t *rhs);

Arguments: 

lhs:

The first vector.

rhs:

The second vector.

Returns: 

Positive integer (=true) if the elements in the lhs are all equal to the corresponding elements in rhs. Returns 0 (=false) if the lengths of the vectors don't match.

Time complexity: O(n), the length of the vectors.

2.9.2. igraph_vector_all_l — Are all elements less?

igraph_bool_t igraph_vector_all_l(const igraph_vector_t *lhs,
        const igraph_vector_t *rhs);

Arguments: 

lhs:

The first vector.

rhs:

The second vector.

Returns: 

Positive integer (=true) if the elements in the lhs are all less than the corresponding elements in rhs. Returns 0 (=false) if the lengths of the vectors don't match. If any element is NaN, it will return 0 (=false).

Time complexity: O(n), the length of the vectors.

2.9.3. igraph_vector_all_g — Are all elements greater?

igraph_bool_t igraph_vector_all_g(const igraph_vector_t *lhs,
        const igraph_vector_t *rhs);

Arguments: 

lhs:

The first vector.

rhs:

The second vector.

Returns: 

Positive integer (=true) if the elements in the lhs are all greater than the corresponding elements in rhs. Returns 0 (=false) if the lengths of the vectors don't match. If any element is NaN, it will return 0 (=false).

Time complexity: O(n), the length of the vectors.

2.9.4. igraph_vector_all_le — Are all elements less or equal?

igraph_bool_t
igraph_vector_all_le(const igraph_vector_t *lhs,
                                const igraph_vector_t *rhs);

Arguments: 

lhs:

The first vector.

rhs:

The second vector.

Returns: 

Positive integer (=true) if the elements in the lhs are all less than or equal to the corresponding elements in rhs. Returns 0 (=false) if the lengths of the vectors don't match. If any element is NaN, it will return 0 (=false).

Time complexity: O(n), the length of the vectors.

2.9.5. igraph_vector_all_ge — Are all elements greater or equal?

igraph_bool_t
igraph_vector_all_ge(const igraph_vector_t *lhs,
                                const igraph_vector_t *rhs);

Arguments: 

lhs:

The first vector.

rhs:

The second vector.

Returns: 

Positive integer (=true) if the elements in the lhs are all greater than or equal to the corresponding elements in rhs. Returns 0 (=false) if the lengths of the vectors don't match. If any element is NaN, it will return 0 (=false).

Time complexity: O(n), the length of the vectors.

2.9.6. igraph_vector_lex_cmp — Lexicographical comparison of two vectors.

int igraph_vector_lex_cmp(const void *lhs, const void *rhs);

If the elements of two vectors match but one is shorter, the shorter one comes first. Thus {1, 3} comes after {1, 2, 3}, but before {1, 3, 4}.

This function is typically used together with igraph_vector_ptr_sort().

Arguments: 

lhs:

Pointer to a pointer to the first vector (interpreted as an igraph_vector_t **).

rhs:

Pointer to a pointer to the second vector (interpreted as an igraph_vector_t **).

Returns: 

-1 if lhs is lexicographically smaller, 0 if lhs and rhs are equal, else 1.

See also: 

igraph_vector_colex_cmp() to compare vectors starting from the last element.

Time complexity: O(n), the number of elements in the smaller vector.

Example 7.2.  File examples/simple/igraph_vector_ptr_sort.c

#include <igraph.h>
#include <stdio.h>

int main() {
    igraph_t graph;
    igraph_vector_ptr_t cliques;
    igraph_integer_t i, n;

    /* Set a random seed to make the program deterministic */
    igraph_rng_seed(igraph_rng_default(), 31415);

    /* Create a random graph with a given number of vertices and edges */
    igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 15, 80, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

    /* Find all maximal cliques in the graph */
    igraph_vector_ptr_init(&cliques, 0);
    igraph_maximal_cliques(&graph, &cliques, -1, -1);

    /* Print the cliques in lexicographical order */
    printf("Maximal cliques in lexicographical order:\n");
    igraph_vector_ptr_sort(&cliques, igraph_vector_lex_cmp);
    n = igraph_vector_ptr_size(&cliques);
    for (i=0; i < n; ++i) {
        igraph_vector_print(VECTOR(cliques)[i]);
    }

    /* Print the cliques in colexicographical order */
    printf("\nMaximal cliques in colexicographical order:\n");
    igraph_vector_ptr_sort(&cliques, igraph_vector_colex_cmp);
    n = igraph_vector_ptr_size(&cliques);
    for (i=0; i < n; ++i) {
        igraph_vector_print(VECTOR(cliques)[i]);
    }

    /* Destroy data structures when we no longer need them */

    IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&cliques, igraph_vector_destroy);
    igraph_vector_ptr_destroy_all(&cliques);

    igraph_destroy(&graph);

    return 0;
}


2.9.7. igraph_vector_colex_cmp — Colexicographical comparison of two vectors.

int igraph_vector_colex_cmp(const void *lhs, const void *rhs);

This comparison starts from the last element of both vectors and moves backward. If the elements of two vectors match but one is shorter, the shorter one comes first. Thus {1, 2} comes after {3, 2, 1}, but before {0, 1, 2}.

This function is typically used together with igraph_vector_ptr_sort().

Arguments: 

lhs:

Pointer to a pointer to the first vector (interpreted as an igraph_vector_t **).

rhs:

Pointer to a pointer to the second vector (interpreted as an igraph_vector_t **).

Returns: 

-1 if lhs in reverse order is lexicographically smaller than the reverse of rhs, 0 if lhs and rhs are equal, else 1.

See also: 

igraph_vector_lex_cmp() to compare vectors starting from the first element.

Time complexity: O(n), the number of elements in the smaller vector.

Example 7.3.  File examples/simple/igraph_vector_ptr_sort.c

#include <igraph.h>
#include <stdio.h>

int main() {
    igraph_t graph;
    igraph_vector_ptr_t cliques;
    igraph_integer_t i, n;

    /* Set a random seed to make the program deterministic */
    igraph_rng_seed(igraph_rng_default(), 31415);

    /* Create a random graph with a given number of vertices and edges */
    igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 15, 80, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

    /* Find all maximal cliques in the graph */
    igraph_vector_ptr_init(&cliques, 0);
    igraph_maximal_cliques(&graph, &cliques, -1, -1);

    /* Print the cliques in lexicographical order */
    printf("Maximal cliques in lexicographical order:\n");
    igraph_vector_ptr_sort(&cliques, igraph_vector_lex_cmp);
    n = igraph_vector_ptr_size(&cliques);
    for (i=0; i < n; ++i) {
        igraph_vector_print(VECTOR(cliques)[i]);
    }

    /* Print the cliques in colexicographical order */
    printf("\nMaximal cliques in colexicographical order:\n");
    igraph_vector_ptr_sort(&cliques, igraph_vector_colex_cmp);
    n = igraph_vector_ptr_size(&cliques);
    for (i=0; i < n; ++i) {
        igraph_vector_print(VECTOR(cliques)[i]);
    }

    /* Destroy data structures when we no longer need them */

    IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&cliques, igraph_vector_destroy);
    igraph_vector_ptr_destroy_all(&cliques);

    igraph_destroy(&graph);

    return 0;
}


2.10. Finding minimum and maximum

2.10.1. igraph_vector_min — Smallest element of a vector.

igraph_real_t igraph_vector_min(const igraph_vector_t* v);

The vector must be non-empty.

Arguments: 

v:

The input vector.

Returns: 

The smallest element of v, or NaN if any element is NaN.

Time complexity: O(n), the number of elements.

2.10.2. igraph_vector_max — Largest element of a vector.

igraph_real_t igraph_vector_max(const igraph_vector_t* v);

If the size of the vector is zero, an arbitrary number is returned.

Arguments: 

v:

The vector object.

Returns: 

The maximum element of v, or NaN if any element is NaN.

Time complexity: O(n), the number of elements.

2.10.3. igraph_vector_which_min — Index of the smallest element.

igraph_integer_t igraph_vector_which_min(const igraph_vector_t* v);

The vector must be non-empty. If the smallest element is not unique, then the index of the first is returned. If the vector contains NaN values, the index of the first NaN value is returned.

Arguments: 

v:

The input vector.

Returns: 

Index of the smallest element.

Time complexity: O(n), the number of elements.

2.10.4. igraph_vector_which_max — Gives the index of the maximum element of the vector.

igraph_integer_t igraph_vector_which_max(const igraph_vector_t* v);

If the size of the vector is zero, -1 is returned. If the largest element is not unique, then the index of the first is returned. If the vector contains NaN values, the index of the first NaN value is returned.

Arguments: 

v:

The vector object.

Returns: 

The index of the first maximum element.

Time complexity: O(n), n is the size of the vector.

2.10.5. igraph_vector_minmax — Minimum and maximum elements of a vector.

igraph_error_t igraph_vector_minmax(const igraph_vector_t *v,
                                    igraph_real_t *min, igraph_real_t *max);

Handy if you want to have both the smallest and largest element of a vector. The vector is only traversed once. The vector must be non-empty. If a vector contains at least one NaN, both min and max will be NaN.

Arguments: 

v:

The input vector. It must contain at least one element.

min:

Pointer to a base type variable, the minimum is stored here.

max:

Pointer to a base type variable, the maximum is stored here.

Returns: 

Error code.

Time complexity: O(n), the number of elements.

2.10.6. igraph_vector_which_minmax — Index of the minimum and maximum elements

igraph_error_t igraph_vector_which_minmax(const igraph_vector_t *v,
        igraph_integer_t *which_min, igraph_integer_t *which_max);

Handy if you need the indices of the smallest and largest elements. The vector is traversed only once. The vector must be non-empty. If the minimum or maximum is not unique, the index of the first minimum or the first maximum is returned, respectively. If a vector contains at least one NaN, both which_min and which_max will point to the first NaN value.

Arguments: 

v:

The input vector. It must contain at least one element.

which_min:

The index of the minimum element will be stored here.

which_max:

The index of the maximum element will be stored here.

Returns: 

Error code.

Time complexity: O(n), the number of elements.

2.11. Vector properties

2.11.1. igraph_vector_empty — Decides whether the size of the vector is zero.

igraph_bool_t igraph_vector_empty(const igraph_vector_t* v);

Arguments: 

v:

The vector object.

Returns: 

Non-zero number (true) if the size of the vector is zero and zero (false) otherwise.

Time complexity: O(1).

2.11.2. igraph_vector_size — Returns the size (=length) of the vector.

igraph_integer_t igraph_vector_size(const igraph_vector_t* v);

Arguments: 

v:

The vector object

Returns: 

The size of the vector.

Time complexity: O(1).

2.11.3. igraph_vector_capacity — Returns the allocated capacity of the vector

igraph_integer_t igraph_vector_capacity(const igraph_vector_t*v);

Note that this might be different from the size of the vector (as queried by igraph_vector_size(), and specifies how many elements the vector can hold, without reallocation.

Arguments: 

v:

Pointer to the (previously initialized) vector object to query.

Returns: 

The allocated capacity.

See also: 

Time complexity: O(1).

2.11.4. igraph_vector_sum — Calculates the sum of the elements in the vector.

igraph_real_t igraph_vector_sum(const igraph_vector_t *v);

For the empty vector 0.0 is returned.

Arguments: 

v:

The vector object.

Returns: 

The sum of the elements.

Time complexity: O(n), the size of the vector.

2.11.5. igraph_vector_prod — Calculates the product of the elements in the vector.

igraph_real_t igraph_vector_prod(const igraph_vector_t *v);

For the empty vector one (1) is returned.

Arguments: 

v:

The vector object.

Returns: 

The product of the elements.

Time complexity: O(n), the size of the vector.

2.11.6. igraph_vector_isininterval — Checks if all elements of a vector are in the given

igraph_bool_t igraph_vector_isininterval(const igraph_vector_t *v,
        igraph_real_t low,
        igraph_real_t high);

interval.

Arguments: 

v:

The vector object.

low:

The lower limit of the interval (inclusive).

high:

The higher limit of the interval (inclusive).

Returns: 

True (positive integer) if the vector is empty or all vector elements are in the interval, false (zero) otherwise. If any element is NaN, it will return 0 (=false).

Time complexity: O(n), the number of elements in the vector.

2.11.7. igraph_vector_maxdifference — The maximum absolute difference of m1 and m2

igraph_real_t igraph_vector_maxdifference(const igraph_vector_t *m1,
        const igraph_vector_t *m2);

The element with the largest absolute value in m1 - m2 is returned. Both vectors must be non-empty, but they not need to have the same length, the extra elements in the longer vector are ignored. If any value is NaN in the shorter vector, the result will be NaN.

Arguments: 

m1:

The first vector.

m2:

The second vector.

Returns: 

The maximum absolute difference of m1 and m2.

Time complexity: O(n), the number of elements in the shorter vector.

2.11.8. igraph_vector_is_nan — Check for each element if it is NaN.

igraph_error_t igraph_vector_is_nan(const igraph_vector_t *v, igraph_vector_bool_t *is_nan);

Arguments: 

v:

The igraph_vector_t object to check.

is_nan:

The resulting boolean vector indicating for each element whether it is NaN or not.

Returns: 

Error code, IGRAPH_ENOMEM if there is not enough memory. Note that this function never returns an error if the vector is_nan will already be large enough. Time complexity: O(n), the number of elements.

2.11.9. igraph_vector_is_any_nan — Check if any element is NaN.

igraph_bool_t igraph_vector_is_any_nan(const igraph_vector_t *v);

Arguments: 

v:

The igraph_vector_t object to check.

Returns: 

1 if any element is NaN, 0 otherwise.

Time complexity: O(n), the number of elements.

2.12. Searching for elements

2.12.1. igraph_vector_contains — Linear search in a vector.

igraph_bool_t igraph_vector_contains(const igraph_vector_t *v,
        igraph_real_t e);

Check whether the supplied element is included in the vector, by linear search.

Arguments: 

v:

The input vector.

e:

The element to look for.

Returns: 

TRUE if the element is found and FALSE otherwise.

Time complexity: O(n), the length of the vector.

2.12.2. igraph_vector_search — Search from a given position

igraph_bool_t igraph_vector_search(const igraph_vector_t *v,
        igraph_integer_t from, igraph_real_t what, igraph_integer_t *pos);

The supplied element what is searched in vector v, starting from element index from. If found then the index of the first instance (after from) is stored in pos.

Arguments: 

v:

The input vector.

from:

The index to start searching from. No range checking is performed.

what:

The element to find.

pos:

If not NULL then the index of the found element is stored here.

Returns: 

Boolean, TRUE if the element was found, FALSE otherwise.

Time complexity: O(m), the number of elements to search, the length of the vector minus the from argument.

2.12.3. igraph_vector_binsearch — Finds an element by binary searching a sorted vector.

igraph_bool_t igraph_vector_binsearch(const igraph_vector_t *v,
        igraph_real_t what, igraph_integer_t *pos);

It is assumed that the vector is sorted. If the specified element (what) is not in the vector, then the position of where it should be inserted (to keep the vector sorted) is returned. If the vector contains any NaN values, the returned value is undefined and pos may point to any position.

Arguments: 

v:

The igraph_vector_t object.

what:

The element to search for.

pos:

Pointer to an igraph_integer_t. This is set to the position of an instance of what in the vector if it is present. If v does not contain what then pos is set to the position to which it should be inserted (to keep the the vector sorted of course).

Returns: 

Positive integer (true) if what is found in the vector, zero (false) otherwise.

Time complexity: O(log(n)), n is the number of elements in v.

2.12.4. igraph_vector_binsearch_slice — Finds an element by binary searching a sorted slice of a vector.

igraph_bool_t igraph_vector_binsearch_slice(const igraph_vector_t *v,
        igraph_real_t what, igraph_integer_t *pos, igraph_integer_t start, igraph_integer_t end);

It is assumed that the indicated slice of the vector, from start to end, is sorted. If the specified element (what) is not in the slice of the vector, then the position of where it should be inserted (to keep the vector sorted) is returned. If the indicated slice contains any NaN values, the returned value is undefined and pos may point to any position within the slice.

Arguments: 

v:

The igraph_vector_t object.

what:

The element to search for.

pos:

Pointer to an igraph_integer_t. This is set to the position of an instance of what in the slice of the vector if it is present. If v does not contain what then pos is set to the position to which it should be inserted (to keep the the vector sorted).

start:

The start position of the slice to search (inclusive).

end:

The end position of the slice to search (exclusive).

Returns: 

Positive integer (true) if what is found in the vector, zero (false) otherwise.

Time complexity: O(log(n)), n is the number of elements in the slice of v, i.e. end - start.

2.12.5. igraph_vector_binsearch2 — Binary search, without returning the index.

igraph_bool_t igraph_vector_binsearch2(const igraph_vector_t *v,
        igraph_real_t what);

It is assumed that the vector is sorted.

Arguments: 

v:

The igraph_vector_t object.

what:

The element to search for.

Returns: 

Positive integer (true) if what is found in the vector, zero (false) otherwise.

Time complexity: O(log(n)), n is the number of elements in v.

2.13. Resizing operations

2.13.1. igraph_vector_clear — Removes all elements from a vector.

void igraph_vector_clear(igraph_vector_t* v);

This function simply sets the size of the vector to zero, it does not free any allocated memory. For that you have to call igraph_vector_destroy().

Arguments: 

v:

The vector object.

Time complexity: O(1).

2.13.2. igraph_vector_reserve — Reserves memory for a vector.

igraph_error_t igraph_vector_reserve(igraph_vector_t* v, igraph_integer_t size);

igraph vectors are flexible, they can grow and shrink. Growing however occasionally needs the data in the vector to be copied. In order to avoid this, you can call this function to reserve space for future growth of the vector.

Note that this function does not change the size of the vector. Let us see a small example to clarify things: if you reserve space for 100 elements and the size of your vector was (and still is) 60, then you can surely add additional 40 elements to your vector before it will be copied.

Arguments: 

v:

The vector object.

size:

The new allocated size of the vector.

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

Time complexity: operating system dependent, should be around O(n), n is the new allocated size of the vector.

2.13.3. igraph_vector_resize — Resize the vector.

igraph_error_t igraph_vector_resize(igraph_vector_t* v, igraph_integer_t newsize);

Note that this function does not free any memory, just sets the size of the vector to the given one. It can on the other hand allocate more memory if the new size is larger than the previous one. In this case the newly appeared elements in the vector are not set to zero, they are uninitialized.

Arguments: 

v:

The vector object

newsize:

The new size of the vector.

Returns: 

Error code, IGRAPH_ENOMEM if there is not enough memory. Note that this function never returns an error if the vector is made smaller.

See also: 

igraph_vector_reserve() for allocating memory for future extensions of a vector. igraph_vector_resize_min() for deallocating the unnneded memory for a vector.

Time complexity: O(1) if the new size is smaller, operating system dependent if it is larger. In the latter case it is usually around O(n), n is the new size of the vector.

2.13.4. igraph_vector_resize_min — Deallocate the unused memory of a vector.

igraph_error_t igraph_vector_resize_min(igraph_vector_t*v);

Note that this function involves additional memory allocation and may result an out-of-memory error.

Arguments: 

v:

Pointer to an initialized vector.

Returns: 

Error code.

See also: 

Time complexity: operating system dependent.

2.13.5. igraph_vector_push_back — Appends one element to a vector.

igraph_error_t igraph_vector_push_back(igraph_vector_t* v, igraph_real_t e);

This function resizes the vector to be one element longer and sets the very last element in the vector to e.

Arguments: 

v:

The vector object.

e:

The element to append to the vector.

Returns: 

Error code: IGRAPH_ENOMEM: not enough memory.

Time complexity: operating system dependent. What is important is that a sequence of n subsequent calls to this function has time complexity O(n), even if there hadn't been any space reserved for the new elements by igraph_vector_reserve(). This is implemented by a trick similar to the C++ vector class: each time more memory is allocated for a vector, the size of the additionally allocated memory is the same as the vector's current length. (We assume here that the time complexity of memory allocation is at most linear.)

2.13.6. igraph_vector_pop_back — Removes and returns the last element of a vector.

igraph_real_t igraph_vector_pop_back(igraph_vector_t* v);

It is an error to call this function with an empty vector.

Arguments: 

v:

The vector object.

Returns: 

The removed last element.

Time complexity: O(1).

2.13.7. igraph_vector_insert — Inserts a single element into a vector.

igraph_error_t igraph_vector_insert(
        igraph_vector_t *v, igraph_integer_t pos, igraph_real_t value);

Note that this function does not do range checking. Insertion will shift the elements from the position given to the end of the vector one position to the right, and the new element will be inserted in the empty space created at the given position. The size of the vector will increase by one.

Arguments: 

v:

The vector object.

pos:

The position where the new element is to be inserted.

value:

The new element to be inserted.

2.13.8. igraph_vector_remove — Removes a single element from a vector.

void igraph_vector_remove(igraph_vector_t *v, igraph_integer_t elem);

Note that this function does not do range checking.

Arguments: 

v:

The vector object.

elem:

The position of the element to remove.

Time complexity: O(n-elem), n is the number of elements in the vector.

2.13.9. igraph_vector_remove_section — Deletes a section from a vector.

void igraph_vector_remove_section(
        igraph_vector_t *v, igraph_integer_t from, igraph_integer_t to);

Note that this function does not do range checking. The result is undefined if you supply invalid limits.

Arguments: 

v:

The vector object.

from:

The position of the first element to remove.

to:

The position of the first element not to remove.

Time complexity: O(n-from), n is the number of elements in the vector.

2.14. Sorting

2.14.1. igraph_vector_sort — Sorts the elements of the vector into ascending order.

void igraph_vector_sort(igraph_vector_t *v);

If the vector contains any NaN values, the resulting ordering of NaN values is undefined and may appear anywhere in the vector.

Arguments: 

v:

Pointer to an initialized vector object.

Time complexity: O(n log n) for n elements.

2.14.2. igraph_vector_reverse_sort — Sorts the elements of the vector into descending order.

void igraph_vector_reverse_sort(igraph_vector_t *v);

If the vector contains any NaN values, the resulting ordering of NaN values is undefined and may appear anywhere in the vector.

Arguments: 

v:

Pointer to an initialized vector object.

Time complexity: O(n log n) for n elements.

2.14.3. igraph_vector_qsort_ind — Return a permutation of indices that sorts a vector

igraph_error_t igraph_vector_qsort_ind(igraph_vector_t *v,
        igraph_vector_int_t *inds, igraph_bool_t descending);

Takes an unsorted array v as input and computes an array of indices inds such that v[ inds[i] ], with i increasing from 0, is an ordered array (either ascending or descending, depending on \v order). The order of indices for identical elements is not defined. If the vector contains any NaN values, the ordering of NaN values is undefined.

Arguments: 

v:

the array to be sorted

inds:

the output array of indices. This must be initialized, but will be resized

descending:

whether the output array should be sorted in descending order.

Returns: 

Error code.

This routine uses igraph's built-in qsort routine. Algorithm: 1) create an array of pointers to the elements of v. 2) Pass this array to qsort. 3) after sorting the difference between the pointer value and the first pointer value gives its original position in the array. Use this to set the values of inds.

2.15. Set operations on sorted vectors

2.15.1. igraph_vector_intersect_sorted — Calculates the intersection of two sorted vectors

igraph_error_t igraph_vector_intersect_sorted(const igraph_vector_t *v1,
        const igraph_vector_t *v2, igraph_vector_t *result);

The elements that are contained in both vectors are stored in the result vector. All three vectors must be initialized.

Instead of the naive intersection which takes O(n), this function uses the set intersection method of Ricardo Baeza-Yates, which is more efficient when one of the vectors is significantly smaller than the other, and gives similar performance on average when the two vectors are equal.

The algorithm keeps the multiplicities of the elements: if an element appears k1 times in the first vector and k2 times in the second, the result will include that element min(k1, k2) times.

Reference: Baeza-Yates R: A fast set intersection algorithm for sorted sequences. In: Lecture Notes in Computer Science, vol. 3109/2004, pp. 400--408, 2004. Springer Berlin/Heidelberg. ISBN: 978-3-540-22341-2.

Arguments: 

v1:

the first vector

v2:

the second vector

result:

the result vector, which will also be sorted.

Time complexity: O(m log(n)) where m is the size of the smaller vector and n is the size of the larger one.

2.15.2. igraph_vector_difference_sorted — Calculates the difference between two sorted vectors (considered as sets)

igraph_error_t igraph_vector_difference_sorted(const igraph_vector_t *v1,
        const igraph_vector_t *v2, igraph_vector_t *result);

The elements that are contained in only the first vector but not the second are stored in the result vector. All three vectors must be initialized.

Arguments: 

v1:

the first vector

v2:

the second vector

result:

the result vector

2.16.  Pointer vectors (igraph_vector_ptr_t)

2.16.1. igraph_vector_ptr_init — Initialize a pointer vector (constructor).
2.16.2. igraph_vector_ptr_copy — Copy a pointer vector (constructor).
2.16.3. igraph_vector_ptr_destroy — Destroys a pointer vector.
2.16.4. igraph_vector_ptr_free_all — Frees all the elements of a pointer vector.
2.16.5. igraph_vector_ptr_destroy_all — Frees all the elements and destroys the pointer vector.
2.16.6. igraph_vector_ptr_size — Gives the number of elements in the pointer vector.
2.16.7. igraph_vector_ptr_clear — Removes all elements from a pointer vector.
2.16.8. igraph_vector_ptr_push_back — Appends an element to the back of a pointer vector.
2.16.9. igraph_vector_ptr_insert — Inserts a single element into a pointer vector.
2.16.10. igraph_vector_ptr_e — Access an element of a pointer vector.
2.16.11. igraph_vector_ptr_set — Assign to an element of a pointer vector.
2.16.12. igraph_vector_ptr_resize — Resizes a pointer vector.
2.16.13. igraph_vector_ptr_sort — Sorts the pointer vector based on an external comparison function.
2.16.14. igraph_vector_ptr_sort_ind — Return a permutation of indices that sorts a vector of pointers
2.16.15. igraph_vector_ptr_permute — Permutes the elements of a pointer vector in place according to an index vector.
2.16.16. igraph_vector_ptr_get_item_destructor — Gets the current item destructor for this pointer vector.
2.16.17. igraph_vector_ptr_set_item_destructor — Sets the item destructor for this pointer vector.
2.16.18. IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR — Sets the item destructor for this pointer vector (macro version).

The igraph_vector_ptr_t data type is very similar to the igraph_vector_t type, but it stores generic pointers instead of real numbers.

This type has the same space complexity as igraph_vector_t, and most implemented operations work the same way as for igraph_vector_t.

This type is mostly used to pass to or receive from a set of graphs to some igraph functions, such as igraph_decompose(), which decomposes a graph to connected components.

The same VECTOR macro used for ordinary vectors can be used for pointer vectors as well, please note that a typeless generic pointer will be provided by this macro and you may need to cast it to a specific pointer before starting to work with it.

Pointer vectors may have an associated item destructor function which takes a pointer and returns nothing. The item destructor will be called on each item in the pointer vector when it is destroyed by igraph_vector_ptr_destroy() or igraph_vector_ptr_destroy_all(), or when its elements are freed by igraph_vector_ptr_free_all(). Note that the semantics of an item destructor does not coincide with C++ destructors; for instance, when a pointer vector is resized to a smaller size, the extra items will not be destroyed automatically! Nevertheless, item destructors may become handy in many cases; for instance, a vector of graphs generated by igraph_decompose() can be destroyed with a single call to igraph_vector_ptr_destroy_all() if the item destructor is set to igraph_destroy().

2.16.1. igraph_vector_ptr_init — Initialize a pointer vector (constructor).

igraph_error_t igraph_vector_ptr_init(igraph_vector_ptr_t* v, igraph_integer_t size);

This is the constructor of the pointer vector data type. All pointer vectors constructed this way should be destroyed via calling igraph_vector_ptr_destroy().

Arguments: 

v:

Pointer to an uninitialized igraph_vector_ptr_t object, to be created.

size:

Integer, the size of the pointer vector.

Returns: 

Error code: IGRAPH_ENOMEM if out of memory

Time complexity: operating system dependent, the amount of time required to allocate size elements.

2.16.2. igraph_vector_ptr_copy — Copy a pointer vector (constructor).

igraph_error_t igraph_vector_ptr_copy(igraph_vector_ptr_t *to, const igraph_vector_ptr_t *from);

This function creates a pointer vector by copying another one. This is shallow copy, only the pointers in the vector will be copied.

It is potentially dangerous to copy a pointer vector with an associated item destructor. The copied vector will inherit the item destructor, which may cause problems when both vectors are destroyed as the items might get destroyed twice. Make sure you know what you are doing when copying a pointer vector with an item destructor, or unset the item destructor on one of the vectors later.

Arguments: 

to:

Pointer to an uninitialized pointer vector object.

from:

A pointer vector object.

Returns: 

Error code: IGRAPH_ENOMEM if out of memory

Time complexity: O(n) if allocating memory for n elements can be done in O(n) time.

2.16.3. igraph_vector_ptr_destroy — Destroys a pointer vector.

void igraph_vector_ptr_destroy(igraph_vector_ptr_t* v);

The destructor for pointer vectors.

Arguments: 

v:

Pointer to the pointer vector to destroy.

Time complexity: operating system dependent, the time required to deallocate O(n) bytes, n is the number of elements allocated for the pointer vector (not necessarily the number of elements in the vector).

2.16.4. igraph_vector_ptr_free_all — Frees all the elements of a pointer vector.

void igraph_vector_ptr_free_all(igraph_vector_ptr_t* v);

If an item destructor is set for this pointer vector, this function will first call the destructor on all elements of the vector and then free all the elements using igraph_free(). If an item destructor is not set, the elements will simply be freed.

Arguments: 

v:

Pointer to the pointer vector whose elements will be freed.

Time complexity: operating system dependent, the time required to call the destructor n times and then deallocate O(n) pointers, each pointing to a memory area of arbitrary size. n is the number of elements in the pointer vector.

2.16.5. igraph_vector_ptr_destroy_all — Frees all the elements and destroys the pointer vector.

void igraph_vector_ptr_destroy_all(igraph_vector_ptr_t* v);

This function is equivalent to igraph_vector_ptr_free_all() followed by igraph_vector_ptr_destroy().

Arguments: 

v:

Pointer to the pointer vector to destroy.

Time complexity: operating system dependent, the time required to deallocate O(n) pointers, each pointing to a memory area of arbitrary size, plus the time required to deallocate O(n) bytes, n being the number of elements allocated for the pointer vector (not necessarily the number of elements in the vector).

2.16.6. igraph_vector_ptr_size — Gives the number of elements in the pointer vector.

igraph_integer_t igraph_vector_ptr_size(const igraph_vector_ptr_t* v);

Arguments: 

v:

The pointer vector object.

Returns: 

The size of the object, i.e. the number of pointers stored.

Time complexity: O(1).

2.16.7. igraph_vector_ptr_clear — Removes all elements from a pointer vector.

void igraph_vector_ptr_clear(igraph_vector_ptr_t* v);

This function resizes a pointer to vector to zero length. Note that the pointed objects are not deallocated, you should call igraph_free() on them, or make sure that their allocated memory is freed in some other way, you'll get memory leaks otherwise. If you have set up an item destructor earlier, the destructor will be called on every element.

Note that the current implementation of this function does not deallocate the memory required for storing the pointers, so making a pointer vector smaller this way does not give back any memory. This behavior might change in the future.

Arguments: 

v:

The pointer vector to clear.

Time complexity: O(1).

2.16.8. igraph_vector_ptr_push_back — Appends an element to the back of a pointer vector.

igraph_error_t igraph_vector_ptr_push_back(igraph_vector_ptr_t* v, void* e);

Arguments: 

v:

The pointer vector.

e:

The new element to include in the pointer vector.

Returns: 

Error code.

See also: 

igraph_vector_push_back() for the corresponding operation of the ordinary vector type.

Time complexity: O(1) or O(n), n is the number of elements in the vector. The pointer vector implementation ensures that n subsequent push_back operations need O(n) time to complete.

2.16.9. igraph_vector_ptr_insert — Inserts a single element into a pointer vector.

igraph_error_t igraph_vector_ptr_insert(igraph_vector_ptr_t* v, igraph_integer_t pos, void* e);

Note that this function does not do range checking. Insertion will shift the elements from the position given to the end of the vector one position to the right, and the new element will be inserted in the empty space created at the given position. The size of the vector will increase by one.

Arguments: 

v:

The pointer vector object.

pos:

The position where the new element is inserted.

e:

The inserted element

2.16.10. igraph_vector_ptr_e — Access an element of a pointer vector.

void *igraph_vector_ptr_e(const igraph_vector_ptr_t* v, igraph_integer_t pos);

Arguments: 

v:

Pointer to a pointer vector.

pos:

The index of the pointer to return.

Returns: 

The pointer at pos position.

Time complexity: O(1).

2.16.11. igraph_vector_ptr_set — Assign to an element of a pointer vector.

void igraph_vector_ptr_set(igraph_vector_ptr_t* v, igraph_integer_t pos, void* value);

Arguments: 

v:

Pointer to a pointer vector.

pos:

The index of the pointer to update.

value:

The new pointer to set in the vector.

Time complexity: O(1).

2.16.12. igraph_vector_ptr_resize — Resizes a pointer vector.

igraph_error_t igraph_vector_ptr_resize(igraph_vector_ptr_t* v, igraph_integer_t newsize);

Note that if a vector is made smaller the pointed object are not deallocated by this function and the item destructor is not called on the extra elements.

Arguments: 

v:

A pointer vector.

newsize:

The new size of the pointer vector.

Returns: 

Error code.

Time complexity: O(1) if the vector if made smaller. Operating system dependent otherwise, the amount of time needed to allocate the memory for the vector elements.

2.16.13. igraph_vector_ptr_sort — Sorts the pointer vector based on an external comparison function.

void igraph_vector_ptr_sort(igraph_vector_ptr_t *v, int (*compar)(const void*, const void*));

Sometimes it is necessary to sort the pointers in the vector based on the property of the element being referenced by the pointer. This function allows us to sort the vector based on an arbitrary external comparison function which accepts two void * pointers p1 and p2 and returns an integer less than, equal to or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second. p1 and p2 will point to the pointer in the vector, so they have to be double-dereferenced if one wants to get access to the underlying object the address of which is stored in v.

Arguments: 

v:

The pointer vector to be sorted.

compar:

A qsort-compatible comparison function. It must take pointers to the elements of the pointer vector. For example, if the pointer vector contains igraph_vector_t * pointers, then the comparison function must interpret its arguments as igraph_vector_t **.

Example 7.4.  File examples/simple/igraph_vector_ptr_sort.c

#include <igraph.h>
#include <stdio.h>

int main() {
    igraph_t graph;
    igraph_vector_ptr_t cliques;
    igraph_integer_t i, n;

    /* Set a random seed to make the program deterministic */
    igraph_rng_seed(igraph_rng_default(), 31415);

    /* Create a random graph with a given number of vertices and edges */
    igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 15, 80, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

    /* Find all maximal cliques in the graph */
    igraph_vector_ptr_init(&cliques, 0);
    igraph_maximal_cliques(&graph, &cliques, -1, -1);

    /* Print the cliques in lexicographical order */
    printf("Maximal cliques in lexicographical order:\n");
    igraph_vector_ptr_sort(&cliques, igraph_vector_lex_cmp);
    n = igraph_vector_ptr_size(&cliques);
    for (i=0; i < n; ++i) {
        igraph_vector_print(VECTOR(cliques)[i]);
    }

    /* Print the cliques in colexicographical order */
    printf("\nMaximal cliques in colexicographical order:\n");
    igraph_vector_ptr_sort(&cliques, igraph_vector_colex_cmp);
    n = igraph_vector_ptr_size(&cliques);
    for (i=0; i < n; ++i) {
        igraph_vector_print(VECTOR(cliques)[i]);
    }

    /* Destroy data structures when we no longer need them */

    IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&cliques, igraph_vector_destroy);
    igraph_vector_ptr_destroy_all(&cliques);

    igraph_destroy(&graph);

    return 0;
}


2.16.14. igraph_vector_ptr_sort_ind — Return a permutation of indices that sorts a vector of pointers

igraph_error_t igraph_vector_ptr_sort_ind(igraph_vector_ptr_t *v,
        igraph_vector_int_t *inds, cmp_t cmp);

Takes an unsorted array v as input and computes an array of indices inds such that v[ inds[i] ], with i increasing from 0, is an ordered array (either ascending or descending, depending on \v order). The order of indices for identical elements is not defined.

Arguments: 

v:

the array to be sorted

inds:

the output array of indices. This must be initialized, but will be resized

cmp:

a comparator function that takes two elements of the pointer vector being sorted (these are constant pointers on their own) and returns a negative value if the item "pointed to" by the first pointer is smaller than the item "pointed to" by the second pointer, a positive value if it is larger, or zero if the two items are equal

Returns: 

Error code.

This routine uses the C library qsort routine. Algorithm: 1) create an array of pointers to the elements of v. 2) Pass this array to qsort. 3) after sorting the difference between the pointer value and the first pointer value gives its original position in the array. Use this to set the values of inds.

2.16.15. igraph_vector_ptr_permute — Permutes the elements of a pointer vector in place according to an index vector.

igraph_error_t igraph_vector_ptr_permute(igraph_vector_ptr_t* v, const igraph_vector_int_t* index);

This function takes a vector v and a corresponding index vector ind, and permutes the elements of v such that v[ind[i]] is moved to become v[i] after the function is executed.

It is an error to call this function with an index vector that does not represent a valid permutation. Each element in the index vector must be between 0 and the length of the vector minus one (inclusive), and each such element must appear only once. The function does not attempt to validate the index vector.

The index vector that this function takes is compatible with the index vector returned from igraph_vector_ptr_sort_ind(); passing in the index vector from igraph_vector_ptr_sort_ind() will sort the original vector.

As a special case, this function allows the index vector to be shorter than the vector being permuted, in which case the elements whose indices do not occur in the index vector will be removed from the vector.

Arguments: 

v:

the vector to permute

ind:

the index vector

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

Time complexity: O(n), the size of the vector.

2.16.16. igraph_vector_ptr_get_item_destructor — Gets the current item destructor for this pointer vector.

igraph_finally_func_t* igraph_vector_ptr_get_item_destructor(const igraph_vector_ptr_t *v);

The item destructor is a function which will be called on every non-null pointer stored in this vector when igraph_vector_ptr_destroy(), igraph_vector_ptr_destroy_all() or igraph_vector_ptr_free_all() is called.

Returns: 

The current item destructor.

Time complexity: O(1).

2.16.17. igraph_vector_ptr_set_item_destructor — Sets the item destructor for this pointer vector.

igraph_finally_func_t* igraph_vector_ptr_set_item_destructor(
    igraph_vector_ptr_t *v, igraph_finally_func_t *func);

The item destructor is a function which will be called on every non-null pointer stored in this vector when igraph_vector_ptr_destroy(), igraph_vector_ptr_destroy_all() or igraph_vector_ptr_free_all() is called.

Returns: 

The old item destructor.

Time complexity: O(1).

2.16.18. IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR — Sets the item destructor for this pointer vector (macro version).

#define IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(v, func)

This macro is expanded to igraph_vector_ptr_set_item_destructor(), the only difference is that the second argument is automatically cast to an igraph_finally_func_t*. The cast is necessary in most cases as the destructor functions we use (such as igraph_vector_destroy()) take a pointer to some concrete igraph data type, while igraph_finally_func_t expects void*

3. Matrices

3.1.  About igraph_matrix_t objects

This type is just an interface to igraph_vector_t.

The igraph_matrix_t type usually stores n elements in O(n) space, but not always. See the documentation of the vector type.

3.2.  Matrix constructors and destructors

3.2.1. igraph_matrix_init — Initializes a matrix.

igraph_error_t igraph_matrix_init(
        igraph_matrix_t *m, igraph_integer_t nrow, igraph_integer_t ncol);

Every matrix needs to be initialized before using it. This is done by calling this function. A matrix has to be destroyed if it is not needed any more; see igraph_matrix_destroy().

Arguments: 

m:

Pointer to a not yet initialized matrix object to be initialized.

nrow:

The number of rows in the matrix.

ncol:

The number of columns in the matrix.

Returns: 

Error code.

Time complexity: usually O(n), n is the number of elements in the matrix.

3.2.2. igraph_matrix_copy — Copies a matrix.

igraph_error_t igraph_matrix_copy(igraph_matrix_t *to, const igraph_matrix_t *from);

Creates a matrix object by copying from an existing matrix.

Arguments: 

to:

Pointer to an uninitialized matrix object.

from:

The initialized matrix object to copy.

Returns: 

Error code, IGRAPH_ENOMEM if there isn't enough memory to allocate the new matrix.

Time complexity: O(n), the number of elements in the matrix.

3.2.3. igraph_matrix_destroy — Destroys a matrix object.

void igraph_matrix_destroy(igraph_matrix_t *m);

This function frees all the memory allocated for a matrix object. The destroyed object needs to be reinitialized before using it again.

Arguments: 

m:

The matrix to destroy.

Time complexity: operating system dependent.

3.3. Initializing elements

3.3.1. igraph_matrix_null — Sets all elements in a matrix to zero.

void igraph_matrix_null(igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Time complexity: O(n), n is the number of elements in the matrix.

3.3.2. igraph_matrix_fill — Fill with an element.

void igraph_matrix_fill(igraph_matrix_t *m, igraph_real_t e);

Set the matrix to a constant matrix.

Arguments: 

m:

The input matrix.

e:

The element to set.

Time complexity: O(mn), the number of elements.

3.4. Copying matrices

3.4.1. igraph_matrix_copy_to — Copies a matrix to a regular C array.

void igraph_matrix_copy_to(const igraph_matrix_t *m, igraph_real_t *to);

The matrix is copied columnwise, as this is the format most programs and languages use. The C array should be of sufficient size; there are (of course) no range checks.

Arguments: 

m:

Pointer to an initialized matrix object.

to:

Pointer to a C array; the place to copy the data to.

Returns: 

Error code.

Time complexity: O(n), n is the number of elements in the matrix.

3.4.2. igraph_matrix_update — Update from another matrix.

igraph_error_t igraph_matrix_update(igraph_matrix_t *to,
                                    const igraph_matrix_t *from);

This function replicates from in the matrix to. Note that to must be already initialized.

Arguments: 

to:

The result matrix.

from:

The matrix to replicate; it is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.4.3. igraph_matrix_swap — Swap two matrices.

igraph_error_t igraph_matrix_swap(igraph_matrix_t *m1, igraph_matrix_t *m2);

The contents of the two matrices will be swapped. They must have the same dimensions.

Arguments: 

m1:

The first matrix.

m2:

The second matrix.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the matrices.

3.5.  Accessing elements of a matrix

3.5.1. MATRIX — Accessing an element of a matrix.

#define MATRIX(m,i,j)

Note that there are no range checks right now. This functionality might be redefined as a proper function later.

Arguments: 

m:

The matrix object.

i:

The index of the row, starting with zero.

j:

The index of the column, starting with zero.

Time complexity: O(1).

3.5.2. igraph_matrix_e — Extract an element from a matrix.

igraph_real_t igraph_matrix_e(const igraph_matrix_t *m,
                                igraph_integer_t row, igraph_integer_t col);

Use this if you need a function for some reason and cannot use the MATRIX macro. Note that no range checking is performed.

Arguments: 

m:

The input matrix.

row:

The row index.

col:

The column index.

Returns: 

The element in the given row and column.

Time complexity: O(1).

3.5.3. igraph_matrix_e_ptr — Pointer to an element of a matrix.

igraph_real_t* igraph_matrix_e_ptr(const igraph_matrix_t *m,
                                     igraph_integer_t row, igraph_integer_t col);

The function returns a pointer to an element. No range checking is performed.

Arguments: 

m:

The input matrix.

row:

The row index.

col:

The column index.

Returns: 

Pointer to the element in the given row and column.

Time complexity: O(1).

3.5.4. igraph_matrix_set — Set an element.

void igraph_matrix_set(
        igraph_matrix_t* m, igraph_integer_t row, igraph_integer_t col,
        igraph_real_t value);

Set an element of a matrix. No range checking is performed.

Arguments: 

m:

The input matrix.

row:

The row index.

col:

The column index.

value:

The new value of the element.

Time complexity: O(1).

3.6. Operations on rows and columns

3.6.1. igraph_matrix_get_row — Extract a row.

igraph_error_t igraph_matrix_get_row(const igraph_matrix_t *m,
                                     igraph_vector_t *res, igraph_integer_t index);

Extract a row from a matrix and return it as a vector.

Arguments: 

m:

The input matrix.

res:

Pointer to an initialized vector; it will be resized if needed.

index:

The index of the row to select.

Returns: 

Error code.

Time complexity: O(n), the number of columns in the matrix.

3.6.2. igraph_matrix_get_col — Select a column.

igraph_error_t igraph_matrix_get_col(const igraph_matrix_t *m,
                                     igraph_vector_t *res,
                                     igraph_integer_t index);

Extract a column of a matrix and return it as a vector.

Arguments: 

m:

The input matrix.

res:

The result will we stored in this vector. It should be initialized and will be resized as needed.

index:

The index of the column to select.

Returns: 

Error code.

Time complexity: O(n), the number of rows in the matrix.

3.6.3. igraph_matrix_set_row — Set a row from a vector.

igraph_error_t igraph_matrix_set_row(igraph_matrix_t *m,
                                     const igraph_vector_t *v, igraph_integer_t index);

Sets the elements of a row with the given vector. This has the effect of setting row index to have the elements in the vector v. The length of the vector and the number of columns in the matrix must match, otherwise an error is triggered.

Arguments: 

m:

The input matrix.

v:

The vector containing the new elements of the row.

index:

Index of the row to set.

Returns: 

Error code.

Time complexity: O(n), the number of columns in the matrix.

3.6.4. igraph_matrix_set_col — Set a column from a vector.

igraph_error_t igraph_matrix_set_col(igraph_matrix_t *m,
                                     const igraph_vector_t *v, igraph_integer_t index);

Sets the elements of a column with the given vector. In effect, column index will be set with elements from the vector v. The length of the vector and the number of rows in the matrix must match, otherwise an error is triggered.

Arguments: 

m:

The input matrix.

v:

The vector containing the new elements of the column.

index:

Index of the column to set.

Returns: 

Error code.

Time complexity: O(m), the number of rows in the matrix.

3.6.5. igraph_matrix_swap_rows — Swap two rows.

igraph_error_t igraph_matrix_swap_rows(igraph_matrix_t *m,
                                       igraph_integer_t i, igraph_integer_t j);

Swap two rows in the matrix.

Arguments: 

m:

The input matrix.

i:

The index of the first row.

j:

The index of the second row.

Returns: 

Error code.

Time complexity: O(n), the number of columns.

3.6.6. igraph_matrix_swap_cols — Swap two columns.

igraph_error_t igraph_matrix_swap_cols(igraph_matrix_t *m,
                                       igraph_integer_t i, igraph_integer_t j);

Swap two columns in the matrix.

Arguments: 

m:

The input matrix.

i:

The index of the first column.

j:

The index of the second column.

Returns: 

Error code.

Time complexity: O(m), the number of rows.

3.6.7. igraph_matrix_select_rows — Select some rows of a matrix.

igraph_error_t igraph_matrix_select_rows(const igraph_matrix_t *m,
        igraph_matrix_t *res,
        const igraph_vector_int_t *rows);

This function selects some rows of a matrix and returns them in a new matrix. The result matrix should be initialized before calling the function.

Arguments: 

m:

The input matrix.

res:

The result matrix. It should be initialized and will be resized as needed.

rows:

Vector; it contains the row indices (starting with zero) to extract. Note that no range checking is performed.

Returns: 

Error code.

Time complexity: O(nm), n is the number of rows, m the number of columns of the result matrix.

3.6.8. igraph_matrix_select_cols — Select some columns of a matrix.

igraph_error_t igraph_matrix_select_cols(const igraph_matrix_t *m,
        igraph_matrix_t *res,
        const igraph_vector_int_t *cols);

This function selects some columns of a matrix and returns them in a new matrix. The result matrix should be initialized before calling the function.

Arguments: 

m:

The input matrix.

res:

The result matrix. It should be initialized and will be resized as needed.

cols:

Vector; it contains the column indices (starting with zero) to extract. Note that no range checking is performed.

Returns: 

Error code.

Time complexity: O(nm), n is the number of rows, m the number of columns of the result matrix.

3.6.9. igraph_matrix_select_rows_cols — Select some rows and columns of a matrix.

igraph_error_t igraph_matrix_select_rows_cols(const igraph_matrix_t *m,
        igraph_matrix_t *res,
        const igraph_vector_int_t *rows,
        const igraph_vector_int_t *cols);

This function selects some rows and columns of a matrix and returns them in a new matrix. The result matrix should be initialized before calling the function.

Arguments: 

m:

The input matrix.

res:

The result matrix. It should be initialized and will be resized as needed.

rows:

Vector; it contains the row indices (starting with zero) to extract. Note that no range checking is performed.

cols:

Vector; it contains the column indices (starting with zero) to extract. Note that no range checking is performed.

Returns: 

Error code.

Time complexity: O(nm), n is the number of rows, m the number of columns of the result matrix.

3.7. Matrix operations

3.7.1. igraph_matrix_add_constant — Add a constant to every element.

void igraph_matrix_add_constant(igraph_matrix_t *m, igraph_real_t plus);

Arguments: 

m:

The input matrix.

plud:

The constant to add.

Time complexity: O(mn), the number of elements.

3.7.2. igraph_matrix_scale — Multiplies each element of the matrix by a constant.

void igraph_matrix_scale(igraph_matrix_t *m, igraph_real_t by);

Arguments: 

m:

The matrix.

by:

The constant.

Added in version 0.2.

Time complexity: O(n), the number of elements in the matrix.

3.7.3. igraph_matrix_add — Add two matrices.

igraph_error_t igraph_matrix_add(igraph_matrix_t *m1,
                                 const igraph_matrix_t *m2);

Add m2 to m1, and store the result in m1. The dimensions of the matrices must match.

Arguments: 

m1:

The first matrix; the result will be stored here.

m2:

The second matrix; it is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.7.4. igraph_matrix_sub — Difference of two matrices.

igraph_error_t igraph_matrix_sub(igraph_matrix_t *m1,
                                 const igraph_matrix_t *m2);

Subtract m2 from m1 and store the result in m1. The dimensions of the two matrices must match.

Arguments: 

m1:

The first matrix; the result is stored here.

m2:

The second matrix; it is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.7.5. igraph_matrix_mul_elements — Elementwise multiplication.

igraph_error_t igraph_matrix_mul_elements(igraph_matrix_t *m1,
        const igraph_matrix_t *m2);

Multiply m1 by m2 elementwise and store the result in m1. The dimensions of the two matrices must match.

Arguments: 

m1:

The first matrix; the result is stored here.

m2:

The second matrix; it is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.7.6. igraph_matrix_div_elements — Elementwise division.

igraph_error_t igraph_matrix_div_elements(igraph_matrix_t *m1,
        const igraph_matrix_t *m2);

Divide m1 by m2 elementwise and store the result in m1. The dimensions of the two matrices must match.

Arguments: 

m1:

The dividend. The result is store here.

m2:

The divisor. It is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.7.7. igraph_matrix_sum — Sum of elements.

igraph_real_t igraph_matrix_sum(const igraph_matrix_t *m);

Returns the sum of the elements of a matrix.

Arguments: 

m:

The input matrix.

Returns: 

The sum of the elements.

Time complexity: O(mn), the number of elements in the matrix.

3.7.8. igraph_matrix_prod — Product of the elements.

igraph_real_t igraph_matrix_prod(const igraph_matrix_t *m);

Note this function can result in overflow easily, even for not too big matrices.

Arguments: 

m:

The input matrix.

Returns: 

The product of the elements.

Time complexity: O(mn), the number of elements.

3.7.9. igraph_matrix_rowsum — Rowwise sum.

igraph_error_t igraph_matrix_rowsum(const igraph_matrix_t *m,
                                    igraph_vector_t *res);

Calculate the sum of the elements in each row.

Arguments: 

m:

The input matrix.

res:

Pointer to an initialized vector; the result is stored here. It will be resized if necessary.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the matrix.

3.7.10. igraph_matrix_colsum — Columnwise sum.

igraph_error_t igraph_matrix_colsum(const igraph_matrix_t *m,
                                    igraph_vector_t *res);

Calculate the sum of the elements in each column.

Arguments: 

m:

The input matrix.

res:

Pointer to an initialized vector; the result is stored here. It will be resized if necessary.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the matrix.

3.7.11. igraph_matrix_transpose — Transpose a matrix.

igraph_error_t igraph_matrix_transpose(igraph_matrix_t *m);

Calculate the transpose of a matrix. Note that the function reallocates the memory used for the matrix.

Arguments: 

m:

The input (and output) matrix.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the matrix.

3.8. Matrix comparisons

3.8.1. igraph_matrix_all_e — Are all elements equal?

igraph_bool_t igraph_matrix_all_e(const igraph_matrix_t *lhs,
        const igraph_matrix_t *rhs);

Arguments: 

lhs:

The first matrix.

rhs:

The second matrix.

Returns: 

Positive integer (=true) if the elements in the lhs are all equal to the corresponding elements in rhs. Returns 0 (=false) if the dimensions of the matrices don't match.

Time complexity: O(nm), the size of the matrices.

3.8.2. igraph_matrix_all_l — Are all elements less?

igraph_bool_t igraph_matrix_all_l(const igraph_matrix_t *lhs,
        const igraph_matrix_t *rhs);

Arguments: 

lhs:

The first matrix.

rhs:

The second matrix.

Returns: 

Positive integer (=true) if the elements in the lhs are all less than the corresponding elements in rhs. Returns 0 (=false) if the dimensions of the matrices don't match.

Time complexity: O(nm), the size of the matrices.

3.8.3. igraph_matrix_all_g — Are all elements greater?

igraph_bool_t igraph_matrix_all_g(const igraph_matrix_t *lhs,
        const igraph_matrix_t *rhs);

Arguments: 

lhs:

The first matrix.

rhs:

The second matrix.

Returns: 

Positive integer (=true) if the elements in the lhs are all greater than the corresponding elements in rhs. Returns 0 (=false) if the dimensions of the matrices don't match.

Time complexity: O(nm), the size of the matrices.

3.8.4. igraph_matrix_all_le — Are all elements less or equal?

igraph_bool_t
igraph_matrix_all_le(const igraph_matrix_t *lhs,
                                const igraph_matrix_t *rhs);

Arguments: 

lhs:

The first matrix.

rhs:

The second matrix.

Returns: 

Positive integer (=true) if the elements in the lhs are all less than or equal to the corresponding elements in rhs. Returns 0 (=false) if the dimensions of the matrices don't match.

Time complexity: O(nm), the size of the matrices.

3.8.5. igraph_matrix_all_ge — Are all elements greater or equal?

igraph_bool_t
igraph_matrix_all_ge(const igraph_matrix_t *lhs,
                                const igraph_matrix_t *rhs);

Arguments: 

lhs:

The first matrix.

rhs:

The second matrix.

Returns: 

Positive integer (=true) if the elements in the lhs are all greater than or equal to the corresponding elements in rhs. Returns 0 (=false) if the dimensions of the matrices don't match.

Time complexity: O(nm), the size of the matrices.

3.9. Combining matrices

3.9.1. igraph_matrix_rbind — Combine two matrices rowwise.

igraph_error_t igraph_matrix_rbind(igraph_matrix_t *to,
                                   const igraph_matrix_t *from);

This function places the rows of from below the rows of to and stores the result in to. The number of columns in the two matrices must match.

Arguments: 

to:

The upper matrix; the result is also stored here.

from:

The lower matrix. It is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the newly created matrix.

3.9.2. igraph_matrix_cbind — Combine matrices columnwise.

igraph_error_t igraph_matrix_cbind(igraph_matrix_t *to,
                                   const igraph_matrix_t *from);

This function places the columns of from on the right of to, and stores the result in to.

Arguments: 

to:

The left matrix; the result is stored here too.

from:

The right matrix. It is left unchanged.

Returns: 

Error code.

Time complexity: O(mn), the number of elements on the new matrix.

3.10. Finding minimum and maximum

3.10.1. igraph_matrix_min — Smallest element of a matrix.

igraph_real_t igraph_matrix_min(const igraph_matrix_t *m);

The matrix must be non-empty.

Arguments: 

m:

The input matrix.

Returns: 

The smallest element of m, or NaN if any element is NaN.

Time complexity: O(mn), the number of elements in the matrix.

3.10.2. igraph_matrix_max — Largest element of a matrix.

igraph_real_t igraph_matrix_max(const igraph_matrix_t *m);

If the matrix is empty, an arbitrary number is returned.

Arguments: 

m:

The matrix object.

Returns: 

The maximum element of m, or NaN if any element is NaN.

Added in version 0.2.

Time complexity: O(mn), the number of elements in the matrix.

3.10.3. igraph_matrix_which_min — Indices of the smallest element.

igraph_error_t igraph_matrix_which_min(
        const igraph_matrix_t *m, igraph_integer_t *i, igraph_integer_t *j);

The matrix must be non-empty. If the smallest element is not unique, then the indices of the first such element are returned. If the matrix contains NaN values, the indices of the first NaN value are returned.

Arguments: 

m:

The matrix.

i:

Pointer to an igraph_integer_t. The row index of the minimum is stored here.

j:

Pointer to an igraph_integer_t. The column index of the minimum is stored here.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.10.4. igraph_matrix_which_max — Indices of the largest element.

igraph_error_t igraph_matrix_which_max(
        const igraph_matrix_t *m, igraph_integer_t *i, igraph_integer_t *j);

The matrix must be non-empty. If the largest element is not unique, then the indices of the first such element are returned. If the matrix contains NaN values, the indices of the first NaN value are returned.

Arguments: 

m:

The matrix.

i:

Pointer to an igraph_integer_t. The row index of the maximum is stored here.

j:

Pointer to an igraph_integer_t. The column index of the maximum is stored here.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.10.5. igraph_matrix_minmax — Minimum and maximum elements of a matrix.

igraph_error_t igraph_matrix_minmax(const igraph_matrix_t *m,
                                    igraph_real_t *min, igraph_real_t *max);

Handy if you want to have both the smallest and largest element of a matrix. The matrix is only traversed once. The matrix must be non-empty. If a matrix contains at least one NaN, both min and max will be NaN.

Arguments: 

m:

The input matrix. It must contain at least one element.

min:

Pointer to a base type variable. The minimum is stored here.

max:

Pointer to a base type variable. The maximum is stored here.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.10.6. igraph_matrix_which_minmax — Indices of the minimum and maximum elements

igraph_error_t igraph_matrix_which_minmax(const igraph_matrix_t *m,
        igraph_integer_t *imin, igraph_integer_t *jmin,
        igraph_integer_t *imax, igraph_integer_t *jmax);

Handy if you need the indices of the smallest and largest elements. The matrix is traversed only once. The matrix must be non-empty. If the minimum or maximum is not unique, the index of the first minimum or the first maximum is returned, respectively. If a matrix contains at least one NaN, both which_min and which_max will point to the first NaN value.

Arguments: 

m:

The input matrix.

imin:

Pointer to an igraph_integer_t, the row index of the minimum is stored here.

jmin:

Pointer to an igraph_integer_t, the column index of the minimum is stored here.

imax:

Pointer to an igraph_integer_t, the row index of the maximum is stored here.

jmax:

Pointer to an igraph_integer_t, the column index of the maximum is stored here.

Returns: 

Error code.

Time complexity: O(mn), the number of elements.

3.11. Matrix properties

3.11.1. igraph_matrix_empty — Check for an empty matrix.

igraph_bool_t igraph_matrix_empty(const igraph_matrix_t *m);

It is possible to have a matrix with zero rows or zero columns, or even both. This functions checks for these.

Arguments: 

m:

The input matrix.

Returns: 

Boolean, TRUE if the matrix contains zero elements, and FALSE otherwise.

Time complexity: O(1).

3.11.2. igraph_matrix_isnull — Check for a null matrix.

igraph_bool_t igraph_matrix_isnull(const igraph_matrix_t *m);

Checks whether all elements are zero.

Arguments: 

m:

The input matrix.

Returns: 

Boolean, TRUE is m contains only zeros and FALSE otherwise.

Time complexity: O(mn), the number of elements.

3.11.3. igraph_matrix_size — The number of elements in a matrix.

igraph_integer_t igraph_matrix_size(const igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Returns: 

The size of the matrix.

Time complexity: O(1).

3.11.4. igraph_matrix_capacity — Returns the number of elements allocated for a matrix.

igraph_integer_t igraph_matrix_capacity(const igraph_matrix_t *m);

Note that this might be different from the size of the matrix (as queried by igraph_matrix_size(), and specifies how many elements the matrix can hold, without reallocation.

Arguments: 

v:

Pointer to the (previously initialized) matrix object to query.

Returns: 

The allocated capacity.

See also: 

Time complexity: O(1).

3.11.5. igraph_matrix_nrow — The number of rows in a matrix.

igraph_integer_t igraph_matrix_nrow(const igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Returns: 

The number of rows in the matrix.

Time complexity: O(1).

3.11.6. igraph_matrix_ncol — The number of columns in a matrix.

igraph_integer_t igraph_matrix_ncol(const igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Returns: 

The number of columns in the matrix.

Time complexity: O(1).

3.11.7. igraph_matrix_is_symmetric — Check for symmetric matrix.

igraph_bool_t igraph_matrix_is_symmetric(const igraph_matrix_t *m);

A non-square matrix is not symmetric by definition.

Arguments: 

m:

The input matrix.

Returns: 

Boolean, TRUE if the matrix is square and symmetric, FALSE otherwise.

Time complexity: O(mn), the number of elements. O(1) for non-square matrices.

3.11.8. igraph_matrix_maxdifference — Maximum absolute difference between two matrices.

igraph_real_t igraph_matrix_maxdifference(const igraph_matrix_t *m1,
        const igraph_matrix_t *m2);

Calculate the maximum absolute difference of two matrices. Both matrices must be non-empty. If their dimensions differ then a warning is given and the comparison is performed by vectors columnwise from both matrices. The remaining elements in the larger vector are ignored.

Arguments: 

m1:

The first matrix.

m2:

The second matrix.

Returns: 

The element with the largest absolute value in m1 - m2.

Time complexity: O(mn), the elements in the smaller matrix.

3.12. Searching for elements

3.12.1. igraph_matrix_contains — Search for an element.

igraph_bool_t igraph_matrix_contains(const igraph_matrix_t *m,
        igraph_real_t e);

Search for the given element in the matrix.

Arguments: 

m:

The input matrix.

e:

The element to search for.

Returns: 

Boolean, TRUE if the matrix contains e, FALSE otherwise.

Time complexity: O(mn), the number of elements.

3.12.2. igraph_matrix_search — Search from a given position.

igraph_bool_t igraph_matrix_search(const igraph_matrix_t *m,
        igraph_integer_t from, igraph_real_t what, igraph_integer_t *pos,
        igraph_integer_t *row, igraph_integer_t *col);

Search for an element in a matrix and start the search from the given position. The search is performed columnwise.

Arguments: 

m:

The input matrix.

from:

The position to search from, the positions are enumerated columnwise.

what:

The element to search for.

pos:

Pointer to an igraph_integer_t. If the element is found, then this is set to the position of its first appearance.

row:

Pointer to an igraph_integer_t. If the element is found, then this is set to its row index.

col:

Pointer to an igraph_integer_t. If the element is found, then this is set to its column index.

Returns: 

Boolean, TRUE if the element is found, FALSE otherwise.

Time complexity: O(mn), the number of elements.

3.13. Resizing operations

3.13.1. igraph_matrix_resize — Resizes a matrix.

igraph_error_t igraph_matrix_resize(igraph_matrix_t *m, igraph_integer_t nrow, igraph_integer_t ncol);

This function resizes a matrix by adding more elements to it. The matrix contains arbitrary data after resizing it. That is, after calling this function you cannot expect that element (i,j) in the matrix remains the same as before.

Arguments: 

m:

Pointer to an already initialized matrix object.

nrow:

The number of rows in the resized matrix.

ncol:

The number of columns in the resized matrix.

Returns: 

Error code.

Time complexity: O(1) if the matrix gets smaller, usually O(n) if it gets larger, n is the number of elements in the resized matrix.

3.13.2. igraph_matrix_resize_min — Deallocates unused memory for a matrix.

igraph_error_t igraph_matrix_resize_min(igraph_matrix_t *m);

Note that this function might fail if there is not enough memory available.

Also note, that this function leaves the matrix intact, i.e. it does not destroy any of the elements. However, usually it involves copying the matrix in memory.

Arguments: 

m:

Pointer to an initialized matrix.

Returns: 

Error code.

See also: 

Time complexity: operating system dependent.

3.13.3. igraph_matrix_add_rows — Adds rows to a matrix.

igraph_error_t igraph_matrix_add_rows(igraph_matrix_t *m, igraph_integer_t n);

Arguments: 

m:

The matrix object.

n:

The number of rows to add.

Returns: 

Error code, IGRAPH_ENOMEM if there isn't enough memory for the operation.

Time complexity: linear with the number of elements of the new, resized matrix.

3.13.4. igraph_matrix_add_cols — Adds columns to a matrix.

igraph_error_t igraph_matrix_add_cols(igraph_matrix_t *m, igraph_integer_t n);

Arguments: 

m:

The matrix object.

n:

The number of columns to add.

Returns: 

Error code, IGRAPH_ENOMEM if there is not enough memory to perform the operation.

Time complexity: linear with the number of elements of the new, resized matrix.

3.13.5. igraph_matrix_remove_row — Remove a row.

igraph_error_t igraph_matrix_remove_row(igraph_matrix_t *m, igraph_integer_t row);

A row is removed from the matrix.

Arguments: 

m:

The input matrix.

row:

The index of the row to remove.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the matrix.

3.13.6. igraph_matrix_remove_col — Removes a column from a matrix.

igraph_error_t igraph_matrix_remove_col(igraph_matrix_t *m, igraph_integer_t col);

Arguments: 

m:

The matrix object.

col:

The column to remove.

Returns: 

Error code, always returns with success.

Time complexity: linear with the number of elements of the new, resized matrix.

4. Sparse matrices

4.1.  About sparse matrices

The igraph_sparsemat_t data type stores sparse matrices, i.e. matrices in which the majority of the elements are zero.

The data type is essentially a wrapper to some of the functions in the CXSparse library, by Tim Davis, see http://faculty.cse.tamu.edu/davis/suitesparse.html

Matrices can be stored in two formats: triplet and column-compressed. The triplet format is intended for sparse matrix initialization, as it is easy to add new (non-zero) elements to it. Most of the computations are done on sparse matrices in column-compressed format, after the user has converted the triplet matrix to column-compressed, via igraph_sparsemat_compress().

Both formats are dynamic, in the sense that new elements can be added to them, possibly resulting the allocation of more memory.

Row and column indices follow the C convention and are zero-based.

Example 7.5.  File examples/simple/igraph_sparsemat.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

int main() {

    igraph_sparsemat_t A, B, C, D;
    igraph_t G, H;
    igraph_vector_t vect;
    igraph_integer_t i;

    /* Create, compress, destroy */
    igraph_sparsemat_init(&A, 100, 20, 50);
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&B);
    igraph_sparsemat_destroy(&A);

    /* Convert a ring graph to a matrix, print it, compress, print again */
#define VC 10
    igraph_ring(&G, VC, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
    igraph_get_sparsemat(&G, &A);
    igraph_destroy(&G);

    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_print(&A, stdout);
    igraph_sparsemat_print(&B, stdout);

    /* Basic query, nrow, ncol, type, is_triplet, is_cc */
    if (igraph_sparsemat_nrow(&A) != VC ||
        igraph_sparsemat_ncol(&A) != VC ||
        igraph_sparsemat_nrow(&B) != VC ||
        igraph_sparsemat_ncol(&B) != VC) {
        return 1;
    }
    if (!igraph_sparsemat_is_triplet(&A)) {
        return 2;
    }
    if (!igraph_sparsemat_is_cc(&B))      {
        return 3;
    }
    if (igraph_sparsemat_type(&A) != IGRAPH_SPARSEMAT_TRIPLET) {
        return 4;
    }
    if (igraph_sparsemat_type(&B) != IGRAPH_SPARSEMAT_CC)      {
        return 5;
    }

    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);
#undef VC

    printf("------------------------\n");

    /* Create unit matrices */
    igraph_sparsemat_eye(&A, /*n=*/ 5, /*nzmax=*/ 5, /*value=*/ 1.0,
                         /*compress=*/ 0);
    igraph_sparsemat_eye(&B, /*n=*/ 5, /*nzmax=*/ 5, /*value=*/ 1.0,
                         /*compress=*/ 1);
    igraph_sparsemat_print(&A, stdout);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);

    printf("------------------------\n");

    /* Create diagonal matrices */
    igraph_vector_init(&vect, 5);
    for (i = 0; i < 5; i++) {
        VECTOR(vect)[i] = i;
    }
    igraph_sparsemat_diag(&A, /*nzmax=*/ 5, /*values=*/ &vect, /*compress=*/ 0);
    igraph_sparsemat_diag(&B, /*nzmax=*/ 5, /*values=*/ &vect, /*compress=*/ 1);
    igraph_vector_destroy(&vect);
    igraph_sparsemat_print(&A, stdout);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);

    printf("------------------------\n");

    /* Transpose matrices */
    igraph_tree(&G, 10, /*children=*/ 2, IGRAPH_TREE_OUT);
    igraph_get_sparsemat(&G, &A);
    igraph_destroy(&G);
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_transpose(&B, &C, /*values=*/ 1);
    igraph_sparsemat_print(&C, stdout);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);
    igraph_sparsemat_destroy(&C);

    printf("------------------------\n");

    /* Add duplicate elements */
    igraph_sparsemat_init(&A, 10, 10, /*nzmax=*/ 20);
    for (i = 1; i < 10; i++) {
        igraph_sparsemat_entry(&A, 0, i, 1.0);
    }
    for (i = 1; i < 10; i++) {
        igraph_sparsemat_entry(&A, 0, i, 1.0);
    }
    igraph_sparsemat_print(&A, stdout);
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_dupl(&B);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);

    printf("------------------------\n");

    /* Drop zero elements */
    igraph_sparsemat_init(&A, 10, 10, /*nzmax=*/ 20);
    igraph_sparsemat_entry(&A, 7, 3, 0.0);
    for (i = 1; i < 10; i++) {
        igraph_sparsemat_entry(&A, 0, i, 1.0);
        igraph_sparsemat_entry(&A, 0, i, 0.0);
    }
    igraph_sparsemat_entry(&A, 0, 0, 0.0);
    igraph_sparsemat_print(&A, stdout);
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_dropzeros(&B);
    igraph_sparsemat_print(&B, stdout);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);

    printf("------------------------\n");

    /* Add two matrices */

    igraph_star(&G, 10, IGRAPH_STAR_OUT, /*center=*/ 0);
    igraph_ring(&H, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
    igraph_get_sparsemat(&G, &A);
    igraph_get_sparsemat(&H, &B);
    igraph_destroy(&G);
    igraph_destroy(&H);
    igraph_sparsemat_compress(&A, &C);
    igraph_sparsemat_compress(&B, &D);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);
    igraph_sparsemat_add(&C, &D, /*alpha=*/ 1.0, /*beta=*/ 2.0, &A);
    igraph_sparsemat_destroy(&C);
    igraph_sparsemat_destroy(&D);
    igraph_sparsemat_print(&A, stdout);
    igraph_sparsemat_destroy(&A);

    return 0;
}


Example 7.6.  File examples/simple/igraph_sparsemat3.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#define NCOMPLEX  /* to make it compile with MSVC on Windows */

#include <cs/cs.h>
#include <igraph.h>

int permute(const igraph_matrix_t *M,
            const igraph_vector_int_t *p,
            const igraph_vector_int_t *q,
            igraph_matrix_t *res) {

    igraph_integer_t nrow = igraph_vector_int_size(p);
    igraph_integer_t ncol = igraph_vector_int_size(q);
    igraph_integer_t i, j;

    igraph_matrix_resize(res, nrow, ncol);

    for (i = 0; i < nrow; i++) {
        for (j = 0; j < ncol; j++) {
            igraph_integer_t ii = VECTOR(*p)[i];
            igraph_integer_t jj = VECTOR(*q)[j];
            MATRIX(*res, i, j) = MATRIX(*M, ii, jj);
        }
    }

    return 0;
}

int permute_rows(const igraph_matrix_t *M,
                 const igraph_vector_int_t *p,
                 igraph_matrix_t *res) {

    igraph_integer_t nrow = igraph_vector_int_size(p);
    igraph_integer_t ncol = igraph_matrix_ncol(M);
    igraph_integer_t i, j;

    igraph_matrix_resize(res, nrow, ncol);

    for (i = 0; i < nrow; i++) {
        for (j = 0; j < ncol; j++) {
            igraph_integer_t ii = VECTOR(*p)[i];
            MATRIX(*res, i, j) = MATRIX(*M, ii, j);
        }
    }

    return 0;
}

int permute_cols(const igraph_matrix_t *M,
                 const igraph_vector_int_t *q,
                 igraph_matrix_t *res) {

    igraph_integer_t nrow = igraph_matrix_nrow(M);
    igraph_integer_t ncol = igraph_vector_int_size(q);
    igraph_integer_t i, j;

    igraph_matrix_resize(res, nrow, ncol);

    for (i = 0; i < nrow; i++) {
        for (j = 0; j < ncol; j++) {
            igraph_integer_t jj = VECTOR(*q)[j];
            MATRIX(*res, i, j) = MATRIX(*M, i, jj);
        }
    }

    return 0;
}

igraph_error_t random_permutation(igraph_vector_int_t *vec) {
    /* We just do size(vec) * 2 swaps */
    igraph_integer_t one, two, i, n = igraph_vector_int_size(vec);
    igraph_integer_t tmp;
    for (i = 0; i < 2 * n; i++) {
        one = RNG_INTEGER(0, n - 1);
        two = RNG_INTEGER(0, n - 1);
        tmp = VECTOR(*vec)[one];
        VECTOR(*vec)[one] = VECTOR(*vec)[two];
        VECTOR(*vec)[two] = tmp;
    }
    return 0;
}

igraph_bool_t check_same(const igraph_sparsemat_t *A,
                         const igraph_matrix_t *M) {

    igraph_integer_t nrow = igraph_sparsemat_nrow(A);
    igraph_integer_t ncol = igraph_sparsemat_ncol(A);
    igraph_integer_t j, p, nzero = 0;

    if (nrow != igraph_matrix_nrow(M) ||
        ncol != igraph_matrix_ncol(M)) {
        return 0;
    }

    for (j = 0; j < A->cs->n; j++) {
        for (p = A->cs->p[j]; p < A->cs->p[j + 1]; p++) {
            igraph_integer_t to = A->cs->i[p];
            igraph_real_t value = A->cs->x[p];
            if (value != MATRIX(*M, to, j)) {
                return 0;
            }
            nzero += 1;
        }
    }

    for (j = 0; j < nrow; j++) {
        for (p = 0; p < ncol; p++) {
            if (MATRIX(*M, j, p) != 0) {
                nzero -= 1;
            }
        }
    }

    return nzero == 0;
}

int main() {

    igraph_sparsemat_t A, B;
    igraph_matrix_t M, N;
    igraph_vector_int_t p, q;
    igraph_integer_t i;

    /* Permutation of a matrix */

#define NROW 10
#define NCOL 5
#define EDGES NROW*NCOL/3
    igraph_matrix_init(&M, NROW, NCOL);
    igraph_sparsemat_init(&A, NROW, NCOL, EDGES);
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, NROW - 1);
        igraph_integer_t c = RNG_INTEGER(0, NCOL - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        MATRIX(M, r, c) = MATRIX(M, r, c) + value;
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);

    igraph_vector_int_init_seq(&p, 0, NROW - 1);
    igraph_vector_int_init_seq(&q, 0, NCOL - 1);

    /* Identity */

    igraph_matrix_init(&N, 0, 0);
    permute(&M, &p, &q, &N);

    igraph_sparsemat_permute(&B, &p, &q, &A);
    igraph_sparsemat_dupl(&A);

    if (! check_same(&A, &N)) {
        return 1;
    }

    /* Random permutation */
    random_permutation(&p);
    random_permutation(&q);

    permute(&M, &p, &q, &N);

    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_permute(&B, &p, &q, &A);
    igraph_sparsemat_dupl(&A);

    if (! check_same(&A, &N)) {
        return 2;
    }

    igraph_vector_int_destroy(&p);
    igraph_vector_int_destroy(&q);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);
    igraph_matrix_destroy(&M);
    igraph_matrix_destroy(&N);

#undef NROW
#undef NCOL
#undef EDGES

    /* Indexing */

#define NROW 10
#define NCOL 5
#define EDGES NROW*NCOL/3
#define I_NROW 6
#define I_NCOL 3
    igraph_matrix_init(&M, NROW, NCOL);
    igraph_sparsemat_init(&A, NROW, NCOL, EDGES);
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, NROW - 1);
        igraph_integer_t c = RNG_INTEGER(0, NCOL - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        MATRIX(M, r, c) = MATRIX(M, r, c) + value;
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);

    igraph_vector_int_init(&p, I_NROW);
    igraph_vector_int_init(&q, I_NCOL);

    for (i = 0; i < I_NROW; i++) {
        VECTOR(p)[i] = RNG_INTEGER(0, I_NROW - 1);
    }
    for (i = 0; i < I_NCOL; i++) {
        VECTOR(p)[i] = RNG_INTEGER(0, I_NCOL - 1);
    }

    igraph_matrix_init(&N, 0, 0);
    permute(&M, &p, &q, &N);

    igraph_sparsemat_index(&B, &p, &q, &A, 0);

    if (! check_same(&A, &N)) {
        return 3;
    }

    /* A single element */

    igraph_vector_int_resize(&p, 1);
    igraph_vector_int_resize(&q, 1);

    for (i = 0; i < 100; i++) {
        igraph_real_t value;
        VECTOR(p)[0] = RNG_INTEGER(0, NROW - 1);
        VECTOR(q)[0] = RNG_INTEGER(0, NCOL - 1);
        igraph_sparsemat_index(&B, &p, &q, /*res=*/ 0, &value);
        if (value != MATRIX(M, VECTOR(p)[0], VECTOR(q)[0])) {
            return 4;
        }
    }

    igraph_sparsemat_destroy(&A);

    for (i = 0; i < 100; i++) {
        igraph_real_t value;
        VECTOR(p)[0] = RNG_INTEGER(0, NROW - 1);
        VECTOR(q)[0] = RNG_INTEGER(0, NCOL - 1);
        igraph_sparsemat_index(&B, &p, &q, /*res=*/ &A, &value);
        igraph_sparsemat_destroy(&A);
        if (value != MATRIX(M, VECTOR(p)[0], VECTOR(q)[0])) {
            return 4;
        }
    }

    igraph_vector_int_destroy(&p);
    igraph_vector_int_destroy(&q);
    igraph_sparsemat_destroy(&B);
    igraph_matrix_destroy(&M);
    igraph_matrix_destroy(&N);

    /* Indexing only the rows or the columns */

    igraph_matrix_init(&M, NROW, NCOL);
    igraph_sparsemat_init(&A, NROW, NCOL, EDGES);
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, NROW - 1);
        igraph_integer_t c = RNG_INTEGER(0, NCOL - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        MATRIX(M, r, c) = MATRIX(M, r, c) + value;
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);

    igraph_vector_int_init(&p, I_NROW);
    igraph_vector_int_init(&q, I_NCOL);

    for (i = 0; i < I_NROW; i++) {
        VECTOR(p)[i] = RNG_INTEGER(0, I_NROW - 1);
    }
    for (i = 0; i < I_NCOL; i++) {
        VECTOR(p)[i] = RNG_INTEGER(0, I_NCOL - 1);
    }

    igraph_matrix_init(&N, 0, 0);
    permute_rows(&M, &p, &N);

    igraph_sparsemat_index(&B, &p, 0, &A, 0);

    if (! check_same(&A, &N)) {
        return 5;
    }

    permute_cols(&M, &q, &N);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_index(&B, 0, &q, &A, 0);

    if (! check_same(&A, &N)) {
        return 6;
    }

    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);
    igraph_vector_int_destroy(&p);
    igraph_vector_int_destroy(&q);
    igraph_matrix_destroy(&M);
    igraph_matrix_destroy(&N);

    return 0;
}


Example 7.7.  File examples/simple/igraph_sparsemat4.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#define NCOMPLEX  /* to make it compile with MSVC on Windows */

#include <cs/cs.h>
#include <igraph.h>

igraph_bool_t check_solution(const igraph_sparsemat_t *A,
                             const igraph_vector_t *x,
                             const igraph_vector_t *b) {

    igraph_integer_t dim = igraph_vector_size(x);
    igraph_vector_t res;
    igraph_integer_t j, p;
    igraph_real_t min, max;

    igraph_vector_copy(&res, b);

    for (j = 0; j < dim; j++) {
        for (p = A->cs->p[j]; p < A->cs->p[j + 1]; p++) {
            igraph_integer_t from = A->cs->i[p];
            igraph_real_t value = A->cs->x[p];
            VECTOR(res)[from] -= VECTOR(*x)[j] * value;
        }
    }

    igraph_vector_minmax(&res, &min, &max);
    igraph_vector_destroy(&res);

    return fabs(min) < 1e-15 && fabs(max) < 1e-15;
}

int main() {

    igraph_sparsemat_t A, B, C;
    igraph_vector_t b, x;
    igraph_integer_t i;

    /* lsolve */

#define DIM 10
#define EDGES (DIM*DIM/6)
    igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM);
    for (i = 0; i < DIM; i++) {
        igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3));
    }
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, DIM - 1);
        igraph_integer_t c = RNG_INTEGER(0, r);
        igraph_real_t value = RNG_INTEGER(1, 5);
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_dupl(&B);

    igraph_vector_init(&b, DIM);
    for (i = 0; i < DIM; i++) {
        VECTOR(b)[i] = RNG_INTEGER(1, 10);
    }

    igraph_vector_init(&x, DIM);
    igraph_sparsemat_lsolve(&B, &b, &x);

    if (! check_solution(&B, &x, &b)) {
        return 1;
    }

    igraph_vector_destroy(&b);
    igraph_vector_destroy(&x);
    igraph_sparsemat_destroy(&B);

#undef DIM
#undef EDGES

    /* ltsolve */

#define DIM 10
#define EDGES (DIM*DIM/6)
    igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM);
    for (i = 0; i < DIM; i++) {
        igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3));
    }
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, DIM - 1);
        igraph_integer_t c = RNG_INTEGER(0, r);
        igraph_real_t value = RNG_INTEGER(1, 5);
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_dupl(&B);

    igraph_vector_init(&b, DIM);
    for (i = 0; i < DIM; i++) {
        VECTOR(b)[i] = RNG_INTEGER(1, 10);
    }

    igraph_vector_init(&x, DIM);
    igraph_sparsemat_ltsolve(&B, &b, &x);

    igraph_sparsemat_transpose(&B, &A, /*values=*/ 1);
    if (! check_solution(&A, &x, &b)) {
        return 2;
    }

    igraph_vector_destroy(&b);
    igraph_vector_destroy(&x);
    igraph_sparsemat_destroy(&B);
    igraph_sparsemat_destroy(&A);

#undef DIM
#undef EDGES

    /* usolve */

#define DIM 10
#define EDGES (DIM*DIM/6)
    igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM);
    for (i = 0; i < DIM; i++) {
        igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3));
    }
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, DIM - 1);
        igraph_integer_t c = RNG_INTEGER(0, r);
        igraph_real_t value = RNG_INTEGER(1, 5);
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_dupl(&B);
    igraph_sparsemat_transpose(&B, &A, /*values=*/ 1);

    igraph_vector_init(&b, DIM);
    for (i = 0; i < DIM; i++) {
        VECTOR(b)[i] = RNG_INTEGER(1, 10);
    }

    igraph_vector_init(&x, DIM);
    igraph_sparsemat_usolve(&A, &b, &x);

    if (! check_solution(&A, &x, &b)) {
        return 3;
    }

    igraph_vector_destroy(&b);
    igraph_vector_destroy(&x);
    igraph_sparsemat_destroy(&B);
    igraph_sparsemat_destroy(&A);

#undef DIM
#undef EDGES

    /* utsolve */

#define DIM 10
#define EDGES (DIM*DIM/6)
    igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM);
    for (i = 0; i < DIM; i++) {
        igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3));
    }
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t r = RNG_INTEGER(0, DIM - 1);
        igraph_integer_t c = RNG_INTEGER(0, r);
        igraph_real_t value = RNG_INTEGER(1, 5);
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_dupl(&B);
    igraph_sparsemat_transpose(&B, &A, /*values=*/ 1);
    igraph_sparsemat_destroy(&B);

    igraph_vector_init(&b, DIM);
    for (i = 0; i < DIM; i++) {
        VECTOR(b)[i] = RNG_INTEGER(1, 10);
    }

    igraph_vector_init(&x, DIM);
    igraph_sparsemat_utsolve(&A, &b, &x);

    igraph_sparsemat_transpose(&A, &B, /*values=*/ 1);
    if (! check_solution(&B, &x, &b)) {
        return 4;
    }

    igraph_vector_destroy(&b);
    igraph_vector_destroy(&x);
    igraph_sparsemat_destroy(&B);
    igraph_sparsemat_destroy(&A);

#undef DIM
#undef EDGES

    /* cholsol */
    /* We need a positive definite matrix, so we create a full-rank
       matrix first and then calculate A'A, which will be positive
       definite. */

#define DIM 10
#define EDGES (DIM*DIM/6)
    igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM);
    for (i = 0; i < DIM; i++) {
        igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3));
    }
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t from = RNG_INTEGER(0, DIM - 1);
        igraph_integer_t to = RNG_INTEGER(0, DIM - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        igraph_sparsemat_entry(&A, from, to, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_dupl(&B);
    igraph_sparsemat_transpose(&B, &A, /*values=*/ 1);
    igraph_sparsemat_multiply(&A, &B, &C);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_destroy(&B);

    igraph_vector_init(&b, DIM);
    for (i = 0; i < DIM; i++) {
        VECTOR(b)[i] = RNG_INTEGER(1, 10);
    }

    igraph_vector_init(&x, DIM);
    igraph_sparsemat_cholsol(&C, &b, &x, /*order=*/ 0);

    if (! check_solution(&C, &x, &b)) {
        return 5;
    }

    igraph_vector_destroy(&b);
    igraph_vector_destroy(&x);
    igraph_sparsemat_destroy(&C);

#undef DIM
#undef EDGES

    /* lusol */

#define DIM 10
#define EDGES (DIM*DIM/4)
    igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM);
    for (i = 0; i < DIM; i++) {
        igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3));
    }
    for (i = 0; i < EDGES; i++) {
        igraph_integer_t from = RNG_INTEGER(0, DIM - 1);
        igraph_integer_t to = RNG_INTEGER(0, DIM - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        igraph_sparsemat_entry(&A, from, to, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);
    igraph_sparsemat_dupl(&B);

    igraph_vector_init(&b, DIM);
    for (i = 0; i < DIM; i++) {
        VECTOR(b)[i] = RNG_INTEGER(1, 10);
    }

    igraph_vector_init(&x, DIM);
    igraph_sparsemat_lusol(&B, &b, &x, /*order=*/ 0, /*tol=*/ 1e-10);

    if (! check_solution(&B, &x, &b)) {
        return 6;
    }

    igraph_vector_destroy(&b);
    igraph_vector_destroy(&x);
    igraph_sparsemat_destroy(&B);

#undef DIM
#undef EDGES

    return 0;
}


Example 7.8.  File examples/simple/igraph_sparsemat6.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

int main() {
    igraph_matrix_t mat, mat2, mat3;
    igraph_sparsemat_t spmat, spmat2;
    int i;

    igraph_rng_seed(igraph_rng_default(), 42);

#define NROW 10
#define NCOL 7
#define NUM_NONZEROS 15

    igraph_matrix_init(&mat, NROW, NCOL);
    for (i = 0; i < NUM_NONZEROS; i++) {
        int r = igraph_rng_get_integer(igraph_rng_default(), 0, NROW - 1);
        int c = igraph_rng_get_integer(igraph_rng_default(), 0, NCOL - 1);
        igraph_real_t val = igraph_rng_get_integer(igraph_rng_default(), 1, 10);
        MATRIX(mat, r, c) = val;
    }

    igraph_matrix_as_sparsemat(&spmat, &mat, /*tol=*/ 1e-14);
    igraph_matrix_init(&mat2, 0, 0);
    igraph_sparsemat_as_matrix(&mat2, &spmat);
    if (!igraph_matrix_all_e(&mat, &mat2)) {
        return 1;
    }

    igraph_sparsemat_compress(&spmat, &spmat2);
    igraph_matrix_init(&mat3, 0, 0);
    igraph_sparsemat_as_matrix(&mat3, &spmat2);
    if (!igraph_matrix_all_e(&mat, &mat3)) {
        return 2;
    }

    igraph_matrix_destroy(&mat);
    igraph_matrix_destroy(&mat2);
    igraph_matrix_destroy(&mat3);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);

    return 0;
}


Example 7.9.  File examples/simple/igraph_sparsemat7.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

#define DIM1 10
#define DIM2 5

#define INT(a) (igraph_rng_get_integer(igraph_rng_default(), 0, (a)))

int main() {
    igraph_matrix_t mat;
    igraph_sparsemat_t spmat, spmat2;
    int i;
    igraph_real_t m1, m2;

    igraph_rng_seed(igraph_rng_default(), 42);

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    igraph_sparsemat_entry(&spmat, 1, 2, -1.0);
    igraph_sparsemat_entry(&spmat, 3, 2, 10.0);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_entry(&spmat, 1, 2, -1.0);
    igraph_sparsemat_entry(&spmat, 3, 2, 10.0);

    igraph_sparsemat_compress(&spmat, &spmat2);
    igraph_matrix_init(&mat, 0, 0);
    igraph_sparsemat_as_matrix(&mat, &spmat2);
    m1 = igraph_sparsemat_min(&spmat2);
    m2 = igraph_matrix_min(&mat);
    if (m1 != m2) {
        printf("%f %f\n", m1, m2);
        return 1;
    }
    m1 = igraph_sparsemat_max(&spmat2);
    m2 = igraph_matrix_max(&mat);
    if (m1 != m2) {
        printf("%f %f\n", m1, m2);
        return 2;
    }

    igraph_sparsemat_minmax(&spmat2, &m1, &m2);
    if (m1 != igraph_matrix_min(&mat)) {
        return 3;
    }
    if (m2 != igraph_matrix_max(&mat)) {
        return 4;
    }

    igraph_matrix_destroy(&mat);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);

    return 0;
}


Example 7.10.  File examples/simple/igraph_sparsemat8.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

#define DIM1 10
#define DIM2 5

#define INT(a) (igraph_rng_get_integer(igraph_rng_default(), 0, (a)))

int main() {
    igraph_matrix_t mat, mat2;
    igraph_sparsemat_t spmat, spmat2;
    igraph_integer_t i, j, nz1, nz2;
    igraph_vector_t sums1, sums2;


    igraph_rng_seed(igraph_rng_default(), 42);

    /* COPY */

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_copy(&spmat2, &spmat);

    igraph_matrix_init(&mat, 0, 0);
    igraph_sparsemat_as_matrix(&mat, &spmat);
    igraph_matrix_init(&mat2, 0, 0);
    igraph_sparsemat_as_matrix(&mat2, &spmat2);
    if (!igraph_matrix_all_e(&mat, &mat2)) {
        return 1;
    }

    igraph_matrix_destroy(&mat2);
    igraph_sparsemat_destroy(&spmat2);

    igraph_sparsemat_compress(&spmat, &spmat2);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_copy(&spmat, &spmat2);

    igraph_matrix_init(&mat2, 0, 0);
    igraph_sparsemat_as_matrix(&mat2, &spmat);
    if (!igraph_matrix_all_e(&mat, &mat2)) {
        return 2;
    }

    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);
    igraph_matrix_destroy(&mat);
    igraph_matrix_destroy(&mat2);

    /* COLSUMS, ROWSUMS */

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_compress(&spmat, &spmat2);

    igraph_matrix_init(&mat, 0, 0);
    igraph_sparsemat_as_matrix(&mat, &spmat);
    igraph_vector_init(&sums1, 0);
    igraph_vector_init(&sums2, 0);
    igraph_sparsemat_colsums(&spmat, &sums1);
    igraph_matrix_colsum(&mat, &sums2);
    if (!igraph_vector_all_e(&sums1, &sums2)) {
        return 3;
    }
    igraph_sparsemat_colsums(&spmat2, &sums1);
    if (!igraph_vector_all_e(&sums1, &sums2)) {
        return 4;
    }

    igraph_sparsemat_rowsums(&spmat, &sums1);
    igraph_matrix_rowsum(&mat, &sums2);
    if (!igraph_vector_all_e(&sums1, &sums2)) {
        return 5;
    }
    igraph_sparsemat_rowsums(&spmat2, &sums1);
    if (!igraph_vector_all_e(&sums1, &sums2)) {
        return 6;
    }

    igraph_matrix_destroy(&mat);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);
    igraph_vector_destroy(&sums1);
    igraph_vector_destroy(&sums2);

    /* COUNT_NONZERO, COUNT_NONZEROTOL */

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    igraph_sparsemat_entry(&spmat, 1, 2, 1.0);
    igraph_sparsemat_entry(&spmat, 1, 2, 1.0);
    igraph_sparsemat_entry(&spmat, 1, 3, 1e-12);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_compress(&spmat, &spmat2);

    igraph_matrix_init(&mat, 0, 0);
    igraph_sparsemat_as_matrix(&mat, &spmat2);

    nz1 = igraph_sparsemat_count_nonzero(&spmat2);
    for (nz2 = 0, i = 0; i < igraph_matrix_nrow(&mat); i++) {
        for (j = 0; j < igraph_matrix_ncol(&mat); j++) {
            if (MATRIX(mat, i, j) != 0) {
                nz2++;
            }
        }
    }
    if (nz1 != nz2) {
        printf("%" IGRAPH_PRId " %" IGRAPH_PRId "\n", nz1, nz2);
        return 7;
    }

    nz1 = igraph_sparsemat_count_nonzerotol(&spmat2, 1e-10);
    for (nz2 = 0, i = 0; i < igraph_matrix_nrow(&mat); i++) {
        for (j = 0; j < igraph_matrix_ncol(&mat); j++) {
            if (fabs(MATRIX(mat, i, j)) >= 1e-10) {
                nz2++;
            }
        }
    }
    if (nz1 != nz2) {
        printf("%" IGRAPH_PRId " %" IGRAPH_PRId "\n", nz1, nz2);
        return 8;
    }

    igraph_matrix_destroy(&mat);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);

    /* SCALE */

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_compress(&spmat, &spmat2);

    igraph_sparsemat_scale(&spmat, 2.0);
    igraph_sparsemat_scale(&spmat2, 2.0);
    igraph_matrix_init(&mat, 0, 0);
    igraph_sparsemat_as_matrix(&mat, &spmat);
    igraph_matrix_init(&mat2, 0, 0);
    igraph_sparsemat_as_matrix(&mat2, &spmat2);
    igraph_matrix_scale(&mat, 1.0 / 2.0);
    igraph_matrix_scale(&mat2, 1.0 / 2.0);
    if (!igraph_matrix_all_e(&mat, &mat2)) {
        return 9;
    }

    igraph_matrix_destroy(&mat);
    igraph_matrix_destroy(&mat2);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);

    /* ADDROWS, ADDCOLS */

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_compress(&spmat, &spmat2);

    igraph_sparsemat_add_rows(&spmat, 3);
    igraph_sparsemat_add_cols(&spmat, 2);

    igraph_sparsemat_add_rows(&spmat2, 3);
    igraph_sparsemat_add_cols(&spmat2, 2);

    igraph_matrix_init(&mat, 0, 0);
    igraph_sparsemat_as_matrix(&mat, &spmat);
    igraph_matrix_init(&mat2, 0, 0);
    igraph_sparsemat_as_matrix(&mat2, &spmat2);
    if (!igraph_matrix_all_e(&mat, &mat2)) {
        return 10;
    }

    igraph_matrix_destroy(&mat);
    igraph_matrix_destroy(&mat2);
    igraph_sparsemat_destroy(&spmat);
    igraph_sparsemat_destroy(&spmat2);

    return 0;
}


4.2. Creating sparse matrix objects

4.2.1. igraph_sparsemat_init — Initializes a sparse matrix, in triplet format.

igraph_error_t igraph_sparsemat_init(igraph_sparsemat_t *A, igraph_integer_t rows,
        igraph_integer_t cols, igraph_integer_t nzmax);

This is the most common way to create a sparse matrix, together with the igraph_sparsemat_entry() function, which can be used to add the non-zero elements one by one. Once done, the user can call igraph_sparsemat_compress() to convert the matrix to column-compressed, to allow computations with it.

The user must call igraph_sparsemat_destroy() on the matrix to deallocate the memory, once the matrix is no more needed.

Arguments: 

A:

Pointer to a not yet initialized sparse matrix.

rows:

The number of rows in the matrix.

cols:

The number of columns.

nzmax:

The maximum number of non-zero elements in the matrix. It is not compulsory to get this right, but it is useful for the allocation of the proper amount of memory.

Returns: 

Error code.

Time complexity: TODO.

4.2.2. igraph_sparsemat_copy — Copies a sparse matrix.

igraph_error_t igraph_sparsemat_copy(igraph_sparsemat_t *to,
                          const igraph_sparsemat_t *from);

Create a sparse matrix object, by copying another one. The source matrix can be either in triplet or column-compressed format.

Exactly the same amount of memory will be allocated to the copy matrix, as it is currently for the original one.

Arguments: 

to:

Pointer to an uninitialized sparse matrix, the copy will be created here.

from:

The sparse matrix to copy.

Returns: 

Error code.

Time complexity: O(n+nzmax), the number of columns plus the maximum number of non-zero elements.

4.2.3. igraph_sparsemat_realloc — Allocates more (or less) memory for a sparse matrix.

igraph_error_t igraph_sparsemat_realloc(igraph_sparsemat_t *A, igraph_integer_t nzmax);

Sparse matrices automatically allocate more memory, as needed. To control memory allocation, the user can call this function, to allocate memory for a given number of non-zero elements.

Arguments: 

A:

The sparse matrix, it can be in triplet or column-compressed format.

nzmax:

The new maximum number of non-zero elements.

Returns: 

Error code.

Time complexity: TODO.

4.2.4. igraph_sparsemat_destroy — Deallocates memory used by a sparse matrix.

void igraph_sparsemat_destroy(igraph_sparsemat_t *A);

One destroyed, the sparse matrix must be initialized again, before calling any other operation on it.

Arguments: 

A:

The sparse matrix to destroy.

Time complexity: O(1).

4.2.5. igraph_sparsemat_eye — Creates a sparse identity matrix.

igraph_error_t igraph_sparsemat_eye(
    igraph_sparsemat_t *A, igraph_integer_t n, igraph_integer_t nzmax,
    igraph_real_t value, igraph_bool_t compress
);

Arguments: 

A:

An uninitialized sparse matrix, the result is stored here.

n:

The number of rows and number of columns in the matrix.

nzmax:

The maximum number of non-zero elements, this essentially gives the amount of memory that will be allocated for matrix elements.

value:

The value to store in the diagonal.

compress:

Whether to create a column-compressed matrix. If false, then a triplet matrix is created.

Returns: 

Error code.

Time complexity: O(n).

4.2.6. igraph_sparsemat_diag — Creates a sparse diagonal matrix.

igraph_error_t igraph_sparsemat_diag(igraph_sparsemat_t *A, igraph_integer_t nzmax,
                          const igraph_vector_t *values,
                          igraph_bool_t compress);

Arguments: 

A:

An uninitialized sparse matrix, the result is stored here.

nzmax:

The maximum number of non-zero elements, this essentially gives the amount of memory that will be allocated for matrix elements.

values:

The values to store in the diagonal, the size of the matrix defined by the length of this vector.

compress:

Whether to create a column-compressed matrix. If false, then a triplet matrix is created.

Returns: 

Error code.

Time complexity: O(n), the length of the diagonal vector.

4.2.7. igraph_sparsemat_view — Initialize a sparse matrix and set all parameters.

igraph_error_t igraph_sparsemat_view(igraph_sparsemat_t *A, igraph_integer_t nzmax, igraph_integer_t m, igraph_integer_t n,
                          igraph_integer_t *p, igraph_integer_t *i, igraph_real_t *x, igraph_integer_t nz);

This function can be used to temporarily handle existing sparse matrix data, usually created by another software library, as an igraph_sparsemat_t object, and thus avoid unnecessary copying. It supports data stored in either the compressed sparse column format, or the (i, j, x) triplet format where i and j are the matrix indices of a non-zero element, and x is its value.

The compressed sparse column (or row) format is commonly used to represent sparse matrix data. It consists of three vectors, the p column pointers, the i row indices, and the x values. p[k] is the number of non-zero entires in matrix columns k-1 and lower. p[0] is always zero and p[n] is always the total number of non-zero entires in the matrix. i[l] is the row index of the l-th stored element, while x[l] is its value. If a matrix element with indices (j, k) is explicitly stored, it must be located between positions p[k] and p[k+1] - 1 (inclusive) in the i and x vectors.

Do not call igraph_sparsemat_destroy() on a sparse matrix created with this function. Instead, igraph_free() must be called on the cs field of A to free the storage allocated by this function.

Warning: Matrices created with this function must not be used with functions that may reallocate the underlying storage, such as igraph_sparsemat_entry().

Arguments: 

A:

The non-initialized sparse matrix.

nzmax:

The maximum number of entries, typically the actual number of entries.

m:

The number of matrix rows.

n:

The number of matrix columns.

p:

For a compressed matrix, this is the column pointer vector, and must be of size n+1. For a triplet format matrix, it is a vector of column indices and must be of size nzmax.

i:

The row vector. This should contain the row indices of the elements in x. It must be of size nzmax.

x:

The values of the non-zero elements of the sparse matrix. It must be of size nzmax.

nz:

For a compressed matrix, is must be -1. For a triplet format matrix, is must contain the number of entries.

Returns: 

Error code.

Time complexity: O(1).

4.3. Query properties of a sparse matrix

4.3.1. igraph_sparsemat_index — Extracts a submatrix or a single element.

igraph_error_t igraph_sparsemat_index(const igraph_sparsemat_t *A,
                           const igraph_vector_int_t *p,
                           const igraph_vector_int_t *q,
                           igraph_sparsemat_t *res,
                           igraph_real_t *constres);

This function indexes into a sparse matrix. It serves two purposes. First, it can extract submatrices from a sparse matrix. Second, as a special case, it can extract a single element from a sparse matrix.

Arguments: 

A:

The input matrix, it must be in column-compressed format.

p:

An integer vector, or a null pointer. The selected row index or indices. A null pointer selects all rows.

q:

An integer vector, or a null pointer. The selected column index or indices. A null pointer selects all columns.

res:

Pointer to an uninitialized sparse matrix, or a null pointer. If not a null pointer, then the selected submatrix is stored here.

constres:

Pointer to a real variable or a null pointer. If not a null pointer, then the first non-zero element in the selected submatrix is stored here, if there is one. Otherwise zero is stored here. This behavior is handy if one wants to select a single entry from the matrix.

Returns: 

Error code.

Time complexity: TODO.

4.3.2. igraph_sparsemat_nrow — Number of rows.

igraph_integer_t igraph_sparsemat_nrow(const igraph_sparsemat_t *A);

Arguments: 

A:

The input matrix, in triplet or column-compressed format.

Returns: 

The number of rows in the A matrix.

Time complexity: O(1).

4.3.3. igraph_sparsemat_ncol — Number of columns.

igraph_integer_t igraph_sparsemat_ncol(const igraph_sparsemat_t *A);

Arguments: 

A:

The input matrix, in triplet or column-compressed format.

Returns: 

The number of columns in the A matrix.

Time complexity: O(1).

4.3.4. igraph_sparsemat_type — Type of a sparse matrix (triplet or column-compressed).

igraph_sparsemat_type_t igraph_sparsemat_type(const igraph_sparsemat_t *A);

Gives whether a sparse matrix is stored in the triplet format or in column-compressed format.

Arguments: 

A:

The input matrix.

Returns: 

Either IGRAPH_SPARSEMAT_CC or IGRAPH_SPARSEMAT_TRIPLET.

Time complexity: O(1).

4.3.5. igraph_sparsemat_is_triplet — Is this sparse matrix in triplet format?

igraph_bool_t igraph_sparsemat_is_triplet(const igraph_sparsemat_t *A);

Decides whether a sparse matrix is in triplet format.

Arguments: 

A:

The input matrix.

Returns: 

One if the input matrix is in triplet format, zero otherwise.

Time complexity: O(1).

4.3.6. igraph_sparsemat_is_cc — Is this sparse matrix in column-compressed format?

igraph_bool_t igraph_sparsemat_is_cc(const igraph_sparsemat_t *A);

Decides whether a sparse matrix is in column-compressed format.

Arguments: 

A:

The input matrix.

Returns: 

One if the input matrix is in column-compressed format, zero otherwise.

Time complexity: O(1).

4.3.7. igraph_sparsemat_getelements_sorted — Returns the sorted elements of a sparse matrix.

igraph_error_t igraph_sparsemat_getelements_sorted(const igraph_sparsemat_t *A,
                                        igraph_vector_int_t *i,
                                        igraph_vector_int_t *j,
                                        igraph_vector_t *x);

This function will sort a sparse matrix and return the elements in 3 vectors. Two vectors will indicate where the elements are located, and one will give the elements.

Arguments: 

A:

A sparse matrix in either triplet or compressed form.

i:

An initialized int vector. This will store the rows of the returned elements.

j:

An initialized int vector. For a triplet matrix this will store the columns of the returned elements. For a compressed matrix, if the column index is k, then j[k] is the index in x of the start of the k-th column, and the last element of j is the total number of elements. The total number of elements in the k-th column is therefore j[k+1] - j[k]. For example, if there is one element in the first column, and five in the second, j will be set to {0, 1, 6}.

x:

An initialized vector. The elements will be placed here.

Returns: 

Error code.

Time complexity: O(n), the number of stored elements in the sparse matrix.

4.3.8. igraph_sparsemat_min — Minimum of a sparse matrix.

igraph_real_t igraph_sparsemat_min(igraph_sparsemat_t *A);

Arguments: 

A:

The input matrix, column-compressed.

Returns: 

The minimum in the input matrix, or IGRAPH_POSINFINITY if the matrix has zero elements.

Time complexity: TODO.

4.3.9. igraph_sparsemat_max — Maximum of a sparse matrix.

igraph_real_t igraph_sparsemat_max(igraph_sparsemat_t *A);

Arguments: 

A:

The input matrix, column-compressed.

Returns: 

The maximum in the input matrix, or IGRAPH_NEGINFINITY if the matrix has zero elements.

Time complexity: TODO.

4.3.10. igraph_sparsemat_minmax — Minimum and maximum of a sparse matrix.

igraph_error_t igraph_sparsemat_minmax(igraph_sparsemat_t *A,
                            igraph_real_t *min, igraph_real_t *max);

Arguments: 

A:

The input matrix, column-compressed.

min:

The minimum in the input matrix is stored here, or IGRAPH_POSINFINITY if the matrix has zero elements.

max:

The maximum in the input matrix is stored here, or IGRAPH_NEGINFINITY if the matrix has zero elements.

Returns: 

Error code.

Time complexity: TODO.

4.3.11. igraph_sparsemat_count_nonzero — Counts nonzero elements of a sparse matrix.

long int igraph_sparsemat_count_nonzero(igraph_sparsemat_t *A);

Arguments: 

A:

The input matrix, column-compressed.

Returns: 

Error code.

Time complexity: TODO.

4.3.12. igraph_sparsemat_count_nonzerotol — Counts nonzero elements of a sparse matrix, ignoring elements close to zero.

long int igraph_sparsemat_count_nonzerotol(igraph_sparsemat_t *A,
        igraph_real_t tol);

Count the number of matrix entries that are closer to zero than tol.

Arguments: 

The:

input matrix, column-compressed.

Real:

scalar, the tolerance.

Returns: 

Error code.

Time complexity: TODO.

4.3.13. igraph_sparsemat_rowsums — Row-wise sums.

igraph_error_t igraph_sparsemat_rowsums(const igraph_sparsemat_t *A,
                             igraph_vector_t *res);

Arguments: 

A:

The input matrix, in triplet or column-compressed format.

res:

An initialized vector, the result is stored here. It will be resized as needed.

Returns: 

Error code.

Time complexity: O(nz), the number of non-zero elements.

4.3.14. igraph_sparsemat_colsums — Column-wise sums.

igraph_error_t igraph_sparsemat_colsums(const igraph_sparsemat_t *A,
                             igraph_vector_t *res);

Arguments: 

A:

The input matrix, in triplet or column-compressed format.

res:

An initialized vector, the result is stored here. It will be resized as needed.

Returns: 

Error code.

Time complexity: O(nz) for triplet matrices, O(nz+n) for column-compressed ones, nz is the number of non-zero elements, n is the number of columns.

4.3.15. igraph_sparsemat_nonzero_storage — Returns number of stored entries of a sparse matrix.

igraph_integer_t igraph_sparsemat_nonzero_storage(const igraph_sparsemat_t *A);

This function will return the number of stored entries of a sparse matrix. These entries can be zero, and multiple entries can be at the same position. Use igraph_sparsemat_dupl() to sum duplicate entries, and igraph_sparsemat_dropzeros() to remove zeros.

Arguments: 

A:

A sparse matrix in either triplet or compressed form.

Returns: 

Number of stored entries.

Time complexity: O(1).

4.4. Operations on sparse matrices

4.4.1. igraph_sparsemat_entry — Adds an element to a sparse matrix.

igraph_error_t igraph_sparsemat_entry(igraph_sparsemat_t *A,
        igraph_integer_t row, igraph_integer_t col, igraph_real_t elem);

This function can be used to add the entries to a sparse matrix, after initializing it with igraph_sparsemat_init(). If you add multiple entries in the same position, they will all be saved, and the resulting value is the sum of all entries in that position.

Arguments: 

A:

The input matrix, it must be in triplet format.

row:

The row index of the entry to add.

col:

The column index of the entry to add.

elem:

The value of the entry.

Returns: 

Error code.

Time complexity: O(1) on average.

4.4.2. igraph_sparsemat_fkeep — Filters the elements of a sparse matrix.

igraph_error_t igraph_sparsemat_fkeep(
    igraph_sparsemat_t *A,
    igraph_integer_t (*fkeep)(igraph_integer_t, igraph_integer_t, igraph_real_t, void*),
    void *other
);

This function can be used to filter the (non-zero) elements of a sparse matrix. For all entries, it calls the supplied function and depending on the return values either keeps, or deleted the element from the matrix.

Arguments: 

A:

The input matrix, in column-compressed format.

fkeep:

The filter function. It must take four arguments: the first is an igraph_integer_t, the row index of the entry, the second is another igraph_integer_t, the column index. The third is igraph_real_t, the value of the entry. The fourth element is a void pointer, the other argument is passed here. The function must return an int. If this is zero, then the entry is deleted, otherwise it is kept.

other:

A void pointer that is passed to the filtering function.

Returns: 

Error code.

Time complexity: TODO.

4.4.3. igraph_sparsemat_dropzeros — Drops the zero elements from a sparse matrix.

igraph_error_t igraph_sparsemat_dropzeros(igraph_sparsemat_t *A);

As a result of matrix operations, some of the entries in a sparse matrix might be zero. This function removes these entries.

Arguments: 

A:

The input matrix, it must be in column-compressed format.

Returns: 

Error code.

Time complexity: TODO.

4.4.4. igraph_sparsemat_droptol — Drops the almost zero elements from a sparse matrix.

igraph_error_t igraph_sparsemat_droptol(igraph_sparsemat_t *A, igraph_real_t tol);

This function is similar to igraph_sparsemat_dropzeros(), but it also drops entries that are closer to zero than the given tolerance threshold.

Arguments: 

A:

The input matrix, it must be in column-compressed format.

tol:

Real number, giving the tolerance threshold.

Returns: 

Error code.

Time complexity: TODO.

4.4.5. igraph_sparsemat_scale — Scales a sparse matrix.

igraph_error_t igraph_sparsemat_scale(igraph_sparsemat_t *A, igraph_real_t by);

Multiplies all elements of a sparse matrix, by the given scalar.

Arguments: 

A:

The input matrix.

by:

The scaling factor.

Returns: 

Error code.

Time complexity: O(nz), the number of non-zero elements in the matrix.

4.4.6. igraph_sparsemat_permute — Permutes the rows and columns of a sparse matrix.

igraph_error_t igraph_sparsemat_permute(const igraph_sparsemat_t *A,
                                        const igraph_vector_int_t *p,
                                        const igraph_vector_int_t *q,
                                        igraph_sparsemat_t *res);

Arguments: 

A:

The input matrix, it must be in column-compressed format.

p:

Integer vector, giving the permutation of the rows.

q:

Integer vector, the permutation of the columns.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

Returns: 

Error code.

Time complexity: O(m+n+nz), the number of rows plus the number of columns plus the number of non-zero elements in the matrix.

4.4.7. igraph_sparsemat_transpose — Transposes a sparse matrix.

igraph_error_t igraph_sparsemat_transpose(const igraph_sparsemat_t *A,
                               igraph_sparsemat_t *res,
                               igraph_bool_t store_values);

Arguments: 

A:

The input matrix, column-compressed or triple format.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

values:

If this is non-zero, the matrix transpose is calculated the normal way. If it is zero, then only the pattern of the input matrix is stored in the result, the values are not.

Returns: 

Error code.

Time complexity: TODO.

4.4.8. igraph_sparsemat_add — Sum of two sparse matrices.

igraph_error_t igraph_sparsemat_add(const igraph_sparsemat_t *A,
                         const igraph_sparsemat_t *B,
                         igraph_real_t alpha,
                         igraph_real_t beta,
                         igraph_sparsemat_t *res);

Arguments: 

A:

The first input matrix, in column-compressed format.

B:

The second input matrix, in column-compressed format.

alpha:

Real scalar, A is multiplied by alpha before the addition.

beta:

Real scalar, B is multiplied by beta before the addition.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.4.9. igraph_sparsemat_multiply — Matrix multiplication.

igraph_error_t igraph_sparsemat_multiply(const igraph_sparsemat_t *A,
                              const igraph_sparsemat_t *B,
                              igraph_sparsemat_t *res);

Multiplies two sparse matrices.

Arguments: 

A:

The first input matrix (left hand side), in column-compressed format.

B:

The second input matrix (right hand side), in column-compressed format.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.4.10. igraph_sparsemat_gaxpy — Matrix-vector product, added to another vector.

igraph_error_t igraph_sparsemat_gaxpy(const igraph_sparsemat_t *A,
                           const igraph_vector_t *x,
                           igraph_vector_t *res);

Arguments: 

A:

The input matrix, in column-compressed format.

x:

The input vector, its size must match the number of columns in A.

res:

This vector is added to the matrix-vector product and it is overwritten by the result.

Returns: 

Error code.

Time complexity: TODO.

4.4.11. igraph_sparsemat_add_rows — Adds rows to a sparse matrix.

igraph_error_t igraph_sparsemat_add_rows(igraph_sparsemat_t *A, igraph_integer_t n);

The current matrix elements are retained and all elements in the new rows are zero.

Arguments: 

A:

The input matrix, in triplet or column-compressed format.

n:

The number of rows to add.

Returns: 

Error code.

Time complexity: O(1).

4.4.12. igraph_sparsemat_add_cols — Adds columns to a sparse matrix.

igraph_error_t igraph_sparsemat_add_cols(igraph_sparsemat_t *A, igraph_integer_t n);

The current matrix elements are retained, and all elements in the new columns are zero.

Arguments: 

A:

The input matrix, in triplet or column-compressed format.

n:

The number of columns to add.

Returns: 

Error code.

Time complexity: TODO.

4.4.13. igraph_sparsemat_resize — Resizes a sparse matrix.

igraph_error_t igraph_sparsemat_resize(igraph_sparsemat_t *A, igraph_integer_t nrow,
                            igraph_integer_t ncol, igraph_integer_t nzmax);

This function resizes a sparse matrix. The resized sparse matrix will be empty.

Arguments: 

A:

The initialized sparse matrix to resize.

nrow:

The new number of rows.

ncol:

The new number of columns.

nzmax:

The new maximum number of elements.

Returns: 

Error code.

Time complexity: O(nzmax), the maximum number of non-zero elements.

4.5. Operations on sparse matrix iterators

4.5.1. igraph_sparsemat_iterator_init — Initialize a sparse matrix iterator.

igraph_error_t igraph_sparsemat_iterator_init(
    igraph_sparsemat_iterator_t *it, igraph_sparsemat_t *sparsemat);

Arguments: 

it:

A pointer to an uninitialized sparse matrix iterator.

sparsemat:

Pointer to the sparse matrix.

Returns: 

Error code. This will always return IGRAPH_SUCCESS

Time complexity: O(n), the number of columns of the sparse matrix.

4.5.2. igraph_sparsemat_iterator_reset — Reset a sparse matrix iterator to the first element.

igraph_error_t igraph_sparsemat_iterator_reset(igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

Error code. This will always return IGRAPH_SUCCESS

Time complexity: O(n), the number of columns of the sparse matrix.

4.5.3. igraph_sparsemat_iterator_end — Query if the iterator is past the last element.

igraph_bool_t
igraph_sparsemat_iterator_end(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

true if the iterator is past the last element, false if it points to an element in a sparse matrix.

Time complexity: O(1).

4.5.4. igraph_sparsemat_iterator_row — Return the row of the iterator.

igraph_integer_t igraph_sparsemat_iterator_row(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The row of the element at the current iterator position.

Time complexity: O(1).

4.5.5. igraph_sparsemat_iterator_col — Return the column of the iterator.

igraph_integer_t igraph_sparsemat_iterator_col(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The column of the element at the current iterator position.

Time complexity: O(1).

4.5.6. igraph_sparsemat_iterator_get — Return the element at the current iterator position.

igraph_real_t
igraph_sparsemat_iterator_get(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The value of the element at the current iterator position.

Time complexity: O(1).

4.5.7. igraph_sparsemat_iterator_next — Let a sparse matrix iterator go to the next element.

igraph_integer_t igraph_sparsemat_iterator_next(igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The position of the iterator in the element vector.

Time complexity: O(n), the number of columns of the sparse matrix.

4.5.8. igraph_sparsemat_iterator_idx — Returns the element vector index of a sparse matrix iterator.

igraph_integer_t igraph_sparsemat_iterator_idx(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The position of the iterator in the element vector.

Time complexity: O(1).

4.6. Operations that change the internal representation

4.6.1. igraph_sparsemat_compress — Converts a sparse matrix to column-compressed format.

igraph_error_t igraph_sparsemat_compress(const igraph_sparsemat_t *A,
                              igraph_sparsemat_t *res);

Converts a sparse matrix from triplet format to column-compressed format. Almost all sparse matrix operations require that the matrix is in column-compressed format.

Arguments: 

A:

The input matrix, it must be in triplet format.

res:

Pointer to an uninitialized sparse matrix object, the compressed version of A is stored here.

Returns: 

Error code.

Time complexity: O(nz) where nz is the number of non-zero elements.

4.6.2. igraph_sparsemat_dupl — Removes duplicate elements from a sparse matrix.

igraph_error_t igraph_sparsemat_dupl(igraph_sparsemat_t *A);

It is possible that a column-compressed sparse matrix stores a single matrix entry in multiple pieces. The entry is then the sum of all its pieces. (Some functions create matrices like this.) This function eliminates the multiple pieces.

Arguments: 

A:

The input matrix, in column-compressed format.

Returns: 

Error code.

Time complexity: TODO.

4.7. Decompositions and solving linear systems

4.7.1. igraph_sparsemat_symblu — Symbolic LU decomposition.

igraph_error_t igraph_sparsemat_symblu(long int order, const igraph_sparsemat_t *A,
                            igraph_sparsemat_symbolic_t *dis);

LU decomposition of sparse matrices involves two steps, the first is calling this function, and then igraph_sparsemat_lu().

Arguments: 

order:

The ordering to use: 0 means natural ordering, 1 means minimum degree ordering of A+A', 2 is minimum degree ordering of A'A after removing the dense rows from A, and 3 is the minimum degree ordering of A'A.

A:

The input matrix, in column-compressed format.

dis:

The result of the symbolic analysis is stored here. Once not needed anymore, it must be destroyed by calling igraph_sparsemat_symbolic_destroy().

Returns: 

Error code.

Time complexity: TODO.

4.7.2. igraph_sparsemat_symbqr — Symbolic QR decomposition.

igraph_error_t igraph_sparsemat_symbqr(long int order, const igraph_sparsemat_t *A,
                            igraph_sparsemat_symbolic_t *dis);

QR decomposition of sparse matrices involves two steps, the first is calling this function, and then igraph_sparsemat_qr().

Arguments: 

order:

The ordering to use: 0 means natural ordering, 1 means minimum degree ordering of A+A', 2 is minimum degree ordering of A'A after removing the dense rows from A, and 3 is the minimum degree ordering of A'A.

A:

The input matrix, in column-compressed format.

dis:

The result of the symbolic analysis is stored here. Once not needed anymore, it must be destroyed by calling igraph_sparsemat_symbolic_destroy().

Returns: 

Error code.

Time complexity: TODO.

4.7.3. igraph_sparsemat_lsolve — Solves a lower-triangular linear system.

igraph_error_t igraph_sparsemat_lsolve(const igraph_sparsemat_t *L,
                            const igraph_vector_t *b,
                            igraph_vector_t *res);

Solve the Lx=b linear equation system, where the L coefficient matrix is square and lower-triangular, with a zero-free diagonal.

Arguments: 

L:

The input matrix, in column-compressed format.

b:

The right hand side of the linear system.

res:

An initialized vector, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.7.4. igraph_sparsemat_ltsolve — Solves an upper-triangular linear system.

igraph_error_t igraph_sparsemat_ltsolve(const igraph_sparsemat_t *L,
                             const igraph_vector_t *b,
                             igraph_vector_t *res);

Solve the L'x=b linear equation system, where the L matrix is square and lower-triangular, with a zero-free diagonal.

Arguments: 

L:

The input matrix, in column-compressed format.

b:

The right hand side of the linear system.

res:

An initialized vector, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.7.5. igraph_sparsemat_usolve — Solves an upper-triangular linear system.

igraph_error_t igraph_sparsemat_usolve(const igraph_sparsemat_t *U,
                            const igraph_vector_t *b,
                            igraph_vector_t *res);

Solves the Ux=b upper triangular system.

Arguments: 

U:

The input matrix, in column-compressed format.

b:

The right hand side of the linear system.

res:

An initialized vector, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.7.6. igraph_sparsemat_utsolve — Solves a lower-triangular linear system.

igraph_error_t igraph_sparsemat_utsolve(const igraph_sparsemat_t *U,
                             const igraph_vector_t *b,
                             igraph_vector_t *res);

This is the same as igraph_sparsemat_usolve(), but U'x=b is solved, where the apostrophe denotes the transpose.

Arguments: 

U:

The input matrix, in column-compressed format.

b:

The right hand side of the linear system.

res:

An initialized vector, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.7.7. igraph_sparsemat_cholsol — Solves a symmetric linear system via Cholesky decomposition.

igraph_error_t igraph_sparsemat_cholsol(const igraph_sparsemat_t *A,
                             const igraph_vector_t *b,
                             igraph_vector_t *res,
                             int order);

Solve Ax=b, where A is a symmetric positive definite matrix.

Arguments: 

A:

The input matrix, in column-compressed format.

v:

The right hand side.

res:

An initialized vector, the result is stored here.

order:

An integer giving the ordering method to use for the factorization. Zero is the natural ordering; if it is one, then the fill-reducing minimum-degree ordering of A+A' is used.

Returns: 

Error code.

Time complexity: TODO.

4.7.8. igraph_sparsemat_lusol — Solves a linear system via LU decomposition.

igraph_error_t igraph_sparsemat_lusol(const igraph_sparsemat_t *A,
                           const igraph_vector_t *b,
                           igraph_vector_t *res,
                           int order,
                           igraph_real_t tol);

Solve Ax=b, via LU factorization of A.

Arguments: 

A:

The input matrix, in column-compressed format.

b:

The right hand side of the equation.

res:

An initialized vector, the result is stored here.

order:

The ordering method to use, zero means the natural ordering, one means the fill-reducing minimum-degree ordering of A+A', two means the ordering of A'*A, after removing the dense rows from A. Three means the ordering of A'*A.

tol:

Real number, the tolerance limit to use for the numeric LU factorization.

Returns: 

Error code.

Time complexity: TODO.

4.7.9. igraph_sparsemat_lu — LU decomposition of a sparse matrix.

igraph_error_t igraph_sparsemat_lu(const igraph_sparsemat_t *A,
                        const igraph_sparsemat_symbolic_t *dis,
                        igraph_sparsemat_numeric_t *din, double tol);

Performs numeric sparse LU decomposition of a matrix.

Arguments: 

A:

The input matrix, in column-compressed format.

dis:

The symbolic analysis for LU decomposition, coming from a call to the igraph_sparsemat_symblu() function.

din:

The numeric decomposition, the result is stored here. It can be used to solve linear systems with changing right hand side vectors, by calling igraph_sparsemat_luresol(). Once not needed any more, it must be destroyed by calling igraph_sparsemat_symbolic_destroy() on it.

tol:

The tolerance for the numeric LU decomposition.

Returns: 

Error code.

Time complexity: TODO.

4.7.10. igraph_sparsemat_qr — QR decomposition of a sparse matrix.

igraph_error_t igraph_sparsemat_qr(const igraph_sparsemat_t *A,
                        const igraph_sparsemat_symbolic_t *dis,
                        igraph_sparsemat_numeric_t *din);

Numeric QR decomposition of a sparse matrix.

Arguments: 

A:

The input matrix, in column-compressed format.

dis:

The result of the symbolic QR analysis, from the function igraph_sparsemat_symbqr().

din:

The result of the decomposition is stored here, it can be used to solve many linear systems with the same coefficient matrix and changing right hand sides, using the igraph_sparsemat_qrresol() function. Once not needed any more, one should call igraph_sparsemat_numeric_destroy() on it to free the allocated memory.

Returns: 

Error code.

Time complexity: TODO.

4.7.11. igraph_sparsemat_luresol — Solves a linear system using a precomputed LU decomposition.

igraph_error_t igraph_sparsemat_luresol(const igraph_sparsemat_symbolic_t *dis,
                             const igraph_sparsemat_numeric_t *din,
                             const igraph_vector_t *b,
                             igraph_vector_t *res);

Uses the LU decomposition of a matrix to solve linear systems.

Arguments: 

dis:

The symbolic analysis of the coefficient matrix, the result of igraph_sparsemat_symblu().

din:

The LU decomposition, the result of a call to igraph_sparsemat_lu().

b:

A vector that defines the right hand side of the linear equation system.

res:

An initialized vector, the solution of the linear system is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.7.12. igraph_sparsemat_qrresol — Solves a linear system using a precomputed QR decomposition.

igraph_error_t igraph_sparsemat_qrresol(const igraph_sparsemat_symbolic_t *dis,
                             const igraph_sparsemat_numeric_t *din,
                             const igraph_vector_t *b,
                             igraph_vector_t *res);

Solves a linear system using a QR decomposition of its coefficient matrix.

Arguments: 

dis:

Symbolic analysis of the coefficient matrix, the result of igraph_sparsemat_symbqr().

din:

The QR decomposition of the coefficient matrix, the result of igraph_sparsemat_qr().

b:

Vector, giving the right hand side of the linear equation system.

res:

An initialized vector, the solution is stored here. It is resized as needed.

Returns: 

Error code.

Time complexity: TODO.

4.7.13. igraph_sparsemat_symbolic_destroy — Deallocates memory after a symbolic decomposition.

void igraph_sparsemat_symbolic_destroy(igraph_sparsemat_symbolic_t *dis);

Frees the memory allocated by igraph_sparsemat_symbqr() or igraph_sparsemat_symblu().

Arguments: 

dis:

The symbolic analysis.

Time complexity: O(1).

4.7.14. igraph_sparsemat_numeric_destroy — Deallocates memory after a numeric decomposition.

void igraph_sparsemat_numeric_destroy(igraph_sparsemat_numeric_t *din);

Frees the memoty allocated by igraph_sparsemat_qr() or igraph_sparsemat_lu().

Arguments: 

din:

The LU or QR decomposition.

Time complexity: O(1).

4.8. Eigenvalues and eigenvectors

4.8.1. igraph_sparsemat_arpack_rssolve — Eigenvalues and eigenvectors of a symmetric sparse matrix via ARPACK.

igraph_error_t igraph_sparsemat_arpack_rssolve(const igraph_sparsemat_t *A,
                                    igraph_arpack_options_t *options,
                                    igraph_arpack_storage_t *storage,
                                    igraph_vector_t *values,
                                    igraph_matrix_t *vectors,
                                    igraph_sparsemat_solve_t solvemethod);

Arguments: 

The:

input matrix, must be column-compressed.

options:

It is passed to igraph_arpack_rssolve(). See igraph_arpack_options_t for the details. If mode is 1, then ARPACK uses regular mode, if mode is 3, then shift and invert mode is used and the sigma structure member defines the shift.

storage:

Storage for ARPACK. See igraph_arpack_rssolve() and igraph_arpack_storage_t for details.

values:

An initialized vector or a null pointer, the eigenvalues are stored here.

vectors:

An initialised matrix, or a null pointer, the eigenvectors are stored here, in the columns.

solvemethod:

The method to solve the linear system, if mode is 3, i.e. the shift and invert mode is used. Possible values:

IGRAPH_SPARSEMAT_SOLVE_LU

The linear system is solved using LU decomposition.

IGRAPH_SPARSEMAT_SOLVE_QR

The linear system is solved using QR decomposition.

Returns: 

Error code.

Time complexity: TODO.

4.8.2. igraph_sparsemat_arpack_rnsolve — Eigenvalues and eigenvectors of a nonsymmetric sparse matrix via ARPACK.

igraph_error_t igraph_sparsemat_arpack_rnsolve(const igraph_sparsemat_t *A,
                                    igraph_arpack_options_t *options,
                                    igraph_arpack_storage_t *storage,
                                    igraph_matrix_t *values,
                                    igraph_matrix_t *vectors);

Eigenvalues and/or eigenvectors of a nonsymmetric sparse matrix.

Arguments: 

A:

The input matrix, in column-compressed mode.

options:

ARPACK options, it is passed to igraph_arpack_rnsolve(). See also igraph_arpack_options_t for details.

storage:

Storage for ARPACK, this is passed to igraph_arpack_rnsolve(). See igraph_arpack_storage_t for details.

values:

An initialized matrix, or a null pointer. If not a null pointer, then the eigenvalues are stored here, the first column is the real part, the second column is the imaginary part.

vectors:

An initialized matrix, or a null pointer. If not a null pointer, then the eigenvectors are stored here, please see igraph_arpack_rnsolve() for the format.

Returns: 

Error code.

Time complexity: TODO.

4.9. Conversion to other data types

4.9.1. igraph_sparsemat — Creates an igraph graph from a sparse matrix.

igraph_error_t igraph_sparsemat(igraph_t *graph, const igraph_sparsemat_t *A,
                     igraph_bool_t directed);

One edge is created for each non-zero entry in the matrix. If you have a symmetric matrix, and want to create an undirected graph, then delete the entries in the upper diagonal first, or call igraph_simplify() on the result graph to eliminate the multiple edges.

Arguments: 

graph:

Pointer to an uninitialized igraph_t object, the graphs is stored here.

A:

The input matrix, in triplet or column-compressed format.

directed:

Boolean scalar, whether to create a directed graph.

Returns: 

Error code.

Time complexity: TODO.

4.9.2. igraph_matrix_as_sparsemat — Converts a dense matrix to a sparse matrix.

igraph_error_t igraph_matrix_as_sparsemat(igraph_sparsemat_t *res,
                               const igraph_matrix_t *mat,
                               igraph_real_t tol);

Arguments: 

res:

An uninitialized sparse matrix, the result is stored here.

mat:

The dense input matrix.

tol:

Real scalar, the tolerance. Values closer than tol to zero are considered as zero, and will not be included in the sparse matrix.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the dense matrix.

4.9.3. igraph_sparsemat_as_matrix — Converts a sparse matrix to a dense matrix.

igraph_error_t igraph_sparsemat_as_matrix(igraph_matrix_t *res,
                               const igraph_sparsemat_t *spmat);

Arguments: 

res:

Pointer to an initialized matrix, the result is stored here. It will be resized to the required size.

spmat:

The input sparse matrix, in triplet or column-compressed format.

Returns: 

Error code.

Time complexity: O(mn), the number of elements in the dense matrix.

4.10. Writing to a file, or to the screen

4.10.1. igraph_sparsemat_print — Prints a sparse matrix to a file.

igraph_error_t igraph_sparsemat_print(const igraph_sparsemat_t *A,
                           FILE *outstream);

Only the non-zero entries are printed. This function serves more as a debugging utility, as currently there is no function that could read back the printed matrix from the file.

Arguments: 

A:

The input matrix, triplet or column-compressed format.

outstream:

The stream to print it to.

Returns: 

Error code.

Time complexity: O(nz) for triplet matrices, O(n+nz) for column-compressed matrices. nz is the number of non-zero elements, n is the number columns in the matrix.

5. Sparse matrices (deprecated variant)

Warning

All the functions and data types described in this section are deprecated from igraph 0.10. Do not use them in new code. They will be removed in igraph 0.11 or igraph 1.0, whichever comes first. Replacements to the functions are provided in the documentation below where a replacement exists.

5.1.  About igraph_spmatrix_t objects

The igraph_spmatrix_t type stores a sparse matrix with the assumption that the number of nonzero elements in the matrix scales linearly with the row or column count of the matrix (so most of the elements are zero). Of course it can store an arbitrary real matrix, but if most of the elements are nonzero, one should use igraph_matrix_t instead.

The elements are stored in column compressed format, so the elements in the same column are stored adjacent in the computer's memory. The storage requirement for a sparse matrix is O(n) where n is the number of nonzero elements. Actually it can be a bit larger, see the documentation of the vector type for an explanation.

5.2.  Sparse matrix constructors and destructors.

5.2.1. igraph_spmatrix_init — Initializes a sparse matrix.

igraph_error_t igraph_spmatrix_init(igraph_spmatrix_t *m, igraph_integer_t nrow, igraph_integer_t ncol);

Every sparse matrix needs to be initialized before using it, this is done by calling this function. A matrix has to be destroyed if it is not needed any more, see igraph_spmatrix_destroy().

Arguments: 

m:

Pointer to a not yet initialized sparse matrix object to be initialized.

nrow:

The number of rows in the matrix.

ncol:

The number of columns in the matrix.

Returns: 

Error code.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_init() instead.

Time complexity: operating system dependent.

5.2.2. igraph_spmatrix_copy — Copies a sparse matrix.

igraph_error_t igraph_spmatrix_copy(igraph_spmatrix_t *to, const igraph_spmatrix_t *from);

Creates a sparse matrix object by copying another one.

Arguments: 

to:

Pointer to an uninitialized sparse matrix object.

from:

The initialized sparse matrix object to copy.

Returns: 

Error code, IGRAPH_ENOMEM if there isn't enough memory to allocate the new sparse matrix.

Time complexity: O(n), the number of elements in the matrix.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_copy() instead.

5.2.3. igraph_spmatrix_destroy — Destroys a sparse matrix object.

void igraph_spmatrix_destroy(igraph_spmatrix_t *m);

This function frees all the memory allocated for a sparse matrix object. The destroyed object needs to be reinitialized before using it again.

Arguments: 

m:

The matrix to destroy.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_destroy() instead.

Time complexity: operating system dependent.

5.3.  Accessing elements of a sparse matrix

5.3.1. igraph_spmatrix_e — Accessing an element of a sparse matrix.

igraph_real_t igraph_spmatrix_e(const igraph_spmatrix_t *m,
                                igraph_integer_t row, igraph_integer_t col);

Note that there are no range checks right now.

Arguments: 

m:

The matrix object.

row:

The index of the row, starting with zero.

col:

The index of the column, starting with zero.

Time complexity: O(log n), where n is the number of nonzero elements in the requested column.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_index() instead.

5.3.2. igraph_spmatrix_set — Setting an element of a sparse matrix.

igraph_error_t igraph_spmatrix_set(igraph_spmatrix_t *m, igraph_integer_t row, igraph_integer_t col,
                        igraph_real_t value);

Note that there are no range checks right now.

Arguments: 

m:

The matrix object.

row:

The index of the row, starting with zero.

col:

The index of the column, starting with zero.

value:

The new value.

Time complexity: O(log n), where n is the number of nonzero elements in the requested column.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_entry() instead.

5.3.3. igraph_spmatrix_add_e — Adding a real value to an element of a sparse matrix.

igraph_error_t igraph_spmatrix_add_e(igraph_spmatrix_t *m, igraph_integer_t row, igraph_integer_t col,
                          igraph_real_t value);

Note that there are no range checks right now. This is implemented to avoid double lookup of a given element in the matrix by using igraph_spmatrix_e() and igraph_spmatrix_set() consecutively.

Arguments: 

m:

The matrix object.

row:

The index of the row, starting with zero.

col:

The index of the column, starting with zero.

value:

The value to add.

Time complexity: O(log n), where n is the number of nonzero elements in the requested column.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_entry() instead.

5.4.  Iterating over the non-zero elements of a sparse matrix

The igraph_spmatrix_iter_t type represents an iterator that can be used to step over the non-zero elements of a sparse matrix in columnwise order efficiently. In general, you shouldn't modify the elements of the matrix while iterating over it; doing so will probably invalidate the iterator, but there are no checks to prevent you from doing this.

To access the row index of the current element of the iterator, use its ri field. Similarly, the ci field stores the column index of the current element and the value field stores the value of the element.

5.4.1. igraph_spmatrix_iter_create — Creates a sparse matrix iterator corresponding to the given matrix.

igraph_error_t igraph_spmatrix_iter_create(igraph_spmatrix_iter_t *mit, const igraph_spmatrix_t *m);

Arguments: 

mit:

pointer to the matrix iterator being initialized

m:

pointer to the matrix we will be iterating over

Returns: 

Error code. The current implementation is always successful.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_iterator_init() instead.

5.4.2. igraph_spmatrix_iter_reset — Resets a sparse matrix iterator.

igraph_error_t igraph_spmatrix_iter_reset(igraph_spmatrix_iter_t *mit);

After resetting, the iterator will point to the first nonzero element (if any).

Arguments: 

mit:

pointer to the matrix iterator being reset

Returns: 

Error code. The current implementation is always successful.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_iterator_reset() instead.

5.4.3. igraph_spmatrix_iter_next — Moves a sparse matrix iterator to the next nonzero element.

igraph_error_t igraph_spmatrix_iter_next(igraph_spmatrix_iter_t *mit);

You should call this function only if igraph_spmatrix_iter_end() returns FALSE (0).

Arguments: 

mit:

pointer to the matrix iterator being moved

Returns: 

Error code. The current implementation is always successful.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_iterator_next() instead.

5.4.4. igraph_spmatrix_iter_end — Checks whether there are more elements in the iterator.

igraph_bool_t igraph_spmatrix_iter_end(igraph_spmatrix_iter_t *mit);

You should call this function before calling igraph_spmatrix_iter_next() to make sure you have more elements in the iterator.

Arguments: 

mit:

pointer to the matrix iterator being checked

Returns: 

TRUE (1) if there are more elements in the iterator, FALSE (0) otherwise.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_iterator_end() instead.

5.4.5. igraph_spmatrix_iter_destroy — Frees the memory used by the iterator.

void igraph_spmatrix_iter_destroy(igraph_spmatrix_iter_t *mit);

The current implementation does not allocate any memory upon creation, so this function does nothing. However, since there is no guarantee that future implementations will not allocate any memory in igraph_spmatrix_iter_create(), you are still required to call this function whenever you are done with the iterator.

Arguments: 

mit:

pointer to the matrix iterator being destroyed

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code.

5.5. Matrix query operations

5.5.1. igraph_spmatrix_size — The number of elements in a sparse matrix.

igraph_integer_t igraph_spmatrix_size(const igraph_spmatrix_t *m);

Arguments: 

m:

Pointer to an initialized sparse matrix object.

Returns: 

The size of the matrix.

Time complexity: O(1).

5.5.2. igraph_spmatrix_nrow — The number of rows in a sparse matrix.

igraph_integer_t igraph_spmatrix_nrow(const igraph_spmatrix_t *m);

Arguments: 

m:

Pointer to an initialized sparse matrix object.

Returns: 

The number of rows in the matrix.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_nrow() instead.

5.5.3. igraph_spmatrix_ncol — The number of columns in a sparse matrix.

igraph_integer_t igraph_spmatrix_ncol(const igraph_spmatrix_t *m);

Arguments: 

m:

Pointer to an initialized sparse matrix object.

Returns: 

The number of columns in the sparse matrix.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_ncol() instead.

5.5.4. igraph_spmatrix_count_nonzero — The number of non-zero elements in a sparse matrix.

igraph_integer_t igraph_spmatrix_count_nonzero(const igraph_spmatrix_t *m);

Arguments: 

m:

Pointer to an initialized sparse matrix object.

Returns: 

The size of the matrix.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_count_nonzero() instead.

5.5.5. igraph_spmatrix_max — Returns the maximum element of a matrix.

igraph_real_t igraph_spmatrix_max(const igraph_spmatrix_t *m,
                                  igraph_real_t *ridx, igraph_real_t *cidx);

If the matrix is empty, zero is returned.

Arguments: 

m:

the matrix object.

ridx:

the row index of the maximum element if not NULL.

cidx:

the column index of the maximum element if not NULL.

Time complexity: O(n), the number of nonzero elements in the matrix.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code.

5.5.6. igraph_spmatrix_rowsums — Calculates the row sums of the matrix.

igraph_error_t igraph_spmatrix_rowsums(const igraph_spmatrix_t *m, igraph_vector_t *res);

Arguments: 

m:

The matrix.

res:

An initialized igraph_vector_t, the result will be stored here. The vector will be resized as needed.

Time complexity: O(n), the number of nonzero elements in the matrix.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_rowsums() instead.

5.5.7. igraph_spmatrix_colsums — Calculates the column sums of the matrix.

igraph_error_t igraph_spmatrix_colsums(const igraph_spmatrix_t *m, igraph_vector_t *res);

Arguments: 

m:

The matrix.

res:

An initialized igraph_vector_t, the result will be stored here. The vector will be resized as needed.

Time complexity: O(n), the number of nonzero elements in the matrix.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_colsums() instead.

5.6. Matrix operations

5.6.1. igraph_spmatrix_scale — Multiplies each element of the sparse matrix by a constant.

void igraph_spmatrix_scale(igraph_spmatrix_t *m, igraph_real_t by);

Arguments: 

m:

The matrix.

by:

The constant.

Time complexity: O(n), the number of elements in the matrix.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_scale() instead.

5.6.2. igraph_spmatrix_add_rows — Adds rows to a sparse matrix.

igraph_error_t igraph_spmatrix_add_rows(igraph_spmatrix_t *m, igraph_integer_t n);

Arguments: 

m:

The sparse matrix object.

n:

The number of rows to add.

Returns: 

Error code.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_add_rows() instead.

5.6.3. igraph_spmatrix_add_cols — Adds columns to a sparse matrix.

igraph_error_t igraph_spmatrix_add_cols(igraph_spmatrix_t *m, igraph_integer_t n);

Arguments: 

m:

The sparse matrix object.

n:

The number of columns to add.

Returns: 

Error code.

Time complexity: O(1).

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_add_cols() instead.

5.6.4. igraph_spmatrix_resize — Resizes a sparse matrix.

igraph_error_t igraph_spmatrix_resize(igraph_spmatrix_t *m, igraph_integer_t nrow, igraph_integer_t ncol);

This function resizes a sparse matrix by adding more elements to it. The matrix retains its data even after resizing it, except for the data which lies outside the new boundaries (if the new size is smaller).

Arguments: 

m:

Pointer to an already initialized sparse matrix object.

nrow:

The number of rows in the resized matrix.

ncol:

The number of columns in the resized matrix.

Returns: 

Error code.

Time complexity: O(n). n is the number of elements in the old matrix.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_resize() instead.

5.7. Printing sparse matrices

5.7.1. igraph_spmatrix_print — Prints a sparse matrix.

igraph_error_t igraph_spmatrix_print(const igraph_spmatrix_t* matrix);

Prints a sparse matrix to the standard output. Only the non-zero entries are printed.

Returns: 

Error code.

Time complexity: O(n), the number of non-zero elements.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_print() instead.

5.7.2. igraph_spmatrix_fprint — Prints a sparse matrix to the given file.

igraph_error_t igraph_spmatrix_fprint(const igraph_spmatrix_t* matrix, FILE *file);

Prints a sparse matrix to the given file. Only the non-zero entries are printed.

Returns: 

Error code.

Time complexity: O(n), the number of non-zero elements.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_sparsemat_print() instead.

6. Stacks

6.1. igraph_stack_init — Initializes a stack.

igraph_error_t igraph_stack_init(igraph_stack_t* s, igraph_integer_t size);

The initialized stack is always empty.

Arguments: 

s:

Pointer to an uninitialized stack.

size:

The number of elements to allocate memory for.

Returns: 

Error code.

Time complexity: O(size).

6.2. igraph_stack_destroy — Destroys a stack object.

void igraph_stack_destroy(igraph_stack_t* s);

Deallocate the memory used for a stack. It is possible to reinitialize a destroyed stack again by igraph_stack_init().

Arguments: 

s:

The stack to destroy.

Time complexity: O(1).

6.3. igraph_stack_reserve — Reserve memory.

igraph_error_t igraph_stack_reserve(igraph_stack_t* s, igraph_integer_t size);

Reserve memory for future use. The actual size of the stack is unchanged.

Arguments: 

s:

The stack object.

size:

The number of elements to reserve memory for. If it is not bigger than the current size then nothing happens.

Returns: 

Error code.

Time complexity: should be around O(n), the new allocated size of the stack.

6.4. igraph_stack_empty — Decides whether a stack object is empty.

igraph_bool_t igraph_stack_empty(igraph_stack_t* s);

Arguments: 

s:

The stack object.

Returns: 

Boolean, TRUE if the stack is empty, FALSE otherwise.

Time complexity: O(1).

6.5. igraph_stack_size — Returns the number of elements in a stack.

igraph_integer_t igraph_stack_size(const igraph_stack_t* s);

Arguments: 

s:

The stack object.

Returns: 

The number of elements in the stack.

Time complexity: O(1).

6.6. igraph_stack_clear — Removes all elements from a stack.

void igraph_stack_clear(igraph_stack_t* s);

Arguments: 

s:

The stack object.

Time complexity: O(1).

6.7. igraph_stack_push — Places an element on the top of a stack.

igraph_error_t igraph_stack_push(igraph_stack_t* s, igraph_real_t elem);

The capacity of the stack is increased, if needed.

Arguments: 

s:

The stack object.

elem:

The element to push.

Returns: 

Error code.

Time complexity: O(1) is no reallocation is needed, O(n) otherwise, but it is ensured that n push operations are performed in O(n) time.

6.8. igraph_stack_pop — Removes and returns an element from the top of a stack.

igraph_real_t igraph_stack_pop(igraph_stack_t* s);

The stack must contain at least one element, call igraph_stack_empty() to make sure of this.

Arguments: 

s:

The stack object.

Returns: 

The removed top element.

Time complexity: O(1).

6.9. igraph_stack_top — Query top element.

igraph_real_t igraph_stack_top(const igraph_stack_t* s);

Returns the top element of the stack, without removing it. The stack must be non-empty.

Arguments: 

s:

The stack.

Returns: 

The top element.

Time complexity: O(1).

7. Double-ended queues

This is the classic data type of the double ended queue. Most of the time it is used if a First-In-First-Out (FIFO) behavior is needed. See the operations below.

Example 7.11.  File examples/simple/dqueue.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

int main() {

    igraph_dqueue_t q;
    int i;

    /* igraph_dqueue_init, igraph_dqueue_destroy, igraph_dqueue_empty */
    igraph_dqueue_init(&q, 5);
    if (!igraph_dqueue_empty(&q)) {
        return 1;
    }
    igraph_dqueue_destroy(&q);

    /* igraph_dqueue_push, igraph_dqueue_pop */
    igraph_dqueue_init(&q, 4);
    igraph_dqueue_push(&q, 1);
    igraph_dqueue_push(&q, 2);
    igraph_dqueue_push(&q, 3);
    igraph_dqueue_push(&q, 4);
    if (igraph_dqueue_pop(&q) != 1) {
        return 2;
    }
    if (igraph_dqueue_pop(&q) != 2) {
        return 3;
    }
    if (igraph_dqueue_pop(&q) != 3) {
        return 4;
    }
    if (igraph_dqueue_pop(&q) != 4) {
        return 5;
    }
    igraph_dqueue_destroy(&q);

    /* igraph_dqueue_clear, igraph_dqueue_size */
    igraph_dqueue_init(&q, 0);
    if (igraph_dqueue_size(&q) != 0) {
        return 6;
    }
    igraph_dqueue_clear(&q);
    if (igraph_dqueue_size(&q) != 0) {
        return 7;
    }
    for (i = 0; i < 10; i++) {
        igraph_dqueue_push(&q, i);
    }
    igraph_dqueue_clear(&q);
    if (igraph_dqueue_size(&q) != 0) {
        return 8;
    }
    igraph_dqueue_destroy(&q);

    /* TODO: igraph_dqueue_full */

    /* igraph_dqueue_head, igraph_dqueue_back, igraph_dqueue_pop_back */
    igraph_dqueue_init(&q, 0);
    for (i = 0; i < 10; i++) {
        igraph_dqueue_push(&q, i);
    }
    for (i = 0; i < 10; i++) {
        if (igraph_dqueue_head(&q) != 0) {
            return 9;
        }
        if (igraph_dqueue_back(&q) != 9 - i) {
            return 10;
        }
        if (igraph_dqueue_pop_back(&q) != 9 - i) {
            return 11;
        }
    }
    igraph_dqueue_destroy(&q);

    /* print */
    igraph_dqueue_init(&q, 4);
    igraph_dqueue_push(&q, 1);
    igraph_dqueue_push(&q, 2);
    igraph_dqueue_push(&q, 3);
    igraph_dqueue_push(&q, 4);
    igraph_dqueue_pop(&q);
    igraph_dqueue_pop(&q);
    igraph_dqueue_push(&q, 5);
    igraph_dqueue_push(&q, 6);
    igraph_dqueue_print(&q);

    igraph_dqueue_clear(&q);
    igraph_dqueue_print(&q);

    igraph_dqueue_destroy(&q);

    if (IGRAPH_FINALLY_STACK_SIZE() != 0) {
        return 12;
    }

    return 0;
}


7.1. igraph_dqueue_init — Initialize a double ended queue (deque).

igraph_error_t igraph_dqueue_init(igraph_dqueue_t* q, igraph_integer_t size);

The queue will be always empty.

Arguments: 

q:

Pointer to an uninitialized deque.

size:

How many elements to allocate memory for.

Returns: 

Error code.

Time complexity: O(size).

7.2. igraph_dqueue_destroy — Destroy a double ended queue.

void igraph_dqueue_destroy(igraph_dqueue_t* q);

Arguments: 

q:

The queue to destroy

Time complexity: O(1).

7.3. igraph_dqueue_empty — Decide whether the queue is empty.

igraph_bool_t igraph_dqueue_empty(const igraph_dqueue_t* q);

Arguments: 

q:

The queue.

Returns: 

Boolean, TRUE if q contains at least one element, FALSE otherwise.

Time complexity: O(1).

7.4. igraph_dqueue_full — Check whether the queue is full.

igraph_bool_t igraph_dqueue_full(igraph_dqueue_t* q);

If a queue is full the next igraph_dqueue_push() operation will allocate more memory.

Arguments: 

q:

The queue.

Returns: 

TRUE if q is full, FALSE otherwise.

Time complecity: O(1).

7.5. igraph_dqueue_clear — Remove all elements from the queue.

void igraph_dqueue_clear(igraph_dqueue_t* q);

Arguments: 

q:

The queue

Time complexity: O(1).

7.6. igraph_dqueue_size — Number of elements in the queue.

igraph_integer_t igraph_dqueue_size(const igraph_dqueue_t* q);

Arguments: 

q:

The queue.

Returns: 

Integer, the number of elements currently in the queue.

Time complexity: O(1).

7.7. igraph_dqueue_head — Head of the queue.

igraph_real_t igraph_dqueue_head(const igraph_dqueue_t* q);

The queue must contain at least one element.

Arguments: 

q:

The queue.

Returns: 

The first element in the queue.

Time complexity: O(1).

7.8. igraph_dqueue_back — Tail of the queue.

igraph_real_t igraph_dqueue_back(const igraph_dqueue_t* q);

The queue must contain at least one element.

Arguments: 

q:

The queue.

Returns: 

The last element in the queue.

Time complexity: O(1).

7.9. igraph_dqueue_pop — Remove the head.

igraph_real_t igraph_dqueue_pop(igraph_dqueue_t* q);

Removes and returns the first element in the queue. The queue must be non-empty.

Arguments: 

q:

The input queue.

Returns: 

The first element in the queue.

Time complexity: O(1).

7.10. igraph_dqueue_pop_back — Remove the tail

igraph_real_t igraph_dqueue_pop_back(igraph_dqueue_t* q);

Removes and returns the last element in the queue. The queue must be non-empty.

Arguments: 

q:

The queue.

Returns: 

The last element in the queue.

Time complexity: O(1).

7.11. igraph_dqueue_push — Appends an element.

igraph_error_t igraph_dqueue_push(igraph_dqueue_t* q, igraph_real_t elem);

Append an element to the end of the queue.

Arguments: 

q:

The queue.

elem:

The element to append.

Returns: 

Error code.

Time complexity: O(1) if no memory allocation is needed, O(n), the number of elements in the queue otherwise. But not that by allocating always twice as much memory as the current size of the queue we ensure that n push operations can always be done in at most O(n) time. (Assuming memory allocation is at most linear.)

8. Maximum and minimum heaps

8.1. igraph_heap_init — Initializes an empty heap object.

igraph_error_t igraph_heap_init(igraph_heap_t* h, igraph_integer_t alloc_size);

Creates an empty heap, but allocates size for some elements.

Arguments: 

h:

Pointer to an uninitialized heap object.

alloc_size:

Number of elements to allocate memory for.

Returns: 

Error code.

Time complexity: O(alloc_size), assuming memory allocation is a linear operation.

8.2. igraph_heap_init_array — Build a heap from an array.

igraph_error_t igraph_heap_init_array(igraph_heap_t *h, igraph_real_t* data, igraph_integer_t len);

Initializes a heap object from an array, the heap is also built of course (constructor).

Arguments: 

h:

Pointer to an uninitialized heap object.

data:

Pointer to an array of base data type.

len:

The length of the array at data.

Returns: 

Error code.

Time complexity: O(n), the number of elements in the heap.

8.3. igraph_heap_destroy — Destroys an initialized heap object.

void igraph_heap_destroy(igraph_heap_t* h);

Arguments: 

h:

The heap object.

Time complexity: O(1).

8.4. igraph_heap_clear — Removes all elements from a heap.

void igraph_heap_clear(igraph_heap_t* h);

This function simply sets the size of the heap to zero, it does not free any allocated memory. For that you have to call igraph_heap_destroy().

Arguments: 

h:

The heap object.

Time complexity: O(1).

8.5. igraph_heap_empty — Decides whether a heap object is empty.

igraph_bool_t igraph_heap_empty(igraph_heap_t* h);

Arguments: 

h:

The heap object.

Returns: 

TRUE if the heap is empty, FALSE otherwise.

TIme complexity: O(1).

8.6. igraph_heap_push — Add an element.

igraph_error_t igraph_heap_push(igraph_heap_t* h, igraph_real_t elem);

Adds an element to the heap.

Arguments: 

h:

The heap object.

elem:

The element to add.

Returns: 

Error code.

Time complexity: O(log n), n is the number of elements in the heap if no reallocation is needed, O(n) otherwise. It is ensured that n push operations are performed in O(n log n) time.

8.7. igraph_heap_top — Top element.

igraph_real_t igraph_heap_top(igraph_heap_t* h);

For maximum heaps this is the largest, for minimum heaps the smallest element of the heap.

Arguments: 

h:

The heap object.

Returns: 

The top element.

Time complexity: O(1).

8.8. igraph_heap_delete_top — Return and removes the top element

igraph_real_t igraph_heap_delete_top(igraph_heap_t* h);

Removes and returns the top element of the heap. For maximum heaps this is the largest, for minimum heaps the smallest element.

Arguments: 

h:

The heap object.

Returns: 

The top element.

Time complexity: O(log n), n is the number of elements in the heap.

8.9. igraph_heap_size — Number of elements

igraph_integer_t igraph_heap_size(igraph_heap_t* h);

Gives the number of elements in a heap.

Arguments: 

h:

The heap object.

Returns: 

The number of elements in the heap.

Time complexity: O(1).

8.10. igraph_heap_reserve — Allocate more memory

igraph_error_t igraph_heap_reserve(igraph_heap_t* h, igraph_integer_t size);

Allocates memory for future use. The size of the heap is unchanged. If the heap is larger than the size parameter then nothing happens.

Arguments: 

h:

The heap object.

size:

The number of elements to allocate memory for.

Returns: 

Error code.

Time complexity: O(size) if size is larger than the current number of elements. O(1) otherwise.

9. String vectors

The igraph_strvector_t type is a vector of strings. The current implementation is very simple and not too efficient. It works fine for not too many strings, e.g. the list of attribute names is returned in a string vector by igraph_cattribute_list(). Do not expect great performance from this type.

Example 7.12.  File examples/simple/igraph_strvector.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

void strvector_print(const igraph_strvector_t *sv) {
    igraph_integer_t i, s = igraph_strvector_size(sv);
    for (i = 0; i < s; i++) {
        printf("---%s---\n", STR(*sv, i));
    }
}

int main() {

    igraph_strvector_t sv1, sv2;
    char *str1;
    int i;

    /* igraph_strvector_init, igraph_strvector_destroy */
    igraph_strvector_init(&sv1, 10);
    igraph_strvector_destroy(&sv1);
    igraph_strvector_init(&sv1, 0);
    igraph_strvector_destroy(&sv1);

    /* igraph_strvector_get, igraph_strvector_set */
    igraph_strvector_init(&sv1, 5);
    for (i = 0; i < igraph_strvector_size(&sv1); i++) {
        igraph_strvector_get(&sv1, i, &str1);
        printf("---%s---\n", str1);
    }
    igraph_strvector_set(&sv1, 0, "zero");
    igraph_strvector_set(&sv1, 1, "one");
    igraph_strvector_set(&sv1, 2, "two");
    igraph_strvector_set(&sv1, 3, "three");
    igraph_strvector_set(&sv1, 4, "four");
    for (i = 0; i < igraph_strvector_size(&sv1); i++) {
        igraph_strvector_get(&sv1, i, &str1);
        printf("---%s---\n", str1);
    }

    /* igraph_strvector_remove_section, igraph_strvector_remove,
       igraph_strvector_resize, igraph_strvector_size */
    igraph_strvector_remove_section(&sv1, 0, 5);
    if (igraph_strvector_size(&sv1) != 0) {
        return 1;
    }
    igraph_strvector_resize(&sv1, 10);
    igraph_strvector_set(&sv1, 0, "zero");
    igraph_strvector_set(&sv1, 1, "one");
    igraph_strvector_set(&sv1, 2, "two");
    igraph_strvector_set(&sv1, 3, "three");
    igraph_strvector_set(&sv1, 4, "four");
    igraph_strvector_resize(&sv1, 5);
    for (i = 0; i < igraph_strvector_size(&sv1); i++) {
        igraph_strvector_get(&sv1, i, &str1);
        printf("---%s---\n", str1);
    }
    igraph_strvector_resize(&sv1, 0);
    if (igraph_strvector_size(&sv1) != 0) {
        return 1;
    }
    igraph_strvector_resize(&sv1, 10);
    igraph_strvector_set(&sv1, 0, "zero");
    igraph_strvector_set(&sv1, 1, "one");
    igraph_strvector_set(&sv1, 2, "two");
    igraph_strvector_set(&sv1, 3, "three");
    igraph_strvector_set(&sv1, 4, "four");
    igraph_strvector_resize(&sv1, 5);
    for (i = 0; i < igraph_strvector_size(&sv1); i++) {
        igraph_strvector_get(&sv1, i, &str1);
        printf("---%s---\n", str1);
    }

    /* igraph_strvector_move_interval */
    igraph_strvector_move_interval(&sv1, 3, 5, 0);
    for (i = 0; i < igraph_strvector_size(&sv1); i++) {
        igraph_strvector_get(&sv1, i, &str1);
        printf("---%s---\n", str1);
    }

    /* igraph_strvector_copy */
    igraph_strvector_copy(&sv2, &sv1);
    for (i = 0; i < igraph_strvector_size(&sv2); i++) {
        igraph_strvector_get(&sv2, i, &str1);
        printf("---%s---\n", str1);
    }
    igraph_strvector_resize(&sv1, 0);
    igraph_strvector_destroy(&sv2);
    igraph_strvector_copy(&sv2, &sv1);
    if (igraph_strvector_size(&sv2) != 0) {
        return 2;
    }
    igraph_strvector_destroy(&sv2);

    /* igraph_strvector_add */
    igraph_strvector_add(&sv1, "zeroth");
    igraph_strvector_add(&sv1, "first");
    igraph_strvector_add(&sv1, "second");
    igraph_strvector_add(&sv1, "third");
    igraph_strvector_add(&sv1, "fourth");
    for (i = 0; i < igraph_strvector_size(&sv1); i++) {
        igraph_strvector_get(&sv1, i, &str1);
        printf("---%s---\n", str1);
    }

    /* TODO: igraph_strvector_permdelete */

    igraph_strvector_destroy(&sv1);

    /* append */
    printf("---\n");
    igraph_strvector_init(&sv1, 0);
    igraph_strvector_init(&sv2, 0);
    igraph_strvector_append(&sv1, &sv2);
    strvector_print(&sv1);
    printf("---\n");

    igraph_strvector_resize(&sv1, 3);
    igraph_strvector_append(&sv1, &sv2);
    strvector_print(&sv1);
    printf("---\n");

    igraph_strvector_append(&sv2, &sv1);
    strvector_print(&sv2);
    printf("---\n");

    igraph_strvector_set(&sv1, 0, "0");
    igraph_strvector_set(&sv1, 1, "1");
    igraph_strvector_set(&sv1, 2, "2");
    igraph_strvector_set(&sv2, 0, "3");
    igraph_strvector_set(&sv2, 1, "4");
    igraph_strvector_set(&sv2, 2, "5");
    igraph_strvector_append(&sv1, &sv2);
    strvector_print(&sv1);

    igraph_strvector_destroy(&sv1);
    igraph_strvector_destroy(&sv2);

    /* clear */
    igraph_strvector_init(&sv1, 3);
    igraph_strvector_set(&sv1, 0, "0");
    igraph_strvector_set(&sv1, 1, "1");
    igraph_strvector_set(&sv1, 2, "2");
    igraph_strvector_clear(&sv1);
    if (igraph_strvector_size(&sv1) != 0) {
        return 3;
    }
    igraph_strvector_resize(&sv1, 4);
    strvector_print(&sv1);
    igraph_strvector_set(&sv1, 0, "one");
    igraph_strvector_set(&sv1, 2, "two");
    strvector_print(&sv1);
    igraph_strvector_destroy(&sv1);

    /* STR */

    igraph_strvector_init(&sv1, 5);
    igraph_strvector_set(&sv1, 0, "one");
    igraph_strvector_set(&sv1, 1, "two");
    igraph_strvector_set(&sv1, 2, "three");
    igraph_strvector_set(&sv1, 3, "four");
    igraph_strvector_set(&sv1, 4, "five");
    strvector_print(&sv1);
    igraph_strvector_destroy(&sv1);

    if (!IGRAPH_FINALLY_STACK_EMPTY) {
        return 4;
    }

    return 0;
}


9.1. igraph_strvector_init — Initialize

igraph_error_t igraph_strvector_init(igraph_strvector_t *sv, igraph_integer_t len);

Reserves memory for the string vector, a string vector must be first initialized before calling other functions on it. All elements of the string vector are set to the empty string.

Arguments: 

sv:

Pointer to an initialized string vector.

len:

The (initial) length of the string vector.

Returns: 

Error code.

Time complexity: O(len).

9.2. igraph_strvector_copy — Initialization by copying.

igraph_error_t igraph_strvector_copy(igraph_strvector_t *to,
                          const igraph_strvector_t *from);

Initializes a string vector by copying another string vector.

Arguments: 

to:

Pointer to an uninitialized string vector.

from:

The other string vector, to be copied.

Returns: 

Error code.

Time complexity: O(l), the total length of the strings in from.

9.3. igraph_strvector_destroy — Free allocated memory

void igraph_strvector_destroy(igraph_strvector_t *sv);

Destroy a string vector. It may be reinitialized with igraph_strvector_init() later.

Arguments: 

sv:

The string vector.

Time complexity: O(l), the total length of the strings, maybe less depending on the memory manager.

9.4. STR — Indexing string vectors

#define STR(sv,i)

This is a macro which allows to query the elements of a string vector in simpler way than igraph_strvector_get(). Note this macro cannot be used to set an element, for that use igraph_strvector_set().

Arguments: 

sv:

The string vector

i:

The the index of the element.

Returns: 

The element at position i.

Time complexity: O(1).

9.5. igraph_strvector_get — Indexing

void igraph_strvector_get(const igraph_strvector_t *sv, igraph_integer_t idx,
                          char **value);

Query an element of a string vector. See also the STR macro for an easier way.

Arguments: 

sv:

The input string vector.

idx:

The index of the element to query.

Pointer:

to a char*, the address of the string is stored here.

Time complexity: O(1).

9.6. igraph_strvector_set — Set an element

igraph_error_t igraph_strvector_set(igraph_strvector_t *sv, igraph_integer_t idx,
                         const char *value);

The provided value is copied into the idx position in the string vector.

Arguments: 

sv:

The string vector.

idx:

The position to set.

value:

The new value.

Returns: 

Error code.

Time complexity: O(l), the length of the new string. Maybe more, depending on the memory management, if reallocation is needed.

9.7. igraph_strvector_set2 — Sets an element.

igraph_error_t igraph_strvector_set2(igraph_strvector_t *sv, igraph_integer_t idx,
                          const char *value, size_t len);

This is almost the same as igraph_strvector_set, but the new value is not a zero terminated string, but its length is given.

Arguments: 

sv:

The string vector.

idx:

The position to set.

value:

The new value.

len:

The length of the new value.

Returns: 

Error code.

Time complexity: O(l), the length of the new string. Maybe more, depending on the memory management, if reallocation is needed.

9.8. igraph_strvector_remove — Removes a single element from a string vector.

void igraph_strvector_remove(igraph_strvector_t *v, igraph_integer_t elem);

The string will be one shorter.

Arguments: 

v:

The string vector.

elem:

The index of the element to remove.

Time complexity: O(n), the length of the string.

9.9. igraph_strvector_append — Concatenate two string vectors.

igraph_error_t igraph_strvector_append(igraph_strvector_t *to,
                            const igraph_strvector_t *from);

Arguments: 

to:

The first string vector, the result is stored here.

from:

The second string vector, it is kept unchanged.

Returns: 

Error code.

Time complexity: O(n+l2), n is the number of strings in the new string vector, l2 is the total length of strings in the from string vector.

9.10. igraph_strvector_clear — Remove all elements

void igraph_strvector_clear(igraph_strvector_t *sv);

After this operation the string vector will be empty.

Arguments: 

sv:

The string vector.

Time complexity: O(l), the total length of strings, maybe less, depending on the memory manager.

9.11. igraph_strvector_resize — Resize

igraph_error_t igraph_strvector_resize(igraph_strvector_t* v, igraph_integer_t newsize);

If the new size is bigger then empty strings are added, if it is smaller then the unneeded elements are removed.

Arguments: 

v:

The string vector.

newsize:

The new size.

Returns: 

Error code.

Time complexity: O(n), the number of strings if the vector is made bigger, O(l), the total length of the deleted strings if it is made smaller, maybe less, depending on memory management.

9.12. igraph_strvector_size — Gives the size of a string vector.

igraph_integer_t igraph_strvector_size(const igraph_strvector_t *sv);

Arguments: 

sv:

The string vector.

Returns: 

The length of the string vector.

Time complexity: O(1).

9.13. igraph_strvector_add — Adds an element to the back of a string vector.

igraph_error_t igraph_strvector_add(igraph_strvector_t *v, const char *value);

Arguments: 

v:

The string vector.

value:

The string to add, it will be copied.

Returns: 

Error code.

Time complexity: O(n+l), n is the total number of strings, l is the length of the new string.

10. Adjacency lists

Sometimes it is easier to work with a graph which is in adjacency list format: a list of vectors; each vector contains the neighbor vertices or incident edges of a given vertex. Typically, this representation is good if we need to iterate over the neighbors of all vertices many times. E.g. when finding the shortest paths between all pairs of vertices or calculating closeness centrality for all the vertices.

The igraph_adjlist_t stores the adjacency lists of a graph. After creation it is independent of the original graph, it can be modified freely with the usual vector operations, the graph is not affected. E.g. the adjacency list can be used to rewire the edges of a graph efficiently. If one used the straightforward igraph_delete_edges() and igraph_add_edges() combination for this that needs O(|V|+|E|) time for every single deletion and insertion operation, it is thus very slow if many edges are rewired. Extracting the graph into an adjacency list, do all the rewiring operations on the vectors of the adjacency list and then creating a new graph needs (depending on how exactly the rewiring is done) typically O(|V|+|E|) time for the whole rewiring process.

Lazy adjacency lists are a bit different. When creating a lazy adjacency list, the neighbors of the vertices are not queried, only some memory is allocated for the vectors. When igraph_lazy_adjlist_get() is called for vertex v the first time, the neighbors of v are queried and stored in a vector of the adjacency list, so they don't need to be queried again. Lazy adjacency lists are handy if you have an at least linear operation (because initialization is generally linear in terms of the number of vertices), but you don't know how many vertices you will visit during the computation.

Example 7.13.  File examples/simple/adjlist.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2008-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include <igraph.h>

int main() {

    igraph_t g, g2;
    igraph_adjlist_t adjlist;
    igraph_bool_t iso;

    /* Create a directed out-tree, convert it into an adjacency list
     * representation, then reconstruct the graph from the tree and check
     * whether the two are isomorphic (they should be) */

    igraph_tree(&g, 42, 3, IGRAPH_TREE_OUT);
    igraph_adjlist_init(&g, &adjlist, IGRAPH_OUT, IGRAPH_LOOPS_ONCE, IGRAPH_MULTIPLE);
    igraph_adjlist(&g2, &adjlist, IGRAPH_OUT, /* duplicate = */ 0);
    igraph_isomorphic(&g, &g2, &iso);
    if (!iso) {
        return 1;
    }
    igraph_adjlist_destroy(&adjlist);
    igraph_destroy(&g2);
    igraph_destroy(&g);

    return 0;
}


10.1. Adjacent vertices

10.1.1. igraph_adjlist_init — Constructs an adjacency list of vertices from an incidence list.

igraph_error_t igraph_adjlist_init_from_inclist(
    const igraph_t *graph, igraph_adjlist_t *al, const igraph_inclist_t *il);

In some algorithms it is useful to have an adjacency list and an incidence list representation of the same graph, and in many cases it is the most useful if they are consistent with each other, i.e. if can be guaranteed that the vertex ID in the i-th entry of the adjacency list of vertex v is the other endpoint of the edge in the i-th entry of the incidence list of the same vertex. This function creates such an adjacency list from the corresponding incidence list by looking up the endpoints of each edge in the incidence list and constructing the corresponding adjacenecy vectors.

The adjacency list is independent of the graph or the incidence list after creation; in other words, modifications that are made to the graph or the incidence list are not reflected in the adjacency list.

Arguments: 

graph:

The input graph.

al:

Pointer to an uninitialized igraph_adjlist_t object.

il:

Pointer to an initialized igraph_inclist_t object that will be converted into an adjacency list.

Returns: 

Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

10.1.2. igraph_adjlist_init_empty — Initializes an empty adjacency list.

igraph_error_t igraph_adjlist_init_empty(igraph_adjlist_t *al, igraph_integer_t no_of_nodes);

Creates a list of vectors, one for each vertex. This is useful when you are constructing a graph using an adjacency list representation as it does not require your graph to exist yet.

Arguments: 

no_of_nodes:

The number of vertices

al:

Pointer to an uninitialized igraph_adjlist_t object.

Returns: 

Error code.

Time complexity: O(|V|), linear in the number of vertices.

10.1.3. igraph_adjlist_init_complementer — Adjacency lists for the complementer graph.

igraph_error_t igraph_adjlist_init_complementer(const igraph_t *graph,
                                     igraph_adjlist_t *al,
                                     igraph_neimode_t mode,
                                     igraph_bool_t loops);

This function creates adjacency lists for the complementer of the input graph. In the complementer graph all edges are present which are not present in the original graph. Multiple edges in the input graph are ignored.

Arguments: 

graph:

The input graph.

al:

Pointer to a not yet initialized adjacency list.

mode:

Constant specifying whether outgoing (IGRAPH_OUT), incoming (IGRAPH_IN), or both (IGRAPH_ALL) types of neighbors (in the complementer graph) to include in the adjacency list. It is ignored for undirected networks.

loops:

Whether to consider loop edges.

Returns: 

Error code.

Time complexity: O(|V|^2+|E|), quadratic in the number of vertices.

10.1.4. igraph_adjlist_destroy — Deallocates an adjacency list.

void igraph_adjlist_destroy(igraph_adjlist_t *al);

Free all memory allocated for an adjacency list.

Arguments: 

al:

The adjacency list to destroy.

Time complexity: depends on memory management.

10.1.5. igraph_adjlist_get — Query a vector in an adjacency list.

#define igraph_adjlist_get(al,no)

Returns a pointer to an igraph_vector_int_t object from an adjacency list. The vector can be modified as desired.

Arguments: 

al:

The adjacency list object.

no:

The vertex whose adjacent vertices will be returned.

Returns: 

Pointer to the igraph_vector_int_t object.

Time complexity: O(1).

10.1.6. igraph_adjlist_size — Returns the number of vertices in an adjacency list.

igraph_integer_t igraph_adjlist_size(const igraph_adjlist_t *al);

Arguments: 

al:

The adjacency list.

Returns: 

The number of vertices in the adjacency list.

Time complexity: O(1).

10.1.7. igraph_adjlist_clear — Removes all edges from an adjacency list.

void igraph_adjlist_clear(igraph_adjlist_t *al);

Arguments: 

al:

The adjacency list. Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the adjacency list.

10.1.8. igraph_adjlist_sort — Sorts each vector in an adjacency list.

void igraph_adjlist_sort(igraph_adjlist_t *al);

Sorts every vector of the adjacency list.

Arguments: 

al:

The adjacency list.

Time complexity: O(n log n), n is the total number of elements in the adjacency list.

10.1.9. igraph_adjlist_simplify — Simplifies an adjacency list.

igraph_error_t igraph_adjlist_simplify(igraph_adjlist_t *al);

Simplifies an adjacency list, i.e. removes loop and multiple edges.

Arguments: 

al:

The adjacency list.

Returns: 

Error code.

Time complexity: O(|V|+|E|), linear in the number of edges and vertices.

10.2. Incident edges

10.2.1. igraph_inclist_init — Initializes an incidence list.

igraph_error_t igraph_inclist_init(const igraph_t *graph,
                        igraph_inclist_t *il,
                        igraph_neimode_t mode,
                        igraph_loops_t loops);

Creates a list of vectors containing the incident edges for all vertices. The incidence list is independent of the graph after creation, subsequent changes of the graph object do not update the incidence list, and changes to the incidence list do not update the graph.

When mode is IGRAPH_IN or IGRAPH_OUT, each edge ID will appear in the incidence list once. When mode is IGRAPH_ALL, each edge ID will appear in the incidence list twice, once for the source vertex and once for the target edge. It also means that the edge IDs of loop edges may potentially appear twice for the same vertex. Use the loops argument to control whether this will be the case (IGRAPH_LOOPS_TWICE ) or not (IGRAPH_LOOPS_ONCE or IGRAPH_NO_LOOPS).

Arguments: 

graph:

The input graph.

il:

Pointer to an uninitialized incidence list.

mode:

Constant specifying whether incoming edges (IGRAPH_IN), outgoing edges (IGRAPH_OUT) or both (IGRAPH_ALL) to include in the incidence lists of directed graphs. It is ignored for undirected graphs.

loops:

Specifies how to treat loop edges. IGRAPH_NO_LOOPS removes loop edges from the incidence list. IGRAPH_LOOPS_ONCE makes each loop edge appear only once in the incidence list of the corresponding vertex. IGRAPH_LOOPS_TWICE makes loop edges appear twice in the incidence list of the corresponding vertex, but only if the graph is undirected or mode is set to IGRAPH_ALL.

Returns: 

Error code.

Time complexity: O(|V|+|E|), linear in the number of vertices and edges.

10.2.2. igraph_inclist_destroy — Frees all memory allocated for an incidence list.

void igraph_inclist_destroy(igraph_inclist_t *il);

Arguments: 

eal:

The incidence list to destroy.

Time complexity: depends on memory management.

10.2.3. igraph_inclist_get — Query a vector in an incidence list.

#define igraph_inclist_get(il,no)

Returns a pointer to an igraph_vector_int_t object from an incidence list containing edge IDs. The vector can be modified, resized, etc. as desired.

Arguments: 

il:

Pointer to the incidence list.

no:

The vertex for which the incident edges are returned.

Returns: 

Pointer to an igraph_vector_int_t object.

Time complexity: O(1).

10.2.4. igraph_inclist_size — Returns the number of vertices in an incidence list.

igraph_integer_t igraph_inclist_size(const igraph_inclist_t *il);

Arguments: 

il:

The incidence list.

Returns: 

The number of vertices in the incidence list.

Time complexity: O(1).

10.2.5. igraph_inclist_clear — Removes all edges from an incidence list.

void igraph_inclist_clear(igraph_inclist_t *il);

Arguments: 

il:

The incidence list.

Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the incidence list.

10.3. Lazy adjacency list for vertices

10.3.1. igraph_lazy_adjlist_init — Initialized a lazy adjacency list.

igraph_error_t igraph_lazy_adjlist_init(const igraph_t *graph,
                             igraph_lazy_adjlist_t *al,
                             igraph_neimode_t mode,
                             igraph_loops_t loops,
                             igraph_multiple_t multiple);

Create a lazy adjacency list for vertices. This function only allocates some memory for storing the vectors of an adjacency list, but the neighbor vertices are not queried, only at the igraph_lazy_adjlist_get() calls.

Arguments: 

graph:

The input graph.

al:

Pointer to an uninitialized adjacency list object.

mode:

Constant, it gives whether incoming edges (IGRAPH_IN), outgoing edges (IGRPAH_OUT) or both types of edges (IGRAPH_ALL) are considered. It is ignored for undirected graphs.

simplify:

Constant, it gives whether to simplify the vectors in the adjacency list (IGRAPH_SIMPLIFY) or not (IGRAPH_DONT_SIMPLIFY).

Returns: 

Error code.

Time complexity: O(|V|), the number of vertices, possibly, but depends on the underlying memory management too.

10.3.2. igraph_lazy_adjlist_destroy — Deallocate a lazt adjacency list.

void igraph_lazy_adjlist_destroy(igraph_lazy_adjlist_t *al);

Free all allocated memory for a lazy adjacency list.

Arguments: 

al:

The adjacency list to deallocate.

Time complexity: depends on the memory management.

10.3.3. igraph_lazy_adjlist_get — Query neighbor vertices.

#define igraph_lazy_adjlist_get(al,no)

If the function is called for the first time for a vertex then the result is stored in the adjacency list and no further query operations are needed when the neighbors of the same vertex are queried again.

Arguments: 

al:

The lazy adjacency list.

no:

The vertex ID to query.

Returns: 

Pointer to a vector. It is allowed to modify it and modification does not affect the original graph.

Time complexity: O(d), the number of neighbor vertices for the first time, O(1) for subsequent calls.

10.3.4. igraph_lazy_adjlist_size — Returns the number of vertices in a lazy adjacency list.

igraph_integer_t igraph_lazy_adjlist_size(const igraph_lazy_adjlist_t *al);

Arguments: 

al:

The lazy adjacency list.

Returns: 

The number of vertices in the lazy adjacency list.

Time complexity: O(1).

10.3.5. igraph_lazy_adjlist_clear — Removes all edges from a lazy adjacency list.

void igraph_lazy_adjlist_clear(igraph_lazy_adjlist_t *al);

Arguments: 

al:

The lazy adjacency list. Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the adjacency list.

10.4. Lazy incidence list for edges

10.4.1. igraph_lazy_inclist_init — Initializes a lazy incidence list of edges.

igraph_error_t igraph_lazy_inclist_init(const igraph_t *graph,
                             igraph_lazy_inclist_t *il,
                             igraph_neimode_t mode,
                             igraph_loops_t loops);

Create a lazy incidence list for edges. This function only allocates some memory for storing the vectors of an incidence list, but the incident edges are not queried, only when igraph_lazy_inclist_get() is called.

When mode is IGRAPH_IN or IGRAPH_OUT, each edge ID will appear in the incidence list once. When mode is IGRAPH_ALL, each edge ID will appear in the incidence list twice, once for the source vertex and once for the target edge. It also means that the edge IDs of loop edges will appear twice for the same vertex.

Arguments: 

graph:

The input graph.

al:

Pointer to an uninitialized incidence list.

mode:

Constant, it gives whether incoming edges (IGRAPH_IN), outgoing edges (IGRAPH_OUT) or both types of edges (IGRAPH_ALL) are considered. It is ignored for undirected graphs.

loops:

Specifies how to treat loop edges. IGRAPH_NO_LOOPS removes loop edges from the incidence list. IGRAPH_LOOPS_ONCE makes each loop edge appear only once in the incidence list of the corresponding vertex. IGRAPH_LOOPS_TWICE makes loop edges appear twice in the incidence list of the corresponding vertex, but only if the graph is undirected or mode is set to IGRAPH_ALL.

Returns: 

Error code.

Time complexity: O(|V|), the number of vertices, possibly. But it also depends on the underlying memory management.

10.4.2. igraph_lazy_inclist_destroy — Deallocates a lazy incidence list.

void igraph_lazy_inclist_destroy(igraph_lazy_inclist_t *il);

Frees all allocated memory for a lazy incidence list.

Arguments: 

al:

The incidence list to deallocate.

Time complexity: depends on memory management.

10.4.3. igraph_lazy_inclist_get — Query incident edges.

#define igraph_lazy_inclist_get(al,no)

If the function is called for the first time for a vertex, then the result is stored in the incidence list and no further query operations are needed when the incident edges of the same vertex are queried again.

Arguments: 

al:

The lazy incidence list object.

no:

The vertex ID to query.

Returns: 

Pointer to a vector. It is allowed to modify it and modification does not affect the original graph.

Time complexity: O(d), the number of incident edges for the first time, O(1) for subsequent calls with the same no argument.

10.4.4. igraph_lazy_inclist_size — Returns the number of vertices in a lazy incidence list.

igraph_integer_t igraph_lazy_inclist_size(const igraph_lazy_inclist_t *il);

Arguments: 

il:

The lazy incidence list.

Returns: 

The number of vertices in the lazy incidence list.

Time complexity: O(1).

10.4.5. igraph_lazy_inclist_clear — Removes all edges from a lazy incidence list.

void igraph_lazy_inclist_clear(igraph_lazy_inclist_t *il);

Arguments: 

il:

The lazy incidence list.

Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the incidence list.

11. Partial prefix sum trees

The igraph_psumtree_t data type represents a partial prefix sum tree. A partial prefix sum tree is a data structure that can be used to draw samples from a discrete probability distribution with dynamic probabilities that are updated frequently. This is achieved by creating a binary tree where the leaves are the items. Each leaf contains the probability corresponding to the items. Intermediate nodes of the tree always contain the sum of its two children. When the value of a leaf node is updated, the values of its ancestors are also updated accordingly.

Samples can be drawn from the probability distribution represented by the tree by generating a uniform random number between 0 (inclusive) and the value of the root of the tree (exclusive), and then following the branches of the tree as follows. In each step, the value in the current node is compared with the generated number. If the value in the node is larger, the left branch of the tree is taken; otherwise the generated number is decreased by the value in the node and the right branch of the tree is taken, until a leaf node is reached.

Note that the sampling process works only if all the values in the tree are non-negative. This is enforced by the object; in particular, trying to set a negative value for an item will produce an igraph error.

11.1. igraph_psumtree_init — Initializes a partial prefix sum tree.

igraph_error_t igraph_psumtree_init(igraph_psumtree_t *t, igraph_integer_t size);

The tree is initialized with a fixed number of elements. After initialization, the value corresponding to each element is zero.

Arguments: 

t:

The tree to initialize

size:

The number of elements in the tree

Returns: 

Error code, typically IGRAPH_ENOMEM if there is not enough memory

Time complexity: O(n) for a tree containing n elements

11.2. igraph_psumtree_destroy — Destroys a partial prefix sum tree.

void igraph_psumtree_destroy(igraph_psumtree_t *t);

All partial prefix sum trees initialized by igraph_psumtree_init() should be properly destroyed by this function. A destroyed tree needs to be reinitialized by igraph_psumtree_init() if you want to use it again.

Arguments: 

t:

Pointer to the (previously initialized) tree to destroy.

Time complexity: operating system dependent.

11.3. igraph_psumtree_size — Returns the size of the tree.

igraph_integer_t igraph_psumtree_size(const igraph_psumtree_t *t);

Arguments: 

t:

The tree object

Returns: 

The number of discrete items in the tree.

Time complexity: O(1).

11.4. igraph_psumtree_get — Retrieves the value corresponding to an item in the tree.

igraph_real_t igraph_psumtree_get(const igraph_psumtree_t *t, igraph_integer_t idx);

Arguments: 

t:

The tree to query.

idx:

The index of the item whose value is to be retrieved.

Returns: 

The value corresponding to the item with the given index.

Time complexity: O(1)

11.5. igraph_psumtree_sum — Returns the sum of the values of the leaves in the tree.

igraph_real_t igraph_psumtree_sum(const igraph_psumtree_t *t);

Arguments: 

t:

The tree object

Returns: 

The sum of the values of the leaves in the tree.

Time complexity: O(1).

11.6. igraph_psumtree_search — Finds an item in the tree, given a value.

igraph_error_t igraph_psumtree_search(const igraph_psumtree_t *t, igraph_integer_t *idx,
                           igraph_real_t search);

This function finds the item with the lowest index where it holds that the sum of all the items with a lower index is less than or equal to the given value and that the sum of all the items with a lower index plus the item itself is larger than the given value.

If you think about the partial prefix sum tree as a tool to sample from a discrete probability distribution, then calling this function repeatedly with uniformly distributed random numbers in the range 0 (inclusive) to the sum of all values in the tree (exclusive) will sample the items in the tree with a probability that is proportional to their associated values.

Arguments: 

t:

The tree to query.

idx:

The index of the item is returned here.

search:

The value to use for the search.

Returns: 

Error code; currently the search always succeeds.

Time complexity: O(log n), where n is the number of items in the tree.

11.7. igraph_psumtree_update — Updates the value associated to an item in the tree.

igraph_error_t igraph_psumtree_update(igraph_psumtree_t *t, igraph_integer_t idx,
                           igraph_real_t new_value);

Arguments: 

t:

The tree to query.

idx:

The index of the item to update.

new_value:

The new value of the item.

Returns: 

Error code, IGRAPH_EINVAL if the new value is negative or NaN, IGRAPH_SUCCESS if the operation was successful.

Time complexity: O(log n), where n is the number of items in the tree.