core: go.gazette.dev/core/allocator/sparse_push_relabel Index | Files

package sparse_push_relabel

import "go.gazette.dev/core/allocator/sparse_push_relabel"

Index

Package Files

push_relabel.go

Constants

❖
const (
    // PageInitial is the first page of node []Arcs.
    PageInitial PageToken = 0
    // PageEOF indicates that no further pages of node []Arcs remain.
    PageEOF PageToken = math.MaxInt32

    // SourceID is the node from which all flow originates.
    SourceID NodeID = 0
    // SinkID is the node to which all flow is ultimately directed.
    SinkID NodeID = 1
)

type Adjacency Uses

❖
type Adjacency struct {
    From, To NodeID
}

Adjacency represents a directed edge between two nodes.

type Arc Uses

❖
type Arc struct {
    To       NodeID // Node to which this Arc directs.
    Capacity Rate   // Maximum flow Rate of this Arc.
    // PushFront indicates whether a Flow associated with this Arc should be
    // added at the head or tail of its linked lists. The primary implication
    // is that Flows residuals are examined by discharge() in reverse order
    // (eg, LIFO). By pushing to the front of the list, an Arc can express
    // a preference that its residual should be considered only if no other
    // residual will suffice.
    PushFront bool
}

Arc is directed edge between a current node and another.

type Flow Uses

❖
type Flow struct {
    Adjacency
    Rate Rate
    // contains filtered or unexported fields
}

Flow is a utilized graph Adjacency having a flow Rate.

type Height Uses

❖
type Height int32

Height of a node.

type MaxFlow Uses

❖
type MaxFlow struct {
    // contains filtered or unexported fields
}

MaxFlow represents a maximum flow achieved over a Network.

func FindMaxFlow Uses

❖
func FindMaxFlow(network Network) *MaxFlow

FindMaxFlow solves for the maximum flow of the given Network using a sparse variant of the push/relabel algorithm.

func (*MaxFlow) Flows Uses

❖
func (mf *MaxFlow) Flows(nodeID NodeID, cb func(Flow))

Flows invokes the callback for each Flow of the given NodeID.

func (*MaxFlow) RelativeHeight Uses

❖
func (mf *MaxFlow) RelativeHeight(nid NodeID) Height

RelativeHeight returns the node Height delta, relative to the source node. Depending on Network semantics, implementations may wish to use RelativeHeight to condition capacities of returned []Arcs, for example by increasing capacity if sufficient "pressure" has built up within the network.

type Network Uses

❖
type Network interface {
    // Nodes returns the number of nodes in the network,
    // including the source & sink.
    Nodes() int
    // InitialHeight returns the initial Height of each node. This may be zero
    // without impacting correctness, but for better performance should be the
    // node's distance from the Sink.
    InitialHeight(NodeID) Height
    // Arcs returns the given page of node []Arcs, along with the next
    // PageToken of Arcs which may be requested. The initial PageToken
    // will be PageInitial, and PageEOF should be returned to indicate
    // that no further pages remain.
    Arcs(*MaxFlow, NodeID, PageToken) ([]Arc, PageToken)
}

Network is a flow network for which a maximum flow is desired. The push/relabel solver inspects the Network as needed while executing the algorithm. Arcs in particular may be called many times for a given NodeID and PageToken.

type NodeID Uses

❖
type NodeID int32

ID (index) of a node.

type PageToken Uses

❖
type PageToken int32

PageToken is used to traverse through a variable number of []Arc "pages" supplied by instances of the Network interface.

type Rate Uses

❖
type Rate int32

Rate is the unit of flow velocity.

Package sparse_push_relabel imports 2 packages (graph) and is imported by 3 packages. Updated 2020-08-25. Refresh now. Tools for package owners.