`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 )

- func AddArc(from, to *Node, capacity, priority int)
- func FindMaxFlow(source, sink *Node)
- func SortNodeArcs(nodes ...Node)
- type Arc
- type Node

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

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

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

❖

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

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.