# 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_int_t (int), char (char), igraph_bool_t (bool), igraph_complex_t (complex) and and void * (ptr). The default is igraph_real_t.

matrix

  Matrix is currently defined for igraph_real_t, igraph_int_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_int_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_int_t (int), char (char) and igraph_bool_t (bool). The default is igraph_real_t.

double-ended queue

  Dqueue is currently defined for igraph_real_t, igraph_int_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_int_t (int), char (char). In addition both maximum and minimum heaps are available. The default is the igraph_real_t maximum heap.

list of vectors

  Lists of vectors are currently defined for vectors holding igraph_real_t and igraph_int_t (int). The default is igraph_real_t.

list of matrices

  Lists of matrices are currently defined for matrices holding igraph_real_t only.

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_int_t elements. Its functions have the `igraph_heap_int_` prefix.

- igraph_heap_min_int_t is a minimum heap containing igraph_int_t elements. Its functions have the `igraph_heap_min_int_` prefix.

- igraph_vector_list_t is a list of (floating-point) vectors; each element in this data structure is an igraph_vector_t. Similarly, igraph_matrix_list_t is a list of (floating-point) matrices; each element in this data structure is an igraph_matrix_t.

- igraph_vector_int_list_t is a list of integer vectors; each element in this data structure is an igraph_vector_int_t.

Note that the VECTOR and the MATRIX macros can be used on all vector and matrix types. VECTOR cannot be used on lists of vectors, though, only on the individial vectors in the list.

## 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_int_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 use 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 described 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_init_copy()` creates a new identical copy of an already existing and initialized vector. `igraph_vector_init_array()` creates a vector by copying a regular C array. `igraph_vector_init_range()` 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_int_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_array` — Initializes a vector from an ordinary C array (constructor).

    igraph_error_t igraph_vector_init_array(
            igraph_vector_t *v, const igraph_real_t *data, igraph_int_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_copy` — Initializes a vector from another vector object (constructor).

    igraph_error_t igraph_vector_init_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.4. `igraph_vector_init_range` — Initializes a vector with a range.

    igraph_error_t igraph_vector_init_range(igraph_vector_t *v, igraph_real_t start, igraph_real_t end);

The vector will contain the numbers `start`, `start`+1, ..., `end`-1. Note that the range is closed from the left and open from the right, according to C conventions.

Arguments:

`v`: | Pointer to an uninitialized vector object.
`start`: | The lower limit in the range (inclusive).
`end`: | The upper limit in the range (exclusive).

Returns:

`` | Error code: `IGRAPH_ENOMEM`: out of memory.

Time complexity: O(n), the number of elements in 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_array()` 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.3.3. `igraph_vector_range` — Updates a vector to store a range.

    igraph_error_t igraph_vector_range(igraph_vector_t *v, igraph_real_t start, igraph_real_t end);

Sets the elements of the vector to contain the numbers `start`, `start`+1, ..., `end`-1. Note that the range is closed from the left and open from the right, according to C conventions. The vector will be resized to fit the range.

Arguments:

`v`: | The vector to update.
`start`: | The lower limit in the range (inclusive).
`end`: | The upper limit in the range (exclusive).

Returns:

`` | Error code: `IGRAPH_ENOMEM`: out of memory.

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

### 2.4. Accessing elements

The simplest and most performant 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_get()` queries and `igraph_vector_set()` sets an element of a vector. `igraph_vector_get_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.

Arguments:

`v`: | The vector object.

Time complexity: O(1).

#### 2.4.2. `igraph_vector_get` — Access an element of a vector.

    igraph_real_t igraph_vector_get(const igraph_vector_t *v, igraph_int_t pos);

Unless you need a function, consider using the `VECTOR` macro instead for better performance.

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_get_ptr()` and the `VECTOR` macro.

Time complexity: O(1).

#### 2.4.3. `igraph_vector_get_ptr` — Get the address of an element of a vector.

    igraph_real_t* igraph_vector_get_ptr(const igraph_vector_t *v, igraph_int_t pos);

Unless you need a function, consider using the `VECTOR` macro instead for better performance.

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_get()` 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_int_t pos, igraph_real_t value);

Unless you need a function, consider using the `VECTOR` macro instead for better performance.

Arguments:

`v`: | The igraph_vector_t element.
`pos`: | Position of the element to set.
`value`: | New value of the element.

See also:

`` | `igraph_vector_get()`.

#### 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.4.6. `igraph_vector_index` — Extract elements from a vector at specific indices.

    igraph_error_t igraph_vector_index(const igraph_vector_t *v,
                                       igraph_vector_t *newv,
                                       const igraph_vector_int_t *idx);

Arguments:

`v`: | the vector to extract elements from
`newv`: | the result vector
`idx`: | vector containing the indices of the elements to extract

See also:

`` | `igraph_vector_index_in_place` for the in-place variant

#### 2.4.7. `igraph_vector_index_in_place` — Extract elements from a vector at specific indices in-place.

    igraph_error_t igraph_vector_index_in_place(igraph_vector_t *v,
                                           const igraph_vector_int_t *idx);

Arguments:

`v`: | the vector to extract elements from. This will be modified in-place.
`idx`: | vector containing the indices of the elements to extract

See also:

`` | `igraph_vector_index` for a function that does not modify the original vector

### 2.5. Vector views

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

    igraph_vector_t igraph_vector_view(
            const igraph_real_t *data, igraph_int_t length);

This function lets you treat an existing C array as an `igraph_vector_t`.

Since this function creates a view into an existing array, you must not destroy the `igraph_vector_t` object when you are done with it. Similarly, you must not call any function on it that may attempt to modify the size of the vector. Modifying an element in the vector will modify the underlying array as the two share the same memory block.

Typical usage pattern:

    igraph_real_t array[] = { 1.0, 1.5, 2.0 };
    const igraph_vector_t v = igraph_vector_view(array, sizeof(array) / sizeof(array[0]));
    printf("The sum of vector elements is %g.\n", igraph_vector_sum(&v));

Arguments:

`data`: | The raw array that the vector provides a view into.
`length`: | The length of the C array.

Returns:

`` | The vector object providing the view into the array.

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 all elements of two vectors.

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

Arguments:

`v1`: | The first vector.
`v2`: | The second vector.

Time complexity: O(1).

### 2.7. Exchanging elements

#### 2.7.1. `igraph_vector_swap_elements` — Swap two elements in a vector.

    void igraph_vector_swap_elements(igraph_vector_t *v,
                                        igraph_int_t i, igraph_int_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).

Time complexity: O(1).

#### 2.7.2. `igraph_vector_reverse` — Reverse the elements of a vector.

    void 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.

See also:

`` | igraph_vector_reverse_section() to reverse only a section of a vector.

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

#### 2.7.3. `igraph_vector_reverse_section` — Reverse the elements in a section of a vector.

    void igraph_vector_reverse_section(igraph_vector_t *v, igraph_int_t from, igraph_int_t to);

Arguments:

`v`: | The input vector.
`from`: | Index of the first element to include in the reversal.
`to`: | Index of the first element not to include in the reversal.

See also:

`` | igraph_vector_reverse() to reverse the entire vector.

Time complexity: O(to - from), the number of elements to reverse.

#### 2.7.4. `igraph_vector_rotate_left` — Rotates the elements of a vector to the left.

    void igraph_vector_rotate_left(igraph_vector_t *v, igraph_int_t n);

Rotates the elements of a vector to the left by the given number of steps. Element index `n` will have index 0 after the rotation. For example, rotating `(0, 1, 2, 3, 4, 5)` by 2 yields `(2, 3, 4, 5, 0, 1)`.

Arguments:

`v`: | The input vector.
`n`: | The number of steps to rotate by. Passing a negative value rotates to the right.

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

#### 2.7.5. `igraph_vector_shuffle` — Shuffles a vector in-place using the Fisher-Yates method.

    void 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.

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`

    #include <igraph.h>

    int main(void) {
        igraph_real_t d;
        igraph_vector_t u, v;
        igraph_int_t i, k, n;

        /* Initialize the library. */
        igraph_setup();

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

        igraph_rng_seed(igraph_rng_default(), 42); /* make tests deterministic */

        /* 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);

        k = RNG_INTEGER(-1000, 1000);
        VECTOR(v)[0] = k;
        igraph_vector_shuffle(&v);
        if (VECTOR(v)[0] != k) {
            return 1;
        }
        d = RNG_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 = RNG_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);
        igraph_vector_shuffle(&v);
        igraph_vector_destroy(&v);

        return 0;
    }

#### 2.7.6. `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_sort_ind()`; passing in the index vector from `igraph_vector_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.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` — Multiplies 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);

Checks element-wise equality of two vectors. For vectors containing floating point values, consider using `igraph_matrix_all_almost_e()`.

Arguments:

`lhs`: | The first vector.
`rhs`: | The second vector.

Returns:

`` | True if the elements in the `lhs` are all equal to the corresponding elements in `rhs`. Returns 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_almost_e` — Are all elements almost equal?

    igraph_bool_t igraph_vector_all_almost_e(const igraph_vector_t *lhs,
                                             const igraph_vector_t *rhs,
                                             igraph_real_t eps);

Checks if the elements of two vectors are equal within a relative tolerance.

Arguments:

`lhs`: | The first vector.
`rhs`: | The second vector.
`eps`: | Relative tolerance, see `igraph_almost_equals()` for details.

Returns:

`` | True if the two vectors are almost equal, false if there is at least one differing element or if the vectors are not of the same size.

#### 2.9.3. `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:

`` | True if the elements in the `lhs` are all less than the corresponding elements in `rhs`. Returns false if the lengths of the vectors don't match. If any element is NaN, it will return false.

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

#### 2.9.4. `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:

`` | True if the elements in the `lhs` are all greater than the corresponding elements in `rhs`. Returns false if the lengths of the vectors don't match. If any element is NaN, it will return false.

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

#### 2.9.5. `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:

`` | True if the elements in the `lhs` are all less than or equal to the corresponding elements in `rhs`. Returns false if the lengths of the vectors don't match. If any element is NaN, it will return false.

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

#### 2.9.6. `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:

`` | True if the elements in the `lhs` are all greater than or equal to the corresponding elements in `rhs`. Returns false if the lengths of the vectors don't match. If any element is NaN, it will return false.

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

#### 2.9.7. `igraph_vector_is_equal` — Are all elements equal?

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

This is an alias of `igraph_vector_all_e()` with a more intuitive name.

Arguments:

`lhs`: | The first vector.
`rhs`: | The second vector.

Returns:

`` | True if the elements in the `lhs` are all equal to the corresponding elements in `rhs`. Returns false if the lengths of the vectors don't match.

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

#### 2.9.8. `igraph_vector_zapsmall` — Replaces small elements of a vector by exact zeros.

    igraph_error_t igraph_vector_zapsmall(igraph_vector_t *v, igraph_real_t tol);

Vector elements which are smaller in magnitude than the given absolute tolerance will be replaced by exact zeros. The default tolerance corresponds to two-thirds of the representable digits of igraph_real_t, i.e. `DBL_EPSILON^(2/3)` which is approximately `10^-10`.

Arguments:

`v`: | The vector to process, it will be changed in-place.
`tol`: | Tolerance value. Numbers smaller than this in magnitude will be replaced by zeros. Pass in zero to use the default tolerance. Must not be negative.

Returns:

`` | Error code.

See also:

`` | `igraph_vector_all_almost_e()` and `igraph_almost_equals()` to perform comparisons with relative tolerances.

#### 2.9.9. `igraph_vector_lex_cmp` — Lexicographical comparison of two vectors (type-safe variant).

    int igraph_vector_lex_cmp(
        const igraph_vector_t *lhs, const igraph_vector_t *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_list_sort()`.

Arguments:

`lhs`: | Pointer to the first vector.
`rhs`: | Pointer to the second vector.

Returns:

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

See also:

`` | `igraph_vector_lex_cmp_untyped()` for an untyped variant of this function, or `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_int_list_sort.c`

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

    int main(void) {
        igraph_t graph;
        igraph_vector_int_list_t cliques;
        igraph_int_t i, n;

        /* Initialize the library. */
        igraph_setup();

        /* 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_gnm(&graph, 15, 80, IGRAPH_UNDIRECTED, IGRAPH_SIMPLE_SW, IGRAPH_EDGE_UNLABELED);

        /* Find all maximal cliques in the graph. IGRAPH_UNLIMITED signifies no limit on the clique sizes. */
        igraph_vector_int_list_init(&cliques, 0);
        igraph_maximal_cliques(&graph, &cliques, /* min_size */ IGRAPH_UNLIMITED, /* max_size */ IGRAPH_UNLIMITED, IGRAPH_UNLIMITED);

        /* Print the cliques in lexicographical order */
        printf("Maximal cliques in lexicographical order:\n");
        igraph_vector_int_list_sort(&cliques, igraph_vector_int_lex_cmp);
        n = igraph_vector_int_list_size(&cliques);
        for (i=0; i < n; ++i) {
            igraph_vector_int_print(igraph_vector_int_list_get_ptr(&cliques, i));
        }

        /* Print the cliques in colexicographical order */
        printf("\nMaximal cliques in colexicographical order:\n");
        igraph_vector_int_list_sort(&cliques, igraph_vector_int_colex_cmp);
        n = igraph_vector_int_list_size(&cliques);
        for (i=0; i < n; ++i) {
            igraph_vector_int_print(igraph_vector_int_list_get_ptr(&cliques, i));
        }

        /* Destroy data structures when we no longer need them */
        igraph_vector_int_list_destroy(&cliques);
        igraph_destroy(&graph);

        return 0;
    }

#### 2.9.10. `igraph_vector_lex_cmp_untyped` — Lexicographical comparison of two vectors (non-type-safe).

    int igraph_vector_lex_cmp_untyped(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_lex_cmp()` for a type-safe variant of this function, or `igraph_vector_colex_cmp_untyped()` to compare vectors starting from the last element.

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

#### 2.9.11. `igraph_vector_colex_cmp` — Colexicographical comparison of two vectors.

    int igraph_vector_colex_cmp(
        const igraph_vector_t *lhs, const igraph_vector_t *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_list_sort()`.

Arguments:

`lhs`: | Pointer to a pointer to the first vector.
`rhs`: | Pointer to a pointer to the second vector.

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_colex_cmp_untyped()` for an untyped variant of this function, or `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_int_list_sort.c`

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

    int main(void) {
        igraph_t graph;
        igraph_vector_int_list_t cliques;
        igraph_int_t i, n;

        /* Initialize the library. */
        igraph_setup();

        /* 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_gnm(&graph, 15, 80, IGRAPH_UNDIRECTED, IGRAPH_SIMPLE_SW, IGRAPH_EDGE_UNLABELED);

        /* Find all maximal cliques in the graph. IGRAPH_UNLIMITED signifies no limit on the clique sizes. */
        igraph_vector_int_list_init(&cliques, 0);
        igraph_maximal_cliques(&graph, &cliques, /* min_size */ IGRAPH_UNLIMITED, /* max_size */ IGRAPH_UNLIMITED, IGRAPH_UNLIMITED);

        /* Print the cliques in lexicographical order */
        printf("Maximal cliques in lexicographical order:\n");
        igraph_vector_int_list_sort(&cliques, igraph_vector_int_lex_cmp);
        n = igraph_vector_int_list_size(&cliques);
        for (i=0; i < n; ++i) {
            igraph_vector_int_print(igraph_vector_int_list_get_ptr(&cliques, i));
        }

        /* Print the cliques in colexicographical order */
        printf("\nMaximal cliques in colexicographical order:\n");
        igraph_vector_int_list_sort(&cliques, igraph_vector_int_colex_cmp);
        n = igraph_vector_int_list_size(&cliques);
        for (i=0; i < n; ++i) {
            igraph_vector_int_print(igraph_vector_int_list_get_ptr(&cliques, i));
        }

        /* Destroy data structures when we no longer need them */
        igraph_vector_int_list_destroy(&cliques);
        igraph_destroy(&graph);

        return 0;
    }

#### 2.9.12. `igraph_vector_colex_cmp_untyped` — Colexicographical comparison of two vectors.

    int igraph_vector_colex_cmp_untyped(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_colex_cmp()` for a type-safe variant of this function, `igraph_vector_lex_cmp_untyped()` to compare vectors starting from the first element.

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

### 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 not be 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);

The vector must not be empty.

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_int_t igraph_vector_which_min(const igraph_vector_t* v);

The vector must not be 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_int_t igraph_vector_which_max(const igraph_vector_t *v);

The vector must not be empty. 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.

    void 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.

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

#### 2.10.6. `igraph_vector_which_minmax` — Index of the minimum and maximum elements.

    void igraph_vector_which_minmax(const igraph_vector_t *v,
            igraph_int_t *which_min, igraph_int_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.

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:

`` | True if the size of the vector is zero and false otherwise.

Time complexity: O(1).

#### 2.11.2. `igraph_vector_size` — The size of the vector.

    igraph_int_t igraph_vector_size(const igraph_vector_t *v);

Returns the number of elements stored in the vector.

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_int_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:

`` | `igraph_vector_size()`.

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 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 interval.

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

Arguments:

`v`: | The vector object.
`low`: | The lower limit of the interval (inclusive).
`high`: | The higher limit of the interval (inclusive).

Returns:

`` | True if the vector is empty or all vector elements are in the interval, false otherwise. If any element is NaN, it will return 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:

`` | True if any element is NaN, false otherwise.

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

#### 2.11.10. `igraph_vector_is_all_finite` — Check if all elements are finite.

    igraph_bool_t igraph_vector_is_all_finite(const igraph_vector_t *v);

Arguments:

`v`: | The igraph_vector_t object to check.

Returns:

`` | True if none of the elements are infinite or NaN.

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 what);

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

Arguments:

`v`: | The input vector.
`what`: | 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` — Searches in a vector from a given position.

    igraph_bool_t igraph_vector_search(const igraph_vector_t *v,
            igraph_int_t from, igraph_real_t what, igraph_int_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_int_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_int_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 vector sorted of course).

Returns:

`` | True if `what` is found in the vector, 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_int_t *pos, igraph_int_t start, igraph_int_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 slice sorted) is returned. Note that this means that the returned index will point inside the slice (including its endpoints), but will not evaluate values outside the slice. 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_int_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 vector sorted).
`start`: | The start position of the slice to search (inclusive).
`end`: | The end position of the slice to search (exclusive).

Returns:

`` | True if `what` is found in the vector, 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_contains_sorted` — Binary search in a sorted vector.

    igraph_bool_t igraph_vector_contains_sorted(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:

`` | True if `what` is found in the vector, 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_int_t capacity);

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.
`capacity`: | 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_int_t new_size);

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
`new_size`: | 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.

    void igraph_vector_resize_min(igraph_vector_t *v);

This function attempts to deallocate the unused reserved storage of a vector. If it succeeds, `igraph_vector_size()` and `igraph_vector_capacity()` will be the same. The data in the vector is always preserved, even if deallocation is not successful.

Arguments:

`v`: | Pointer to an initialized vector.

See also:

`` | `igraph_vector_resize()`, `igraph_vector_reserve()`.

Time complexity: operating system dependent, O(n) at worst.

#### 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_int_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_int_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_int_t from, igraph_int_t to);

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. Complex vector operations

#### 2.14.1. `igraph_vector_complex_real` — Gives the real part of a complex vector.

    igraph_error_t igraph_vector_complex_real(const igraph_vector_complex_t *v,
                                   igraph_vector_t *real);

Arguments:

`v`: | Pointer to a complex vector.
`real`: | Pointer to an initialized vector. The result will be stored here.

Returns:

`` | Error code.

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

#### 2.14.2. `igraph_vector_complex_imag` — Gives the imaginary part of a complex vector.

    igraph_error_t igraph_vector_complex_imag(const igraph_vector_complex_t *v,
                                   igraph_vector_t *imag);

Arguments:

`v`: | Pointer to a complex vector.
`imag`: | Pointer to an initialized vector. The result will be stored here.

Returns:

`` | Error code.

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

#### 2.14.3. `igraph_vector_complex_realimag` — Gives the real and imaginary parts of a complex vector.

    igraph_error_t igraph_vector_complex_realimag(const igraph_vector_complex_t *v,
                                       igraph_vector_t *real,
                                       igraph_vector_t *imag);

Arguments:

`v`: | Pointer to a complex vector.
`real`: | Pointer to an initialized vector. The real part will be stored here.
`imag`: | Pointer to an initialized vector. The imaginary part will be stored here.

Returns:

`` | Error code.

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

#### 2.14.4. `igraph_vector_complex_create` — Creates a complex vector from a real and imaginary part.

    igraph_error_t igraph_vector_complex_create(igraph_vector_complex_t *v,
                                     const igraph_vector_t *real,
                                     const igraph_vector_t *imag);

Arguments:

`v`: | Pointer to an uninitialized complex vector.
`real`: | Pointer to the real part of the complex vector.
`imag`: | Pointer to the imaginary part of the complex vector.

Returns:

`` | Error code.

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

#### 2.14.5. `igraph_vector_complex_create_polar` — Creates a complex matrix from a magnitude and an angle.

    igraph_error_t igraph_vector_complex_create_polar(igraph_vector_complex_t *v,
                                           const igraph_vector_t *r,
                                           const igraph_vector_t *theta);

Arguments:

`v`: | Pointer to an uninitialized complex vector.
`r`: | Pointer to a real vector containing magnitudes.
`theta`: | Pointer to a real vector containing arguments (phase angles).

Returns:

`` | Error code.

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

#### 2.14.6. `igraph_vector_complex_all_almost_e` — Are all elements almost equal?

    igraph_bool_t igraph_vector_complex_all_almost_e(const igraph_vector_complex_t *lhs,
                                                     const igraph_vector_complex_t *rhs,
                                                     igraph_real_t eps);

Checks if the elements of two complex vectors are equal within a relative tolerance.

Arguments:

`lhs`: | The first vector.
`rhs`: | The second vector.
`eps`: | Relative tolerance, see `igraph_complex_almost_equals()` for details.

Returns:

`` | True if the two vectors are almost equal, false if there is at least one differing element or if the vectors are not of the same size.

#### 2.14.7. `igraph_vector_complex_zapsmall` — Replaces small elements of a complex vector by exact zeros.

    igraph_error_t igraph_vector_complex_zapsmall(igraph_vector_complex_t *v, igraph_real_t tol);

Similarly to `igraph_vector_zapsmall()`, small elements will be replaced by zeros. The operation is performed separately on the real and imaginary parts of the numbers. This way, complex numbers with a large real part and tiny imaginary part will effectively be transformed to real numbers. The default tolerance corresponds to two-thirds of the representable digits of igraph_real_t, i.e. `DBL_EPSILON^(2/3)` which is approximately `10^-10`.

Arguments:

`v`: | The vector to process, it will be changed in-place.
`tol`: | Tolerance value. Real and imaginary parts smaller than this in magnitude will be replaced by zeros. Pass in zero to use the default tolerance. Must not be negative.

Returns:

`` | Error code.

See also:

`` | `igraph_vector_complex_all_almost_e()` and `igraph_complex_almost_equals()` to perform comparisons with relative tolerances.

### 2.15. Sorting

#### 2.15.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.15.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.15.3. `igraph_vector_sort_ind` — Returns a permutation of indices that sorts a vector.

    igraph_error_t igraph_vector_sort_ind(
            const igraph_vector_t *v,
            igraph_vector_int_t *inds,
            igraph_order_t order);

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 `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
`order`: | whether the output array should be sorted in ascending or descending order. Use `IGRAPH_ASCENDING` for ascending and `IGRAPH_DESCENDING` for 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.16. Set operations on sorted vectors

#### 2.16.1. `igraph_vector_intersect_sorted` — Set 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.

For similar-size vectors, this function uses a straightforward linear scan. When the vector sizes differ substantially, it uses the set intersection method of Ricardo Baeza-Yates, which takes logarithmic time in the length of the larger vector.

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. https://doi.org/10.1007/978-3-540-27801-6_30

Arguments:

`v1`: | The first vector
`v2`: | The second vector
`result`: | The result vector, which will also be sorted.

Returns:

`` | Error code.

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.16.2. `igraph_vector_intersection_size_sorted` — Intersection size of two sorted vectors.

    igraph_int_t igraph_vector_intersection_size_sorted(
            const igraph_vector_t *v1,
            const igraph_vector_t *v2);

Counts elements that are present in both vectors. This is particularly useful for counting common neighbours of two vertices.

For similar-size vectors, this function uses a straightforward linear scan. When the vector sizes differ substantially, it uses the set intersection method of Ricardo Baeza-Yates, which takes logarithmic time in the length of the larger vector.

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. https://doi.org/10.1007/978-3-540-27801-6_30

Arguments:

`v1`: | The first vector
`v2`: | The second vector

Returns:

`` | The number of common elements.

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.16.3. `igraph_vector_difference_sorted` — Set difference of two sorted vectors.

    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.

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 `max(0, k1-k2)` times.

Arguments:

`v1`: | the first vector
`v2`: | the second vector
`result`: | the result vector

#### 2.16.4. `igraph_vector_difference_and_intersection_sorted` — Simultaneous difference and intersection of two sorted vectors.

    igraph_error_t igraph_vector_difference_and_intersection_sorted(
            const igraph_vector_t *v1, const igraph_vector_t *v2,
            igraph_vector_t *vdiff12, igraph_vector_t*vdiff21,
            igraph_vector_t*vint);

This function iterates over all the elements of the two input vectors and sorts them into three other vectors: elements that are in the first vector but not in the second, elements that are in the second vector but not in the first, and the intersection of the two vectors. The input vectors must be initialized. The output arguments can be `NULL`, but they must be initialized if they are not `NULL` and will be resized accordingly.

The multiplicities of the individual elements are treated consistently with `igraph_vector_difference_sorted()` and `igraph_vector_intersect_sorted()`: 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 intersection vector will include that element `min(k1, k2)` times, while the difference vectors will include that element `max(0, k1-k2)` and `max(0, k2-k1)` times, respectively.

Arguments:

`v1`: | the first vector
`v2`: | the second vector
`vdiff12`: | output vector containing the elements that are in the first vector but not the second one, or `NULL` if not needed
`vdiff21`: | output vector containing the elements that are in the second vector but not the first one, or `NULL` if not needed
`vint`: | output vector containing the intersection, or `NULL` if not needed

### 2.17. Pointer vectors (igraph_vector_ptr_t)

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`.

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 some function can be destroyed with a single call to `igraph_vector_ptr_destroy_all()` if the item destructor is set to `igraph_destroy()`.

#### 2.17.1. `igraph_vector_ptr_init` — Initialize a pointer vector (constructor).

    igraph_error_t igraph_vector_ptr_init(igraph_vector_ptr_t* v, igraph_int_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.17.2. `igraph_vector_ptr_init_copy` — Initializes a pointer vector from another one (constructor).

    igraph_error_t igraph_vector_ptr_init_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.17.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.17.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.17.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.17.6. `igraph_vector_ptr_size` — Gives the number of elements in the pointer vector.

    igraph_int_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.17.7. `igraph_vector_ptr_capacity` — Returns the allocated capacity of the pointer vector.

    igraph_int_t igraph_vector_ptr_capacity(const igraph_vector_ptr_t* v);

Arguments:

`v`: | The pointer vector object.

Returns:

`` | The allocated capacity.

Time complexity: O(1).

#### 2.17.8. `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.17.9. `igraph_vector_ptr_reserve` — Reserves memory for a pointer vector for later use.

    igraph_error_t igraph_vector_ptr_reserve(igraph_vector_ptr_t* v, igraph_int_t capacity);

Returns:

`` | Error code.

#### 2.17.10. `igraph_vector_ptr_resize` — Resizes a pointer vector.

    igraph_error_t igraph_vector_ptr_resize(igraph_vector_ptr_t* v, igraph_int_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.17.11. `igraph_vector_ptr_resize_min` — Deallocate the unused memory of a pointer vector.

    void igraph_vector_ptr_resize_min(igraph_vector_ptr_t* v);

This function attempts to deallocate the unused reserved storage of a pointer vector. If it succeeds, `igraph_vector_ptr_size()` and `igraph_vector_ptr_capacity()` will be the same. The data in the pointer vector is always preserved, even if deallocation is not successful.

Arguments:

`v`: | Pointer to an initialized pointer vector.

See also:

`` | `igraph_vector_ptr_resize()`, `igraph_vector_ptr_reserve()`.

Time complexity: operating system dependent, O(n) at worst.

#### 2.17.12. `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.17.13. `igraph_vector_ptr_pop_back` — Removes and returns the last element of a pointer vector.

    void *igraph_vector_ptr_pop_back(igraph_vector_ptr_t *v);

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

Arguments:

`v`: | The pointer vector.

Returns:

`` | The removed last element.

Time complexity: O(1).

#### 2.17.14. `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_int_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.17.15. `igraph_vector_ptr_get` — Access an element of a pointer vector.

    void *igraph_vector_ptr_get(const igraph_vector_ptr_t* v, igraph_int_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.17.16. `igraph_vector_ptr_set` — Assign to an element of a pointer vector.

    void igraph_vector_ptr_set(igraph_vector_ptr_t* v, igraph_int_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.17.17. `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 **`.

#### 2.17.18. `igraph_vector_ptr_sort_ind` — Returns 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.17.19. `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.17.20. `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.17.21. `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.17.22. `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_int_t nrow, igraph_int_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_init_array` — Initializes a matrix from an ordinary C array (constructor).

    igraph_error_t igraph_matrix_init_array(
            igraph_matrix_t *m, const igraph_real_t *data,
            igraph_int_t nrow, igraph_int_t ncol,
            igraph_matrix_storage_t storage);

The array is assumed to store the matrix data contiguously, either in a column-major or row-major format. In other words, `data` may store concatenated matrix columns or concatenated matrix rows. Constructing a matrix from column-major data is faster, as this is igraph's native storage format.

Arguments:

`v`: | Pointer to an uninitialized matrix object.
`data`: | A regular C array, storing the elements of the matrix in column-major order, i.e. the elements of the first column are stored first, followed by the second column and so on.
`nrow`: | The number of rows in the matrix.
`ncol`: | The number of columns in the matrix.
`storage`: | `IGRAPH_ROW_MAJOR` if the array is in row-major format, `IGRAPH_COLUMN_MAJOR` if the array is in column-major format.

Returns:

`` | Error code: `IGRAPH_ENOMEM` if there is not enough memory.

Time complexity: operating system specific, usually O(`nrow` `ncol`).

#### 3.2.3. `igraph_matrix_init_copy` — Copies a matrix.

    igraph_error_t igraph_matrix_init_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.4. `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. Accessing elements of a matrix

#### 3.4.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.4.2. `igraph_matrix_get` — Extract an element from a matrix.

    igraph_real_t igraph_matrix_get(const igraph_matrix_t *m,
                                    igraph_int_t row, igraph_int_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.4.3. `igraph_matrix_get_ptr` — Pointer to an element of a matrix.

    igraph_real_t* igraph_matrix_get_ptr(const igraph_matrix_t *m,
                                           igraph_int_t row, igraph_int_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.4.4. `igraph_matrix_set` — Set an element.

    void igraph_matrix_set(
            igraph_matrix_t* m, igraph_int_t row, igraph_int_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.5. Matrix views

#### 3.5.1. `igraph_matrix_view` — Creates a matrix view into an existing array.

    igraph_matrix_t igraph_matrix_view(
            const igraph_real_t *data,
            igraph_int_t nrow, igraph_int_t ncol);

This function lets you treat an existing C array as a matrix. The elements of the matrix are assumed to be stored in column-major order in the array, i.e. the elements of the first column are stored first, followed by the second column and so on.

Since this function creates a view into an existing array, you must not destroy the igraph_matrix_t object when you are done with it. Similarly, you must not call any function on it that may attempt to modify the size of the matrix. Modifying an element in the matrix will modify the underlying array as the two share the same memory block.

Arguments:

`data`: | The raw array that the matrix provides a view into.
`nrow`: | The number of rows in the matrix.
`ncol`: | The number of columns in the matrix.

Returns:

`` | The matrix object providing the view into the array.

Time complexity: O(1).

#### 3.5.2. `igraph_matrix_view_from_vector` — Creates a matrix view that treats an existing vector as a matrix.

    igraph_matrix_t igraph_matrix_view_from_vector(
        const igraph_vector_t *v,
        igraph_int_t nrow
    );

This function lets you treat an existing igraph vector as a matrix. The elements of the matrix are assumed to be stored in column-major order in the vector, i.e. the elements of the first column are stored first, followed by the second column and so on.

Since this function creates a view into an existing vector, you must not destroy the `igraph_matrix_t` object when you are done with it. Similarly, you must not call any function on it that may attempt to modify the size of the vector. Modifying an element in the matrix will modify the underlying vector as the two share the same memory block.

Additionally, you must not attempt to grow the underlying vector by any vector operation as that may result in a re-allocation of the backing memory block of the vector, and the matrix view will not be informed about the re-allocation so it will point to an invalid memory area afterwards.

Arguments:

`v`: | The vector that the matrix will provide a view into.
`nrow`: | The number of rows in the matrix. The number of columns will be derived implicitly from the size of the vector. If the number of items in the vector is not divisible by the number of rows, the last few elements of the vector will not be covered by the view.

Returns:

`` | The matrix object providing the view into the vector.

Time complexity: O(1).

### 3.6. Copying matrices

#### 3.6.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, igraph_matrix_storage_t storage);

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.
`storage`: | `IGRAPH_ROW_MAJOR` to write the data in row-major format, `IGRAPH_COLUMN_MAJOR` to write it in column-major format. Currently igraph uses column-major storage internally, thus `IGRAPH_COLUMN_MAJOR` is much faster.

Returns:

`` | Error code.

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

#### 3.6.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.6.3. `igraph_matrix_swap` — Swap two matrices.

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

The contents of the two matrices will be swapped.

Arguments:

`m1`: | The first matrix.
`m2`: | The second matrix.

Time complexity: O(1).

### 3.7. Operations on rows and columns

#### 3.7.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_int_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.7.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_int_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.7.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_int_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.7.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_int_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.7.5. `igraph_matrix_swap_rows` — Swap two rows.

    igraph_error_t igraph_matrix_swap_rows(igraph_matrix_t *m,
                                           igraph_int_t i, igraph_int_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.7.6. `igraph_matrix_swap_cols` — Swap two columns.

    igraph_error_t igraph_matrix_swap_cols(igraph_matrix_t *m,
                                           igraph_int_t i, igraph_int_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.7.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.7.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.7.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.8. Matrix operations

#### 3.8.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.8.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.8.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.8.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.8.5. `igraph_matrix_mul_elements` — Elementwise matrix 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.8.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.8.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.8.8. `igraph_matrix_prod` — Product of all matrix elements.

    igraph_real_t igraph_matrix_prod(const igraph_matrix_t *m);

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

Arguments:

`m`: | The input matrix.

Returns:

`` | The product of the elements.

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

#### 3.8.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.8.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.8.11. `igraph_matrix_transpose` — Transpose of a matrix.

    igraph_error_t igraph_matrix_transpose(igraph_matrix_t *m);

Calculates the transpose of a matrix. When the matrix is non-square, this function reallocates the storage 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.9. Matrix comparisons

#### 3.9.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);

Checks element-wise equality of two matrices. For matrices containing floating point values, consider using `igraph_matrix_all_almost_e()`.

Arguments:

`lhs`: | The first matrix.
`rhs`: | The second matrix.

Returns:

`` | True if the elements in the `lhs` are all equal to the corresponding elements in `rhs`. Returns false if the dimensions of the matrices don't match.

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

#### 3.9.2. `igraph_matrix_all_almost_e` — Are all elements almost equal?

    igraph_bool_t igraph_matrix_all_almost_e(const igraph_matrix_t *lhs,
                                             const igraph_matrix_t *rhs,
                                             igraph_real_t eps);

Checks if the elements of two matrices are equal within a relative tolerance.

Arguments:

`lhs`: | The first matrix.
`rhs`: | The second matrix.
`eps`: | Relative tolerance, see `igraph_almost_equals()` for details.

Returns:

`` | True if the two matrices are almost equal, false if there is at least one differing element or if the matrices are not of the same dimensions.

#### 3.9.3. `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:

`` | True if the elements in the `lhs` are all less than the corresponding elements in `rhs`. Returns false if the dimensions of the matrices don't match.

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

#### 3.9.4. `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:

`` | True if the elements in the `lhs` are all greater than the corresponding elements in `rhs`. Returns false if the dimensions of the matrices don't match.

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

#### 3.9.5. `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:

`` | True if the elements in the `lhs` are all less than or equal to the corresponding elements in `rhs`. Returns false if the dimensions of the matrices don't match.

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

#### 3.9.6. `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:

`` | True if the elements in the `lhs` are all greater than or equal to the corresponding elements in `rhs`. Returns false if the dimensions of the matrices don't match.

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

#### 3.9.7. `igraph_matrix_zapsmall` — Replaces small elements of a matrix by exact zeros.

    igraph_error_t igraph_matrix_zapsmall(igraph_matrix_t *m, igraph_real_t tol);

Matrix elements which are smaller in magnitude than the given absolute tolerance will be replaced by exact zeros. The default tolerance corresponds to two-thirds of the representable digits of igraph_real_t, i.e. `DBL_EPSILON^(2/3)` which is approximately `10^-10`.

Arguments:

`m`: | The matrix to process, it will be changed in-place.
`tol`: | Tolerance value. Numbers smaller than this in magnitude will be replaced by zeros. Pass in zero to use the default tolerance. Must not be negative.

Returns:

`` | Error code.

See also:

`` | `igraph_matrix_all_almost_e()` and `igraph_almost_equals()` to perform comparisons with relative tolerances.

### 3.10. Combining matrices

#### 3.10.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.10.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.11. Finding minimum and maximum

#### 3.11.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.11.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.11.3. `igraph_matrix_which_min` — Indices of the smallest element.

    void igraph_matrix_which_min(
            const igraph_matrix_t *m, igraph_int_t *i, igraph_int_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_int_t. The row index of the minimum is stored here.
`j`: | Pointer to an igraph_int_t. The column index of the minimum is stored here.

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

#### 3.11.4. `igraph_matrix_which_max` — Indices of the largest element.

    void igraph_matrix_which_max(
            const igraph_matrix_t *m, igraph_int_t *i, igraph_int_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_int_t. The row index of the maximum is stored here.
`j`: | Pointer to an igraph_int_t. The column index of the maximum is stored here.

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

#### 3.11.5. `igraph_matrix_minmax` — Minimum and maximum elements of a matrix.

    void 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.

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

#### 3.11.6. `igraph_matrix_which_minmax` — Indices of the minimum and maximum elements.

    void igraph_matrix_which_minmax(const igraph_matrix_t *m,
            igraph_int_t *imin, igraph_int_t *jmin,
            igraph_int_t *imax, igraph_int_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_int_t, the row index of the minimum is stored here.
`jmin`: | Pointer to an igraph_int_t, the column index of the minimum is stored here.
`imax`: | Pointer to an igraph_int_t, the row index of the maximum is stored here.
`jmax`: | Pointer to an igraph_int_t, the column index of the maximum is stored here.

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

### 3.12. Matrix properties

#### 3.12.1. `igraph_matrix_empty` — Is the matrix empty?

    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.12.2. `igraph_matrix_isnull` — Checks 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.12.3. `igraph_matrix_size` — The number of elements in a matrix.

    igraph_int_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.12.4. `igraph_matrix_capacity` — Returns the number of elements allocated for a matrix.

    igraph_int_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:

`` | `igraph_matrix_size()`, `igraph_matrix_nrow()`, `igraph_matrix_ncol()`.

Time complexity: O(1).

#### 3.12.5. `igraph_matrix_nrow` — The number of rows in a matrix.

    igraph_int_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.12.6. `igraph_matrix_ncol` — The number of columns in a matrix.

    igraph_int_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.12.7. `igraph_matrix_is_symmetric` — Is the matrix symmetric?

    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.12.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.13. Searching for elements

#### 3.13.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.13.2. `igraph_matrix_search` — Search from a given position.

    igraph_bool_t igraph_matrix_search(const igraph_matrix_t *m,
            igraph_int_t from, igraph_real_t what, igraph_int_t *pos,
            igraph_int_t *row, igraph_int_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_int_t. If the element is found, then this is set to the position of its first appearance.
`row`: | Pointer to an igraph_int_t. If the element is found, then this is set to its row index.
`col`: | Pointer to an igraph_int_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.14. Resizing operations

#### 3.14.1. `igraph_matrix_resize` — Resizes a matrix.

    igraph_error_t igraph_matrix_resize(igraph_matrix_t *m, igraph_int_t nrow, igraph_int_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.14.2. `igraph_matrix_resize_min` — Deallocates unused memory for a matrix.

    void igraph_matrix_resize_min(igraph_matrix_t *m);

This function attempts to deallocate the unused reserved storage of a matrix.

Arguments:

`m`: | Pointer to an initialized matrix.

See also:

`` | `igraph_matrix_resize()`.

Time complexity: operating system dependent, O(n) at worst.

#### 3.14.3. `igraph_matrix_add_rows` — Adds rows to a matrix.

    igraph_error_t igraph_matrix_add_rows(igraph_matrix_t *m, igraph_int_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.14.4. `igraph_matrix_add_cols` — Adds columns to a matrix.

    igraph_error_t igraph_matrix_add_cols(igraph_matrix_t *m, igraph_int_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.14.5. `igraph_matrix_remove_row` — Remove a row.

    igraph_error_t igraph_matrix_remove_row(igraph_matrix_t *m, igraph_int_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.14.6. `igraph_matrix_remove_col` — Removes a column from a matrix.

    igraph_error_t igraph_matrix_remove_col(igraph_matrix_t *m, igraph_int_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.

### 3.15. Complex matrix operations

#### 3.15.1. `igraph_matrix_complex_real` — Gives the real part of a complex matrix.

    igraph_error_t igraph_matrix_complex_real(const igraph_matrix_complex_t *m,
                                   igraph_matrix_t *real);

Arguments:

`m`: | Pointer to a complex matrix.
`real`: | Pointer to an initialized matrix. The result will be stored here.

Returns:

`` | Error code.

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

#### 3.15.2. `igraph_matrix_complex_imag` — Gives the imaginary part of a complex matrix.

    igraph_error_t igraph_matrix_complex_imag(const igraph_matrix_complex_t *m,
                                   igraph_matrix_t *imag);

Arguments:

`m`: | Pointer to a complex matrix.
`imag`: | Pointer to an initialized matrix. The result will be stored here.

Returns:

`` | Error code.

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

#### 3.15.3. `igraph_matrix_complex_realimag` — Gives the real and imaginary parts of a complex matrix.

    igraph_error_t igraph_matrix_complex_realimag(const igraph_matrix_complex_t *m,
                                       igraph_matrix_t *real,
                                       igraph_matrix_t *imag);

Arguments:

`m`: | Pointer to a complex matrix.
`real`: | Pointer to an initialized matrix. The real part will be stored here.
`imag`: | Pointer to an initialized matrix. The imaginary part will be stored here.

Returns:

`` | Error code.

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

#### 3.15.4. `igraph_matrix_complex_create` — Creates a complex matrix from a real and imaginary part.

    igraph_error_t igraph_matrix_complex_create(igraph_matrix_complex_t *m,
                                     const igraph_matrix_t *real,
                                     const igraph_matrix_t *imag);

Arguments:

`m`: | Pointer to an uninitialized complex matrix.
`real`: | Pointer to the real part of the complex matrix.
`imag`: | Pointer to the imaginary part of the complex matrix.

Returns:

`` | Error code.

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

#### 3.15.5. `igraph_matrix_complex_create_polar` — Creates a complex matrix from a magnitude and an angle.

    igraph_error_t igraph_matrix_complex_create_polar(igraph_matrix_complex_t *m,
                                           const igraph_matrix_t *r,
                                           const igraph_matrix_t *theta);

Arguments:

`m`: | Pointer to an uninitialized complex matrix.
`r`: | Pointer to a real matrix containing magnitudes.
`theta`: | Pointer to a real matrix containing arguments (phase angles).

Returns:

`` | Error code.

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

#### 3.15.6. `igraph_matrix_complex_all_almost_e` — Are all elements almost equal?

    igraph_bool_t igraph_matrix_complex_all_almost_e(igraph_matrix_complex_t *lhs,
                                                      igraph_matrix_complex_t *rhs,
                                                      igraph_real_t eps);

Checks if the elements of two complex matrices are equal within a relative tolerance.

Arguments:

`lhs`: | The first matrix.
`rhs`: | The second matrix.
`eps`: | Relative tolerance, see `igraph_complex_almost_equals()` for details.

Returns:

`` | True if the two matrices are almost equal, false if there is at least one differing element or if the matrices are not of the same dimensions.

#### 3.15.7. `igraph_matrix_complex_zapsmall` — Replaces small elements of a complex matrix by exact zeros.

    igraph_error_t igraph_matrix_complex_zapsmall(igraph_matrix_complex_t *m, igraph_real_t tol);

Similarly to `igraph_matrix_zapsmall()`, small elements will be replaced by zeros. The operation is performed separately on the real and imaginary parts of the numbers. This way, complex numbers with a large real part and tiny imaginary part will effectively be transformed to real numbers. The default tolerance corresponds to two-thirds of the representable digits of igraph_real_t, i.e. `DBL_EPSILON^(2/3)` which is approximately `10^-10`.

Arguments:

`m`: | The matrix to process, it will be changed in-place.
`tol`: | Tolerance value. Real and imaginary parts smaller than this in magnitude will be replaced by zeros. Pass in zero to use the default tolerance. Must not be negative.

Returns:

`` | Error code.

See also:

`` | `igraph_matrix_complex_all_almost_e()` and `igraph_complex_almost_equals()` to perform comparisons with relative tolerances.

## 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.4. File `examples/simple/igraph_sparsemat.c`

    #include <igraph.h>

    int main(void) {

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

        /* Initialize the library. */
        igraph_setup();

        /* 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_sparsemat_init(&A, 1, 1, 0);
        igraph_ring(&G, VC, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
        igraph_get_adjacency_sparse(&G, &A, IGRAPH_GET_ADJACENCY_BOTH, NULL, IGRAPH_LOOPS_ONCE);
        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_init_eye(&A, /*n=*/ 5, /*nzmax=*/ 5, /*value=*/ 1.0, /*compress=*/ 0);
        igraph_sparsemat_init_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_init_diag(&A, /*nzmax=*/ 5, /*values=*/ &vect, /*compress=*/ 0);
        igraph_sparsemat_init_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_sparsemat_init(&A, 1, 1, 0);
        igraph_kary_tree(&G, 10, /*children=*/ 2, IGRAPH_TREE_OUT);
        igraph_get_adjacency_sparse(&G, &A, IGRAPH_GET_ADJACENCY_BOTH, NULL, IGRAPH_LOOPS_ONCE);
        igraph_destroy(&G);
        igraph_sparsemat_compress(&A, &B);
        igraph_sparsemat_print(&B, stdout);
        igraph_sparsemat_transpose(&B, &C);
        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_sparsemat_init(&A, 1, 1, 0);
        igraph_sparsemat_init(&B, 1, 1, 0);
        igraph_star(&G, 10, IGRAPH_STAR_OUT, /*center=*/ 0);
        igraph_ring(&H, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
        igraph_get_adjacency_sparse(&G, &A, IGRAPH_GET_ADJACENCY_BOTH, NULL, IGRAPH_LOOPS_ONCE);
        igraph_get_adjacency_sparse(&H, &B, IGRAPH_GET_ADJACENCY_BOTH, NULL, IGRAPH_LOOPS_ONCE);
        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.5. File `examples/simple/igraph_sparsemat3.c`

    #include <igraph.h>

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

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

        igraph_matrix_resize(res, nrow, ncol);

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

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

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

        igraph_matrix_resize(res, nrow, ncol);

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

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

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

        igraph_matrix_resize(res, nrow, ncol);

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

    void random_permutation(igraph_vector_int_t *vec) {
        /* We just do size(vec) * 2 swaps */
        igraph_int_t one, two, i, n = igraph_vector_int_size(vec);
        igraph_int_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;
        }
    }

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

        igraph_matrix_init(&A_dense, 1, 1);
        igraph_sparsemat_as_matrix(&A_dense, A);
        result = igraph_matrix_all_e(&A_dense, M);
        igraph_matrix_destroy(&A_dense);

        return result;
    }

    int main(void) {

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

        /* Initialize the library. */
        igraph_setup();

        /* 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_int_t r = RNG_INTEGER(0, NROW - 1);
            igraph_int_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_range(&p, 0, NROW);
        igraph_vector_int_init_range(&q, 0, NCOL);

        /* 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_int_t r = RNG_INTEGER(0, NROW - 1);
            igraph_int_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;
        }

        igraph_sparsemat_destroy(&A);

        /* Getting single elements with index() */

        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;
            }
        }

        /* Getting single elements with get() */

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

        for (i = 0; i < 100; i++) {
            igraph_int_t row = RNG_INTEGER(0, NROW - 1);
            igraph_int_t col = RNG_INTEGER(0, NCOL - 1);
            if (igraph_sparsemat_get(&B, row, col) != MATRIX(M, row, col)) {
                return 4;
            }
        }

        /* Getting submatrices with index() */

        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_int_t r = RNG_INTEGER(0, NROW - 1);
            igraph_int_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.6. File `examples/simple/igraph_sparsemat4.c`

    #include <igraph.h>

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

        igraph_vector_t res;
        igraph_real_t min, max;
        igraph_bool_t success;
        igraph_sparsemat_iterator_t it;

        igraph_vector_init_copy(&res, b);

        igraph_sparsemat_iterator_init(&it, (igraph_sparsemat_t*) A);
        while (!igraph_sparsemat_iterator_end(&it)) {
            igraph_int_t row = igraph_sparsemat_iterator_row(&it);
            igraph_int_t col = igraph_sparsemat_iterator_col(&it);
            igraph_real_t value = igraph_sparsemat_iterator_get(&it);
            VECTOR(res)[row] -= VECTOR(*x)[col] * value;
            igraph_sparsemat_iterator_next(&it);
        }

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

        success = fabs(min) < 1e-12 && fabs(max) < 1e-12;

        if (!success) {
            printf("Incorrect solution.\n\n");
            printf("A =\n"); igraph_sparsemat_print(A, stdout); printf("\n");
            printf("x =\n"); igraph_vector_print(x); printf("\n");
            printf("b =\n"); igraph_vector_print(b); printf("\n");
            printf("difference between A*x and b =\n");
            igraph_vector_print(&res); printf("\n\n");
        }

        igraph_vector_destroy(&res);

        return success;
    }

    int main(void) {

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

        /* Initialize the library. */
        igraph_setup();

        /* Seed the RNG for reproducible results */
        igraph_rng_seed(igraph_rng_default(), 123);

        /* 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_int_t r = RNG_INTEGER(0, DIM - 1);
            igraph_int_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_int_t r = RNG_INTEGER(0, DIM - 1);
            igraph_int_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);
        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_int_t r = RNG_INTEGER(0, DIM - 1);
            igraph_int_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);

        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_int_t r = RNG_INTEGER(0, DIM - 1);
            igraph_int_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);
        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);
        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_int_t from = RNG_INTEGER(0, DIM - 1);
            igraph_int_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);
        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_int_t from = RNG_INTEGER(0, DIM - 1);
            igraph_int_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.7. File `examples/simple/igraph_sparsemat6.c`

    #include <igraph.h>

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

        /* Initialize the library. */
        igraph_setup();

        igraph_rng_seed(igraph_rng_default(), 42);

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

        igraph_matrix_init(&mat, NROW, NCOL);
        for (igraph_int_t i = 0; i < NUM_NONZEROS; i++) {
            igraph_int_t r = igraph_rng_get_integer(igraph_rng_default(), 0, NROW - 1);
            igraph_int_t 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.8. File `examples/simple/igraph_sparsemat7.c`

    #include <igraph.h>

    #define DIM1 10
    #define DIM2 5

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

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

        /* Initialize the library. */
        igraph_setup();

        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 (int i = 0; i < 10; i++) {
            igraph_sparsemat_entry(&spmat, RANDINT(DIM1 - 1), RANDINT(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.9. File `examples/simple/igraph_sparsemat8.c`

    #include <igraph.h>

    #define DIM1 10
    #define DIM2 5

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

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

        /* Initialize the library. */
        igraph_setup();

        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_init_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_init_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_int_t rows,
            igraph_int_t cols, igraph_int_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_init_copy` — Copies a sparse matrix.

    igraph_error_t igraph_sparsemat_init_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_init_diag` — Creates a sparse diagonal matrix.

    igraph_error_t igraph_sparsemat_init_diag(
        igraph_sparsemat_t *A, igraph_int_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.4. `igraph_sparsemat_init_eye` — Creates a sparse identity matrix.

    igraph_error_t igraph_sparsemat_init_eye(
        igraph_sparsemat_t *A, igraph_int_t n, igraph_int_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.5. `igraph_sparsemat_realloc` — Allocates more (or less) memory for a sparse matrix.

    igraph_error_t igraph_sparsemat_realloc(igraph_sparsemat_t *A, igraph_int_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.6. `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.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_int_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_int_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_is_symmetric` — Returns whether a sparse matrix is symmetric.

    igraph_error_t igraph_sparsemat_is_symmetric(const igraph_sparsemat_t *A, igraph_bool_t *result);

Arguments:

`A`: | The input matrix
`result`: | Pointer to an `igraph_bool_t` ; the result is provided here.

Returns:

`` | Error code.

#### 4.3.8. `igraph_sparsemat_get` — Return the value of a single element from a sparse matrix.

    igraph_real_t igraph_sparsemat_get(
        const igraph_sparsemat_t *A, igraph_int_t row, igraph_int_t col
    );

Arguments:

`A`: | The input matrix, in triplet or column-compressed format.
`row`: | The row index
`col`: | The column index

Returns:

`` | The value of the cell with the given row and column indices in the matrix; zero if the indices are out of bounds.

Time complexity: TODO.

#### 4.3.9. `igraph_sparsemat_getelements` — Returns all elements of a sparse matrix.

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

This function will return the elements of a sparse matrix in three vectors. Two vectors will indicate where the elements are located, and one will specify the elements themselves.

Arguments:

`A`: | A sparse matrix in either triplet or compressed form.
`i`: | An initialized integer vector. This will store the rows of the returned elements.

`j`:

An initialized integer 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.10. `igraph_sparsemat_getelements_sorted` — Returns all elements of a sparse matrix, sorted by row and column indices.

    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 three vectors. Two vectors will indicate where the elements are located, and one will specify the elements themselves.

Sorting is done based on the indices of the elements, not their numeric values. The returned entries will be sorted by column indices; entries in the same column are then sorted by row indices.

Arguments:

`A`: | A sparse matrix in either triplet or compressed form.
`i`: | An initialized integer vector. This will store the rows of the returned elements.

`j`:

An initialized integer 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: TODO.

#### 4.3.11. `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_INFINITY` if the matrix has zero elements.

Time complexity: TODO.

#### 4.3.12. `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_INFINITY` if the matrix has zero elements.

Time complexity: TODO.

#### 4.3.13. `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_INFINITY` if the matrix has zero elements.
`max`: | The maximum in the input matrix is stored here, or `-IGRAPH_INFINITY` if the matrix has zero elements.

Returns:

`` | Error code.

Time complexity: TODO.

#### 4.3.14. `igraph_sparsemat_count_nonzero` — Counts nonzero elements of a sparse matrix.

    igraph_int_t igraph_sparsemat_count_nonzero(igraph_sparsemat_t *A);

Arguments:

`A`: | The input matrix, column-compressed.

Returns:

`` | Error code.

Time complexity: TODO.

#### 4.3.15. `igraph_sparsemat_count_nonzerotol` — Counts nonzero elements of a sparse matrix, ignoring elements close to zero.

    igraph_int_t 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:

`A`: | The input matrix, column-compressed.
`tol`: | The tolerance for zero comparisons.

Returns:

`` | Error code.

Time complexity: TODO.

#### 4.3.16. `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.17. `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.18. `igraph_sparsemat_nonzero_storage` — Returns number of stored entries of a sparse matrix.

    igraph_int_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_int_t row, igraph_int_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_int_t (*fkeep)(igraph_int_t, igraph_int_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_int_t`, the row index of the entry, the second is another `igraph_int_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 factor.

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
    );

Arguments:

`A`: | The input matrix, column-compressed or triple format.
`res`: | Pointer to an uninitialized sparse matrix, the result is stored here.

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 value, `A` is multiplied by `alpha` before the addition.
`beta`: | Real value, `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_int_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_int_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 and clears all the elements.

    igraph_error_t igraph_sparsemat_resize(igraph_sparsemat_t *A, igraph_int_t nrow,
                                igraph_int_t ncol, igraph_int_t nzmax);

This function resizes a sparse matrix. The resized sparse matrix will become empty, even if it contained nonzero entries.

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.4.14. `igraph_sparsemat_sort` — Sorts all elements of a sparse matrix by row and column indices.

    igraph_error_t igraph_sparsemat_sort(const igraph_sparsemat_t *A,
                              igraph_sparsemat_t *sorted);

This function will sort the elements of a sparse matrix such that iterating over the entries will return them sorted by column indices; elements in the same column are then sorted by row indices.

Arguments:

`A`: | A sparse matrix in either triplet or compressed form.
`sorted`: | An uninitialized sparse matrix; the result will be returned here. The result will be in triplet form if the input was in triplet form, otherwise it will be in compressed form. Note that sorting is more efficient when the matrix is already in compressed form.

Returns:

`` | Error code.

Time complexity: TODO

### 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, const 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_int_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_int_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_int_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_int_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(igraph_int_t 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(igraph_int_t 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,
                                 igraph_int_t order);

Solve Ax=b, where A is a symmetric positive definite matrix.

Arguments:

`A`: | The input matrix, in column-compressed format.
`b`: | 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,
                               igraph_int_t 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:

`A`: | The input matrix, must be column-compressed.
`options`: | It is passed to `igraph_arpack_rssolve()`. Supply `NULL` here to use the defaults. 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()`. Supply `NULL` here to use the defaults. 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_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`: | The tolerance for zero comparisons. Values closer than `tol` to zero are considered as zero, and will not be included in the sparse matrix.

Returns:

`` | Error code.

See also:

`` | `igraph_sparsemat_as_matrix()` for the reverse conversion.

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

#### 4.9.2. `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.

See also:

`` | `igraph_matrix_as_sparsemat()` for the reverse conversion.

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. Stacks

### 5.1. `igraph_stack_init` — Initializes a stack.

    igraph_error_t igraph_stack_init(igraph_stack_t* s, igraph_int_t capacity);

The initialized stack is always empty.

Arguments:

`s`: | Pointer to an uninitialized stack.
`capacity`: | The number of elements to allocate memory for.

Returns:

`` | Error code.

Time complexity: O(`size`).

### 5.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).

### 5.3. `igraph_stack_reserve` — Reserve memory.

    igraph_error_t igraph_stack_reserve(igraph_stack_t* s, igraph_int_t capacity);

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.

### 5.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).

### 5.5. `igraph_stack_size` — Returns the number of elements in a stack.

    igraph_int_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).

### 5.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).

### 5.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.

### 5.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).

### 5.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).

## 6. 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.10. File `examples/simple/dqueue.c`

    #include <igraph.h>

    int main(void) {

        igraph_dqueue_t q;

        /* Initialize the library. */
        igraph_setup();

        /* 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 (int 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 (int i = 0; i < 10; i++) {
            igraph_dqueue_push(&q, i);
        }
        for (int 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;
    }

### 6.1. `igraph_dqueue_init` — Initialize a double ended queue (deque).

    igraph_error_t igraph_dqueue_init(igraph_dqueue_t* q, igraph_int_t capacity);

The queue will be always empty.

Arguments:

`q`: | Pointer to an uninitialized deque.
`capacity`: | How many elements to allocate memory for.

Returns:

`` | Error code.

Time complexity: O(`capacity`).

### 6.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).

### 6.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).

### 6.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).

### 6.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).

### 6.6. `igraph_dqueue_size` — Number of elements in the queue.

    igraph_int_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).

### 6.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).

### 6.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).

### 6.9. `igraph_dqueue_get` — Access an element in a queue.

    igraph_real_t igraph_dqueue_get(const igraph_dqueue_t *q, igraph_int_t idx);

Arguments:

`q`: | The queue.
`idx`: | The index of the element within the queue.

Returns:

`` | The desired element.

Time complexity: O(1).

### 6.10. `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).

### 6.11. `igraph_dqueue_pop_back` — Removes 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).

### 6.12. `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 note 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.)

## 7. Maximum and minimum heaps

### 7.1. `igraph_heap_init` — Initializes an empty heap object.

    igraph_error_t igraph_heap_init(igraph_heap_t* h, igraph_int_t capacity);

Creates an empty heap, and also allocates memory for some elements.

Arguments:

`h`: | Pointer to an uninitialized heap object.
`capacity`: | Number of elements to allocate memory for.

Returns:

`` | Error code.

Time complexity: O(`alloc_size`), assuming memory allocation is a linear operation.

### 7.2. `igraph_heap_init_array` — Build a heap from an array.

    igraph_error_t igraph_heap_init_array(igraph_heap_t *h, const igraph_real_t *data, igraph_int_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.

### 7.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).

### 7.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).

### 7.5. `igraph_heap_empty` — Decides whether a heap object is empty.

    igraph_bool_t igraph_heap_empty(const igraph_heap_t* h);

Arguments:

`h`: | The heap object.

Returns:

`` | `true` if the heap is empty, `false` otherwise.

TIme complexity: O(1).

### 7.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.

### 7.7. `igraph_heap_top` — Top element.

    igraph_real_t igraph_heap_top(const 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).

### 7.8. `igraph_heap_delete_top` — Removes and returns 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.

### 7.9. `igraph_heap_size` — Number of elements in the heap.

    igraph_int_t igraph_heap_size(const 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).

### 7.10. `igraph_heap_reserve` — Reserves memory for a heap.

    igraph_error_t igraph_heap_reserve(igraph_heap_t* h, igraph_int_t capacity);

Allocates memory for future use. The size of the heap is unchanged. If the heap is larger than the `capacity` parameter then nothing happens.

Arguments:

`h`: | The heap object.
`capacity`: | The number of elements to allocate memory for.

Returns:

`` | Error code.

Time complexity: O(`capacity`) if `capacity` is larger than the current number of elements. O(1) otherwise.

## 8. String vectors

The igraph_strvector_t type is a vector of null-terminated strings. It is used internally for storing graph attribute names as well as string attributes in the C attribute handler.

This container automatically manages the memory of its elements. The strings within an igraph_strvector_t should be considered constant, and not modified directly. Functions that add new elements always make copies of the string passed to them.

Example 7.11. File `examples/simple/igraph_strvector.c`

    #include <igraph.h>

    void strvector_print(const igraph_strvector_t sv) {
        igraph_int_t i, s = igraph_strvector_size(&sv);
        for (i = 0; i < s; i++) {
            printf("---%s---\n", igraph_strvector_get(&sv, i));
        }
        printf("\n");
    }

    int main(void) {

        igraph_strvector_t sv1, sv2;

        /* Initialize the library. */
        igraph_setup();

        printf("Initializing and setting elements:\n");
        igraph_strvector_init(&sv1, 5);

        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");
        strvector_print(sv1);

        printf("strvector size after first removing one element, and then the rest:\n");
        igraph_strvector_remove(&sv1, 4);
        igraph_strvector_remove_section(&sv1, 0, 4);
        printf("%" IGRAPH_PRId "\n\n", igraph_strvector_size(&sv1));

        printf("Resize to three elements, and set them:\n");
        igraph_strvector_resize(&sv1, 3);
        igraph_strvector_set(&sv1, 0, "zero");
        igraph_strvector_set(&sv1, 1, "one");
        igraph_strvector_set(&sv1, 2, "two");
        strvector_print(sv1);

        printf("Then copy the first element over the third element:\n");
        igraph_strvector_set(&sv1, 2, igraph_strvector_get(&sv1, 0));
        strvector_print(sv1);

        printf("Make a copy of the strvector and set the last element of the copy:\n");
        igraph_strvector_init_copy(&sv2, &sv1);
        igraph_strvector_set(&sv2, 2, "copy two");
        strvector_print(sv2);

        printf("Append the copy to the strvector:\n");
        igraph_strvector_append(&sv1, &sv2);
        strvector_print(sv1);

        printf("Add two strings at the end:\n");
        igraph_strvector_push_back(&sv1, "zeroth");
        igraph_strvector_push_back(&sv1, "first");
        strvector_print(sv1);
        igraph_strvector_destroy(&sv1);

        printf("strvector size after clearing it:\n");
        igraph_strvector_clear(&sv2);
        printf("%" IGRAPH_PRId "\n", igraph_strvector_size(&sv2));

        igraph_strvector_destroy(&sv2);

        return 0;
    }

### 8.1. `igraph_strvector_init` — Initializes a string vector.

    igraph_error_t igraph_strvector_init(igraph_strvector_t *sv, igraph_int_t size);

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.
`size`: | The (initial) length of the string vector.

Returns:

`` | Error code.

Time complexity: O(`len`).

### 8.2. `igraph_strvector_init_copy` — Initialization by copying.

    igraph_error_t igraph_strvector_init_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`.

### 8.3. `igraph_strvector_destroy` — Frees the memory allocated for the string vector.

    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.

### 8.4. `STR` — Indexing string vectors.

    #define STR(sv,i)

This is a macro that allows to query the elements of a string vector, just like `igraph_strvector_get()`. Note this macro cannot be used to set an element. Use `igraph_strvector_set()` to set an element instead.

Arguments:

`sv`: | The string vector
`i`: | The index of the element.

Returns:

`` | The element at position `i`.

Time complexity: O(1).

### Warning

Deprecated since version 0.10.9. Please do not use this function in new code; use `igraph_strvector_get()` instead.

### 8.5. `igraph_strvector_get` — Retrieves an element of a string vector.

    const char *igraph_strvector_get(const igraph_strvector_t *sv, igraph_int_t idx);

Query an element of a string vector. The returned string must not be modified.

Arguments:

`sv`: | The input string vector.
`idx`: | The index of the element to query.

Time complexity: O(1).

### 8.6. `igraph_strvector_set` — Sets an element of the string vector from a string.

    igraph_error_t igraph_strvector_set(igraph_strvector_t *sv, igraph_int_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.

### 8.7. `igraph_strvector_set_len` — Sets an element of the string vector given a buffer and its size.

    igraph_error_t igraph_strvector_set_len(igraph_strvector_t *sv, igraph_int_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.

### 8.8. `igraph_strvector_push_back` — Adds an element to the back of a string vector.

    igraph_error_t igraph_strvector_push_back(igraph_strvector_t *sv, const char *value);

Arguments:

`sv`: | 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.

### 8.9. `igraph_strvector_push_back_len` — Adds a string of the given length to the back of a string vector.

    igraph_error_t igraph_strvector_push_back_len(
            igraph_strvector_t *sv,
            const char *value, size_t len);

Arguments:

`sv`: | The string vector.
`value`: | The start of the string to add. At most `len` characters will be copied.
`len`: | The length of the string.

Returns:

`` | Error code.

Time complexity: O(n+l), n is the total number of strings, l is the length of the new string.

### 8.10. `igraph_strvector_swap_elements` — Swap two elements in a string vector.

    void igraph_strvector_swap_elements(igraph_strvector_t *sv, igraph_int_t i, igraph_int_t j);

Note that currently no range checking is performed.

Arguments:

`sv`: | The string vector.
`i`: | Index of the first element.
`j`: | Index of the second element (may be the same as the first one).

Time complexity: O(1).

### 8.11. `igraph_strvector_remove` — Removes a single element from a string vector.

    void igraph_strvector_remove(igraph_strvector_t *sv, igraph_int_t elem);

The string will be one shorter.

Arguments:

`sv`: | The string vector.
`elem`: | The index of the element to remove.

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

### 8.12. `igraph_strvector_remove_section` — Removes a section from a string vector.

    void igraph_strvector_remove_section(
            igraph_strvector_t *sv, igraph_int_t from, igraph_int_t to);

This function removes the range `[from, to)` from the string vector.

Arguments:

`sv`: | The string vector.
`from`: | The position of the first element to remove.
`to`: | The position of the first element not to remove.

### 8.13. `igraph_strvector_append` — Concatenates two string vectors.

    igraph_error_t igraph_strvector_append(igraph_strvector_t *to,
                                           const igraph_strvector_t *from);

Appends the contents of the `from` vector to the `to` vector. If the `from` vector is no longer needed after this operation, use `igraph_strvector_merge()` for better performance.

Arguments:

`to`: | The first string vector, the result is stored here.
`from`: | The second string vector, it is kept unchanged.

Returns:

`` | Error code.

See also:

`` | `igraph_strvector_merge()`

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.

### 8.14. `igraph_strvector_merge` — Moves the contents of a string vector to the end of another.

    igraph_error_t igraph_strvector_merge(igraph_strvector_t *to, igraph_strvector_t *from);

Transfers the contents of the `from` vector to the end of `to`, clearing `from` in the process. If this operation fails, both vectors are left intact. This function does not copy or reallocate individual strings, therefore it performs better than `igraph_strvector_append()`.

Arguments:

`to`: | The target vector. The contents of `from` will be appended to it.
`from`: | The source vector. It will be cleared.

Returns:

`` | Error code.

See also:

`` | `igraph_strvector_append()`

Time complexity: O(l2) if `to` has sufficient capacity, O(2*l1+l2) otherwise, where l1 and l2 are the lengths of `to` and \from respectively.

### 8.15. `igraph_strvector_swap` — Swaps all elements of two string vectors.

    void igraph_strvector_swap(igraph_strvector_t *v1, igraph_strvector_t *v2);

Arguments:

`v1`: | The first string vector.
`v2`: | The second string vector.

Time complexity: O(1).

### 8.16. `igraph_strvector_update` — Updates a string vector from another one.

    igraph_error_t igraph_strvector_update(
        igraph_strvector_t *to, const igraph_strvector_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 string vector to update.
`from`: | The string vector to update from.

Returns:

`` | Error code.

### 8.17. `igraph_strvector_clear` — Removes all elements from a string vector.

    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.

### 8.18. `igraph_strvector_resize` — Resizes a string vector.

    igraph_error_t igraph_strvector_resize(igraph_strvector_t *sv, igraph_int_t newsize);

If the new size is bigger then empty strings are added, if it is smaller then the unneeded elements are removed.

Arguments:

`sv`: | 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.

### 8.19. `igraph_strvector_reserve` — Reserves memory for a string vector.

    igraph_error_t igraph_strvector_reserve(igraph_strvector_t *sv, igraph_int_t capacity);

igraph string 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 string vector. Let us see a small example to clarify things: if you reserve space for 100 strings and the size of your vector was (and still is) 60, then you can surely add additional 40 strings to your vector before it will be copied.

Arguments:

`sv`: | The string vector object.
`capacity`: | The new allocated size of the string 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.

### 8.20. `igraph_strvector_resize_min` — Deallocates the unused memory of a string vector.

    void igraph_strvector_resize_min(igraph_strvector_t *sv);

This function attempts to deallocate the unused reserved storage of a string vector. If it succeeds, `igraph_strvector_size()` and `igraph_strvector_capacity()` will be the same. The data in the string vector is always preserved, even if deallocation is not successful.

Arguments:

`sv`: | The string vector.

Time complexity: Operating system dependent, at most O(n).

### 8.21. `igraph_strvector_size` — Returns the size of a string vector.

    igraph_int_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).

### 8.22. `igraph_strvector_capacity` — Returns the capacity of a string vector.

    igraph_int_t igraph_strvector_capacity(const igraph_strvector_t *sv);

Arguments:

`sv`: | The string vector.

Returns:

`` | The capacity of the string vector.

Time complexity: O(1).

## 9. Lists of vectors, matrices and graphs

### 9.1. About igraph_vector_list_t objects

The igraph_vector_list_t data type is essentially a list of igraph_vector_t objects with automatic memory management. It is something similar to (but much simpler than) the vector template in the C++ standard library where the elements are vectors themselves.

There are multiple variants of igraph_vector_list_t; the basic variant stores vectors of doubles (i.e. each item is an `igraph_vector_t`), but there is also igraph_vector_int_list_t for integers (where each item is an igraph_vector_int_t), igraph_matrix_list_t for matrices of doubles and so on. The following list summarizes the variants that are currently available in the library:

- igraph_vector_list_t for lists of vectors of floating-point numbers (igraph_vector_t)

- igraph_vector_int_list_t for lists of integer vectors (igraph_vector_int_t)

- igraph_matrix_list_t for lists of matrices of floating-point numbers (igraph_matrix_t)

- igraph_graph_list_t for lists of graphs (igraph_t)

Lists of vectors are used in igraph in many cases, e.g., when returning lists of paths, cliques or vertex sets. Functions that expect or return a list of numeric vectors typically use igraph_vector_list_t or igraph_vector_int_list_t to achieve this. Lists of integer vectors are used when the vectors in the list are supposed to hold vertex or edge identifiers, while lists of floating-point vectors are used when the vectors are expected to hold fractional numbers or infinities.

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

Almost all of the functions described below for igraph_vector_list_t also exist for all the other vector list variants. These variants are not documented separately; you can simply replace `vector_list` with, say, `vector_int_list` if you need a function for another variant. For instance, to initialize a list of integer vectors, you need to use `igraph_vector_int_list_init`() and not `igraph_vector_list_init()`.

Before diving into a detailed description of the functions related to lists of vectors, we must also talk about the ownership rules of these objects. The most important rule is that the vectors in the list are owned by the list itself, meaning that the user is not responsible for allocating memory for the vectors or for freeing the memory associated to the vectors. It is the responsibility of the list to allocate and initialize the vectors when new items are created in the list, and it is also the responsibility of the list to destroy the items when they are removed from the list without passing on their ownership to the user. As a consequence, the list may not contain "uninitialized" or "null" items; each item is initialized when it comes to existence. If you create a list containing one million vectors, you are not only allocating memory for one million `igraph_vector_t` object but you are also initializing one million vectors. Also, if you have a list containing one million vectors and you clear the list by calling `igraph_vector_list_clear()`, the list will implicitly destroy these lists, and any pointers that you may hold to the items become invalid at once.

Speaking about pointers, the typical way of working with vectors in a list is to obtain a pointer to one of the items via the `igraph_vector_list_get_ptr()` method and then passing this pointer onwards to functions that manipulate `igraph_vector_t` objects. However, note that the pointers are ephemeral in the sense that they may be invalidated any time when the list is modified because a modification may involve the re-allocation of the internal storage of the list if more space is needed, and the pointers that you obtained will not follow the reallocation. This limitation does not appear often in real-world usage of `igraph_vector_list_t` and in general, the advantages of the automatic memory management outweigh this limitation.

### 9.2. Constructors and destructors

igraph_vector_list_t objects have to be initialized before using them, this is analogous to calling a constructor on them. `igraph_vector_list_init()` is the basic constructor; it creates a list of the given length and also initializes each vector in the newly created list to zero length.

If an igraph_vector_list_t object is not needed any more, it should be destroyed to free its allocated memory by calling the igraph_vector_list_t destructor, `igraph_vector_list_destroy()`. Calling the destructor also destroys all the vectors inside the vector list due to the ownership rules. If you want to keep a few of the vectors in the vector list, you need to copy them with `igraph_vector_init_copy()` or `igraph_vector_update()`, or you need to remove them from the list and take ownership by calling `igraph_vector_list_pop_back()`, `igraph_vector_list_remove()` or `igraph_vector_list_remove_fast()` .

#### 9.2.1. `igraph_vector_list_init` — Initializes a list of vectors (constructor).

    igraph_error_t igraph_vector_list_init(igraph_vector_list_t *v, igraph_int_t size);

This function constructs a list of vectors of the given size, and initializes each vector in the newly created list to become an empty vector.

Vector objects initialized by this function are owned by the list, and they will be destroyed automatically when the list is destroyed with `igraph_vector_list_destroy()`.

Arguments:

`v`: | Pointer to a not yet initialized list of vectors.
`size`: | The size of the list.

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 and initialize the corresponding vectors; n is the number of elements.

#### 9.2.2. `igraph_vector_list_init_copy` — Initializes a list of vectors from another list of vectors (constructor).

    igraph_error_t igraph_vector_list_init_copy(igraph_vector_list_t* to, const igraph_vector_list_t* from);

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

Arguments:

`to`: | Pointer to a not yet initialized list of vectors.
`from`: | The original list of vectors to copy.

Returns:

`` | Error code: `IGRAPH_ENOMEM` if there is not enough memory.

Time complexity: operating system dependent, usually O(nm), n is the size of the list, m is the size of each element in the list, assuming that copying a single item takes O(m) time.

#### 9.2.3. `igraph_vector_list_destroy` — Destroys a list of vectors object.

    void igraph_vector_list_destroy(igraph_vector_list_t *v);

All lists initialized by `igraph_vector_list_init()` should be properly destroyed by this function. A destroyed list of vectors needs to be reinitialized by `igraph_vector_list_init()` if you want to use it again.

Vectors that are in the list when it is destroyed are also destroyed implicitly.

Arguments:

`v`: | Pointer to the (previously initialized) list object to destroy.

Time complexity: operating system dependent.

### 9.3. Accessing elements

Elements of a vector list may be accessed with the `igraph_vector_list_get_ptr()` function. The function returns a pointer to the vector with a given index inside the list, and you may then pass this pointer onwards to other functions that can query or manipulate vectors. The pointer itself is guaranteed to stay valid as long as the list itself is not modified; however, any modification to the list will invalidate the pointer, even modifications that are seemingly unrelated to the vector that the pointer points to (such as adding a new vector at the end of the list). This is because the list data structure may be forced to re-allocate its internal storage if a new element does not fit into the already allocated space, and there are no guarantees that the re-allocated block remains at the same memory location (typically it gets moved elsewhere).

Note that the standard `VECTOR` macro that works for ordinary vectors does not work for lists of vectors to access the i-th element (but of course you can use it to index into an existing vector that you retrieved from the vector list with `igraph_vector_list_get_ptr()` ). This is because the macro notation would allow one to overwrite the vector in the list with another one without the list knowing about it, so the list would not be able to destroy the vector that was overwritten by a new one.

`igraph_vector_list_tail_ptr()` returns a pointer to the last vector in the list, or `NULL` if the list is empty. There is no `igraph_vector_list_head_ptr()`, however, as it is easy to write `igraph_vector_list_get_ptr(v, 0)` instead.

#### 9.3.1. `igraph_vector_list_get_ptr` — The address of a vector in the vector list.

    igraph_vector_t *igraph_vector_list_get_ptr(const igraph_vector_list_t *v, igraph_int_t pos);

Arguments:

`v`: | The list object.
`pos`: | The position of the vector in the list. The position of the first vector is zero.

Returns:

`` | A pointer to the vector. It remains valid as long as the underlying list of vectors is not modified.

Time complexity: O(1).

#### 9.3.2. `igraph_vector_list_tail_ptr` — The address of the last vector in the vector list.

    igraph_vector_t *igraph_vector_list_tail_ptr(const igraph_vector_list_t *v);

Arguments:

`v`: | The list object.

Returns:

`` | A pointer to the last vector in the list, or `NULL` if the list is empty.

Time complexity: O(1).

#### 9.3.3. `igraph_vector_list_set` — Sets the vector at the given index in the list.

    void igraph_vector_list_set(igraph_vector_list_t *v, igraph_int_t pos, igraph_vector_t *e);

This function destroys the vector that is already at the given index `pos` in the list, and replaces it with the vector pointed to by `e`. The ownership of the vector pointed to by `e` is taken by the list so the user is not responsible for destroying `e` any more; it will be destroyed when the list itself is destroyed or if `e` gets removed from the list without passing on the ownership to somewhere else.

Arguments:

`v`: | The list object.
`pos`: | The index to modify in the list.
`e`: | The vector to set in the list.

Time complexity: O(1).

#### 9.3.4. `igraph_vector_list_replace` — Replaces the vector at the given index in the list with another one.

    void igraph_vector_list_replace(igraph_vector_list_t *v, igraph_int_t pos, igraph_vector_t *e);

This function replaces the vector that is already at the given index `pos` in the list with the vector pointed to by `e`. The ownership of the vector pointed to by `e` is taken by the list so the user is not responsible for destroying `e` any more. At the same time, the ownership of the vector that was in the list at position `pos` will be transferred to the caller and `e` will be updated to point to it, so the caller becomes responsible for destroying it when it does not need the vector any more.

Arguments:

`v`: | The list object.
`pos`: | The index to modify in the list.
`e`: | The vector to swap with the one already in the list.

Time complexity: O(1).

### 9.4. Vector properties

#### 9.4.1. `igraph_vector_list_empty` — Decides whether the size of the list is zero.

    igraph_bool_t igraph_vector_list_empty(const igraph_vector_list_t *v);

Arguments:

`v`: | The list object.

Returns:

`` | True if the size of the list is zero and false otherwise.

Time complexity: O(1).

#### 9.4.2. `igraph_vector_list_size` — The size of the vector list.

    igraph_int_t igraph_vector_list_size(const igraph_vector_list_t *v);

Returns the number of vectors stored in the list.

Arguments:

`v`: | The list object

Returns:

`` | The size of the list.

Time complexity: O(1).

#### 9.4.3. `igraph_vector_list_capacity` — Returns the allocated capacity of the list.

    igraph_int_t igraph_vector_list_capacity(const igraph_vector_list_t *v);

Note that this might be different from the size of the list (as queried by `igraph_vector_list_size()`), and specifies how many vectors the list can hold, without reallocation.

Arguments:

`v`: | Pointer to the (previously initialized) list object to query.

Returns:

`` | The allocated capacity.

See also:

`` | `igraph_vector_list_size()`.

Time complexity: O(1).

### 9.5. Resizing operations

#### 9.5.1. `igraph_vector_list_clear` — Removes all elements from a list of vectors.

    void igraph_vector_list_clear(igraph_vector_list_t *v);

This function sets the size of the list to zero, and it also destroys all the vectors that were placed in the list before clearing it.

Arguments:

`v`: | The list object.

Time complexity: O(n), n is the number of items being deleted.

#### 9.5.2. `igraph_vector_list_reserve` — Reserves memory for a list.

    igraph_error_t igraph_vector_list_reserve(igraph_vector_list_t *v, igraph_int_t capacity);

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

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

Arguments:

`v`: | The list object.
`capacity`: | The new allocated size of the list.

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 list.

#### 9.5.3. `igraph_vector_list_resize` — Resizes the list of vectors.

    igraph_error_t igraph_vector_list_resize(igraph_vector_list_t *v, igraph_int_t new_size);

Note that this function does not free any memory, just sets the size of the list to the given one. It can on the other hand allocate more memory if the new size is larger than the previous one.

When the new size is larger than the current size, the newly added vectors in the list are initialized to empty vectors. When the new size is smaller than the current size, the vectors that were removed from the end of the list are destroyed automatically.

Arguments:

`v`: | The list object
`new_size`: | The new size of the list.

Returns:

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

See also:

`` | `igraph_vector_list_reserve()` for allocating memory for future extensions of a list.

Time complexity: O(m) if the new size is smaller (m is the number of items that were removed from the list), operating system dependent if the new size is larger. In the latter case it is usually around O(n), where n is the new size of the vector.

#### 9.5.4. `igraph_vector_list_push_back` — Appends an existing vector to the list, transferring ownership.

    igraph_error_t igraph_vector_list_push_back(igraph_vector_list_t *v, igraph_vector_t *e);

This function resizes the list to be one element longer, and sets the very last element in the list to the specified vector `e` . The list takes ownership of the vector so the user is not responsible for freeing `e` any more; the vector will be destroyed when the list itself is destroyed or if `e` gets removed from the list without passing on the ownership to somewhere else.

Arguments:

`v`: | The list object.
`e`: | Pointer to the vector to append to the list.

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_list_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).

#### 9.5.5. `igraph_vector_list_push_back_copy` — Appends the copy of a vector to the list.

    igraph_error_t igraph_vector_list_push_back_copy(igraph_vector_list_t *v, const igraph_vector_t *e);

This function resizes the list to be one element longer, and copies the specified vector given as an argument to the last element. The newly added element is owned by the list, but the ownership of the original vector is retained at the caller.

Arguments:

`v`: | The list object.
`e`: | Pointer to the vector to copy to the end of the list.

Returns:

`` | Error code: `IGRAPH_ENOMEM`: not enough memory.

Time complexity: same as `igraph_vector_list_push_back()` plus the time needed to copy the vector (which is O(n) for n elements in the vector).

#### 9.5.6. `igraph_vector_list_push_back_new` — Appends a new vector to the list.

    igraph_error_t igraph_vector_list_push_back_new(igraph_vector_list_t *v, igraph_vector_t** e);

This function resizes the list to be one element longer. The newly added element will be an empty vector that is owned by the list. A pointer to the newly added element is returned in the last argument if it is not `NULL` .

Arguments:

`v`: | The list object.
`result`: | Pointer to a vector pointer; this will be updated to point to the newly added vector. May be `NULL` if you do not need a pointer to the newly added vector.

Returns:

`` | Error code: `IGRAPH_ENOMEM`: not enough memory.

Time complexity: same as `igraph_vector_list_push_back()`.

#### 9.5.7. `igraph_vector_list_pop_back` — Removes the last item from the vector list and transfer ownership to the caller.

    igraph_vector_t igraph_vector_list_pop_back(igraph_vector_list_t *v);

This function removes the last vector from the list. The vector that was removed from the list is returned and its ownership is passed back to the caller; in other words, the caller becomes responsible for destroying the vector when it is not needed any more.

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

Arguments:

`v`: | The list object.
`result`: | Pointer to an `igraph_vector_t` object; it will be updated to the item that was removed from the list. Ownership of this vector is passed on to the caller.

Time complexity: O(1).

#### 9.5.8. `igraph_vector_list_insert` — Inserts an existing vector into the list, transferring ownership.

    igraph_error_t igraph_vector_list_insert(igraph_vector_list_t *v, igraph_int_t pos, igraph_vector_t *e);

This function inserts `e` into the list at the given index, moving other items towards the end of the list as needed. The list takes ownership of the vector so the user is not responsible for freeing `e` any more; the vector will be destroyed when the list itself is destroyed or if `e` gets removed from the list without passing on the ownership to somewhere else.

Arguments:

`v`: | The list object.
`pos`: | The position where the new element is to be inserted.
`e`: | Pointer to the vector to insert into the list.

Returns:

`` | Error code: `IGRAPH_ENOMEM`: not enough memory.

Time complexity: O(n).

#### 9.5.9. `igraph_vector_list_insert_copy` — Inserts the copy of a vector to the list.

    igraph_error_t igraph_vector_list_insert_copy(igraph_vector_list_t *v, igraph_int_t pos, const igraph_vector_t *e);

This function inserts a copy of `e` into the list at the given index, moving other items towards the end of the list as needed. The newly added element is owned by the list, but the ownership of the original vector is retained at the caller.

Arguments:

`v`: | The list object.
`pos`: | The position where the new element is to be inserted.
`e`: | Pointer to the vector to copy to the end of the list.

Returns:

`` | Error code: `IGRAPH_ENOMEM`: not enough memory.

Time complexity: same as `igraph_vector_list_insert()` plus the time needed to copy the vector (which is O(n) for n elements in the vector).

#### 9.5.10. `igraph_vector_list_insert_new` — Inserts a new vector into the list.

    igraph_error_t igraph_vector_list_insert_new(igraph_vector_list_t *v, igraph_int_t pos, igraph_vector_t** e);

This function inserts a newly created empty vector into the list at the given index, moving other items towards the end of the list as needed. The newly added vector is owned by the list. A pointer to the new element is returned in the last argument if it is not `NULL` .

Arguments:

`v`: | The list object.
`pos`: | The position where the new element is to be inserted.
`result`: | Pointer to a vector pointer; this will be updated to point to the newly added vector. May be `NULL` if you do not need a pointer to the newly added vector.

Returns:

`` | Error code: `IGRAPH_ENOMEM`: not enough memory.

Time complexity: same as `igraph_vector_list_push_back()`.

#### 9.5.11. `igraph_vector_list_remove` — Removes the item at the given index from the vector list and transfer ownership to the caller.

    igraph_error_t igraph_vector_list_remove(igraph_vector_list_t *v, igraph_int_t index, igraph_vector_t *result);

This function removes the vector at the given index from the list, and moves all subsequent items in the list by one slot to the left to fill the gap. The vector that was removed from the list is returned in `e` and its ownership is passed back to the caller; in other words, the caller becomes responsible for destroying the vector when it is not needed any more.

Arguments:

`v`: | The list object.
`index`: | Index of the item to be removed.
`result`: | Pointer to an `igraph_vector_t` object; it will be updated to the item that was removed from the list. Ownership of this vector is passed on to the caller. It is an error to supply a null pointer here.

See also:

`` | `igraph_vector_list_discard()` if you are not interested in the item that was removed, `igraph_vector_list_remove_fast()` if you do not care about the order of the items in the list.

Time complexity: O(n), where n is the number of items in the list.

#### 9.5.12. `igraph_vector_list_remove_fast` — Removes the item at the given index in the vector list, move the last item to its place and transfer ownership to the caller.

    igraph_error_t igraph_vector_list_remove_fast(igraph_vector_list_t *v, igraph_int_t index, igraph_vector_t *result);

This function removes the vector at the given index from the list, moves the last item in the list to `index` to fill the gap, and then transfers ownership of the removed vector back to the caller; in other words, the caller becomes responsible for destroying the vector when it is not needed any more.

Arguments:

`v`: | The list object.
`index`: | Index of the item to be removed.
`result`: | Pointer to an `igraph_vector_t` object; it will be updated to the item that was removed from the list. Ownership of this vector is passed on to the caller. It is an error to supply a null pointer here.

See also:

`` | `igraph_vector_list_remove()` if you want to preserve the order of the items in the list, `igraph_vector_list_discard_fast()` if you are not interested in the item that was removed.

Time complexity: O(1).

#### 9.5.13. `igraph_vector_list_discard` — Discards the item at the given index in the vector list.

    void igraph_vector_list_discard(igraph_vector_list_t *v, igraph_int_t index);

This function removes the vector at the given index from the list, and moves all subsequent items in the list by one slot to the left to fill the gap. The vector that was removed from the list is destroyed automatically.

Arguments:

`v`: | The list object.
`index`: | Index of the item to be discarded and destroyed.

See also:

`` | `igraph_vector_list_discard_fast()` if you do not care about the order of the items in the list, `igraph_vector_list_remove()` if you want to gain ownership of the item that was removed instead of destroying it.

Time complexity: O(n), where n is the number of items in the list.

#### 9.5.14. `igraph_vector_list_discard_back` — Discards the last item in the vector list.

    void igraph_vector_list_discard_back(igraph_vector_list_t *v);

This function removes the last vector from the list and destroys it.

Arguments:

`v`: | The list object.

Time complexity: O(1).

#### 9.5.15. `igraph_vector_list_discard_fast` — Discards the item at the given index in the vector list and moves the last item to its place.

    void igraph_vector_list_discard_fast(igraph_vector_list_t *v, igraph_int_t index);

This function removes the vector at the given index from the list, and moves the last item in the list to `index` to fill the gap. The vector that was removed from the list is destroyed automatically.

Arguments:

`v`: | The list object.
`index`: | Index of the item to be discarded and destroyed.

See also:

`` | `igraph_vector_list_discard()` if you want to preserve the order of the items in the list, `igraph_vector_list_remove_fast()` if you want to gain ownership of the item that was removed instead of destroying it.

Time complexity: O(1).

### 9.6. Sorting and reordering

#### 9.6.1. `igraph_vector_list_permute` — Permutes the elements of a list in place according to an index vector.

    igraph_error_t igraph_vector_list_permute(igraph_vector_list_t *v, const igraph_vector_int_t* index);

This function takes a list `v` and a corresponding index vector `index`, and permutes the elements of `v` such that `v`[index[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 list minus one (inclusive), and each such element must appear only once. The function does not attempt to validate the index vector. Memory may be leaked if the index vector does not satisfy these conditions.

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

Arguments:

`v`: | the list to permute
`index`: | the index vector

Time complexity: O(n), the number of items in the list.

#### 9.6.2. `igraph_vector_list_sort` — Sorts the elements of the list into ascending order.

    void igraph_vector_list_sort(igraph_vector_list_t *v, int (*cmp)(const igraph_vector_t*, const igraph_vector_t*));

Arguments:

`v`: | Pointer to an initialized list object.
`cmp`: | A comparison function that takes pointers to two vectors and returns zero if the two vectors are considered equal, any negative number if the first vector is smaller and any positive number if the second vector is smaller.

Returns:

`` | Error code.

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

#### 9.6.3. `igraph_vector_list_sort_ind` — Returns a permutation of indices that sorts the list.

    igraph_error_t igraph_vector_list_sort_ind(
        igraph_vector_list_t *v, igraph_vector_int_t *inds,
        int (*cmp)(const igraph_vector_t*, const igraph_vector_t*)
    );

Takes an unsorted list `v` as input and computes an array of indices `inds` such that v[ inds[i] ], with i increasing from 0, is an ordered array according to the comparison function `cmp`. The order of indices for identical elements is not defined.

Arguments:

`v`: | the list to be sorted
`inds`: | the output array of indices. This must be initialized, but will be resized
`cmp`: | A comparison function that takes pointers to two vectors and returns zero if the two vectors are considered equal, any negative number if the first vector is smaller and any positive number if the second vector is smaller.

Returns:

`` | Error code.

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

#### 9.6.4. `igraph_vector_list_swap` — Swaps all elements of two vector lists.

    void igraph_vector_list_swap(igraph_vector_list_t *v1, igraph_vector_list_t *v2);

Arguments:

`v1`: | The first list.
`v2`: | The second list.

Returns:

`` | Error code.

Time complexity: O(1).

#### 9.6.5. `igraph_vector_list_swap_elements` — Swap two elements in a vector list.

    void igraph_vector_list_swap_elements(igraph_vector_list_t *v1, igraph_int_t i, igraph_int_t j);

Note that currently no range checking is performed.

Arguments:

`v`: | The input list.
`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).

## 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.12. File `examples/simple/adjlist.c`

    #include <igraph.h>

    int main(void) {
        igraph_t g, g2;
        igraph_adjlist_t adjlist;
        igraph_bool_t iso;

        /* Initialize the library. */
        igraph_setup();

        /* 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_kary_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 a given graph.

    igraph_error_t igraph_adjlist_init(const igraph_t *graph, igraph_adjlist_t *al,
                            igraph_neimode_t mode, igraph_loops_t loops,
                            igraph_bool_t multiple);

Creates a list of vectors containing the neighbors of all vertices in a graph. The adjacency list is independent of the graph after creation, e.g. the graph can be destroyed and modified, the adjacency list contains the state of the graph at the time of its initialization.

This function returns each neighbor list in sorted order, just like `igraph_neighbors()`. However, adjacency lists "in general" are not guaranteed to be sorted, and we reserve the right to change the ordering of vertices in the result in the future without considering this a breaking change. If you need to ensure that the adjacency lists are sorted, you can use `igraph_adjlist_sort()` to sort all the adjacency lists, or call `igraph_vector_int_sort()` on the individual adjacency vectors after the initialization.

As of igraph 0.10, there is a small performance cost to setting `loops` to a different value than `IGRAPH_LOOPS_TWICE` or setting `multiple` to a different value from `IGRAPH_MULTIPLE`.

Arguments:

`graph`: | The input graph.
`al`: | Pointer to an uninitialized igraph_adjlist_t object.
`mode`: | Constant specifying whether to include only outgoing (`IGRAPH_OUT`), only incoming (`IGRAPH_IN`), or both (`IGRAPH_ALL`) types of neighbors in the adjacency list. It is ignored for undirected graphs.
`loops`: | Specifies how to treat loop edges. `IGRAPH_NO_LOOPS` removes loop edges from the adjacency list. `IGRAPH_LOOPS_ONCE` makes each loop edge appear only once in the adjacency list of the corresponding vertex. `IGRAPH_LOOPS_TWICE` makes loop edges appear twice in the adjacency list of the corresponding vertex, but only if the graph is undirected or `mode` is set to `IGRAPH_ALL`.
`multiple`: | Specifies how to treat multiple (parallel) edges. `IGRAPH_NO_MULTIPLE` collapses parallel edges into a single one; `IGRAPH_MULTIPLE` keeps the multiplicities of parallel edges so the same vertex will appear as many times in the adjacency list of another vertex as the number of parallel edges going between the two vertices.

Returns:

`` | Error code.

See also:

`` | `igraph_neighbors()` for getting the neighbor lists of individual vertices.

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_int_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:

`al`: | Pointer to an uninitialized igraph_adjlist_t object.
`no_of_nodes`: | The number of vertices

Returns:

`` | Error code.

Time complexity: O(n), 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_loops_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.

This function returns each neighbor list in sorted order.

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`:

Specifies how to treat loop edges. `IGRAPH_NO_LOOPS` will not include loops edges in the returned adjacency list. `IGRAPH_LOOPS_ONCE` will include vertex `i` in the adjacency list of vetex `i` once if the original graph did not have a loop edge incident on vertex `i`, while `IGRAPH_LOOPS_TWICE` will include vertex `i` twice if `mode` is set to `IGRAPH_ALL` (otherwise it is treated the same way as `IGRAPH_LOOPS_ONCE` ).

Returns:

`` | Error code.

See also:

`` | `igraph_adjlist_init()`, `igraph_complementer()`

Time complexity: O(|V|^2+|E|), quadratic in the number of vertices.

#### 10.1.4. `igraph_adjlist_init_from_inclist` — 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.5. `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: O(n), where n is the size of the adjacency list.

#### 10.1.6. `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.7. `igraph_adjlist_size` — Returns the number of vertices in an adjacency list.

    igraph_int_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.8. `igraph_adjlist_clear` — Removes all edges from an adjacency list.

    void igraph_adjlist_clear(igraph_adjlist_t *al);

The size of the adjacency list stays unchanged, but all adjacent vertices will be removed.

Arguments:

`al`: | The adjacency list.

Time complexity: O(n), where n is the size of the adjacency list.

#### 10.1.9. `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. Note that `igraph_adjlist_init()` already produces sorted neighbor lists. This function is useful when the adjacency list is produced in a different manner, or is modified in a way that does not preserve the sorted order.

Arguments:

`al`: | The adjacency list.

Time complexity: O(m log m), m is the total number of neighbors stored in the adjacency list.

#### 10.1.10. `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.

When the adjacency list is created with `igraph_adjlist_init()`, use the `loops` and `multiple` parameters of that function instead.

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`).

As of igraph 0.10, there is a small performance cost to setting `loops` to a different value than `IGRAPH_LOOPS_TWICE`.

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:

`il`: | The incidence list to destroy.

Time complexity: O(n), where n is the size of the incidence list.

#### 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_int_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);

The size of the incidence list stays unchanged, but all incident edges will be removed.

Arguments:

`il`: | The incidence list.

Time complexity: O(n), where n is the size of the incidence list.

### 10.3. Lazy adjacency list for vertices

#### 10.3.1. `igraph_lazy_adjlist_init` — Initializes 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_bool_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. Neighbor lists will be returned in sorted order.

As of igraph 0.10, there is a small performance cost to setting `loops` to a different value than `IGRAPH_LOOPS_TWICE` or setting `multiple` to a different value from `IGRAPH_MULTIPLE`.

Arguments:

`graph`: | The input graph.
`al`: | Pointer to an uninitialized adjacency list object.
`mode`: | Constant specifying whether to include only outgoing (`IGRAPH_OUT`), only incoming (`IGRAPH_IN`), or both (`IGRAPH_ALL`) types of neighbors in the adjacency list. It is ignored for undirected graphs.
`loops`: | Specifies how to treat loop edges. `IGRAPH_NO_LOOPS` removes loop edges from the adjacency list. `IGRAPH_LOOPS_ONCE` makes each loop edge appear only once in the adjacency list of the corresponding vertex. `IGRAPH_LOOPS_TWICE` makes loop edges appear twice in the adjacency list of the corresponding vertex, but only if the graph is undirected or `mode` is set to `IGRAPH_ALL`.
`multiple`: | Specifies how to treat multiple (parallel) edges. `IGRAPH_NO_MULTIPLE` collapses parallel edges into a single one; `IGRAPH_MULTIPLE` keeps the multiplicities of parallel edges so the same vertex will appear as many times in the adjacency list of another vertex as the number of parallel edges going between the two vertices.

Returns:

`` | Error code.

See also:

`` | `igraph_neighbors()` for getting the neighbor lists of individual vertices.

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, or `NULL` upon error. Errors can only occur the first time this function is called for a given vertex. It is safe to modify this vector, modification does not affect the original graph.

See also:

`` | `igraph_lazy_adjlist_has()` to check if this function has already been called for a vertex.

Time complexity: O(d), the number of neighbor vertices for the first time, O(1) for subsequent calls.

#### 10.3.4. `igraph_lazy_adjlist_has` — Are adjacenct vertices already stored in a lazy adjacency list?

    #define igraph_lazy_adjlist_has(al,no)

Arguments:

`al`: | The lazy adjacency list.
`no`: | The vertex ID to query.

Returns:

`` | True if the adjacent vertices of this vertex are already computed and stored, false otherwise.

Time complexity: O(1).

#### 10.3.5. `igraph_lazy_adjlist_size` — Returns the number of vertices in a lazy adjacency list.

    igraph_int_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.6. `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.

As of igraph 0.10, there is a small performance cost to setting `loops` to a different value than `IGRAPH_LOOPS_TWICE`.

Arguments:

`graph`: | The input graph.
`il`: | 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:

`il`: | 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(il,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:

`il`: | The lazy incidence list object.
`no`: | The vertex ID to query.

Returns:

`` | Pointer to a vector, or `NULL` upon error. Errors can only occur the first time this function is called for a given vertex. It is safe to modify this vector, modification does not affect the original graph.

See also:

`` | `igraph_lazy_inclist_has()` to check if this function has already been called for a vertex.

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_has` — Are incident edges already stored in a lazy inclist?

    #define igraph_lazy_inclist_has(il,no)

Arguments:

`il`: | The lazy incidence list.
`no`: | The vertex ID to query.

Returns:

`` | True if the incident edges of this vertex are already computed and stored, false otherwise.

Time complexity: O(1).

#### 10.4.5. `igraph_lazy_inclist_size` — Returns the number of vertices in a lazy incidence list.

    igraph_int_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.6. `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_int_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. It must be at least one.

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_int_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_int_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_int_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. Must be in the interval `[0, sum)`, where `sum` is the sum of all elements (leaves) in the tree.

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_int_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.

### 11.8. `igraph_psumtree_reset` — Resets all the values in the tree to zero.

    void igraph_psumtree_reset(igraph_psumtree_t *t);

Arguments:

`t`: | The tree to reset.

## 12. Bitsets

### 12.1. About igraph_bitset_t objects

The igraph_bitset_t data type is a simple and efficient interface to arrays containing boolean values. It is similar to the bitset template in the C++ standard library, although the main difference being the C++ version's size is initialized at compile time.

The igraph_bitset_t type and use O(n/w) space to store n elements, where w is the bit width of igraph_int_t, the integer type used throughout the library (either 32 or 64). Sometimes they use more, this is because bitsets can shrink, but even if they shrink, the current implementation does not free a single bit of memory.

The elements in an igraph_bitset_t object and its variants are indexed from zero, we follow the usual C convention here. Bitsets are indexed from right to left, meaning index 0 is the least significant bit and index `n - 1` is the most significant bit.

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

Note that while the interface of bitset functions is similar to igraph's vector functions, there is one major difference: bitset functions such as `igraph_bitset_and()` do not verify that that sizes of input parameters are compatible, and do not automatically resize the output parameter. Doing so is the responsibility of the user.

### 12.2. Constructors and destructors

igraph_bitset_t objects have to be initialized before using them, this is analogous to calling a constructor on them. There are two igraph_bitset_t constructors, for your convenience. `igraph_bitset_init()` is the basic constructor, it creates a bitset of the given length, filled with zeros. `igraph_bitset_init_copy()` creates a new identical copy of an already existing and initialized bitset.

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

#### 12.2.1. `igraph_bitset_init` — Initializes a bitset object (constructor).

    igraph_error_t igraph_bitset_init(igraph_bitset_t *bitset, igraph_int_t size);

Every bitset 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 bitset of the given size and initializes each entry to 0.

Every bitset 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_bitset_destroy()` function is responsible for this.

Arguments:

`bitset`: | Pointer to a not yet initialized bitset object.
`size`: | The size of the bitset.

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/w) elements, n is the number of elements. w is the word size of the machine (32 or 64).

#### 12.2.2. `igraph_bitset_init_copy` — Initializes a bitset from another bitset object (constructor).

    igraph_error_t igraph_bitset_init_copy(igraph_bitset_t *dest, const igraph_bitset_t *src);

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

Arguments:

`dest`: | Pointer to a not yet initialized bitset object.
`src`: | The original bitset object to copy.

Returns:

`` | Error code: `IGRAPH_ENOMEM` if there is not enough memory.

Time complexity: operating system dependent, usually O(n/w), n is the size of the bitset, w is the word size of the machine (32 or 64).

#### 12.2.3. `igraph_bitset_destroy` — Destroys a bitset object.

    void igraph_bitset_destroy(igraph_bitset_t *bitset);

All bitsets initialized by `igraph_bitset_init()` should be properly destroyed by this function. A destroyed bitset needs to be reinitialized by `igraph_bitset_init()` or another constructor.

Arguments:

`bitset`: | Pointer to the (previously initialized) bitset object to destroy.

Time complexity: operating system dependent.

### 12.3. Accessing elements

The simplest way to access an element of a bitset is to use the `IGRAPH_BIT_TEST()`, `IGRAPH_BIT_SET()` and `IGRAPH_BIT_CLEAR()` macros.

There are a few other macros which allow manual manipulation of bitsets. Those are `VECTOR()`, `IGRAPH_BIT_SLOT()`, `IGRAPH_BIT_MASK()` and `IGRAPH_BIT_NSLOTS()`.

#### 12.3.1. `IGRAPH_BIT_MASK` — Computes mask used to access a specific bit of an integer.

    #define IGRAPH_BIT_MASK(i)

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

Used in combination with `IGRAPH_BIT_SLOT()` to access an element of a bitset. Usage:

     IGRAPH_BIT_MASK(10)

to obtain an integer where only the 11th least significant bit is set. Note that passing negative values here results in undefined behaviour.

Arguments:

`b`: | The only bit index that should have its bit set.

Time complexity: O(1).

#### 12.3.2. `IGRAPH_BIT_SLOT` — Computes index used to access a specific slot of a bitset.

    #define IGRAPH_BIT_SLOT(i)

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

Used in combination with `IGRAPH_BIT_MASK` to access an element of a bitset. Usage:

     IGRAPH_BIT_SLOT(70)

will return 1 if using 64-bit words or 2 if using 32-bit words.

Arguments:

`i`: | The bit index whose slot should be determined.

Time complexity: O(1).

#### 12.3.3. `IGRAPH_BIT_SET` — Sets a specific bit in a bitset to 1 without altering other bits.

    #define IGRAPH_BIT_SET(bitset, i)

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

Usage:

     IGRAPH_BIT_SET(bitset, 3)

will set the fourth least significant bit in the bitset to 1.

Arguments:

`bitset`: | The bitset
`i`: | The bit index that should have its bit set to 1 after the operation.

Time complexity: O(1).

#### 12.3.4. `IGRAPH_BIT_CLEAR` — Sets a specific bit in a bitset to 0 without altering other bits.

    #define IGRAPH_BIT_CLEAR(bitset, i)

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

Usage:

     IGRAPH_BIT_CLEAR(bitset, 4)

will set the fifth least significant bit in the bitset to 0.

Arguments:

`bitset`: | The bitset
`i`: | The bit index that should have its bit set to 0 after the operation.

Time complexity: O(1).

#### 12.3.5. `IGRAPH_BIT_TEST` — Tests whether a bit is set in a bitset.

    #define IGRAPH_BIT_TEST(bitset, i)

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

Returns 0 if the bit at the specified bit index is not set, otherwise returns a non-zero value. Usage:

     IGRAPH_BIT_TEST(bitset, 7)

will test the eighth least significant bit in the bitset.

Arguments:

`bitset`: | The bitset
`i`: | The bit index that should have its bit tested.

Time complexity: O(1).

#### 12.3.6. `IGRAPH_BIT_NSLOTS` — Computes the number of slots required to store a specified number of bits.

    #define IGRAPH_BIT_NSLOTS(nbits)

### Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

Usage:

     IGRAPH_BIT_NSLOTS(70)

will return 2 if using 64-bit words and 3 if using 32-bit words.

     IGRAPH_BIT_NSLOTS(128)

will return 2 if using 64-bit words and 4 if using 32-bit words.

Arguments:

`nbits`: | The specified number of bits.

Time complexity: O(1).

### 12.4. Bitset operations

#### 12.4.1. `igraph_bitset_fill` — Fills a bitset with a constant value.

    void igraph_bitset_fill(igraph_bitset_t *bitset, igraph_bool_t value);

Sets all bits of a bitset to the same value.

Arguments:

`bitset`: | The bitset object to modify.
`value`: | The value to set for all bits.

See also:

`` | `igraph_bitset_null()`

Time complexity: O(n/w).

#### 12.4.2. `igraph_bitset_null` — Clears all bits in a bitset.

    void igraph_bitset_null(igraph_bitset_t *bitset);

Arguments:

`bitset`: | The bitset object to clear all bits in.

See also:

`` | `igraph_bitset_fill()`

Time complexity: O(n/w).

#### 12.4.3. `igraph_bitset_or` — Bitwise OR of two bitsets.

    void igraph_bitset_or(igraph_bitset_t *dest,
                          const igraph_bitset_t *src1, const igraph_bitset_t *src2);

Applies a bitwise or to the contents of two bitsets and stores it in an already initialized bitset. The destination bitset may be equal to one (or even both) of the sources. When working with bitsets, it is common that those created are of the same size fixed size. Therefore, this function does not check the sizes of the bitsets passed to it, the caller must do so if necessary.

Arguments:

`dest`: | The bitset object where the result is stored
`src1`: | A bitset. Must have have same size as `dest`.
`src2`: | A bitset. Must have have same size as `dest`.

Time complexity: O(n/w).

#### 12.4.4. `igraph_bitset_and` — Bitwise AND of two bitsets.

    void igraph_bitset_and(igraph_bitset_t *dest, const igraph_bitset_t *src1, const igraph_bitset_t *src2);

Applies a bitwise and to the contents of two bitsets and stores it in an already initialized bitset. The destination bitset may be equal to one (or even both) of the sources. When working with bitsets, it is common that those created are of the same size fixed size. Therefore, this function does not check the sizes of the bitsets passed to it, the caller must do so if necessary.

Arguments:

`dest`: | The bitset object where the result is stored
`src1`: | A bitset. Must have have same size as `dest`.
`src2`: | A bitset. Must have have same size as `dest`.

Time complexity: O(n/w).

#### 12.4.5. `igraph_bitset_xor` — Bitwise XOR of two bitsets.

    void igraph_bitset_xor(igraph_bitset_t *dest,
                           const igraph_bitset_t *src1, const igraph_bitset_t *src2);

Applies a bitwise xor to the contents of two bitsets and stores it in an already initialized bitset. The destination bitset may be equal to one (or even both) of the sources. When working with bitsets, it is common that those created are of the same size fixed size. Therefore, this function does not check the sizes of the bitsets passed to it, the caller must do so if necessary.

Arguments:

`dest`: | The bitset object where the result is stored
`src1`: | A bitset. Must have have same size as `dest`.
`src2`: | A bitset. Must have have same size as `dest`.

Time complexity: O(n/w).

#### 12.4.6. `igraph_bitset_not` — Bitwise negation of a bitset.

    void igraph_bitset_not(igraph_bitset_t *dest, const igraph_bitset_t *src);

Applies a bitwise not to the contents of a bitset and stores it in an already initialized bitset. The destination bitset may be equal to the source. When working with bitsets, it is common that those created are of the same size fixed size. Therefore, this function does not check the sizes of the bitsets passed to it, the caller must do so if necessary.

Arguments:

`dest`: | The bitset object where the result is stored
`src`: | A bitset. Must have have same size as `dest`.

Time complexity: O(n/w).

#### 12.4.7. `igraph_bitset_popcount` — The population count of the bitset.

    igraph_int_t igraph_bitset_popcount(const igraph_bitset_t *bitset);

Returns the number of set bits, also called the population count, of the bitset.

Arguments:

`bitset`: | The bitset object

Returns:

`` | The population count of the bitset.

Time complexity: O(n/w).

#### 12.4.8. `igraph_bitset_countl_zero` — The number of leading zeros in the bitset.

    igraph_int_t igraph_bitset_countl_zero(const igraph_bitset_t *bitset);

Returns the number of leading (starting at the most significant bit) zeros in the bitset before the first one is encountered. If the bitset is all zeros, then its size is returned.

Arguments:

`bitset`: | The bitset object

Returns:

`` | The number of leading zeros in the bitset.

Time complexity: O(n/w).

#### 12.4.9. `igraph_bitset_countl_one` — The number of leading ones in the bitset.

    igraph_int_t igraph_bitset_countl_one(const igraph_bitset_t *bitset);

Returns the number of leading ones (starting at the most significant bit) in the bitset before the first zero is encountered. If the bitset is all ones, then its size is returned.

Arguments:

`bitset`: | The bitset object

Returns:

`` | The number of leading ones in the bitset.

Time complexity: O(n/w).

#### 12.4.10. `igraph_bitset_countr_zero` — The number of trailing zeros in the bitset.

    igraph_int_t igraph_bitset_countr_zero(const igraph_bitset_t *bitset);

Returns the number of trailing (starting at the least significant bit) zeros in the bitset before the first one is encountered. If the bitset is all zeros, then its size is returned.

Arguments:

`bitset`: | The bitset object

Returns:

`` | The number of trailing zeros in the bitset.

Time complexity: O(n/w).

#### 12.4.11. `igraph_bitset_countr_one` — The number of trailing ones in the bitset.

    igraph_int_t igraph_bitset_countr_one(const igraph_bitset_t *bitset);

Returns the number of trailing ones (starting at the least significant bit) in the bitset before the first zero is encountered. If the bitset is all ones, then its size is returned.

Arguments:

`bitset`: | The bitset object

Returns:

`` | The number of trailing ones in the bitset.

Time complexity: O(n/w).

#### 12.4.12. `igraph_bitset_is_all_zero` — Are all bits zeros?

    igraph_bool_t igraph_bitset_is_all_zero(const igraph_bitset_t *bitset);

Arguments:

`bitset`: | The bitset object to test.

Returns:

`` | True if none of the bits are set.

Time complexity: O(n/w).

#### 12.4.13. `igraph_bitset_is_all_one` — Are all bits ones?

    igraph_bool_t igraph_bitset_is_all_one(const igraph_bitset_t *bitset);

Arguments:

`bitset`: | The bitset object to test.

Returns:

`` | True if all of the bits are set.

Time complexity: O(n/w).

#### 12.4.14. `igraph_bitset_is_any_zero` — Are any bits zeros?

    igraph_bool_t igraph_bitset_is_any_zero(const igraph_bitset_t *bitset);

Arguments:

`bitset`: | The bitset object to test.

Returns:

`` | True if at least one bit is zero.

Time complexity: O(n/w).

#### 12.4.15. `igraph_bitset_is_any_one` — Are any bits ones?

    igraph_bool_t igraph_bitset_is_any_one(const igraph_bitset_t *bitset);

Arguments:

`bitset`: | The bitset object to test.

Returns:

`` | True if at least one bit is one.

Time complexity: O(n/w).

### 12.5. Bitset properties

#### 12.5.1. `igraph_bitset_size` — Returns the length of the bitset.

    igraph_int_t igraph_bitset_size(const igraph_bitset_t *bitset);

Arguments:

`bitset`: | The bitset object

Returns:

`` | The size of the bitset.

Time complexity: O(1).

#### 12.5.2. `igraph_bitset_capacity` — Returns the allocated capacity of the bitset.

    igraph_int_t igraph_bitset_capacity(const igraph_bitset_t *bitset);

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

Arguments:

`bitset`: | Pointer to the (previously initialized) bitset object to query.

Returns:

`` | The allocated capacity.

See also:

`` | `igraph_bitset_size()`.

Time complexity: O(1).

### 12.6. Resizing operations

#### 12.6.1. `igraph_bitset_reserve` — Reserves memory for a bitset.

    igraph_error_t igraph_bitset_reserve(igraph_bitset_t *bitset, igraph_int_t capacity);

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

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

Arguments:

`bitset`: | The bitset object.
`capacity`: | The new allocated size of the bitset.

Returns:

`` | Error code: `IGRAPH_ENOMEM` if there is not enough memory.

Time complexity: operating system dependent, should be around O(n/w), n is the new allocated size of the bitset, w is the word size of the machine (32 or 64).

#### 12.6.2. `igraph_bitset_resize` — Resizes the bitset.

    igraph_error_t igraph_bitset_resize(igraph_bitset_t *bitset, igraph_int_t new_size);

Note that this function does not free any memory, just sets the size of the bitset to the given one. It may, 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 bitset are set to zero.

Arguments:

`bitset`: | The bitset object
`new_size`: | The new size of the bitset.

Returns:

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

See also:

`` | `igraph_bitset_reserve()` for allocating memory for future extensions of a bitset.

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/w), n is the new size of the bitset, w is the word size of the machine (32 or 64).

### 12.7. Copying bitsets

#### 12.7.1. `igraph_bitset_update` — Update a bitset from another one.

    igraph_error_t igraph_bitset_update(igraph_bitset_t *dest, const igraph_bitset_t *src);

The size and contents of `dest` will be identical to that of `src`.

Arguments:

`dest`: | Pointer to an initialized bitset object. This will be updated.
`src`: | The bitset to update from.

Returns:

`` | Error code: `IGRAPH_ENOMEM` if there is not enough memory.

Time complexity: operating system dependent, usually O(n/w), n is the size of the bitset, w is the word size of the machine (32 or 64).