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.

Import cycles

Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.

A directed graph with 18 vertices and 30 edges.

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?

Use it in Go

it, err := traverse.NewRandomWalkIterator(g, "main", 20)
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