For using the igraph C library
int igraph_bfs(const igraph_t *graph, igraph_integer_t root, const igraph_vector_t *roots, igraph_neimode_t mode, igraph_bool_t unreachable, const igraph_vector_t *restricted, igraph_vector_t *order, igraph_vector_t *rank, igraph_vector_t *father, igraph_vector_t *pred, igraph_vector_t *succ, igraph_vector_t *dist, igraph_bfshandler_t *callback, void *extra);
A simple breadthfirst 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.
Arguments:

The input graph. 

The id of the root vertex. It is ignored if the 

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. 

For directed graphs, it defines which edges to follow.


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. 

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. 

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

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

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

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. 

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. 

If not a null pointer, then the distance from the root of the current search tree is stored here. 

If not null, then it should be a pointer to a
function of type 

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 14.1. File examples/simple/igraph_bfs.c
/* * mode: C * */ /* IGraph library. Copyright (C) 20062012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard street, Cambridge, MA 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301 USA */ #include <igraph.h> void vector_print(igraph_vector_t *v) { long int i; for (i = 0; i < igraph_vector_size(v); i++) { printf(" %li", (long int) VECTOR(*v)[i]); } printf("\n"); } int main() { igraph_t g; igraph_vector_t vids, layers, parents; igraph_ring(&g, 10, IGRAPH_UNDIRECTED, 0, 0); igraph_vector_init(&vids, 0); igraph_vector_init(&layers, 0); igraph_vector_init(&parents, 0); igraph_i_bfs(&g, 0, IGRAPH_ALL, &vids, &layers, &parents); vector_print(&vids); vector_print(&layers); vector_print(&parents); igraph_destroy(&g); igraph_tree(&g, 20, 2, IGRAPH_TREE_UNDIRECTED); igraph_i_bfs(&g, 0, IGRAPH_ALL, &vids, &layers, &parents); vector_print(&vids); vector_print(&layers); vector_print(&parents); igraph_destroy(&g); igraph_vector_destroy(&vids); igraph_vector_destroy(&layers); igraph_vector_destroy(&parents); return 0; }
Example 14.2. File examples/simple/igraph_bfs2.c
/* * mode: C * */ /* IGraph library. Copyright (C) 20092012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard street, Cambridge, MA 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301 USA */ #include <igraph.h> igraph_bool_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) { printf(" %li", (long int) vid); return 0; } int main() { igraph_t graph, ring; igraph_vector_t order, rank, father, pred, succ, dist; igraph_vector_t restricted; igraph_vector_t roots; long int i; igraph_ring(&ring, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1); igraph_disjoint_union(&graph, &ring, &ring); igraph_destroy(&ring); igraph_vector_init(&order, 0); igraph_vector_init(&rank, 0); igraph_vector_init(&father, 0); igraph_vector_init(&pred, 0); igraph_vector_init(&succ, 0); igraph_vector_init(&dist, 0); igraph_bfs(&graph, /*root=*/0, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 1, /*restricted=*/ 0, &order, &rank, &father, &pred, &succ, &dist, /*callback=*/ 0, /*extra=*/ 0); igraph_vector_print(&order); igraph_vector_print(&rank); igraph_vector_print(&father); igraph_vector_print(&pred); igraph_vector_print(&succ); igraph_vector_print(&dist); igraph_vector_destroy(&order); igraph_vector_destroy(&rank); igraph_vector_destroy(&father); igraph_vector_destroy(&pred); igraph_vector_destroy(&succ); igraph_vector_destroy(&dist); /* Test the callback */ igraph_bfs(&graph, /*root=*/ 0, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 1, /*restricted=*/ 0, 0, 0, 0, 0, 0, 0, &bfs_callback, 0); printf("\n"); /* Test different roots */ igraph_bfs(&graph, /*root=*/ 2, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 1, /*restricted=*/ 0, 0, 0, 0, 0, 0, 0, &bfs_callback, 0); printf("\n"); /* Test restricted */ igraph_vector_init(&restricted, 0); for (i = 5; i < igraph_vcount(&graph); i++) { igraph_vector_push_back(&restricted, i); } igraph_bfs(&graph, /*root=*/ 5, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 1, &restricted, 0, 0, 0, 0, 0, 0, &bfs_callback, 0); printf("\n"); /* Root not in restricted set */ igraph_bfs(&graph, /*root=*/ 4, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 1, &restricted, 0, 0, 0, 0, 0, 0, &bfs_callback, 0); printf("\n"); igraph_bfs(&graph, /*root=*/ 3, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 0, &restricted, 0, 0, 0, 0, 0, 0, &bfs_callback, 0); printf("\n"); /* Multiple root vertices */ igraph_vector_init(&roots, 3); VECTOR(roots)[0] = 3; VECTOR(roots)[1] = 4; VECTOR(roots)[2] = 6; igraph_bfs(&graph, /*root=*/ 1, &roots, /*neimode=*/ IGRAPH_OUT, /*unreachable=*/ 0, &restricted, 0, 0, 0, 0, 0, 0, &bfs_callback, 0); printf("\n"); igraph_vector_destroy(&roots); igraph_vector_destroy(&restricted); igraph_destroy(&graph); return 0; }
typedef igraph_bool_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 breadthfirst search. This
callback function must be of type igraph_bfshandler_t
. It has
the following arguments:
Arguments:

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

The id of the vertex just found by the breadthfirst search. 

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. 

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. 

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

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

The extra argument that was passed to 
Returns:
A logical value, if TRUE (=nonzero), that is interpreted as a request to stop the BFS and return to the caller. If a BFS is terminated like this, then all elements of the result vectors that were not yet calculated at the point of the termination contain NaN. 
See also:
int igraph_dfs(const igraph_t *graph, igraph_integer_t root, igraph_neimode_t mode, igraph_bool_t unreachable, igraph_vector_t *order, igraph_vector_t *order_out, igraph_vector_t *father, igraph_vector_t *dist, igraph_dfshandler_t *in_callback, igraph_dfshandler_t *out_callback, void *extra);
A simple depthfirst 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:

The input graph. 

The id of the root vertex. 

For directed graphs, it defines which edges to follow.


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. 

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

If not a null pointer, then the vertex ids of the graphs are stored here, in the order of the completion of their subtree. 

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

If not a null pointer, then the distance from the root of the current search tree is stored here. 

If not null, then it should be a pointer to a
function of type 

If not null, then it should be a pointer to a
function of type 

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.
typedef igraph_bool_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:

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

The id of the vertex just found by the depthfirst search. 

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

The extra argument that was passed to 
Returns:
A logical value, if TRUE (=nonzero), that is interpreted as a request to stop the DFS and return to the caller. If a DFS is terminated like this, then all elements of the result vectors that were not yet calculated at the point of the termination contain NaN. 
See also:
int igraph_random_walk(const igraph_t *graph, igraph_vector_t *walk, 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:

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

An allocated vector, the result is stored here. It will be resized as needed. 

The start vertex for the walk. 

The number of steps to take. If the random walk gets
stuck, then the 

How to walk along the edges in directed graphs.


What to do if the random walk gets stuck.

Returns:
Error code. 
Time complexity: O(l + d), where l
is the length of the
walk, and d
is the total degree of the visited nodes.
int igraph_random_edge_walk(const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_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:

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

A vector of nonnegative edge weights. It is assumed that at least one strictly positive weight is found among the outgoing edges of each vertex. If it is a NULL pointer, all edges are considered to have equal weight. 

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

The start vertex for the walk. 

The number of steps to take. If the random walk gets
stuck, then the 

How to walk along the edges in directed graphs.


What to do if the random walk gets stuck.

Returns:
Error code. 
← Chapter 13. Structural Properties of Graphs  Chapter 15. Cliques and Independent Vertex Sets → 