core: go.gazette.dev/core/allocator/push_relabel

## package push_relabel

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

Package push_relabel implements a greedy variant of the push/relabel algorithm. Specifically, it is a standard variant of the algorithm using node "discharge" operations with height-based node prioritization (see [1]), but additionally introduces a notion of Arc "Priority" with greedy selection at each step. Since push/relabel specifies no order over admissible arcs, this does not change the properties of the algorithm. Use of priorities provide no formal guarantees (as min-cost/max-flow would, for example). However in practice, where priorities encode a previous max-flow solution of a closely related, incrementally updated flow network, push/relabel-with-priorities does a good job of minimizing departures from the prior solution at low computational cost.

`[1] https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm#%22Current-arc%22_data_structure_and_discharge_operation )`

### Index ¶

#### Package Files¶

`func AddArc(from, to *Node, capacity, priority int)`

AddArc adds an Arc from |from| to |to|, having |capacity| and |priority|. It also creates a residual Arc from |to| to |from|.

### func FindMaxFlow¶Uses

`func FindMaxFlow(source, sink *Node)`

FindMaxFlow determines the maximum flow of the flow network rooted at |source|.

### func SortNodeArcs¶Uses

`func SortNodeArcs(nodes ...Node)`

SortNodeArcs orders the Arcs of one or more Nodes by their respective priorities.

### type Arc¶Uses

```type Arc struct {
// Capacity of the Arc in the flow network. Positive,
// however residual Arcs may have Capacity of zero.
Capacity int32
// Output Flow of the Arc in the network. Zero or positive in Arcs with Capacity > 0,
// and zero or negative in their Capacity=0 residuals.
Flow int32
// Priority is the (descending) order in which Arcs should be selected for.
Priority int8

// Target Node of this Arc.
Target *Node
// contains filtered or unexported fields
}```

Arc defines an edge along which flow may occur in a flow network. Arcs are created in pairs: every Arc on a Node with positive Capacity, Flow, and Priority, has a reciprocal Arc on the target Node with Capacity of zero, and negative Flow and Priority of equivalent absolute values (the residual Arc).

### type Node¶Uses

```type Node struct {
// User-defined ID of this Node. Useful for identifying Nodes reached
// by walking Arcs.
ID  uint32
// Height label of this Node. Run-time is reduced if this is initialized
// to the distance of the Node from the flow network sink.
Height uint32
// Ordered Arcs of this Node (both primary and residual).
Arcs []Arc
// contains filtered or unexported fields
}```

Node defines a vertex in a flow network, through which flow occurs.

#### func InitNodes¶Uses

`func InitNodes(nodes []Node, n int, height int) []Node`

InitNodes returns a slice of Nodes having size |n|. If |nodes| has sufficient capacity, it is re-sliced and returned. Otherwise, a new backing slice is allocated. All Nodes are initialized to Height |height|.

Package push_relabel imports 3 packages (graph) and is imported by 3 packages. Updated 2019-09-12. Refresh now. Tools for package owners.