simple

package module
v0.0.0-...-b970da5 Latest Latest
Warning

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

 Go to latest Published: Apr 10, 2024 License: BSD-3-Clause Imports: 5 Imported by: 0

README

Gonum Simple Graph

GoDoc Widget Go Report Card Widget

This is the gonum graph/simple package extracted to a separate module.

The goal is to reduce the weight of this dependency significantly if you only need the basic graph functions.

Importing the graph/mat package significantly increases the binary size of this package, so those imports have been excluded here.

Upstream

Check out the upstream project as well.

License

BSD-3

Documentation

Overview

Package simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces.

All types in simple return the graph.Empty value for empty iterators.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DirectedGraph 

type DirectedGraph struct {
	// contains filtered or unexported fields
}

DirectedGraph implements a generalized directed graph.

func NewDirectedGraph 

func NewDirectedGraph() *DirectedGraph

NewDirectedGraph returns a DirectedGraph.

func (*DirectedGraph) AddNode 

func (g *DirectedGraph) AddNode(n graph.Node)

AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.

func (*DirectedGraph) Edge 

func (g *DirectedGraph) Edge(uid, vid int64) graph.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 (*DirectedGraph) Edges 

func (g *DirectedGraph) Edges() graph.Edges

Edges returns all the edges in the graph.

func (*DirectedGraph) From 

func (g *DirectedGraph) From(id int64) graph.Nodes

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

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*DirectedGraph) HasEdgeBetween 

func (g *DirectedGraph) HasEdgeBetween(xid, yid int64) bool

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

func (*DirectedGraph) HasEdgeFromTo 

func (g *DirectedGraph) HasEdgeFromTo(uid, vid int64) bool

HasEdgeFromTo returns whether an edge exists in the graph from u to v.

func (*DirectedGraph) NewEdge 

func (g *DirectedGraph) NewEdge(from, to graph.Node) graph.Edge

NewEdge returns a new Edge from the source to the destination node.

func (*DirectedGraph) NewNode 

func (g *DirectedGraph) NewNode() graph.Node

NewNode returns a new unique Node to be added to g. The Node's ID does not become valid in g until the Node is added to g.

func (*DirectedGraph) Node 

func (g *DirectedGraph) Node(id int64) graph.Node

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

func (*DirectedGraph) NodeWithID 

func (g *DirectedGraph) NodeWithID(id int64) (n graph.Node, new bool)

NodeWithID returns a Node with the given ID if possible. If a graph.Node is returned that is not already in the graph NodeWithID will return true for new and the graph.Node must be added to the graph before use.

func (*DirectedGraph) Nodes 

func (g *DirectedGraph) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*DirectedGraph) RemoveEdge 

func (g *DirectedGraph) RemoveEdge(fid, tid int64)

RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal nodes. If the edge does not exist it is a no-op.

func (*DirectedGraph) RemoveNode 

func (g *DirectedGraph) RemoveNode(id int64)

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.

func (*DirectedGraph) SetEdge 

func (g *DirectedGraph) SetEdge(e graph.Edge)

SetEdge adds e, an edge from one node to another. If the nodes do not exist, they are added and are set to the nodes of the edge otherwise. It will panic if the IDs of the e.From and e.To are equal.

func (*DirectedGraph) To 

func (g *DirectedGraph) To(id int64) graph.Nodes

To returns all nodes in g that can reach directly to n.

The returned graph.Nodes is only valid until the next mutation of the receiver.

type Edge 

type Edge struct {
	F, T graph.Node
}

Edge is a simple graph edge.

func (Edge) From 

func (e Edge) From() graph.Node

From returns the from-node of the edge.

func (Edge) ReversedEdge 

func (e Edge) ReversedEdge() graph.Edge

ReversedEdge returns a new Edge with the F and T fields swapped.

func (Edge) To 

func (e Edge) To() graph.Node

To returns the to-node of the edge.

type Node 

type Node int64

Node is a simple graph node.

func (Node) ID 

func (n Node) ID() int64

ID returns the ID number of the node.

type UndirectedGraph 

type UndirectedGraph struct {
	// contains filtered or unexported fields
}

UndirectedGraph implements a generalized undirected graph.

func NewUndirectedGraph 

func NewUndirectedGraph() *UndirectedGraph

NewUndirectedGraph returns an UndirectedGraph.

func (*UndirectedGraph) AddNode 

func (g *UndirectedGraph) AddNode(n graph.Node)

AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.

func (*UndirectedGraph) Edge 

func (g *UndirectedGraph) Edge(uid, vid int64) graph.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 (*UndirectedGraph) EdgeBetween 

func (g *UndirectedGraph) EdgeBetween(xid, yid int64) graph.Edge

EdgeBetween returns the edge between nodes x and y.

func (*UndirectedGraph) Edges 

func (g *UndirectedGraph) Edges() graph.Edges

Edges returns all the edges in the graph.

func (*UndirectedGraph) From 

func (g *UndirectedGraph) From(id int64) graph.Nodes

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

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*UndirectedGraph) HasEdgeBetween 

func (g *UndirectedGraph) HasEdgeBetween(xid, yid int64) bool

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

func (*UndirectedGraph) NewEdge 

func (g *UndirectedGraph) NewEdge(from, to graph.Node) graph.Edge

NewEdge returns a new Edge from the source to the destination node.

func (*UndirectedGraph) NewNode 

func (g *UndirectedGraph) NewNode() graph.Node

NewNode returns a new unique Node to be added to g. The Node's ID does not become valid in g until the Node is added to g.

func (*UndirectedGraph) Node 

func (g *UndirectedGraph) Node(id int64) graph.Node

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

func (*UndirectedGraph) NodeWithID 

func (g *UndirectedGraph) NodeWithID(id int64) (n graph.Node, new bool)

NodeWithID returns a Node with the given ID if possible. If a graph.Node is returned that is not already in the graph NodeWithID will return true for new and the graph.Node must be added to the graph before use.

func (*UndirectedGraph) Nodes 

func (g *UndirectedGraph) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*UndirectedGraph) RemoveEdge 

func (g *UndirectedGraph) RemoveEdge(fid, tid int64)

RemoveEdge removes the edge with the given end IDs from the graph, leaving the terminal nodes. If the edge does not exist it is a no-op.

func (*UndirectedGraph) RemoveNode 

func (g *UndirectedGraph) RemoveNode(id int64)

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.

func (*UndirectedGraph) SetEdge 

func (g *UndirectedGraph) SetEdge(e graph.Edge)

SetEdge adds e, an edge from one node to another. If the nodes do not exist, they are added and are set to the nodes of the edge otherwise. It will panic if the IDs of the e.From and e.To are equal.

type WeightedDirectedGraph 

type WeightedDirectedGraph struct {
	// contains filtered or unexported fields
}

WeightedDirectedGraph implements a generalized weighted directed graph.

func NewWeightedDirectedGraph 

func NewWeightedDirectedGraph(self, absent float64) *WeightedDirectedGraph

NewWeightedDirectedGraph returns a WeightedDirectedGraph with the specified self and absent edge weight values.

func (*WeightedDirectedGraph) AddNode 

func (g *WeightedDirectedGraph) AddNode(n graph.Node)

AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.

func (*WeightedDirectedGraph) Edge 

func (g *WeightedDirectedGraph) Edge(uid, vid int64) graph.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 (*WeightedDirectedGraph) Edges 

func (g *WeightedDirectedGraph) Edges() graph.Edges

Edges returns all the edges in the graph.

func (*WeightedDirectedGraph) From 

func (g *WeightedDirectedGraph) From(id int64) graph.Nodes

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

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*WeightedDirectedGraph) HasEdgeBetween 

func (g *WeightedDirectedGraph) HasEdgeBetween(xid, yid int64) bool

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

func (*WeightedDirectedGraph) HasEdgeFromTo 

func (g *WeightedDirectedGraph) HasEdgeFromTo(uid, vid int64) bool

HasEdgeFromTo returns whether an edge exists in the graph from u to v.

func (*WeightedDirectedGraph) NewNode 

func (g *WeightedDirectedGraph) NewNode() graph.Node

NewNode returns a new unique Node to be added to g. The Node's ID does not become valid in g until the Node is added to g.

func (*WeightedDirectedGraph) NewWeightedEdge 

func (g *WeightedDirectedGraph) NewWeightedEdge(from, to graph.Node, weight float64) graph.WeightedEdge

NewWeightedEdge returns a new weighted edge from the source to the destination node.

func (*WeightedDirectedGraph) Node 

func (g *WeightedDirectedGraph) Node(id int64) graph.Node

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

func (*WeightedDirectedGraph) NodeWithID 

func (g *WeightedDirectedGraph) NodeWithID(id int64) (n graph.Node, new bool)

NodeWithID returns a Node with the given ID if possible. If a graph.Node is returned that is not already in the graph NodeWithID will return true for new and the graph.Node must be added to the graph before use.

func (*WeightedDirectedGraph) Nodes 

func (g *WeightedDirectedGraph) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*WeightedDirectedGraph) RemoveEdge 

func (g *WeightedDirectedGraph) RemoveEdge(fid, tid int64)

RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal nodes. If the edge does not exist it is a no-op.

func (*WeightedDirectedGraph) RemoveNode 

func (g *WeightedDirectedGraph) RemoveNode(id int64)

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.

func (*WeightedDirectedGraph) SetWeightedEdge 

func (g *WeightedDirectedGraph) SetWeightedEdge(e graph.WeightedEdge)

SetWeightedEdge adds a weighted edge from one node to another. If the nodes do not exist, they are added and are set to the nodes of the edge otherwise. It will panic if the IDs of the e.From and e.To are equal.

func (*WeightedDirectedGraph) To 

func (g *WeightedDirectedGraph) To(id int64) graph.Nodes

To returns all nodes in g that can reach directly to n.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*WeightedDirectedGraph) Weight 

func (g *WeightedDirectedGraph) 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 or there is no joining edge between the two nodes the weight value returned is either the graph's absent or self value. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.

func (*WeightedDirectedGraph) WeightedEdge 

func (g *WeightedDirectedGraph) WeightedEdge(uid, vid int64) graph.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.

func (*WeightedDirectedGraph) WeightedEdges 

func (g *WeightedDirectedGraph) WeightedEdges() graph.WeightedEdges

WeightedEdges returns all the weighted edges in the graph.

type WeightedEdge 

type WeightedEdge struct {
	F, T graph.Node
	W    float64
}

WeightedEdge is a simple weighted graph edge.

func (WeightedEdge) From 

func (e WeightedEdge) From() graph.Node

From returns the from-node of the edge.

func (WeightedEdge) ReversedEdge 

func (e WeightedEdge) ReversedEdge() graph.Edge

ReversedEdge returns a new Edge with the F and T fields swapped. The weight of the new Edge is the same as the weight of the receiver.

func (WeightedEdge) To 

func (e WeightedEdge) To() graph.Node

To returns the to-node of the edge.

func (WeightedEdge) Weight 

func (e WeightedEdge) Weight() float64

Weight returns the weight of the edge.

type WeightedUndirectedGraph 

type WeightedUndirectedGraph struct {
	// contains filtered or unexported fields
}

WeightedUndirectedGraph implements a generalized weighted undirected graph.

func NewWeightedUndirectedGraph 

func NewWeightedUndirectedGraph(self, absent float64) *WeightedUndirectedGraph

NewWeightedUndirectedGraph returns an WeightedUndirectedGraph with the specified self and absent edge weight values.

func (*WeightedUndirectedGraph) AddNode 

func (g *WeightedUndirectedGraph) AddNode(n graph.Node)

AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.

func (*WeightedUndirectedGraph) Edge 

func (g *WeightedUndirectedGraph) Edge(uid, vid int64) graph.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 (*WeightedUndirectedGraph) EdgeBetween 

func (g *WeightedUndirectedGraph) EdgeBetween(xid, yid int64) graph.Edge

EdgeBetween returns the edge between nodes x and y.

func (*WeightedUndirectedGraph) Edges 

func (g *WeightedUndirectedGraph) Edges() graph.Edges

Edges returns all the edges in the graph.

func (*WeightedUndirectedGraph) From 

func (g *WeightedUndirectedGraph) From(id int64) graph.Nodes

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

func (*WeightedUndirectedGraph) HasEdgeBetween 

func (g *WeightedUndirectedGraph) HasEdgeBetween(xid, yid int64) bool

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

func (*WeightedUndirectedGraph) NewNode 

func (g *WeightedUndirectedGraph) NewNode() graph.Node

NewNode returns a new unique Node to be added to g. The Node's ID does not become valid in g until the Node is added to g.

func (*WeightedUndirectedGraph) NewWeightedEdge 

func (g *WeightedUndirectedGraph) NewWeightedEdge(from, to graph.Node, weight float64) graph.WeightedEdge

NewWeightedEdge returns a new weighted edge from the source to the destination node.

func (*WeightedUndirectedGraph) Node 

func (g *WeightedUndirectedGraph) Node(id int64) graph.Node

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

func (*WeightedUndirectedGraph) NodeWithID 

func (g *WeightedUndirectedGraph) NodeWithID(id int64) (n graph.Node, new bool)

NodeWithID returns a Node with the given ID if possible. If a graph.Node is returned that is not already in the graph NodeWithID will return true for new and the graph.Node must be added to the graph before use.

func (*WeightedUndirectedGraph) Nodes 

func (g *WeightedUndirectedGraph) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

The returned graph.Nodes is only valid until the next mutation of the receiver.

func (*WeightedUndirectedGraph) RemoveEdge 

func (g *WeightedUndirectedGraph) RemoveEdge(fid, tid int64)

RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal nodes. If the edge does not exist it is a no-op.

func (*WeightedUndirectedGraph) RemoveNode 

func (g *WeightedUndirectedGraph) RemoveNode(id int64)

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.

func (*WeightedUndirectedGraph) SetWeightedEdge 

func (g *WeightedUndirectedGraph) SetWeightedEdge(e graph.WeightedEdge)

SetWeightedEdge adds a weighted edge from one node to another. If the nodes do not exist, they are added and are set to the nodes of the edge otherwise. It will panic if the IDs of the e.From and e.To are equal.

func (*WeightedUndirectedGraph) Weight 

func (g *WeightedUndirectedGraph) 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 or there is no joining edge between the two nodes the weight value returned is either the graph's absent or self value. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.

func (*WeightedUndirectedGraph) WeightedEdge 

func (g *WeightedUndirectedGraph) WeightedEdge(uid, vid int64) graph.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.

func (*WeightedUndirectedGraph) WeightedEdgeBetween 

func (g *WeightedUndirectedGraph) WeightedEdgeBetween(xid, yid int64) graph.WeightedEdge

WeightedEdgeBetween returns the weighted edge between nodes x and y.

func (*WeightedUndirectedGraph) WeightedEdges 

func (g *WeightedUndirectedGraph) WeightedEdges() graph.WeightedEdges

WeightedEdges returns all the weighted edges in the graph.

Source Files

View all Source files

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.