Skip to content

Instantly share code, notes, and snippets.

@wkschwartz
Created September 16, 2013 14:50
Show Gist options
  • Save wkschwartz/6581689 to your computer and use it in GitHub Desktop.
Save wkschwartz/6581689 to your computer and use it in GitHub Desktop.
An example of using Ruby-block-like callbacks for iteration in Go. This example is basic depth-first search on an undirected graph. The function using the "block" is `dfs`, at the end.
// Undirected graph where each node is labeled by a small integer.
type Graph struct {
neighbors [][]int // a list of neighbors for each node
}
// Omitting code to initialize a graph. The initializer would take the number
// of nodes and set up the neighbors array to be the right length. Another method
// would be available to add a neighbor to a given vertex. That way for a
// Graph `g`, `g.neighbors[node]` would be an array of nodes adjacent to `node`.
// `ForEachNeighbor` repeatedly calls function `block` on the nodes that are
// adjacent in the graph to `node`
func (g *Graph) ForEachNeighbor(node int, block func(neighbor int)) {
for _, neighbor := range neighbors[node] { // ignore index (_)
block(neighbor)
}
}
// Search a graph depth first (always choosing the next node to be farther away from the
// starting node `origin`, if one is available). `visited` is the return value (Go has named
// return values). `visited` is an array of bools with one slot for each node. A node is marked
// true if it's visited on the serach. This allows us to see which which nodes are connected
// by some path in the graph to `origin`.
func (g *Graph) WhichNodesAreConnected(origin int) (visited []bool){
visited = make([]bool, len(g.neighbors)) // Go automatically fills the array with falses
visited[origin] = true
g.dfs(origin, visited)
return // `visited` automatically returned since it's a named return value
}
// Recursive part of the depth first earch algorithm
func (g *Graph) dfs(origin int, visited []bool)
g.ForEachNeighbor(origin, func(neighbor int) {
if !visited[neighbor] {
visited[neighbor] = true
g.dfs(neighbor, visited)
}
return
}
return
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment