graph

package
v1.0.1 Latest Latest
Warning

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

 Go to latest Published: Jun 30, 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, edgeKind string) 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, edgeKind string) 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, edgeKind string) 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, edgeKind string) bool

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

Types

type Edge 

type Edge struct {
	concrete.Edge
	K string
}

func NewEdge 

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

func (Edge) Kind 

func (e Edge) Kind() string

type EdgeFunc 

type EdgeFunc func(g Interface, head, tail graph.Node, edgeKind string) 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.

type Graph 

type Graph struct {
	// the standard graph
	graph.DirectedGraph
	// 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) EdgeList 

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

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) 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) 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, edgeKind ...string)

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

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, edgeKind ...string)

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

type GraphDescriber 

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

type Interface 

type Interface interface {
	graph.DirectedGraph
	graph.EdgeLister

	GraphDescriber
	MutableUniqueGraph
}

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.

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 SortedNodeList added in v1.0.1 

type SortedNodeList []graph.Node

func (SortedNodeList) Len added in v1.0.1 

func (m SortedNodeList) Len() int

func (SortedNodeList) Less added in v1.0.1 

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

func (SortedNodeList) Swap added in v1.0.1 

func (m SortedNodeList) 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.