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 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

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

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 MutableDirectedEdge

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

type Node

type Node struct {
	concrete.Node
	UniqueName
}

type NodeFinder

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.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL