Example output:
prepping work area
getting bread
adding peanut-butter
adding jelly
combining bread slices to form sandwich
Last active
July 10, 2021 21:25
-
-
Save sayotte/b57a50777b33a913c5096df0942f03d1 to your computer and use it in GitHub Desktop.
Topological sorting example
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
| package main | |
| import "fmt" | |
| func prepWorkAreaFunction(){ fmt.Println("prepping work area")} | |
| func getBreadFunction(){ fmt.Println("getting bread")} | |
| func addPBFunction(){ fmt.Println("adding peanut-butter")} | |
| func addJellyFunction(){ fmt.Println("adding jelly")} | |
| func combineSlicesFunction(){ fmt.Println("combining bread slices to form sandwich")} | |
| type graphNode struct { | |
| Implementation func() | |
| Requires []string | |
| Visited bool | |
| } | |
| var graph = map[string]*graphNode{ | |
| "combine PB&J bread slices": {Implementation: combineSlicesFunction, Requires: []string{"add peanut-butter", "add jelly"}}, | |
| "add peanut-butter": {Implementation: addPBFunction, Requires: []string{"get bread"}}, | |
| "prep work area": {Implementation: prepWorkAreaFunction}, | |
| "get bread": {Implementation: getBreadFunction, Requires: []string{"prep work area"}}, | |
| "add jelly": {Implementation: addJellyFunction, Requires: []string{"get bread"}}, | |
| } | |
| func visitPostOrderRecursive(graph map[string]*graphNode, startingKey string) []string { | |
| graphNode := graph[startingKey] | |
| if graphNode.Visited { return nil } | |
| graphNode.Visited = true | |
| var requiredKeys []string | |
| for _, requiredKey := range graphNode.Requires { | |
| requiredKeys = append(requiredKeys, visitPostOrderRecursive(graph, requiredKey)...) | |
| } | |
| requiredKeys = append(requiredKeys, startingKey) | |
| return requiredKeys | |
| } | |
| func main() { | |
| var sorted []string | |
| // visit all nodes in the graph | |
| for key := range graph { | |
| sorted = append(sorted, visitPostOrderRecursive(graph, key)...) | |
| } | |
| for _, key := range sorted { | |
| graphNode := graph[key] | |
| graphNode.Implementation() | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment