String vectors, lists and bit sets

Creates a string vector holding size empty strings.

og_error_t og_strvector_init(og_strvector_t *sv, og_int_t size);

Sets up sv with size entries, each the empty string. An empty entry costs no allocation: its slot holds NULL, which strvector_get() reads as "". The capacity is at least one slot.

Every string later stored in the vector is a private copy that the vector owns; strvector_destroy() frees them all. After a failure sv is still safe to destroy.

Parameters

• sv the vector to set up; its previous contents are ignored
• size number of entries, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL size is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(size)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_init

In notebooks

Og.Native.og_strvector_init

igraph 1.0

igraph_strvector_init

See also

strvector_destroy, strvector_init_copy, strvector_push_back, strvector_get

og_strvector_t names;
OG_STRVECTOR_INIT_FINALLY(&names, 0);
OG_CHECK(og_strvector_push_back(&names, "Oslo"));
OG_CHECK(og_strvector_push_back(&names, "Bergen"));
printf("%s\n", og_strvector_get(&names, 1));   /* Bergen */
og_strvector_destroy(&names);
OG_FINALLY_CLEAN(1);

Creates a string vector that is a deep copy of another.

og_error_t og_strvector_init_copy(
    og_strvector_t *to,
    const og_strvector_t *from
);

Every string of from is copied, so the two vectors share no memory afterwards and either may be changed or destroyed alone. On failure to holds nothing and is safe to destroy.

Parameters

• to the vector to set up
• from the vector to copy; not changed

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(n + total length of the strings)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_init_copy

In notebooks

Og.Native.og_strvector_init_copy

igraph 1.0

igraph_strvector_init_copy

See also

strvector_update, strvector_init, strvector_destroy

Releases a string vector together with all its strings.

void og_strvector_destroy(og_strvector_t *sv);

Afterwards the vector holds no memory. Calling it a second time, or on a vector whose constructor failed, is harmless; NULL is accepted.

Parameters

• sv the vector to free

Returns

Nothing.

Complexity

O(n)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_destroy

In notebooks

Og.Native.og_strvector_destroy

igraph 1.0

igraph_strvector_destroy

See also

strvector_init, strvector_clear

Returns the string at a position; an empty entry reads as "".

const char *og_strvector_get(const og_strvector_t *sv, og_int_t idx);

The pointer refers to the vector's own storage: do not free or change it, and do not use it after the entry is replaced or removed or the vector is destroyed. The index is not checked and must be in 0 .. size-1.

OG_STR(sv, i), and STR(sv, i) unless OG_NO_SHORT_NAMES is defined, call this function; they take the vector itself rather than a pointer to it.

Parameters

• sv the vector
• idx position, 0 .. size-1

Returns

A NUL-terminated string, never NULL.

Complexity

O(1)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_get

In notebooks

Og.Native.og_strvector_get

igraph 1.0

igraph_strvector_get

See also

strvector_set, strvector_size

Replaces the string at a position with a copy of value.

og_error_t og_strvector_set(
    og_strvector_t *sv,
    og_int_t idx,
    const char *value
);

The new copy is made before the old string is freed, so on failure the entry is unchanged, and value may point into the same vector. NULL and "" both store the empty string.

Parameters

• sv the vector
• idx position, 0 .. size-1
• value NUL-terminated string to copy, or NULL

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL idx is outside 0 .. size-1
• OG_ENOMEM memory could not be allocated

Complexity

O(length of value)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_set

In notebooks

Og.Native.og_strvector_set

igraph 1.0

igraph_strvector_set

See also

strvector_set_len, strvector_get, strvector_push_back

Replaces the string at a position with at most len bytes of value.

og_error_t og_strvector_set_len(
    og_strvector_t *sv,
    og_int_t idx,
    const char *value,
    size_t len
);

Copies the first len bytes of value, stopping earlier at a NUL byte, and adds the terminating NUL; value does not have to be NUL-terminated. A length of zero stores the empty string. On failure the entry is unchanged.

Parameters

• sv the vector
• idx position, 0 .. size-1
• value the bytes to copy
• len most bytes to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL idx is outside 0 .. size-1
• OG_ENOMEM memory could not be allocated

Complexity

O(len)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_set_len

In notebooks

Og.Native.og_strvector_set_len

igraph 1.0

igraph_strvector_set_len

See also

strvector_set, strvector_push_back_len

Appends a copy of a string at the end.

og_error_t og_strvector_push_back(og_strvector_t *sv, const char *value);

The storage grows geometrically, so a series of appends costs amortised constant time per entry plus the copy of the string. NULL and "" append the empty string. On failure the vector is unchanged.

Parameters

• sv the vector
• value NUL-terminated string to copy, or NULL

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

amortised O(1) plus O(length of value)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_push_back

In notebooks

Og.Native.og_strvector_push_back

igraph 1.0

igraph_strvector_push_back

See also

strvector_push_back_len, strvector_append, strvector_reserve

Appends at most len bytes of a string at the end.

og_error_t og_strvector_push_back_len(
    og_strvector_t *sv,
    const char *value,
    size_t len
);

Copies the first len bytes of value, stopping earlier at a NUL byte, and adds the terminating NUL, as strvector_set_len() does. On failure the vector is unchanged.

Parameters

• sv the vector
• value the bytes to copy
• len most bytes to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

amortised O(1) plus O(len)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_push_back_len

In notebooks

Og.Native.og_strvector_push_back_len

igraph 1.0

igraph_strvector_push_back_len

See also

strvector_push_back, strvector_set_len

Exchanges two entries of a string vector.

void og_strvector_swap_elements(og_strvector_t *sv, og_int_t i, og_int_t j);

Only the two string pointers trade places; nothing is copied. The indices are not checked.

Parameters

• sv the vector
• i first position
• j second position

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_swap_elements

In notebooks

Og.Native.og_strvector_swap_elements

igraph 1.0

igraph_strvector_swap_elements

See also

strvector_swap

Removes one entry and moves the later entries down by one.

void og_strvector_remove(og_strvector_t *sv, og_int_t elem);

The removed string is freed. An index outside 0 .. size-1 is ignored. The capacity does not change.

Parameters

• sv the vector
• elem position of the entry to remove

Returns

Nothing.

Complexity

O(n)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_remove

In notebooks

Og.Native.og_strvector_remove

igraph 1.0

igraph_strvector_remove

See also

strvector_remove_section, strvector_resize

Removes the entries at positions from .. to-1.

void og_strvector_remove_section(
    og_strvector_t *sv,
    og_int_t from,
    og_int_t to
);

The range is half-open: to itself stays. The strings in the range are freed and the later entries move down. The range is clipped to the vector, and an empty range does nothing. The capacity does not change.

Parameters

• sv the vector
• from first position removed
• to first position kept after the range

Returns

Nothing.

Complexity

O(n)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_remove_section

In notebooks

Og.Native.og_strvector_remove_section

igraph 1.0

igraph_strvector_remove_section

See also

strvector_remove, strvector_resize

Appends copies of all strings of one vector to another.

og_error_t og_strvector_append(
    og_strvector_t *to,
    const og_strvector_t *from
);

from is not changed; appending a vector to itself doubles it. On failure to is left exactly as it was.

Parameters

• to the vector that grows
• from the strings to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(size of from + length of the strings copied)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_append

In notebooks

Og.Native.og_strvector_append

igraph 1.0

igraph_strvector_append

See also

strvector_merge, strvector_update

Hands all strings of one vector over to another, appending them without copying.

og_error_t og_strvector_merge(og_strvector_t *to, og_strvector_t *from);

The strings change owner: afterwards to holds them and from is empty (its capacity is kept). Merging a vector into itself does nothing. If memory runs out, both vectors are left as they were.

Parameters

• to the vector that grows
• from the vector that is emptied

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(size of from)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_merge

In notebooks

Og.Native.og_strvector_merge

igraph 1.0

igraph_strvector_merge

See also

strvector_append, strvector_swap

Exchanges what two string vectors hold.

void og_strvector_swap(og_strvector_t *v1, og_strvector_t *v2);

Only the internal pointers and counts trade places, so the cost does not depend on the sizes.

Parameters

• v1 first vector
• v2 second vector

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_swap

In notebooks

Og.Native.og_strvector_swap

igraph 1.0

igraph_strvector_swap

See also

strvector_swap_elements, strvector_update

Overwrites a string vector with a copy of another.

og_error_t og_strvector_update(
    og_strvector_t *to,
    const og_strvector_t *from
);

to takes the size and the strings of from; its old strings are freed. The copy is built first, so on failure to is unchanged. Updating a vector from itself does nothing.

Parameters

• to the vector that is overwritten
• from the vector to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(size of to + size of from + length of the strings copied)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_update

In notebooks

Og.Native.og_strvector_update

igraph 1.0

igraph_strvector_update

See also

strvector_init_copy, strvector_append

Removes every entry and keeps the allocated capacity.

void og_strvector_clear(og_strvector_t *sv);

All strings are freed and the size becomes zero; the vector can be refilled without reallocating.

Parameters

• sv the vector

Returns

Nothing.

Complexity

O(n)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_clear

In notebooks

Og.Native.og_strvector_clear

igraph 1.0

igraph_strvector_clear

See also

strvector_resize, strvector_destroy

Grows or shrinks a string vector to a given number of entries.

og_error_t og_strvector_resize(og_strvector_t *sv, og_int_t newsize);

Growing appends empty strings; shrinking frees the strings beyond the new size. When more room is needed the capacity grows geometrically; it is never reduced here (see strvector_resize_min()).

Parameters

• sv the vector
• newsize new number of entries, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL newsize is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(|newsize - size|), plus a reallocation when growing past the capacity

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_resize

In notebooks

Og.Native.og_strvector_resize

igraph 1.0

igraph_strvector_resize

See also

strvector_reserve, strvector_resize_min, strvector_clear

Allocates room for at least capacity entries.

og_error_t og_strvector_reserve(og_strvector_t *sv, og_int_t capacity);

Size and contents do not change. A capacity at or below the current one does nothing. Reserving ahead avoids repeated reallocation when the final size is known.

Parameters

• sv the vector
• capacity number of entries to make room for

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(capacity) for the reallocation, O(1) when nothing changes

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_reserve

In notebooks

Og.Native.og_strvector_reserve

igraph 1.0

igraph_strvector_reserve

See also

strvector_capacity, strvector_resize_min

Shrinks the allocated storage to the current number of entries.

void og_strvector_resize_min(og_strvector_t *sv);

Afterwards the capacity equals the size, also zero for an empty vector. If the smaller block cannot be obtained, the larger one is kept; that is not an error.

Parameters

• sv the vector

Returns

Nothing.

Complexity

O(n) at most (one reallocation)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_resize_min

In notebooks

Og.Native.og_strvector_resize_min

igraph 1.0

igraph_strvector_resize_min

See also

strvector_reserve, strvector_capacity

Tells how many entries a string vector holds.

og_int_t og_strvector_size(const og_strvector_t *sv);

Empty strings count as entries.

Parameters

• sv the vector

Returns

The number of entries.

Complexity

O(1)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_size

In notebooks

Og.Native.og_strvector_size

igraph 1.0

igraph_strvector_size

See also

strvector_capacity, strvector_resize

Returns how many entries fit before the vector must reallocate.

og_int_t og_strvector_capacity(const og_strvector_t *sv);

Always at least the size.

Parameters

• sv the vector

Returns

The capacity, in entries.

Complexity

O(1)

Checked

python-igraph has no string vector type; checked by unit tests, out-of-memory runs and 12,000 random operations compared step by step with a plain model

C name

og_strvector_capacity

In notebooks

Og.Native.og_strvector_capacity

igraph 1.0

igraph_strvector_capacity

See also

strvector_size, strvector_reserve, strvector_resize_min

Creates a list of size new, empty items.

og_error_t og_vector_list_init(og_vector_list_t *v, og_int_t size);

Each item is a new, empty item of the list's type: a real vector of length 0 here; an empty integer vector, a 0 x 0 matrix, an undirected graph with no vertices or a bitset of size 0 in the other list types. A list owns its items: an item is created when it enters the list and destroyed when it leaves, unless a function hands it to the caller (pop_back, remove, remove_fast, replace). On failure the list is safe to destroy.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list to set up
• size number of items, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL size is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(size)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_init

In notebooks

Og.Native.og_vector_list_init

igraph 1.0

igraph_vector_list_init

See also

vector_list_destroy, vector_list_push_back_new, vector_list_get_ptr, vector_list_size

og_vector_list_t rows;
og_vector_t *row;
OG_VECTOR_LIST_INIT_FINALLY(&rows, 0);
OG_CHECK(og_vector_list_push_back_new(&rows, &row));   /* row belongs to the list */
OG_CHECK(og_vector_push_back(row, 1.5));
printf("%" OG_PRId " rows\n", og_vector_list_size(&rows));
og_vector_list_destroy(&rows);                          /* destroys row too */
OG_FINALLY_CLEAN(1);

Creates a list holding deep copies of another list's items.

og_error_t og_vector_list_init_copy(
    og_vector_list_t *to,
    const og_vector_list_t *from
);

The two lists share nothing afterwards. On failure to is safe to destroy.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• to the list to set up
• from the list to copy; not changed

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(total size of the items)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_init_copy

In notebooks

Og.Native.og_vector_list_init_copy

igraph 1.0

igraph_vector_list_init_copy

See also

vector_list_init, vector_list_destroy

Destroys every item of a list and frees the list.

void og_vector_list_destroy(og_vector_list_t *v);

Calling it a second time, or on a list whose constructor failed, is harmless; NULL is accepted.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

Nothing.

Complexity

O(total size of the items)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_destroy

In notebooks

Og.Native.og_vector_list_destroy

igraph 1.0

igraph_vector_list_destroy

See also

vector_list_init, vector_list_clear

Returns a pointer to the item at a position.

og_vector_t *og_vector_list_get_ptr(
    const og_vector_list_t *v,
    og_int_t pos
);

The item stays the list's: change it in place, but do not destroy it. The position is not checked. The pointer stays valid only until the list changes size or order (push, insert, remove, discard, resize, reserve, sort, permute).

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• pos position, 0 .. size-1

Returns

A pointer to the item.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_get_ptr

In notebooks

Og.Native.og_vector_list_get_ptr

igraph 1.0

igraph_vector_list_get_ptr

See also

vector_list_tail_ptr, vector_list_set, vector_list_replace

Returns a pointer to the last item, or NULL for an empty list.

og_vector_t *og_vector_list_tail_ptr(const og_vector_list_t *v);

The item stays the list's. The pointer stays valid only until the list changes size or order (push, insert, remove, discard, resize, reserve, sort, permute).

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

A pointer to the last item, or NULL.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_tail_ptr

In notebooks

Og.Native.og_vector_list_tail_ptr

igraph 1.0

igraph_vector_list_tail_ptr

See also

vector_list_get_ptr, vector_list_pop_back

Puts the caller's item at a position and destroys the item that was there.

void og_vector_list_set(og_vector_list_t *v, og_int_t pos, og_vector_t *e);

The list takes ownership of *e: the caller must not destroy it afterwards. The position is not checked.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• pos position, 0 .. size-1
• e the item to store; moved into the list

Returns

Nothing.

Complexity

O(1) plus destroying the old item

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_set

In notebooks

Og.Native.og_vector_list_set

igraph 1.0

igraph_vector_list_set

See also

vector_list_replace, vector_list_get_ptr

Exchanges the item at a position with the caller's item.

void og_vector_list_replace(
    og_vector_list_t *v,
    og_int_t pos,
    og_vector_t *e
);

After the call the list owns what *e held, and *e holds the item that was in the list; the caller now owns that one and must destroy it. The position is not checked.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• pos position, 0 .. size-1
• e in: the new item; out: the old one

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_replace

In notebooks

Og.Native.og_vector_list_replace

igraph 1.0

igraph_vector_list_replace

See also

vector_list_set, vector_list_swap_elements

Tells whether a list has no items.

og_bool_t og_vector_list_empty(const og_vector_list_t *v);

Equivalent to vector_list_size(v) == 0.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

true when the list has no items.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_empty

In notebooks

Og.Native.og_vector_list_empty

igraph 1.0

igraph_vector_list_empty

See also

vector_list_size

Returns the number of items in a list.

og_int_t og_vector_list_size(const og_vector_list_t *v);

Positions run from 0 to size-1.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

The number of items.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_size

In notebooks

Og.Native.og_vector_list_size

igraph 1.0

igraph_vector_list_size

See also

vector_list_capacity, vector_list_empty

Returns how many items fit before the list must reallocate.

og_int_t og_vector_list_capacity(const og_vector_list_t *v);

Always at least the size.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

The capacity, in items.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_capacity

In notebooks

Og.Native.og_vector_list_capacity

igraph 1.0

igraph_vector_list_capacity

See also

vector_list_reserve, vector_list_size

Destroys all items and keeps the allocated capacity.

void og_vector_list_clear(og_vector_list_t *v);

The size becomes zero; the list can be refilled without reallocating.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

Nothing.

Complexity

O(total size of the items)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_clear

In notebooks

Og.Native.og_vector_list_clear

igraph 1.0

igraph_vector_list_clear

See also

vector_list_destroy, vector_list_resize

Allocates room for at least capacity items without changing the list.

og_error_t og_vector_list_reserve(og_vector_list_t *v, og_int_t capacity);

A capacity at or below the current one does nothing. If the storage moves, pointers from get_ptr and tail_ptr become invalid.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• capacity number of items to make room for

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(capacity) for the reallocation, O(1) when nothing changes

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_reserve

In notebooks

Og.Native.og_vector_list_reserve

igraph 1.0

igraph_vector_list_reserve

See also

vector_list_capacity, vector_list_resize

Changes the number of items of a list.

og_error_t og_vector_list_resize(og_vector_list_t *v, og_int_t new_size);

Items beyond the new size are destroyed; new positions receive new, empty items. If making a new item fails, the items made so far stay, so the list can end up between its old and its new size.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• new_size new number of items, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL new_size is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(|new_size - size|) items made or destroyed, plus a possible reallocation

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_resize

In notebooks

Og.Native.og_vector_list_resize

igraph 1.0

igraph_vector_list_resize

See also

vector_list_reserve, vector_list_clear

Appends the caller's item to the list, taking ownership of it.

og_error_t og_vector_list_push_back(og_vector_list_t *v, og_vector_t *e);

The item is moved in by value, not copied: the caller must not destroy *e afterwards. If memory runs out, nothing changes and the caller still owns *e.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• e the item to move in

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

amortised O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_push_back

In notebooks

Og.Native.og_vector_list_push_back

igraph 1.0

igraph_vector_list_push_back

See also

vector_list_push_back_copy, vector_list_push_back_new, vector_list_pop_back

Appends a deep copy of an item.

og_error_t og_vector_list_push_back_copy(
    og_vector_list_t *v,
    const og_vector_t *e
);

The caller keeps *e. The copy is made before the list grows, so *e may be an item of the same list.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• e the item to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(size of the item), amortised

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_push_back_copy

In notebooks

Og.Native.og_vector_list_push_back_copy

igraph 1.0

igraph_vector_list_push_back_copy

See also

vector_list_push_back, vector_list_insert_copy

Appends a new, empty item and can return a pointer to it.

og_error_t og_vector_list_push_back_new(
    og_vector_list_t *v,
    og_vector_t **e
);

The usual way to add an item that is then filled in place. e may be NULL. The pointer stays valid only until the list changes size or order (push, insert, remove, discard, resize, reserve, sort, permute).

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• e receives a pointer to the new item; may be NULL

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

amortised O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_push_back_new

In notebooks

Og.Native.og_vector_list_push_back_new

igraph 1.0

igraph_vector_list_push_back_new

See also

vector_list_push_back, vector_list_insert_new

Takes the last item off a list and returns it; the caller then owns it.

og_vector_t og_vector_list_pop_back(og_vector_list_t *v);

The caller must destroy the returned item. Calling it on an empty list is a programming error: it stops in Open Graph's fatal handler (OG_ASSERT), not with an error code.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list; must not be empty

Returns

The removed item, by value.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_pop_back

In notebooks

Og.Native.og_vector_list_pop_back

igraph 1.0

igraph_vector_list_pop_back

See also

vector_list_discard_back, vector_list_remove, vector_list_tail_ptr

Inserts the caller's item at a position, taking ownership of it.

og_error_t og_vector_list_insert(
    og_vector_list_t *v,
    og_int_t pos,
    og_vector_t *e
);

pos runs from 0 to size (size appends); later items move up one place. On failure nothing changes and the caller still owns *e.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• pos position, 0 .. size
• e the item to move in

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL pos is outside 0 .. size
• OG_ENOMEM memory could not be allocated

Complexity

O(n)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_insert

In notebooks

Og.Native.og_vector_list_insert

igraph 1.0

igraph_vector_list_insert

See also

vector_list_insert_copy, vector_list_insert_new, vector_list_remove

Inserts a deep copy of an item at a position.

og_error_t og_vector_list_insert_copy(
    og_vector_list_t *v,
    og_int_t pos,
    const og_vector_t *e
);

The caller keeps *e. Later items move up one place. On failure the list is unchanged.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• pos position, 0 .. size
• e the item to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL pos is outside 0 .. size
• OG_ENOMEM memory could not be allocated

Complexity

O(n + size of the item)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_insert_copy

In notebooks

Og.Native.og_vector_list_insert_copy

igraph 1.0

igraph_vector_list_insert_copy

See also

vector_list_insert, vector_list_push_back_copy

Inserts a new, empty item at a position and can return a pointer to it.

og_error_t og_vector_list_insert_new(
    og_vector_list_t *v,
    og_int_t pos,
    og_vector_t **e
);

If the new item cannot be made, the list is unchanged. e may be NULL. The pointer stays valid only until the list changes size or order (push, insert, remove, discard, resize, reserve, sort, permute).

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• pos position, 0 .. size
• e receives a pointer to the new item; may be NULL

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL pos is outside 0 .. size
• OG_ENOMEM memory could not be allocated

Complexity

O(n)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_insert_new

In notebooks

Og.Native.og_vector_list_insert_new

igraph 1.0

igraph_vector_list_insert_new

See also

vector_list_insert, vector_list_push_back_new

Takes the item at a position out of the list and hands it to the caller.

og_error_t og_vector_list_remove(
    og_vector_list_t *v,
    og_int_t index,
    og_vector_t *result
);

Later items move down one place. *result receives the item; the caller owns it and must destroy it.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• index position, 0 .. size-1
• result receives the removed item

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL index is outside 0 .. size-1

Complexity

O(n)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_remove

In notebooks

Og.Native.og_vector_list_remove

igraph 1.0

igraph_vector_list_remove

See also

vector_list_remove_fast, vector_list_discard, vector_list_pop_back

Takes an item out of the list in constant time; the last item fills its place.

og_error_t og_vector_list_remove_fast(
    og_vector_list_t *v,
    og_int_t index,
    og_vector_t *result
);

*result receives the item and the caller owns it. The order of the remaining items is not kept.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• index position, 0 .. size-1
• result receives the removed item

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL index is outside 0 .. size-1

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_remove_fast

In notebooks

Og.Native.og_vector_list_remove_fast

igraph 1.0

igraph_vector_list_remove_fast

See also

vector_list_remove, vector_list_discard_fast

Destroys the item at a position and closes the gap.

void og_vector_list_discard(og_vector_list_t *v, og_int_t index);

Later items move down one place. An index outside the list is ignored.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• index position of the item to destroy

Returns

Nothing.

Complexity

O(n)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_discard

In notebooks

Og.Native.og_vector_list_discard

igraph 1.0

igraph_vector_list_discard

See also

vector_list_discard_fast, vector_list_discard_back, vector_list_remove

Destroys the last item of a list, if there is one.

void og_vector_list_discard_back(og_vector_list_t *v);

Unlike vector_list_pop_back(), the item is destroyed rather than returned.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list

Returns

Nothing.

Complexity

O(1) plus destroying the item

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_discard_back

In notebooks

Og.Native.og_vector_list_discard_back

igraph 1.0

igraph_vector_list_discard_back

See also

vector_list_pop_back, vector_list_discard

Destroys the item at a position; the last item fills its place.

void og_vector_list_discard_fast(og_vector_list_t *v, og_int_t index);

The order of the remaining items is not kept. An index outside the list is ignored.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• index position of the item to destroy

Returns

Nothing.

Complexity

O(1) plus destroying the item

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_discard_fast

In notebooks

Og.Native.og_vector_list_discard_fast

igraph 1.0

igraph_vector_list_discard_fast

See also

vector_list_discard, vector_list_remove_fast

Reorders a list: new position i receives the item at old position index[i].

og_error_t og_vector_list_permute(
    og_vector_list_t *v,
    const og_vector_int_t *index
);

index must not repeat a position or name one outside the list. It may be shorter than the list: the items it does not name are destroyed and the list shrinks to the length of index. On an invalid index the list is unchanged.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• index old position of each new position

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL index is longer than the list, repeats a position or names one outside the list
• OG_ENOMEM memory could not be allocated

Complexity

O(n)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_permute

In notebooks

Og.Native.og_vector_list_permute

igraph 1.0

igraph_vector_list_permute

See also

vector_list_sort_ind, vector_list_sort

Sorts the items of a list in place with a comparison function.

void og_vector_list_sort(
    og_vector_list_t *v,
    int (*cmp)(const og_vector_t *, const og_vector_t *)
);

cmp(a, b) returns a negative number, zero or a positive number when a sorts before, level with, or after b, as for qsort(). The sort is a heapsort (Williams 1964): no extra memory, and items that compare equal may change their relative order.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• cmp comparison function on two items

Returns

Nothing.

Complexity

O(n log n) comparisons

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_sort

In notebooks

Og.Native.og_vector_list_sort

igraph 1.0

igraph_vector_list_sort

See also

vector_list_sort_ind, vector_list_permute

Writes the positions of a list's items in sorted order, without moving them.

og_error_t og_vector_list_sort_ind(
    og_vector_list_t *v,
    og_vector_int_t *inds,
    int (*cmp)(const og_vector_t *, const og_vector_t *)
);

inds is resized to the size of the list; inds[k] is the position of the k-th item in sorted order. The sort is a stable merge sort, so items that compare equal keep their relative order. The list itself is not changed; vector_list_permute(v, inds) applies the order.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• inds receives the positions in sorted order
• cmp comparison function on two items, as for vector_list_sort()

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(n log n) comparisons, O(n) extra memory

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_sort_ind

In notebooks

Og.Native.og_vector_list_sort_ind

igraph 1.0

igraph_vector_list_sort_ind

See also

vector_list_sort, vector_list_permute

Exchanges the contents of two lists of the same type.

void og_vector_list_swap(og_vector_list_t *v1, og_vector_list_t *v2);

Only the internal pointers and counts trade places; no item is copied.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v1 first list
• v2 second list

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_swap

In notebooks

Og.Native.og_vector_list_swap

igraph 1.0

igraph_vector_list_swap

See also

vector_list_swap_elements

Exchanges two items of a list.

void og_vector_list_swap_elements(
    og_vector_list_t *v,
    og_int_t i,
    og_int_t j
);

The items trade places by value; the positions are not checked.

The list template generates this function for every list type: vector_list_t (real vectors, documented here), og_vector_int_list_t, og_matrix_list_t, og_graph_list_t and og_bitset_list_t, and og_attribute_record_list_t in the attributes area; change the prefix and the item type.

Parameters

• v the list
• i first position
• j second position

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no list type; checked by unit tests, out-of-memory runs and 20,000 random operations compared step by step with a plain model

C name

og_vector_list_swap_elements

In notebooks

Og.Native.og_vector_list_swap_elements

igraph 1.0

igraph_vector_list_swap_elements

See also

vector_list_swap, vector_list_replace

Builds a list of every vertex's neighbours.

og_error_t og_adjlist_init(
    const og_t *graph,
    og_adjlist_t *al,
    og_neimode_t mode,
    og_loops_t loops,
    og_bool_t multiple
);

Afterwards adjlist_get(al, v) is an integer vector with the neighbours of v. The list is a snapshot: it no longer refers to the graph, and its vectors belong to the list but may be changed by the caller (sorted, extended, cut).

In a directed graph mode selects out-neighbours (OG_OUT), in-neighbours (OG_IN) or both (OG_ALL); in an undirected graph it is ignored. Each vector comes sorted by neighbour id, in the order neighbors() reports. loops decides how a self-loop at v is listed: OG_NO_LOOPS leaves it out, OG_LOOPS_ONCE lists v once, OG_LOOPS_TWICE lists v twice where the loop is seen from both ends (undirected graphs and OG_ALL; with OG_OUT or OG_IN a loop appears once). With multiple false, parallel edges give one entry per neighbour (a self-loop listed twice stays twice); with true, one entry per edge.

Parameters

• graph the graph to read
• al the list to set up
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS): how a self-loop is listed
• multiple true: one entry per edge; false: parallel edges collapse to one entry

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVAL loops is not OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE
• OG_ENOMEM memory could not be allocated

Complexity

O(|V| + |E|)

Checked

identical to python-igraph 1.0's Graph.get_adjlist for every mode / loops / multiple combination: 220 random graphs (0-294 vertices, loops and multi-edges), 260 dense multigraphs, 78 graphs from python-igraph's generators and a further cross-check set

C name

og_adjlist_init

In notebooks

Og.Native.og_adjlist_init

igraph 1.0

igraph_adjlist_init

See also

adjlist_get, adjlist_destroy, inclist_init, lazy_adjlist_init, neighbors

og_t g;
og_adjlist_t al;
og_int_t v, k;
OG_CHECK(og_small(&g, 4, OG_UNDIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, -1));
OG_FINALLY(og_destroy, &g);
OG_CHECK(og_adjlist_init(&g, &al, OG_ALL, OG_NO_LOOPS, true));
OG_FINALLY(og_adjlist_destroy, &al);
for (v = 0; v < og_adjlist_size(&al); v++) {
    og_vector_int_t *neis = og_adjlist_get(&al, v);
    for (k = 0; k < og_vector_int_size(neis); k++) {
        printf("%" OG_PRId " - %" OG_PRId "\n", v, OG_VECTOR(*neis)[k]);
    }
}
og_adjlist_destroy(&al);
og_destroy(&g);
OG_FINALLY_CLEAN(2);

Creates an adjacency list of n vertices with no neighbours.

og_error_t og_adjlist_init_empty(og_adjlist_t *al, og_int_t no_of_nodes);

For building a list by hand: append to adjlist_get(al, v) with og_vector_int_push_back(). On failure the list is safe to destroy.

Parameters

• al the list to set up
• no_of_nodes number of vertices, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL no_of_nodes is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(n)

Checked

unit tests (negative size, failed allocation); used to build 200 random lists in the simplify checks

C name

og_adjlist_init_empty

In notebooks

Og.Native.og_adjlist_init_empty

igraph 1.0

igraph_adjlist_init_empty

See also

adjlist_init, adjlist_get, adjlist_simplify

Builds, for each vertex, the list of vertices it is not joined to.

og_error_t og_adjlist_init_complementer(
    const og_t *graph,
    og_adjlist_t *al,
    og_neimode_t mode,
    og_loops_t loops
);

Vertex u is in v's vector when no edge joins v to u in the direction mode selects: in an undirected graph no edge at all, in a directed graph with OG_ALL no edge in either direction. Parallel edges count as one. Each vector is sorted by vertex id.

v itself is listed only when v has no self-loop and loops is not OG_NO_LOOPS; it is listed twice for OG_LOOPS_TWICE in an undirected graph or with OG_ALL.

Parameters

• graph the graph to read
• al the list to set up
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs
• loops whether (and how often) v may appear in its own vector

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVAL loops is not OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE
• OG_ENOMEM memory could not be allocated

Complexity

O(|V|^2 + |E|)

Checked

out / in modes and undirected graphs identical to the neighbours in python-igraph 1.0's Graph.complementer (parallel edges collapsed) on 197 graphs, every mode and loops value; directed OG_ALL has no python-igraph counterpart and is checked against the definition

C name

og_adjlist_init_complementer

In notebooks

Og.Native.og_adjlist_init_complementer

igraph 1.0

igraph_adjlist_init_complementer

See also

adjlist_init, complementer

Turns an incidence list into an adjacency list that lines up with it.

og_error_t og_adjlist_init_from_inclist(
    const og_t *graph,
    og_adjlist_t *al,
    const og_inclist_t *il
);

Entry k of v's vector is the other end of the k-th edge in il's vector for v (v itself for a self-loop), so the two lists correspond entry by entry: the neighbour and the edge that leads to it. il must have been built for graph.

Parameters

• graph the graph the incidence list belongs to
• al the list to set up
• il the incidence list to convert

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL il does not have one vector per vertex of graph
• OG_EINVEID il names an edge id that graph does not have
• OG_ENOMEM memory could not be allocated

Complexity

O(|V| + total length of il)

Checked

identical to the other end of each edge for every python-igraph incidence list of the test sets (1602 random-graph lists plus the dense, structured and cross-check sets)

C name

og_adjlist_init_from_inclist

In notebooks

Og.Native.og_adjlist_init_from_inclist

igraph 1.0

igraph_adjlist_init_from_inclist

See also

inclist_init, adjlist_init

Releases an adjacency list with all its vectors.

void og_adjlist_destroy(og_adjlist_t *al);

Safe to call twice and after a failed constructor; NULL is accepted.

Parameters

• al the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests: safe twice and after every failing constructor

C name

og_adjlist_destroy

In notebooks

Og.Native.og_adjlist_destroy

igraph 1.0

igraph_adjlist_destroy

See also

adjlist_init, adjlist_clear

Gives the neighbour vector of a vertex in an adjacency list.

#define og_adjlist_get(al, no) (&(al)->adjs[(no)])

Expands to an og_vector_int_t * pointing at the list's own vector: read it, or change it in place. The vertex id is not checked.

Parameters

• al pointer to the adjacency list
• no vertex id, 0 .. size-1

Returns

A pointer to the vertex's vector (og_vector_int_t *).

Complexity

O(1)

Checked

identical to python-igraph 1.0's Graph.get_adjlist for every mode / loops / multiple combination: 220 random graphs (0-294 vertices, loops and multi-edges), 260 dense multigraphs, 78 graphs from python-igraph's generators and a further cross-check set

C name

og_adjlist_get

In notebooks

Og.AdjlistGet

igraph 1.0

igraph_adjlist_get

See also

adjlist_init, adjlist_size

Tells how many vertices an adjacency list covers.

og_int_t og_adjlist_size(const og_adjlist_t *al);

For a list built from a graph this is the graph's vertex count.

Parameters

• al the list

Returns

The number of vertices.

Complexity

O(1)

Checked

equals the vertex count on all structured test graphs

C name

og_adjlist_size

In notebooks

Og.Native.og_adjlist_size

igraph 1.0

igraph_adjlist_size

See also

adjlist_get

Empties every vertex's vector and keeps the number of vertices.

void og_adjlist_clear(og_adjlist_t *al);

The vectors keep their capacity, so the list can be refilled cheaply.

Parameters

• al the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests

C name

og_adjlist_clear

In notebooks

Og.Native.og_adjlist_clear

igraph 1.0

igraph_adjlist_clear

See also

adjlist_destroy, adjlist_init_empty

Sorts every vertex's vector in increasing order.

void og_adjlist_sort(og_adjlist_t *al);

Lists made by adjlist_init() and adjlist_init_complementer() are already sorted; this is for lists the caller has built or edited.

Parameters

• al the list

Returns

Nothing.

Complexity

O(sum over v of d(v) log d(v))

Checked

python-igraph's lists, reversed and sorted back, come out identical

C name

og_adjlist_sort

In notebooks

Og.Native.og_adjlist_sort

igraph 1.0

igraph_adjlist_sort

See also

adjlist_simplify

Removes self-references and repeated entries from every vertex's vector.

og_error_t og_adjlist_simplify(og_adjlist_t *al);

In v's vector, v itself is dropped and only the first copy of every other vertex is kept. The entries kept stay in their order, so a sorted list stays sorted and becomes strictly increasing. If an entry is out of range the call stops with an error, and the vectors before it are already simplified.

Parameters

• al the list

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVVID an entry is not in 0 .. size-1
• OG_ENOMEM memory could not be allocated

Complexity

O(|V| + total length of the vectors)

Checked

checked against a plain keep-first filter on 200 random lists; sorting and simplifying the full lists of 78 structured graphs gives python-igraph's simple adjacency lists

C name

og_adjlist_simplify

In notebooks

Og.Native.og_adjlist_simplify

igraph 1.0

igraph_adjlist_simplify

See also

adjlist_sort, adjlist_init

Builds a list of every vertex's incident edges.

og_error_t og_inclist_init(
    const og_t *graph,
    og_inclist_t *il,
    og_neimode_t mode,
    og_loops_t loops
);

Afterwards inclist_get(il, v) is an integer vector with the ids of the edges at v, in the order incident() reports them: by the neighbour at the other end. mode and loops work as for adjlist_init(): OG_NO_LOOPS leaves loop edges out, OG_LOOPS_ONCE lists a loop edge once, OG_LOOPS_TWICE twice in an undirected graph or with OG_ALL. Parallel edges are distinct edges and are always all listed.

Like an adjacency list, the result is a snapshot owned by the list.

Parameters

• graph the graph to read
• il the list to set up
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS): how a self-loop is listed

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVAL loops is not OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE
• OG_ENOMEM memory could not be allocated

Complexity

O(|V| + |E|)

Checked

identical to python-igraph 1.0's Graph.get_inclist for every mode / loops combination on the same random, dense, structured and cross-check graph sets

C name

og_inclist_init

In notebooks

Og.Native.og_inclist_init

igraph 1.0

igraph_inclist_init

See also

inclist_get, inclist_destroy, adjlist_init_from_inclist, lazy_inclist_init, incident

Releases an incidence list with all its vectors.

void og_inclist_destroy(og_inclist_t *il);

Safe to call twice and after a failed inclist_init(); NULL is accepted.

Parameters

• il the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests: safe twice and after a failing constructor

C name

og_inclist_destroy

In notebooks

Og.Native.og_inclist_destroy

igraph 1.0

igraph_inclist_destroy

See also

inclist_init

Gives the incident-edge vector of a vertex in an incidence list.

#define og_inclist_get(il, no) (&(il)->incs[(no)])

Expands to an og_vector_int_t * pointing at the list's own vector. The vertex id is not checked.

Parameters

• il pointer to the incidence list
• no vertex id, 0 .. size-1

Returns

A pointer to the vertex's vector of edge ids (og_vector_int_t *).

Complexity

O(1)

Checked

identical to python-igraph 1.0's Graph.get_inclist for every mode / loops combination on the same random, dense, structured and cross-check graph sets

C name

og_inclist_get

In notebooks

Og.InclistGet

igraph 1.0

igraph_inclist_get

See also

inclist_init, inclist_size

Tells how many vertices an incidence list covers.

og_int_t og_inclist_size(const og_inclist_t *il);

For a list built from a graph this is the graph's vertex count.

Parameters

• il the list

Returns

The number of vertices.

Complexity

O(1)

Checked

equals the vertex count on all structured test graphs

C name

og_inclist_size

In notebooks

Og.Native.og_inclist_size

igraph 1.0

igraph_inclist_size

See also

inclist_get

Empties every vertex's vector and keeps the number of vertices.

void og_inclist_clear(og_inclist_t *il);

The vectors keep their capacity.

Parameters

• il the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests

C name

og_inclist_clear

In notebooks

Og.Native.og_inclist_clear

igraph 1.0

igraph_inclist_clear

See also

inclist_destroy

Sets up an adjacency list that reads a vertex's neighbours only when first asked.

og_error_t og_lazy_adjlist_init(
    const og_t *graph,
    og_lazy_adjlist_t *al,
    og_neimode_t mode,
    og_loops_t loops,
    og_bool_t multiple
);

Nothing is read from the graph here. lazy_adjlist_get() fills a vertex's vector on its first lookup and returns the stored vector after that; the vectors are the ones adjlist_init() would build with the same arguments. This pays off when an algorithm visits only part of the graph.

The list keeps a pointer to graph: the graph must stay alive and unchanged while the list is in use.

Parameters

• graph the graph to read later
• al the list to set up
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS): how a self-loop is listed
• multiple true: one entry per edge; false: parallel edges collapse to one entry

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVAL loops is not OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE
• OG_ENOMEM memory could not be allocated

Complexity

O(|V|) here; O(d(v)) for the first lookup of v

Checked

every python-igraph adjacency list of the test sets (3078 on random graphs, plus the dense, structured and cross-check sets) reproduced through the lazy list, vertices visited in scrambled order

C name

og_lazy_adjlist_init

In notebooks

Og.Native.og_lazy_adjlist_init

igraph 1.0

igraph_lazy_adjlist_init

See also

lazy_adjlist_get, lazy_adjlist_has, lazy_adjlist_destroy, adjlist_init

og_lazy_adjlist_t al;
og_vector_int_t *neis;
OG_CHECK(og_lazy_adjlist_init(&g, &al, OG_OUT, OG_NO_LOOPS, false));
OG_FINALLY(og_lazy_adjlist_destroy, &al);
neis = og_lazy_adjlist_get(&al, 0);   /* vertex 0 is read now */
OG_CHECK_OOM(neis, "Cannot read the neighbours of vertex 0.");
/* ... use neis; a second lookup of 0 returns the same vector ... */
og_lazy_adjlist_destroy(&al);
OG_FINALLY_CLEAN(1);

Releases a lazy adjacency list and whatever vectors it stored.

void og_lazy_adjlist_destroy(og_lazy_adjlist_t *al);

Safe to call twice and after a failed lazy_adjlist_init(); NULL is accepted. The graph is not touched.

Parameters

• al the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests: safe twice and after a failing constructor

C name

og_lazy_adjlist_destroy

In notebooks

Og.Native.og_lazy_adjlist_destroy

igraph 1.0

igraph_lazy_adjlist_destroy

See also

lazy_adjlist_init

Returns a vertex's neighbour vector, reading it from the graph on first use.

#define og_lazy_adjlist_get(al, no) og_i_lazy_adjlist_get((al), (no))

Expands to an og_vector_int_t * owned by the list. It yields NULL after an error, which has already been reported to the error handler: OG_ENOMEM on a first lookup, or OG_EINVVID when no is not a vertex of the list. Check the result for NULL before using it.

Parameters

• al pointer to the lazy list
• no vertex id

Returns

A pointer to the vertex's neighbour vector, or NULL after an error.

Errors

• OG_EINVVID no is not in 0 .. size-1 (result NULL)
• OG_ENOMEM the first lookup could not store the vector (result NULL)

Complexity

O(d(v)) for the first lookup of v, O(1) afterwards

Checked

every python-igraph adjacency list of the test sets reproduced through the lazy list, vertices visited in scrambled order; second lookups return the stored vector

C name

og_lazy_adjlist_get

igraph 1.0

igraph_lazy_adjlist_get

See also

lazy_adjlist_has, lazy_adjlist_init, adjlist_get

Tells whether a vertex's neighbours have been read already.

#define og_lazy_adjlist_has(al, no) ((al)->adjs[(no)].data != NULL)

Expands to a true/false expression. The vertex id is not checked.

Parameters

• al pointer to the lazy list
• no vertex id, 0 .. size-1

Returns

true when the vertex has been looked up since the list was made or cleared.

Complexity

O(1)

Checked

unit tests: false before and true after the first lookup of every vertex of the structured and cross-check graphs, false again after a clear

C name

og_lazy_adjlist_has

In notebooks

Og.LazyAdjlistHas

igraph 1.0

igraph_lazy_adjlist_has

See also

lazy_adjlist_get, lazy_adjlist_clear

Tells how many vertices a lazy adjacency list covers.

og_int_t og_lazy_adjlist_size(const og_lazy_adjlist_t *al);

This is the graph's vertex count at the time the list was made.

Parameters

• al the list

Returns

The number of vertices.

Complexity

O(1)

Checked

equals the vertex count on all structured test graphs

C name

og_lazy_adjlist_size

In notebooks

Og.Native.og_lazy_adjlist_size

igraph 1.0

igraph_lazy_adjlist_size

See also

lazy_adjlist_get

Forgets every stored neighbour vector of a lazy adjacency list.

void og_lazy_adjlist_clear(og_lazy_adjlist_t *al);

The stored vectors are freed and lazy_adjlist_has() becomes false for every vertex; later lookups read the graph again. Pointers returned by earlier lookups become invalid.

Parameters

• al the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests: after a clear, lookups on 60 random multigraphs give the eager lists again

C name

og_lazy_adjlist_clear

In notebooks

Og.Native.og_lazy_adjlist_clear

igraph 1.0

igraph_lazy_adjlist_clear

See also

lazy_adjlist_has, lazy_adjlist_destroy

Sets up an incidence list that reads a vertex's incident edges only when first asked.

og_error_t og_lazy_inclist_init(
    const og_t *graph,
    og_lazy_inclist_t *il,
    og_neimode_t mode,
    og_loops_t loops
);

Nothing is read from the graph here. lazy_inclist_get() fills a vertex's vector of edge ids on its first lookup and returns the stored vector after that; the vectors are the ones inclist_init() would build with the same arguments.

The list keeps a pointer to graph: the graph must stay alive and unchanged while the list is in use.

Parameters

• graph the graph to read later
• il the list to set up
• mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs
• loops OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE (= OG_LOOPS): how a self-loop is listed

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
• OG_EINVAL loops is not OG_NO_LOOPS, OG_LOOPS_ONCE or OG_LOOPS_TWICE
• OG_ENOMEM memory could not be allocated

Complexity

O(|V|) here; O(d(v)) for the first lookup of v

Checked

every python-igraph incidence list of the test sets (1602 on random graphs, plus the dense, structured and cross-check sets) reproduced through the lazy list, vertices visited in scrambled order

C name

og_lazy_inclist_init

In notebooks

Og.Native.og_lazy_inclist_init

igraph 1.0

igraph_lazy_inclist_init

See also

lazy_inclist_get, lazy_inclist_has, lazy_inclist_destroy, inclist_init

Releases a lazy incidence list and whatever vectors it stored.

void og_lazy_inclist_destroy(og_lazy_inclist_t *il);

Safe to call twice and after a failed lazy_inclist_init(); NULL is accepted. The graph is not touched.

Parameters

• il the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests: safe twice and after a failing constructor

C name

og_lazy_inclist_destroy

In notebooks

Og.Native.og_lazy_inclist_destroy

igraph 1.0

igraph_lazy_inclist_destroy

See also

lazy_inclist_init

Returns a vertex's incident-edge vector, reading it from the graph on first use.

#define og_lazy_inclist_get(il, no) og_i_lazy_inclist_get((il), (no))

Expands to an og_vector_int_t * owned by the list. It yields NULL after an error, which has already been reported to the error handler: OG_ENOMEM on a first lookup, or OG_EINVVID when no is not a vertex of the list. Check the result for NULL before using it.

Parameters

• il pointer to the lazy list
• no vertex id

Returns

A pointer to the vertex's vector of edge ids, or NULL after an error.

Errors

• OG_EINVVID no is not in 0 .. size-1 (result NULL)
• OG_ENOMEM the first lookup could not store the vector (result NULL)

Complexity

O(d(v)) for the first lookup of v, O(1) afterwards

Checked

every python-igraph incidence list of the test sets reproduced through the lazy list, vertices visited in scrambled order

C name

og_lazy_inclist_get

igraph 1.0

igraph_lazy_inclist_get

See also

lazy_inclist_has, lazy_inclist_init, inclist_get

Tells whether a vertex's incident edges have been read already.

#define og_lazy_inclist_has(il, no) ((il)->incs[(no)].data != NULL)

Expands to a true/false expression. The vertex id is not checked.

Parameters

• il pointer to the lazy list
• no vertex id, 0 .. size-1

Returns

true when the vertex has been looked up since the list was made or cleared.

Complexity

O(1)

Checked

unit tests: false before and true after the first lookup of every vertex of the structured and cross-check graphs, false again after a clear

C name

og_lazy_inclist_has

In notebooks

Og.LazyInclistHas

igraph 1.0

igraph_lazy_inclist_has

See also

lazy_inclist_get, lazy_inclist_clear

Tells how many vertices a lazy incidence list covers.

og_int_t og_lazy_inclist_size(const og_lazy_inclist_t *il);

This is the graph's vertex count at the time the list was made.

Parameters

• il the list

Returns

The number of vertices.

Complexity

O(1)

Checked

equals the vertex count on all structured test graphs

C name

og_lazy_inclist_size

In notebooks

Og.Native.og_lazy_inclist_size

igraph 1.0

igraph_lazy_inclist_size

See also

lazy_inclist_get

Forgets every stored incident-edge vector of a lazy incidence list.

void og_lazy_inclist_clear(og_lazy_inclist_t *il);

The stored vectors are freed and lazy_inclist_has() becomes false for every vertex; later lookups read the graph again. Pointers returned by earlier lookups become invalid.

Parameters

• il the list

Returns

Nothing.

Complexity

O(|V|)

Checked

unit tests: after a clear, lookups on 60 random multigraphs give the eager lists again

C name

og_lazy_inclist_clear

In notebooks

Og.Native.og_lazy_inclist_clear

igraph 1.0

igraph_lazy_inclist_clear

See also

lazy_inclist_has, lazy_inclist_destroy

Creates a prefix sum tree over size items, all with value zero.

og_error_t og_psumtree_init(og_psumtree_t *t, og_int_t size);

A prefix sum tree keeps non-negative values together with the sum of every subtree, so changing one value and drawing an item with probability proportional to its value both take O(log n) steps (Wong and Easton, SIAM J. Comput. 1980). Items are numbered 0 .. size-1; internally the leaves are padded to a power of two. A size of zero is accepted. On failure the tree is safe to destroy.

Parameters

• t the tree to set up
• size number of items, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL size is negative
• OG_ENOMEM size is too large, or memory could not be allocated

Complexity

O(size)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_init

In notebooks

Og.Native.og_psumtree_init

igraph 1.0

igraph_psumtree_init

See also

psumtree_update, psumtree_search, psumtree_destroy

og_psumtree_t t;
og_int_t pick;
OG_PSUMTREE_INIT_FINALLY(&t, 3);
OG_CHECK(og_psumtree_update(&t, 0, 1.0));
OG_CHECK(og_psumtree_update(&t, 2, 3.0));   /* item 1 keeps value 0 */
/* item 2 comes out three times as often as item 0; item 1 never */
OG_CHECK(og_psumtree_search(&t, &pick, OG_RNG_UNIF(0, og_psumtree_sum(&t))));
og_psumtree_destroy(&t);
OG_FINALLY_CLEAN(1);

Frees a prefix sum tree.

void og_psumtree_destroy(og_psumtree_t *t);

Safe to call twice and after a failed psumtree_init(); NULL is accepted.

Parameters

• t the tree

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_destroy

In notebooks

Og.Native.og_psumtree_destroy

igraph 1.0

igraph_psumtree_destroy

See also

psumtree_init

Tells how many items a prefix sum tree holds.

og_int_t og_psumtree_size(const og_psumtree_t *t);

The padding leaves are not counted.

Parameters

• t the tree

Returns

The number of items.

Complexity

O(1)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_size

In notebooks

Og.Native.og_psumtree_size

igraph 1.0

igraph_psumtree_size

See also

psumtree_get

Returns the value of one item.

og_real_t og_psumtree_get(const og_psumtree_t *t, og_int_t idx);

The index is not checked; it must be in 0 .. size-1.

Parameters

• t the tree
• idx item, 0 .. size-1

Returns

The item's value.

Complexity

O(1)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_get

In notebooks

Og.Native.og_psumtree_get

igraph 1.0

igraph_psumtree_get

See also

psumtree_update, psumtree_sum

Returns the total of all item values.

og_real_t og_psumtree_sum(const og_psumtree_t *t);

Read from the root, which every update keeps current.

Parameters

• t the tree

Returns

The total of the values.

Complexity

O(1)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_sum

In notebooks

Og.Native.og_psumtree_sum

igraph 1.0

igraph_psumtree_sum

See also

psumtree_search, psumtree_get

Maps a number in [0, total) to the item whose share of the running total contains it.

og_error_t og_psumtree_search(
    const og_psumtree_t *t,
    og_int_t *idx,
    og_real_t search
);

Give item i the half-open range [S(i), S(i) + value(i)), where S(i) is the sum of the values of the items before it. For search in [0, total) the result is the item whose range holds search. Drawing search uniformly from [0, total) therefore picks item i with probability value(i) / total, and items of value zero are never picked.

A value at or beyond the total gives the last item with a positive value; when every value is zero the result is item 0.

Parameters

• t the tree
• idx receives the item found
• search the value to look up, normally in [0, sum)

Returns

OG_SUCCESS (the search itself cannot fail).

Complexity

O(log n)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_search

In notebooks

Og.Native.og_psumtree_search

igraph 1.0

igraph_psumtree_search

See also

psumtree_sum, psumtree_update

Gives one item a new value and refreshes the sums above it.

og_error_t og_psumtree_update(
    og_psumtree_t *t,
    og_int_t idx,
    og_real_t new_value
);

The sums on the path to the root are recomputed from their two children, so many updates do not accumulate rounding drift. +infinity is accepted.

Parameters

• t the tree
• idx item, 0 .. size-1
• new_value the new value; non-negative

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL new_value is negative or NaN
• OG_EINVAL idx is outside 0 .. size-1

Complexity

O(log n)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_update

In notebooks

Og.Native.og_psumtree_update

igraph 1.0

igraph_psumtree_update

See also

psumtree_get, psumtree_reset

Sets every value of a prefix sum tree to zero.

void og_psumtree_reset(og_psumtree_t *t);

The number of items does not change.

Parameters

• t the tree

Returns

Nothing.

Complexity

O(n)

Checked

python-igraph has no prefix sum tree; search checked against a linear scan on random trees of 1-300 items before and after updates, and sampling frequencies with a chi-square test over 200,000 draws

C name

og_psumtree_reset

In notebooks

Og.Native.og_psumtree_reset

igraph 1.0

igraph_psumtree_reset

See also

psumtree_update, psumtree_init

Creates a bitset of size bits, all zero.

og_error_t og_bitset_init(og_bitset_t *bitset, og_int_t size);

Bits are packed into 64-bit words: bit i is in word i / 64 at position i % 64, bit 0 being the lowest bit of word 0, and OG_VECTOR(bs) is the word array. Single bits are set, cleared and read with OG_BIT_SET(bs, i), OG_BIT_CLEAR(bs, i) and OG_BIT_TEST(bs, i) (og/vectors.h), which take the bitset itself rather than a pointer and do not check i.

The functions of this group keep the unused bits of the last word zero. The capacity is at least one word. On failure the bitset is safe to destroy.

Parameters

• bitset the bitset to set up
• size number of bits, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL size is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_init

In notebooks

Og.Native.og_bitset_init

igraph 1.0

igraph_bitset_init

See also

bitset_destroy, bitset_popcount, bitset_resize, bitset_fill

og_bitset_t seen;
OG_BITSET_INIT_FINALLY(&seen, 100);
OG_BIT_SET(seen, 3);
OG_BIT_SET(seen, 64);
if (OG_BIT_TEST(seen, 64)) {
    printf("%" OG_PRId " bits set\n", og_bitset_popcount(&seen));   /* 2 */
}
og_bitset_destroy(&seen);
OG_FINALLY_CLEAN(1);

Creates a bitset with the same size and bits as another.

og_error_t og_bitset_init_copy(og_bitset_t *dest, const og_bitset_t *src);

The copy owns its own storage. On failure dest is safe to destroy.

Parameters

• dest the bitset to set up
• src the bitset to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_init_copy

In notebooks

Og.Native.og_bitset_init_copy

igraph 1.0

igraph_bitset_init_copy

See also

bitset_update, bitset_init

Frees a bitset.

void og_bitset_destroy(og_bitset_t *bitset);

Safe to call twice and after a failed constructor; NULL is accepted.

Parameters

• bitset the bitset

Returns

Nothing.

Complexity

O(1)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_destroy

In notebooks

Og.Native.og_bitset_destroy

igraph 1.0

igraph_bitset_destroy

See also

bitset_init

Sets every bit of a bitset to the same value.

void og_bitset_fill(og_bitset_t *bitset, og_bool_t value);

Only the bits in use change; the unused bits of the last word stay zero.

Parameters

• bitset the bitset
• value true sets every bit, false clears every bit

Returns

Nothing.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_fill

In notebooks

Og.Native.og_bitset_fill

igraph 1.0

igraph_bitset_fill

See also

bitset_null

Sets every bit of a bitset to zero.

void og_bitset_null(og_bitset_t *bitset);

Same as bitset_fill(bitset, false).

Parameters

• bitset the bitset

Returns

Nothing.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_null

In notebooks

Og.Native.og_bitset_null

igraph 1.0

igraph_bitset_null

See also

bitset_fill

Combines two bitsets bit by bit with OR, writing the result into a third.

void og_bitset_or(
    og_bitset_t *dest,
    const og_bitset_t *src1,
    const og_bitset_t *src2
);

All bitsets involved must have the same size; this is not checked (dest's size is used). dest may be one of the sources. Runs on Open Graph's SIMD kernels (AVX-512, AVX2 or NEON where the CPU has them, plain C otherwise); every path gives the same bits.

Parameters

• dest receives the result
• src1 first operand
• src2 second operand

Returns

Nothing.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

SIMD

The word-by-word union runs on the SIMD kernel bits_or (AVX-512, AVX2, NEON or plain C, chosen at run time); integer work, so every path gives the same bits.

C name

og_bitset_or

In notebooks

Og.Native.og_bitset_or

igraph 1.0

igraph_bitset_or

See also

bitset_and, bitset_xor, bitset_not

Combines two bitsets bit by bit with AND, writing the result into a third.

void og_bitset_and(
    og_bitset_t *dest,
    const og_bitset_t *src1,
    const og_bitset_t *src2
);

All bitsets involved must have the same size; this is not checked (dest's size is used). dest may be one of the sources. Runs on Open Graph's SIMD kernels (AVX-512, AVX2 or NEON where the CPU has them, plain C otherwise); every path gives the same bits.

Parameters

• dest receives the result
• src1 first operand
• src2 second operand

Returns

Nothing.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

SIMD

The word-by-word intersection runs on the SIMD kernel bits_and (AVX-512, AVX2, NEON or plain C, chosen at run time); every path gives the same bits.

C name

og_bitset_and

In notebooks

Og.Native.og_bitset_and

igraph 1.0

igraph_bitset_and

See also

bitset_or, bitset_xor, bitset_not

Combines two bitsets bit by bit with exclusive OR, writing the result into a third.

void og_bitset_xor(
    og_bitset_t *dest,
    const og_bitset_t *src1,
    const og_bitset_t *src2
);

All bitsets involved must have the same size; this is not checked (dest's size is used). dest may be one of the sources. Runs on Open Graph's SIMD kernels (AVX-512, AVX2 or NEON where the CPU has them, plain C otherwise); every path gives the same bits.

Parameters

• dest receives the result
• src1 first operand
• src2 second operand

Returns

Nothing.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

SIMD

The word-by-word exclusive or runs on the SIMD kernel bits_xor (AVX-512, AVX2, NEON or plain C, chosen at run time); every path gives the same bits.

C name

og_bitset_xor

In notebooks

Og.Native.og_bitset_xor

igraph 1.0

igraph_bitset_xor

See also

bitset_or, bitset_and, bitset_not

Writes a bitset with every bit flipped.

void og_bitset_not(og_bitset_t *dest, const og_bitset_t *src);

dest and src must have the same size; this is not checked. dest may be src. The unused bits of the last word stay zero.

Parameters

• dest receives the result
• src the bitset to complement

Returns

Nothing.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_not

In notebooks

Og.Native.og_bitset_not

igraph 1.0

igraph_bitset_not

See also

bitset_xor, bitset_fill

Counts the bits that are set.

og_int_t og_bitset_popcount(const og_bitset_t *bitset);

Whole words go through Open Graph's SIMD bit-count kernel (POPCNT, AVX-512 VPOPCNTDQ or NEON CNT, plain C otherwise); the last word is masked to the bits in use, so stray bits written through OG_VECTOR() beyond the size are not counted.

Parameters

• bitset the bitset

Returns

The number of bits set.

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

SIMD

The count runs on the SIMD popcount kernel (VPOPCNTDQ, POPCNT or NEON CNT where the CPU has it); every path gives the same count.

C name

og_bitset_popcount

In notebooks

Og.Native.og_bitset_popcount

igraph 1.0

igraph_bitset_popcount

See also

bitset_is_any_one, bitset_countr_zero

Counts the zero bits from the highest bit (bit size-1) downward, up to the first one bit.

og_int_t og_bitset_countl_zero(const og_bitset_t *bitset);

Returns the size when every bit is zero, and 0 for an empty bitset. Bits beyond the size are ignored.

Parameters

• bitset the bitset

Returns

The length of the run.

Complexity

O(size / 64) at most; stops at the first word that ends the run

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_countl_zero

In notebooks

Og.Native.og_bitset_countl_zero

igraph 1.0

igraph_bitset_countl_zero

See also

bitset_countl_one, bitset_countr_zero, bitset_countr_one

Counts the one bits from the highest bit (bit size-1) downward, up to the first zero bit.

og_int_t og_bitset_countl_one(const og_bitset_t *bitset);

Returns the size when every bit is one, and 0 for an empty bitset. Bits beyond the size are ignored.

Parameters

• bitset the bitset

Returns

The length of the run.

Complexity

O(size / 64) at most; stops at the first word that ends the run

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_countl_one

In notebooks

Og.Native.og_bitset_countl_one

igraph 1.0

igraph_bitset_countl_one

See also

bitset_countl_zero, bitset_countr_zero, bitset_countr_one

Counts the zero bits from bit 0 upward, up to the first one bit.

og_int_t og_bitset_countr_zero(const og_bitset_t *bitset);

Returns the size when every bit is zero, and 0 for an empty bitset. This equals the index of the lowest set bit. Bits beyond the size are ignored.

Parameters

• bitset the bitset

Returns

The length of the run.

Complexity

O(size / 64) at most; stops at the first word that ends the run

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_countr_zero

In notebooks

Og.Native.og_bitset_countr_zero

igraph 1.0

igraph_bitset_countr_zero

See also

bitset_countl_zero, bitset_countl_one, bitset_countr_one

Counts the one bits from bit 0 upward, up to the first zero bit.

og_int_t og_bitset_countr_one(const og_bitset_t *bitset);

Returns the size when every bit is one, and 0 for an empty bitset. This equals the index of the lowest clear bit. Bits beyond the size are ignored.

Parameters

• bitset the bitset

Returns

The length of the run.

Complexity

O(size / 64) at most; stops at the first word that ends the run

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_countr_one

In notebooks

Og.Native.og_bitset_countr_one

igraph 1.0

igraph_bitset_countr_one

See also

bitset_countl_zero, bitset_countl_one, bitset_countr_zero

Tells whether no bit of a bitset is set.

og_bool_t og_bitset_is_all_zero(const og_bitset_t *bitset);

Gives true for an empty bitset. Bits beyond the size are ignored; the scan stops at the first word that decides the answer.

Parameters

• bitset the bitset

Returns

true or false.

Complexity

O(size / 64) at most

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_is_all_zero

In notebooks

Og.Native.og_bitset_is_all_zero

igraph 1.0

igraph_bitset_is_all_zero

See also

bitset_is_all_one, bitset_is_any_zero, bitset_is_any_one, bitset_popcount

Tells whether every bit of a bitset is set.

og_bool_t og_bitset_is_all_one(const og_bitset_t *bitset);

Gives true for an empty bitset. Bits beyond the size are ignored; the scan stops at the first word that decides the answer.

Parameters

• bitset the bitset

Returns

true or false.

Complexity

O(size / 64) at most

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_is_all_one

In notebooks

Og.Native.og_bitset_is_all_one

igraph 1.0

igraph_bitset_is_all_one

See also

bitset_is_all_zero, bitset_is_any_zero, bitset_is_any_one, bitset_popcount

Tells whether at least one bit of a bitset is clear.

og_bool_t og_bitset_is_any_zero(const og_bitset_t *bitset);

Gives false for an empty bitset. Bits beyond the size are ignored; the scan stops at the first word that decides the answer.

Parameters

• bitset the bitset

Returns

true or false.

Complexity

O(size / 64) at most

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_is_any_zero

In notebooks

Og.Native.og_bitset_is_any_zero

igraph 1.0

igraph_bitset_is_any_zero

See also

bitset_is_all_zero, bitset_is_all_one, bitset_is_any_one, bitset_popcount

Tells whether at least one bit of a bitset is set.

og_bool_t og_bitset_is_any_one(const og_bitset_t *bitset);

Gives false for an empty bitset. Bits beyond the size are ignored; the scan stops at the first word that decides the answer.

Parameters

• bitset the bitset

Returns

true or false.

Complexity

O(size / 64) at most

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_is_any_one

In notebooks

Og.Native.og_bitset_is_any_one

igraph 1.0

igraph_bitset_is_any_one

See also

bitset_is_all_zero, bitset_is_all_one, bitset_is_any_zero, bitset_popcount

Tells how many bits a bitset holds.

og_int_t og_bitset_size(const og_bitset_t *bitset);

Bits are numbered 0 .. size-1.

Parameters

• bitset the bitset

Returns

The number of bits.

Complexity

O(1)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_size

In notebooks

Og.Native.og_bitset_size

igraph 1.0

igraph_bitset_size

See also

bitset_capacity, bitset_resize

Returns how many bits fit before the bitset must reallocate.

og_int_t og_bitset_capacity(const og_bitset_t *bitset);

Always a multiple of 64 and at least the size.

Parameters

• bitset the bitset

Returns

The capacity, in bits.

Complexity

O(1)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_capacity

In notebooks

Og.Native.og_bitset_capacity

igraph 1.0

igraph_bitset_capacity

See also

bitset_reserve, bitset_size

Allocates storage for at least capacity bits.

og_error_t og_bitset_reserve(og_bitset_t *bitset, og_int_t capacity);

Size and bits do not change; the capacity is rounded up to whole 64-bit words. A capacity at or below the current one does nothing.

Parameters

• bitset the bitset
• capacity number of bits to make room for

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(capacity / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_reserve

In notebooks

Og.Native.og_bitset_reserve

igraph 1.0

igraph_bitset_reserve

See also

bitset_capacity, bitset_resize

Changes the number of bits of a bitset; new bits are zero.

og_error_t og_bitset_resize(og_bitset_t *bitset, og_int_t new_size);

Shrinking drops the highest bits. Bits that come back into use after a shrink and a grow are zero, not their old values. When more room is needed the capacity grows geometrically.

Parameters

• bitset the bitset
• new_size new number of bits, zero or more

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_EINVAL new_size is negative
• OG_ENOMEM memory could not be allocated

Complexity

O(|new_size - size| / 64), plus a reallocation when growing past the capacity

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_resize

In notebooks

Og.Native.og_bitset_resize

igraph 1.0

igraph_bitset_resize

See also

bitset_reserve, bitset_size

Makes one bitset a copy of another, size included.

og_error_t og_bitset_update(og_bitset_t *dest, const og_bitset_t *src);

dest is resized to src's size and takes its bits. Updating a bitset from itself does nothing.

Parameters

• dest the bitset that is overwritten
• src the bitset to copy

Returns

OG_SUCCESS, or an error code (see errors).

Errors

• OG_ENOMEM memory could not be allocated

Complexity

O(size / 64)

Checked

python-igraph has no bitset; compared with a plain array of Booleans on sizes 0-1100 (word boundaries included) at five densities, and 6,000 random operations with resizes and aliased operands

C name

og_bitset_update

In notebooks

Og.Native.og_bitset_update

igraph 1.0

igraph_bitset_update

See also

bitset_init_copy