graph

package
v0.0.4 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 26, 2024 License: BSD-3-Clause Imports: 0 Imported by: 0

README

Gonum graph

go.dev reference GoDoc

This is a generalized graph package for the Go language.

Documentation

Overview

Package graph defines graph interfaces.

Routines to test contract compliance by user implemented graph types are available in github.com/jak9708/gonummat/graph/testgraph.

Example (Implicit) 
package main

import (
	"fmt"

	"github.com/jak9708/gonummat/graph"
	"github.com/jak9708/gonummat/graph/iterator"
	"github.com/jak9708/gonummat/graph/simple"
	"github.com/jak9708/gonummat/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)
	}

}

Output:


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

Connected components:
 [G]
 [e clusterB clusterC]
 [d D C f]
 [clusterA]
 [a b]

Index

Examples

Constants

View Source 
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.

Variables

This section is empty.

Functions

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.

Types

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

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.

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

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.

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.

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 

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
}

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 

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.

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

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.

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

View all Source files

Directories

Path Synopsis
Package coloring provides graph coloring functions.
 Package coloring provides graph coloring functions.
Package community provides graph community detection functions.
 Package community provides graph community detection functions.
Package encoding provides a common graph encoding API.
 Package encoding provides a common graph encoding API.
digraph6
Package digraph6 implements graphs specified by digraph6 strings.
 Package digraph6 implements graphs specified by digraph6 strings.
dot
Package dot implements GraphViz DOT marshaling and unmarshaling of graphs.
 Package dot implements GraphViz DOT marshaling and unmarshaling of graphs.
graph6
Package graph6 implements graphs specified by graph6 strings.
 Package graph6 implements graphs specified by graph6 strings.
graphql
Package graphql implements JSON marshaling and unmarshaling of graph as used by GraphQL
 Package graphql implements JSON marshaling and unmarshaling of graph as used by GraphQL
Package flow provides control flow analysis functions.
 Package flow provides control flow analysis functions.
formats
cytoscapejs
Package cytoscapejs implements marshaling and unmarshaling of Cytoscape.js JSON documents.
 Package cytoscapejs implements marshaling and unmarshaling of Cytoscape.js JSON documents.
dot
Package dot implements a parser for Graphviz DOT files.
 Package dot implements a parser for Graphviz DOT files.
dot/ast
Package ast declares the types used to represent abstract syntax trees of Graphviz DOT graphs.
 Package ast declares the types used to represent abstract syntax trees of Graphviz DOT graphs.
dot/internal/astx
Package astx implements utility functions for generating abstract syntax trees of Graphviz DOT graphs.
 Package astx implements utility functions for generating abstract syntax trees of Graphviz DOT graphs.
dot/internal/errors
Package errors provides generated internal error functions for DOT parsing.
 Package errors provides generated internal error functions for DOT parsing.
dot/internal/lexer
Package lexer provides generated internal lexer functions for DOT parsing.
 Package lexer provides generated internal lexer functions for DOT parsing.
dot/internal/parser
Package parser provides generated internal parsing functions for DOT parsing.
 Package parser provides generated internal parsing functions for DOT parsing.
dot/internal/token
Package token provides generated internal tokenizing functions for DOT parsing.
 Package token provides generated internal tokenizing functions for DOT parsing.
dot/internal/util
Package util provides generated internal utility functions for DOT parsing.
 Package util provides generated internal utility functions for DOT parsing.
gexf12
Package gexf12 implements marshaling and unmarshaling of GEXF1.2 documents.
 Package gexf12 implements marshaling and unmarshaling of GEXF1.2 documents.
rdf
Package rdf implements decoding the RDF 1.1 N-Quads line-based plain text format for encoding an RDF dataset.
 Package rdf implements decoding the RDF 1.1 N-Quads line-based plain text format for encoding an RDF dataset.
sigmajs
Package sigmajs implements marshaling and unmarshaling of Sigma.js JSON documents.
 Package sigmajs implements marshaling and unmarshaling of Sigma.js JSON documents.
graphs
gen
Package gen provides random graph generation functions.
 Package gen provides random graph generation functions.
internal
linear
Package linear provides common linear data structures.
 Package linear provides common linear data structures.
set
Package set provides integer and graph.Node sets.
 Package set provides integer and graph.Node sets.
Package iterator provides node, edge and line iterators.
 Package iterator provides node, edge and line iterators.
Package layout defines functions for performing graph layout.
 Package layout defines functions for performing graph layout.
Package multi provides a suite of multigraph implementations satisfying the gonum/graph interfaces.
 Package multi provides a suite of multigraph implementations satisfying the gonum/graph interfaces.
Package network provides network analysis functions.
 Package network provides network analysis functions.
Package path provides graph path finding functions.
 Package path provides graph path finding functions.
dynamic
Package dynamic provides incremental heuristic graph path finding functions.
 Package dynamic provides incremental heuristic graph path finding functions.
internal/testgraphs
Package testgraphs provides a number of graphs used for testing routines in the path and path/dynamic packages.
 Package testgraphs provides a number of graphs used for testing routines in the path and path/dynamic packages.
Package product implements graph product functions.
 Package product implements graph product functions.
set
uid
Package uid implements unique ID provision for graphs.
 Package uid implements unique ID provision for graphs.
Package simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces.
 Package simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces.
Package spectral provides graph spectral analysis functions.
 Package spectral provides graph spectral analysis functions.
Package testgraph provides a set of testing helper functions that test Gonum graph interface implementations.
 Package testgraph provides a set of testing helper functions that test Gonum graph interface implementations.
Package topo provides graph topology analysis functions.
 Package topo provides graph topology analysis functions.
Package traverse provides basic graph traversal primitives.
 Package traverse provides basic graph traversal primitives.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.