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
- type DeliveryEdges
- type 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
- type GraphIterator
- type HubNode
- type StopNode
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
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 HubNode ¶
type HubNode struct {
Val int64
}
HubNode represents a location from which vehicles are dispatched.
Source Files