Documentation
¶
Overview ¶
Package sparse_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 virtual graph model which allows for dynamically controlling the possible Arcs and capacities which are exposed to the solver.
As the solver is greedy at each individual step, and push/relabel specifies no particular order over admissible arcs, networks can leverage arc presentation order to coerce the maximum flow solution towards a previous solution without breaking the fundamental properties of the algorithm.
Tuning the presentation of certain arcs over others 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 does a good job of minimizing departures from the prior solution at low computational cost. The solver will depart from that desired solution only where necessary to establish a maximum flow.
[1] https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm#%22Current-arc%22_data_structure_and_discharge_operation )
Index ¶
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 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Adjacency ¶
type Adjacency struct {
From, To NodeID
}
Adjacency represents a directed edge between two nodes.
type Arc ¶
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 MaxFlow ¶
type MaxFlow struct {
// contains filtered or unexported fields
}
MaxFlow represents a maximum flow achieved over a Network.
func FindMaxFlow ¶
FindMaxFlow solves for the maximum flow of the given Network using a sparse variant of the push/relabel algorithm.
func (*MaxFlow) RelativeHeight ¶
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 ¶
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.
Source Files