int igraph_vector_init(igraph_vector_t* v, int long 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: 

Returns: 

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

int igraph_vector_init_copy(igraph_vector_t *v,
                                       const igraph_real_t *data, long int length);

Arguments: 

Returns: 

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

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

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

Arguments: 

Returns: 

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

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

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

Arguments: 

Returns: 

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

void igraph_vector_destroy(igraph_vector_t* v);

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

Arguments: 

Time complexity: operating system dependent.

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: 

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

void igraph_vector_fill(igraph_vector_t* v, igraph_real_t e);

Sets each element of the vector to the supplied constant.

Arguments: 

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

#define VECTOR(v)

Usage:

 VECTOR(v)[0] 

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

 VECTOR(v)[10]=5; 

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

Arguments: 

Time complexity: O(1).

igraph_real_t igraph_vector_e(const igraph_vector_t* v, long int pos);

Arguments: 

Returns: 

See also: 

Time complexity: O(1).

igraph_real_t* igraph_vector_e_ptr(const igraph_vector_t* v, long int pos);

Arguments: 

Returns: 

See also: 

Time complexity: O(1).

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

Arguments: 

See also: 

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: 

Returns: 

Time complexity: O(1).

const igraph_vector_t*igraph_vector_view(const igraph_vector_t *v,
        const igraph_real_t *data,
        long int 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: 

Returns: 

Time complexity: O(1)

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

The C array should have sufficient length.

Arguments: 

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

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

Returns: 

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

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

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

Arguments: 

Returns: 

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

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

Arguments: 

Returns: 

Time complexity: O(1).

int igraph_vector_swap_elements(igraph_vector_t *v,
        long int i, long int j);

Note that currently no range checking is performed.

Arguments: 

Returns: 

Time complexity: O(1).

int igraph_vector_reverse(igraph_vector_t *v);

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

Arguments: 

Returns: 

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

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

Returns: 

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

References:

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

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

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

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

#include <igraph.h>

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

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

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

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

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

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

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

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

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

    return ret == 0 ? 0 : 6;
}

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: 

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

void igraph_vector_scale(igraph_vector_t *v, igraph_real_t by);

Arguments: 

Returns: 

Added in version 0.2.

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

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

Returns: 

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

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

Returns: 

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

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

Returns: 

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

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

Returns: 

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

int igraph_vector_floor(const igraph_vector_t *from, igraph_vector_long_t *to);

Flooring means rounding down to the nearest integer.

Arguments: 

Returns: 

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

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

Arguments: 

Returns: 

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

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

Arguments: 

Returns: 

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

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

Arguments: 

Returns: 

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

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

Arguments: 

Returns: 

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

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

Arguments: 

Returns: 

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

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

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

This function is typically used together with igraph_vector_ptr_sort().

Arguments: 

Returns: 

See also: 

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

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

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

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

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

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

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

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

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

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

    igraph_destroy(&graph);

    return 0;
}

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

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

This function is typically used together with igraph_vector_ptr_sort().

Arguments: 

Returns: 

See also: 

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

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

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

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

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

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

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

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

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

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

    igraph_destroy(&graph);

    return 0;
}

igraph_real_t igraph_vector_min(const igraph_vector_t* v);

The vector must be non-empty.

Arguments: 

Returns: 

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

igraph_real_t igraph_vector_max(const igraph_vector_t* v);

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

Arguments: 

Returns: 

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

long int igraph_vector_which_min(const igraph_vector_t* v);

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

Arguments: 

Returns: 

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

long int igraph_vector_which_max(const igraph_vector_t* v);

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

Arguments: 

Returns: 

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

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

Returns: 

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

int igraph_vector_which_minmax(const igraph_vector_t *v,
        long int *which_min, long int *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: 

Returns: 

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

igraph_bool_t igraph_vector_empty(const igraph_vector_t* v);

Arguments: 

Returns: 

Time complexity: O(1).

long int igraph_vector_size(const igraph_vector_t* v);

Arguments: 

Returns: 

Time complexity: O(1).

long int 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: 

Returns: 

See also: 

Time complexity: O(1).

igraph_real_t igraph_vector_sum(const igraph_vector_t *v);

For the empty vector 0.0 is returned.

Arguments: 

Returns: 

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

igraph_real_t igraph_vector_prod(const igraph_vector_t *v);

For the empty vector one (1) is returned.

Arguments: 

Returns: 

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

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

interval.

Arguments: 

Returns: 

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

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: 

Returns: 

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

int igraph_vector_order(const igraph_vector_t* v,
                        const igraph_vector_t *v2,
                        igraph_vector_t* res, igraph_real_t nodes);

The smallest element will have order zero, the second smallest order one, etc.

Arguments: 

Returns: 

Time complexity: O()

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

Arguments: 

Returns: 

igraph_bool_t igraph_vector_is_any_nan(const igraph_vector_t *v);

Arguments: 

Returns: 

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

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: 

Returns: 

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

igraph_bool_t igraph_vector_search(const igraph_vector_t *v,
        long int from, igraph_real_t what,
        long int *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: 

Returns: 

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

igraph_bool_t igraph_vector_binsearch(const igraph_vector_t *v,
        igraph_real_t what, long int *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: 

Returns: 

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

igraph_bool_t igraph_vector_binsearch_slice(const igraph_vector_t *v,
        igraph_real_t what, long int *pos,
        long int start, long int 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: 

Returns: 

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

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

It is assumed that the vector is sorted.

Arguments: 

Returns: 

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

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: 

Time complexity: O(1).

int igraph_vector_reserve(igraph_vector_t* v, long int size);

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

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

Arguments: 

Returns: 

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

int igraph_vector_resize(igraph_vector_t* v, long int newsize);

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

Arguments: 

Returns: 

See also: 

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.

int igraph_vector_resize_min(igraph_vector_t*v);

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

Arguments: 

Returns: 

See also: 

Time complexity: operating system dependent.

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

Returns: 

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

igraph_real_t igraph_vector_pop_back(igraph_vector_t* v);

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

Arguments: 

Returns: 

Time complexity: O(1).

int igraph_vector_insert(igraph_vector_t *v, long int 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: 

void igraph_vector_remove(igraph_vector_t *v, long int elem);

Note that this function does not do range checking.

Arguments: 

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

void igraph_vector_remove_section(igraph_vector_t *v,
        long int from, long int to);

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

Arguments: 

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

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: 

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

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: 

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

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

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

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

int igraph_vector_ptr_init(igraph_vector_ptr_t* v, int long 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: 

Returns: 

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

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

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

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

Arguments: 

Returns: 

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

void igraph_vector_ptr_destroy(igraph_vector_ptr_t* v);

The destructor for pointer vectors.

Arguments: 

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

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: 

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.

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: 

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

long int igraph_vector_ptr_size(const igraph_vector_ptr_t* v);

Arguments: 

Returns: 

Time complexity: O(1).

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: 

Time complexity: O(1).

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

Arguments: 

Returns: 

See also: 

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.

int igraph_vector_ptr_insert(igraph_vector_ptr_t* v, long int 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: 

void *igraph_vector_ptr_e(const igraph_vector_ptr_t* v, long int pos);

Arguments: 

Returns: 

Time complexity: O(1).

void igraph_vector_ptr_set(igraph_vector_ptr_t* v, long int pos, void* value);

Arguments: 

Time complexity: O(1).

int igraph_vector_ptr_resize(igraph_vector_ptr_t* v, long int 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: 

Returns: 

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.

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: 

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

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

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

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

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

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

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

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

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

    igraph_destroy(&graph);

    return 0;
}

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: 

Time complexity: O(1).

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: 

Time complexity: O(1).

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

int igraph_matrix_init(igraph_matrix_t *m, long int nrow, long int 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: 

Returns: 

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

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

Creates a matrix object by copying from an existing matrix.

Arguments: 

Returns: 

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

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: 

Time complexity: operating system dependent.

void igraph_matrix_null(igraph_matrix_t *m);

Arguments: 

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

void igraph_matrix_fill(igraph_matrix_t *m, igraph_real_t e);

Set the matrix to a constant matrix.

Arguments: 

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

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: 

Returns: 

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

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

Returns: 

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

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

The contents of the two matrices will be swapped.

Arguments: 

Returns: 

Time complexity: O(1).

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

Time complexity: O(1).

igraph_real_t igraph_matrix_e(const igraph_matrix_t *m,
                                long int row, long int 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: 

Returns: 

Time complexity: O(1).

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

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

Arguments: 

Returns: 

Time complexity: O(1).

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

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

Arguments: 

Time complexity: O(1).

int igraph_matrix_get_row(const igraph_matrix_t *m,
                                     igraph_vector_t *res, long int index);

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

Arguments: 

Returns: 

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

int igraph_matrix_get_col(const igraph_matrix_t *m,
                                     igraph_vector_t *res,
                                     long int index);

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

Arguments: 

Returns: 

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

int igraph_matrix_set_row(igraph_matrix_t *m,
                                     const igraph_vector_t *v, long int 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: 

Returns: 

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

int igraph_matrix_set_col(igraph_matrix_t *m,
                                     const igraph_vector_t *v, long int 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: 

Returns: 

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

int igraph_matrix_swap_rows(igraph_matrix_t *m,
                                       long int i, long int j);

Swap two rows in the matrix.

Arguments: 

Returns: 

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

int igraph_matrix_swap_cols(igraph_matrix_t *m,
                                       long int i, long int j);

Swap two columns in the matrix.

Arguments: 

Returns: 

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

int igraph_matrix_select_rows(const igraph_matrix_t *m,
        igraph_matrix_t *res,
        const igraph_vector_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: 

Returns: 

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

int igraph_matrix_select_cols(const igraph_matrix_t *m,
        igraph_matrix_t *res,
        const igraph_vector_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: 

Returns: 

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

int igraph_matrix_select_rows_cols(const igraph_matrix_t *m,
        igraph_matrix_t *res,
        const igraph_vector_t *rows,
        const igraph_vector_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: 

Returns: 

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

void igraph_matrix_add_constant(igraph_matrix_t *m, igraph_real_t plus);

Arguments: 

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

void igraph_matrix_scale(igraph_matrix_t *m, igraph_real_t by);

Arguments: 

Added in version 0.2.

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

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

Returns: 

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

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

Returns: 

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

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

Returns: 

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

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

Returns: 

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

igraph_real_t igraph_matrix_sum(const igraph_matrix_t *m);

Returns the sum of the elements of a matrix.

Arguments: 

Returns: 

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

igraph_real_t igraph_matrix_prod(const igraph_matrix_t *m);

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

Arguments: 

Returns: 

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

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

Calculate the sum of the elements in each row.

Arguments: 

Returns: 

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

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

Calculate the sum of the elements in each column.

Arguments: 

Returns: 

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

int igraph_matrix_transpose(igraph_matrix_t *m);

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

Arguments: