Generar paseo aleatorio en un gráfico

Nuestros mejores programadores agotaron sus depósitos de café, en su búsqueda noche y día por la respuesta, hasta que Paúl halló la respuesta en GitHub y hoy la comparte con nosotros.

Solución:

Block[
 
  graph = RandomGraph[20, 100]
  , start
  , path
  ,
 start = RandomChoice[VertexList[graph]];
 path = NestList[RandomChoice[AdjacencyList[graph, #]] &, start, 5];
 ListAnimate[
  Table[
   Graph[graph
    , VertexStyle -> v -> Red
    , VertexSize -> Large
    ]
   , v, path
   ]]]

---

Block[
 
  graph = GridGraph[6, 6]
  , start
  , path
  ,
 start = RandomChoice[VertexList[graph]];
 path = NestList[RandomChoice[AdjacencyList[graph, #]] &, start, 30];
 ListAnimate[
  Table[
   Graph[
    graph
    , VertexStyle -> 
     Append[Map[Rule[#, Pink] &, Union[path[[1 ;; v]]]], 
      path[[v]] -> Red]
    , EdgeStyle -> 
     Evaluate[(UndirectedEdge[#1, #2] -> Directive[Red, Thick]) & @@@ 
       Partition[path[[1 ;; v]], 2, 1]]
    , VertexSize -> Large
    ]
   , v, Length[path]
   ]]]

Si necesita un buen rendimiento (por ejemplo, calcular cientos de caminatas aleatorias largas para obtener buenas estadísticas), considere usar IGRandomWalk del paquete IGraph/M.

rg = RandomGraph[100, 200]

walk = IGRandomWalk[rg, 1, 100]

Animate[
 HighlightGraph[rg, vertex],
 vertex, walk
]

Puedes usar DiscreteMarkovProcess.

Por ejemplo,

graph = GridGraph[5, 5]

mp = DiscreteMarkovProcess[1 (* starting vertex index, not name *), graph]

walk = RandomFunction[mp, 1, 10]["Values"]
(* 1, 2, 1, 6, 11, 16, 11, 12, 7, 2 *)

Animar:

Animate[
 HighlightGraph[g, vertex],
 vertex, walk
]

Comparación de rendimiento con IGRandomWalk de IGraph/M:

RandomFunction[mp, 1, 10000]; // RepeatedTiming
(* 0.034, Null *)

IGRandomWalk[graph, 1, 10000]; // RepeatedTiming
(* 0.00038, Null *)

Aquí tienes las comentarios y calificaciones

Si te animas, tienes el poder dejar una reseña acerca de qué te ha impresionado de este artículo.

---

---

Utiliza Nuestro Buscador