traverse.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  // BreadthFirst implements stateful breadth-first graph traversal.
    16  type BreadthFirst struct {
    17  	EdgeFilter func(graph.Edge) bool
    18  	Visit      func(u, v graph.Node)
    19  	queue      linear.NodeQueue
    20  	visited    *intsets.Sparse
    21  }
    22  
    23  // Walk performs a breadth-first traversal of the graph g starting from the given node,
    24  // depending on the EdgeFilter field and the until parameter if they are non-nil. The
    25  // traversal follows edges for which EdgeFilter(edge) is true and returns the first node
    26  // for which until(node, depth) is true. During the traversal, if the Visit field is
    27  // non-nil, it is called with the nodes joined by each followed edge.
    28  func (b *BreadthFirst) Walk(g graph.Graph, from graph.Node, until func(n graph.Node, d int) bool) graph.Node {
    29  	if b.visited == nil {
    30  		b.visited = &intsets.Sparse{}
    31  	}
    32  	b.queue.Enqueue(from)
    33  	b.visited.Insert(from.ID())
    34  
    35  	var (
    36  		depth     int
    37  		children  int
    38  		untilNext = 1
    39  	)
    40  	for b.queue.Len() > 0 {
    41  		t := b.queue.Dequeue()
    42  		if until != nil && until(t, depth) {
    43  			return t
    44  		}
    45  		for _, n := range g.From(t) {
    46  			if b.EdgeFilter != nil && !b.EdgeFilter(g.Edge(t, n)) {
    47  				continue
    48  			}
    49  			if b.visited.Has(n.ID()) {
    50  				continue
    51  			}
    52  			if b.Visit != nil {
    53  				b.Visit(t, n)
    54  			}
    55  			b.visited.Insert(n.ID())
    56  			children++
    57  			b.queue.Enqueue(n)
    58  		}
    59  		if untilNext--; untilNext == 0 {
    60  			depth++
    61  			untilNext = children
    62  			children = 0
    63  		}
    64  	}
    65  
    66  	return nil
    67  }
    68  
    69  // WalkAll calls Walk for each unvisited node of the graph g using edges independent
    70  // of their direction. The functions before and after are called prior to commencing
    71  // and after completing each walk if they are non-nil respectively. The function
    72  // during is called on each node as it is traversed.
    73  func (b *BreadthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node)) {
    74  	b.Reset()
    75  	for _, from := range g.Nodes() {
    76  		if b.Visited(from) {
    77  			continue
    78  		}
    79  		if before != nil {
    80  			before()
    81  		}
    82  		b.Walk(g, from, func(n graph.Node, _ int) bool {
    83  			if during != nil {
    84  				during(n)
    85  			}
    86  			return false
    87  		})
    88  		if after != nil {
    89  			after()
    90  		}
    91  	}
    92  }
    93  
    94  // Visited returned whether the node n was visited during a traverse.
    95  func (b *BreadthFirst) Visited(n graph.Node) bool {
    96  	return b.visited != nil && b.visited.Has(n.ID())
    97  }
    98  
    99  // Reset resets the state of the traverser for reuse.
   100  func (b *BreadthFirst) Reset() {
   101  	b.queue.Reset()
   102  	if b.visited != nil {
   103  		b.visited.Clear()
   104  	}
   105  }
   106  
   107  // DepthFirst implements stateful depth-first graph traversal.
   108  type DepthFirst struct {
   109  	EdgeFilter func(graph.Edge) bool
   110  	Visit      func(u, v graph.Node)
   111  	stack      linear.NodeStack
   112  	visited    *intsets.Sparse
   113  }
   114  
   115  // Walk performs a depth-first traversal of the graph g starting from the given node,
   116  // depending on the EdgeFilter field and the until parameter if they are non-nil. The
   117  // traversal follows edges for which EdgeFilter(edge) is true and returns the first node
   118  // for which until(node) is true. During the traversal, if the Visit field is non-nil, it
   119  // is called with the nodes joined by each followed edge.
   120  func (d *DepthFirst) Walk(g graph.Graph, from graph.Node, until func(graph.Node) bool) graph.Node {
   121  	if d.visited == nil {
   122  		d.visited = &intsets.Sparse{}
   123  	}
   124  	d.stack.Push(from)
   125  	d.visited.Insert(from.ID())
   126  
   127  	for d.stack.Len() > 0 {
   128  		t := d.stack.Pop()
   129  		if until != nil && until(t) {
   130  			return t
   131  		}
   132  		for _, n := range g.From(t) {
   133  			if d.EdgeFilter != nil && !d.EdgeFilter(g.Edge(t, n)) {
   134  				continue
   135  			}
   136  			if d.visited.Has(n.ID()) {
   137  				continue
   138  			}
   139  			if d.Visit != nil {
   140  				d.Visit(t, n)
   141  			}
   142  			d.visited.Insert(n.ID())
   143  			d.stack.Push(n)
   144  		}
   145  	}
   146  
   147  	return nil
   148  }
   149  
   150  // WalkAll calls Walk for each unvisited node of the graph g using edges independent
   151  // of their direction. The functions before and after are called prior to commencing
   152  // and after completing each walk if they are non-nil respectively. The function
   153  // during is called on each node as it is traversed.
   154  func (d *DepthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node)) {
   155  	d.Reset()
   156  	for _, from := range g.Nodes() {
   157  		if d.Visited(from) {
   158  			continue
   159  		}
   160  		if before != nil {
   161  			before()
   162  		}
   163  		d.Walk(g, from, func(n graph.Node) bool {
   164  			if during != nil {
   165  				during(n)
   166  			}
   167  			return false
   168  		})
   169  		if after != nil {
   170  			after()
   171  		}
   172  	}
   173  }
   174  
   175  // Visited returned whether the node n was visited during a traverse.
   176  func (d *DepthFirst) Visited(n graph.Node) bool {
   177  	return d.visited != nil && d.visited.Has(n.ID())
   178  }
   179  
   180  // Reset resets the state of the traverser for reuse.
   181  func (d *DepthFirst) Reset() {
   182  	d.stack = d.stack[:0]
   183  	if d.visited != nil {
   184  		d.visited.Clear()
   185  	}
   186  }
   187
View as plain text