igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 15. Graph visitors

1. Breadth-first search

1.1. igraph_bfs — Breadth-first search.

igraph_error_t igraph_bfs(const igraph_t *graph,
               igraph_integer_t root, const igraph_vector_int_t *roots,
               igraph_neimode_t mode, igraph_bool_t unreachable,
               const igraph_vector_int_t *restricted,
               igraph_vector_int_t *order, igraph_vector_int_t *rank,
               igraph_vector_int_t *parents,
               igraph_vector_int_t *pred, igraph_vector_int_t *succ,
               igraph_vector_int_t *dist, igraph_bfshandler_t *callback,
               void *extra);

A simple breadth-first search, with a lot of different results and the possibility to call a callback whenever a vertex is visited. It is allowed to supply null pointers as the output arguments the user is not interested in, in this case they will be ignored.

If not all vertices can be reached from the supplied root vertex, then additional root vertices will be used, in the order of their vertex IDs.

Consider using igraph_bfs_simple instead if you set most of the output arguments provided by this function to a null pointer.

Arguments: 

graph:

The input graph.

root:

The id of the root vertex. It is ignored if the roots argument is not a null pointer.

roots:

Pointer to an initialized vector, or a null pointer. If not a null pointer, then it is a vector containing root vertices to start the BFS from. The vertices are considered in the order they appear. If a root vertex was already found while searching from another one, then no search is conducted from it.

mode:

For directed graphs, it defines which edges to follow. IGRAPH_OUT means following the direction of the edges, IGRAPH_IN means the opposite, and IGRAPH_ALL ignores the direction of the edges. This parameter is ignored for undirected graphs.

unreachable:

Logical scalar, whether the search should visit the vertices that are unreachable from the given root node(s). If true, then additional searches are performed until all vertices are visited.

restricted:

If not a null pointer, then it must be a pointer to a vector containing vertex IDs. The BFS is carried out only on these vertices.

order:

If not null pointer, then the vertex IDs of the graph are stored here, in the same order as they were visited.

rank:

If not a null pointer, then the rank of each vertex is stored here.

parents:

If not a null pointer, then the id of the parent of each vertex is stored here. When a vertex was not visited during the traversal, -2 will be stored as the ID of its parent. When a vertex was visited during the traversal and it was one of the roots of the search trees, -1 will be stored as the ID of its parent.

pred:

If not a null pointer, then the id of vertex that was visited before the current one is stored here. If there is no such vertex (the current vertex is the root of a search tree), then -1 is stored as the predecessor of the vertex. If the vertex was not visited at all, then -2 is stored for the predecessor of the vertex.

succ:

If not a null pointer, then the id of the vertex that was visited after the current one is stored here. If there is no such vertex (the current one is the last in a search tree), then -1 is stored as the successor of the vertex. If the vertex was not visited at all, then -2 is stored for the successor of the vertex.

dist:

If not a null pointer, then the distance from the root of the current search tree is stored here for each vertex. If a vertex was not reached during the traversal, its distance will be -1 in this vector.

callback:

If not null, then it should be a pointer to a function of type igraph_bfshandler_t. This function will be called, whenever a new vertex is visited.

extra:

Extra argument to pass to the callback function.

Returns: 

Error code.

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

Example 15.1.  File examples/simple/igraph_bfs.c

#include <igraph.h>

int main(void) {

    igraph_t graph, ring;
    igraph_vector_int_t order, rank, father, pred, succ, dist;

    /* Create a disjoint union of two rings */
    igraph_ring(&ring, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
    igraph_disjoint_union(&graph, &ring, &ring);
    igraph_destroy(&ring);

    /* Initialize the vectors where the result will be stored. Any of these
     * can be omitted and replaced with a null pointer when calling
     * igraph_bfs() */
    igraph_vector_int_init(&order, 0);
    igraph_vector_int_init(&rank, 0);
    igraph_vector_int_init(&father, 0);
    igraph_vector_int_init(&pred, 0);
    igraph_vector_int_init(&succ, 0);
    igraph_vector_int_init(&dist, 0);

    /* Now call the BFS function */
    igraph_bfs(&graph, /*root=*/0, /*roots=*/ NULL, /*neimode=*/ IGRAPH_OUT,
               /*unreachable=*/ 1, /*restricted=*/ NULL,
               &order, &rank, &father, &pred, &succ, &dist,
               /*callback=*/ NULL, /*extra=*/ NULL);

    /* Print the results */
    igraph_vector_int_print(&order);
    igraph_vector_int_print(&rank);
    igraph_vector_int_print(&father);
    igraph_vector_int_print(&pred);
    igraph_vector_int_print(&succ);
    igraph_vector_int_print(&dist);

    /* Cleam up after ourselves */
    igraph_vector_int_destroy(&order);
    igraph_vector_int_destroy(&rank);
    igraph_vector_int_destroy(&father);
    igraph_vector_int_destroy(&pred);
    igraph_vector_int_destroy(&succ);
    igraph_vector_int_destroy(&dist);

    igraph_destroy(&graph);

    return 0;
}


Example 15.2.  File examples/simple/igraph_bfs_callback.c

#include <igraph.h>

igraph_error_t bfs_callback(const igraph_t *graph,
                           igraph_integer_t vid,
                           igraph_integer_t pred,
                           igraph_integer_t succ,
                           igraph_integer_t rank,
                           igraph_integer_t dist,
                           void *extra) {
    IGRAPH_UNUSED(graph);
    IGRAPH_UNUSED(pred);
    IGRAPH_UNUSED(succ);
    IGRAPH_UNUSED(rank);
    IGRAPH_UNUSED(dist);
    printf(" %" IGRAPH_PRId "", vid);
    return IGRAPH_SUCCESS;
}

int main(void) {
    igraph_t graph, ring;

    /* Create a disjoint union of two rings */
    igraph_ring(&ring, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
    igraph_disjoint_union(&graph, &ring, &ring);
    igraph_destroy(&ring);

    /* Now call the BFS function */
    printf("(");
    igraph_bfs(&graph, /*root=*/0, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
               /*unreachable=*/ 1, /*restricted=*/ 0,
               /*order=*/ 0, /*rank=*/ 0, /*father=*/ 0, /*pred=*/ 0,
               /*succ=*/ 0, /*dist=*/ 0,
               /*callback=*/ bfs_callback, /*extra=*/ 0);
    printf(" )\n");

    /* Cleam up after ourselves */
    igraph_destroy(&graph);

    return 0;
}


1.2. igraph_bfs_simple — Breadth-first search, single-source version

igraph_error_t igraph_bfs_simple(
    const igraph_t *graph, igraph_integer_t root, igraph_neimode_t mode,
    igraph_vector_int_t *order, igraph_vector_int_t *layers,
    igraph_vector_int_t *parents
);

An alternative breadth-first search implementation to cater for the simpler use-cases when only a single breadth-first search has to be conducted from a source node and most of the output arguments from igraph_bfs are not needed. It is allowed to supply null pointers as the output arguments the user is not interested in, in this case they will be ignored.

Arguments: 

graph:

The input graph.

root:

The id of the root vertex.

mode:

For directed graphs, it defines which edges to follow. IGRAPH_OUT means following the direction of the edges, IGRAPH_IN means the opposite, and IGRAPH_ALL ignores the direction of the edges. This parameter is ignored for undirected graphs.

order:

If not a null pointer, then an initialized vector must be passed here. The IDs of the vertices visited during the traversal will be stored here, in the same order as they were visited.

layers:

If not a null pointer, then an initialized vector must be passed here. The i-th element of the vector will contain the index into order where the vertices that are at distance i from the root are stored. In other words, if you are interested in the vertices that are at distance i from the root, you need to look in the order vector from layers[i] to layers[i+1].

parents:

If not a null pointer, then an initialized vector must be passed here. The vector will be resized so its length is equal to the number of nodes, and it will contain the index of the parent node for each visited node. The values in the vector are set to -2 for vertices that were not visited, and -1 for the root vertex.

Returns: 

Error code.

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

Example 15.3.  File examples/simple/igraph_bfs_simple.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_t vids, layers, parents;

    igraph_ring(&g, 10, IGRAPH_UNDIRECTED, 0, 0);

    igraph_vector_int_init(&vids, 0);
    igraph_vector_int_init(&layers, 0);
    igraph_vector_int_init(&parents, 0);

    igraph_bfs_simple(&g, 0, IGRAPH_ALL, &vids, &layers, &parents);

    igraph_vector_int_print(&vids);
    igraph_vector_int_print(&layers);
    igraph_vector_int_print(&parents);

    igraph_destroy(&g);

    igraph_vector_int_destroy(&vids);
    igraph_vector_int_destroy(&layers);
    igraph_vector_int_destroy(&parents);

    return 0;
}


1.3. igraph_bfshandler_t — Callback type for BFS function.

typedef igraph_error_t igraph_bfshandler_t(const igraph_t *graph,
        igraph_integer_t vid,
        igraph_integer_t pred,
        igraph_integer_t succ,
        igraph_integer_t rank,
        igraph_integer_t dist,
        void *extra);

igraph_bfs() is able to call a callback function, whenever a new vertex is found, while doing the breadth-first search. This callback function must be of type igraph_bfshandler_t. It has the following arguments:

Arguments: 

graph:

The graph that the algorithm is working on. Of course this must not be modified.

vid:

The id of the vertex just found by the breadth-first search.

pred:

The id of the previous vertex visited. It is -1 if there is no previous vertex, because the current vertex is the root is a search tree.

succ:

The id of the next vertex that will be visited. It is -1 if there is no next vertex, because the current vertex is the last one in a search tree.

rank:

The rank of the current vertex, it starts with zero.

dist:

The distance (number of hops) of the current vertex from the root of the current search tree.

extra:

The extra argument that was passed to igraph_bfs().

Returns: 

IGRAPH_SUCCESS if the BFS should continue, IGRAPH_STOP if the BFS should stop and return to the caller normally. Any other value is treated as an igraph error code, terminating the search and returning to the caller with the same error code. If a BFS is is terminated prematurely, then all elements of the result vectors that were not yet calculated at the point of the termination contain negative values.

See also: 

2. Depth-first search

2.1. igraph_dfs — Depth-first search.

igraph_error_t igraph_dfs(const igraph_t *graph, igraph_integer_t root,
               igraph_neimode_t mode, igraph_bool_t unreachable,
               igraph_vector_int_t *order,
               igraph_vector_int_t *order_out, igraph_vector_int_t *parents,
               igraph_vector_int_t *dist, igraph_dfshandler_t *in_callback,
               igraph_dfshandler_t *out_callback,
               void *extra);

A simple depth-first search, with the possibility to call a callback whenever a vertex is discovered and/or whenever a subtree is finished. It is allowed to supply null pointers as the output arguments the user is not interested in, in this case they will be ignored.

If not all vertices can be reached from the supplied root vertex, then additional root vertices will be used, in the order of their vertex IDs.

Arguments: 

graph:

The input graph.

root:

The id of the root vertex.

mode:

For directed graphs, it defines which edges to follow. IGRAPH_OUT means following the direction of the edges, IGRAPH_IN means the opposite, and IGRAPH_ALL ignores the direction of the edges. This parameter is ignored for undirected graphs.

unreachable:

Logical scalar, whether the search should visit the vertices that are unreachable from the given root node(s). If true, then additional searches are performed until all vertices are visited.

order:

If not null pointer, then the vertex IDs of the graph are stored here, in the same order as they were discovered. The tail of the vector will be padded with -1 to ensure that the length of the vector is the same as the number of vertices, even if some vertices were not visited during the traversal.

order_out:

If not a null pointer, then the vertex IDs of the graphs are stored here, in the order of the completion of their subtree. The tail of the vector will be padded with -1 to ensure that the length of the vector is the same as the number of vertices, even if some vertices were not visited during the traversal.

parents:

If not a null pointer, then the id of the parent of each vertex is stored here. -1 will be stored for the root of the search tree; -2 will be stored for vertices that were not visited.

dist:

If not a null pointer, then the distance from the root of the current search tree is stored here. -1 will be stored for vertices that were not visited.

in_callback:

If not null, then it should be a pointer to a function of type igraph_dfshandler_t. This function will be called, whenever a new vertex is discovered.

out_callback:

If not null, then it should be a pointer to a function of type igraph_dfshandler_t. This function will be called, whenever the subtree of a vertex is completed.

extra:

Extra argument to pass to the callback function(s).

Returns: 

Error code.

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

2.2. igraph_dfshandler_t — Callback type for the DFS function.

typedef igraph_error_t igraph_dfshandler_t(const igraph_t *graph,
        igraph_integer_t vid,
        igraph_integer_t dist,
        void *extra);

igraph_dfs() is able to call a callback function, whenever a new vertex is discovered, and/or whenever a subtree is completed. These callbacks must be of type igraph_dfshandler_t. They have the following arguments:

Arguments: 

graph:

The graph that the algorithm is working on. Of course this must not be modified.

vid:

The id of the vertex just found by the depth-first search.

dist:

The distance (number of hops) of the current vertex from the root of the current search tree.

extra:

The extra argument that was passed to igraph_dfs().

Returns: 

IGRAPH_SUCCESS if the DFS should continue, IGRAPH_STOP if the DFS should stop and return to the caller normally. Any other value is treated as an igraph error code, terminating the search and returning to the caller with the same error code. If a DFS is is terminated prematurely, then all elements of the result vectors that were not yet calculated at the point of the termination contain negative values.

See also: 

3. Random walks

3.1. igraph_random_walk — Performs a random walk on a graph.

igraph_error_t igraph_random_walk(const igraph_t *graph,
                       const igraph_vector_t *weights,
                       igraph_vector_int_t *vertices,
                       igraph_vector_int_t *edges,
                       igraph_integer_t start,
                       igraph_neimode_t mode,
                       igraph_integer_t steps,
                       igraph_random_walk_stuck_t stuck);

Performs a random walk with a given length on a graph, from the given start vertex. Edge directions are (potentially) considered, depending on the mode argument.

Arguments: 

graph:

The input graph, it can be directed or undirected. Multiple edges are respected, so are loop edges.

weights:

A vector of non-negative edge weights. It is assumed that at least one strictly positive weight is found among the outgoing edges of each vertex. Additionally, no edge weight may be NaN. If either case does not hold, an error is returned. If it is NULL, all edges are considered to have equal weight.

vertices:

An allocated vector, the result is stored here as a list of vertex IDs. It will be resized as needed. It includes the vertex IDs of starting and ending vertices. Length of the vertices vector: steps + 1

edges:

An initialized vector, the indices of traversed edges are stored here. It will be resized as needed. Length of the edges vector: steps

start:

The start vertex for the walk.

steps:

The number of steps to take. If the random walk gets stuck, then the stuck argument specifies what happens. steps is the number of edges to traverse during the walk.

mode:

How to walk along the edges in directed graphs. IGRAPH_OUT means following edge directions, IGRAPH_IN means going opposite the edge directions, IGRAPH_ALL means ignoring edge directions. This argument is ignored for undirected graphs.

stuck:

What to do if the random walk gets stuck. IGRAPH_RANDOM_WALK_STUCK_RETURN means that the function returns with a shorter walk; IGRAPH_RANDOM_WALK_STUCK_ERROR means that an IGRAPH_ERWSTUCK error is reported. In both cases, vertices and edges are truncated to contain the actual interrupted walk.

Returns: 

Error code: IGRAPH_ERWSTUCK if the walk got stuck.

Time complexity: O(l + d) for unweighted graphs and O(l * log(k) + d) for weighted graphs, where l is the length of the walk, d is the total degree of the visited nodes and k is the average degree of vertices of the given graph.

4. Deprecated functions

4.1. igraph_random_edge_walk — Performs a random walk on a graph and returns the traversed edges.

igraph_error_t igraph_random_edge_walk(
        const igraph_t *graph,
        const igraph_vector_t *weights,
        igraph_vector_int_t *edgewalk,
        igraph_integer_t start, igraph_neimode_t mode,
        igraph_integer_t steps,
        igraph_random_walk_stuck_t stuck);

Performs a random walk with a given length on a graph, from the given start vertex. Edge directions are (potentially) considered, depending on the mode argument.

Arguments: 

graph:

The input graph, it can be directed or undirected. Multiple edges are respected, so are loop edges.

weights:

A vector of non-negative edge weights. It is assumed that at least one strictly positive weight is found among the outgoing edges of each vertex. Additionally, no edge weight may be NaN. If either case does not hold, an error is returned. If it is a NULL pointer, all edges are considered to have equal weight.

edgewalk:

An initialized vector; the indices of traversed edges are stored here. It will be resized as needed.

start:

The start vertex for the walk.

steps:

The number of steps to take. If the random walk gets stuck, then the stuck argument specifies what happens.

mode:

How to walk along the edges in directed graphs. IGRAPH_OUT means following edge directions, IGRAPH_IN means going opposite the edge directions, IGRAPH_ALL means ignoring edge directions. This argument is ignored for undirected graphs.

stuck:

What to do if the random walk gets stuck. IGRAPH_RANDOM_WALK_STUCK_RETURN means that the function returns with a shorter walk; IGRAPH_RANDOM_WALK_STUCK_ERROR means that an IGRAPH_ERWSTUCK error is reported. In both cases, edgewalk is truncated to contain the actual interrupted walk.

Returns: 

Error code.

Warning

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