Documentation

Overview

    Package traverse provides basic graph traversal primitives.

    Index

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    Types

    type BreadthFirst

    type BreadthFirst struct {
    	// Visit is called on all nodes on their first visit.
    	Visit func(graph.Node)
    
    	// Traverse is called on all edges that may be traversed
    	// during the walk. This includes edges that would hop to
    	// an already visited node.
    	//
    	// The value returned by Traverse determines whether
    	// an edge can be traversed during the walk.
    	Traverse func(graph.Edge) bool
    	// contains filtered or unexported fields
    }

      BreadthFirst implements stateful breadth-first graph traversal.

      func (*BreadthFirst) Reset

      func (b *BreadthFirst) Reset()

        Reset resets the state of the traverser for reuse.

        func (*BreadthFirst) Visited

        func (b *BreadthFirst) Visited(n graph.Node) bool

          Visited returned whether the node n was visited during a traverse.

          func (*BreadthFirst) Walk

          func (b *BreadthFirst) Walk(g Graph, from graph.Node, until func(n graph.Node, d int) bool) graph.Node

            Walk performs a breadth-first traversal of the graph g starting from the given node, depending on the Traverse field and the until parameter if they are non-nil. The traversal follows edges for which Traverse(edge) is true and returns the first node for which until(node, depth) is true. During the traversal, if the Visit field is non-nil, it is called with each node the first time it is visited.

            func (*BreadthFirst) WalkAll

            func (b *BreadthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))

              WalkAll calls Walk for each unvisited node of the graph g using edges independent of their direction. The functions before and after are called prior to commencing and after completing each walk if they are non-nil respectively. The function during is called on each node as it is traversed.

              type DepthFirst

              type DepthFirst struct {
              	// Visit is called on all nodes on their first visit.
              	Visit func(graph.Node)
              
              	// Traverse is called on all edges that may be traversed
              	// during the walk. This includes edges that would hop to
              	// an already visited node.
              	//
              	// The value returned by Traverse determines whether an
              	// edge can be traversed during the walk.
              	Traverse func(graph.Edge) bool
              	// contains filtered or unexported fields
              }

                DepthFirst implements stateful depth-first graph traversal.

                func (*DepthFirst) Reset

                func (d *DepthFirst) Reset()

                  Reset resets the state of the traverser for reuse.

                  func (*DepthFirst) Visited

                  func (d *DepthFirst) Visited(n graph.Node) bool

                    Visited returned whether the node n was visited during a traverse.

                    func (*DepthFirst) Walk

                    func (d *DepthFirst) Walk(g Graph, from graph.Node, until func(graph.Node) bool) graph.Node

                      Walk performs a depth-first traversal of the graph g starting from the given node, depending on the Traverse field and the until parameter if they are non-nil. The traversal follows edges for which Traverse(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 each node the first time it is visited.

                      func (*DepthFirst) WalkAll

                      func (d *DepthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))

                        WalkAll calls Walk for each unvisited node of the graph g using edges independent of their direction. The functions before and after are called prior to commencing and after completing each walk if they are non-nil respectively. The function during is called on each node as it is traversed.

                        type Graph

                        type Graph interface {
                        	// From returns all nodes that can be reached directly
                        	// from the node with the given ID.
                        	From(id int64) graph.Nodes
                        
                        	// Edge returns the edge from u to v, with IDs uid and vid,
                        	// if such an edge exists and nil otherwise. The node v
                        	// must be directly reachable from u as defined by
                        	// the From method.
                        	Edge(uid, vid int64) graph.Edge
                        }

                          Graph is the subset of graph.Graph necessary for graph traversal.

                          Source Files