package graph

import "k8s.io/kubernetes/third_party/forked/gonum/graph"

Index ¶

• func Copy(dst Builder, src Graph)
• type Builder
• type Directed
• type DirectedBuilder
• type Edge
• type EdgeRemover
• type EdgeSetter
• type Graph
• type Node
• type NodeAdder
• type NodeRemover
• type Undirected
• type UndirectedBuilder
• type Weighter

Package Files ¶

graph.go

func Copy ¶ Uses

func Copy(dst Builder, src Graph)

Copy copies nodes and edges as undirected edges from the source to the destination without first clearing the destination. Copy will panic if a node ID in the source graph matches a node ID in the destination.

If the source is undirected and the destination is directed both directions will be present in the destination after the copy is complete.

If the source is a directed graph, the destination is undirected, and a fundamental cycle exists with two nodes where the edge weights differ, the resulting destination graph's edge weight between those nodes is undefined. If there is a defined function to resolve such conflicts, an Undirect may be used to do this.

type Builder ¶ Uses

type Builder interface {
    NodeAdder
    EdgeSetter
}

Builder is a graph that can have nodes and edges added.

type Directed ¶ Uses

type Directed interface {
    Graph

    // HasEdgeFromTo returns whether an edge exists
    // in the graph from u to v.
    HasEdgeFromTo(u, v Node) bool

    // To returns all nodes that can reach directly
    // to the given node.
    To(Node) []Node
}

Directed is a directed graph.

type DirectedBuilder ¶ Uses

type DirectedBuilder interface {
    Directed
    Builder
}

DirectedBuilder is a directed graph builder.

type Edge ¶ Uses

type Edge interface {
    From() Node
    To() Node
    Weight() float64
}

Edge is a graph edge. In directed graphs, the direction of the edge is given from -> to, otherwise the edge is semantically unordered.

type EdgeRemover ¶ Uses

type EdgeRemover interface {
    // RemoveEdge removes the given edge, leaving the
    // terminal nodes. If the edge does not exist it
    // is a no-op.
    RemoveEdge(Edge)
}

EdgeRemover is an interface for removing nodes from a graph.

type EdgeSetter ¶ Uses

type EdgeSetter interface {
    // SetEdge adds an edge from one node to another.
    // If the graph supports node addition the nodes
    // will be added if they do not exist, otherwise
    // SetEdge will panic.
    // If the IDs returned by e.From and e.To are
    // equal, SetEdge will panic.
    SetEdge(e Edge)
}

EdgeSetter is an interface for adding edges to a graph.

type Graph ¶ Uses

type Graph interface {
    // Has returns whether the node exists within the graph.
    Has(Node) bool

    // Nodes returns all the nodes in the graph.
    Nodes() []Node

    // From returns all nodes that can be reached directly
    // from the given node.
    From(Node) []Node

    // HasEdgeBeteen returns whether an edge exists between
    // nodes x and y without considering direction.
    HasEdgeBetween(x, y Node) bool

    // Edge returns the edge from u to v if such an edge
    // exists and nil otherwise. The node v must be directly
    // reachable from u as defined by the From method.
    Edge(u, v Node) Edge
}

Graph is a generalized graph.

type Node ¶ Uses

type Node interface {
    ID() int
}

Node is a graph node. It returns a graph-unique integer ID.

type NodeAdder ¶ Uses

type NodeAdder interface {
    // NewNodeID returns a new unique arbitrary ID.
    NewNodeID() int

    // Adds a node to the graph. AddNode panics if
    // the added node ID matches an existing node ID.
    AddNode(Node)
}

NodeAdder is an interface for adding arbitrary nodes to a graph.

type NodeRemover ¶ Uses

type NodeRemover interface {
    // RemoveNode removes a node from the graph, as
    // well as any edges attached to it. If the node
    // is not in the graph it is a no-op.
    RemoveNode(Node)
}

NodeRemover is an interface for removing nodes from a graph.

type Undirected ¶ Uses

type Undirected interface {
    Graph

    // EdgeBetween returns the edge between nodes x and y.
    EdgeBetween(x, y Node) Edge
}

Undirected is an undirected graph.

type UndirectedBuilder ¶ Uses

type UndirectedBuilder interface {
    Undirected
    Builder
}

UndirectedBuilder is an undirected graph builder.

type Weighter ¶ Uses

type Weighter interface {
    // Weight returns the weight for the edge between
    // x and y if Edge(x, y) returns a non-nil Edge.
    // If x and y are the same node or there is no
    // joining edge between the two nodes the weight
    // value returned is implementation dependent.
    // Weight returns true if an edge exists between
    // x and y or if x and y have the same ID, false
    // otherwise.
    Weight(x, y Node) (w float64, ok bool)
}

Weighter defines graphs that can report edge weights.

Directories ¶