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

- Constants
- type Adjacency
- type Arc
- type Flow
- type Height
- type MaxFlow
- func FindMaxFlow(network Network) *MaxFlow
- func (mf *MaxFlow) Flows(nodeID NodeID, cb func(Flow))
- func (mf *MaxFlow) RelativeHeight(nid NodeID) Height
- type Network
- type NodeID
- type PageToken
- type Rate

❖

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 )

Adjacency represents a directed edge between two nodes.

❖

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.

Flow is a utilized graph Adjacency having a flow Rate.

Height of a node.

❖

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

MaxFlow represents a maximum flow achieved over a Network.

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

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

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 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.

ID (index) of a node.

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

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.