For using the igraph C library
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 is currently defined for igraph_real_t, long int (long), char (char), igraph_bool_t (bool). The default is igraph_real_t.
Matrix is currently defined for igraph_real_t, long int (long), char (char), igraph_bool_t (bool). The default is igraph_real_t.
Array3 is currently defined for igraph_real_t, long int (long), char (char), igraph_bool_t (bool). The default is igraph_real_t.
Stack is currently defined for igraph_real_t, long int (long), char (char), igraph_bool_t (bool). The default is igraph_real_t.
Dqueue is currently defined for igraph_real_t, long int (long), char (char), igraph_bool_t (bool). The default is igraph_real_t.
Heap is currently defined for igraph_real_t, long int (long), char (char). In addition both maximum and minimum heaps are available. The default is the igraph_real_t maximum heap.
The name of the base element (in parentheses) is added to the function names, except for the default type.
Some examples:
igraph_vector_t is a vector of
igraph_real_t elements. Its functions are
igraph_vector_init
,
igraph_vector_destroy
,
igraph_vector_sort
, etc.
igraph_vector_bool_t is a vector of
igraph_bool_t elements, initialize it with
igraph_vector_bool_init
, destroy it with
igraph_vector_bool_destroy
, etc.
igraph_heap_t is a maximum heap with
igraph_real_t elements. The corresponding functions are
igraph_heap_init
,
igraph_heap_pop
, etc.
igraph_heap_min_t is a minimum heap with
igraph_real_t elements. The corresponding functions are
called igraph_heap_min_init
,
igraph_heap_min_pop
, etc.
igraph_heap_long_t is a maximum heap with long
int elements. Its function have the
igraph_heap_long_
prefix.
igraph_heap_min_long_t is a minimum heap containing
long int elements. Its functions have the
igraph_heap_min_long_
prefix.
Note that the VECTOR and the MATRIX macros can be used on all vector and matrix types.
The igraph_vector_t data type is a simple and efficient interface to arrays containing numbers. It is something similar as (but much simpler than) the vector template in the C++ standard library.
Vectors are used extensively in igraph, all functions which expect or return a list of numbers use igraph_vector_t to achieve this.
The igraph_vector_t type usually uses O(n) space to store n elements. Sometimes it uses more, this is because vectors can shrink, but even if they shrink, the current implementation does not free a single bit of memory.
The elements in an igraph_vector_t object 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.
igraph_vector_init
— Initializes a vector object (constructor).igraph_vector_init_copy
— Initializes a vector from an ordinary C array (constructor).igraph_vector_init_seq
— Initializes a vector with a sequence.igraph_vector_copy
— Initializes a vector from another vector object (constructor).igraph_vector_destroy
— Destroys a vector object.igraph_vector_t objects have to be initialized before using
them, this is analogous to calling a constructor on them. There are a
number of igraph_vector_t constructors, for your
convenience. igraph_vector_init()
is the basic constructor, it
creates a vector of the given length, filled with zeros.
igraph_vector_copy()
creates a new identical copy
of an already existing and initialized vector. igraph_vector_init_copy()
creates a vector by copying a regular C array.
igraph_vector_init_seq()
creates a vector containing a regular
sequence with increment one.
igraph_vector_view()
is a special constructor, it allows you to
handle a regular C array as a vector without copying
its elements.
If a igraph_vector_t object is not needed any more, it
should be destroyed to free its allocated memory by calling the
igraph_vector_t destructor, igraph_vector_destroy()
.
Note that vectors created by igraph_vector_view()
are special,
you mustn't call igraph_vector_destroy()
on these.
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:
|
Pointer to a not yet initialized vector object. |
|
The size of the vector. |
Returns:
error code:
|
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:
|
Pointer to an uninitialized vector object. |
|
A regular C array. |
|
The length of the C array. |
Returns:
Error code:
|
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:
|
Pointer to an uninitialized vector object. |
|
The lower limit in the sequence (inclusive). |
|
The upper limit in the sequence (inclusive). |
Returns:
Error code:
|
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:
|
Pointer to a not yet initialized vector object. |
|
The original vector object to copy. |
Returns:
Error code:
|
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:
|
Pointer to the (previously initialized) vector object to destroy. |
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:
|
The vector object. |
Time complexity: O(n), the size of the vector.
VECTOR
— Accessing an element of a vector.igraph_vector_e
— Access an element of a vector.igraph_vector_e_ptr
— Get the address of an element of a vectorigraph_vector_set
— Assignment to an element of a vector.igraph_vector_tail
— Returns the last element in a vector.The simplest way to access an element of a vector is to use the
VECTOR
macro. This macro can be used both for querying and setting
igraph_vector_t elements. If you need a function, igraph_vector_e()
queries and igraph_vector_set()
sets an element of a
vector. igraph_vector_e_ptr()
returns the address of an element.
igraph_vector_tail()
returns the last element of a non-empty
vector. There is no igraph_vector_head()
function
however, as it is easy to write VECTOR(v)[0]
instead.
#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:
|
The vector object. |
Time complexity: O(1).
igraph_real_t igraph_vector_e(const igraph_vector_t* v, long int pos);
Arguments:
|
The igraph_vector_t object. |
|
The position of the element, the index of the first element is zero. |
Returns:
The desired element. |
See also:
|
Time complexity: O(1).
igraph_real_t* igraph_vector_e_ptr(const igraph_vector_t* v, long int pos);
Arguments:
|
The igraph_vector_t object. |
|
The position of the element, the position of the first element is zero. |
Returns:
Pointer to the desired element. |
See also:
|
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:
|
Pointer to an uninitialized igraph_vector_t object. |
|
Pointer, the C array. It may not be |
|
The length of the C array. |
Returns:
Pointer to the vector object, the same as the
|
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:
|
The vector object. |
|
The C array. |
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:
|
The vector to update. |
|
The vector to update from. |
Returns:
Error code. |
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:
|
The vector to append to. |
|
The vector to append, it is kept unchanged. |
Returns:
Error code. |
Time complexity: O(n), the number of elements in the new vector.
int igraph_vector_swap_elements(igraph_vector_t *v, long int i, long int j);
Note that currently no range checking is performed.
Arguments:
|
The input vector. |
|
Index of the first element. |
|
Index of the second element (may be the same as the first one). |
Returns:
Error code, currently always |
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:
|
The input vector. |
Returns:
Error code, currently always |
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:
|
The vector object. |
Returns:
Error code, currently always |
Time complexity: O(n), n is the number of elements in the vector.
References:
|
R. A. Fisher and F. Yates. Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd, 6th edition, 1963, page 37. |
|
D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 3rd edition, 1998, page 145. |
Example 7.1. File examples/simple/igraph_fisher_yates_shuffle.c
/* -*- mode: C -*- */ /* Test suite for the Fisher-Yates shuffle. Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #define R_INTEGER(a,b) (igraph_rng_get_integer(igraph_rng_default(), (a), (b))) #define R_UNIF(a,b) (igraph_rng_get_unif(igraph_rng_default(), (a), (b))) int main() { igraph_real_t d; igraph_vector_t u, v; int ret; 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; }
igraph_vector_add_constant
— Add a constant to the vector.igraph_vector_scale
— Multiply all elements of a vector by a constantigraph_vector_add
— Add two vectors.igraph_vector_sub
— Subtract a vector from another one.igraph_vector_mul
— Multiply two vectors.igraph_vector_div
— Divide a vector by another one.igraph_vector_floor
— Transform a real vector to a long vector by flooring each element.
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:
|
The input vector. |
|
The constant to add. |
Time complexity: O(n), the number of elements.
void igraph_vector_scale(igraph_vector_t *v, igraph_real_t by);
Arguments:
|
The vector. |
|
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.
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:
|
The first vector, the result will be stored here. |
|
The second vector, its contents will be unchanged. |
Returns:
Error code. |
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:
|
The first vector, to subtract from. The result is stored here. |
|
The vector to subtract, it will be unchanged. |
Returns:
Error code. |
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:
|
The first vector, the result will be stored here. |
|
The second vector, it is left unchanged. |
Returns:
Error code. |
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:
|
The dividend. The result is also stored here. |
|
The divisor, it is left unchanged. |
Returns:
Error code. |
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:
|
The original real vector object. |
|
Pointer to an initialized long vector. The result will be stored here. |
Returns:
Error code:
|
Time complexity: O(n), where n is the number of elements in the vector.
igraph_vector_all_e
— Are all elements equal?igraph_vector_all_l
— Are all elements less?igraph_vector_all_g
— Are all elements greater?igraph_vector_all_le
— Are all elements less or equal?igraph_vector_all_ge
— Are all elements greater or equal?igraph_vector_lex_cmp
— Lexicographical comparison of two vectors.igraph_vector_colex_cmp
— Colexicographical comparison of two vectors.
igraph_bool_t igraph_vector_all_e(const igraph_vector_t *lhs, const igraph_vector_t *rhs);
Arguments:
|
The first vector. |
|
The second vector. |
Returns:
Positive integer (=true) if the elements in the |
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:
|
The first vector. |
|
The second vector. |
Returns:
Positive integer (=true) if the elements in the |
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:
|
The first vector. |
|
The second vector. |
Returns:
Positive integer (=true) if the elements in the |
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:
|
The first vector. |
|
The second vector. |
Returns:
Positive integer (=true) if the elements in the |
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:
|
The first vector. |
|
The second vector. |
Returns:
Positive integer (=true) if the elements in the |
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:
|
Pointer to a pointer to the first vector (interpreted as an |
|
Pointer to a pointer to the second vector (interpreted as an |
Returns:
-1 if |
See also:
|
Time complexity: O(n), the number of elements in the smaller vector.
Example 7.2. File examples/simple/igraph_vector_ptr_sort.c
#include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_vector_ptr_t cliques; 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:
|
Pointer to a pointer to the first vector (interpreted as an |
|
Pointer to a pointer to the second vector (interpreted as an |
Returns:
-1 if |
See also:
|
Time complexity: O(n), the number of elements in the smaller vector.
Example 7.3. File examples/simple/igraph_vector_ptr_sort.c
#include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_vector_ptr_t cliques; 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_vector_min
— Smallest element of a vector.igraph_vector_max
— Largest element of a vector.igraph_vector_which_min
— Index of the smallest element.igraph_vector_which_max
— Gives the index of the maximum element of the vector.igraph_vector_minmax
— Minimum and maximum elements of a vector.igraph_vector_which_minmax
— Index of the minimum and maximum elements
igraph_real_t igraph_vector_min(const igraph_vector_t* v);
The vector must be non-empty.
Arguments:
|
The input vector. |
Returns:
The smallest element of |
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:
|
The vector object. |
Returns:
The maximum element of |
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:
|
The input vector. |
Returns:
Index of the smallest element. |
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:
|
The vector object. |
Returns:
The index of the first maximum element. |
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:
|
The input vector. It must contain at least one element. |
|
Pointer to a base type variable, the minimum is stored here. |
|
Pointer to a base type variable, the maximum is stored here. |
Returns:
Error code. |
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:
|
The input vector. It must contain at least one element. |
|
The index of the minimum element will be stored here. |
|
The index of the maximum element will be stored here. |
Returns:
Error code. |
Time complexity: O(n), the number of elements.
igraph_vector_empty
— Decides whether the size of the vector is zero.igraph_vector_size
— Returns the size (=length) of the vector.igraph_vector_capacity
— Returns the allocated capacity of the vectorigraph_vector_sum
— Calculates the sum of the elements in the vector.igraph_vector_prod
— Calculates the product of the elements in the vector.igraph_vector_isininterval
— Checks if all elements of a vector are in the givenigraph_vector_maxdifference
— The maximum absolute difference of m1
and m2
igraph_vector_order
— Calculate the order of the elements in a vector.igraph_vector_is_nan
— Check for each element if it is NaN.igraph_vector_is_any_nan
— Check if any element is NaN.
igraph_bool_t igraph_vector_empty(const igraph_vector_t* v);
Arguments:
|
The vector object. |
Returns:
Non-zero number (true) if the size of the vector is zero and zero (false) otherwise. |
Time complexity: O(1).
long int igraph_vector_size(const igraph_vector_t* v);
Arguments:
|
The vector object |
Returns:
The size of the vector. |
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:
|
Pointer to the (previously initialized) vector object to query. |
Returns:
The allocated capacity. |
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:
|
The vector object. |
Returns:
The sum of the elements. |
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:
|
The vector object. |
Returns:
The product of the elements. |
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:
|
The vector object. |
|
The lower limit of the interval (inclusive). |
|
The higher limit of the interval (inclusive). |
Returns:
True (positive integer) if all vector elements are in the
interval, false (zero) otherwise. If any element is NaN, it will
return |
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:
|
The first vector. |
|
The second vector. |
Returns:
The maximum absolute difference of |
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:
|
The original igraph_vector_t object. |
|
A secondary key, another igraph_vector_t object. |
|
An initialized igraph_vector_t object, it will be
resized to match the size of |
|
Hint, the largest element in |
Returns:
Error code:
|
Time complexity: O()
int igraph_vector_is_nan(const igraph_vector_t *v, igraph_vector_bool_t *is_nan);
Arguments:
|
The igraph_vector_t object to check. |
|
The resulting boolean vector indicating for each element whether it is NaN or not. |
Returns:
Error code,
|
igraph_vector_contains
— Linear search in a vector.igraph_vector_search
— Search from a given positionigraph_vector_binsearch
— Finds an element by binary searching a sorted vector.igraph_vector_binsearch_slice
— Finds an element by binary searching a sorted slice of a vector.igraph_vector_binsearch2
— Binary search, without returning the index.
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:
|
The input vector. |
|
The element to look for. |
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:
|
The input vector. |
|
The index to start searching from. No range checking is performed. |
|
The element to find. |
|
If not |
Returns:
Boolean, |
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:
|
The igraph_vector_t object. |
|
The element to search for. |
|
Pointer to a long int. This is set to the
position of an instance of |
Returns:
Positive integer (true) if |
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:
|
The igraph_vector_t object. |
|
The element to search for. |
|
Pointer to a long int. This is set to the position of an
instance of |
|
The start position of the slice to search (inclusive). |
|
The end position of the slice to search (exclusive). |
Returns:
Positive integer (true) if |
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:
|
The igraph_vector_t object. |
|
The element to search for. |
Returns:
Positive integer (true) if |
Time complexity: O(log(n)),
n is the number of elements in
v
.
igraph_vector_clear
— Removes all elements from a vector.igraph_vector_reserve
— Reserves memory for a vector.igraph_vector_resize
— Resize the vector.igraph_vector_resize_min
— Deallocate the unused memory of a vector.igraph_vector_push_back
— Appends one element to a vector.igraph_vector_pop_back
— Removes and returns the last element of a vector.igraph_vector_insert
— Inserts a single element into a vector.igraph_vector_remove
— Removes a single element from a vector.igraph_vector_remove_section
— Deletes a section 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:
|
The vector object. |
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:
|
The vector object. |
|
The new allocated size of the vector. |
Returns:
Error code:
|
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:
|
The vector object |
|
The new size of the vector. |
Returns:
Error code,
|
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:
|
Pointer to an initialized vector. |
Returns:
Error code. |
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:
|
The vector object. |
|
The element to append to the vector. |
Returns:
Error code:
|
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:
|
The vector object. |
Returns:
The removed last element. |
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:
|
The vector object. |
|
The position where the new element is to be inserted. |
|
The new element to be inserted. |
void igraph_vector_remove(igraph_vector_t *v, long int elem);
Note that this function does not do range checking.
Arguments:
|
The vector object. |
|
The position of the element to remove. |
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:
|
The vector object. |
|
The position of the first element to remove. |
|
The position of the first element not to remove. |
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:
|
Pointer to an initialized vector object. |
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:
|
the first vector |
|
the second vector |
|
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.
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:
|
the first vector |
|
the second vector |
|
the result vector |
igraph_vector_ptr_init
— Initialize a pointer vector (constructor).igraph_vector_ptr_copy
— Copy a pointer vector (constructor).igraph_vector_ptr_destroy
— Destroys a pointer vector.igraph_vector_ptr_free_all
— Frees all the elements of a pointer vector.igraph_vector_ptr_destroy_all
— Frees all the elements and destroys the pointer vector.igraph_vector_ptr_size
— Gives the number of elements in the pointer vector.igraph_vector_ptr_clear
— Removes all elements from a pointer vector.igraph_vector_ptr_push_back
— Appends an element to the back of a pointer vector.igraph_vector_ptr_insert
— Inserts a single element into a pointer vector.igraph_vector_ptr_e
— Access an element of a pointer vector.igraph_vector_ptr_set
— Assign to an element of a pointer vector.igraph_vector_ptr_resize
— Resizes a pointer vector.igraph_vector_ptr_sort
— Sorts the pointer vector based on an external comparison function.igraph_vector_ptr_get_item_destructor
— Gets the current item destructor for this pointer vector.igraph_vector_ptr_set_item_destructor
— Sets the item destructor for this pointer vector.IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR
— Sets the item destructor for this pointer vector (macro version).The igraph_vector_ptr_t data type is very similar to
the igraph_vector_t
type, but it stores generic pointers instead of
real numbers.
This type has the same space complexity as igraph_vector_t
, and most implemented operations work the same way
as for igraph_vector_t
.
This type is mostly used to pass to or receive from a set of
graphs to some igraph functions, such as igraph_decompose()
, which decomposes a graph to connected
components.
The same VECTOR
macro used for ordinary vectors can be
used for pointer vectors as well, please note that a typeless
generic pointer will be provided by this macro and you may need to
cast it to a specific pointer before starting to work with it.
Pointer vectors may have an associated item destructor function
which takes a pointer and returns nothing. The item destructor will
be called on each item in the pointer vector when it is destroyed by
igraph_vector_ptr_destroy()
or igraph_vector_ptr_destroy_all()
,
or when its elements are freed by igraph_vector_ptr_free_all()
.
Note that the semantics of an item destructor does not coincide with
C++ destructors; for instance, when a pointer vector is resized to a
smaller size, the extra items will not be destroyed automatically!
Nevertheless, item destructors may become handy in many cases; for
instance, a vector of graphs generated by igraph_decompose()
can
be destroyed with a single call to igraph_vector_ptr_destroy_all()
if the item destructor is set to igraph_destroy()
.
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:
|
Pointer to an uninitialized igraph_vector_ptr_t object, to be created. |
|
Integer, the size of the pointer vector. |
Returns:
Error code:
|
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:
|
Pointer to an uninitialized pointer vector object. |
|
A pointer vector object. |
Returns:
Error code:
|
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:
|
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).
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:
|
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.
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:
|
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).
long int igraph_vector_ptr_size(const igraph_vector_ptr_t* v);
Arguments:
|
The pointer vector object. |
Returns:
The size of the object, i.e. the number of pointers stored. |
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:
|
The pointer vector to clear. |
Time complexity: O(1).
int igraph_vector_ptr_push_back(igraph_vector_ptr_t* v, void* e);
Arguments:
|
The pointer vector. |
|
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.
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:
|
The pointer vector object. |
|
The position where the new element is inserted. |
|
The inserted element |
void *igraph_vector_ptr_e(const igraph_vector_ptr_t* v, long int pos);
Arguments:
|
Pointer to a pointer vector. |
|
The index of the pointer to return. |
Returns:
The pointer at |
Time complexity: O(1).
void igraph_vector_ptr_set(igraph_vector_ptr_t* v, long int pos, void* value);
Arguments:
|
Pointer to a pointer vector. |
|
The index of the pointer to update. |
|
The new pointer to set in the vector. |
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:
|
A pointer vector. |
|
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.
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:
|
The pointer vector to be sorted. |
|
A qsort-compatible comparison function. It must take pointers to the
elements of the pointer vector. For example, if the pointer vector contains
|
Example 7.4. File examples/simple/igraph_vector_ptr_sort.c
#include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_vector_ptr_t cliques; 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:
The current item destructor. |
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:
The old item destructor. |
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
*
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.
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:
|
Pointer to a not yet initialized matrix object to be initialized. |
|
The number of rows in the matrix. |
|
The number of columns in the matrix. |
Returns:
Error code. |
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:
|
Pointer to an uninitialized matrix object. |
|
The initialized matrix object to copy. |
Returns:
Error code, |
Time complexity: O(n), the number of elements in the matrix.
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:
|
Pointer to an initialized matrix object. |
|
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.
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:
|
The result matrix. |
|
The matrix to replicate; it is left unchanged. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements.
#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:
|
The matrix object. |
|
The index of the row, starting with zero. |
|
The index of the column, starting with zero. |
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:
|
The input matrix. |
|
The row index. |
|
The column index. |
Returns:
The element in the given row and column. |
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:
|
The input matrix. |
|
The row index. |
|
The column index. |
Returns:
Pointer to the element in the given row and column. |
Time complexity: O(1).
igraph_matrix_get_row
— Extract a row.igraph_matrix_get_col
— Select a column.igraph_matrix_set_row
— Set a row from a vector.igraph_matrix_set_col
— Set a column from a vector.igraph_matrix_swap_rows
— Swap two rows.igraph_matrix_swap_cols
— Swap two columns.igraph_matrix_select_rows
— Select some rows of a matrix.igraph_matrix_select_cols
— Select some columns of a matrix.igraph_matrix_select_rows_cols
— Select some rows and columns of a matrix.
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:
|
The input matrix. |
|
Pointer to an initialized vector; it will be resized if needed. |
|
The index of the row to select. |
Returns:
Error code. |
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:
|
The input matrix. |
|
The result will we stored in this vector. It should be initialized and will be resized as needed. |
|
The index of the column to select. |
Returns:
Error code. |
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:
|
The input matrix. |
|
The vector containing the new elements of the row. |
|
Index of the row to set. |
Returns:
Error code. |
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:
|
The input matrix. |
|
The vector containing the new elements of the column. |
|
Index of the column to set. |
Returns:
Error code. |
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:
|
The input matrix. |
|
The index of the first row. |
|
The index of the second row. |
Returns:
Error code. |
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:
|
The input matrix. |
|
The index of the first column. |
|
The index of the second column. |
Returns:
Error code. |
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:
|
The input matrix. |
|
The result matrix. It should be initialized and will be resized as needed. |
|
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.
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:
|
The input matrix. |
|
The result matrix. It should be initialized and will be resized as needed. |
|
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.
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:
|
The input matrix. |
|
The result matrix. It should be initialized and will be resized as needed. |
|
Vector; it contains the row indices (starting with zero) to extract. Note that no range checking is performed. |
|
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.
igraph_matrix_add_constant
— Add a constant to every element.igraph_matrix_scale
— Multiplies each element of the matrix by a constant.igraph_matrix_add
— Add two matrices.igraph_matrix_sub
— Difference of two matrices.igraph_matrix_mul_elements
— Elementwise multiplication.igraph_matrix_div_elements
— Elementwise division.igraph_matrix_sum
— Sum of elements.igraph_matrix_prod
— Product of the elements.igraph_matrix_rowsum
— Rowwise sum.igraph_matrix_colsum
— Columnwise sum.igraph_matrix_transpose
— Transpose a matrix.
void igraph_matrix_add_constant(igraph_matrix_t *m, igraph_real_t plus);
Arguments:
|
The input matrix. |
|
The constant to add. |
Time complexity: O(mn), the number of elements.
void igraph_matrix_scale(igraph_matrix_t *m, igraph_real_t by);
Arguments:
|
The matrix. |
|
The constant. |
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:
|
The first matrix; the result will be stored here. |
|
The second matrix; it is left unchanged. |
Returns:
Error code. |
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:
|
The first matrix; the result is stored here. |
|
The second matrix; it is left unchanged. |
Returns:
Error code. |
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:
|
The first matrix; the result is stored here. |
|
The second matrix; it is left unchanged. |
Returns:
Error code. |
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:
|
The dividend. The result is store here. |
|
The divisor. It is left unchanged. |
Returns:
Error code. |
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:
|
The input matrix. |
Returns:
The sum of the elements. |
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:
|
The input matrix. |
Returns:
The product of the elements. |
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:
|
The input matrix. |
|
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.
int igraph_matrix_colsum(const igraph_matrix_t *m, igraph_vector_t *res);
Calculate the sum of the elements in each column.
Arguments:
|
The input matrix. |
|
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.
igraph_bool_t igraph_matrix_all_e(const igraph_matrix_t *lhs, const igraph_matrix_t *rhs);
Arguments:
|
The first matrix. |
|
The second matrix. |
Returns:
Positive integer (=true) if the elements in the |
Time complexity: O(nm), the size of the matrices.
igraph_bool_t igraph_matrix_all_l(const igraph_matrix_t *lhs, const igraph_matrix_t *rhs);
Arguments:
|
The first matrix. |
|
The second matrix. |
Returns:
Positive integer (=true) if the elements in the |
Time complexity: O(nm), the size of the matrices.
igraph_bool_t igraph_matrix_all_g(const igraph_matrix_t *lhs, const igraph_matrix_t *rhs);
Arguments:
|
The first matrix. |
|
The second matrix. |
Returns:
Positive integer (=true) if the elements in the |
Time complexity: O(nm), the size of the matrices.
igraph_bool_t igraph_matrix_all_le(const igraph_matrix_t *lhs, const igraph_matrix_t *rhs);
Arguments:
|
The first matrix. |
|
The second matrix. |
Returns:
Positive integer (=true) if the elements in the |
Time complexity: O(nm), the size of the matrices.
igraph_bool_t igraph_matrix_all_ge(const igraph_matrix_t *lhs, const igraph_matrix_t *rhs);
Arguments:
|
The first matrix. |
|
The second matrix. |
Returns:
Positive integer (=true) if the elements in the |
Time complexity: O(nm), the size of the matrices.
int 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:
|
The upper matrix; the result is also stored here. |
|
The lower matrix. It is left unchanged. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements in the newly created matrix.
int 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:
|
The left matrix; the result is stored here too. |
|
The right matrix. It is left unchanged. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements on the new matrix.
igraph_matrix_min
— Smallest element of a matrix.igraph_matrix_max
— Largest element of a matrix.igraph_matrix_which_min
— Indices of the smallest element.igraph_matrix_which_max
— Indices of the largest element.igraph_matrix_minmax
— Minimum and maximum elements of a matrix.igraph_matrix_which_minmax
— Indices of the minimum and maximum elements
igraph_real_t igraph_matrix_min(const igraph_matrix_t *m);
The matrix must be non-empty.
Arguments:
|
The input matrix. |
Returns:
The smallest element of |
Time complexity: O(mn), the number of elements in the matrix.
igraph_real_t igraph_matrix_max(const igraph_matrix_t *m);
If the matrix is empty, an arbitrary number is returned.
Arguments:
|
The matrix object. |
Returns:
The maximum element of |
Added in version 0.2.
Time complexity: O(mn), the number of elements in the matrix.
int igraph_matrix_which_min(const igraph_matrix_t *m, long int *i, long int *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:
|
The matrix. |
|
Pointer to a long int. The row index of the minimum is stored here. |
|
Pointer to a long int. The column index of the minimum is stored here. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements.
int igraph_matrix_which_max(const igraph_matrix_t *m, long int *i, long int *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:
|
The matrix. |
|
Pointer to a long int. The row index of the maximum is stored here. |
|
Pointer to a long int. The column index of the maximum is stored here. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements.
int 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:
|
The input matrix. It must contain at least one element. |
|
Pointer to a base type variable. The minimum is stored here. |
|
Pointer to a base type variable. The maximum is stored here. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements.
int igraph_matrix_which_minmax(const igraph_matrix_t *m, long int *imin, long int *jmin, long int *imax, long int *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:
|
The input matrix. |
|
Pointer to a long int, the row index of the minimum is stored here. |
|
Pointer to a long int, the column index of the minimum is stored here. |
|
Pointer to a long int, the row index of the maximum is stored here. |
|
Pointer to a long int, the column index of the maximum is stored here. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements.
igraph_matrix_empty
— Check for an empty matrix.igraph_matrix_isnull
— Check for a null matrix.igraph_matrix_size
— The number of elements in a matrix.igraph_matrix_capacity
— Returns the number of elements allocated for a matrix.igraph_matrix_nrow
— The number of rows in a matrix.igraph_matrix_ncol
— The number of columns in a matrix.igraph_matrix_is_symmetric
— Check for symmetric matrix.igraph_matrix_maxdifference
— Maximum absolute difference between two matrices.
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:
|
The input matrix. |
Returns:
Boolean, |
Time complexity: O(1).
igraph_bool_t igraph_matrix_isnull(const igraph_matrix_t *m);
Checks whether all elements are zero.
Arguments:
|
The input matrix. |
Returns:
Boolean, |
Time complexity: O(mn), the number of elements.
long int igraph_matrix_size(const igraph_matrix_t *m);
Arguments:
|
Pointer to an initialized matrix object. |
Returns:
The size of the matrix. |
Time complexity: O(1).
long int 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:
|
Pointer to the (previously initialized) matrix object to query. |
Returns:
The allocated capacity. |
See also:
Time complexity: O(1).
long int igraph_matrix_nrow(const igraph_matrix_t *m);
Arguments:
|
Pointer to an initialized matrix object. |
Returns:
The number of rows in the matrix. |
Time complexity: O(1).
long int igraph_matrix_ncol(const igraph_matrix_t *m);
Arguments:
|
Pointer to an initialized matrix object. |
Returns:
The number of columns in the matrix. |
Time complexity: O(1).
igraph_bool_t igraph_matrix_is_symmetric(const igraph_matrix_t *m);
A non-square matrix is not symmetric by definition.
Arguments:
|
The input matrix. |
Returns:
Boolean, |
Time complexity: O(mn), the number of elements. O(1) for non-square 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:
|
The first matrix. |
|
The second matrix. |
Returns:
The element with the largest absolute value in |
Time complexity: O(mn), the elements in the smaller matrix.
igraph_bool_t igraph_matrix_contains(const igraph_matrix_t *m, igraph_real_t e);
Search for the given element in the matrix.
Arguments:
|
The input matrix. |
|
The element to search for. |
Returns:
Boolean, |
Time complexity: O(mn), the number of elements.
igraph_bool_t igraph_matrix_search(const igraph_matrix_t *m, long int from, igraph_real_t what, long int *pos, long int *row, long int *col);
Search for an element in a matrix and start the search from the given position. The search is performed columnwise.
Arguments:
|
The input matrix. |
|
The position to search from, the positions are enumerated columnwise. |
|
The element to search for. |
|
Pointer to a long int. If the element is found, then this is set to the position of its first appearance. |
|
Pointer to a long int. If the element is found, then this is set to its row index. |
|
Pointer to a long int. If the element is found, then this is set to its column index. |
Returns:
Boolean, |
Time complexity: O(mn), the number of elements.
igraph_matrix_resize
— Resizes a matrix.igraph_matrix_resize_min
— Deallocates unused memory for a matrix.igraph_matrix_add_rows
— Adds rows to a matrix.igraph_matrix_add_cols
— Adds columns to a matrix.igraph_matrix_remove_row
— Remove a row.igraph_matrix_remove_col
— Removes a column from a matrix.
int igraph_matrix_resize(igraph_matrix_t *m, long int nrow, long int 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:
|
Pointer to an already initialized matrix object. |
|
The number of rows in the resized matrix. |
|
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.
int igraph_matrix_resize_min(igraph_matrix_t *m);
Note that this function might fail if there is not enough memory available.
Also note, that this function leaves the matrix intact, i.e. it does not destroy any of the elements. However, usually it involves copying the matrix in memory.
Arguments:
|
Pointer to an initialized matrix. |
Returns:
Error code. |
See also:
Time complexity: operating system dependent.
int igraph_matrix_add_rows(igraph_matrix_t *m, long int n);
Arguments:
|
The matrix object. |
|
The number of rows to add. |
Returns:
Error code, |
Time complexity: linear with the number of elements of the new, resized matrix.
int igraph_matrix_add_cols(igraph_matrix_t *m, long int n);
Arguments:
|
The matrix object. |
|
The number of columns to add. |
Returns:
Error code, |
Time complexity: linear with the number of elements of the new, resized matrix.
int igraph_matrix_remove_row(igraph_matrix_t *m, long int row);
A row is removed from the matrix.
Arguments:
|
The input matrix. |
|
The index of the row to remove. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements in the matrix.
The igraph_spmatrix_t type stores a sparse matrix with the assumption that the number of nonzero elements in the matrix scales linearly with the row or column count of the matrix (so most of the elements are zero). Of course it can store an arbitrary real matrix, but if most of the elements are nonzero, one should use igraph_matrix_t instead.
The elements are stored in column compressed format, so the elements in the same column are stored adjacent in the computer's memory. The storage requirement for a sparse matrix is O(n) where n is the number of nonzero elements. Actually it can be a bit larger, see the documentation of the vector type for an explanation.
int igraph_spmatrix_init(igraph_spmatrix_t *m, long int nrow, long int ncol);
Every sparse matrix needs to be initialized before using it, this is done
by calling this function. A matrix has to be destroyed if it is not
needed any more, see igraph_spmatrix_destroy()
.
Arguments:
|
Pointer to a not yet initialized sparse matrix object to be initialized. |
|
The number of rows in the matrix. |
|
The number of columns in the matrix. |
Returns:
Error code. |
Time complexity: operating system dependent.
int igraph_spmatrix_copy(igraph_spmatrix_t *to, const igraph_spmatrix_t *from);
Creates a sparse matrix object by copying another one.
Arguments:
|
Pointer to an uninitialized sparse matrix object. |
|
The initialized sparse matrix object to copy. |
Returns:
Error code, |
Time complexity: O(n), the number of elements in the matrix.
igraph_real_t igraph_spmatrix_e(const igraph_spmatrix_t *m, long int row, long int col);
Note that there are no range checks right now.
Arguments:
|
The matrix object. |
|
The index of the row, starting with zero. |
|
The index of the column, starting with zero. |
Time complexity: O(log n), where n is the number of nonzero elements in the requested column.
int igraph_spmatrix_set(igraph_spmatrix_t *m, long int row, long int col, igraph_real_t value);
Note that there are no range checks right now.
Arguments:
|
The matrix object. |
|
The index of the row, starting with zero. |
|
The index of the column, starting with zero. |
|
The new value. |
Time complexity: O(log n), where n is the number of nonzero elements in the requested column.
int igraph_spmatrix_add_e(igraph_spmatrix_t *m, long int row, long int col, igraph_real_t value);
Note that there are no range checks right now. This is implemented to avoid
double lookup of a given element in the matrix by using igraph_spmatrix_e()
and igraph_spmatrix_set()
consecutively.
Arguments:
|
The matrix object. |
|
The index of the row, starting with zero. |
|
The index of the column, starting with zero. |
|
The value to add. |
Time complexity: O(log n), where n is the number of nonzero elements in the requested column.
igraph_spmatrix_iter_create
— Creates a sparse matrix iterator corresponding to the given matrix.igraph_spmatrix_iter_reset
— Resets a sparse matrix iterator.igraph_spmatrix_iter_next
— Moves a sparse matrix iterator to the next nonzero element.igraph_spmatrix_iter_end
— Checks whether there are more elements in the iterator.igraph_spmatrix_iter_destroy
— Frees the memory used by the iterator.The igraph_spmatrix_iter_t type represents an iterator that can be used to step over the non-zero elements of a sparse matrix in columnwise order efficiently. In general, you shouldn't modify the elements of the matrix while iterating over it; doing so will probably invalidate the iterator, but there are no checks to prevent you from doing this.
To access the row index of the current element of the iterator, use its
ri
field. Similarly, the ci
field stores the column index of the current
element and the value
field stores the value of the element.
int igraph_spmatrix_iter_create(igraph_spmatrix_iter_t *mit, const igraph_spmatrix_t *m);
Arguments:
|
pointer to the matrix iterator being initialized |
|
pointer to the matrix we will be iterating over |
Returns:
Error code. The current implementation is always successful. |
Time complexity: O(1).
int igraph_spmatrix_iter_reset(igraph_spmatrix_iter_t *mit);
After resetting, the iterator will point to the first nonzero element (if any).
Arguments:
|
pointer to the matrix iterator being reset |
Returns:
Error code. The current implementation is always successful. |
Time complexity: O(1).
int igraph_spmatrix_iter_next(igraph_spmatrix_iter_t *mit);
You should call this function only if igraph_spmatrix_iter_end()
returns FALSE (0).
Arguments:
|
pointer to the matrix iterator being moved |
Returns:
Error code. The current implementation is always successful. |
Time complexity: O(1).
igraph_bool_t igraph_spmatrix_iter_end(igraph_spmatrix_iter_t *mit);
You should call this function before calling igraph_spmatrix_iter_next()
to make sure you have more elements in the iterator.
Arguments:
|
pointer to the matrix iterator being checked |
Returns:
TRUE (1) if there are more elements in the iterator, FALSE (0) otherwise. |
Time complexity: O(1).
void igraph_spmatrix_iter_destroy(igraph_spmatrix_iter_t *mit);
The current implementation does not allocate any memory upon
creation, so this function does nothing. However, since there is
no guarantee that future implementations will not allocate any
memory in igraph_spmatrix_iter_create()
, you are still
required to call this function whenever you are done with the
iterator.
Arguments:
|
pointer to the matrix iterator being destroyed |
Time complexity: O(1).
igraph_spmatrix_size
— The number of elements in a sparse matrix.igraph_spmatrix_nrow
— The number of rows in a sparse matrix.igraph_spmatrix_ncol
— The number of columns in a sparse matrix.igraph_spmatrix_count_nonzero
— The number of non-zero elements in a sparse matrix.igraph_spmatrix_max
— Returns the maximum element of a matrix.igraph_spmatrix_rowsums
— Calculates the row sums of the matrix.igraph_spmatrix_colsums
— Calculates the column sums of the matrix.
long int igraph_spmatrix_size(const igraph_spmatrix_t *m);
Arguments:
|
Pointer to an initialized sparse matrix object. |
Returns:
The size of the matrix. |
Time complexity: O(1).
long int igraph_spmatrix_nrow(const igraph_spmatrix_t *m);
Arguments:
|
Pointer to an initialized sparse matrix object. |
Returns:
The number of rows in the matrix. |
Time complexity: O(1).
long int igraph_spmatrix_ncol(const igraph_spmatrix_t *m);
Arguments:
|
Pointer to an initialized sparse matrix object. |
Returns:
The number of columns in the sparse matrix. |
Time complexity: O(1).
long int igraph_spmatrix_count_nonzero(const igraph_spmatrix_t *m);
Arguments:
|
Pointer to an initialized sparse matrix object. |
Returns:
The size of the matrix. |
Time complexity: O(1).
igraph_real_t igraph_spmatrix_max(const igraph_spmatrix_t *m, igraph_real_t *ridx, igraph_real_t *cidx);
If the matrix is empty, zero is returned.
Arguments:
|
the matrix object. |
|
the row index of the maximum element if not |
|
the column index of the maximum element if not |
Time complexity: O(n), the number of nonzero elements in the matrix.
int igraph_spmatrix_rowsums(const igraph_spmatrix_t *m, igraph_vector_t *res);
Arguments:
|
The matrix. |
|
An initialized |
Time complexity: O(n), the number of nonzero elements in the matrix.
void igraph_spmatrix_scale(igraph_spmatrix_t *m, igraph_real_t by);
Arguments:
|
The matrix. |
|
The constant. |
Time complexity: O(n), the number of elements in the matrix.
int igraph_spmatrix_add_rows(igraph_spmatrix_t *m, long int n);
Arguments:
|
The sparse matrix object. |
|
The number of rows to add. |
Returns:
Error code. |
Time complexity: O(1).
int igraph_spmatrix_add_cols(igraph_spmatrix_t *m, long int n);
Arguments:
|
The sparse matrix object. |
|
The number of columns to add. |
Returns:
Error code. |
Time complexity: O(1).
int igraph_spmatrix_resize(igraph_spmatrix_t *m, long int nrow, long int ncol);
This function resizes a sparse matrix by adding more elements to it. The matrix retains its data even after resizing it, except for the data which lies outside the new boundaries (if the new size is smaller).
Arguments:
|
Pointer to an already initialized sparse matrix object. |
|
The number of rows in the resized matrix. |
|
The number of columns in the resized matrix. |
Returns:
Error code. |
Time complexity: O(n). n is the number of elements in the old matrix.
int igraph_spmatrix_print(const igraph_spmatrix_t* matrix);
Prints a sparse matrix to the standard output. Only the non-zero entries are printed.
Returns:
Error code. |
Time complexity: O(n), the number of non-zero elements.
The igraph_sparsemat_t
data type stores sparse matrices,
i.e. matrices in which the majority of the elements are zero.
The data type is essentially a wrapper to some of the functions in the CXSparse library, by Tim Davis, see http://faculty.cse.tamu.edu/davis/suitesparse.html
Matrices can be stored in two formats: triplet and
column-compressed. The triplet format is intended for sparse matrix
initialization, as it is easy to add new (non-zero) elements to
it. Most of the computations are done on sparse matrices in
column-compressed format, after the user has converted the triplet
matrix to column-compressed, via igraph_sparsemat_compress()
.
Both formats are dynamic, in the sense that new elements can be added to them, possibly resulting the allocation of more memory.
Row and column indices follow the C convention and are zero-based.
Example 7.5. File examples/simple/igraph_sparsemat.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> int main() { igraph_sparsemat_t A, B, C, D; igraph_t G, H; igraph_vector_t vect; long int i; /* Create, compress, destroy */ igraph_sparsemat_init(&A, 100, 20, 50); igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); /* Convert a ring graph to a matrix, print it, compress, print again */ #define VC 10 igraph_ring(&G, VC, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1); igraph_get_sparsemat(&G, &A); igraph_destroy(&G); igraph_sparsemat_compress(&A, &B); igraph_sparsemat_print(&A, stdout); igraph_sparsemat_print(&B, stdout); /* Basic query, nrow, ncol, type, is_triplet, is_cc */ if (igraph_sparsemat_nrow(&A) != VC || igraph_sparsemat_ncol(&A) != VC || igraph_sparsemat_nrow(&B) != VC || igraph_sparsemat_ncol(&B) != VC) { return 1; } if (!igraph_sparsemat_is_triplet(&A)) { return 2; } if (!igraph_sparsemat_is_cc(&B)) { return 3; } if (igraph_sparsemat_type(&A) != IGRAPH_SPARSEMAT_TRIPLET) { return 4; } if (igraph_sparsemat_type(&B) != IGRAPH_SPARSEMAT_CC) { return 5; } igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); #undef VC printf("------------------------\n"); /* Create unit matrices */ igraph_sparsemat_eye(&A, /*n=*/ 5, /*nzmax=*/ 5, /*value=*/ 1.0, /*compress=*/ 0); igraph_sparsemat_eye(&B, /*n=*/ 5, /*nzmax=*/ 5, /*value=*/ 1.0, /*compress=*/ 1); igraph_sparsemat_print(&A, stdout); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); printf("------------------------\n"); /* Create diagonal matrices */ igraph_vector_init(&vect, 5); for (i = 0; i < 5; i++) { VECTOR(vect)[i] = i; } igraph_sparsemat_diag(&A, /*nzmax=*/ 5, /*values=*/ &vect, /*compress=*/ 0); igraph_sparsemat_diag(&B, /*nzmax=*/ 5, /*values=*/ &vect, /*compress=*/ 1); igraph_vector_destroy(&vect); igraph_sparsemat_print(&A, stdout); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); printf("------------------------\n"); /* Transpose matrices */ igraph_tree(&G, 10, /*children=*/ 2, IGRAPH_TREE_OUT); igraph_get_sparsemat(&G, &A); igraph_destroy(&G); igraph_sparsemat_compress(&A, &B); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_transpose(&B, &C, /*values=*/ 1); igraph_sparsemat_print(&C, stdout); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&C); printf("------------------------\n"); /* Add duplicate elements */ igraph_sparsemat_init(&A, 10, 10, /*nzmax=*/ 20); for (i = 1; i < 10; i++) { igraph_sparsemat_entry(&A, 0, i, 1.0); } for (i = 1; i < 10; i++) { igraph_sparsemat_entry(&A, 0, i, 1.0); } igraph_sparsemat_print(&A, stdout); igraph_sparsemat_compress(&A, &B); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_dupl(&B); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); printf("------------------------\n"); /* Drop zero elements */ igraph_sparsemat_init(&A, 10, 10, /*nzmax=*/ 20); igraph_sparsemat_entry(&A, 7, 3, 0.0); for (i = 1; i < 10; i++) { igraph_sparsemat_entry(&A, 0, i, 1.0); igraph_sparsemat_entry(&A, 0, i, 0.0); } igraph_sparsemat_entry(&A, 0, 0, 0.0); igraph_sparsemat_print(&A, stdout); igraph_sparsemat_compress(&A, &B); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_dropzeros(&B); igraph_sparsemat_print(&B, stdout); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); printf("------------------------\n"); /* Add two matrices */ igraph_star(&G, 10, IGRAPH_STAR_OUT, /*center=*/ 0); igraph_ring(&H, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1); igraph_get_sparsemat(&G, &A); igraph_get_sparsemat(&H, &B); igraph_destroy(&G); igraph_destroy(&H); igraph_sparsemat_compress(&A, &C); igraph_sparsemat_compress(&B, &D); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); igraph_sparsemat_add(&C, &D, /*alpha=*/ 1.0, /*beta=*/ 2.0, &A); igraph_sparsemat_destroy(&C); igraph_sparsemat_destroy(&D); igraph_sparsemat_print(&A, stdout); igraph_sparsemat_destroy(&A); return 0; }
Example 7.6. File examples/simple/igraph_sparsemat3.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #define NCOMPLEX /* to make it compile with MSVC on Windows */ #include <cs.h> #include <igraph.h> int permute(const igraph_matrix_t *M, const igraph_vector_int_t *p, const igraph_vector_int_t *q, igraph_matrix_t *res) { long int nrow = igraph_vector_int_size(p); long int ncol = igraph_vector_int_size(q); long int i, j; igraph_matrix_resize(res, nrow, ncol); for (i = 0; i < nrow; i++) { for (j = 0; j < ncol; j++) { int ii = VECTOR(*p)[i]; int jj = VECTOR(*q)[j]; MATRIX(*res, i, j) = MATRIX(*M, ii, jj); } } return 0; } int permute_rows(const igraph_matrix_t *M, const igraph_vector_int_t *p, igraph_matrix_t *res) { long int nrow = igraph_vector_int_size(p); long int ncol = igraph_matrix_ncol(M); long int i, j; igraph_matrix_resize(res, nrow, ncol); for (i = 0; i < nrow; i++) { for (j = 0; j < ncol; j++) { int ii = VECTOR(*p)[i]; MATRIX(*res, i, j) = MATRIX(*M, ii, j); } } return 0; } int permute_cols(const igraph_matrix_t *M, const igraph_vector_int_t *q, igraph_matrix_t *res) { long int nrow = igraph_matrix_nrow(M); long int ncol = igraph_vector_int_size(q); long int i, j; igraph_matrix_resize(res, nrow, ncol); for (i = 0; i < nrow; i++) { for (j = 0; j < ncol; j++) { int jj = VECTOR(*q)[j]; MATRIX(*res, i, j) = MATRIX(*M, i, jj); } } return 0; } int random_permutation(igraph_vector_int_t *vec) { /* We just do size(vec) * 2 swaps */ long int one, two, i, n = igraph_vector_int_size(vec); int tmp; for (i = 0; i < 2 * n; i++) { one = RNG_INTEGER(0, n - 1); two = RNG_INTEGER(0, n - 1); tmp = VECTOR(*vec)[one]; VECTOR(*vec)[one] = VECTOR(*vec)[two]; VECTOR(*vec)[two] = tmp; } return 0; } igraph_bool_t check_same(const igraph_sparsemat_t *A, const igraph_matrix_t *M) { long int nrow = igraph_sparsemat_nrow(A); long int ncol = igraph_sparsemat_ncol(A); long int j, p, nzero = 0; if (nrow != igraph_matrix_nrow(M) || ncol != igraph_matrix_ncol(M)) { return 0; } for (j = 0; j < A->cs->n; j++) { for (p = A->cs->p[j]; p < A->cs->p[j + 1]; p++) { long int to = A->cs->i[p]; igraph_real_t value = A->cs->x[p]; if (value != MATRIX(*M, to, j)) { return 0; } nzero += 1; } } for (j = 0; j < nrow; j++) { for (p = 0; p < ncol; p++) { if (MATRIX(*M, j, p) != 0) { nzero -= 1; } } } return nzero == 0; } int main() { igraph_sparsemat_t A, B; igraph_matrix_t M, N; igraph_vector_int_t p, q; long int i; /* Permutation of a matrix */ #define NROW 10 #define NCOL 5 #define EDGES NROW*NCOL/3 igraph_matrix_init(&M, NROW, NCOL); igraph_sparsemat_init(&A, NROW, NCOL, EDGES); for (i = 0; i < EDGES; i++) { long int r = RNG_INTEGER(0, NROW - 1); long int c = RNG_INTEGER(0, NCOL - 1); igraph_real_t value = RNG_INTEGER(1, 5); MATRIX(M, r, c) = MATRIX(M, r, c) + value; igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_vector_int_init_seq(&p, 0, NROW - 1); igraph_vector_int_init_seq(&q, 0, NCOL - 1); /* Identity */ igraph_matrix_init(&N, 0, 0); permute(&M, &p, &q, &N); igraph_sparsemat_permute(&B, &p, &q, &A); igraph_sparsemat_dupl(&A); if (! check_same(&A, &N)) { return 1; } /* Random permutation */ random_permutation(&p); random_permutation(&q); permute(&M, &p, &q, &N); igraph_sparsemat_destroy(&A); igraph_sparsemat_permute(&B, &p, &q, &A); igraph_sparsemat_dupl(&A); if (! check_same(&A, &N)) { return 2; } igraph_vector_int_destroy(&p); igraph_vector_int_destroy(&q); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); igraph_matrix_destroy(&M); igraph_matrix_destroy(&N); #undef NROW #undef NCOL #undef EDGES /* Indexing */ #define NROW 10 #define NCOL 5 #define EDGES NROW*NCOL/3 #define I_NROW 6 #define I_NCOL 3 igraph_matrix_init(&M, NROW, NCOL); igraph_sparsemat_init(&A, NROW, NCOL, EDGES); for (i = 0; i < EDGES; i++) { long int r = RNG_INTEGER(0, NROW - 1); long int c = RNG_INTEGER(0, NCOL - 1); igraph_real_t value = RNG_INTEGER(1, 5); MATRIX(M, r, c) = MATRIX(M, r, c) + value; igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_vector_int_init(&p, I_NROW); igraph_vector_int_init(&q, I_NCOL); for (i = 0; i < I_NROW; i++) { VECTOR(p)[i] = RNG_INTEGER(0, I_NROW - 1); } for (i = 0; i < I_NCOL; i++) { VECTOR(p)[i] = RNG_INTEGER(0, I_NCOL - 1); } igraph_matrix_init(&N, 0, 0); permute(&M, &p, &q, &N); igraph_sparsemat_index(&B, &p, &q, &A, 0); if (! check_same(&A, &N)) { return 3; } /* A single element */ igraph_vector_int_resize(&p, 1); igraph_vector_int_resize(&q, 1); for (i = 0; i < 100; i++) { igraph_real_t value; VECTOR(p)[0] = RNG_INTEGER(0, NROW - 1); VECTOR(q)[0] = RNG_INTEGER(0, NCOL - 1); igraph_sparsemat_index(&B, &p, &q, /*res=*/ 0, &value); if (value != MATRIX(M, VECTOR(p)[0], VECTOR(q)[0])) { return 4; } } igraph_sparsemat_destroy(&A); for (i = 0; i < 100; i++) { igraph_real_t value; VECTOR(p)[0] = RNG_INTEGER(0, NROW - 1); VECTOR(q)[0] = RNG_INTEGER(0, NCOL - 1); igraph_sparsemat_index(&B, &p, &q, /*res=*/ &A, &value); igraph_sparsemat_destroy(&A); if (value != MATRIX(M, VECTOR(p)[0], VECTOR(q)[0])) { return 4; } } igraph_vector_int_destroy(&p); igraph_vector_int_destroy(&q); igraph_sparsemat_destroy(&B); igraph_matrix_destroy(&M); igraph_matrix_destroy(&N); /* Indexing only the rows or the columns */ igraph_matrix_init(&M, NROW, NCOL); igraph_sparsemat_init(&A, NROW, NCOL, EDGES); for (i = 0; i < EDGES; i++) { long int r = RNG_INTEGER(0, NROW - 1); long int c = RNG_INTEGER(0, NCOL - 1); igraph_real_t value = RNG_INTEGER(1, 5); MATRIX(M, r, c) = MATRIX(M, r, c) + value; igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_vector_int_init(&p, I_NROW); igraph_vector_int_init(&q, I_NCOL); for (i = 0; i < I_NROW; i++) { VECTOR(p)[i] = RNG_INTEGER(0, I_NROW - 1); } for (i = 0; i < I_NCOL; i++) { VECTOR(p)[i] = RNG_INTEGER(0, I_NCOL - 1); } igraph_matrix_init(&N, 0, 0); permute_rows(&M, &p, &N); igraph_sparsemat_index(&B, &p, 0, &A, 0); if (! check_same(&A, &N)) { return 5; } permute_cols(&M, &q, &N); igraph_sparsemat_destroy(&A); igraph_sparsemat_index(&B, 0, &q, &A, 0); if (! check_same(&A, &N)) { return 6; } igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); igraph_vector_int_destroy(&p); igraph_vector_int_destroy(&q); igraph_matrix_destroy(&M); igraph_matrix_destroy(&N); return 0; }
Example 7.7. File examples/simple/igraph_sparsemat4.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #define NCOMPLEX /* to make it compile with MSVC on Windows */ #include <cs.h> #include <igraph.h> igraph_bool_t check_solution(const igraph_sparsemat_t *A, const igraph_vector_t *x, const igraph_vector_t *b) { long int dim = igraph_vector_size(x); igraph_vector_t res; int j, p; igraph_real_t min, max; igraph_vector_copy(&res, b); for (j = 0; j < dim; j++) { for (p = A->cs->p[j]; p < A->cs->p[j + 1]; p++) { long int from = A->cs->i[p]; igraph_real_t value = A->cs->x[p]; VECTOR(res)[from] -= VECTOR(*x)[j] * value; } } igraph_vector_minmax(&res, &min, &max); igraph_vector_destroy(&res); return fabs(min) < 1e-15 && fabs(max) < 1e-15; } int main() { igraph_sparsemat_t A, B, C; igraph_vector_t b, x; long int i; /* lsolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM); for (i = 0; i < DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3)); } for (i = 0; i < EDGES; i++) { long int r = RNG_INTEGER(0, DIM - 1); long int 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++) { long int r = RNG_INTEGER(0, DIM - 1); long int c = RNG_INTEGER(0, r); igraph_real_t value = RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_vector_init(&b, DIM); for (i = 0; i < DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1, 10); } igraph_vector_init(&x, DIM); igraph_sparsemat_ltsolve(&B, &b, &x); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); if (! check_solution(&A, &x, &b)) { return 2; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); #undef DIM #undef EDGES /* usolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM); for (i = 0; i < DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3)); } for (i = 0; i < EDGES; i++) { long int r = RNG_INTEGER(0, DIM - 1); long int c = RNG_INTEGER(0, r); igraph_real_t value = RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); igraph_vector_init(&b, DIM); for (i = 0; i < DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1, 10); } igraph_vector_init(&x, DIM); igraph_sparsemat_usolve(&A, &b, &x); if (! check_solution(&A, &x, &b)) { return 3; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); #undef DIM #undef EDGES /* utsolve */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM); for (i = 0; i < DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3)); } for (i = 0; i < EDGES; i++) { long int r = RNG_INTEGER(0, DIM - 1); long int c = RNG_INTEGER(0, r); igraph_real_t value = RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, r, c, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); igraph_sparsemat_destroy(&B); igraph_vector_init(&b, DIM); for (i = 0; i < DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1, 10); } igraph_vector_init(&x, DIM); igraph_sparsemat_utsolve(&A, &b, &x); igraph_sparsemat_transpose(&A, &B, /*values=*/ 1); if (! check_solution(&B, &x, &b)) { return 4; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); igraph_sparsemat_destroy(&A); #undef DIM #undef EDGES /* cholsol */ /* We need a positive definite matrix, so we create a full-rank matrix first and then calculate A'A, which will be positive definite. */ #define DIM 10 #define EDGES (DIM*DIM/6) igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM); for (i = 0; i < DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3)); } for (i = 0; i < EDGES; i++) { long int from = RNG_INTEGER(0, DIM - 1); long int to = RNG_INTEGER(0, DIM - 1); igraph_real_t value = RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, from, to, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_sparsemat_transpose(&B, &A, /*values=*/ 1); igraph_sparsemat_multiply(&A, &B, &C); igraph_sparsemat_destroy(&A); igraph_sparsemat_destroy(&B); igraph_vector_init(&b, DIM); for (i = 0; i < DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1, 10); } igraph_vector_init(&x, DIM); igraph_sparsemat_cholsol(&C, &b, &x, /*order=*/ 0); if (! check_solution(&C, &x, &b)) { return 5; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&C); #undef DIM #undef EDGES /* lusol */ #define DIM 10 #define EDGES (DIM*DIM/4) igraph_sparsemat_init(&A, DIM, DIM, EDGES + DIM); for (i = 0; i < DIM; i++) { igraph_sparsemat_entry(&A, i, i, RNG_INTEGER(1, 3)); } for (i = 0; i < EDGES; i++) { long int from = RNG_INTEGER(0, DIM - 1); long int to = RNG_INTEGER(0, DIM - 1); igraph_real_t value = RNG_INTEGER(1, 5); igraph_sparsemat_entry(&A, from, to, value); } igraph_sparsemat_compress(&A, &B); igraph_sparsemat_destroy(&A); igraph_sparsemat_dupl(&B); igraph_vector_init(&b, DIM); for (i = 0; i < DIM; i++) { VECTOR(b)[i] = RNG_INTEGER(1, 10); } igraph_vector_init(&x, DIM); igraph_sparsemat_lusol(&B, &b, &x, /*order=*/ 0, /*tol=*/ 1e-10); if (! check_solution(&B, &x, &b)) { return 6; } igraph_vector_destroy(&b); igraph_vector_destroy(&x); igraph_sparsemat_destroy(&B); #undef DIM #undef EDGES return 0; }
Example 7.8. File examples/simple/igraph_sparsemat6.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> int main() { igraph_matrix_t mat, mat2, mat3; igraph_sparsemat_t spmat, spmat2; int i; igraph_rng_seed(igraph_rng_default(), 42); #define NROW 10 #define NCOL 7 #define NUM_NONZEROS 15 igraph_matrix_init(&mat, NROW, NCOL); for (i = 0; i < NUM_NONZEROS; i++) { int r = igraph_rng_get_integer(igraph_rng_default(), 0, NROW - 1); int c = igraph_rng_get_integer(igraph_rng_default(), 0, NCOL - 1); igraph_real_t val = igraph_rng_get_integer(igraph_rng_default(), 1, 10); MATRIX(mat, r, c) = val; } igraph_matrix_as_sparsemat(&spmat, &mat, /*tol=*/ 1e-14); igraph_matrix_init(&mat2, 0, 0); igraph_sparsemat_as_matrix(&mat2, &spmat); if (!igraph_matrix_all_e(&mat, &mat2)) { return 1; } igraph_sparsemat_compress(&spmat, &spmat2); igraph_matrix_init(&mat3, 0, 0); igraph_sparsemat_as_matrix(&mat3, &spmat2); if (!igraph_matrix_all_e(&mat, &mat3)) { return 2; } igraph_matrix_destroy(&mat); igraph_matrix_destroy(&mat2); igraph_matrix_destroy(&mat3); igraph_sparsemat_destroy(&spmat); igraph_sparsemat_destroy(&spmat2); return 0; }
Example 7.9. File examples/simple/igraph_sparsemat7.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #define DIM1 10 #define DIM2 5 #define INT(a) (igraph_rng_get_integer(igraph_rng_default(), 0, (a))) int main() { igraph_matrix_t mat; igraph_sparsemat_t spmat, spmat2; int i; igraph_real_t m1, m2; igraph_rng_seed(igraph_rng_default(), 42); igraph_sparsemat_init(&spmat, DIM1, DIM2, 20); igraph_sparsemat_entry(&spmat, 1, 2, -1.0); igraph_sparsemat_entry(&spmat, 3, 2, 10.0); for (i = 0; i < 10; i++) { igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0); } igraph_sparsemat_entry(&spmat, 1, 2, -1.0); igraph_sparsemat_entry(&spmat, 3, 2, 10.0); igraph_sparsemat_compress(&spmat, &spmat2); igraph_matrix_init(&mat, 0, 0); igraph_sparsemat_as_matrix(&mat, &spmat2); m1 = igraph_sparsemat_min(&spmat2); m2 = igraph_matrix_min(&mat); if (m1 != m2) { printf("%f %f\n", m1, m2); return 1; } m1 = igraph_sparsemat_max(&spmat2); m2 = igraph_matrix_max(&mat); if (m1 != m2) { printf("%f %f\n", m1, m2); return 2; } igraph_sparsemat_minmax(&spmat2, &m1, &m2); if (m1 != igraph_matrix_min(&mat)) { return 3; } if (m2 != igraph_matrix_max(&mat)) { return 4; } igraph_matrix_destroy(&mat); igraph_sparsemat_destroy(&spmat); igraph_sparsemat_destroy(&spmat2); return 0; }
Example 7.10. File examples/simple/igraph_sparsemat8.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #define DIM1 10 #define DIM2 5 #define INT(a) (igraph_rng_get_integer(igraph_rng_default(), 0, (a))) int main() { igraph_matrix_t mat, mat2; igraph_sparsemat_t spmat, spmat2; int i, j, nz1, nz2; igraph_vector_t sums1, sums2; igraph_rng_seed(igraph_rng_default(), 42); /* COPY */ igraph_sparsemat_init(&spmat, DIM1, DIM2, 20); for (i = 0; i < 10; i++) { igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0); } igraph_sparsemat_copy(&spmat2, &spmat); igraph_matrix_init(&mat, 0, 0); igraph_sparsemat_as_matrix(&mat, &spmat); igraph_matrix_init(&mat2, 0, 0); igraph_sparsemat_as_matrix(&mat2, &spmat2); if (!igraph_matrix_all_e(&mat, &mat2)) { return 1; } igraph_matrix_destroy(&mat2); igraph_sparsemat_destroy(&spmat2); igraph_sparsemat_compress(&spmat, &spmat2); igraph_sparsemat_destroy(&spmat); igraph_sparsemat_copy(&spmat, &spmat2); igraph_matrix_init(&mat2, 0, 0); igraph_sparsemat_as_matrix(&mat2, &spmat); if (!igraph_matrix_all_e(&mat, &mat2)) { return 2; } igraph_sparsemat_destroy(&spmat); igraph_sparsemat_destroy(&spmat2); igraph_matrix_destroy(&mat); igraph_matrix_destroy(&mat2); /* COLSUMS, ROWSUMS */ igraph_sparsemat_init(&spmat, DIM1, DIM2, 20); for (i = 0; i < 10; i++) { igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0); } igraph_sparsemat_compress(&spmat, &spmat2); igraph_matrix_init(&mat, 0, 0); igraph_sparsemat_as_matrix(&mat, &spmat); igraph_vector_init(&sums1, 0); igraph_vector_init(&sums2, 0); igraph_sparsemat_colsums(&spmat, &sums1); igraph_matrix_colsum(&mat, &sums2); if (!igraph_vector_all_e(&sums1, &sums2)) { return 3; } igraph_sparsemat_colsums(&spmat2, &sums1); if (!igraph_vector_all_e(&sums1, &sums2)) { return 4; } igraph_sparsemat_rowsums(&spmat, &sums1); igraph_matrix_rowsum(&mat, &sums2); if (!igraph_vector_all_e(&sums1, &sums2)) { return 5; } igraph_sparsemat_rowsums(&spmat2, &sums1); if (!igraph_vector_all_e(&sums1, &sums2)) { return 6; } igraph_matrix_destroy(&mat); igraph_sparsemat_destroy(&spmat); igraph_sparsemat_destroy(&spmat2); igraph_vector_destroy(&sums1); igraph_vector_destroy(&sums2); /* COUNT_NONZERO, COUNT_NONZEROTOL */ igraph_sparsemat_init(&spmat, DIM1, DIM2, 20); igraph_sparsemat_entry(&spmat, 1, 2, 1.0); igraph_sparsemat_entry(&spmat, 1, 2, 1.0); igraph_sparsemat_entry(&spmat, 1, 3, 1e-12); for (i = 0; i < 10; i++) { igraph_sparsemat_entry(&spmat, INT(DIM1 - 1), INT(DIM2 - 1), 1.0); } igraph_sparsemat_compress(&spmat, &spmat2); igraph_matrix_init(&mat, 0, 0); igraph_sparsemat_as_matrix(&mat, &spmat2); nz1 = igraph_sparsemat_count_nonzero(&spmat2); for (nz2 = 0, i = 0; i < igraph_matrix_nrow(&mat); i++) { for (j = 0; j < igraph_matrix_ncol(&mat); j++) { if (MATRIX(mat, i, j) != 0) { nz2++; } } } if (nz1 != nz2) { printf("%i %i\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("%i %i\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; }
igraph_sparsemat_init
— Initializes a sparse matrix, in triplet format.igraph_sparsemat_copy
— Copies a sparse matrix.igraph_sparsemat_realloc
— Allocates more (or less) memory for a sparse matrix.igraph_sparsemat_destroy
— Deallocates memory used by a sparse matrix.igraph_sparsemat_eye
— Creates a sparse identity matrix.igraph_sparsemat_diag
— Creates a sparse diagonal matrix.igraph_sparsemat_view
— Initialize a sparse matrix and set all parameters.
int igraph_sparsemat_init(igraph_sparsemat_t *A, int rows, int cols, int 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:
|
Pointer to a not yet initialized sparse matrix. |
|
The number of rows in the matrix. |
|
The number of columns. |
|
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.
int igraph_sparsemat_copy(igraph_sparsemat_t *to, const igraph_sparsemat_t *from);
Create a sparse matrix object, by copying another one. The source matrix can be either in triplet or column-compressed format.
Exactly the same amount of memory will be allocated to the copy matrix, as it is currently for the original one.
Arguments:
|
Pointer to an uninitialized sparse matrix, the copy will be created here. |
|
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.
int igraph_sparsemat_realloc(igraph_sparsemat_t *A, int 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:
|
The sparse matrix, it can be in triplet or column-compressed format. |
|
The new maximum number of non-zero elements. |
Returns:
Error code. |
Time complexity: TODO.
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:
|
The sparse matrix to destroy. |
Time complexity: O(1).
int igraph_sparsemat_eye(igraph_sparsemat_t *A, int n, int nzmax, igraph_real_t value, igraph_bool_t compress);
Arguments:
|
An uninitialized sparse matrix, the result is stored here. |
|
The number of rows and number of columns in the matrix. |
|
The maximum number of non-zero elements, this essentially gives the amount of memory that will be allocated for matrix elements. |
|
The value to store in the diagonal. |
|
Whether to create a column-compressed matrix. If false, then a triplet matrix is created. |
Returns:
Error code. |
Time complexity: O(n).
int igraph_sparsemat_diag(igraph_sparsemat_t *A, int nzmax, const igraph_vector_t *values, igraph_bool_t compress);
Arguments:
|
An uninitialized sparse matrix, the result is stored here. |
|
The maximum number of non-zero elements, this essentially gives the amount of memory that will be allocated for matrix elements. |
|
The values to store in the diagonal, the size of the matrix defined by the length of this vector. |
|
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.
int igraph_sparsemat_view(igraph_sparsemat_t *A, int nzmax, int m, int n, int *p, int *i, double *x, int 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:
|
The non-initialized sparse matrix. |
|
The maximum number of entries, typically the actual number of entries. |
|
The number of matrix rows. |
|
The number of matrix columns. |
|
For a compressed matrix, this is the column pointer vector, and
must be of size |
|
The row vector. This should contain the row indices of the
elements in |
|
The values of the non-zero elements of the sparse matrix.
It must be of size |
|
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).
igraph_sparsemat_index
— Extracts a submatrix or a single element.igraph_sparsemat_nrow
— Number of rows.igraph_sparsemat_ncol
— Number of columns.igraph_sparsemat_type
— Type of a sparse matrix (triplet or column-compressed).igraph_sparsemat_is_triplet
— Is this sparse matrix in triplet format?igraph_sparsemat_is_cc
— Is this sparse matrix in column-compressed format?igraph_sparsemat_getelements_sorted
— Returns the sorted elements of a sparse matrix.igraph_sparsemat_min
— Minimum of a sparse matrix.igraph_sparsemat_max
— Maximum of a sparse matrix.igraph_sparsemat_minmax
— Minimum and maximum of a sparse matrix.igraph_sparsemat_count_nonzero
— Counts nonzero elements of a sparse matrix.igraph_sparsemat_count_nonzerotol
— Counts nonzero elements of a sparse matrix, ignoring elements close to zero.igraph_sparsemat_rowsums
— Row-wise sums.igraph_sparsemat_colsums
— Column-wise sums.igraph_sparsemat_nonzero_storage
— Returns number of stored entries of a sparse matrix.
int 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:
|
The input matrix, it must be in column-compressed format. |
|
An integer vector, or a null pointer. The selected row index or indices. A null pointer selects all rows. |
|
An integer vector, or a null pointer. The selected column index or indices. A null pointer selects all columns. |
|
Pointer to an uninitialized sparse matrix, or a null pointer. If not a null pointer, then the selected submatrix is stored here. |
|
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.
long int igraph_sparsemat_nrow(const igraph_sparsemat_t *A);
Arguments:
|
The input matrix, in triplet or column-compressed format. |
Returns:
The number of rows in the |
Time complexity: O(1).
long int igraph_sparsemat_ncol(const igraph_sparsemat_t *A);
Arguments:
|
The input matrix, in triplet or column-compressed format. |
Returns:
The number of columns in the |
Time complexity: O(1).
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:
|
The input matrix. |
Returns:
Either |
Time complexity: O(1).
igraph_bool_t igraph_sparsemat_is_triplet(const igraph_sparsemat_t *A);
Decides whether a sparse matrix is in triplet format.
Arguments:
|
The input matrix. |
Returns:
One if the input matrix is in triplet format, zero otherwise. |
Time complexity: O(1).
igraph_bool_t igraph_sparsemat_is_cc(const igraph_sparsemat_t *A);
Decides whether a sparse matrix is in column-compressed format.
Arguments:
|
The input matrix. |
Returns:
One if the input matrix is in column-compressed format, zero otherwise. |
Time complexity: O(1).
int igraph_sparsemat_getelements_sorted(const igraph_sparsemat_t *A, igraph_vector_int_t *i, igraph_vector_int_t *j, igraph_vector_t *x);
This function will sort a sparse matrix and return the elements in 3 vectors. Two vectors will indicate where the elements are located, and one will give the elements.
Arguments:
|
A sparse matrix in either triplet or compressed form. |
|
An initialized int vector. This will store the rows of the returned elements. |
|
An initialized int vector. For a triplet matrix this will
store the columns of the returned elements. For a compressed
matrix, if the column index is |
|
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.
igraph_real_t igraph_sparsemat_min(igraph_sparsemat_t *A);
Arguments:
|
The input matrix, column-compressed. |
Returns:
The minimum in the input matrix, or |
Time complexity: TODO.
igraph_real_t igraph_sparsemat_max(igraph_sparsemat_t *A);
Arguments:
|
The input matrix, column-compressed. |
Returns:
The maximum in the input matrix, or |
Time complexity: TODO.
int igraph_sparsemat_minmax(igraph_sparsemat_t *A, igraph_real_t *min, igraph_real_t *max);
Arguments:
|
The input matrix, column-compressed. |
|
The minimum in the input matrix is stored here, or |
|
The maximum in the input matrix is stored here, or |
Returns:
Error code. |
Time complexity: TODO.
long int igraph_sparsemat_count_nonzero(igraph_sparsemat_t *A);
Arguments:
|
The input matrix, column-compressed. |
Returns:
Error code. |
Time complexity: TODO.
long int igraph_sparsemat_count_nonzerotol(igraph_sparsemat_t *A, igraph_real_t tol);
Count the number of matrix entries that are closer to zero than tol
.
Arguments:
|
input matrix, column-compressed. |
|
scalar, the tolerance. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_rowsums(const igraph_sparsemat_t *A, igraph_vector_t *res);
Arguments:
|
The input matrix, in triplet or column-compressed format. |
|
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.
int igraph_sparsemat_colsums(const igraph_sparsemat_t *A, igraph_vector_t *res);
Arguments:
|
The input matrix, in triplet or column-compressed format. |
|
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.
int 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 sparse matrix in either triplet or compressed form. |
Returns:
Number of stored entries. |
Time complexity: O(1).
igraph_sparsemat_entry
— Adds an element to a sparse matrix.igraph_sparsemat_fkeep
— Filters the elements of a sparse matrix.igraph_sparsemat_dropzeros
— Drops the zero elements from a sparse matrix.igraph_sparsemat_droptol
— Drops the almost zero elements from a sparse matrix.igraph_sparsemat_scale
— Scales a sparse matrix.igraph_sparsemat_permute
— Permutes the rows and columns of a sparse matrix.igraph_sparsemat_transpose
— Transposes a sparse matrix.igraph_sparsemat_add
— Sum of two sparse matrices.igraph_sparsemat_multiply
— Matrix multiplication.igraph_sparsemat_gaxpy
— Matrix-vector product, added to another vector.igraph_sparsemat_add_rows
— Adds rows to a sparse matrix.igraph_sparsemat_add_cols
— Adds columns to a sparse matrix.igraph_sparsemat_resize
— Resizes a sparse matrix.
int igraph_sparsemat_entry(igraph_sparsemat_t *A, int row, int 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:
|
The input matrix, it must be in triplet format. |
|
The row index of the entry to add. |
|
The column index of the entry to add. |
|
The value of the entry. |
Returns:
Error code. |
Time complexity: O(1) on average.
int 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:
|
The input matrix, in column-compressed format. |
|
The filter function. It must take four arguments: the
first is an |
|
A |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, it must be in column-compressed format. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, it must be in column-compressed format. |
|
Real number, giving the tolerance threshold. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_scale(igraph_sparsemat_t *A, igraph_real_t by);
Multiplies all elements of a sparse matrix, by the given scalar.
Arguments:
|
The input matrix. |
|
The scaling factor. |
Returns:
Error code. |
Time complexity: O(nz), the number of non-zero elements in the matrix.
int 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:
|
The input matrix, it must be in column-compressed format. |
|
Integer vector, giving the permutation of the rows. |
|
Integer vector, the permutation of the columns. |
|
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.
int igraph_sparsemat_transpose(const igraph_sparsemat_t *A, igraph_sparsemat_t *res, int values);
Arguments:
|
The input matrix, column-compressed or triple format. |
|
Pointer to an uninitialized sparse matrix, the result is stored here. |
|
If this is non-zero, the matrix transpose is calculated the normal way. If it is zero, then only the pattern of the input matrix is stored in the result, the values are not. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The first input matrix, in column-compressed format. |
|
The second input matrix, in column-compressed format. |
|
Real scalar, |
|
Real scalar, |
|
Pointer to an uninitialized sparse matrix, the result is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_multiply(const igraph_sparsemat_t *A, const igraph_sparsemat_t *B, igraph_sparsemat_t *res);
Multiplies two sparse matrices.
Arguments:
|
The first input matrix (left hand side), in column-compressed format. |
|
The second input matrix (right hand side), in column-compressed format. |
|
Pointer to an uninitialized sparse matrix, the result is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_gaxpy(const igraph_sparsemat_t *A, const igraph_vector_t *x, igraph_vector_t *res);
Arguments:
|
The input matrix, in column-compressed format. |
|
The input vector, its size must match the number of
columns in |
|
This vector is added to the matrix-vector product and it is overwritten by the result. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_add_rows(igraph_sparsemat_t *A, long int n);
The current matrix elements are retained and all elements in the new rows are zero.
Arguments:
|
The input matrix, in triplet or column-compressed format. |
|
The number of rows to add. |
Returns:
Error code. |
Time complexity: O(1).
int igraph_sparsemat_add_cols(igraph_sparsemat_t *A, long int n);
The current matrix elements are retained, and all elements in the new columns are zero.
Arguments:
|
The input matrix, in triplet or column-compressed format. |
|
The number of columns to add. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_resize(igraph_sparsemat_t *A, long int nrow, long int ncol, int nzmax);
This function resizes a sparse matrix. The resized sparse matrix will be empty.
Arguments:
|
The initialized sparse matrix to resize. |
|
The new number of rows. |
|
The new number of columns. |
|
The new maximum number of elements. |
Returns:
Error code. |
Time complexity: O(nzmax), the maximum number of non-zero elements.
igraph_sparsemat_iterator_init
— Initialize a sparse matrix iterator.igraph_sparsemat_iterator_reset
— Reset a sparse matrix iterator to the first element.igraph_sparsemat_iterator_end
— Query if the iterator is past the last element.igraph_sparsemat_iterator_row
— Return the row of the iterator.igraph_sparsemat_iterator_col
— Return the column of the iterator.igraph_sparsemat_iterator_get
— Return the element at the current iterator position.igraph_sparsemat_iterator_next
— Let a sparse matrix iterator go to the next element.igraph_sparsemat_iterator_idx
— Returns the element vector index of a sparse matrix iterator.
int igraph_sparsemat_iterator_init(igraph_sparsemat_iterator_t *it, igraph_sparsemat_t *sparsemat);
Arguments:
|
A pointer to an uninitialized sparse matrix iterator. |
|
Pointer to the sparse matrix. |
Returns:
Error code. This will always return |
Time complexity: O(n), the number of columns of the sparse matrix.
int igraph_sparsemat_iterator_reset(igraph_sparsemat_iterator_t *it);
Arguments:
|
A pointer to the sparse matrix iterator. |
Returns:
Error code. This will always return |
Time complexity: O(n), the number of columns of the sparse matrix.
igraph_bool_t igraph_sparsemat_iterator_end(const igraph_sparsemat_iterator_t *it);
Arguments:
|
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).
int igraph_sparsemat_iterator_row(const igraph_sparsemat_iterator_t *it);
Arguments:
|
A pointer to the sparse matrix iterator. |
Returns:
The row of the element at the current iterator position. |
Time complexity: O(1).
int igraph_sparsemat_iterator_col(const igraph_sparsemat_iterator_t *it);
Arguments:
|
A pointer to the sparse matrix iterator. |
Returns:
The column of the element at the current iterator position. |
Time complexity: O(1).
igraph_real_t igraph_sparsemat_iterator_get(const igraph_sparsemat_iterator_t *it);
Arguments:
|
A pointer to the sparse matrix iterator. |
Returns:
The value of the element at the current iterator position. |
Time complexity: O(1).
int igraph_sparsemat_iterator_next(igraph_sparsemat_iterator_t *it);
Arguments:
|
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.
int 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:
|
The input matrix, it must be in triplet format. |
|
Pointer to an uninitialized sparse matrix object, the
compressed version of |
Returns:
Error code. |
Time complexity: O(nz) where nz
is the number of non-zero elements.
int 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:
|
The input matrix, in column-compressed format. |
Returns:
Error code. |
Time complexity: TODO.
igraph_sparsemat_symblu
— Symbolic LU decomposition.igraph_sparsemat_symbqr
— Symbolic QR decomposition.igraph_sparsemat_lsolve
— Solves a lower-triangular linear system.igraph_sparsemat_ltsolve
— Solves an upper-triangular linear system.igraph_sparsemat_usolve
— Solves an upper-triangular linear system.igraph_sparsemat_utsolve
— Solves a lower-triangular linear system.igraph_sparsemat_cholsol
— Solves a symmetric linear system via Cholesky decomposition.igraph_sparsemat_lusol
— Solves a linear system via LU decomposition.igraph_sparsemat_lu
— LU decomposition of a sparse matrix.igraph_sparsemat_qr
— QR decomposition of a sparse matrix.igraph_sparsemat_luresol
— Solves a linear system using a precomputed LU decomposition.igraph_sparsemat_qrresol
— Solves a linear system using a precomputed QR decomposition.igraph_sparsemat_symbolic_destroy
— Deallocates memory after a symbolic decomposition.igraph_sparsemat_numeric_destroy
— Deallocates memory after a numeric decomposition.
int igraph_sparsemat_symblu(long int order, const igraph_sparsemat_t *A, igraph_sparsemat_symbolic_t *dis);
LU decomposition of sparse matrices involves two steps, the first
is calling this function, and then igraph_sparsemat_lu()
.
Arguments:
|
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. |
|
The input matrix, in column-compressed format. |
|
The result of the symbolic analysis is stored here. Once
not needed anymore, it must be destroyed by calling |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_symbqr(long int order, const igraph_sparsemat_t *A, igraph_sparsemat_symbolic_t *dis);
QR decomposition of sparse matrices involves two steps, the first
is calling this function, and then igraph_sparsemat_qr()
.
Arguments:
|
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. |
|
The input matrix, in column-compressed format. |
|
The result of the symbolic analysis is stored here. Once
not needed anymore, it must be destroyed by calling |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed format. |
|
The right hand side of the linear system. |
|
An initialized vector, the result is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed format. |
|
The right hand side of the linear system. |
|
An initialized vector, the result is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed format. |
|
The right hand side of the linear system. |
|
An initialized vector, the result is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed format. |
|
The right hand side of the linear system. |
|
An initialized vector, the result is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_sparsemat_cholsol(const igraph_sparsemat_t *A, const igraph_vector_t *b, igraph_vector_t *res, int order);
Solve Ax=b, where A is a symmetric positive definite matrix.
Arguments:
|
The input matrix, in column-compressed format. |
|
The right hand side. |
|
An initialized vector, the result is stored here. |
|
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.
int igraph_sparsemat_lusol(const igraph_sparsemat_t *A, const igraph_vector_t *b, igraph_vector_t *res, int order, igraph_real_t tol);
Solve Ax=b, via LU factorization of A.
Arguments:
|
The input matrix, in column-compressed format. |
|
The right hand side of the equation. |
|
An initialized vector, the result is stored here. |
|
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. |
|
Real number, the tolerance limit to use for the numeric LU factorization. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed format. |
|
The symbolic analysis for LU decomposition, coming from
a call to the |
|
The numeric decomposition, the result is stored here. It
can be used to solve linear systems with changing right hand
side vectors, by calling |
|
The tolerance for the numeric LU decomposition. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed format. |
|
The result of the symbolic QR analysis, from the
function |
|
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 |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The symbolic analysis of the coefficient matrix, the
result of |
|
The LU decomposition, the result of a call to |
|
A vector that defines the right hand side of the linear equation system. |
|
An initialized vector, the solution of the linear system is stored here. |
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
Symbolic analysis of the coefficient matrix, the result
of |
|
The QR decomposition of the coefficient matrix, the
result of |
|
Vector, giving the right hand side of the linear equation system. |
|
An initialized vector, the solution is stored here. It is resized as needed. |
Returns:
Error code. |
Time complexity: TODO.
void igraph_sparsemat_symbolic_destroy(igraph_sparsemat_symbolic_t *dis);
Frees the memory allocated by igraph_sparsemat_symbqr()
or
igraph_sparsemat_symblu()
.
Arguments:
|
The symbolic analysis. |
Time complexity: O(1).
void igraph_sparsemat_numeric_destroy(igraph_sparsemat_numeric_t *din);
Frees the memoty allocated by igraph_sparsemat_qr()
or igraph_sparsemat_lu()
.
Arguments:
|
The LU or QR decomposition. |
Time complexity: O(1).
int 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:
|
input matrix, must be column-compressed. |
||||
|
It is passed to |
||||
|
Storage for ARPACK. See |
||||
|
An initialized vector or a null pointer, the eigenvalues are stored here. |
||||
|
An initialised matrix, or a null pointer, the eigenvectors are stored here, in the columns. |
||||
|
The method to solve the linear system, if
|
Returns:
Error code. |
Time complexity: TODO.
int 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:
|
The input matrix, in column-compressed mode. |
|
ARPACK options, it is passed to |
|
Storage for ARPACK, this is passed to |
|
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. |
|
An initialized matrix, or a null pointer. If not a
null pointer, then the eigenvectors are stored here, please see
|
Returns:
Error code. |
Time complexity: TODO.
igraph_sparsemat
— Creates an igraph graph from a sparse matrix.igraph_get_sparsemat
— Converts an igraph graph to a sparse matrix.igraph_matrix_as_sparsemat
— Converts a dense matrix to a sparse matrix.igraph_sparsemat_as_matrix
— Converts a sparse matrix to a dense matrix.
int 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:
|
Pointer to an uninitialized igraph_t object, the graphs is stored here. |
|
The input matrix, in triplet or column-compressed format. |
|
Boolean scalar, whether to create a directed graph. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_get_sparsemat(const igraph_t *graph, igraph_sparsemat_t *res);
If the graph is undirected, then a symmetric matrix is created.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized sparse matrix. The result will be stored here. |
Returns:
Error code. |
Time complexity: TODO.
int igraph_matrix_as_sparsemat(igraph_sparsemat_t *res, const igraph_matrix_t *mat, igraph_real_t tol);
Arguments:
|
An uninitialized sparse matrix, the result is stored here. |
|
The dense input matrix. |
|
Real scalar, the tolerance. Values closer than |
Returns:
Error code. |
Time complexity: O(mn), the number of elements in the dense matrix.
int igraph_sparsemat_as_matrix(igraph_matrix_t *res, const igraph_sparsemat_t *spmat);
Arguments:
|
Pointer to an initialized matrix, the result is stored here. It will be resized to the required size. |
|
The input sparse matrix, in triplet or column-compressed format. |
Returns:
Error code. |
Time complexity: O(mn), the number of elements in the dense matrix.
int 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:
|
The input matrix, triplet or column-compressed format. |
|
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.
igraph_stack_init
— Initializes a stack.igraph_stack_destroy
— Destroys a stack object.igraph_stack_reserve
— Reserve memory.igraph_stack_empty
— Decides whether a stack object is empty.igraph_stack_size
— Returns the number of elements in a stack.igraph_stack_clear
— Removes all elements from a stack.igraph_stack_push
— Places an element on the top of a stack.igraph_stack_pop
— Removes and returns an element from the top of a stack.igraph_stack_top
— Query top element.
int igraph_stack_init(igraph_stack_t* s, long int size);
The initialized stack is always empty.
Arguments:
|
Pointer to an uninitialized stack. |
|
The number of elements to allocate memory for. |
Returns:
Error code. |
Time complexity: O(size
).
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:
|
The stack to destroy. |
Time complexity: O(1).
int igraph_stack_reserve(igraph_stack_t* s, long int size);
Reserve memory for future use. The actual size of the stack is unchanged.
Arguments:
|
The stack object. |
|
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.
igraph_bool_t igraph_stack_empty(igraph_stack_t* s);
Arguments:
|
The stack object. |
Returns:
Boolean, |
Time complexity: O(1).
long int igraph_stack_size(const igraph_stack_t* s);
Arguments:
|
The stack object. |
Returns:
The number of elements in the stack. |
Time complexity: O(1).
int igraph_stack_push(igraph_stack_t* s, igraph_real_t elem);
The capacity of the stack is increased, if needed.
Arguments:
|
The stack object. |
|
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.
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:
|
The stack object. |
Returns:
The removed top element. |
Time complexity: O(1).
igraph_dqueue_init
— Initialize a double ended queue (deque).igraph_dqueue_destroy
— Destroy a double ended queue.igraph_dqueue_empty
— Decide whether the queue is empty.igraph_dqueue_full
— Check whether the queue is full.igraph_dqueue_clear
— Remove all elements from the queue.igraph_dqueue_size
— Number of elements in the queue.igraph_dqueue_head
— Head of the queue.igraph_dqueue_back
— Tail of the queue.igraph_dqueue_pop
— Remove the head.igraph_dqueue_pop_back
— Remove the tailigraph_dqueue_push
— Appends an element.This is the classic data type of the double ended queue. Most of the time it is used if a First-In-First-Out (FIFO) behavior is needed. See the operations below.
Example 7.11. File examples/simple/dqueue.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard street, Cambridge, MA 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> int main() { igraph_dqueue_t q; int i; /* igraph_dqueue_init, igraph_dqueue_destroy, igraph_dqueue_empty */ igraph_dqueue_init(&q, 5); if (!igraph_dqueue_empty(&q)) { return 1; } igraph_dqueue_destroy(&q); /* igraph_dqueue_push, igraph_dqueue_pop */ igraph_dqueue_init(&q, 4); igraph_dqueue_push(&q, 1); igraph_dqueue_push(&q, 2); igraph_dqueue_push(&q, 3); igraph_dqueue_push(&q, 4); if (igraph_dqueue_pop(&q) != 1) { return 2; } if (igraph_dqueue_pop(&q) != 2) { return 3; } if (igraph_dqueue_pop(&q) != 3) { return 4; } if (igraph_dqueue_pop(&q) != 4) { return 5; } igraph_dqueue_destroy(&q); /* igraph_dqueue_clear, igraph_dqueue_size */ igraph_dqueue_init(&q, 0); if (igraph_dqueue_size(&q) != 0) { return 6; } igraph_dqueue_clear(&q); if (igraph_dqueue_size(&q) != 0) { return 7; } for (i = 0; i < 10; i++) { igraph_dqueue_push(&q, i); } igraph_dqueue_clear(&q); if (igraph_dqueue_size(&q) != 0) { return 8; } igraph_dqueue_destroy(&q); /* TODO: igraph_dqueue_full */ /* igraph_dqueue_head, igraph_dqueue_back, igraph_dqueue_pop_back */ igraph_dqueue_init(&q, 0); for (i = 0; i < 10; i++) { igraph_dqueue_push(&q, i); } for (i = 0; i < 10; i++) { if (igraph_dqueue_head(&q) != 0) { return 9; } if (igraph_dqueue_back(&q) != 9 - i) { return 10; } if (igraph_dqueue_pop_back(&q) != 9 - i) { return 11; } } igraph_dqueue_destroy(&q); /* print */ igraph_dqueue_init(&q, 4); igraph_dqueue_push(&q, 1); igraph_dqueue_push(&q, 2); igraph_dqueue_push(&q, 3); igraph_dqueue_push(&q, 4); igraph_dqueue_pop(&q); igraph_dqueue_pop(&q); igraph_dqueue_push(&q, 5); igraph_dqueue_push(&q, 6); igraph_dqueue_print(&q); igraph_dqueue_clear(&q); igraph_dqueue_print(&q); igraph_dqueue_destroy(&q); if (IGRAPH_FINALLY_STACK_SIZE() != 0) { return 12; } return 0; }
int igraph_dqueue_init(igraph_dqueue_t* q, long int size);
The queue will be always empty.
Arguments:
|
Pointer to an uninitialized deque. |
|
How many elements to allocate memory for. |
Returns:
Error code. |
Time complexity: O(size
).
void igraph_dqueue_destroy(igraph_dqueue_t* q);
Arguments:
|
The queue to destroy |
Time complexity: O(1).
igraph_bool_t igraph_dqueue_empty(const igraph_dqueue_t* q);
Arguments:
|
The queue. |
Returns:
Boolean, |
Time complexity: O(1).
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:
|
The queue. |
Returns:
|
Time complecity: O(1).
long int igraph_dqueue_size(const igraph_dqueue_t* q);
Arguments:
|
The queue. |
Returns:
Integer, the number of elements currently in the queue. |
Time complexity: O(1).
igraph_real_t igraph_dqueue_head(const igraph_dqueue_t* q);
The queue must contain at least one element.
Arguments:
|
The queue. |
Returns:
The first element in the queue. |
Time complexity: O(1).
igraph_real_t igraph_dqueue_back(const igraph_dqueue_t* q);
The queue must contain at least one element.
Arguments:
|
The queue. |
Returns:
The last element in the queue. |
Time complexity: O(1).
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:
|
The input queue. |
Returns:
The first element in the queue. |
Time complexity: O(1).
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:
|
The queue. |
Returns:
The last element in the queue. |
Time complexity: O(1).
int igraph_dqueue_push(igraph_dqueue_t* q, igraph_real_t elem);
Append an element to the end of the queue.
Arguments:
|
The queue. |
|
The element to append. |
Returns:
Error code. |
Time complexity: O(1) if no memory allocation is needed, O(n), the number of elements in the queue otherwise. But not that by allocating always twice as much memory as the current size of the queue we ensure that n push operations can always be done in at most O(n) time. (Assuming memory allocation is at most linear.)
igraph_heap_init
— Initializes an empty heap object.igraph_heap_init_array
— Build a heap from an array.igraph_heap_destroy
— Destroys an initialized heap object.igraph_heap_empty
— Decides whether a heap object is empty.igraph_heap_push
— Add an element.igraph_heap_top
— Top element.igraph_heap_delete_top
— Return and removes the top elementigraph_heap_size
— Number of elementsigraph_heap_reserve
— Allocate more memory
int igraph_heap_init(igraph_heap_t* h, long int alloc_size);
Creates an empty heap, but allocates size for some elements.
Arguments:
|
Pointer to an uninitialized heap object. |
|
Number of elements to allocate memory for. |
Returns:
Error code. |
Time complexity: O(alloc_size
), assuming memory allocation is a
linear operation.
int igraph_heap_init_array(igraph_heap_t *h, igraph_real_t* data, long int len);
Initializes a heap object from an array, the heap is also built of course (constructor).
Arguments:
|
Pointer to an uninitialized heap object. |
|
Pointer to an array of base data type. |
|
The length of the array at |
Returns:
Error code. |
Time complexity: O(n), the number of elements in the heap.
igraph_bool_t igraph_heap_empty(igraph_heap_t* h);
Arguments:
|
The heap object. |
Returns:
|
TIme complexity: O(1).
int igraph_heap_push(igraph_heap_t* h, igraph_real_t elem);
Adds an element to the heap.
Arguments:
|
The heap object. |
|
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.
igraph_real_t igraph_heap_top(igraph_heap_t* h);
For maximum heaps this is the largest, for minimum heaps the smallest element of the heap.
Arguments:
|
The heap object. |
Returns:
The top element. |
Time complexity: O(1).
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:
|
The heap object. |
Returns:
The top element. |
Time complexity: O(log n), n is the number of elements in the heap.
long int igraph_heap_size(igraph_heap_t* h);
Gives the number of elements in a heap.
Arguments:
|
The heap object. |
Returns:
The number of elements in the heap. |
Time complexity: O(1).
int igraph_heap_reserve(igraph_heap_t* h, long int size);
Allocates memory for future use. The size of the heap is
unchanged. If the heap is larger than the size
parameter then
nothing happens.
Arguments:
|
The heap object. |
|
The number of elements to allocate memory for. |
Returns:
Error code. |
Time complexity: O(size
) if size
is larger than the current
number of elements. O(1) otherwise.
igraph_strvector_init
— Initializeigraph_strvector_copy
— Initialization by copying.igraph_strvector_destroy
— Free allocated memorySTR
— Indexing string vectorsigraph_strvector_get
— Indexingigraph_strvector_set
— Set an elementigraph_strvector_set2
— Sets an element.igraph_strvector_remove
— Removes a single element from a string vector.igraph_strvector_append
— Concatenate two string vectors.igraph_strvector_clear
— Remove all elementsigraph_strvector_resize
— Resizeigraph_strvector_size
— Gives the size of a string vector.igraph_strvector_add
— Adds an element to the back of a string vector.The igraph_strvector_t type is a vector of strings.
The current implementation is very simple and not too efficient. It
works fine for not too many strings, e.g. the list of attribute
names is returned in a string vector by igraph_cattribute_list()
. Do not expect great performance from this
type.
Example 7.12. File examples/simple/igraph_strvector.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> void strvector_print(const igraph_strvector_t *sv) { long int i, s = igraph_strvector_size(sv); for (i = 0; i < s; i++) { printf("---%s---\n", STR(*sv, i)); } } int main() { igraph_strvector_t sv1, sv2; char *str1; int i; /* igraph_strvector_init, igraph_strvector_destroy */ igraph_strvector_init(&sv1, 10); igraph_strvector_destroy(&sv1); igraph_strvector_init(&sv1, 0); igraph_strvector_destroy(&sv1); /* igraph_strvector_get, igraph_strvector_set */ igraph_strvector_init(&sv1, 5); for (i = 0; i < igraph_strvector_size(&sv1); i++) { igraph_strvector_get(&sv1, i, &str1); printf("---%s---\n", str1); } igraph_strvector_set(&sv1, 0, "zero"); igraph_strvector_set(&sv1, 1, "one"); igraph_strvector_set(&sv1, 2, "two"); igraph_strvector_set(&sv1, 3, "three"); igraph_strvector_set(&sv1, 4, "four"); for (i = 0; i < igraph_strvector_size(&sv1); i++) { igraph_strvector_get(&sv1, i, &str1); printf("---%s---\n", str1); } /* igraph_strvector_remove_section, igraph_strvector_remove, igraph_strvector_resize, igraph_strvector_size */ igraph_strvector_remove_section(&sv1, 0, 5); if (igraph_strvector_size(&sv1) != 0) { return 1; } igraph_strvector_resize(&sv1, 10); igraph_strvector_set(&sv1, 0, "zero"); igraph_strvector_set(&sv1, 1, "one"); igraph_strvector_set(&sv1, 2, "two"); igraph_strvector_set(&sv1, 3, "three"); igraph_strvector_set(&sv1, 4, "four"); igraph_strvector_resize(&sv1, 5); for (i = 0; i < igraph_strvector_size(&sv1); i++) { igraph_strvector_get(&sv1, i, &str1); printf("---%s---\n", str1); } igraph_strvector_resize(&sv1, 0); if (igraph_strvector_size(&sv1) != 0) { return 1; } igraph_strvector_resize(&sv1, 10); igraph_strvector_set(&sv1, 0, "zero"); igraph_strvector_set(&sv1, 1, "one"); igraph_strvector_set(&sv1, 2, "two"); igraph_strvector_set(&sv1, 3, "three"); igraph_strvector_set(&sv1, 4, "four"); igraph_strvector_resize(&sv1, 5); for (i = 0; i < igraph_strvector_size(&sv1); i++) { igraph_strvector_get(&sv1, i, &str1); printf("---%s---\n", str1); } /* igraph_strvector_move_interval */ igraph_strvector_move_interval(&sv1, 3, 5, 0); for (i = 0; i < igraph_strvector_size(&sv1); i++) { igraph_strvector_get(&sv1, i, &str1); printf("---%s---\n", str1); } /* igraph_strvector_copy */ igraph_strvector_copy(&sv2, &sv1); for (i = 0; i < igraph_strvector_size(&sv2); i++) { igraph_strvector_get(&sv2, i, &str1); printf("---%s---\n", str1); } igraph_strvector_resize(&sv1, 0); igraph_strvector_destroy(&sv2); igraph_strvector_copy(&sv2, &sv1); if (igraph_strvector_size(&sv2) != 0) { return 2; } igraph_strvector_destroy(&sv2); /* igraph_strvector_add */ igraph_strvector_add(&sv1, "zeroth"); igraph_strvector_add(&sv1, "first"); igraph_strvector_add(&sv1, "second"); igraph_strvector_add(&sv1, "third"); igraph_strvector_add(&sv1, "fourth"); for (i = 0; i < igraph_strvector_size(&sv1); i++) { igraph_strvector_get(&sv1, i, &str1); printf("---%s---\n", str1); } /* TODO: igraph_strvector_permdelete */ /* TODO: igraph_strvector_remove_negidx */ igraph_strvector_destroy(&sv1); /* append */ printf("---\n"); igraph_strvector_init(&sv1, 0); igraph_strvector_init(&sv2, 0); igraph_strvector_append(&sv1, &sv2); strvector_print(&sv1); printf("---\n"); igraph_strvector_resize(&sv1, 3); igraph_strvector_append(&sv1, &sv2); strvector_print(&sv1); printf("---\n"); igraph_strvector_append(&sv2, &sv1); strvector_print(&sv2); printf("---\n"); igraph_strvector_set(&sv1, 0, "0"); igraph_strvector_set(&sv1, 1, "1"); igraph_strvector_set(&sv1, 2, "2"); igraph_strvector_set(&sv2, 0, "3"); igraph_strvector_set(&sv2, 1, "4"); igraph_strvector_set(&sv2, 2, "5"); igraph_strvector_append(&sv1, &sv2); strvector_print(&sv1); igraph_strvector_destroy(&sv1); igraph_strvector_destroy(&sv2); /* clear */ igraph_strvector_init(&sv1, 3); igraph_strvector_set(&sv1, 0, "0"); igraph_strvector_set(&sv1, 1, "1"); igraph_strvector_set(&sv1, 2, "2"); igraph_strvector_clear(&sv1); if (igraph_strvector_size(&sv1) != 0) { return 3; } igraph_strvector_resize(&sv1, 4); strvector_print(&sv1); igraph_strvector_set(&sv1, 0, "one"); igraph_strvector_set(&sv1, 2, "two"); strvector_print(&sv1); igraph_strvector_destroy(&sv1); /* STR */ igraph_strvector_init(&sv1, 5); igraph_strvector_set(&sv1, 0, "one"); igraph_strvector_set(&sv1, 1, "two"); igraph_strvector_set(&sv1, 2, "three"); igraph_strvector_set(&sv1, 3, "four"); igraph_strvector_set(&sv1, 4, "five"); strvector_print(&sv1); igraph_strvector_destroy(&sv1); if (!IGRAPH_FINALLY_STACK_EMPTY) { return 4; } return 0; }
int igraph_strvector_init(igraph_strvector_t *sv, long int len);
Reserves memory for the string vector, a string vector must be first initialized before calling other functions on it. All elements of the string vector are set to the empty string.
Arguments:
|
Pointer to an initialized string vector. |
|
The (initial) length of the string vector. |
Returns:
Error code. |
Time complexity: O(len
).
int igraph_strvector_copy(igraph_strvector_t *to, const igraph_strvector_t *from);
Initializes a string vector by copying another string vector.
Arguments:
|
Pointer to an uninitialized string vector. |
|
The other string vector, to be copied. |
Returns:
Error code. |
Time complexity: O(l), the total length of the strings in from
.
void igraph_strvector_destroy(igraph_strvector_t *sv);
Destroy a string vector. It may be reinitialized with igraph_strvector_init()
later.
Arguments:
|
The string vector. |
Time complexity: O(l), the total length of the strings, maybe less depending on the memory manager.
#define STR(sv,i)
This is a macro which allows to query the elements of a string vector in
simpler way than igraph_strvector_get()
. Note this macro cannot be
used to set an element, for that use igraph_strvector_set()
.
Arguments:
|
The string vector |
|
The the index of the element. |
Returns:
The element at position |
Time complexity: O(1).
void igraph_strvector_get(const igraph_strvector_t *sv, long int idx, char **value);
Query an element of a string vector. See also the STR
macro
for an easier way.
Arguments:
|
The input string vector. |
|
The index of the element to query. |
|
to a char*, the address of the string is stored here. |
Time complexity: O(1).
int igraph_strvector_set(igraph_strvector_t *sv, long int idx, const char *value);
The provided value
is copied into the idx
position in the
string vector.
Arguments:
|
The string vector. |
|
The position to set. |
|
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.
int igraph_strvector_set2(igraph_strvector_t *sv, long int idx, const char *value, int 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:
|
The string vector. |
|
The position to set. |
|
The new value. |
|
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.
void igraph_strvector_remove(igraph_strvector_t *v, long int elem);
The string will be one shorter.
Arguments:
|
The string vector. |
|
The index of the element to remove. |
Time complexity: O(n), the length of the string.
int igraph_strvector_append(igraph_strvector_t *to, const igraph_strvector_t *from);
Arguments:
|
The first string vector, the result is stored here. |
|
The second string vector, it is kept unchanged. |
Returns:
Error code. |
Time complexity: O(n+l2), n is the number of strings in the new
string vector, l2 is the total length of strings in the from
string vector.
void igraph_strvector_clear(igraph_strvector_t *sv);
After this operation the string vector will be empty.
Arguments:
|
The string vector. |
Time complexity: O(l), the total length of strings, maybe less, depending on the memory manager.
int igraph_strvector_resize(igraph_strvector_t* v, long int newsize);
If the new size is bigger then empty strings are added, if it is smaller then the unneeded elements are removed.
Arguments:
|
The string vector. |
|
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.
long int igraph_strvector_size(const igraph_strvector_t *sv);
Arguments:
|
The string vector. |
Returns:
The length of the string vector. |
Time complexity: O(1).
Sometimes it is easier to work with a graph which is in adjacency list format: a list of vectors; each vector contains the neighbor vertices or incident edges of a given vertex. Typically, this representation is good if we need to iterate over the neighbors of all vertices many times. E.g. when finding the shortest paths between all pairs of vertices or calculating closeness centrality for all the vertices.
The igraph_adjlist_t stores the adjacency lists
of a graph. After creation it is independent of the original graph,
it can be modified freely with the usual vector operations, the
graph is not affected. E.g. the adjacency list can be used to
rewire the edges of a graph efficiently. If one used the
straightforward igraph_delete_edges()
and igraph_add_edges()
combination for this that needs O(|V|+|E|) time
for every single deletion and insertion operation, it is thus very
slow if many edges are rewired. Extracting the graph into an
adjacency list, do all the rewiring operations on the vectors of
the adjacency list and then creating a new graph needs (depending
on how exactly the rewiring is done) typically O(|V|+|E|) time for
the whole rewiring process.
Lazy adjacency lists are a bit different. When creating a
lazy adjacency list, the neighbors of the vertices are not queried,
only some memory is allocated for the vectors. When igraph_lazy_adjlist_get()
is called for vertex v the first time,
the neighbors of v are queried and stored in a vector of the
adjacency list, so they don't need to be queried again. Lazy
adjacency lists are handy if you have an at least linear operation
(because initialization is generally linear in terms of the number of
vertices), but you don't know how many vertices you will visit
during the computation.
Example 7.13. File examples/simple/adjlist.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2008-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard street, Cambridge, MA 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> int main() { igraph_t g, g2; igraph_adjlist_t adjlist; igraph_bool_t iso; /* Create a directed out-tree, convert it into an adjacency list * representation, then reconstruct the graph from the tree and check * whether the two are isomorphic (they should be) */ igraph_tree(&g, 42, 3, IGRAPH_TREE_OUT); igraph_adjlist_init(&g, &adjlist, IGRAPH_OUT, IGRAPH_LOOPS_ONCE, IGRAPH_MULTIPLE); igraph_adjlist(&g2, &adjlist, IGRAPH_OUT, /* duplicate = */ 0); igraph_isomorphic(&g, &g2, &iso); if (!iso) { return 1; } igraph_adjlist_destroy(&adjlist); igraph_destroy(&g2); igraph_destroy(&g); return 0; }
igraph_adjlist_init
— Constructs an adjacency list of vertices from a given graph.igraph_adjlist_init_empty
— Initializes an empty adjacency list.igraph_adjlist_init_complementer
— Adjacency lists for the complementer graph.igraph_adjlist_destroy
— Deallocates an adjacency list.igraph_adjlist_get
— Query a vector in an adjacency list.igraph_adjlist_size
— Returns the number of vertices in an adjacency list.igraph_adjlist_clear
— Removes all edges from an adjacency list.igraph_adjlist_sort
— Sorts each vector in an adjacency list.igraph_adjlist_simplify
— Simplifies an adjacency list.
int 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.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized igraph_adjlist_t object. |
|
Constant specifying whether outgoing
( |
|
Specifies how to treat loop edges. |
|
Specifies how to treat multiple (parallel) edges.
|
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
int 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:
|
The number of vertices |
|
Pointer to an uninitialized igraph_adjlist_t object. |
Returns:
Error code. |
Time complexity: O(|V|), linear in the number of vertices.
int igraph_adjlist_init_complementer(const igraph_t *graph, igraph_adjlist_t *al, igraph_neimode_t mode, igraph_bool_t loops);
This function creates adjacency lists for the complementer of the input graph. In the complementer graph all edges are present which are not present in the original graph. Multiple edges in the input graph are ignored.
Arguments:
|
The input graph. |
|
Pointer to a not yet initialized adjacency list. |
|
Constant specifying whether outgoing
( |
|
Whether to consider loop edges. |
Returns:
Error code. |
Time complexity: O(|V|^2+|E|), quadratic in the number of vertices.
void igraph_adjlist_destroy(igraph_adjlist_t *al);
Free all memory allocated for an adjacency list.
Arguments:
|
The adjacency list to destroy. |
Time complexity: depends on memory management.
#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:
|
The adjacency list object. |
|
The vertex whose adjacent vertices will be returned. |
Returns:
Pointer to the igraph_vector_int_t object. |
Time complexity: O(1).
igraph_integer_t igraph_adjlist_size(const igraph_adjlist_t *al);
Arguments:
|
The adjacency list. |
Returns:
The number of vertices in the adjacency list. |
Time complexity: O(1).
void igraph_adjlist_clear(igraph_adjlist_t *al);
Arguments:
|
The adjacency list. Time complexity: depends on memory management, typically O(n), where n is the total number of elements in the adjacency list. |
void igraph_adjlist_sort(igraph_adjlist_t *al);
Sorts every vector of the adjacency list.
Arguments:
|
The adjacency list. |
Time complexity: O(n log n), n is the total number of elements in the adjacency list.
igraph_inclist_init
— Initializes an incidence list.igraph_inclist_destroy
— Frees all memory allocated for an incidence list.igraph_inclist_get
— Query a vector in an incidence list.igraph_inclist_size
— Returns the number of vertices in an incidence list.igraph_inclist_clear
— Removes all edges from an incidence list.
int igraph_inclist_init(const igraph_t *graph, igraph_inclist_t *il, igraph_neimode_t mode, igraph_loops_t loops);
Creates a list of vectors containing the incident edges for all vertices. The incidence list is independent of the graph after creation, subsequent changes of the graph object do not update the incidence list, and changes to the incidence list do not update the graph.
When mode
is IGRAPH_IN
or IGRAPH_OUT
, each edge ID will appear
in the incidence list once. When mode
is IGRAPH_ALL
, each edge ID
will appear in the incidence list twice, once for the source vertex
and once for the target edge. It also means that the edge IDs of loop edges
may potentially appear twice for the same vertex. Use the loops
argument to control whether this will be the case (IGRAPH_LOOPS_TWICE
)
or not (IGRAPH_LOOPS_ONCE
or IGRAPH_NO_LOOPS
).
Arguments:
|
The input graph. |
|
Pointer to an uninitialized incidence list. |
|
Constant specifying whether incoming edges
( |
|
Specifies how to treat loop edges. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
void igraph_inclist_destroy(igraph_inclist_t *il);
Arguments:
|
The incidence list to destroy. |
Time complexity: depends on memory management.
#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:
|
Pointer to the incidence list. |
|
The vertex for which the incident edges are returned. |
Returns:
Pointer to an igraph_vector_int_t object. |
Time complexity: O(1).
igraph_lazy_adjlist_init
— Initialized a lazy adjacency list.igraph_lazy_adjlist_destroy
— Deallocate a lazt adjacency list.igraph_lazy_adjlist_get
— Query neighbor vertices.igraph_lazy_adjlist_size
— Returns the number of vertices in a lazy adjacency list.igraph_lazy_adjlist_clear
— Removes all edges from a lazy adjacency list.
int igraph_lazy_adjlist_init(const igraph_t *graph, igraph_lazy_adjlist_t *al, igraph_neimode_t mode, igraph_loops_t loops, igraph_multiple_t multiple);
Create a lazy adjacency list for vertices. This function only
allocates some memory for storing the vectors of an adjacency list,
but the neighbor vertices are not queried, only at the igraph_lazy_adjlist_get()
calls.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized adjacency list object. |
|
Constant, it gives whether incoming edges
( |
|
Constant, it gives whether to simplify the vectors
in the adjacency list ( |
Returns:
Error code. |
Time complexity: O(|V|), the number of vertices, possibly, but depends on the underlying memory management too.
void igraph_lazy_adjlist_destroy(igraph_lazy_adjlist_t *al);
Free all allocated memory for a lazy adjacency list.
Arguments:
|
The adjacency list to deallocate. |
Time complexity: depends on the memory management.
#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:
|
The lazy adjacency list. |
|
The vertex ID to query. |
Returns:
Pointer to a vector. It is allowed to modify it and modification does not affect the original graph. |
Time complexity: O(d), the number of neighbor vertices for the first time, O(1) for subsequent calls.
igraph_integer_t igraph_lazy_adjlist_size(const igraph_lazy_adjlist_t *al);
Arguments:
|
The lazy adjacency list. |
Returns:
The number of vertices in the lazy adjacency list. |
Time complexity: O(1).
igraph_lazy_inclist_init
— Initializes a lazy incidence list of edges.igraph_lazy_inclist_destroy
— Deallocates a lazy incidence list.igraph_lazy_inclist_get
— Query incident edges.igraph_lazy_inclist_size
— Returns the number of vertices in a lazy incidence list.igraph_lazy_inclist_clear
— Removes all edges from a lazy incidence list.
int igraph_lazy_inclist_init(const igraph_t *graph, igraph_lazy_inclist_t *il, igraph_neimode_t mode, igraph_loops_t loops);
Create a lazy incidence list for edges. This function only
allocates some memory for storing the vectors of an incidence list,
but the incident edges are not queried, only when igraph_lazy_inclist_get()
is called.
When mode
is IGRAPH_IN
or IGRAPH_OUT
, each edge ID will appear
in the incidence list once. When mode
is IGRAPH_ALL
, each edge ID
will appear in the incidence list twice, once for the source vertex
and once for the target edge. It also means that the edge IDs of loop edges
will appear twice for the same vertex.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized incidence list. |
|
Constant, it gives whether incoming edges
( |
|
Specifies how to treat loop edges. |
Returns:
Error code. |
Time complexity: O(|V|), the number of vertices, possibly. But it also depends on the underlying memory management.
void igraph_lazy_inclist_destroy(igraph_lazy_inclist_t *il);
Frees all allocated memory for a lazy incidence list.
Arguments:
|
The incidence list to deallocate. |
Time complexity: depends on memory management.
#define igraph_lazy_inclist_get(al,no)
If the function is called for the first time for a vertex, then the result is stored in the incidence list and no further query operations are needed when the incident edges of the same vertex are queried again.
Arguments:
|
The lazy incidence list object. |
|
The vertex id to query. |
Returns:
Pointer to a vector. It is allowed to modify it and modification does not affect the original graph. |
Time complexity: O(d), the number of incident edges for the first
time, O(1) for subsequent calls with the same no
argument.
igraph_integer_t igraph_lazy_inclist_size(const igraph_lazy_inclist_t *il);
Arguments:
|
The lazy incidence list. |
Returns:
The number of vertices in the lazy incidence list. |
Time complexity: O(1).
igraph_psumtree_init
— Initializes a partial prefix sum tree.igraph_psumtree_destroy
— Destroys a partial prefix sum tree.igraph_psumtree_size
— Returns the size of the tree.igraph_psumtree_get
— Retrieves the value corresponding to an item in the tree.igraph_psumtree_sum
— Returns the sum of the values of the leaves in the tree.igraph_psumtree_search
— Finds an item in the tree, given a value.igraph_psumtree_update
— Updates the value associated to an item in the tree.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.
int igraph_psumtree_init(igraph_psumtree_t *t, long int size);
The tree is initialized with a fixed number of elements. After initialization, the value corresponding to each element is zero.
Arguments:
|
The tree to initialize |
|
The number of elements in the tree |
Returns:
Error code, typically |
Time complexity: O(n) for a tree containing n elements
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:
|
Pointer to the (previously initialized) tree to destroy. |
Time complexity: operating system dependent.
long int igraph_psumtree_size(const igraph_psumtree_t *t);
Arguments:
|
The tree object |
Returns:
The number of discrete items in the tree. |
Time complexity: O(1).
igraph_real_t igraph_psumtree_get(const igraph_psumtree_t *t, long int idx);
Arguments:
|
The tree to query. |
|
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)
igraph_real_t igraph_psumtree_sum(const igraph_psumtree_t *t);
Arguments:
|
The tree object |
Returns:
The sum of the values of the leaves in the tree. |
Time complexity: O(1).
int igraph_psumtree_search(const igraph_psumtree_t *t, long int *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:
|
The tree to query. |
|
The index of the item is returned here. |
|
The value to use for the search. Must be in the interval
|
Returns:
Error code; currently the search always succeeds. |
Time complexity: O(log n), where n is the number of items in the tree.
int igraph_psumtree_update(igraph_psumtree_t *t, long int idx, igraph_real_t new_value);
Arguments:
|
The tree to query. |
|
The index of the item to update. |
|
The new value of the item. |
Returns:
Error code, |
Time complexity: O(log n), where n is the number of items in the tree.
← Chapter 6. Memory (de)allocation | Chapter 8. Random numbers → |