sparse_push_relabel

Documentation

Index

• Constants
• type Adjacency
• type Arc
• type Flow
• type Height
• type MaxFlow
  • func FindMaxFlow(network Network) *MaxFlow
  • func (mf *MaxFlow) Flows(nodeID NodeID, cb func(Flow))
  • func (mf *MaxFlow) RelativeHeight(nid NodeID) Height
• type Network
• type NodeID
• type PageToken
• type Rate

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
)

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 Flow

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

Flow is a utilized graph Adjacency having a flow Rate.

type Height

type Height int32

Height of a node.

type MaxFlow

type MaxFlow struct {
	// contains filtered or unexported fields
}

MaxFlow represents a maximum flow achieved over a Network.

func FindMaxFlow

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

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

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

func (*MaxFlow) RelativeHeight

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

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

type NodeID int32

ID (index) of a node.

type PageToken

type PageToken int32

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

type Rate

type Rate int32

Rate is the unit of flow velocity.