visit_depth_first.go

Documentation: k8s.io/kubernetes/third_party/forked/gonum/graph/traverse

     1  // Copyright ©2015 The gonum Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package traverse provides basic graph traversal primitives.
     6  package traverse
     7  
     8  import (
     9  	"golang.org/x/tools/container/intsets"
    10  
    11  	"k8s.io/kubernetes/third_party/forked/gonum/graph"
    12  	"k8s.io/kubernetes/third_party/forked/gonum/graph/internal/linear"
    13  )
    14  
    15  // VisitableGraph
    16  type VisitableGraph interface {
    17  	graph.Graph
    18  
    19  	// VisitFrom invokes visitor with all nodes that can be reached directly from the given node.
    20  	// If visitor returns false, visiting is short-circuited.
    21  	VisitFrom(from graph.Node, visitor func(graph.Node) (shouldContinue bool))
    22  }
    23  
    24  // VisitingDepthFirst implements stateful depth-first graph traversal on a visitable graph.
    25  type VisitingDepthFirst struct {
    26  	EdgeFilter func(graph.Edge) bool
    27  	Visit      func(u, v graph.Node)
    28  	stack      linear.NodeStack
    29  	visited    *intsets.Sparse
    30  }
    31  
    32  // Walk performs a depth-first traversal of the graph g starting from the given node,
    33  // depending on the EdgeFilter field and the until parameter if they are non-nil. The
    34  // traversal follows edges for which EdgeFilter(edge) is true and returns the first node
    35  // for which until(node) is true. During the traversal, if the Visit field is non-nil, it
    36  // is called with the nodes joined by each followed edge.
    37  func (d *VisitingDepthFirst) Walk(g VisitableGraph, from graph.Node, until func(graph.Node) bool) graph.Node {
    38  	if d.visited == nil {
    39  		d.visited = &intsets.Sparse{}
    40  	}
    41  	d.stack.Push(from)
    42  	d.visited.Insert(from.ID())
    43  	if until != nil && until(from) {
    44  		return from
    45  	}
    46  
    47  	var found graph.Node
    48  	for d.stack.Len() > 0 {
    49  		t := d.stack.Pop()
    50  		g.VisitFrom(t, func(n graph.Node) (shouldContinue bool) {
    51  			if d.EdgeFilter != nil && !d.EdgeFilter(g.Edge(t, n)) {
    52  				return true
    53  			}
    54  			if d.visited.Has(n.ID()) {
    55  				return true
    56  			}
    57  			if d.Visit != nil {
    58  				d.Visit(t, n)
    59  			}
    60  			d.visited.Insert(n.ID())
    61  			d.stack.Push(n)
    62  			if until != nil && until(n) {
    63  				found = n
    64  				return false
    65  			}
    66  			return true
    67  		})
    68  		if found != nil {
    69  			return found
    70  		}
    71  	}
    72  	return nil
    73  }
    74  
    75  // Visited returned whether the node n was visited during a traverse.
    76  func (d *VisitingDepthFirst) Visited(n graph.Node) bool {
    77  	return d.visited != nil && d.visited.Has(n.ID())
    78  }
    79  
    80  // Reset resets the state of the traverser for reuse.
    81  func (d *VisitingDepthFirst) Reset() {
    82  	d.stack = d.stack[:0]
    83  	if d.visited != nil {
    84  		d.visited.Clear()
    85  	}
    86  }
    87
View as plain text