{"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":"import-cycles","name":"Import cycles","description":"Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"main","x":500,"y":80},{"id":"cli","x":180,"y":240},{"id":"api","x":560,"y":200},{"id":"config","x":860,"y":320},{"id":"handlers","x":420,"y":340},{"id":"middleware","x":680,"y":370},{"id":"auth","x":720,"y":470},{"id":"session","x":700,"y":640},{"id":"users","x":480,"y":540},{"id":"billing","x":280,"y":470},{"id":"invoices","x":300,"y":650},{"id":"models","x":480,"y":790},{"id":"db","x":180,"y":800},{"id":"cache","x":320,"y":900},{"id":"email","x":700,"y":800},{"id":"templates","x":880,"y":860},{"id":"utils","x":900,"y":480},{"id":"logging","x":900,"y":660}],"edges":[{"from":"main","to":"cli"},{"from":"main","to":"api"},{"from":"main","to":"config"},{"from":"cli","to":"config"},{"from":"cli","to":"db"},{"from":"api","to":"handlers"},{"from":"api","to":"middleware"},{"from":"api","to":"config"},{"from":"handlers","to":"auth"},{"from":"handlers","to":"users"},{"from":"handlers","to":"billing"},{"from":"middleware","to":"auth"},{"from":"middleware","to":"logging"},{"from":"auth","to":"session"},{"from":"session","to":"users"},{"from":"users","to":"auth"},{"from":"users","to":"billing"},{"from":"users","to":"models"},{"from":"billing","to":"invoices"},{"from":"invoices","to":"users"},{"from":"invoices","to":"models"},{"from":"invoices","to":"email"},{"from":"models","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"models"},{"from":"email","to":"templates"},{"from":"templates","to":"email"},{"from":"config","to":"utils"},{"from":"utils","to":"logging"},{"from":"logging","to":"utils"}],"details":{"vertices":18,"edges":30,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.09803921568627451,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":1,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Starting from main, a reader opens one of the imported packages at random, then does the same from there. Which packages do they read in 20 stops, counting main?","params":{"start":"main","steps":20},"result":{"kind":"order","vertices":["main","cli","config","utils","logging","utils","logging","utils","logging","utils","logging","utils","logging","utils","logging","utils","logging","utils","logging","utils"]},"answer":"On this run, the walk from main went through 20 vertices, 5 of them different: main, cli, config, utils, logging, utils, logging, utils, logging, utils, and so on to utils.","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 main. The walk stops after 20 vertices, or sooner at a vertex with no outgoing edges.","ops":[{"v":"main","state":"current"},{"panel":"order","list":[{"key":"main"}]}]},{"say":"main has 3 out-neighbors, so each has a 1 in 3 chance.","ops":[{"panel":"chance","set":{"cli":"33.3%"}},{"v":"cli","state":"waiting"},{"e":["main","cli"],"state":"examined"},{"panel":"chance","set":{"api":"33.3%"}},{"v":"api","state":"waiting"},{"e":["main","api"],"state":"examined"},{"panel":"chance","set":{"config":"33.3%"}},{"v":"config","state":"waiting"},{"e":["main","config"],"state":"examined"}]},{"say":"The walk picks cli, which had a 33.3% chance.","ops":[{"v":"main","state":"done"},{"v":"api","state":"idle"},{"e":["main","api"],"state":"idle"},{"v":"config","state":"idle"},{"e":["main","config"],"state":"idle"},{"e":["main","cli"],"state":"tree"},{"v":"cli","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"}]}]},{"say":"cli has 2 out-neighbors, so each has a 1 in 2 chance.","ops":[{"panel":"chance","unset":["cli","api"]},{"panel":"chance","set":{"config":"50%"}},{"v":"config","state":"waiting"},{"e":["cli","config"],"state":"examined"},{"panel":"chance","set":{"db":"50%"}},{"v":"db","state":"waiting"},{"e":["cli","db"],"state":"examined"}]},{"say":"The walk picks config, which had a 50% chance.","ops":[{"v":"cli","state":"done"},{"v":"db","state":"idle"},{"e":["cli","db"],"state":"idle"},{"e":["cli","config"],"state":"tree"},{"v":"config","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"}]}]},{"say":"config has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["config","db"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["config","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"config","state":"done"},{"e":["config","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"utils has one out-neighbor, logging, so the walk must go there.","ops":[{"panel":"chance","unset":["utils"]},{"panel":"chance","set":{"logging":"100%"}},{"v":"logging","state":"waiting"},{"e":["utils","logging"],"state":"examined"}]},{"say":"The walk moves to logging.","ops":[{"v":"utils","state":"done"},{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging has one out-neighbor, utils, so the walk must go there.","ops":[{"panel":"chance","unset":["logging"]},{"panel":"chance","set":{"utils":"100%"}},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"examined"}]},{"say":"The walk moves to utils.","ops":[{"v":"logging","state":"done"},{"e":["logging","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"},{"key":"logging"},{"key":"utils"}]}]},{"say":"Done. The walk reached its limit with 20 vertices, 5 of them different.","ops":[{"v":"utils","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, \"main\", 20)\nif err != nil {\n\treturn err\n}\nfor it.HasNext() {\n\tfmt.Println(it.Next().Label())\n}"}
