Random walk

Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.

Time complexity O(steps × degree), gograph function traverse.NewRandomWalkIterator.

Microservice calls

Nine services of an online shop. Each edge is a call from one service to another, and some services call each other back.

A directed graph with 9 vertices and 15 edges.

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?

Use it in Go

it, err := traverse.NewRandomWalkIterator(g, "Gateway", 12)
if err != nil {
	return err
}
for it.HasNext() {
	fmt.Println(it.Next().Label())
}

Example graphs

• Microservice calls, 9 vertices and 15 edges
• Import cycles, 18 vertices and 30 edges
• Linked web pages, 40 vertices and 114 edges
• Web crawl, 100 vertices and 274 edges

More in Traversal

• Breadth-first: Visits vertices level by level from a start vertex.
• Depth-first: Follows one path as deep as it can, then continues from the most recently found vertex.
• Closest-first: Visits vertices in order of their distance from a start vertex, nearest first.

All algorithms