{"algorithm":"random-walk","about":["A random walk starts at a vertex and moves to one of its out-neighbors at random, again and again. In an unweighted graph every neighbor has the same chance. In a weighted graph the chance follows the edge's weight, so heavier edges are taken more often. An edge with a weight of zero or less is never taken, unless none of the vertex's edges has a positive weight.","The walk returns the start first and stops after the number of vertices you ask for, or earlier at a vertex with no outgoing edges. Vertices can come up more than once. Each move costs time in proportion to the degree of the current vertex. gograph draws from crypto/rand, so a walk can't be replayed from a seed.","Use it to sample a graph too large to search, to simulate someone clicking from page to page, or to estimate how often a walk passes each vertex, which ranking methods build on."],"template":{"id":"service-calls","name":"Microservice calls","description":"Nine services of an online shop. Each edge is a call from one service to another, and some services call each other back.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"Gateway","x":96,"y":384},{"id":"Auth","x":320,"y":128},{"id":"Users","x":608,"y":128},{"id":"Orders","x":384,"y":384},{"id":"Payments","x":640,"y":320},{"id":"Shipping","x":640,"y":544},{"id":"Inventory","x":448,"y":640},{"id":"Search","x":192,"y":640},{"id":"Notify","x":896,"y":320}],"edges":[{"from":"Gateway","to":"Auth"},{"from":"Gateway","to":"Orders"},{"from":"Gateway","to":"Search"},{"from":"Auth","to":"Users"},{"from":"Users","to":"Auth"},{"from":"Users","to":"Notify"},{"from":"Orders","to":"Users"},{"from":"Orders","to":"Inventory"},{"from":"Orders","to":"Payments"},{"from":"Payments","to":"Shipping"},{"from":"Payments","to":"Notify"},{"from":"Shipping","to":"Orders"},{"from":"Shipping","to":"Notify"},{"from":"Inventory","to":"Search"},{"from":"Search","to":"Inventory"}],"details":{"vertices":9,"edges":15,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.20833333333333334,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":0,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"A request enters at the gateway, and each service passes it on to one of the services it calls, picked at random. Which services does it pass through in 12 stops, counting the gateway?","params":{"start":"Gateway","steps":12},"result":{"kind":"order","vertices":["Gateway","Search","Inventory","Search","Inventory","Search","Inventory","Search","Inventory","Search","Inventory","Search"]},"answer":"On this run, the walk from Gateway went through 12 vertices, 3 of them different: Gateway, Search, Inventory, Search, Inventory, Search, Inventory, Search, Inventory, Search, and so on to Search.","legend":{"vertex":[{"id":"idle","label":"Not visited","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Could go next","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Walker is here","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Visited","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Walked","color":"#009E73","shape":"thick"},{"id":"examined","label":"Could be taken next","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"chance","title":"Chance to go next","kind":"table"},{"id":"order","title":"Walk so far","kind":"list"}]},"steps":[{"say":"Start at Gateway. The walk stops after 12 vertices, or sooner at a vertex with no outgoing edges.","ops":[{"v":"Gateway","state":"current"},{"panel":"order","list":[{"key":"Gateway"}]}]},{"say":"Gateway has 3 out-neighbors, so each has a 1 in 3 chance.","ops":[{"panel":"chance","set":{"Auth":"33.3%"}},{"v":"Auth","state":"waiting"},{"e":["Gateway","Auth"],"state":"examined"},{"panel":"chance","set":{"Orders":"33.3%"}},{"v":"Orders","state":"waiting"},{"e":["Gateway","Orders"],"state":"examined"},{"panel":"chance","set":{"Search":"33.3%"}},{"v":"Search","state":"waiting"},{"e":["Gateway","Search"],"state":"examined"}]},{"say":"The walk picks Search, which had a 33.3% chance.","ops":[{"v":"Gateway","state":"done"},{"v":"Auth","state":"idle"},{"e":["Gateway","Auth"],"state":"idle"},{"v":"Orders","state":"idle"},{"e":["Gateway","Orders"],"state":"idle"},{"e":["Gateway","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"}]}]},{"say":"Search has one out-neighbor, Inventory, so the walk must go there.","ops":[{"panel":"chance","unset":["Auth","Orders","Search"]},{"panel":"chance","set":{"Inventory":"100%"}},{"v":"Inventory","state":"waiting"},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"The walk moves to Inventory.","ops":[{"v":"Search","state":"done"},{"e":["Search","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"}]}]},{"say":"Inventory has one out-neighbor, Search, so the walk must go there.","ops":[{"panel":"chance","unset":["Inventory"]},{"panel":"chance","set":{"Search":"100%"}},{"v":"Search","state":"waiting"},{"e":["Inventory","Search"],"state":"examined"}]},{"say":"The walk moves to Search.","ops":[{"v":"Inventory","state":"done"},{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"}]}]},{"say":"Search has one out-neighbor, Inventory, so the walk must go there.","ops":[{"panel":"chance","unset":["Search"]},{"panel":"chance","set":{"Inventory":"100%"}},{"v":"Inventory","state":"waiting"},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"The walk moves to Inventory.","ops":[{"v":"Search","state":"done"},{"e":["Search","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"}]}]},{"say":"Inventory has one out-neighbor, Search, so the walk must go there.","ops":[{"panel":"chance","unset":["Inventory"]},{"panel":"chance","set":{"Search":"100%"}},{"v":"Search","state":"waiting"},{"e":["Inventory","Search"],"state":"examined"}]},{"say":"The walk moves to Search.","ops":[{"v":"Inventory","state":"done"},{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"}]}]},{"say":"Search has one out-neighbor, Inventory, so the walk must go there.","ops":[{"panel":"chance","unset":["Search"]},{"panel":"chance","set":{"Inventory":"100%"}},{"v":"Inventory","state":"waiting"},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"The walk moves to Inventory.","ops":[{"v":"Search","state":"done"},{"e":["Search","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"}]}]},{"say":"Inventory has one out-neighbor, Search, so the walk must go there.","ops":[{"panel":"chance","unset":["Inventory"]},{"panel":"chance","set":{"Search":"100%"}},{"v":"Search","state":"waiting"},{"e":["Inventory","Search"],"state":"examined"}]},{"say":"The walk moves to Search.","ops":[{"v":"Inventory","state":"done"},{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"}]}]},{"say":"Search has one out-neighbor, Inventory, so the walk must go there.","ops":[{"panel":"chance","unset":["Search"]},{"panel":"chance","set":{"Inventory":"100%"}},{"v":"Inventory","state":"waiting"},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"The walk moves to Inventory.","ops":[{"v":"Search","state":"done"},{"e":["Search","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"}]}]},{"say":"Inventory has one out-neighbor, Search, so the walk must go there.","ops":[{"panel":"chance","unset":["Inventory"]},{"panel":"chance","set":{"Search":"100%"}},{"v":"Search","state":"waiting"},{"e":["Inventory","Search"],"state":"examined"}]},{"say":"The walk moves to Search.","ops":[{"v":"Inventory","state":"done"},{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"}]}]},{"say":"Search has one out-neighbor, Inventory, so the walk must go there.","ops":[{"panel":"chance","unset":["Search"]},{"panel":"chance","set":{"Inventory":"100%"}},{"v":"Inventory","state":"waiting"},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"The walk moves to Inventory.","ops":[{"v":"Search","state":"done"},{"e":["Search","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"}]}]},{"say":"Inventory has one out-neighbor, Search, so the walk must go there.","ops":[{"panel":"chance","unset":["Inventory"]},{"panel":"chance","set":{"Search":"100%"}},{"v":"Search","state":"waiting"},{"e":["Inventory","Search"],"state":"examined"}]},{"say":"The walk moves to Search.","ops":[{"v":"Inventory","state":"done"},{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"order","list":[{"key":"Gateway"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"},{"key":"Inventory"},{"key":"Search"}]}]},{"say":"Done. The walk reached its limit with 12 vertices, 3 of them different.","ops":[{"v":"Search","state":"done"}]}],"traceNote":"","verification":"The steps replay the walk gograph took when the server started, so a restart can show a different walk.","snippet":"it, err := traverse.NewRandomWalkIterator(g, \"Gateway\", 12)\nif err != nil {\n\treturn err\n}\nfor it.HasNext() {\n\tfmt.Println(it.Next().Label())\n}"}
