multi

package
v0.9.2 Latest Latest
Warning

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

Go to latest
Published: May 11, 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

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

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

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL