Rでフロイドの循環検出法を可視化する ref: https://qiita.com/nozma/items/bfa3e089cd432b74c10d

file0.r

## フロイドの循環検出法を可視化する ----
library(dplyr)
library(igraph)
library(ggplot2)
library(GGally)
library(ggnetwork)
#devtools::install_github("dill/emoGG")
library(emoGG)

make_rho_graph <- function(lambda, mu, type = "network"){
  # ρの字型の有向グラフを作る
  nodes <- c(rep(1:(lambda+mu), rep(2, lambda+mu))[-c(1, 2*(lambda+mu))], lambda+mu, lambda+1) 
  if(type == "network"){
    nodes %>%
      matrix(ncol = 2, byrow = TRUE) %>%
      network
  } else {
    nodes %>% make_graph
  }
}

nextnode <- function(g, n){
  # 次のノードを返す
  ego(g, nodes = n, mode = "out")[[1]][2]
}

floyd_plot <- function(lambda, mu){
  # グラフの作成
  g_n <- make_rho_graph(lambda, mu)
  g_i <- make_rho_graph(lambda, mu, "igraph")
  # 座標位置の決定
  x <- gplot.layout.fruchtermanreingold(g_n, NULL)
  g_n %v% "x" <- x[,1]
  g_n %v% "y" <- x[,2]
  p <- ggnet2(g_n, mode = c("x", "y"), label = TRUE, arrow.gap = 0.025, arrow.size = 10)
  xp <- p$data$x
  yp <- p$data$y
  # プロットの保存先
  plist <- list()
  pidx <- 1

  # 最初にウサギとカメが出会うまで
  m <- 0
  plist[[pidx]] <- p + 
    add_emoji("1f422", xp[1], yp[1], .2) + add_emoji("1f430", xp[1], yp[1], .15) +
    annotate("text", x = .5, y = .9, label = paste("m =", m))

  rabbit <- 3
  turtle <- 2
  pidx <- 2
  m <- 1

  while(rabbit != turtle){
    plist[[pidx]] <- p + 
      add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
      add_emoji("1f430", xp[rabbit], yp[rabbit], .15) +
      annotate("text", x = .5, y = .9, label = paste("m =", m))
    rabbit <- nextnode(g_i, rabbit) %>% nextnode(g_i, .)
    turtle <- nextnode(g_i, turtle)
    pidx <- pidx + 1
    m <- m + 1
  }
  plist[[pidx]] <- p + 
    add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
    add_emoji("1f430", xp[rabbit], yp[rabbit], .15) + 
    annotate("text", x = xp[turtle], yp[turtle]+0.1, label = "!", col = "tomato", size = 10) +
    annotate("text", x = .5, y = .9, label = paste("m =", m))
  pidx <- pidx + 1

  # 等速で動くウサギ
  rabbit <- 1
  lmd <- 0
  while(rabbit != turtle){
    plist[[pidx]] <- p + 
      add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
      add_emoji("1f430", xp[rabbit], yp[rabbit], .15) +
      annotate("text", x = .5, y = .9, label = paste("m =", m, " λ = ", lmd))
    rabbit <- nextnode(g_i, rabbit)
    turtle <- nextnode(g_i, turtle)
    pidx <- pidx + 1
    lmd <- lmd + 1
  }
  plist[[pidx]] <- p + 
    add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
    add_emoji("1f430", xp[rabbit], yp[rabbit], .15) + 
    annotate("text", x = xp[turtle], yp[turtle]+0.1, label = "!", col = "tomato", size = 13) +
    annotate("text", x = .5, y = .9, label = paste("m =", m, " λ = ", lmd))
  pidx <- pidx + 1

  # 再び倍速で動くウサギ
  mu <- 0
  plist[[pidx]] <- p + 
    add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
    add_emoji("1f430", xp[rabbit], yp[rabbit], .15) +
    annotate("text", x = .5, y = .9, label = paste("m =", m, " λ =", lmd, " μ =", mu))
  rabbit <- nextnode(g_i, rabbit) %>% nextnode(g_i, .)
  turtle <- nextnode(g_i, turtle)
  pidx <- pidx + 1
  mu <- mu + 1
  while(rabbit != turtle){
    plist[[pidx]] <- p + 
      add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
      add_emoji("1f430", xp[rabbit], yp[rabbit], .15) +
      annotate("text", x = .5, y = .9, label = paste("m =", m, " λ =", lmd, " μ =", mu))
    rabbit <- nextnode(g_i, rabbit) %>% nextnode(g_i, .)
    turtle <- nextnode(g_i, turtle)
    pidx <- pidx + 1
    mu <- mu + 1
  }
  plist[[pidx]] <- p + 
    add_emoji("1f422", xp[turtle], yp[turtle], .2) + 
    add_emoji("1f430", xp[rabbit], yp[rabbit], .15) + 
    annotate("text", x = xp[turtle], yp[turtle]+0.1, label = "!", col = "tomato", size = 15) +
    annotate("text", x = .5, y = .9, label = paste("m =", m, " λ =", lmd, " μ =", mu))

  return(plist)
}

library(animation)

result <- floyd_plot(8, 12)
saveGIF(lapply(result, print))

result <- floyd_plot(11, 5)
saveGIF(lapply(result, print), movie.name = "animation2.gif")