package graph
import "gonum.org/v1/gonum/graph"
Package graph defines graph interfaces.
Routines to test contract compliance by user implemented graph types
are available in gonum.org/v1/gonum/graph/testgraph.
Code:play
Output:Example (Implicit)¶
package main
import (
"fmt"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/iterator"
"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/graph/topo"
)
// GraphNode is a node in an implicit graph.
type GraphNode struct {
id int64
neighbors []graph.Node
roots []*GraphNode
name string
}
// NewGraphNode returns a new GraphNode.
func NewGraphNode(id int64, name string) *GraphNode {
return &GraphNode{name: name, id: id}
}
// String returns the node's name.
func (g *GraphNode) String() string {
return g.name
}
// Node allows GraphNode to satisfy the graph.Graph interface.
func (g *GraphNode) Node(id int64) graph.Node {
if id == g.id {
return g
}
seen := map[int64]struct{}{g.id: {}}
for _, root := range g.roots {
if root.ID() == id || root.has(seen, id) {
return root
}
}
for _, n := range g.neighbors {
if n.ID() == id {
return n
}
if gn, ok := n.(*GraphNode); ok {
if gn.has(seen, id) {
return gn
}
}
}
return nil
}
func (g *GraphNode) has(seen map[int64]struct{}, id int64) bool {
for _, root := range g.roots {
if _, ok := seen[root.ID()]; ok {
continue
}
seen[root.ID()] = struct{}{}
if root.ID() == id || root.has(seen, id) {
return true
}
}
for _, n := range g.neighbors {
if _, ok := seen[n.ID()]; ok {
continue
}
seen[n.ID()] = struct{}{}
if n.ID() == id {
return true
}
if gn, ok := n.(*GraphNode); ok {
if gn.has(seen, id) {
return true
}
}
}
return false
}
// Nodes allows GraphNode to satisfy the graph.Graph interface.
func (g *GraphNode) Nodes() graph.Nodes {
nodes := []graph.Node{g}
seen := map[int64]struct{}{g.id: {}}
for _, root := range g.roots {
seen[root.ID()] = struct{}{}
nodes = root.nodes(append(nodes, root), seen)
}
for _, n := range g.neighbors {
seen[n.ID()] = struct{}{}
nodes = append(nodes, n)
if gn, ok := n.(*GraphNode); ok {
nodes = gn.nodes(nodes, seen)
}
}
return iterator.NewOrderedNodes(nodes)
}
func (g *GraphNode) nodes(dst []graph.Node, seen map[int64]struct{}) []graph.Node {
for _, root := range g.roots {
if _, ok := seen[root.ID()]; ok {
continue
}
seen[root.ID()] = struct{}{}
dst = root.nodes(append(dst, graph.Node(root)), seen)
}
for _, n := range g.neighbors {
if _, ok := seen[n.ID()]; ok {
continue
}
seen[n.ID()] = struct{}{}
dst = append(dst, n)
if gn, ok := n.(*GraphNode); ok {
dst = gn.nodes(dst, seen)
}
}
return dst
}
// From allows GraphNode to satisfy the graph.Graph interface.
func (g *GraphNode) From(id int64) graph.Nodes {
if id == g.ID() {
return iterator.NewOrderedNodes(g.neighbors)
}
seen := map[int64]struct{}{g.id: {}}
for _, root := range g.roots {
seen[root.ID()] = struct{}{}
if result := root.findNeighbors(id, seen); result != nil {
return iterator.NewOrderedNodes(result)
}
}
for _, n := range g.neighbors {
seen[n.ID()] = struct{}{}
if gn, ok := n.(*GraphNode); ok {
if result := gn.findNeighbors(id, seen); result != nil {
return iterator.NewOrderedNodes(result)
}
}
}
return graph.Empty
}
func (g *GraphNode) findNeighbors(id int64, seen map[int64]struct{}) []graph.Node {
if id == g.ID() {
return g.neighbors
}
for _, root := range g.roots {
if _, ok := seen[root.ID()]; ok {
continue
}
seen[root.ID()] = struct{}{}
if result := root.findNeighbors(id, seen); result != nil {
return result
}
}
for _, n := range g.neighbors {
if _, ok := seen[n.ID()]; ok {
continue
}
seen[n.ID()] = struct{}{}
if gn, ok := n.(*GraphNode); ok {
if result := gn.findNeighbors(id, seen); result != nil {
return result
}
}
}
return nil
}
// HasEdgeBetween allows GraphNode to satisfy the graph.Graph interface.
func (g *GraphNode) HasEdgeBetween(uid, vid int64) bool {
return g.EdgeBetween(uid, vid) != nil
}
// Edge allows GraphNode to satisfy the graph.Graph interface.
func (g *GraphNode) Edge(uid, vid int64) graph.Edge {
return g.EdgeBetween(uid, vid)
}
// EdgeBetween allows GraphNode to satisfy the graph.Graph interface.
func (g *GraphNode) EdgeBetween(uid, vid int64) graph.Edge {
if uid == g.id || vid == g.id {
for _, n := range g.neighbors {
if n.ID() == uid || n.ID() == vid {
return simple.Edge{F: g, T: n}
}
}
return nil
}
seen := map[int64]struct{}{g.id: {}}
for _, root := range g.roots {
seen[root.ID()] = struct{}{}
if result := root.edgeBetween(uid, vid, seen); result != nil {
return result
}
}
for _, n := range g.neighbors {
seen[n.ID()] = struct{}{}
if gn, ok := n.(*GraphNode); ok {
if result := gn.edgeBetween(uid, vid, seen); result != nil {
return result
}
}
}
return nil
}
func (g *GraphNode) edgeBetween(uid, vid int64, seen map[int64]struct{}) graph.Edge {
if uid == g.id || vid == g.id {
for _, n := range g.neighbors {
if n.ID() == uid || n.ID() == vid {
return simple.Edge{F: g, T: n}
}
}
return nil
}
for _, root := range g.roots {
if _, ok := seen[root.ID()]; ok {
continue
}
seen[root.ID()] = struct{}{}
if result := root.edgeBetween(uid, vid, seen); result != nil {
return result
}
}
for _, n := range g.neighbors {
if _, ok := seen[n.ID()]; ok {
continue
}
seen[n.ID()] = struct{}{}
if gn, ok := n.(*GraphNode); ok {
if result := gn.edgeBetween(uid, vid, seen); result != nil {
return result
}
}
}
return nil
}
// ID allows GraphNode to satisfy the graph.Node interface.
func (g *GraphNode) ID() int64 {
return g.id
}
// AddMeighbor adds an edge between g and n.
func (g *GraphNode) AddNeighbor(n *GraphNode) {
g.neighbors = append(g.neighbors, graph.Node(n))
}
// AddRoot adds provides an entrance into the graph g from n.
func (g *GraphNode) AddRoot(n *GraphNode) {
g.roots = append(g.roots, n)
}
func main() {
// This example shows the construction of the following graph
// using the implicit graph type above.
//
// The visual representation of the graph can be seen at
// https://graphviz.gitlab.io/_pages/Gallery/undirected/fdpclust.html
//
// graph G {
// e
// subgraph clusterA {
// a -- b
// subgraph clusterC {
// C -- D
// }
// }
// subgraph clusterB {
// d -- f
// }
// d -- D
// e -- clusterB
// clusterC -- clusterB
// }
// graph G {
G := NewGraphNode(0, "G")
// e
e := NewGraphNode(1, "e")
// subgraph clusterA {
clusterA := NewGraphNode(2, "clusterA")
// a -- b
a := NewGraphNode(3, "a")
b := NewGraphNode(4, "b")
a.AddNeighbor(b)
b.AddNeighbor(a)
clusterA.AddRoot(a)
clusterA.AddRoot(b)
// subgraph clusterC {
clusterC := NewGraphNode(5, "clusterC")
// C -- D
C := NewGraphNode(6, "C")
D := NewGraphNode(7, "D")
C.AddNeighbor(D)
D.AddNeighbor(C)
clusterC.AddRoot(C)
clusterC.AddRoot(D)
// }
clusterA.AddRoot(clusterC)
// }
// subgraph clusterB {
clusterB := NewGraphNode(8, "clusterB")
// d -- f
d := NewGraphNode(9, "d")
f := NewGraphNode(10, "f")
d.AddNeighbor(f)
f.AddNeighbor(d)
clusterB.AddRoot(d)
clusterB.AddRoot(f)
// }
// d -- D
d.AddNeighbor(D)
D.AddNeighbor(d)
// e -- clusterB
e.AddNeighbor(clusterB)
clusterB.AddNeighbor(e)
// clusterC -- clusterB
clusterC.AddNeighbor(clusterB)
clusterB.AddNeighbor(clusterC)
G.AddRoot(e)
G.AddRoot(clusterA)
G.AddRoot(clusterB)
// }
if topo.IsPathIn(G, []graph.Node{C, D, d, f}) {
fmt.Println("C--D--d--f is a path in G.")
}
fmt.Println("\nConnected components:")
for _, c := range topo.ConnectedComponents(G) {
fmt.Printf(" %s\n", c)
}
}
C--D--d--f is a path in G.
Connected components:
[G]
[e clusterB clusterC]
[d D C f]
[clusterA]
[a b]
Index ¶
- Constants
- func Copy(dst Builder, src Graph)
- func CopyWeighted(dst WeightedBuilder, src Weighted)
- type Builder
- type Complement
- func (g Complement) Edge(uid, vid int64) Edge
- func (g Complement) From(uid int64) Nodes
- func (g Complement) HasEdgeBetween(xid, yid int64) bool
- type Directed
- type DirectedBuilder
- type DirectedMultigraph
- type DirectedMultigraphBuilder
- type DirectedWeightedBuilder
- type DirectedWeightedMultigraphBuilder
- type Edge
- type EdgeAdder
- type EdgePair
- type EdgeRemover
- type EdgeSlicer
- type Edges
- type Graph
- type Iterator
- type Line
- type LineAdder
- type LineRemover
- type LineSlicer
- type Lines
- type Multigraph
- type MultigraphBuilder
- type Node
- type NodeAdder
- type NodeRemover
- type NodeSlicer
- type NodeWithIDer
- type Nodes
- type Undirect
- func (g Undirect) Edge(uid, vid int64) Edge
- func (g Undirect) EdgeBetween(xid, yid int64) Edge
- func (g Undirect) From(uid int64) Nodes
- func (g Undirect) HasEdgeBetween(xid, yid int64) bool
- func (g Undirect) Node(id int64) Node
- func (g Undirect) Nodes() Nodes
- type UndirectWeighted
- func (g UndirectWeighted) Edge(uid, vid int64) Edge
- func (g UndirectWeighted) EdgeBetween(xid, yid int64) Edge
- func (g UndirectWeighted) From(uid int64) Nodes
- func (g UndirectWeighted) HasEdgeBetween(xid, yid int64) bool
- func (g UndirectWeighted) Node(id int64) Node
- func (g UndirectWeighted) Nodes() Nodes
- func (g UndirectWeighted) Weight(xid, yid int64) (w float64, ok bool)
- func (g UndirectWeighted) WeightedEdge(uid, vid int64) WeightedEdge
- func (g UndirectWeighted) WeightedEdgeBetween(xid, yid int64) WeightedEdge
- type Undirected
- type UndirectedBuilder
- type UndirectedMultigraph
- type UndirectedMultigraphBuilder
- type UndirectedWeightedBuilder
- type UndirectedWeightedMultigraphBuilder
- type Weighted
- type WeightedBuilder
- type WeightedDirected
- type WeightedDirectedMultigraph
- type WeightedEdge
- type WeightedEdgeAdder
- type WeightedEdgePair
- type WeightedEdgeSlicer
- type WeightedEdges
- type WeightedLine
- type WeightedLineAdder
- type WeightedLineSlicer
- type WeightedLines
- type WeightedMultigraph
- type WeightedMultigraphBuilder
- type WeightedUndirected
- type WeightedUndirectedMultigraph
Examples ¶
Constants ¶
const Empty = nothing
Empty is an empty set of nodes, edges or lines. It should be used when a graph returns a zero-length Iterator. Empty implements the slicer interfaces for nodes, edges and lines, returning nil for each of these.
Functions ¶
func Copy ¶
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.
func CopyWeighted ¶
func CopyWeighted(dst WeightedBuilder, src Weighted)
CopyWeighted 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 UndirectWeighted may be used to do this.
Types ¶
type Builder ¶
Builder is a graph that can have nodes and edges added.
type Complement ¶
type Complement struct { Graph }
Complement provides the complement of a graph. The complement will not include self-edges, and edges within the complement will not hold any information other than the nodes in the original graph and the connection topology. Nodes returned by the Complement directly or via queries to returned Edges will be those stored in the original graph.
func (Complement) Edge ¶
func (g Complement) Edge(uid, vid int64) Edge
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.
func (Complement) From ¶
func (g Complement) From(uid int64) Nodes
From returns all nodes in g that can be reached directly from u in the complement.
func (Complement) HasEdgeBetween ¶
func (g Complement) HasEdgeBetween(xid, yid int64) bool
HasEdgeBetween returns whether an edge exists between nodes x and y.
type Directed ¶
type Directed interface { Graph // HasEdgeFromTo returns whether an edge exists // in the graph from u to v with IDs uid and vid. HasEdgeFromTo(uid, vid int64) bool // To returns all nodes that can reach directly // to the node with the given ID. // // To must not return nil. To(id int64) Nodes }
Directed is a directed graph.
type DirectedBuilder ¶
DirectedBuilder is a directed graph builder.
type DirectedMultigraph ¶
type DirectedMultigraph interface { Multigraph // HasEdgeFromTo returns whether an edge exists // in the multigraph from u to v with IDs uid // and vid. HasEdgeFromTo(uid, vid int64) bool // To returns all nodes that can reach directly // to the node with the given ID. // // To must not return nil. To(id int64) Nodes }
DirectedMultigraph is a directed multigraph.
type DirectedMultigraphBuilder ¶
type DirectedMultigraphBuilder interface { DirectedMultigraph MultigraphBuilder }
DirectedMultigraphBuilder is a directed multigraph builder.
type DirectedWeightedBuilder ¶
type DirectedWeightedBuilder interface { Directed WeightedBuilder }
DirectedWeightedBuilder is a directed weighted graph builder.
type DirectedWeightedMultigraphBuilder ¶
type DirectedWeightedMultigraphBuilder interface { DirectedMultigraph WeightedMultigraphBuilder }
DirectedWeightedMultigraphBuilder is a directed weighted multigraph builder.
type Edge ¶
type Edge interface { // From returns the from node of the edge. From() Node // To returns the to node of the edge. To() Node // ReversedEdge returns the edge reversal of the receiver // if a reversal is valid for the data type. // When a reversal is valid an edge of the same type as // the receiver with nodes of the receiver swapped should // be returned, otherwise the receiver should be returned // unaltered. ReversedEdge() Edge }
Edge is a graph edge. In directed graphs, the direction of the edge is given from -> to, otherwise the edge is semantically unordered.
func EdgesOf ¶
EdgesOf returns it.Len() nodes from it. If it is an EdgeSlicer, the EdgeSlice method is used to obtain the edges. It is safe to pass a nil Edges to EdgesOf.
type EdgeAdder ¶
type EdgeAdder interface { // NewEdge returns a new Edge from the source to the destination node. NewEdge(from, to Node) Edge // 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. // The behavior of an EdgeAdder when the IDs // returned by e.From() and e.To() are equal is // implementation-dependent. // Whether e, e.From() and e.To() are stored // within the graph is implementation dependent. SetEdge(e Edge) }
EdgeAdder is an interface for adding edges to a graph.
type EdgePair ¶
type EdgePair [2]Edge
EdgePair is an opposed pair of directed edges.
func (EdgePair) From ¶
From returns the from node of the first non-nil edge, or nil.
func (EdgePair) ReversedEdge ¶
ReversedEdge returns a new Edge with the end point of the edges in the pair swapped.
func (EdgePair) To ¶
To returns the to node of the first non-nil edge, or nil.
type EdgeRemover ¶
type EdgeRemover interface { // RemoveEdge removes the edge with the given end // IDs, leaving the terminal nodes. If the edge // does not exist it is a no-op. RemoveEdge(fid, tid int64) }
EdgeRemover is an interface for removing nodes from a graph.
type EdgeSlicer ¶
type EdgeSlicer interface { // EdgeSlice returns the set of edges remaining // to be iterated by an Edges iterator. // The holder of the iterator may arbitrarily // change elements in the returned slice, but // those changes may be reflected to other // iterators. EdgeSlice() []Edge }
EdgeSlicer wraps the EdgeSlice method.
type Edges ¶
Edges is an Edge iterator.
type Graph ¶
type Graph interface { // Node returns the node with the given ID if it exists // in the graph, and nil otherwise. Node(id int64) Node // Nodes returns all the nodes in the graph. // // Nodes must not return nil. Nodes() Nodes // From returns all nodes that can be reached directly // from the node with the given ID. // // From must not return nil. From(id int64) Nodes // HasEdgeBetween returns whether an edge exists between // nodes with IDs xid and yid without considering direction. HasEdgeBetween(xid, yid int64) bool // 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) Edge }
Graph is a generalized graph.
type Iterator ¶
type Iterator interface { // Next advances the iterator and returns whether // the next call to the item method will return a // non-nil item. // // Next should be called prior to any call to the // iterator's item retrieval method after the // iterator has been obtained or reset. // // The order of iteration is implementation // dependent. Next() bool // Len returns the number of items remaining in the // iterator. // // If the number of items in the iterator is unknown, // too large to materialize or too costly to calculate // then Len may return a negative value. // In this case the consuming function must be able // to operate on the items of the iterator directly // without materializing the items into a slice. // The magnitude of a negative length has // implementation-dependent semantics. Len() int // Reset returns the iterator to its start position. Reset() }
Iterator is an item iterator.
type Line ¶
type Line interface { // From returns the from node of the edge. From() Node // To returns the to node of the edge. To() Node // ReversedLine returns the edge reversal of the receiver // if a reversal is valid for the data type. // When a reversal is valid an edge of the same type as // the receiver with nodes of the receiver swapped should // be returned, otherwise the receiver should be returned // unaltered. ReversedLine() Line // ID returns the unique ID for the Line. ID() int64 }
Line is an edge in a multigraph. A Line returns an ID that must distinguish Lines sharing Node end points.
func LinesOf ¶
LinesOf returns it.Len() nodes from it. If it is a LineSlicer, the LineSlice method is used to obtain the lines. It is safe to pass a nil Lines to LinesOf.
type LineAdder ¶
type LineAdder interface { // NewLine returns a new Line from the source to the destination node. NewLine(from, to Node) Line // SetLine adds a Line from one node to another. // If the multigraph supports node addition the nodes // will be added if they do not exist, otherwise // SetLine will panic. // Whether l, l.From() and l.To() are stored // within the graph is implementation dependent. SetLine(l Line) }
LineAdder is an interface for adding lines to a multigraph.
type LineRemover ¶
type LineRemover interface { // RemoveLine removes the line with the given end // and line IDs, leaving the terminal nodes. If // the line does not exist it is a no-op. RemoveLine(fid, tid, id int64) }
LineRemover is an interface for removing lines from a multigraph.
type LineSlicer ¶
type LineSlicer interface { // LineSlice returns the set of lines remaining // to be iterated by an Lines iterator. // The holder of the iterator may arbitrarily // change elements in the returned slice, but // those changes may be reflected to other // iterators. LineSlice() []Line }
LineSlicer wraps the LineSlice method.
type Lines ¶
Lines is a Line iterator.
type Multigraph ¶
type Multigraph interface { // Node returns the node with the given ID if it exists // in the multigraph, and nil otherwise. Node(id int64) Node // Nodes returns all the nodes in the multigraph. // // Nodes must not return nil. Nodes() Nodes // From returns all nodes that can be reached directly // from the node with the given ID. // // From must not return nil. From(id int64) Nodes // HasEdgeBetween returns whether an edge exists between // nodes with IDs xid and yid without considering direction. HasEdgeBetween(xid, yid int64) bool // Lines returns the lines from u to v, with IDs uid and // vid, if any such lines exist and nil otherwise. The // node v must be directly reachable from u as defined by // the From method. // // Lines must not return nil. Lines(uid, vid int64) Lines }
Multigraph is a generalized multigraph.
type MultigraphBuilder ¶
MultigraphBuilder is a multigraph that can have nodes and lines added.
type Node ¶
type Node interface { ID() int64 }
Node is a graph node. It returns a graph-unique integer ID.
func NodesOf ¶
NodesOf returns it.Len() nodes from it. If it is a NodeSlicer, the NodeSlice method is used to obtain the nodes. It is safe to pass a nil Nodes to NodesOf.
type NodeAdder ¶
type NodeAdder interface { // NewNode returns a new Node with a unique // arbitrary ID. NewNode() Node // AddNode 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 ¶
type NodeRemover interface { // RemoveNode removes the node with the given ID // 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(id int64) }
NodeRemover is an interface for removing nodes from a graph.
type NodeSlicer ¶
type NodeSlicer interface { // NodeSlice returns the set of nodes remaining // to be iterated by a Nodes iterator. // The holder of the iterator may arbitrarily // change elements in the returned slice, but // those changes may be reflected to other // iterators. NodeSlice() []Node }
NodeSlicer wraps the NodeSlice method.
type NodeWithIDer ¶
type NodeWithIDer interface { // NodeWithID returns a Node with the given ID if possible. // A nil Node will be returned if no Node exists or // can be created. // If a non-nil Node is returned that is not already in the // graph NodeWithID will return true for new and the Node // must be added to the graph before use. NodeWithID(id int64) (n Node, new bool) }
NodeWithIDer is a graph that can return potentially new nodes with a defined ID.
type Nodes ¶
Nodes is a Node iterator.
type Undirect ¶
type Undirect struct { G Directed }
Undirect converts a directed graph to an undirected graph.
func (Undirect) Edge ¶
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. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of the edges between u and v.
func (Undirect) EdgeBetween ¶
EdgeBetween returns the edge between nodes x and y. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of edges between x and y.
func (Undirect) From ¶
From returns all nodes in g that can be reached directly from u.
func (Undirect) HasEdgeBetween ¶
HasEdgeBetween returns whether an edge exists between nodes x and y.
func (Undirect) Node ¶
Node returns the node with the given ID if it exists in the graph, and nil otherwise.
func (Undirect) Nodes ¶
Nodes returns all the nodes in the graph.
type UndirectWeighted ¶
type UndirectWeighted struct { G WeightedDirected // Absent is the value used to // represent absent edge weights // passed to Merge if the reverse // edge is present. Absent float64 // Merge defines how discordant edge // weights in G are resolved. A merge // is performed if at least one edge // exists between the nodes being // considered. The edges corresponding // to the two weights are also passed, // in the same order. // The order of weight parameters // passed to Merge is not defined, so // the function should be commutative. // If Merge is nil, the arithmetic // mean is used to merge weights. Merge func(x, y float64, xe, ye Edge) float64 }
UndirectWeighted converts a directed weighted graph to an undirected weighted graph, resolving edge weight conflicts.
func (UndirectWeighted) Edge ¶
func (g UndirectWeighted) Edge(uid, vid int64) Edge
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. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of the edges between u and v.
func (UndirectWeighted) EdgeBetween ¶
func (g UndirectWeighted) EdgeBetween(xid, yid int64) Edge
EdgeBetween returns the edge between nodes x and y. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of edges between x and y.
func (UndirectWeighted) From ¶
func (g UndirectWeighted) From(uid int64) Nodes
From returns all nodes in g that can be reached directly from u.
func (UndirectWeighted) HasEdgeBetween ¶
func (g UndirectWeighted) HasEdgeBetween(xid, yid int64) bool
HasEdgeBetween returns whether an edge exists between nodes x and y.
func (UndirectWeighted) Node ¶
func (g UndirectWeighted) Node(id int64) Node
Node returns the node with the given ID if it exists in the graph, and nil otherwise.
func (UndirectWeighted) Nodes ¶
func (g UndirectWeighted) Nodes() Nodes
Nodes returns all the nodes in the graph.
func (UndirectWeighted) Weight ¶
func (g UndirectWeighted) Weight(xid, yid int64) (w float64, ok bool)
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 the internal node weight is returned. If there is no joining edge between the two nodes the weight value returned is zero. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.
func (UndirectWeighted) WeightedEdge ¶
func (g UndirectWeighted) WeightedEdge(uid, vid int64) WeightedEdge
WeightedEdge returns the weighted 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. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of the edges between u and v.
func (UndirectWeighted) WeightedEdgeBetween ¶
func (g UndirectWeighted) WeightedEdgeBetween(xid, yid int64) WeightedEdge
WeightedEdgeBetween returns the weighted edge between nodes x and y. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of edges between x and y.
type Undirected ¶
type Undirected interface { Graph // EdgeBetween returns the edge between nodes x and y // with IDs xid and yid. EdgeBetween(xid, yid int64) Edge }
Undirected is an undirected graph.
type UndirectedBuilder ¶
type UndirectedBuilder interface { Undirected Builder }
UndirectedBuilder is an undirected graph builder.
type UndirectedMultigraph ¶
type UndirectedMultigraph interface { Multigraph // LinesBetween returns the lines between nodes x and y // with IDs xid and yid. // // LinesBetween must not return nil. LinesBetween(xid, yid int64) Lines }
UndirectedMultigraph is an undirected multigraph.
type UndirectedMultigraphBuilder ¶
type UndirectedMultigraphBuilder interface { UndirectedMultigraph MultigraphBuilder }
UndirectedMultigraphBuilder is an undirected multigraph builder.
type UndirectedWeightedBuilder ¶
type UndirectedWeightedBuilder interface { Undirected WeightedBuilder }
UndirectedWeightedBuilder is an undirected weighted graph builder.
type UndirectedWeightedMultigraphBuilder ¶
type UndirectedWeightedMultigraphBuilder interface { UndirectedMultigraph WeightedMultigraphBuilder }
UndirectedWeightedMultigraphBuilder is an undirected weighted multigraph builder.
type Weighted ¶
type Weighted interface { Graph // WeightedEdge returns the weighted 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. WeightedEdge(uid, vid int64) WeightedEdge // Weight returns the weight for the edge between // x and y with IDs xid and yid if Edge(xid, yid) // 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(xid, yid int64) (w float64, ok bool) }
Weighted is a weighted graph.
type WeightedBuilder ¶
type WeightedBuilder interface { NodeAdder WeightedEdgeAdder }
WeightedBuilder is a graph that can have nodes and weighted edges added.
type WeightedDirected ¶
type WeightedDirected interface { Weighted // HasEdgeFromTo returns whether an edge exists // in the graph from u to v with the IDs uid and // vid. HasEdgeFromTo(uid, vid int64) bool // To returns all nodes that can reach directly // to the node with the given ID. // // To must not return nil. To(id int64) Nodes }
WeightedDirected is a weighted directed graph.
type WeightedDirectedMultigraph ¶
type WeightedDirectedMultigraph interface { WeightedMultigraph // HasEdgeFromTo returns whether an edge exists // in the multigraph from u to v with IDs uid // and vid. HasEdgeFromTo(uid, vid int64) bool // To returns all nodes that can reach directly // to the node with the given ID. // // To must not return nil. To(id int64) Nodes }
WeightedDirectedMultigraph is a weighted directed multigraph.
type WeightedEdge ¶
WeightedEdge is a weighted graph edge. In directed graphs, the direction of the edge is given from -> to, otherwise the edge is semantically unordered.
func WeightedEdgesOf ¶
func WeightedEdgesOf(it WeightedEdges) []WeightedEdge
WeightedEdgesOf returns it.Len() weighted edge from it. If it is a WeightedEdgeSlicer, the WeightedEdgeSlice method is used to obtain the edges. It is safe to pass a nil WeightedEdges to WeightedEdgesOf.
type WeightedEdgeAdder ¶
type WeightedEdgeAdder interface { // NewWeightedEdge returns a new WeightedEdge from // the source to the destination node. NewWeightedEdge(from, to Node, weight float64) WeightedEdge // SetWeightedEdge 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 SetWeightedEdge will panic. // The behavior of a WeightedEdgeAdder when the IDs // returned by e.From() and e.To() are equal is // implementation-dependent. // Whether e, e.From() and e.To() are stored // within the graph is implementation dependent. SetWeightedEdge(e WeightedEdge) }
WeightedEdgeAdder is an interface for adding edges to a graph.
type WeightedEdgePair ¶
WeightedEdgePair is an opposed pair of directed edges.
func (WeightedEdgePair) ReversedEdge ¶
func (e WeightedEdgePair) ReversedEdge() Edge
ReversedEdge returns a new Edge with the end point of the edges in the pair swapped.
func (WeightedEdgePair) Weight ¶
func (e WeightedEdgePair) Weight() float64
Weight returns the merged edge weights of the two edges.
type WeightedEdgeSlicer ¶
type WeightedEdgeSlicer interface { // WeightedEdgeSlice returns the set of edges remaining // to be iterated by an Edges iterator. // The holder of the iterator may arbitrarily // change elements in the returned slice, but // those changes may be reflected to other // iterators. WeightedEdgeSlice() []WeightedEdge }
WeightedEdgeSlicer wraps the WeightedEdgeSlice method.
type WeightedEdges ¶
type WeightedEdges interface { Iterator // WeightedEdge returns the current Edge from the iterator. WeightedEdge() WeightedEdge }
WeightedEdges is a WeightedEdge iterator.
type WeightedLine ¶
WeightedLine is a weighted multigraph edge.
func WeightedLinesOf ¶
func WeightedLinesOf(it WeightedLines) []WeightedLine
WeightedLinesOf returns it.Len() weighted line from it. If it is a WeightedLineSlicer, the WeightedLineSlice method is used to obtain the lines. It is safe to pass a nil WeightedLines to WeightedLinesOf.
type WeightedLineAdder ¶
type WeightedLineAdder interface { // NewWeightedLine returns a new WeightedLine from // the source to the destination node. NewWeightedLine(from, to Node, weight float64) WeightedLine // SetWeightedLine adds a weighted line from one node // to another. If the multigraph supports node addition // the nodes will be added if they do not exist, // otherwise SetWeightedLine will panic. // Whether l, l.From() and l.To() are stored // within the graph is implementation dependent. SetWeightedLine(l WeightedLine) }
WeightedLineAdder is an interface for adding lines to a multigraph.
type WeightedLineSlicer ¶
type WeightedLineSlicer interface { // WeightedLineSlice returns the set of lines remaining // to be iterated by a WeightedLines iterator. // The holder of the iterator may arbitrarily // change elements in the returned slice, but // those changes may be reflected to other // iterators. WeightedLineSlice() []WeightedLine }
WeightedLineSlicer wraps the WeightedLineSlice method.
type WeightedLines ¶
type WeightedLines interface { Iterator // WeightedLine returns the current WeightedLine from the iterator. WeightedLine() WeightedLine }
WeightedLines is a WeightedLine iterator.
type WeightedMultigraph ¶
type WeightedMultigraph interface { Multigraph // WeightedLines returns the weighted lines from u to v // with IDs uid and vid if any such lines exist and nil // otherwise. The node v must be directly reachable // from u as defined by the From method. // // WeightedLines must not return nil. WeightedLines(uid, vid int64) WeightedLines }
WeightedMultigraph is a weighted multigraph.
type WeightedMultigraphBuilder ¶
type WeightedMultigraphBuilder interface { NodeAdder WeightedLineAdder }
WeightedMultigraphBuilder is a multigraph that can have nodes and weighted lines added.
type WeightedUndirected ¶
type WeightedUndirected interface { Weighted // WeightedEdgeBetween returns the edge between nodes // x and y with IDs xid and yid. WeightedEdgeBetween(xid, yid int64) WeightedEdge }
WeightedUndirected is a weighted undirected graph.
type WeightedUndirectedMultigraph ¶
type WeightedUndirectedMultigraph interface { WeightedMultigraph // WeightedLinesBetween returns the lines between nodes // x and y with IDs xid and yid. // // WeightedLinesBetween must not return nil. WeightedLinesBetween(xid, yid int64) WeightedLines }
WeightedUndirectedMultigraph is a weighted undirected multigraph.
Source Files ¶
complement.go doc.go graph.go multigraph.go nodes_edges.go undirect.go
Directories ¶
Path | Synopsis |
---|---|
graph/coloring | Package coloring provides graph coloring functions. |
graph/community | Package community provides graph community detection functions. |
graph/encoding | Package encoding provides a common graph encoding API. |
graph/encoding/digraph6 | Package digraph6 implements graphs specified by digraph6 strings. |
graph/encoding/dot | Package dot implements GraphViz DOT marshaling and unmarshaling of graphs. |
graph/encoding/graph6 | Package graph6 implements graphs specified by graph6 strings. |
graph/encoding/graphql | Package graphql implements JSON marshaling and unmarshaling of graph as used by GraphQL |
graph/flow | Package flow provides control flow analysis functions. |
graph/formats | |
graph/formats/cytoscapejs | Package cytoscapejs implements marshaling and unmarshaling of Cytoscape.js JSON documents. |
graph/formats/dot | Package dot implements a parser for Graphviz DOT files. |
graph/formats/dot/ast | Package ast declares the types used to represent abstract syntax trees of Graphviz DOT graphs. |
graph/formats/dot/internal | |
graph/formats/gexf12 | Package gexf12 implements marshaling and unmarshaling of GEXF1.2 documents. |
graph/formats/rdf | Package rdf implements decoding the RDF 1.1 N-Quads line-based plain text format for encoding an RDF dataset. |
graph/formats/sigmajs | Package sigmajs implements marshaling and unmarshaling of Sigma.js JSON documents. |
graph/graphs | |
graph/graphs/gen | Package gen provides random graph generation functions. |
graph/internal | |
graph/iterator | Package iterator provides node, edge and line iterators. |
graph/layout | Package layout defines functions for performing graph layout. |
graph/multi | Package multi provides a suite of multigraph implementations satisfying the gonum/graph interfaces. |
graph/network | Package network provides network analysis functions. |
graph/path | Package path provides graph path finding functions. |
graph/path/dynamic | Package dynamic provides incremental heuristic graph path finding functions. |
graph/path/internal | |
graph/product | Package product implements graph product functions. |
graph/set | |
graph/set/uid | Package uid implements unique ID provision for graphs. |
graph/simple | Package simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces. |
graph/spectral | Package spectral provides graph spectral analysis functions. |
graph/testgraph | Package testgraph provides a set of testing helper functions that test Gonum graph interface implementations. |
graph/topo | Package topo provides graph topology analysis functions. |
graph/traverse | Package traverse provides basic graph traversal primitives. |
- Version
- v0.15.1 (latest)
- Published
- Aug 16, 2024
- Platform
- linux/amd64
- Last checked
- 20 hours ago –
Tools for package owners.