Movatterモバイル変換

[0]ホーム
URL:

igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 14. Graph cycles

1. Finding cycles

1.1. igraph_find_cycle — Finds a single cycle in the graph.

igraph_error_t igraph_find_cycle(const igraph_t *graph,                                 igraph_vector_int_t *vertices,                                 igraph_vector_int_t *edges,                                 igraph_neimode_t mode);

Warning

This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.

This function returns a cycle of the graph, if there is one. If the graphis acyclic, it returns empty vectors.

Arguments: 

graph:

The input graph.

vertices:

Pointer to an integer vector. If a cycle is found, its vertices will be stored here. Otherwise the vector will be empty.

edges:

Pointer to an integer vector. If a cycle is found, its edges will be stored here. Otherwise the vector will be empty.

mode:

A constant specifying how edge directions are considered in directed graphs. Valid modes are:IGRAPH_OUT, follows edge directions;IGRAPH_IN, follows the opposite directions; andIGRAPH_ALL, ignores edge directions. This argument is ignored for undirected graphs.

Returns: 

Error code.

Time complexity: O(|V|+|E|), where |V| and |E| are the number ofvertices and edges in the original input graph.

See also: 

igraph_is_acyclic() to determine if a graph is acyclic,without returning a specific cycle;igraph_simple_cycles()to list all cycles in a graph.

1.2. igraph_simple_cycles — Finds all simple cycles.

igraph_error_t igraph_simple_cycles(        const igraph_t *graph,        igraph_vector_int_list_t *vertices,        igraph_vector_int_list_t *edges,        igraph_neimode_t mode,        igraph_integer_t min_cycle_length,        igraph_integer_t max_cycle_length);

Warning

This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.

This function searches for all simple cycles using Johnson's cycledetection algorithm, and stores them in the provided vector lists.A simple cycle is a cycle (i.e. closed path) without repeated vertices.

Reference:

Johnson DB: Finding all the elementary circuits of a directed graph.SIAM J. Comput. 4(1):77-84.https://doi.org/10.1137/0204007

Arguments: 

graph:

The graph to search for cycles in.

vertices:

The vertex IDs of each cycle will be stored here.

edges:

The edge IDs of each cycle will be stored here.

mode:

A constant specifying how edge directions are considered in directed graphs. Valid modes are:IGRAPH_OUT, follows edge directions;IGRAPH_IN, follows the opposite directions; andIGRAPH_ALL, ignores edge directions. This argument is ignored for undirected graphs.

min_cycle_length:

Limit the minimum length of cycles to search for. Pass a negative value to search for all cycles.

max_cycle_length:

Limit the maximum length of cycles to search for. Pass a negative value to search for all cycles.

Returns: 

Error code.

See also: 

igraph_simple_cycles_callback() to call a function for each foundcycle;igraph_find_cycle() to find a single cycle;igraph_fundamental_cycles() andigraph_minimum_cycle_basis()to find a cycle basis, a compact representation of the cycle structureof the graph.

1.3. igraph_simple_cycles_callback — Finds all simple cycles (callback version).

igraph_error_t igraph_simple_cycles_callback(        const igraph_t *graph,        igraph_neimode_t mode,        igraph_integer_t min_cycle_length,        igraph_integer_t max_cycle_length,        igraph_cycle_handler_t *callback,        void *arg);

Warning

This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.

This function searches for all simple cycles using Johnson's cycledetection algorithm, and calls a function for each.A simple cycle is a cycle (i.e. closed path) without repeated vertices.

Reference:

Johnson DB: Finding all the elementary circuits of a directed graph.SIAM J. Comput. 4(1):77-84.https://doi.org/10.1137/0204007

Arguments: 

graph:

The graph to search for

mode:

A constant specifying how edge directions are considered in directed graphs. Valid modes are:IGRAPH_OUT, follows edge directions;IGRAPH_IN, follows the opposite directions; andIGRAPH_ALL, ignores edge directions. This argument is ignored for undirected graphs.

min_cycle_length:

Limit the minimum length of cycles to search for. Pass a negative value to search for all cycles.

max_cycle_length:

Limit the maximum length of cycles to search for. Pass a negative value to search for all cycles.

callback:

A function to call for each cycle that is found. See alsoigraph_cycle_handler_t

arg:

This parameter will be passed tocallback.

Returns: 

Error code.

See also: 

igraph_simple_cycles() to store the found cycles;igraph_find_cycle() to find a single cycle;igraph_fundamental_cycles() and igraph_minimum_cycle_basis()to find a cycle basis, a compact representation of the cycle structureof the graph.

1.4. igraph_cycle_handler_t — Type of cycle handler functions.

typedef igraph_error_t igraph_cycle_handler_t(        const igraph_vector_int_t *vertices,        const igraph_vector_int_t *edges,        void *arg);

Callback type, called byigraph_simple_cycles_callback() whena cycle is found.

Arguments: 

vertices:

The vertices of the current cycle. Must not be modified.

edges:

The edges of the current cycle. Must not be modified.

arg:

The extra parameter passed toigraph_simple_cycles_callback()

Returns: 

Error code;IGRAPH_SUCCESS to continue the search orIGRAPH_STOP to stop the search without signaling an error.

1.5. igraph_is_acyclic — Checks whether a graph is acyclic or not.

igraph_error_t igraph_is_acyclic(const igraph_t *graph, igraph_bool_t *res);

This function checks whether a graph has any cycles. Edge directions areconsidered, i.e. in directed graphs, only directed cycles are searched for.

Arguments: 

graph:

The input graph.

res:

Pointer to a boolean constant, the result is stored here.

Returns: 

Error code.

See also: 

igraph_find_cycle() to find a cycle that demonstratesthat the graph is not acyclic;igraph_is_forest() to lookfor undirected cycles even in directed graphs.

Time complexity: O(|V|+|E|), where |V| and |E| are the number ofvertices and edges in the original input graph.

2. Eulerian cycles and paths

These functions calculate whether an Eulerian path or cycle existsand if so, can find them.

2.1. igraph_is_eulerian — Checks whether an Eulerian path or cycle exists.

igraph_error_t igraph_is_eulerian(const igraph_t *graph, igraph_bool_t *has_path, igraph_bool_t *has_cycle);

An Eulerian path traverses each edge of the graph precisely once. A closedEulerian path is referred to as an Eulerian cycle.

Arguments: 

graph:

The graph object.

has_path:

Pointer to a Boolean, will be set to true if an Eulerian path exists. Must not beNULL.

has_cycle:

Pointer to a Boolean, will be set to true if an Eulerian cycle exists. Must not beNULL.

Returns: 

Error code:IGRAPH_ENOMEM, not enough memory for temporary data.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

2.2. igraph_eulerian_cycle — Finds an Eulerian cycle.

igraph_error_t igraph_eulerian_cycle(        const igraph_t *graph, igraph_vector_int_t *edge_res, igraph_vector_int_t *vertex_res);

Finds an Eulerian cycle, if it exists. An Eulerian cycle is a closed paththat traverses each edge precisely once.

If the graph has no edges, a zero-length cycle is returned.

This function uses Hierholzer's algorithm.

Arguments: 

graph:

The graph object.

edge_res:

Pointer to an initialised vector. The indices of edges belonging to the cycle will be stored here. May beNULL if it is not needed by the caller.

vertex_res:

Pointer to an initialised vector. The indices of vertices belonging to the cycle will be stored here. The first and last vertex in the vector will be the same. May beNULL if it is not needed by the caller.

Returns: 

Error code:

IGRAPH_ENOMEM

not enough memory for temporary data.

IGRAPH_ENOSOL

graph does not have an Eulerian cycle.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

2.3. igraph_eulerian_path — Finds an Eulerian path.

igraph_error_t igraph_eulerian_path(        const igraph_t *graph, igraph_vector_int_t *edge_res, igraph_vector_int_t *vertex_res);

Finds an Eulerian path, if it exists. An Eulerian path traverseseach edge precisely once.

If the graph has no edges, a zero-length path is returned.

This function uses Hierholzer's algorithm.

Arguments: 

graph:

The graph object.

edge_res:

Pointer to an initialised vector. The indices of edges belonging to the path will be stored here. May beNULL if it is not needed by the caller.

vertex_res:

Pointer to an initialised vector. The indices of vertices belonging to the path will be stored here. May beNULL if it is not needed by the caller.

Returns: 

Error code:

IGRAPH_ENOMEM

not enough memory for temporary data.

IGRAPH_ENOSOL

graph does not have an Eulerian path.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

3. Cycle bases

3.1. igraph_fundamental_cycles — Finds a fundamental cycle basis.

igraph_error_t igraph_fundamental_cycles(const igraph_t *graph,                                         igraph_vector_int_list_t *result,                                         igraph_integer_t start_vid,                                         igraph_integer_t bfs_cutoff,                                         const igraph_vector_t *weights);

Warning

This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.

This function computes a fundamental cycle basis associated with a breadth-firstsearch tree of the graph.

Edge directions are ignored. Multi-edges and self-loops are supported.

Arguments: 

graph:

The graph object.

result:

An initialized integer vector list. The result will be stored here, each vector containing the edge IDs of a basis element.

start_vid:

If negative, a complete fundamental cycle basis is returned. If a vertex ID, the fundamental cycles associated with the BFS tree rooted in that vertex will be returned, only for the weakly connected component containing that vertex.

bfs_cutoff:

If negative, a complete cycle basis is returned. Otherwise, only cycles of length2*bfs_cutoff + 1 or shorter are included.bfs_cutoff is used to limit the depth of the BFS tree when searching for cycle edges.

weights:

Currently unused.

Returns: 

Error code.

See also: 

Time complexity: O(|V| + |E|).

3.2. igraph_minimum_cycle_basis — Computes a minimum weight cycle basis.

igraph_error_t igraph_minimum_cycle_basis(const igraph_t *graph,                                          igraph_vector_int_list_t *result,                                          igraph_integer_t bfs_cutoff,                                          igraph_bool_t complete,                                          igraph_bool_t use_cycle_order,                                          const igraph_vector_t *weights);

Warning

This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.

This function computes a minimum weight cycle basis of a graph. Currently,a modified version of Horton's algorithm is used that allows for cutoffs.

Edge directions are ignored. Multi-edges and self-loops are supported.

References:

Horton, J. D. (1987)A polynomial-time algorithm to find the shortest cycle basis of a graph,SIAM Journal on Computing, 16 (2): 358–366.https://doi.org/10.1137%2F0216026

Arguments: 

graph:

The graph object.

result:

An initialized integer vector list, the elements of the cycle basis will be stored here as vectors of edge IDs.

bfs_cutoff:

If negative, an exact minimum cycle basis is returned. Otherwise only those cycles in the result will be part of some minimum cycle basis which are of size2*bfs_cutoff + 1 or smaller. Cycles longer than this limit may not be of the smallest possible size.bfs_cutoff is used to limit the depth of the BFS tree when computing candidate cycles. Specifying a bfs_cutoff can speed up the computation substantially.

complete:

Boolean value. Used only whenbfs_cutoff was given. If true, a complete basis is returned. If false, only cycles not greater than2*bfs_cutoff + 1 are returned. This may save computation time, however, the result will not span the entire cycle space.

use_cycle_order:

If true, each cycle is returned in natural order: the edge IDs will appear ordered along the cycle. This comes at a small performance cost. If false, no guarantees are given about the ordering of edge IDs within cycles. This parameter exists solely to control performance tradeoffs.

weights:

Currently unused.

Returns: 

Error code.

See also: 

Time complexity: TODO.

← Chapter 13. Structural properties of graphsChapter 15. Graph visitors →

© 2003 – 2025 The igraph core team. • Code licensed under GNU GPL 2 or later, documentation underGNU FDL.

[8]ページ先頭
©2009-2025 Movatter.jp