graph

package
v1.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 20, 2015 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	UnknownEdgeKind = "UnknownEdge"
	// ReferencedByEdgeKind is the kind to use if you're building reverse links that don't have a specific edge in the other direction
	// other uses are discouraged.  You should create a kind for your edge
	ReferencedByEdgeKind = "ReferencedBy"
	// ContainsEdgeKind is the kind to use if one node's contents logically contain another node's contents.  A given node can only have
	// a single inbound Contais edge.  The code does not prevent contains cycles, but that's insane, don't do that.
	ContainsEdgeKind = "Contains"
)
View Source 
var (
	UnknownNodeKind = "UnknownNode"
)

Functions

func AddReversedEdge 

func AddReversedEdge(g Interface, head, tail graph.Node, edgeKinds util.StringSet) bool

AddReversedEdge adds a reversed edge for every passed edge and preserves the existing edge. Used to convert a one directional edge into a bidirectional edge, but will create duplicate edges if a bidirectional edge between two nodes already exists.

func AllNodes 

func AllNodes(g Interface, node graph.Node) bool

AllNodes includes all nodes in the graph

func EnsureUnique 

func EnsureUnique(g UniqueNodeInitializer, name UniqueName, fn NodeInitializerFunc) graph.Node

func ExistingDirectEdge 

func ExistingDirectEdge(g Interface, head, tail graph.Node, edgeKinds util.StringSet) bool

ExistingDirectEdge returns true if both head and tail already exist in the graph and the edge kind is not ReferencedByEdgeKind (the generic reverse edge kind). This will purge the graph of any edges created by AddReversedEdge.

func Fprint added in v0.4.4 

func Fprint(out io.Writer, g Graph)

func GetContainingNode added in v1.0.1 

func GetContainingNode(g Graph, containedNode graph.Node) graph.Node

GetContainingNode returns the direct predecessor that is linked to the node by a ContainsEdgeKind. It returns nil if no container is found.

func GetTopLevelContainerNode added in v1.0.1 

func GetTopLevelContainerNode(g Graph, containedNode graph.Node) graph.Node

GetTopLevelContainerNode traverses the reverse ContainsEdgeKind edges until it finds a node that does not have an inbound ContainsEdgeKind edge. This could be the node itself

func NodesByKind 

func NodesByKind(g Interface, nodes []graph.Node, kinds ...string) [][]graph.Node

func ReverseExistingDirectEdge 

func ReverseExistingDirectEdge(g Interface, head, tail graph.Node, edgeKinds util.StringSet) bool

ReverseExistingDirectEdge reverses the order of the edge and drops the existing edge only if both head and tail already exist in the graph and the edge kind is not ReferencedByEdgeKind (the generic reverse edge kind).

func ReverseGraphEdge 

func ReverseGraphEdge(g Interface, head, tail graph.Node, edgeKinds util.StringSet) bool

ReverseGraphEdge reverses the order of the edge and drops the existing edge.

Types

type Edge 

type Edge struct {
	concrete.Edge
	// contains filtered or unexported fields
}

func NewEdge 

func NewEdge(head, tail graph.Node, kinds ...string) Edge

func (Edge) IsKind added in v1.0.3 

func (e Edge) IsKind(kind string) bool

func (Edge) Kinds added in v1.0.3 

func (e Edge) Kinds() util.StringSet

type EdgeFunc 

type EdgeFunc func(g Interface, head, tail graph.Node, edgeKinds util.StringSet) bool

EdgeFunc is passed a new graph, an edge in the current graph, and should mutate the new graph as needed. If true is returned, the existing edge will be added to the graph.

func AddGraphEdgesTo 

func AddGraphEdgesTo(g Interface) EdgeFunc

AddGraphEdgesTo returns an EdgeFunc that will add the selected edges to the passed graph.

func EdgesOfKind added in v1.0.3 

func EdgesOfKind(kinds ...string) EdgeFunc

EdgesOfKind returns a new EdgeFunc accepting the provided kinds of edges

type ExistenceChecker added in v1.0.2 

type ExistenceChecker interface {
	// Found returns true if the node represents an object that we don't have the backing object for
	Found() bool
}

ExistenceChecker is an interface for those nodes that can be created without a backing object. This can happen when a node wants an edge to a non-existent node. We know the node should exist, The graph needs something in that location to track the information we have about the node, but the backing object doesn't exist.

type Graph 

type Graph struct {
	// the standard graph
	graph.Directed
	// helper methods for switching on the kind and types of the node
	GraphDescriber
	// contains filtered or unexported fields
}

func New 

func New() Graph

New initializes a graph from input to output.

func (Graph) AddEdge 

func (g Graph) AddEdge(head, tail graph.Node, edgeKind string)

AddEdge implements MutableUniqueGraph

func (Graph) AddNode 

func (g Graph) AddNode(n graph.Node)

func (Graph) ConnectedEdgeSubgraph 

func (g Graph) ConnectedEdgeSubgraph(fn EdgeFunc) Graph

ConnectedEdgeSubgraph creates a new graph that iterates through all edges in the graph and includes all edges the provided function returns true for. Nodes not referenced by an edge will be dropped unless the function adds them explicitly.

func (Graph) EdgeSubgraph 

func (g Graph) EdgeSubgraph(edgeFn EdgeFunc) Graph

EdgeSubgraph returns the directed subgraph with only the edges that match the provided function.

func (Graph) Edges added in v1.0.3 

func (g Graph) Edges() []graph.Edge

func (Graph) Find added in v0.5.3 

func (g Graph) Find(name UniqueName) graph.Node

func (Graph) FindOrCreate 

func (g Graph) FindOrCreate(name UniqueName, fn NodeInitializerFunc) (graph.Node, bool)

func (Graph) InboundEdges added in v1.0.1 

func (g Graph) InboundEdges(node graph.Node, edgeKinds ...string) []graph.Edge

InboundEdges returns all the inbound edges to node that are in the list of edgeKinds if edgeKinds is empty, then all edges are returned

func (Graph) NodesByKind added in v1.0.2 

func (g Graph) NodesByKind(nodeKinds ...string) []graph.Node

func (Graph) OutboundEdges added in v1.0.1 

func (g Graph) OutboundEdges(node graph.Node, edgeKinds ...string) []graph.Edge

OutboundEdges returns all the outbound edges from node that are in the list of edgeKinds if edgeKinds is empty, then all edges are returned

func (Graph) PredecessorEdges 

func (g Graph) PredecessorEdges(node graph.Node, fn EdgeFunc, edgeKinds ...string)

PredecessorEdges invokes fn with all of the predecessor edges of node that have the specified edge kind.

func (Graph) PredecessorNodesByEdgeKind added in v1.0.2 

func (g Graph) PredecessorNodesByEdgeKind(node graph.Node, edgeKinds ...string) []graph.Node

func (Graph) RootNodes 

func (g Graph) RootNodes() []graph.Node

RootNodes returns all the roots of this graph.

func (Graph) String added in v1.0.1 

func (g Graph) String() string

func (Graph) Subgraph 

func (g Graph) Subgraph(nodeFn NodeFunc, edgeFn EdgeFunc) Graph

Subgraph returns the directed subgraph with only the nodes and edges that match the provided functions.

func (Graph) SubgraphWithNodes 

func (g Graph) SubgraphWithNodes(nodes []graph.Node, fn EdgeFunc) Graph

SubgraphWithNodes returns the directed subgraph with only the listed nodes and edges that match the provided function.

func (Graph) SuccessorEdges 

func (g Graph) SuccessorEdges(node graph.Node, fn EdgeFunc, edgeKinds ...string)

SuccessorEdges invokes fn with all of the successor edges of node that have the specified edge kind.

func (Graph) SuccessorNodesByEdgeKind added in v1.0.2 

func (g Graph) SuccessorNodesByEdgeKind(node graph.Node, edgeKinds ...string) []graph.Node

func (Graph) SuccessorNodesByNodeAndEdgeKind added in v1.0.2 

func (g Graph) SuccessorNodesByNodeAndEdgeKind(node graph.Node, nodeKind, edgeKind string) []graph.Node

func (Graph) SyntheticNodes added in v1.0.2 

func (g Graph) SyntheticNodes() []graph.Node

SyntheticNodes returns back the set of nodes that were created in response to edge requests, but did not exist

type GraphDescriber 

type GraphDescriber interface {
	Name(node graph.Node) string
	Kind(node graph.Node) string
	Object(node graph.Node) interface{}
	EdgeKinds(edge graph.Edge) util.StringSet
}

type Interface 

type Interface interface {
	graph.Directed

	GraphDescriber
	MutableUniqueGraph

	Edges() []graph.Edge
}

type MutableDirectedEdge 

type MutableDirectedEdge interface {
	AddEdge(head, tail graph.Node, edgeKind string)
}

type MutableUniqueGraph 

type MutableUniqueGraph interface {
	graph.Mutable
	MutableDirectedEdge
	UniqueNodeInitializer
	NodeFinder
}

type Node 

type Node struct {
	concrete.Node
	UniqueName
}

type NodeFinder added in v0.5.3 

type NodeFinder interface {
	Find(name UniqueName) graph.Node
}

type NodeFunc 

type NodeFunc func(g Interface, n graph.Node) bool

NodeFunc is passed a new graph, a node in the graph, and should return true if the node should be included.

func NodesOfKind added in v1.0.3 

func NodesOfKind(kinds ...string) NodeFunc

NodesOfKind returns a new NodeFunc accepting the provided kinds of nodes

type NodeInitializerFunc 

type NodeInitializerFunc func(Node) graph.Node

type NodeSet 

type NodeSet map[int]struct{}

func (NodeSet) Add 

func (n NodeSet) Add(id int)

func (NodeSet) Has 

func (n NodeSet) Has(id int) bool

type ResourceNode added in v1.0.2 

type ResourceNode interface {
	ResourceString() string
}

type SortedNodes added in v1.0.3 

type SortedNodes []graph.Node

func (SortedNodes) Len added in v1.0.3 

func (m SortedNodes) Len() int

func (SortedNodes) Less added in v1.0.3 

func (m SortedNodes) Less(i, j int) bool

func (SortedNodes) Swap added in v1.0.3 

func (m SortedNodes) Swap(i, j int)

type UniqueName 

type UniqueName string

func GetUniqueRuntimeObjectNodeName added in v1.0.1 

func GetUniqueRuntimeObjectNodeName(nodeKind string, obj runtime.Object) UniqueName

func (UniqueName) UniqueName 

func (n UniqueName) UniqueName() string

type UniqueNameFunc added in v1.0.1 

type UniqueNameFunc func(obj interface{}) UniqueName

type UniqueNodeInitializer 

type UniqueNodeInitializer interface {
	FindOrCreate(name UniqueName, fn NodeInitializerFunc) (graph.Node, bool)
}

UniqueNodeInitializer is a graph that allows nodes with a unique name to be added without duplication. If the node is newly added, true will be returned.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.