gonum: gonum.org/v1/gonum/graph Index | Files | Directories

package graph

import "gonum.org/v1/gonum/graph"

Package graph defines graph interfaces.

Index

Package Files

doc.go graph.go multigraph.go undirect.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.

func CopyWeighted Uses

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.

type Builder Uses

type Builder interface {
    NodeAdder
    EdgeAdder
}

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 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(id int64) []Node
}

Directed is a directed graph.

type DirectedBuilder Uses

type DirectedBuilder interface {
    Directed
    Builder
}

DirectedBuilder is a directed graph builder.

type DirectedMultigraph Uses

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(id int64) []Node
}

DirectedMultigraph is a directed multigraph.

type DirectedMultigraphBuilder Uses

type DirectedMultigraphBuilder interface {
    DirectedMultigraph
    MultigraphBuilder
}

DirectedMultigraphBuilder is a directed multigraph builder.

type DirectedWeightedBuilder Uses

type DirectedWeightedBuilder interface {
    Directed
    WeightedBuilder
}

DirectedWeightedBuilder is a directed weighted graph builder.

type DirectedWeightedMultigraphBuilder Uses

type DirectedWeightedMultigraphBuilder interface {
    DirectedMultigraph
    WeightedMultigraphBuilder
}

DirectedWeightedMultigraphBuilder is a directed weighted multigraph builder.

type Edge Uses

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

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

type EdgeAdder Uses

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.
    SetEdge(e Edge)
}

EdgeAdder is an interface for adding edges to a graph.

type EdgePair Uses

type EdgePair [2]Edge

EdgePair is an opposed pair of directed edges.

func (EdgePair) From Uses

func (e EdgePair) From() Node

From returns the from node of the first non-nil edge, or nil.

func (EdgePair) To Uses

func (e EdgePair) To() Node

To returns the to node of the first non-nil edge, or nil.

type EdgeRemover Uses

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

type Graph interface {
    // Has returns whether a node with the given ID exists
    // within the graph.
    Has(id int64) bool

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

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

    // 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 Line Uses

type Line interface {
    Edge
    ID() int64
}

Line is an edge in a multigraph. A Line returns an ID that must distinguish Lines sharing Node end points.

type LineAdder Uses

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.
    SetLine(l Line)
}

LineAdder is an interface for adding lines to a multigraph.

type LineRemover Uses

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

type Multigraph interface {
    // Has returns whether the node with the given ID exists
    // within the multigraph.
    Has(id int64) bool

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

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

    // 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(uid, vid int64) []Line
}

Multigraph is a generalized multigraph.

type MultigraphBuilder Uses

type MultigraphBuilder interface {
    NodeAdder
    LineAdder
}

MultigraphBuilder is a multigraph that can have nodes and lines added.

type Node Uses

type Node interface {
    ID() int64
}

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

type NodeAdder Uses

type NodeAdder interface {
    // NewNode returns a new Node with a unique
    // arbitrary ID.
    NewNode() Node

    // 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 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 Undirect Uses

type Undirect struct {
    G Directed
}

Undirect converts a directed graph to an undirected graph.

func (Undirect) Edge Uses

func (g Undirect) 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 (Undirect) EdgeBetween Uses

func (g Undirect) 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 (Undirect) From Uses

func (g Undirect) From(uid int64) []Node

From returns all nodes in g that can be reached directly from u.

func (Undirect) Has Uses

func (g Undirect) Has(id int64) bool

Has returns whether the node exists within the graph.

func (Undirect) HasEdgeBetween Uses

func (g Undirect) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y.

func (Undirect) Nodes Uses

func (g Undirect) Nodes() []Node

Nodes returns all the nodes in the graph.

type UndirectWeighted Uses

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 Uses

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 Uses

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 Uses

func (g UndirectWeighted) From(uid int64) []Node

From returns all nodes in g that can be reached directly from u.

func (UndirectWeighted) Has Uses

func (g UndirectWeighted) Has(id int64) bool

Has returns whether the node exists within the graph.

func (UndirectWeighted) HasEdgeBetween Uses

func (g UndirectWeighted) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y.

func (UndirectWeighted) Nodes Uses

func (g UndirectWeighted) Nodes() []Node

Nodes returns all the nodes in the graph.

func (UndirectWeighted) Weight Uses

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 Uses

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 Uses

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 Uses

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 Uses

type UndirectedBuilder interface {
    Undirected
    Builder
}

UndirectedBuilder is an undirected graph builder.

type UndirectedMultigraph Uses

type UndirectedMultigraph interface {
    Multigraph

    // LinesBetween returns the lines between nodes x and y
    // with IDs xid and yid.
    LinesBetween(xid, yid int64) []Line
}

UndirectedMultigraph is an undirected multigraph.

type UndirectedMultigraphBuilder Uses

type UndirectedMultigraphBuilder interface {
    UndirectedMultigraph
    MultigraphBuilder
}

UndirectedMultgraphBuilder is an undirected multigraph builder.

type UndirectedWeightedBuilder Uses

type UndirectedWeightedBuilder interface {
    Undirected
    WeightedBuilder
}

UndirectedWeightedBuilder is an undirected weighted graph builder.

type UndirectedWeightedMultigraphBuilder Uses

type UndirectedWeightedMultigraphBuilder interface {
    UndirectedMultigraph
    WeightedMultigraphBuilder
}

UndirectedWeightedMultigraphBuilder is an undirected weighted multigraph builder.

type Weighted Uses

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 Uses

type WeightedBuilder interface {
    NodeAdder
    WeightedEdgeAdder
}

WeightedBuilder is a graph that can have nodes and weighted edges added.

type WeightedDirected Uses

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(id int64) []Node
}

WeightedDirected is a weighted directed graph.

type WeightedDirectedMultigraph Uses

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(id int64) []Node
}

WeightedDirectedMultigraph is a weighted directed multigraph.

type WeightedEdge Uses

type WeightedEdge interface {
    Edge
    Weight() float64
}

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

type WeightedEdgeAdder Uses

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.
    SetWeightedEdge(e WeightedEdge)
}

WeightedEdgeAdder is an interface for adding edges to a graph.

type WeightedEdgePair Uses

type WeightedEdgePair struct {
    EdgePair
    W   float64
}

WeightedEdgePair is an opposed pair of directed edges.

func (WeightedEdgePair) Weight Uses

func (e WeightedEdgePair) Weight() float64

Weight returns the merged edge weights of the two edges.

type WeightedLine Uses

type WeightedLine interface {
    Line
    Weight() float64
}

WeightedLine is a weighted multigraph edge.

type WeightedLineAdder Uses

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.
    SetWeightedLine(e WeightedLine)
}

WeightedLineAdder is an interface for adding lines to a multigraph.

type WeightedMultigraph Uses

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(uid, vid int64) []WeightedLine
}

WeightedMultigraph is a weighted multigraph.

type WeightedMultigraphBuilder Uses

type WeightedMultigraphBuilder interface {
    NodeAdder
    WeightedLineAdder
}

WeightedMultigraphBuilder is a multigraph that can have nodes and weighted lines added.

type WeightedUndirected Uses

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 Uses

type WeightedUndirectedMultigraph interface {
    WeightedMultigraph

    // WeightedLinesBetween returns the lines between nodes
    // x and y with IDs xid and yid.
    WeightedLinesBetween(xid, yid int64) []WeightedLine
}

WeightedUndirectedMultigraph is a weighted undirected multigraph.

Directories

PathSynopsis
communityPackage community provides graph community detection functions.
encodingPackage encoding provides a common graph encoding API.
encoding/dotPackage dot implements GraphViz DOT marshaling and unmarshaling of graphs.
encoding/graphqlPackage graphql implements JSON marshaling and unmarshaling of graph as used by GraphQL
formats/dotPackage dot implements a parser for Graphviz DOT files.
formats/dot/astPackage ast declares the types used to represent abstract syntax trees of Graphviz DOT graphs.
formats/dot/internal/astxPackage astx implements utility functions for generating abstract syntax trees of Graphviz DOT graphs.
formats/dot/internal/errorsPackage error provides generated internal error functions for DOT parsing.
formats/dot/internal/lexerPackage lexer provides generated internal lexer functions for DOT parsing.
formats/dot/internal/parserPackage parser provides generated internal parsing functions for DOT parsing.
formats/dot/internal/tokenPackage token provides generated internal tokenizing functions for DOT parsing.
formats/dot/internal/utilPackage util provides generated internal utility functions for DOT parsing.
graphs/genPackage gen provides random graph generation functions.
internal/linearPackage linear provides common linear data structures.
internal/orderedPackage ordered provides common sort ordering types.
internal/setPackage set provides integer and graph.Node sets.
internal/uidPackage uid implements unique ID provision for graphs.
multiPackage multi provides a suite of multigraph implementations satisfying the gonum/graph interfaces.
networkPackage network provides network analysis functions.
pathPackage path provides graph path finding functions.
path/dynamicPackage dynamic provides incremental heuristic graph path finding functions.
path/internal/testgraphsPackage testsgraphs provides a number of graphs used for testing routines in the path and path/dynamic packages.
simplePackage simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces.
topoPackage topo provides graph topology analysis functions.
traversePackage traverse provides basic graph traversal primitives.

Package graph is imported by 55 packages. Updated 2018-09-06. Refresh now. Tools for package owners.