kubernetes visit_depth_first 源码

2022-09-18
浏览 (636)

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

相关信息

kubernetes 源码目录

相关文章

kubernetes traverse 源码

0 赞

所属分类： 后端技术
本文标签： golang docker
版权声明： 原创文章如转载，请注明本文链接: https://www.seaxiang.com/blog/533042bb31304e73bf9913c5be549980

热门推荐

1、直接访问google.com
2、 - 优质文章
3、 gate.io
4、 harmony 鸿蒙hdc使用指导
5、 harmony 鸿蒙初识ArkTS语言
6、 harmony 鸿蒙ArkUI组件（ArkTS）开发常见问题
7、 flink kafka connector scan.startup.mode 的几个选项
8、 golang
9、 openharmony
10、 Vue中input框自动聚焦

Loading...