README
¶
flownet
Code for maximum-flow and two of its more interesting variants, circulations and transshipments.
Documentation
¶
Overview ¶
Package flownet provides algorithms for solving optimization problems on a flow network.
Index ¶
- Constants
- func TopSort(fn FlowNetwork, less func(int, int) bool) ([]int, error)
- type Circulation
- func (c *Circulation) AddEdge(fromID, toID int, capacity, demand int64) error
- func (c *Circulation) Capacity(from, to int) int64
- func (c *Circulation) EdgeDemand(from, to int) int64
- func (c *Circulation) Flow(from, to int) int64
- func (c *Circulation) NodeDemand(nodeID int) int64
- func (c *Circulation) PushRelabel()
- func (c *Circulation) SatisfiesDemand() bool
- func (c *Circulation) SetNodeDemand(nodeID int, demand int64) error
- type FlowNetwork
- func (g *FlowNetwork) AddEdge(fromID, toID int, capacity int64) error
- func (g *FlowNetwork) AddNode() int
- func (g FlowNetwork) Capacity(from, to int) int64
- func (g FlowNetwork) Flow(from, to int) int64
- func (g FlowNetwork) Outflow() int64
- func (g *FlowNetwork) PushRelabel()
- func (g FlowNetwork) Residual(from, to int) int64
- func (g *FlowNetwork) SetNodeOrder(nodeIDs []int) error
- type SanityCheckers
- type Transshipment
Examples ¶
Constants ¶
const Sink int = -1
Sink is the ID of the sink pseudonode.
const Source int = -2
Source is the ID of the source pseudonode.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Circulation ¶
type Circulation struct {
FlowNetwork
// contains filtered or unexported fields
}
A Circulation is a flow network which has an additional demand associated with each of its nodes or edges. Flow may be supplied to the network via negative node demands.
Whereas in a traditional flow network problem we are interested in maximizing the amount of flow from the source to the sink, in a circulation we ask if there is a feasible flow which satisfies the demand. Nodes in a circulation are not connected the source or sink as in a traditional flow network. Trying to add these connections to a Circulation will cause an error.
Example ¶
Demonstrates how to use a circulation to work with node and edge demands.
package main
import (
"fmt"
"github.com/kalexmills/flownet"
)
func main() {
c := flownet.NewCirculation(6)
type edge struct {
source, target int
capacity, demand int64
}
// a circulation allows for demand values on the edges of the flow network.
edges := []edge{
{0, 1, 15, 0}, {0, 2, 4, 0}, {1, 3, 12, 0}, {3, 2, 3, 0}, {2, 4, 10, 0},
{4, 1, 5, 4}, {4, 5, 10, 0}, {3, 5, 7, 0},
}
for _, edge := range edges {
c.AddEdge(edge.source, edge.target, edge.capacity, edge.demand)
}
c.SetNodeDemand(0, -4)
c.SetNodeDemand(5, 4)
c.PushRelabel()
// there is no notion of source or sink in a circulation; the only question
// is whether there is a flow which satisfies the requested demand.
fmt.Printf("demand satisfied: %t\n", c.SatisfiesDemand())
// the outflow for a circulation is the total amount of flow circulating
// through the network.
fmt.Printf("total flow: %d\n", c.Outflow())
for _, e := range edges {
flow := c.Flow(e.source, e.target)
capacity := c.Capacity(e.source, e.target)
demand := c.EdgeDemand(e.source, e.target)
fmt.Printf("\tedge %d -> %d: flow = %d / %d\tdemand = %d\n", e.source, e.target, flow, capacity, demand)
}
}
Output: demand satisfied: true total flow: 4 edge 0 -> 1: flow = 3 / 15 demand = 0 edge 0 -> 2: flow = 1 / 4 demand = 0 edge 1 -> 3: flow = 7 / 12 demand = 0 edge 3 -> 2: flow = 3 / 3 demand = 0 edge 2 -> 4: flow = 4 / 10 demand = 0 edge 4 -> 1: flow = 4 / 5 demand = 4 edge 4 -> 5: flow = 0 / 10 demand = 0 edge 3 -> 5: flow = 4 / 7 demand = 0
func NewCirculation ¶
func NewCirculation(numNodes int) Circulation
NewCirculation constructs a new graph allocating initial capacity for the provided number of nodes.
func (*Circulation) AddEdge ¶
func (c *Circulation) AddEdge(fromID, toID int, capacity, demand int64) error
AddEdge sets the capacity and non-negative demand of the edge in the circulation. An error is returned if either fromID or toID are not valid node IDs. Adding an edge twice has no additional effect. Setting demands on edges also updates the demand on the adjacent nodes.
func (*Circulation) Capacity ¶
func (c *Circulation) Capacity(from, to int) int64
Capacity returns the capacity of the provided edge.
func (*Circulation) EdgeDemand ¶
func (c *Circulation) EdgeDemand(from, to int) int64
EdgeDemand returns the demand required along each edge.
func (*Circulation) Flow ¶
func (c *Circulation) Flow(from, to int) int64
Flow returns the flow achieved by the circulation along the provided edge. The results are only meaningful after PushRelabel has been run.
func (*Circulation) NodeDemand ¶
func (c *Circulation) NodeDemand(nodeID int) int64
NodeDemand returns the demand required at each node.
func (*Circulation) PushRelabel ¶
func (c *Circulation) PushRelabel()
PushRelabel finds a valid circulation (if one exists) via the push-relabel algorithm.
func (*Circulation) SatisfiesDemand ¶
func (c *Circulation) SatisfiesDemand() bool
SatisfiesDemand is true iff the flow satisfies all of the required node and edge demands.
func (*Circulation) SetNodeDemand ¶
func (c *Circulation) SetNodeDemand(nodeID int, demand int64) error
SetNodeDemand sets the demand for a node.
type FlowNetwork ¶
type FlowNetwork struct {
// contains filtered or unexported fields
}
A FlowNetwork is a directed graph which can be used to solve maximum-flow problems. Each edge is associated with a capacity and a flow. The flow on each edge may not exceed the stated capacity.
Each node may optionally be connected to a source or a sink node. By default, nodes which do not have any incoming edges are presumed to be connected to the source, while nodes which have no outgoing edges are presumed to be connected to the sink. These default source/sink connections all have maximum capacity of math.MaxInt64. The first time AddEdge is called with a value of either flownet.Source or flownet.Sink, all the presumptive edges to the respective node are cleared and the programmer becomes responsible for managing all edges to the Source or Sink, respectively.
Example ¶
Demonstrates how to use a flow network to compute max-flow.
package main
import (
"fmt"
"github.com/kalexmills/flownet"
)
func main() {
fn := flownet.NewFlowNetwork(6) // allocates a flow network with nodeIDs 0, 1, ..., 5
type edge struct {
source, target int
capacity int64
}
edges := []edge{
{0, 1, 15}, {0, 2, 4}, {1, 3, 12}, {3, 2, 3}, {2, 4, 10},
{4, 1, 5}, {4, 5, 10}, {3, 5, 7},
}
for _, edge := range edges {
// adds an edge between nodes with the provided capacity
fn.AddEdge(edge.source, edge.target, edge.capacity)
}
fn.PushRelabel() // run max-flow
fmt.Printf("found max flow of %d = 14\n", fn.Outflow())
for _, e := range edges {
flow := fn.Flow(e.source, e.target)
capacity := fn.Capacity(e.source, e.target)
fmt.Printf("\tedge %d -> %d: flow = %d / %d\n", e.source, e.target, flow, capacity)
}
}
Output: found max flow of 14 = 14 edge 0 -> 1: flow = 10 / 15 edge 0 -> 2: flow = 4 / 4 edge 1 -> 3: flow = 10 / 12 edge 3 -> 2: flow = 3 / 3 edge 2 -> 4: flow = 7 / 10 edge 4 -> 1: flow = 0 / 5 edge 4 -> 5: flow = 7 / 10 edge 3 -> 5: flow = 7 / 7
func NewFlowNetwork ¶
func NewFlowNetwork(numNodes int) FlowNetwork
NewFlowNetwork constructs a new graph, preallocating enough memory for the provided number of nodes.
func (*FlowNetwork) AddEdge ¶
func (g *FlowNetwork) AddEdge(fromID, toID int, capacity int64) error
AddEdge sets the capacity of an edge in the flow network. Adding an edge twice has no additional effect. Attempting to use flownet.Source as toId or flownet.Sink as fromID yields an error. An error is returned if either fromID or toID are not valid node IDs.
func (*FlowNetwork) AddNode ¶
func (g *FlowNetwork) AddNode() int
AddNode adds a new node to the graph and returns its ID, which must be used in subsequent calls.
func (FlowNetwork) Capacity ¶
func (g FlowNetwork) Capacity(from, to int) int64
Capacity returns the capacity of the provided edge.
func (FlowNetwork) Flow ¶
func (g FlowNetwork) Flow(from, to int) int64
Flow returns the flow along an edge. Before PushRelabel is called this method returns 0.
func (FlowNetwork) Outflow ¶
func (g FlowNetwork) Outflow() int64
Outflow returns the amount of flow which leaves the network via the sink. After PushRelabel has been called, this will be a solution to the max-flow problem.
func (*FlowNetwork) PushRelabel ¶
func (g *FlowNetwork) PushRelabel()
PushRelabel finds a maximum flow via the relabel-to-front variant of the push-relabel algorithm. More specifically, PushRelabel visits each node in the network in the node order and attempts to discharges excess flow from the node. This may update the node's label. When a node's label changes as a result of the algorithm, it is moved to the front of the node order, and all nodes are visited once more.
func (FlowNetwork) Residual ¶
func (g FlowNetwork) Residual(from, to int) int64
Residual returns the residual flow along an edge, defined as capacity - flow.
func (*FlowNetwork) SetNodeOrder ¶
func (g *FlowNetwork) SetNodeOrder(nodeIDs []int) error
SetNodeOrder sets the order in which nodes are initially visited by the PushRelabel algorithm. By default, nodes are first visited in order of ID, then in descending order of label. As long as all of the nodeIDs are contained in the provided array, the PushRelabel algorithm will work properly. If some nodeID is missing, an error is returned and the order will remain unchanged. If any node is added after SetNodeOrder is called, the node order will reset to the default.
The node order set here only affects the initial node ordering for the purposes of the push-relabel algorithm. Any relabeling that occurs during the algorithm may alter this order in unintuitive ways.
type SanityCheckers ¶
type SanityCheckers struct{}
SanityCheckers holds sanity check procedures for flownet types.
var SanityChecks SanityCheckers
SanityChecks contains sanity check procedures for FlowNetworks, Transshipments, and Circulations.
func (SanityCheckers) Circulation ¶
func (sc SanityCheckers) Circulation(c Circulation) error
Circulation runs sanity checks against a circulation that has previously had its flow computed. These sanity checks include the FlowNetwork checks; they do not need to be run separately.
func (SanityCheckers) FlowNetwork ¶
func (sc SanityCheckers) FlowNetwork(fn FlowNetwork, flowEquality bool) error
FlowNetwork runs several sanity checks against a FlowNetwork that has had previously had its flow computed. If flowEquality is true, the inflow of each node is checked to ensure it is equal to the outflow.
func (SanityCheckers) Transshipment ¶
func (sc SanityCheckers) Transshipment(t Transshipment) error
Transshipment runs sanity checks and reports them as appropriate for a Transshipment. These sanity checks include the Circulation and FlowNetwork checks; they do not need to be run separately.
type Transshipment ¶
type Transshipment struct {
Circulation
// contains filtered or unexported fields
}
A Transshipment is a circulation which allows flow to remain in a node without flowing out. Each node has an amount of storage, with an associated minimum and maximum. By default, every node in a Transshipment stores no extra flow.
Transshipments can be used to model problems in which flow leaks or is consumed at certain points in the network.
func NewTransshipment ¶
func NewTransshipment(numNodes int) Transshipment
NewTransshipment constructs a new graph, allocating enough capacity for the provided number of nodes.
func (*Transshipment) NodeFlow ¶
func (t *Transshipment) NodeFlow(nodeID int) int64
NodeFlow returns the amount of flow stored at the provided node. The results are only meaningful after PushRelabel has been run.
func (*Transshipment) PushRelabel ¶
func (t *Transshipment) PushRelabel()
PushRelabel finds a valid transshipment (if one exists) via the push-relabel algorithm.
func (*Transshipment) SetNodeBounds ¶
func (t *Transshipment) SetNodeBounds(nodeID int, storageMin, storageMax int64) error
SetNodeBounds sets the upper and lower bounds on capacity which is allowed to stay in a node.
Source Files