igraph Reference Manual

For using the igraph C library

Search the manual:

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

1. About template types

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

vector

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

matrix

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

array3

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

stack

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

double-ended queue

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

heap

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

list of vectors

Lists of vectors are currently defined for vectors holding igraph_real_t and igraph_integer_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_integer_t elements. Its functions have the igraph_heap_int_ prefix.

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

  • 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_integer_t), igraph_vector_bool_t for booleans (of type igraph_bool_t) and so on. Vectors are used extensively in igraph; all functions that expect or return a list of numbers use igraph_vector_t or igraph_vector_int_t to achieve this. Integer vectors are typically used when the vector is supposed to hold vertex or edge identifiers, while igraph_vector_t is used when the vector is expected to hold fractional numbers or infinities.

The igraph_vector_t type and its variants usually use O(n) space to store n elements. Sometimes they 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_integer_t size);

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

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

Arguments: 

v:

Pointer to a not yet initialized vector object.

size:

The size of the vector.

Returns: 

error code: IGRAPH_ENOMEM if there is not enough memory.

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

2.2.2. igraph_vector_init_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_integer_t length);

Arguments: 

v:

Pointer to an uninitialized vector object.

data:

A regular C array.

length:

The length of the C array.

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

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

2.2.3. igraph_vector_init_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 from, igraph_real_t to);

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 from, igraph_real_t to);

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

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

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

igraph_real_t igraph_vector_tail(const igraph_vector_t *v);

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

Arguments: 

v:

The vector object.

Returns: 

The last element.

Time complexity: O(1).

2.5. Vector views

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

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

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

Arguments: 

v:

Pointer to an uninitialized igraph_vector_t object.

data:

Pointer, the C array. It may not be NULL, except when length is zero.

length:

The length of the C array.

Returns: 

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

Time complexity: O(1)

2.6. Copying vectors

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

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

The C array should have sufficient length.

Arguments: 

v:

The vector object.

to:

The C array.

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

2.6.2. igraph_vector_update — Update a vector from another one.

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

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

Arguments: 

to:

The vector to update.

from:

The vector to update from.

Returns: 

Error code.

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

2.6.3. igraph_vector_append — Append a vector to another one.

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

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

Arguments: 

to:

The vector to append to.

from:

The vector to append, it is kept unchanged.

Returns: 

Error code.

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

2.6.4. igraph_vector_swap — Swap all elements of two vectors.

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

Arguments: 

v1:

The first vector.

v2:

The second vector.

Returns: 

Error code.

Time complexity: O(1).

2.7. Exchanging elements

2.7.1. igraph_vector_swap_elements — Swap two elements in a vector.

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

Note that currently no range checking is performed.

Arguments: 

v:

The input vector.

i:

Index of the first element.

j:

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

Returns: 

Error code, currently always IGRAPH_SUCCESS.

Time complexity: O(1).

2.7.2. igraph_vector_reverse — Reverse the elements of a vector.

igraph_error_t igraph_vector_reverse(igraph_vector_t *v);

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

Arguments: 

v:

The input vector.

Returns: 

Error code, currently always IGRAPH_SUCCESS.

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

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

igraph_error_t igraph_vector_shuffle(igraph_vector_t *v);

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

Arguments: 

v:

The vector object.

Returns: 

Error code, currently always IGRAPH_SUCCESS.

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

References:

(Fisher & Yates 1963)

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

(Knuth 1998)

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

Example 7.1.  File examples/simple/igraph_fisher_yates_shuffle.c

#include <igraph.h>

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

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

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

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

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

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

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

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

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

    return 0;
}


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

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

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

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

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

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

Arguments: 

v:

the vector to permute

ind:

the index vector

Returns: 

Error code: IGRAPH_ENOMEM if there is not enough memory.

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

2.8. Vector operations

2.8.1. igraph_vector_add_constant — Add a constant to the vector.

void igraph_vector_add_constant(igraph_vector_t *v, igraph_real_t plus);

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

Arguments: 

v:

The input vector.

plus:

The constant to add.

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

2.8.2. igraph_vector_scale — 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_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.8. 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_integer_t i, n;

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

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

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

    /* Print the cliques in lexicographical order */
    printf("Maximal cliques in lexicographical order:\n");
    igraph_vector_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.9. 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.10. 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_integer_t i, n;

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

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

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

    /* Print the cliques in lexicographical order */
    printf("Maximal cliques in lexicographical order:\n");
    igraph_vector_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.11. 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_integer_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_integer_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_integer_t *which_min, igraph_integer_t *which_max);

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

Arguments: 

v:

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

which_min:

The index of the minimum element will be stored here.

which_max:

The index of the maximum element will be stored here.

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 — Returns the size (=length) of the vector.

igraph_integer_t igraph_vector_size(const igraph_vector_t* v);

Arguments: 

v:

The vector object

Returns: 

The size of the vector.

Time complexity: O(1).

2.11.3. igraph_vector_capacity — Returns the allocated capacity of the vector.

igraph_integer_t igraph_vector_capacity(const igraph_vector_t*v);

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

Arguments: 

v:

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

Returns: 

The allocated capacity.

See also: 

Time complexity: O(1).

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

igraph_real_t igraph_vector_sum(const igraph_vector_t *v);

For the empty vector 0.0 is returned.

Arguments: 

v:

The vector object.

Returns: 

The sum of the elements.

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

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

igraph_real_t igraph_vector_prod(const igraph_vector_t *v);

For the empty vector one (1) is returned.

Arguments: 

v:

The vector object.

Returns: 

The product of the elements.

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

2.11.6. igraph_vector_isininterval — Checks if all elements of a vector are in the given 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.12. Searching for elements

2.12.1. igraph_vector_contains — Linear search in a vector.

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

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

Arguments: 

v:

The input vector.

e:

The element to look for.

Returns: 

true if the element is found and false otherwise.

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

2.12.2. igraph_vector_search — Searches in a vector from a given position.

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

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

Arguments: 

v:

The input vector.

from:

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

what:

The element to find.

pos:

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

Returns: 

Boolean, true if the element was found, false otherwise.

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

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

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

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

Arguments: 

v:

The igraph_vector_t object.

what:

The element to search for.

pos:

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

Returns: 

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_integer_t *pos, igraph_integer_t start, igraph_integer_t end);

It is assumed that the indicated slice of the vector, from start to end, is sorted. If the specified element (what) is not in the slice of the vector, then the position of where it should be inserted (to keep the 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_integer_t. This is set to the position of an instance of what in the slice of the vector if it is present. If v does not contain what then pos is set to the position to which it should be inserted (to keep the the vector sorted).

start:

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

end:

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

Returns: 

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_binsearch2 — Binary search, without returning the index.

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

It is assumed that the vector is sorted.

Arguments: 

v:

The igraph_vector_t object.

what:

The element to search for.

Returns: 

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

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_integer_t pos, igraph_real_t value);

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

Arguments: 

v:

The vector object.

pos:

The position where the new element is to be inserted.

value:

The new element to be inserted.

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

void igraph_vector_remove(igraph_vector_t *v, igraph_integer_t elem);

Note that this function does not do range checking.

Arguments: 

v:

The vector object.

elem:

The position of the element to remove.

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

2.13.9. igraph_vector_remove_section — Deletes a section from a vector.

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

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.

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

m:

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_qsort_ind — Returns a permutation of indices that sorts a vector.

igraph_error_t igraph_vector_qsort_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 \v order). The order of indices for identical elements is not defined. If the vector contains any NaN values, the ordering of NaN values is undefined.

Arguments: 

v:

the array to be sorted

inds:

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

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 — Calculates the intersection of two sorted vectors.

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

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

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

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

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

Arguments: 

v1:

the first vector

v2:

the second vector

result:

the result vector, which will also be sorted.

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

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

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

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

Arguments: 

v1:

the first vector

v2:

the second vector

result:

the result vector

2.17.  Pointer vectors (igraph_vector_ptr_t)

2.17.1. igraph_vector_ptr_init — Initialize a pointer vector (constructor).
2.17.2. igraph_vector_ptr_init_copy — Initializes a pointer vector from another one (constructor).
2.17.3. igraph_vector_ptr_destroy — Destroys a pointer vector.
2.17.4. igraph_vector_ptr_free_all — Frees all the elements of a pointer vector.
2.17.5. igraph_vector_ptr_destroy_all — Frees all the elements and destroys the pointer vector.
2.17.6. igraph_vector_ptr_size — Gives the number of elements in the pointer vector.
2.17.7. igraph_vector_ptr_clear — Removes all elements from a pointer vector.
2.17.8. igraph_vector_ptr_push_back — Appends an element to the back of a pointer vector.
2.17.9. igraph_vector_ptr_pop_back — Removes and returns the last element of a pointer vector.
2.17.10. igraph_vector_ptr_insert — Inserts a single element into a pointer vector.
2.17.11. igraph_vector_ptr_get — Access an element of a pointer vector.
2.17.12. igraph_vector_ptr_set — Assign to an element of a pointer vector.
2.17.13. igraph_vector_ptr_resize — Resizes a pointer vector.
2.17.14. igraph_vector_ptr_sort — Sorts the pointer vector based on an external comparison function.
2.17.15. igraph_vector_ptr_sort_ind — Returns a permutation of indices that sorts a vector of pointers.
2.17.16. igraph_vector_ptr_permute — Permutes the elements of a pointer vector in place according to an index vector.
2.17.17. igraph_vector_ptr_get_item_destructor — Gets the current item destructor for this pointer vector.
2.17.18. igraph_vector_ptr_set_item_destructor — Sets the item destructor for this pointer vector.
2.17.19. IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR — Sets the item destructor for this pointer vector (macro version).

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

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

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

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

Arguments: 

v:

Pointer to an uninitialized igraph_vector_ptr_t object, to be created.

size:

Integer, the size of the pointer vector.

Returns: 

Error code: IGRAPH_ENOMEM if out of memory

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

2.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_integer_t igraph_vector_ptr_size(const igraph_vector_ptr_t* v);

Arguments: 

v:

The pointer vector object.

Returns: 

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

Time complexity: O(1).

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

void igraph_vector_ptr_clear(igraph_vector_ptr_t* v);

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

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

Arguments: 

v:

The pointer vector to clear.

Time complexity: O(1).

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

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

Arguments: 

v:

The pointer vector.

e:

The new element to include in the pointer vector.

Returns: 

Error code.

See also: 

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

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

2.17.9. 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.10. igraph_vector_ptr_insert — Inserts a single element into a pointer vector.

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

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

Arguments: 

v:

The pointer vector object.

pos:

The position where the new element is inserted.

e:

The inserted element

2.17.11. igraph_vector_ptr_get — Access an element of a pointer vector.

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

Arguments: 

v:

Pointer to a pointer vector.

pos:

The index of the pointer to return.

Returns: 

The pointer at pos position.

Time complexity: O(1).

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

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

Arguments: 

v:

Pointer to a pointer vector.

pos:

The index of the pointer to update.

value:

The new pointer to set in the vector.

Time complexity: O(1).

2.17.13. igraph_vector_ptr_resize — Resizes a pointer vector.

igraph_error_t igraph_vector_ptr_resize(igraph_vector_ptr_t* v, igraph_integer_t newsize);

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

Arguments: 

v:

A pointer vector.

newsize:

The new size of the pointer vector.

Returns: 

Error code.

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

2.17.14. 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.15. 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.16. 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.17. 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.18. 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.19. 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*

2.18. Deprecated functions

2.18.1. igraph_vector_copy — Initializes a vector from another vector object (deprecated alias).

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

Warning

Deprecated since version 0.10. Please do not use this function in new code; use igraph_vector_init_copy() instead.

2.18.2. igraph_vector_e — Access an element of a vector (deprecated alias).

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

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_vector_get() instead.

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

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

Arguments: 

v:

The igraph_vector_t object.

pos:

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

Returns: 

Pointer to the desired element.

See also: 

igraph_vector_get() and the VECTOR macro.

Time complexity: O(1).

2.18.4. igraph_vector_init_seq — Initializes a vector with a sequence, inclusive endpoints (deprecated).

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

The vector will contain the numbers from, from+1, ..., to. Note that both endpoints are inclusive, contrary to typical usage of ranges in C.

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_vector_init_range() instead.

Arguments: 

v:

Pointer to an uninitialized vector object.

from:

The lower limit in the sequence (inclusive).

to:

The upper limit in the sequence (inclusive).

Returns: 

Error code: IGRAPH_ENOMEM: out of memory.

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

2.18.5. igraph_vector_ptr_copy — Initializes a pointer vector from another one (deprecated alias).

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

Warning

Deprecated since version 0.10. Please do not use this function in new code; use igraph_vector_ptr_init_copy() instead.

2.18.6. igraph_vector_ptr_e — Access an element of a pointer vector (deprecated alias).

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

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_vector_ptr_get() instead.

3. Matrices

3.1.  About igraph_matrix_t objects

This type is just an interface to igraph_vector_t.

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

3.2.  Matrix constructors and destructors

3.2.1. igraph_matrix_init — Initializes a matrix.

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

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

Arguments: 

m:

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

nrow:

The number of rows in the matrix.

ncol:

The number of columns in the matrix.

Returns: 

Error code.

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

3.2.2. igraph_matrix_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_integer_t nrow, igraph_integer_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_integer_t row, igraph_integer_t col);

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

Arguments: 

m:

The input matrix.

row:

The row index.

col:

The column index.

Returns: 

The element in the given row and column.

Time complexity: O(1).

3.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_integer_t row, igraph_integer_t col);

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

Arguments: 

m:

The input matrix.

row:

The row index.

col:

The column index.

Returns: 

Pointer to the element in the given row and column.

Time complexity: O(1).

3.4.4. igraph_matrix_set — Set an element.

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

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

Arguments: 

m:

The input matrix.

row:

The row index.

col:

The column index.

value:

The new value of the element.

Time complexity: O(1).

3.5. Matrix views

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

const igraph_matrix_t* igraph_matrix_view(
        const igraph_matrix_t *m, const igraph_real_t *data,
        igraph_integer_t nrow, igraph_integer_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: 

m:

Pointer to a not yet initialized matrix object where the view will be created.

data:

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

Pointer to the matrix object, the same as the m parameter, for convenience.

Time complexity: O(1).

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

const igraph_matrix_t *igraph_matrix_view_from_vector(
    const igraph_matrix_t *m, const igraph_vector_t *v,
    igraph_integer_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: 

m:

Pointer to a not yet initialized matrix object where the view will be created.

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: 

Error code.

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

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

Arguments: 

m:

Pointer to an initialized matrix object.

to:

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

Returns: 

Error code.

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

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

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

Returns: 

Error code.

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

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

Arguments: 

m:

The input matrix.

res:

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

index:

The index of the row to select.

Returns: 

Error code.

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

3.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_integer_t index);

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

Arguments: 

m:

The input matrix.

res:

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

index:

The index of the column to select.

Returns: 

Error code.

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

3.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_integer_t index);

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

Arguments: 

m:

The input matrix.

v:

The vector containing the new elements of the row.

index:

Index of the row to set.

Returns: 

Error code.

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

3.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_integer_t index);

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

Arguments: 

m:

The input matrix.

v:

The vector containing the new elements of the column.

index:

Index of the column to set.

Returns: 

Error code.

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

3.7.5. igraph_matrix_swap_rows — Swap two rows.

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

Swap two rows in the matrix.

Arguments: 

m:

The input matrix.

i:

The index of the first row.

j:

The index of the second row.

Returns: 

Error code.

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

3.7.6. igraph_matrix_swap_cols — Swap two columns.

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

Swap two columns in the matrix.

Arguments: 

m:

The input matrix.

i:

The index of the first column.

j:

The index of the second column.

Returns: 

Error code.

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

3.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_integer_t *i, igraph_integer_t *j);

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

Arguments: 

m:

The matrix.

i:

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

j:

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

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_integer_t *i, igraph_integer_t *j);

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

Arguments: 

m:

The matrix.

i:

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

j:

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

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_integer_t *imin, igraph_integer_t *jmin,
        igraph_integer_t *imax, igraph_integer_t *jmax);

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

Arguments: 

m:

The input matrix.

imin:

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

jmin:

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

imax:

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

jmax:

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

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_integer_t igraph_matrix_size(const igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Returns: 

The size of the matrix.

Time complexity: O(1).

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

igraph_integer_t igraph_matrix_capacity(const igraph_matrix_t *m);

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

Arguments: 

v:

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

Returns: 

The allocated capacity.

See also: 

Time complexity: O(1).

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

igraph_integer_t igraph_matrix_nrow(const igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Returns: 

The number of rows in the matrix.

Time complexity: O(1).

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

igraph_integer_t igraph_matrix_ncol(const igraph_matrix_t *m);

Arguments: 

m:

Pointer to an initialized matrix object.

Returns: 

The number of columns in the matrix.

Time complexity: O(1).

3.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_integer_t from, igraph_real_t what, igraph_integer_t *pos,
        igraph_integer_t *row, igraph_integer_t *col);

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

Arguments: 

m:

The input matrix.

from:

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

what:

The element to search for.

pos:

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

row:

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

col:

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

Returns: 

Boolean, true if the element is found, false otherwise.

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

3.14. Resizing operations

3.14.1. igraph_matrix_resize — Resizes a matrix.

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

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

Arguments: 

m:

Pointer to an already initialized matrix object.

nrow:

The number of rows in the resized matrix.

ncol:

The number of columns in the resized matrix.

Returns: 

Error code.

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

3.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: 

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

Arguments: 

m:

The matrix object.

n:

The number of rows to add.

Returns: 

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

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

3.14.4. igraph_matrix_add_cols — Adds columns to a matrix.

igraph_error_t igraph_matrix_add_cols(igraph_matrix_t *m, igraph_integer_t n);

Arguments: 

m:

The matrix object.

n:

The number of columns to add.

Returns: 

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

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

3.14.5. igraph_matrix_remove_row — Remove a row.

igraph_error_t igraph_matrix_remove_row(igraph_matrix_t *m, igraph_integer_t row);

A row is removed from the matrix.

Arguments: 

m:

The input matrix.

row:

The index of the row to remove.

Returns: 

Error code.

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

3.14.6. igraph_matrix_remove_col — Removes a column from a matrix.

igraph_error_t igraph_matrix_remove_col(igraph_matrix_t *m, igraph_integer_t col);

Arguments: 

m:

The matrix object.

col:

The column to remove.

Returns: 

Error code, always returns with success.

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

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.

3.16. Deprecated functions

3.16.1. igraph_matrix_copy — Copies a matrix (deprecated alias).

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

Warning

Deprecated since version 0.10. Please do not use this function in new code; use igraph_matrix_init_copy() instead.

3.16.2. igraph_matrix_e — Extract an element from a matrix (deprecated alias).

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

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_matrix_get() instead.

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

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

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_matrix_get_ptr() instead.

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_integer_t i;

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

    /* Convert a ring graph to a matrix, print it, compress, print again */
#define VC 10
    igraph_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_integer_t nrow = igraph_vector_int_size(p);
    igraph_integer_t ncol = igraph_vector_int_size(q);
    igraph_integer_t i, j;

    igraph_matrix_resize(res, nrow, ncol);

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

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

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

    igraph_matrix_resize(res, nrow, ncol);

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

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

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

    igraph_matrix_resize(res, nrow, ncol);

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

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

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_integer_t i;

    RNG_BEGIN();

    /* Permutation of a matrix */

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

    igraph_vector_int_init_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_integer_t r = RNG_INTEGER(0, NROW - 1);
        igraph_integer_t c = RNG_INTEGER(0, NCOL - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        MATRIX(M, r, c) = MATRIX(M, r, c) + value;
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);

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

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

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

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

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

    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_integer_t row = RNG_INTEGER(0, NROW - 1);
        igraph_integer_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_integer_t r = RNG_INTEGER(0, NROW - 1);
        igraph_integer_t c = RNG_INTEGER(0, NCOL - 1);
        igraph_real_t value = RNG_INTEGER(1, 5);
        MATRIX(M, r, c) = MATRIX(M, r, c) + value;
        igraph_sparsemat_entry(&A, r, c, value);
    }
    igraph_sparsemat_compress(&A, &B);
    igraph_sparsemat_destroy(&A);

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

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

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

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

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

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

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

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

    RNG_END();

    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_integer_t row = igraph_sparsemat_iterator_row(&it);
        igraph_integer_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);
    igraph_vector_destroy(&res);

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

    return success;
}

int main(void) {

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

    RNG_BEGIN();

    /* lsolve */

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

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

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

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

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

#undef DIM
#undef EDGES

    /* ltsolve */

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

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

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

    igraph_sparsemat_transpose(&B, &A);
    if (! check_solution(&A, &x, &b)) {
        return 2;
    }

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

#undef DIM
#undef EDGES

    /* usolve */

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

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

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

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

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

#undef DIM
#undef EDGES

    /* utsolve */

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

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

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

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

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

#undef DIM
#undef EDGES

    /* lusol */

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

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

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

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

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

#undef DIM
#undef EDGES

    RNG_END();

    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;

    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_integer_t i = 0; i < NUM_NONZEROS; i++) {
        igraph_integer_t r = igraph_rng_get_integer(igraph_rng_default(), 0, NROW - 1);
        igraph_integer_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;

    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_integer_t i, j, nz1, nz2;
    igraph_vector_t sums1, sums2;


    igraph_rng_seed(igraph_rng_default(), 42);

    /* COPY */

    igraph_sparsemat_init(&spmat, DIM1, DIM2, 20);
    for (i = 0; i < 10; i++) {
        igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0);
    }
    igraph_sparsemat_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_integer_t rows,
        igraph_integer_t cols, igraph_integer_t nzmax);

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

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

Arguments: 

A:

Pointer to a not yet initialized sparse matrix.

rows:

The number of rows in the matrix.

cols:

The number of columns.

nzmax:

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

Returns: 

Error code.

Time complexity: TODO.

4.2.2. igraph_sparsemat_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_integer_t nzmax, const igraph_vector_t *values,
    igraph_bool_t compress
);

Arguments: 

A:

An uninitialized sparse matrix, the result is stored here.

nzmax:

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

values:

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

compress:

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

Returns: 

Error code.

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

4.2.4. igraph_sparsemat_init_eye — Creates a sparse identity matrix.

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

Arguments: 

A:

An uninitialized sparse matrix, the result is stored here.

n:

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

nzmax:

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

value:

The value to store in the diagonal.

compress:

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

Returns: 

Error code.

Time complexity: O(n).

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

igraph_error_t igraph_sparsemat_realloc(igraph_sparsemat_t *A, igraph_integer_t nzmax);

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

Arguments: 

A:

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

nzmax:

The new maximum number of non-zero elements.

Returns: 

Error code.

Time complexity: TODO.

4.2.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.2.7. igraph_sparsemat_view — Initialize a sparse matrix and set all parameters.

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

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

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

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

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

Arguments: 

A:

The non-initialized sparse matrix.

nzmax:

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

m:

The number of matrix rows.

n:

The number of matrix columns.

p:

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

i:

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

x:

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

nz:

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

Returns: 

Error code.

Time complexity: O(1).

4.3. Query properties of a sparse matrix

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

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

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

Arguments: 

A:

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

p:

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

q:

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

res:

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

constres:

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

Returns: 

Error code.

Time complexity: TODO.

4.3.2. igraph_sparsemat_nrow — Number of rows.

igraph_integer_t igraph_sparsemat_nrow(const igraph_sparsemat_t *A);

Arguments: 

A:

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

Returns: 

The number of rows in the A matrix.

Time complexity: O(1).

4.3.3. igraph_sparsemat_ncol — Number of columns.

igraph_integer_t igraph_sparsemat_ncol(const igraph_sparsemat_t *A);

Arguments: 

A:

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

Returns: 

The number of columns in the A matrix.

Time complexity: O(1).

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

igraph_sparsemat_type_t igraph_sparsemat_type(const igraph_sparsemat_t *A);

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

Arguments: 

A:

The input matrix.

Returns: 

Either IGRAPH_SPARSEMAT_CC or IGRAPH_SPARSEMAT_TRIPLET.

Time complexity: O(1).

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

igraph_bool_t igraph_sparsemat_is_triplet(const igraph_sparsemat_t *A);

Decides whether a sparse matrix is in triplet format.

Arguments: 

A:

The input matrix.

Returns: 

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

Time complexity: O(1).

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

igraph_bool_t igraph_sparsemat_is_cc(const igraph_sparsemat_t *A);

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

Arguments: 

A:

The input matrix.

Returns: 

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

Time complexity: O(1).

4.3.7. igraph_sparsemat_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_integer_t row, igraph_integer_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_POSINFINITY 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_NEGINFINITY 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_POSINFINITY if the matrix has zero elements.

max:

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

Returns: 

Error code.

Time complexity: TODO.

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

igraph_integer_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_integer_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: 

The:

input matrix, column-compressed.

Real:

scalar, the tolerance.

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_integer_t igraph_sparsemat_nonzero_storage(const igraph_sparsemat_t *A);

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

Arguments: 

A:

A sparse matrix in either triplet or compressed form.

Returns: 

Number of stored entries.

Time complexity: O(1).

4.4. Operations on sparse matrices

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

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

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

Arguments: 

A:

The input matrix, it must be in triplet format.

row:

The row index of the entry to add.

col:

The column index of the entry to add.

elem:

The value of the entry.

Returns: 

Error code.

Time complexity: O(1) on average.

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

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

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

Arguments: 

A:

The input matrix, in column-compressed format.

fkeep:

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

other:

A void pointer that is passed to the filtering function.

Returns: 

Error code.

Time complexity: TODO.

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

igraph_error_t igraph_sparsemat_dropzeros(igraph_sparsemat_t *A);

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

Arguments: 

A:

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

Returns: 

Error code.

Time complexity: TODO.

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

igraph_error_t igraph_sparsemat_droptol(igraph_sparsemat_t *A, igraph_real_t tol);

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

Arguments: 

A:

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

tol:

Real number, giving the tolerance threshold.

Returns: 

Error code.

Time complexity: TODO.

4.4.5. igraph_sparsemat_scale — Scales a sparse matrix.

igraph_error_t igraph_sparsemat_scale(igraph_sparsemat_t *A, igraph_real_t by);

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

Arguments: 

A:

The input matrix.

by:

The scaling factor.

Returns: 

Error code.

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

4.4.6. igraph_sparsemat_permute — Permutes the rows and columns of a sparse matrix.

igraph_error_t igraph_sparsemat_permute(const igraph_sparsemat_t *A,
                                        const igraph_vector_int_t *p,
                                        const igraph_vector_int_t *q,
                                        igraph_sparsemat_t *res);

Arguments: 

A:

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

p:

Integer vector, giving the permutation of the rows.

q:

Integer vector, the permutation of the columns.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

Returns: 

Error code.

Time complexity: O(m+n+nz), the number of rows plus the number of columns plus the number of non-zero elements in the matrix.

4.4.7. igraph_sparsemat_transpose — Transposes a sparse matrix.

igraph_error_t igraph_sparsemat_transpose(
    const igraph_sparsemat_t *A, igraph_sparsemat_t *res
);

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 scalar, A is multiplied by alpha before the addition.

beta:

Real scalar, B is multiplied by beta before the addition.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.4.9. igraph_sparsemat_multiply — Matrix multiplication.

igraph_error_t igraph_sparsemat_multiply(const igraph_sparsemat_t *A,
                              const igraph_sparsemat_t *B,
                              igraph_sparsemat_t *res);

Multiplies two sparse matrices.

Arguments: 

A:

The first input matrix (left hand side), in column-compressed format.

B:

The second input matrix (right hand side), in column-compressed format.

res:

Pointer to an uninitialized sparse matrix, the result is stored here.

Returns: 

Error code.

Time complexity: TODO.

4.4.10. igraph_sparsemat_gaxpy — Matrix-vector product, added to another vector.

igraph_error_t igraph_sparsemat_gaxpy(const igraph_sparsemat_t *A,
                           const igraph_vector_t *x,
                           igraph_vector_t *res);

Arguments: 

A:

The input matrix, in column-compressed format.

x:

The input vector, its size must match the number of columns in A.

res:

This vector is added to the matrix-vector product and it is overwritten by the result.

Returns: 

Error code.

Time complexity: TODO.

4.4.11. igraph_sparsemat_add_rows — Adds rows to a sparse matrix.

igraph_error_t igraph_sparsemat_add_rows(igraph_sparsemat_t *A, igraph_integer_t n);

The current matrix elements are retained and all elements in the new rows are zero.

Arguments: 

A:

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

n:

The number of rows to add.

Returns: 

Error code.

Time complexity: O(1).

4.4.12. igraph_sparsemat_add_cols — Adds columns to a sparse matrix.

igraph_error_t igraph_sparsemat_add_cols(igraph_sparsemat_t *A, igraph_integer_t n);

The current matrix elements are retained, and all elements in the new columns are zero.

Arguments: 

A:

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

n:

The number of columns to add.

Returns: 

Error code.

Time complexity: TODO.

4.4.13. igraph_sparsemat_resize — Resizes a sparse matrix and clears all the elements.

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

This function resizes a sparse matrix. The resized sparse matrix will 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_integer_t igraph_sparsemat_iterator_row(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The row of the element at the current iterator position.

Time complexity: O(1).

4.5.5. igraph_sparsemat_iterator_col — Return the column of the iterator.

igraph_integer_t igraph_sparsemat_iterator_col(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The column of the element at the current iterator position.

Time complexity: O(1).

4.5.6. igraph_sparsemat_iterator_get — Return the element at the current iterator position.

igraph_real_t
igraph_sparsemat_iterator_get(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The value of the element at the current iterator position.

Time complexity: O(1).

4.5.7. igraph_sparsemat_iterator_next — Let a sparse matrix iterator go to the next element.

igraph_integer_t igraph_sparsemat_iterator_next(igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The position of the iterator in the element vector.

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

4.5.8. igraph_sparsemat_iterator_idx — Returns the element vector index of a sparse matrix iterator.

igraph_integer_t igraph_sparsemat_iterator_idx(const igraph_sparsemat_iterator_t *it);

Arguments: 

it:

A pointer to the sparse matrix iterator.

Returns: 

The position of the iterator in the element vector.

Time complexity: O(1).

4.6. Operations that change the internal representation

4.6.1. igraph_sparsemat_compress — Converts a sparse matrix to column-compressed format.

igraph_error_t igraph_sparsemat_compress(const igraph_sparsemat_t *A,
                              igraph_sparsemat_t *res);

Converts a sparse matrix from triplet format to column-compressed format. Almost all sparse matrix operations require that the matrix is in column-compressed format.

Arguments: 

A:

The input matrix, it must be in triplet format.

res:

Pointer to an uninitialized sparse matrix object, the compressed version of A is stored here.

Returns: 

Error code.

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

4.6.2. igraph_sparsemat_dupl — Removes duplicate elements from a sparse matrix.

igraph_error_t igraph_sparsemat_dupl(igraph_sparsemat_t *A);

It is possible that a column-compressed sparse matrix stores a single matrix entry in multiple pieces. The entry is then the sum of all its pieces. (Some functions create matrices like this.) This function eliminates the multiple pieces.

Arguments: 

A:

The input matrix, in column-compressed format.

Returns: 

Error code.

Time complexity: TODO.

4.7. Decompositions and solving linear systems

4.7.1. igraph_sparsemat_symblu — Symbolic LU decomposition.

igraph_error_t igraph_sparsemat_symblu(igraph_integer_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_integer_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_integer_t order);

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

Arguments: 

A:

The input matrix, in column-compressed format.

v:

The right hand side.

res:

An initialized vector, the result is stored here.

order:

An integer giving the ordering method to use for the factorization. Zero is the natural ordering; if it is one, then the fill-reducing minimum-degree ordering of A+A' is used.

Returns: 

Error code.

Time complexity: TODO.

4.7.8. igraph_sparsemat_lusol — Solves a linear system via LU decomposition.

igraph_error_t igraph_sparsemat_lusol(const igraph_sparsemat_t *A,
                           const igraph_vector_t *b,
                           igraph_vector_t *res,
                           igraph_integer_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: 

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_sparsemat — Creates an igraph graph from a sparse matrix.

igraph_error_t igraph_sparsemat(igraph_t *graph, const igraph_sparsemat_t *A,
                     igraph_bool_t directed);

One edge is created for each non-zero entry in the matrix. If you have a symmetric matrix, and want to create an undirected graph, then delete the entries in the upper diagonal first, or call igraph_simplify() on the result graph to eliminate the multiple edges.

Arguments: 

graph:

Pointer to an uninitialized igraph_t object, the graphs is stored here.

A:

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

directed:

Boolean scalar, whether to create a directed graph.

Returns: 

Error code.

Time complexity: TODO.

4.9.2. igraph_matrix_as_sparsemat — Converts a dense matrix to a sparse matrix.

igraph_error_t igraph_matrix_as_sparsemat(igraph_sparsemat_t *res,
                               const igraph_matrix_t *mat,
                               igraph_real_t tol);

Arguments: 

res:

An uninitialized sparse matrix, the result is stored here.

mat:

The dense input matrix.

tol:

Real scalar, the tolerance. Values closer than tol to zero are considered as zero, and will not be included in the sparse matrix.

Returns: 

Error code.

See also: 

igraph_sparsemat_as_matrix() for the reverse conversion.

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

4.9.3. igraph_sparsemat_as_matrix — Converts a sparse matrix to a dense matrix.

igraph_error_t igraph_sparsemat_as_matrix(igraph_matrix_t *res,
                               const igraph_sparsemat_t *spmat);

Arguments: 

res:

Pointer to an initialized matrix, the result is stored here. It will be resized to the required size.

spmat:

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

Returns: 

Error code.

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.

4.11. Deprecated functions

4.11.1. igraph_sparsemat_copy — Copies a sparse matrix (deprecated alias).

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

Warning

Deprecated since version 0.10. Please do not use this function in new code; use igraph_sparsemat_init_copy() instead.

4.11.2. igraph_sparsemat_diag — Creates a sparse diagonal matrix (deprecated alias).

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

Warning

Deprecated since version 0.10. Please do not use this function in new code; use igraph_sparsemat_init_diag() instead.

4.11.3. igraph_sparsemat_eye — Creates a sparse identity matrix (deprecated alias).

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

Warning

Deprecated since version 0.10. Please do not use this function in new code; use igraph_sparsemat_init_eye() instead.

5. Stacks

5.1. igraph_stack_init — Initializes a stack.

igraph_error_t igraph_stack_init(igraph_stack_t* s, igraph_integer_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_integer_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_integer_t igraph_stack_size(const igraph_stack_t* s);

Arguments: 

s:

The stack object.

Returns: 

The number of elements in the stack.

Time complexity: O(1).

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;

    /* 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_integer_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_integer_t igraph_dqueue_size(const igraph_dqueue_t* q);

Arguments: 

q:

The queue.

Returns: 

Integer, the number of elements currently in the queue.

Time complexity: O(1).

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_integer_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_integer_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_integer_t len);

Initializes a heap object from an array. The heap is also built of course (constructor).

Arguments: 

h:

Pointer to an uninitialized heap object.

data:

Pointer to an array of base data type.

len:

The length of the array at data.

Returns: 

Error code.

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

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

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

len:

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 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_integer_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_integer_t idx,
                         const char *value);

The provided value is copied into the idx position in the string vector.

Arguments: 

sv:

The string vector.

idx:

The position to set.

value:

The new value.

Returns: 

Error code.

Time complexity: O(l), the length of the new string. Maybe more, depending on the memory management, if reallocation is needed.

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_integer_t idx,
                          const char *value, size_t len);

This is almost the same as igraph_strvector_set, but the new value is not a zero terminated string, but its length is given.

Arguments: 

sv:

The string vector.

idx:

The position to set.

value:

The new value.

len:

The length of the new value.

Returns: 

Error code.

Time complexity: O(l), the length of the new string. Maybe more, depending on the memory management, if reallocation is needed.

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, igraph_integer_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_remove — Removes a single element from a string vector.

void igraph_strvector_remove(igraph_strvector_t *sv, igraph_integer_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.11. igraph_strvector_remove_section — Removes a section from a string vector.

void igraph_strvector_remove_section(
        igraph_strvector_t *sv, igraph_integer_t from, igraph_integer_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.12. 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: 

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.13. 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: 

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.14. 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.15. igraph_strvector_resize — Resizes a string vector.

igraph_error_t igraph_strvector_resize(igraph_strvector_t *sv, igraph_integer_t newsize);

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

Arguments: 

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.16. igraph_strvector_reserve — Reserves memory for a string vector.

igraph_error_t igraph_strvector_reserve(igraph_strvector_t *sv, igraph_integer_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.17. 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.18. igraph_strvector_size — Returns the size of a string vector.

igraph_integer_t igraph_strvector_size(const igraph_strvector_t *sv);

Arguments: 

sv:

The string vector.

Returns: 

The length of the string vector.

Time complexity: O(1).

8.19. igraph_strvector_capacity — Returns the capacity of a string vector.

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

8.20. Deprecated functions

8.20.1. igraph_strvector_copy — Initialization by copying (deprecated alias).

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

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_strvector_init_copy() instead.

8.20.2. igraph_strvector_add — Adds an element to the back of a string vector (deprecated alias).

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

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_strvector_push_back() instead.

8.20.3. igraph_strvector_set2 — Sets an element of the string vector given a buffer and its size (deprecated alias).

igraph_error_t igraph_strvector_set2(
    igraph_strvector_t *sv, igraph_integer_t idx, const char *value, size_t len
);

Warning

Deprecated since version 0.10.0. Please do not use this function in new code; use igraph_strvector_set_len() instead.

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_integer_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_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 — Retrieve the address of a vector in the vector list.

igraph_vector_t* igraph_vector_list_get_ptr(const igraph_vector_list_t* v, igraph_integer_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 — Retrieve 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_integer_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_integer_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 — Returns the size (=length) of the vector.

igraph_integer_t igraph_vector_list_size(const igraph_vector_list_t* v);

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

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_integer_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 — Resize the list of vectors.

igraph_error_t igraph_vector_list_resize(igraph_vector_list_t* v, igraph_integer_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 — Append 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 — Append 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 — Append 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 — Remove 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 — Insert an existing vector into the list, transferring ownership.

igraph_error_t igraph_vector_list_insert(igraph_vector_list_t* v, igraph_integer_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 — Insert the copy of a vector to the list.

igraph_error_t igraph_vector_list_insert_copy(igraph_vector_list_t* v, igraph_integer_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 — Insert a new vector into the list.

igraph_error_t igraph_vector_list_insert_new(igraph_vector_list_t* v, igraph_integer_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 — Remove 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_integer_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 — Remove 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_integer_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 — Discard the item at the given index in the vector list.

void igraph_vector_list_discard(igraph_vector_list_t* v, igraph_integer_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 — Discard 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 — Discard the item at the given index in the vector list and move the last item to its place.

void igraph_vector_list_discard_fast(igraph_vector_list_t* v, igraph_integer_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.

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

igraph_error_t igraph_vector_list_swap_elements(igraph_vector_list_t *v1, igraph_integer_t i, igraph_integer_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;

    /* 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_multiple_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().

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

Creates a list of vectors, one for each vertex. This is useful when you are constructing a graph using an adjacency list representation as it does not require your graph to exist yet.

Arguments: 

no_of_nodes:

The number of vertices

al:

Pointer to an uninitialized igraph_adjlist_t object.

Returns: 

Error code.

Time complexity: O(|V|), linear in the number of vertices.

10.1.3. igraph_adjlist_init_complementer — Adjacency lists for the complementer graph.

igraph_error_t igraph_adjlist_init_complementer(const igraph_t *graph,
                                     igraph_adjlist_t *al,
                                     igraph_neimode_t mode,
                                     igraph_bool_t loops);

This function creates adjacency lists for the complementer of the input graph. In the complementer graph all edges are present which are not present in the original graph. Multiple edges in the input graph are ignored.

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:

Whether to consider loop edges.

Returns: 

Error code.

See also: 

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

10.1.4. igraph_adjlist_destroy — Deallocates an adjacency list.

void igraph_adjlist_destroy(igraph_adjlist_t *al);

Free all memory allocated for an adjacency list.

Arguments: 

al:

The adjacency list to destroy.

Time complexity: depends on memory management.

10.1.5. igraph_adjlist_get — Query a vector in an adjacency list.

#define igraph_adjlist_get(al,no)

Returns a pointer to an igraph_vector_int_t object from an adjacency list. The vector can be modified as desired.

Arguments: 

al:

The adjacency list object.

no:

The vertex whose adjacent vertices will be returned.

Returns: 

Pointer to the igraph_vector_int_t object.

Time complexity: O(1).

10.1.6. igraph_adjlist_size — Returns the number of vertices in an adjacency list.

igraph_integer_t igraph_adjlist_size(const igraph_adjlist_t *al);

Arguments: 

al:

The adjacency list.

Returns: 

The number of vertices in the adjacency list.

Time complexity: O(1).

10.1.7. igraph_adjlist_clear — Removes all edges from an adjacency list.

void igraph_adjlist_clear(igraph_adjlist_t *al);

Arguments: 

al:

The adjacency list. Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the adjacency list.

10.1.8. igraph_adjlist_sort — Sorts each vector in an adjacency list.

void igraph_adjlist_sort(igraph_adjlist_t *al);

Sorts every vector of the adjacency list. 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(n log n), n is the total number of elements in the adjacency list.

10.1.9. igraph_adjlist_simplify — Simplifies an adjacency list.

igraph_error_t igraph_adjlist_simplify(igraph_adjlist_t *al);

Simplifies an adjacency list, i.e. removes loop and multiple edges.

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: 

eal:

The incidence list to destroy.

Time complexity: depends on memory management.

10.2.3. igraph_inclist_get — Query a vector in an incidence list.

#define igraph_inclist_get(il,no)

Returns a pointer to an igraph_vector_int_t object from an incidence list containing edge IDs. The vector can be modified, resized, etc. as desired.

Arguments: 

il:

Pointer to the incidence list.

no:

The vertex for which the incident edges are returned.

Returns: 

Pointer to an igraph_vector_int_t object.

Time complexity: O(1).

10.2.4. igraph_inclist_size — Returns the number of vertices in an incidence list.

igraph_integer_t igraph_inclist_size(const igraph_inclist_t *il);

Arguments: 

il:

The incidence list.

Returns: 

The number of vertices in the incidence list.

Time complexity: O(1).

10.2.5. igraph_inclist_clear — Removes all edges from an incidence list.

void igraph_inclist_clear(igraph_inclist_t *il);

Arguments: 

il:

The incidence list.

Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the incidence list.

10.3. Lazy adjacency list for vertices

10.3.1. igraph_lazy_adjlist_init — 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_multiple_t multiple);

Create a lazy adjacency list for vertices. This function only allocates some memory for storing the vectors of an adjacency list, but the neighbor vertices are not queried, only at the igraph_lazy_adjlist_get() calls. 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_integer_t igraph_lazy_adjlist_size(const igraph_lazy_adjlist_t *al);

Arguments: 

al:

The lazy adjacency list.

Returns: 

The number of vertices in the lazy adjacency list.

Time complexity: O(1).

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

al:

Pointer to an uninitialized incidence list.

mode:

Constant, it gives whether incoming edges (IGRAPH_IN), outgoing edges (IGRAPH_OUT) or both types of edges (IGRAPH_ALL) are considered. It is ignored for undirected graphs.

loops:

Specifies how to treat loop edges. IGRAPH_NO_LOOPS removes loop edges from the incidence list. IGRAPH_LOOPS_ONCE makes each loop edge appear only once in the incidence list of the corresponding vertex. IGRAPH_LOOPS_TWICE makes loop edges appear twice in the incidence list of the corresponding vertex, but only if the graph is undirected or mode is set to IGRAPH_ALL.

Returns: 

Error code.

Time complexity: O(|V|), the number of vertices, possibly. But it also depends on the underlying memory management.

10.4.2. igraph_lazy_inclist_destroy — Deallocates a lazy incidence list.

void igraph_lazy_inclist_destroy(igraph_lazy_inclist_t *il);

Frees all allocated memory for a lazy incidence list.

Arguments: 

al:

The incidence list to deallocate.

Time complexity: depends on memory management.

10.4.3. igraph_lazy_inclist_get — Query incident edges.

#define igraph_lazy_inclist_get(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_integer_t igraph_lazy_inclist_size(const igraph_lazy_inclist_t *il);

Arguments: 

il:

The lazy incidence list.

Returns: 

The number of vertices in the lazy incidence list.

Time complexity: O(1).

10.4.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_integer_t size);

The tree is initialized with a fixed number of elements. After initialization, the value corresponding to each element is zero.

Arguments: 

t:

The tree to initialize.

size:

The number of elements in the tree. 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_integer_t igraph_psumtree_size(const igraph_psumtree_t *t);

Arguments: 

t:

The tree object

Returns: 

The number of discrete items in the tree.

Time complexity: O(1).

11.4. igraph_psumtree_get — Retrieves the value corresponding to an item in the tree.

igraph_real_t igraph_psumtree_get(const igraph_psumtree_t *t, igraph_integer_t idx);

Arguments: 

t:

The tree to query.

idx:

The index of the item whose value is to be retrieved.

Returns: 

The value corresponding to the item with the given index.

Time complexity: O(1)

11.5. igraph_psumtree_sum — Returns the sum of the values of the leaves in the tree.

igraph_real_t igraph_psumtree_sum(const igraph_psumtree_t *t);

Arguments: 

t:

The tree object

Returns: 

The sum of the values of the leaves in the tree.

Time complexity: O(1).

11.6. igraph_psumtree_search — Finds an item in the tree, given a value.

igraph_error_t igraph_psumtree_search(const igraph_psumtree_t *t, igraph_integer_t *idx,
                           igraph_real_t search);

This function finds the item with the lowest index where it holds that the sum of all the items with a lower index is less than or equal to the given value and that the sum of all the items with a lower index plus the item itself is larger than the given value.

If you think about the partial prefix sum tree as a tool to sample from a discrete probability distribution, then calling this function repeatedly with uniformly distributed random numbers in the range 0 (inclusive) to the sum of all values in the tree (exclusive) will sample the items in the tree with a probability that is proportional to their associated values.

Arguments: 

t:

The tree to query.

idx:

The index of the item is returned here.

search:

The value to use for the search. 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_integer_t idx,
                           igraph_real_t new_value);

Arguments: 

t:

The tree to query.

idx:

The index of the item to update.

new_value:

The new value of the item.

Returns: 

Error code, IGRAPH_EINVAL if the new value is negative or NaN, IGRAPH_SUCCESS if the operation was successful.

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

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

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

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.

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

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.

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

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.

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(b)

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(b)

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: 

b:

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(a, b)

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: 

a:

The bitset

b:

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(a, b)

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: 

a:

The bitset

b:

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(a, b)

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: 

a:

The bitset

b:

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(nb)

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: 

nb:

The specified number of bits.

Time complexity: O(1).

12.4. Bitset operations

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

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.

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

src2:

A bitset

Time complexity: O(n/w).

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

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.

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

src2:

A bitset

Time complexity: O(n/w).

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

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.

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

src2:

A bitset

Time complexity: O(n/w).

12.4.4. igraph_bitset_not — Bitwise negation of a bitset.

void igraph_bitset_not(igraph_bitset_t *dest, const igraph_bitset_t *src);

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.

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

Time complexity: O(n/w).

12.4.5. igraph_bitset_popcount — The population count of the bitset.

igraph_integer_t igraph_bitset_popcount(const igraph_bitset_t *bitset);

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 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.6. igraph_bitset_countl_zero — The number of leading zeros in the bitset.

igraph_integer_t igraph_bitset_countl_zero(const igraph_bitset_t *bitset);

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 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.7. igraph_bitset_countl_one — The number of leading ones in the bitset.

igraph_integer_t igraph_bitset_countl_one(const igraph_bitset_t *bitset);

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 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.8. igraph_bitset_countr_zero — The number of trailing zeros in the bitset.

igraph_integer_t igraph_bitset_countr_zero(const igraph_bitset_t *bitset);

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 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.9. igraph_bitset_countr_one — The number of trailing ones in the bitset.

igraph_integer_t igraph_bitset_countr_one(const igraph_bitset_t *bitset);

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 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.5. Bitset properties

12.5.1. igraph_bitset_size — Returns the length of the bitset.

igraph_integer_t igraph_bitset_size(const igraph_bitset_t *bitset);

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.

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_integer_t igraph_bitset_capacity(const igraph_bitset_t *bitset);

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.

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: 

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

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.

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

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.

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