kubernetes visit_depth_first 源码
kubernetes visit_depth_first 代码
文件路径：/third_party/forked/gonum/graph/traverse/visit_depth_first.go
// Copyright ©2015 The gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package traverse provides basic graph traversal primitives.
package traverse
import (
"golang.org/x/tools/container/intsets"
"k8s.io/kubernetes/third_party/forked/gonum/graph"
"k8s.io/kubernetes/third_party/forked/gonum/graph/internal/linear"
)
// VisitableGraph
type VisitableGraph interface {
graph.Graph
// VisitFrom invokes visitor with all nodes that can be reached directly from the given node.
// If visitor returns false, visiting is short-circuited.
VisitFrom(from graph.Node, visitor func(graph.Node) (shouldContinue bool))
}
// VisitingDepthFirst implements stateful depth-first graph traversal on a visitable graph.
type VisitingDepthFirst struct {
EdgeFilter func(graph.Edge) bool
Visit func(u, v graph.Node)
stack linear.NodeStack
visited *intsets.Sparse
}
// Walk performs a depth-first traversal of the graph g starting from the given node,
// depending on the EdgeFilter field and the until parameter if they are non-nil. The
// traversal follows edges for which EdgeFilter(edge) is true and returns the first node
// for which until(node) is true. During the traversal, if the Visit field is non-nil, it
// is called with the nodes joined by each followed edge.
func (d *VisitingDepthFirst) Walk(g VisitableGraph, from graph.Node, until func(graph.Node) bool) graph.Node {
if d.visited == nil {
d.visited = &intsets.Sparse{}
}
d.stack.Push(from)
d.visited.Insert(from.ID())
if until != nil && until(from) {
return from
}
var found graph.Node
for d.stack.Len() > 0 {
t := d.stack.Pop()
g.VisitFrom(t, func(n graph.Node) (shouldContinue bool) {
if d.EdgeFilter != nil && !d.EdgeFilter(g.Edge(t, n)) {
return true
}
if d.visited.Has(n.ID()) {
return true
}
if d.Visit != nil {
d.Visit(t, n)
}
d.visited.Insert(n.ID())
d.stack.Push(n)
if until != nil && until(n) {
found = n
return false
}
return true
})
if found != nil {
return found
}
}
return nil
}
// Visited returned whether the node n was visited during a traverse.
func (d *VisitingDepthFirst) Visited(n graph.Node) bool {
return d.visited != nil && d.visited.Has(n.ID())
}
// Reset resets the state of the traverser for reuse.
func (d *VisitingDepthFirst) Reset() {
d.stack = d.stack[:0]
if d.visited != nil {
d.visited.Clear()
}
}
相关信息
相关文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
6、 golang
-
8、 openharmony