core: Index | Files

package sparse_push_relabel

import ""


Package Files



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

type Adjacency Uses

type Adjacency struct {
    From, To NodeID

Adjacency represents a directed edge between two nodes.

type Arc Uses

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 Flow Uses

type Flow struct {
    Rate Rate
    // contains filtered or unexported fields

Flow is a utilized graph Adjacency having a flow Rate.

type Height Uses

type Height int32

Height of a node.

type MaxFlow Uses

type MaxFlow struct {
    // contains filtered or unexported fields

MaxFlow represents a maximum flow achieved over a Network.

func FindMaxFlow Uses

func FindMaxFlow(network Network) *MaxFlow

FindMaxFlow solves for the maximum flow of the given Network using a sparse variant of the push/relabel algorithm.

func (*MaxFlow) Flows Uses

func (mf *MaxFlow) Flows(nodeID NodeID, cb func(Flow))

Flows invokes the callback for each Flow of the given NodeID.

func (*MaxFlow) RelativeHeight Uses

func (mf *MaxFlow) RelativeHeight(nid NodeID) Height

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 Uses

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.

type NodeID Uses

type NodeID int32

ID (index) of a node.

type PageToken Uses

type PageToken int32

PageToken is used to traverse through a variable number of []Arc "pages" supplied by instances of the Network interface.

type Rate Uses

type Rate int32

Rate is the unit of flow velocity.

Package sparse_push_relabel imports 2 packages (graph) and is imported by 3 packages. Updated 2020-08-25. Refresh now. Tools for package owners.