push_relabel

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

• func AddArc(from, to *Node, capacity, priority int)
• func FindMaxFlow(source, sink *Node)
• func SortNodeArcs(nodes ...Node)
• type Arc
• type Node
  • func InitNodes(nodes []Node, n int, height int) []Node

Functions

func AddArc

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

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.

func InitNodes

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