Back to godoc.org

Package graph

v0.7.0
Latest Go to latest

The latest major version is .

Published: Feb 26, 2020 | License: BSD-3-Clause | Module: gonum.org/v1/gonum

Overview

Package graph defines graph interfaces.

Routines to test contract compliance by user implemented graph types are available in gonum.org/v1/gonum/graph/testgraph.

Example (Implicit)

Code:

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
}

// NewGraphNode returns a new GraphNode.
func NewGraphNode(id int64) *GraphNode {
	return &GraphNode{id: id}
}

// 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 {
			return root
		}

		if 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 {
			return true
		}

		if 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 {
		nodes = append(nodes, root)
		seen[root.ID()] = struct{}{}

		nodes = root.nodes(nodes, seen)
	}

	for _, n := range g.neighbors {
		nodes = append(nodes, n)
		seen[n.ID()] = struct{}{}

		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 = append(dst, graph.Node(root))

		dst = root.nodes(dst, seen)
	}

	for _, n := range g.neighbors {
		if _, ok := seen[n.ID()]; ok {
			continue
		}

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

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)
	// 	e
	e := NewGraphNode(1)

	// 	subgraph clusterA {
	clusterA := NewGraphNode(2)
	// 		a -- b
	a := NewGraphNode(3)
	b := NewGraphNode(4)
	a.AddNeighbor(b)
	b.AddNeighbor(a)
	clusterA.AddRoot(a)
	clusterA.AddRoot(b)

	// 		subgraph clusterC {
	clusterC := NewGraphNode(5)
	// 			C -- D
	C := NewGraphNode(6)
	D := NewGraphNode(7)
	C.AddNeighbor(D)
	D.AddNeighbor(C)

	clusterC.AddRoot(C)
	clusterC.AddRoot(D)
	// 		}
	clusterA.AddRoot(clusterC)
	// 	}

	// 	subgraph clusterB {
	clusterB := NewGraphNode(8)
	// 		d -- f
	d := NewGraphNode(9)
	f := NewGraphNode(10)
	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.")
	}

}

C--D--d--f is a path in G.

Index

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.

func Copy

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

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

type Builder interface {
	NodeAdder
	EdgeAdder
}

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

type DirectedBuilder interface {
	Directed
	Builder
}

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 an edge that has
	// the end points of the receiver swapped.
	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

func EdgesOf(it Edges) []Edge

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.

If the Edges has an indeterminate length, EdgesOf will panic.

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

func (e EdgePair) From() Node

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

func (EdgePair) ReversedEdge

func (e EdgePair) ReversedEdge() Edge

ReversedEdge returns a new Edge with the end point of the edges in the pair swapped.

func (EdgePair) To

func (e EdgePair) To() Node

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

type Edges interface {
	Iterator

	// Edge returns the current Edge from the iterator.
	Edge() Edge
}

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 a line that has the
	// end points of the receiver swapped.
	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

func LinesOf(it Lines) []Line

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.

If the Lines has an indeterminate length, LinesOf will panic.

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

type Lines interface {
	Iterator

	// Line returns the current Line from the iterator.
	Line() Line
}

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

type MultigraphBuilder interface {
	NodeAdder
	LineAdder
}

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

func NodesOf(it Nodes) []Node

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.

If the Nodes has an indeterminate length, NodesOf will panic.

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 Nodes

type Nodes interface {
	Iterator

	// Node returns the current Node from the iterator.
	Node() Node
}

Nodes is a Node iterator.

type Undirect

type Undirect struct {
	G Directed
}

Undirect converts a directed graph to an undirected graph.

func (Undirect) Edge

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

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

func (g Undirect) From(uid int64) Nodes

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

func (Undirect) HasEdgeBetween

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

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

func (Undirect) Node

func (g Undirect) Node(id int64) Node

Node returns the node with the given ID if it exists in the graph, and nil otherwise.

func (Undirect) Nodes

func (g Undirect) Nodes() 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
}

UndirectedMultgraphBuilder 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

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.

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.

If the WeightedEdges has an indeterminate length, WeightedEdgesOf will panic.

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

type WeightedEdgePair struct {
	EdgePair
	W float64
}

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 {
	// 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.
	WeightedEdgeSlice() []WeightedEdge
}

WeightedEdgeSlicer wraps the WeightedEdgeSlice method.

type WeightedEdges

type WeightedEdges interface {
	Iterator

	// Edge returns the current Edge from the iterator.
	WeightedEdge() WeightedEdge
}

WeightedEdges is a WeightedEdge iterator.

type WeightedLine

type WeightedLine interface {
	Line
	Weight() float64
}

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.

If the WeightedLines has an indeterminate length, WeightedLinesOf will panic.

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 {
	// 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.
	WeightedLineSlice() []WeightedLine
}

WeightedLineSlicer wraps the WeightedLineSlice method.

type WeightedLines

type WeightedLines interface {
	Iterator

	// Line returns the current Line 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.

Package Files

Documentation was rendered with GOOS=linux and GOARCH=amd64.

Jump to identifier

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to identifier