multi

package
v0.8.1-0...-a25970e Latest Latest
Warning

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

 Go to latest Published: Mar 17, 2021 License: BSD-3-Clause Imports: 4 Imported by: 0

Documentation

Overview

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

All types in multi 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. The returned graph.Edge is a multi.Edge if an edge exists.

func (*DirectedGraph) Edges 

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

Edges returns all the edges in the graph. Each edge in the returned slice is a multi.Edge.

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

func (g *DirectedGraph) Lines(uid, vid int64) graph.Lines

Lines returns the lines from u to v if such any such lines exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

func (*DirectedGraph) NewLine 

func (g *DirectedGraph) NewLine(from, to graph.Node) graph.Line

NewLine returns a new Line from the source to the destination node. The returned Line will have a graph-unique ID. The Line's ID does not become valid in g until the Line is added to g.

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

func (g *DirectedGraph) RemoveLine(fid, tid, id int64)

RemoveLine removes the line with the given end point and line IDs from the graph, leaving the terminal nodes. If the line 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) SetLine 

func (g *DirectedGraph) SetLine(l graph.Line)

SetLine adds l, a line from one node to another. If the nodes do not exist, they are added and are set to the nodes of the line otherwise.

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

	graph.Lines
}

Edge is a collection of multigraph edges sharing end points.

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 Line 

type Line struct {
	F, T graph.Node

	UID int64
}

Line is a multigraph edge.

func (Line) From 

func (l Line) From() graph.Node

From returns the from-node of the line.

func (Line) ID 

func (l Line) ID() int64

ID returns the ID of the line.

func (Line) ReversedLine 

func (l Line) ReversedLine() graph.Line

ReversedLine returns a new Line with the F and T fields swapped. The UID of the new Line is the same as the UID of the receiver. The Lines within the Edge are not altered.

func (Line) To 

func (l Line) To() graph.Node

To returns the to-node of the line.

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. The returned graph.Edge is a multi.Edge if an edge exists.

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. Each edge in the returned slice is a multi.Edge.

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

func (g *UndirectedGraph) Lines(uid, vid int64) graph.Lines

Lines returns the lines 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) LinesBetween 

func (g *UndirectedGraph) LinesBetween(xid, yid int64) graph.Lines

LinesBetween returns the lines between nodes x and y.

func (*UndirectedGraph) NewLine 

func (g *UndirectedGraph) NewLine(from, to graph.Node) graph.Line

NewLine returns a new Line from the source to the destination node. The returned Line will have a graph-unique ID. The Line's ID does not become valid in g until the Line is added to g.

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

func (g *UndirectedGraph) RemoveLine(fid, tid, id int64)

RemoveLine removes the line with the given end point and line Ids from the graph, leaving the terminal nodes. If the line 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) SetLine 

func (g *UndirectedGraph) SetLine(l graph.Line)

SetLine adds l, a line from one node to another. If the nodes do not exist, they are added and are set to the nodes of the line otherwise.

type WeightedDirectedGraph 

type WeightedDirectedGraph struct {
	// EdgeWeightFunc is used to provide
	// the WeightFunc function for WeightedEdge
	// values returned by the graph.
	// WeightFunc must accept a nil input.
	EdgeWeightFunc func(graph.WeightedLines) float64
	// contains filtered or unexported fields
}

WeightedDirectedGraph implements a generalized directed graph.

func NewWeightedDirectedGraph 

func NewWeightedDirectedGraph() *WeightedDirectedGraph

NewWeightedDirectedGraph returns a WeightedDirectedGraph.

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. The returned graph.Edge is a multi.WeightedEdge if an edge exists.

func (*WeightedDirectedGraph) Edges 

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

Edges returns all the edges in the graph. Each edge in the returned slice is a multi.WeightedEdge.

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

func (g *WeightedDirectedGraph) Lines(uid, vid int64) graph.Lines

Lines returns the lines from u to v if such any such lines exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

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

func (g *WeightedDirectedGraph) NewWeightedLine(from, to graph.Node, weight float64) graph.WeightedLine

NewWeightedLine returns a new WeightedLine from the source to the destination node. The returned WeightedLine will have a graph-unique ID. The Line's ID does not become valid in g until the Line is added to g.

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

func (g *WeightedDirectedGraph) RemoveLine(fid, tid, id int64)

RemoveLine removes the line with the given end point and line IDs from the graph, leaving the terminal nodes. If the line 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) SetWeightedLine 

func (g *WeightedDirectedGraph) SetWeightedLine(l graph.WeightedLine)

SetWeightedLine adds l, a line from one node to another. If the nodes do not exist, they are added and are set to the nodes of the line otherwise.

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(uid, vid int64) (w float64, ok bool)

Weight returns the weight for the lines between x and y summarised by the receiver's EdgeWeightFunc. Weight returns true if an edge exists between x and y, 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. The returned graph.WeightedEdge is a multi.WeightedEdge if an edge exists.

func (*WeightedDirectedGraph) WeightedEdges 

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

WeightedEdges returns all the edges in the graph. Each edge in the returned slice is a multi.WeightedEdge.

func (*WeightedDirectedGraph) WeightedLines 

func (g *WeightedDirectedGraph) WeightedLines(uid, vid int64) graph.WeightedLines

WeightedLines returns the weighted lines from u to v if such any such lines exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

type WeightedEdge 

type WeightedEdge struct {
	F, T graph.Node

	graph.WeightedLines

	// WeightFunc calculates the aggregate
	// weight of the lines in Lines. If
	// WeightFunc is nil, the sum of weights
	// is used as the edge weight.
	// The graph.WeightedLines can be expected
	// to be positioned at the first line of
	// the iterator on entry and must be
	// Reset before exit.
	// WeightFunc must accept a nil input.
	WeightFunc func(graph.WeightedLines) float64
}

WeightedEdge is a collection of weighted multigraph edges sharing end points.

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 Lines within the WeightedEdge are not altered.

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. Weight uses WeightFunc field to calculate the weight, so the WeightedLines field is expected to be positioned at the first line and is reset before Weight returns.

type WeightedLine 

type WeightedLine struct {
	F, T graph.Node
	W    float64

	UID int64
}

WeightedLine is a weighted multigraph edge.

func (WeightedLine) From 

func (l WeightedLine) From() graph.Node

From returns the from-node of the line.

func (WeightedLine) ID 

func (l WeightedLine) ID() int64

ID returns the ID of the line.

func (WeightedLine) ReversedLine 

func (l WeightedLine) ReversedLine() graph.Line

ReversedLine returns a new Line with the F and T fields swapped. The UID and W of the new Line are the same as the UID and W of the receiver.

func (WeightedLine) To 

func (l WeightedLine) To() graph.Node

To returns the to-node of the line.

func (WeightedLine) Weight 

func (l WeightedLine) Weight() float64

Weight returns the weight of the edge.

type WeightedUndirectedGraph 

type WeightedUndirectedGraph struct {
	// EdgeWEightFunc is used to provide
	// the WeightFunc function for WeightedEdge
	// values returned by the graph.
	// WeightFunc must accept a nil input.
	EdgeWeightFunc func(graph.WeightedLines) float64
	// contains filtered or unexported fields
}

WeightedUndirectedGraph implements a generalized undirected graph.

func NewWeightedUndirectedGraph 

func NewWeightedUndirectedGraph() *WeightedUndirectedGraph

NewWeightedUndirectedGraph returns an WeightedUndirectedGraph.

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. The returned graph.Edge is a multi.WeightedEdge if an edge exists.

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. Each edge in the returned slice is a multi.Edge.

func (*WeightedUndirectedGraph) From 

func (g *WeightedUndirectedGraph) 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 (*WeightedUndirectedGraph) HasEdgeBetween 

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

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

func (*WeightedUndirectedGraph) Lines 

func (g *WeightedUndirectedGraph) Lines(uid, vid int64) graph.Lines

Lines returns the lines 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) LinesBetween 

func (g *WeightedUndirectedGraph) LinesBetween(xid, yid int64) graph.Lines

LinesBetween returns the lines 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) NewWeightedLine 

func (g *WeightedUndirectedGraph) NewWeightedLine(from, to graph.Node, weight float64) graph.WeightedLine

NewWeightedLine returns a new WeightedLine from the source to the destination node. The returned WeightedLine will have a graph-unique ID. The Line's ID does not become valid in g until the Line is added to g.

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

func (g *WeightedUndirectedGraph) RemoveLine(fid, tid, id int64)

RemoveLine removes the line with the given end point and line IDs from the graph, leaving the terminal nodes. If the line 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) SetWeightedLine 

func (g *WeightedUndirectedGraph) SetWeightedLine(l graph.WeightedLine)

SetWeightedLine adds l, a line from one node to another. If the nodes do not exist, they are added and are set to the nodes of the line otherwise.

func (*WeightedUndirectedGraph) Weight 

func (g *WeightedUndirectedGraph) Weight(xid, yid int64) (w float64, ok bool)

Weight returns the weight for the lines between x and y summarised by the receiver's EdgeWeightFunc. Weight returns true if an edge exists between x and y, 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. The returned graph.WeightedEdge is a multi.WeightedEdge if an edge exists.

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 edges in the graph. Each edge in the returned slice is a multi.Edge.

func (*WeightedUndirectedGraph) WeightedLines 

func (g *WeightedUndirectedGraph) WeightedLines(uid, vid int64) graph.WeightedLines

WeightedLines returns the lines 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) WeightedLinesBetween 

func (g *WeightedUndirectedGraph) WeightedLinesBetween(xid, yid int64) graph.WeightedLines

WeightedLinesBetween returns the lines between nodes x and y.

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.