core: go.gazette.dev/core/allocator/push_relabel Index | Files

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

push_relabel.go

func AddArc Uses

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.