1
2#' Random walk on a graph
3#'
4#' Do a random walk. From the given start vertex, take the given number of
5#' steps, choosing an edge from the actual vertex uniformly randomly. Edge
6#' directions are observed in directed graphs (see the \code{mode} argument
7#' as well). Multiple and loop edges are also observed.
8#'
9#' @param graph The input graph, might be undirected or directed.
10#' @param start The start vertex.
11#' @param steps The number of steps to make.
12#' @param mode How to follow directed edges. \code{"out"} steps along the
13#'   edge direction, \code{"in"} is opposite to that. \code{"all"} ignores
14#'   edge directions. This argument is ignored for undirected graphs.
15#' @param stuck What to do if the random walk gets stuck. \code{"return"}
16#'   returns the partial walk, \code{"error"} raises an error.
17#' @return A vertex sequence containing the vertices along the walk.
18#' @export
19#' @examples
20#' ## Stationary distribution of a Markov chain
21#' g <- make_ring(10, directed = TRUE) %u%
22#'   make_star(11, center = 11) + edge(11, 1)
23#'
24#' ec <- eigen_centrality(g, directed = TRUE)$vector
25#' pg <- page_rank(g, damping = 0.999)$vector
26#' w <- random_walk(g, start = 1, steps = 10000)
27#'
28#' ## These are similar, but not exactly the same
29#' cor(table(w), ec)
30#'
31#' ## But these are (almost) the same
32#' cor(table(w), pg)
33
34random_walk <- function(graph, start, steps, mode = c("out", "in", "all"),
35                        stuck = c("return", "error")) {
36  ## Argument checks
37  if (!is_igraph(graph)) stop("Not a graph object")
38  start <- as.igraph.vs(graph, start)
39  mode <- switch(igraph.match.arg(mode), "out" = 1, "in" = 2, "all" = 3,
40                 "total" = 3)
41  steps <- as.integer(steps)
42  stuck <- switch(igraph.match.arg(stuck), "error" = 0L, "return" = 1L)
43
44  on.exit( .Call(C_R_igraph_finalizer) )
45
46  ## Function call
47  res <- .Call(C_R_igraph_random_walk, graph, start - 1, mode, steps, stuck)
48  if (igraph_opt("return.vs.es")) {
49    res <- create_vs(graph, res)
50  }
51  res
52}
53