Topological sorting example

0-toposort.go

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()
	}
}

1-README.md

Example output:

prepping work area
getting bread
adding peanut-butter
adding jelly
combining bread slices to form sandwich