Created
September 16, 2013 14:50
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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