network

Documentation

Overview

burrow is a collection of network structures for exploring specific network theory concepts that interest me. In particular, there is a focus on delivery networks, which are DAGs with heterogeneous node types representing the locations visited by delivery vehicles.

This package builds on and makes extensive use of the gonum graph library. For more details on the underlying interfaces, see:

https://pkg.go.dev/gonum.org/v1/gonum/graph

All node, edge and graph structures in burrow implement the corresponding interfaces in gonum/graph. More specifically:

• HubNode, StopNode -> gonum/graph.Node
• DeliveryNodes -> gonum/graph.Nodes
• DeliveryEdge -> gonum/graph.{Edge, WeightedEdge}
• DeliveryEdges -> gonum/graph.{Edges, WeightedEdges}
• DeliveryNetwork -> gonum/graph.{Graph, Directed, Weighted}

Index

• type DeliveryEdge
  • func (e *DeliveryEdge) From() graph.Node
  • func (e *DeliveryEdge) ReversedEdge() graph.Edge
  • func (e *DeliveryEdge) To() graph.Node
  • func (e *DeliveryEdge) Weight() float64
• type DeliveryEdges
  • func NewDeliveryEdges() *DeliveryEdges
  • func (e DeliveryEdges) Current() graph.WeightedEdge
  • func (e DeliveryEdges) Edge() graph.Edge
  • func (e DeliveryEdges) Len() int
  • func (e *DeliveryEdges) Next() bool
  • func (e *DeliveryEdges) Reset()
  • func (e DeliveryEdges) WeightedEdge() graph.WeightedEdge
• type DeliveryNetwork
  • func NewDeliveryNetwork() *DeliveryNetwork
  • func (G *DeliveryNetwork) Edge(uid, vid int64) graph.Edge
  • func (G *DeliveryNetwork) Edges() graph.WeightedEdges
  • func (G *DeliveryNetwork) From(id int64) graph.Nodes
  • func (G *DeliveryNetwork) GetStopGraph() *DeliveryNetwork
  • func (G *DeliveryNetwork) HasEdgeBetween(xid, yid int64) bool
  • func (G *DeliveryNetwork) HasEdgeFromTo(uid, vid int64) bool
  • func (G *DeliveryNetwork) Node(id int64) graph.Node
  • func (G *DeliveryNetwork) Nodes() graph.Nodes
  • func (G *DeliveryNetwork) To(id int64) graph.Nodes
  • func (G *DeliveryNetwork) Weight(uid, vid int64) (float64, bool)
  • func (G *DeliveryNetwork) WeightedEdge(uid, vid int64) graph.WeightedEdge
• type DeliveryNode
• type DeliveryNodes
  • func NewDeliveryNodes() *DeliveryNodes
  • func (d *DeliveryNodes) Current() graph.Node
  • func (d DeliveryNodes) Len() int
  • func (d *DeliveryNodes) Next() bool
  • func (d *DeliveryNodes) Node() graph.Node
  • func (d *DeliveryNodes) Reset()
• type GraphIterator
• type HubNode
  • func (n *HubNode) ID() int64
  • func (n *HubNode) IsHub() bool
• type StopNode
  • func (s *StopNode) ID() int64
  • func (s *StopNode) IsHub() bool

Types

type DeliveryEdge

type DeliveryEdge struct {
	Src DeliveryNode
	Dst DeliveryNode
	Wgt float64
}

DeliveryEdge is a directional edge connecting two DeliveryNodes. It implements the standard gonum Edge interface.

func (*DeliveryEdge) From

func (e *DeliveryEdge) From() graph.Node

From() returns the edge's source node.

func (*DeliveryEdge) ReversedEdge

func (e *DeliveryEdge) ReversedEdge() graph.Edge

ReversedEdge() returns a DeliveryEdge struct with the same source and destination as the receiver, but reversed. In this implementation, a reversed edge has the same weight as the original edge. This reflects the idea that the weights represent travel duration.

func (*DeliveryEdge) To

func (e *DeliveryEdge) To() graph.Node

To() returns the edge's destination node.

func (*DeliveryEdge) Weight

func (e *DeliveryEdge) Weight() float64

Weight() returns the weight of the given edge as a float.

type DeliveryEdges

type DeliveryEdges struct {
	Payload    []*DeliveryEdge
	CurrentIdx int
}

An iterator-like structure that implements the graph.Edges and graph.WeightedEdges interfaces.

func NewDeliveryEdges

func NewDeliveryEdges() *DeliveryEdges

Constructor that returns a properly initialized DeliveryEdges iterator.

func (DeliveryEdges) Current

func (e DeliveryEdges) Current() graph.WeightedEdge

Returns the current edge pointed to by the iterator. Identical to WeightedEdge, but allows me to create a common interface around gonum's graph iterators.

func (DeliveryEdges) Edge

func (e DeliveryEdges) Edge() graph.Edge

Returns the current edge as a graph.Edge, or a nil if the iterator is exhausted.

func (DeliveryEdges) Len

func (e DeliveryEdges) Len() int

Returns the number of items remaining in the iterator.

func (*DeliveryEdges) Next

func (e *DeliveryEdges) Next() bool

Advances the iterator to the next item if any items in the iterator are unexamined.

Next() returns true if there are any unexamined items remaining after the _new_ current item. If there are not, or if the iterator has already been exhausted, it returns false.

func (*DeliveryEdges) Reset

func (e *DeliveryEdges) Reset()

Returns the iterator's focus to the start of the collection.

func (DeliveryEdges) WeightedEdge

func (e DeliveryEdges) WeightedEdge() graph.WeightedEdge

Returns the current edge as a graph.WeightedEdge, or a nil if the iterator is exhausted.

type DeliveryNetwork

type DeliveryNetwork struct {
	Stops  map[int64]*StopNode
	Hubs   map[int64]*HubNode
	DEdges map[int64][]*DeliveryEdge
}

DeliveryNetwork implements a two-type DAG structure for networks consisting of delivery hubs and stops for vehicles. This network implements the Graph interface from gonum/graph.

The DeliveryNetwork struct stores nodes and edges internally using maps. This decision was made to make accessing structures by index fast and easy; the tradeoff is that it requires a little more work to marshal member structures into collections.

func NewDeliveryNetwork

func NewDeliveryNetwork() *DeliveryNetwork

NewDeliveryNetwork() bootstraps an empty delivery network, initializing all internal containers.

func (*DeliveryNetwork) Edge

func (G *DeliveryNetwork) Edge(uid, vid int64) graph.Edge

Returns the edge running from uid to vid, or nil if said edge doesn't exist.

func (*DeliveryNetwork) Edges

func (G *DeliveryNetwork) Edges() graph.WeightedEdges

Returns an iterator over all the edges in the network.

func (*DeliveryNetwork) From

func (G *DeliveryNetwork) From(id int64) graph.Nodes

From() returns an iterator over all nodes reached by id's outbound edges. If the specified node has no outbound edges, an empty list is returned.

func (*DeliveryNetwork) GetStopGraph

func (G *DeliveryNetwork) GetStopGraph() *DeliveryNetwork

GetStopGraph() extracts the subgraph formed by the stop nodes and stop-to-stop edges of G. For the time being, this is a copying (i.e., non-destructive) operation.

func (*DeliveryNetwork) HasEdgeBetween

func (G *DeliveryNetwork) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns true if an edge connects the two nodes. This function is present to satisfy the Graph interface requirements, but it is NOT direction-sensitive, even though delivery networks are.

func (*DeliveryNetwork) HasEdgeFromTo

func (G *DeliveryNetwork) HasEdgeFromTo(uid, vid int64) bool

HasEdgeFromTo is a directional version of HasEdgeBetween(), returning true if an edge exists with uid as a source and vid as a destination, and false otherwise.

func (*DeliveryNetwork) Node

func (G *DeliveryNetwork) Node(id int64) graph.Node

Node(int) returns the node referenced by the given index, or nil if the index can't be found in the network.

Note that this function does not distinguish between hub or stop nodes.

func (*DeliveryNetwork) Nodes

func (G *DeliveryNetwork) Nodes() graph.Nodes

Nodes() returns an iterator of type DeliveryNodes, allowing a pass over all the nodes in this network. If the network has no nodes, an empty list is returned.

func (*DeliveryNetwork) To

func (G *DeliveryNetwork) To(id int64) graph.Nodes

Returns an iterator over all nodes with a direct hop to the node specified by id. If the specified node has no inbound edges, an empty list is returned.

func (*DeliveryNetwork) Weight

func (G *DeliveryNetwork) Weight(uid, vid int64) (float64, bool)

Returns the weight of the edge specified, as well a hash-style ok variable. If no edge exists between the specified vertices, then it returns a 0 value for the edge weight, as well as a success value of false.

Note that Weight()'s ok return value will be set to true if uid == vid, even though the weight return will be the default option.

func (*DeliveryNetwork) WeightedEdge

func (G *DeliveryNetwork) WeightedEdge(uid, vid int64) graph.WeightedEdge

Returns the weighted edge specified by the two vertex IDs uid, vid. Returns nil if no such edge exists.

type DeliveryNode

type DeliveryNode interface {
	graph.Node
	IsHub() bool
}

DeliveryNode an extension of the standard gonum Node interface that encompasses both delivery stops as well as the hubs from which vehicles are dispatched.

type DeliveryNodes

type DeliveryNodes struct {
	Payload    []DeliveryNode
	CurrentIdx int
}

DeliveryNodes is the DeliveryNetwork implementation of the Nodes type in gonum/graph. Specifically, it is an iterator that allows application code to traverse the delivery network nodes in a list-like fashion.

Note that the DeliveryNodes iterator traverses hub nodes first, then stop nodes.

func NewDeliveryNodes

func NewDeliveryNodes() *DeliveryNodes

Creates a new DeliveryNodes struct with a properly-initialized index. Note that the Node() and Current() methods will fail on this new struct unless Next() is called first.

func (*DeliveryNodes) Current

func (d *DeliveryNodes) Current() graph.Node

Current() returns the current node without advancing the iterator. This essentially the same as Node(), but the more generic name allows me to standardize the interface across some other graph iterator types.

func (DeliveryNodes) Len

func (d DeliveryNodes) Len() int

Len() returns the number of nodes remaining in the iterator.

func (*DeliveryNodes) Next

func (d *DeliveryNodes) Next() bool

Next() returns true if there are any nodes remaining in the iterator; it then advances the Nodes iterator to the next node, if one exists.

Note that Next() must be called to _initialize_ the iterator. If this is not done, the Current() and Node() methods will return nil.

If the current node is the last node in the iterator, Next() returns false and does not advance.

This implementation borrows heavily from the [OrderedNodes](https://github.com/gonum/gonum/blob/v0.11.0/graph/iterator/nodes.go) iterator in the Gonum graph library, as it's the most economical way to meet the interface requirements.

func (*DeliveryNodes) Node

func (d *DeliveryNodes) Node() graph.Node

Node() returns the current node without advancing the iterator; i.e., it works as an implementation of peek.

func (*DeliveryNodes) Reset

func (d *DeliveryNodes) Reset()

Reset() moves the DeliveryNodes iterator's internal reference back to the start, effectively resetting the iterator.

type GraphIterator

type GraphIterator[T any] interface {
	graph.Iterator
	Current() T
}

type HubNode

type HubNode struct {
	Val int64
}

HubNode represents a location from which vehicles are dispatched.

func (*HubNode) ID

func (n *HubNode) ID() int64

ID() is a Node interface implementer that returns the hub node's ID.

func (*HubNode) IsHub

func (n *HubNode) IsHub() bool

IsHub() returns true for hub nodes.

type StopNode

type StopNode struct {
	Val       int64
	Timestamp time.Time
}

StopNode represents a delivery stop made by a vehicle. It is implicitly assumed that stops cannot be hubs.

func (*StopNode) ID

func (s *StopNode) ID() int64

ID() is a Node interface implementer that returns the stop node's ID.

func (*StopNode) IsHub

func (s *StopNode) IsHub() bool

IsHub() always returns false for stop nodes, as it's assumed for algorithmic purposes that delivery stops cannot also be hubs.