Documentation
¶
Overview ¶
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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AddArc ¶
AddArc adds an Arc from |from| to |to|, having |capacity| and |priority|. It also creates a residual Arc from |to| to |from|.
func FindMaxFlow ¶
func FindMaxFlow(source, sink *Node)
FindMaxFlow determines the maximum flow of the flow network rooted at |source|.
func SortNodeArcs ¶
func SortNodeArcs(nodes ...Node)
SortNodeArcs orders the Arcs of one or more Nodes by their respective priorities.
Types ¶
type Arc ¶
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 ¶
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.
Source Files