func visit(graph Graph, frontier container.List, fn NodeVisitor) bool {
	visited := make(map[NodeID]bool)
	for frontier.Size() > 0 {
		next := frontier.Pop().(*visitInfo)
		visited[next.Node.ID] = true
		if fn(next.Node, next.Path, next.Weights) {
			return true
		}
		children, weights := graph.ChildrenWithWeights(next.Node.ID)
		for i := 0; i < len(children); i++ {
			if !visited[children[i].ID] {
				frontier.Push(&visitInfo{
					Node:    children[i],
					Path:    append(next.Path, children[i]),
					Weights: append(next.Weights, weights[i]),
				})
			}
		}
	}
	return false
}
Generic graph visitor method
package graph
import (
	"github.com/jesand/numgo/container"
	"github.com/jesand/numgo/matrix"
	"math"
	"strings"
)
func NewDenseAdjacencyGraph(directed bool, maxNodes int) Graph {
	return &adjacencyGraph{
		directed: directed,
		edges:    matrix.Dense(maxNodes, maxNodes).M(),
	}
}
func NewSparseAdjacencyGraph(directed bool, maxNodes int) Graph {
	return &adjacencyGraph{
		directed: directed,
		edges:    matrix.SparseCoo(maxNodes, maxNodes),
	}
}
type adjacencyGraph struct {
	directed bool
	nodes []Node
	edges matrix.Matrix
}
func (graph *adjacencyGraph) AddEdge(from, to NodeID) {
	graph.AddEdgeWithWeight(from, to, 1)
}
func (graph *adjacencyGraph) AddEdgeWithWeight(from, to NodeID, weight float64) {
	if int(from) >= len(graph.nodes) || int(to) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	graph.edges.ItemSet(weight, int(from), int(to))
	graph.nodes[from].OutDegree++
	graph.nodes[to].InDegree++
	if !graph.directed {
		graph.edges.ItemSet(weight, int(to), int(from))
		graph.nodes[to].OutDegree++
		graph.nodes[from].InDegree++
	}
}
func (graph *adjacencyGraph) AddNode(name string) NodeID {
	if len(graph.nodes) >= graph.edges.Rows() {
		panic(ErrGraphCapacity{})
	}
	id := NodeID(len(graph.nodes))
	graph.nodes = append(graph.nodes, Node{
		ID:        id,
		Name:      name,
		InDegree:  0,
		OutDegree: 0,
	})
	return id
}
func (graph adjacencyGraph) Children(of NodeID) (children []Node) {
	if int(of) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	for child := 0; child < len(graph.nodes); child++ {
		if graph.edges.Item(int(of), int(child)) != 0 {
			children = append(children, graph.nodes[child])
		}
	}
	return
}
func (graph adjacencyGraph) ChildrenWithWeights(of NodeID) (children []Node, weights []float64) {
	if int(of) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	for child := 0; child < len(graph.nodes); child++ {
		weight := graph.edges.Item(int(of), int(child))
		if weight != 0 {
			children = append(children, graph.nodes[child])
			weights = append(weights, weight)
		}
	}
	return
}
func (graph adjacencyGraph) Copy() Graph {
	result := &adjacencyGraph{
		directed: graph.directed,
		nodes:    make([]Node, len(graph.nodes)),
		edges:    graph.edges.Copy().M(),
	}
	copy(result.nodes[:], graph.nodes[:])
	return result
}
func (graph adjacencyGraph) HasEdge(from, to NodeID) bool {
	if int(from) >= len(graph.nodes) || int(to) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	return graph.edges.Item(int(from), int(to)) != 0
}
func (graph adjacencyGraph) HasEdges() bool {
	return graph.edges.CountNonzero() > 0
}
func (graph adjacencyGraph) HasCycles() bool {
	_, err := graph.TopologicalSort()
	return err != nil
}
func (graph adjacencyGraph) HasNodes() bool {
	return len(graph.nodes) > 0
}
func (graph adjacencyGraph) HasPath(from, to NodeID) bool {
	if int(from) >= len(graph.nodes) || int(to) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	p, _ := graph.ShortestPath(from, to)
	return len(p) > 0
}
func (graph adjacencyGraph) IsDag() bool {
	return graph.IsDirected() && !graph.HasCycles()
}
func (graph adjacencyGraph) IsDirected() bool {
	return graph.directed
}
func (graph adjacencyGraph) IsTree() bool {
	if !graph.IsDag() {
		return false
	}
	for _, node := range graph.nodes {
		if node.InDegree > 1 {
			return false
		}
	}
	return true
}
func (graph adjacencyGraph) Leaves() (leaves []Node) {
	for _, node := range graph.nodes {
		if node.OutDegree == 0 {
			leaves = append(leaves, node)
		}
	}
	return
}
func (graph adjacencyGraph) Node(id NodeID) Node {
	if int(id) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	return graph.nodes[id]
}
func (graph adjacencyGraph) Parents(of NodeID) (parents []Node) {
	if int(of) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	for parent := 0; parent < len(graph.nodes); parent++ {
		if graph.edges.Item(int(parent), int(of)) != 0 {
			parents = append(parents, graph.nodes[parent])
		}
	}
	return
}
func (graph adjacencyGraph) ParentsWithWeights(of NodeID) (parents []Node, weights []float64) {
	if int(of) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	for parent := 0; parent < len(graph.nodes); parent++ {
		weight := graph.edges.Item(int(parent), int(of))
		if weight != 0 {
			parents = append(parents, graph.nodes[parent])
			weights = append(weights, weight)
		}
	}
	return
}
func (graph *adjacencyGraph) RemoveEdge(from, to NodeID) {
	if int(from) >= len(graph.nodes) || int(to) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	} else if graph.edges.Item(int(from), int(to)) == 0 {
		return
	}
	graph.edges.ItemSet(0.0, int(from), int(to))
	graph.nodes[from].OutDegree--
	graph.nodes[to].InDegree--
	if !graph.directed {
		graph.edges.ItemSet(0.0, int(to), int(from))
		graph.nodes[to].OutDegree--
		graph.nodes[from].InDegree--
	}
}
func (graph adjacencyGraph) Roots() (roots []Node) {
	for _, node := range graph.nodes {
		if node.InDegree == 0 {
			roots = append(roots, node)
		}
	}
	return
}
func (graph adjacencyGraph) ShortestPath(from, to NodeID) (p []Node, w []float64) {
	if int(from) >= len(graph.nodes) || int(to) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	if from == to {
		return []Node{graph.nodes[from]}, []float64{}
	}
	var isNode = func(node Node, path []Node, weights []float64) bool {
		if node.ID == to {
			p = path
			w = weights
			return true
		}
		return false
	}
	graph.VisitBFS(from, isNode)
	return
}
func (graph adjacencyGraph) ShortestPathWeight(from, to NodeID) (weight float64) {
	if int(from) >= len(graph.nodes) || int(to) >= len(graph.nodes) {
		panic(ErrInvalidNode{})
	}
	path, weights := graph.ShortestPath(from, to)
	if len(path) == 0 {
		return math.Inf(1)
	}
	weight = 0
	for _, w := range weights {
		weight += w
	}
	return
}
func (graph adjacencyGraph) ShortestPathWeights() (weights [][]float64) {
	return graph.floydWarshallShortestPathWeights()
}
func (graph adjacencyGraph) floydWarshallShortestPathWeights() (weights [][]float64) {
	var numNodes = len(graph.nodes)
	for i := 0; i < numNodes; i++ {
		weights = append(weights, make([]float64, numNodes))
		for j := 0; j < numNodes; j++ {
			if i != j {
				weight := graph.edges.Item(i, j)
				if weight == 0 {
					weight = math.Inf(1)
				}
				weights[i][j] = weight
			}
		}
	}
	for k := 0; k < numNodes; k++ {
		for i := 0; i < numNodes; i++ {
			for j := 0; j < numNodes; j++ {
				path := weights[i][k] + weights[k][j]
				if path < weights[i][j] {
					weights[i][j] = path
				}
			}
		}
	}
	return
}
func (graph adjacencyGraph) Size() (nodes, edges int) {
	return len(graph.nodes), graph.edges.CountNonzero()
}
func (graph adjacencyGraph) String() string {
	var ss []string
	printed := make(map[NodeID]bool)
	for _, r := range graph.Roots() {
		ss = append(ss, graph.nodeString(r, 0, printed))
	}
	return strings.Join(ss, "\n")
}
func (graph adjacencyGraph) nodeString(node Node, depth int, printed map[NodeID]bool) string {
	var ss []string
	for i := 0; i < depth; i++ {
		ss = append(ss, "|  ")
	}
	ss = append(ss, node.Name)
	ss = append(ss, "\n")
	printed[node.ID] = true
	for _, child := range graph.Children(node.ID) {
		if printed[child.ID] {
			for i := 0; i < depth+1; i++ {
				ss = append(ss, "|  ")
			}
			ss = append(ss, child.Name)
			ss = append(ss, " <above>\n")
		} else {
			ss = append(ss, graph.nodeString(child, depth+1, printed))
		}
	}
	return strings.Join(ss, "")
}
func (graph adjacencyGraph) TopologicalSort() (order []Node, err error) {
	var (
		g     = graph.Copy()
		queue = g.Roots()
	)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, graph.Node(node.ID))
		for _, child := range g.Children(node.ID) {
			if child.InDegree == 1 {
				queue = append(queue, child)
			}
			g.RemoveEdge(node.ID, child.ID)
		}
	}
	if g.HasEdges() {
		return nil, ErrGraphIsCyclic{}
	}
	return
}
func (graph adjacencyGraph) TransitiveClosure() Graph {
	var (
		numNodes = len(graph.nodes)
		g        = graph.Copy()
		weights  = g.ShortestPathWeights()
	)
	for i := 0; i < numNodes; i++ {
		for j := 0; j < numNodes; j++ {
			if i != j && graph.edges.Item(i, j) == 0 && !math.IsInf(weights[i][j], 1) {
				g.AddEdgeWithWeight(NodeID(i), NodeID(j), weights[i][j])
			}
		}
	}
	return g
}
func (graph adjacencyGraph) TransitiveReduction() Graph {
	var (
		numNodes = len(graph.nodes)
		g        = graph.Copy().(*adjacencyGraph)
	)
	weights := g.ShortestPathWeights()
	for i := 0; i < numNodes; i++ {
		for j := 0; j < numNodes; j++ {
			if weights[i][j] != 0 && !math.IsInf(weights[i][j], 1) {
				for k := 0; k < numNodes; k++ {
					if weights[j][k] != 0 && !math.IsInf(weights[j][k], 1) {
						g.RemoveEdge(NodeID(i), NodeID(k))
					}
				}
			}
		}
	}
	return g
}
type visitInfo struct {
	Node    Node
	Path    []Node
	Weights []float64
}