Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.MaxFlow

Contents

Max flow graph
Constructor
Graph building
Flow operations
Minimum cut
Edge information

Description

It solves maximum flow problem.

Example

Expand

Create a max flow graph (MfGraph):

>>> import AtCoder.MaxFlow qualified as MF
>>> g <- MF.new @_ @Int 3        --  0     1     2

Build a simple graph with addEdge g from to cap or addEdge_:

>>> MF.addEdge g 0 1 (2 :: Int)  --  0 --> 1     2
0

>>> MF.addEdge_ g 1 2 (1 :: Int) --  0 --> 1 --> 2

Augument the flow with flow. maxFlow can also be used when there's no flow limit:

>>> MF.flow g 0 2 {- flowLimit -} maxBound -- same as `MF.maxFlow g 0 2`
1

Get the minimum cut with minCut. In this case, removing the second edge makes the minimum cut (note that the edge capacity $1$ = max flow):

>>> MF.minCut g 0 -- returns a Bit vector. `1` (`Bit True`) is on the `s` side.
[1,1,0]

Retrieve the edge state with getEdge. We can confirm the flow is 1:

>>> MF.getEdge g 0 -- returns (from, to, cap, flow)
(0,1,2,1)

Since: 1.0.0.0

Synopsis

data MfGraph s cap
new :: (PrimMonad m, Unbox cap) => Int -> m (MfGraph (PrimState m) cap)
addEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m Int
addEdge_ :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m ()
getEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> m (Int, Int, cap, cap)
flow :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m cap
maxFlow :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Bounded cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> m cap
minCut :: (PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> m (Vector Bit)
edges :: (PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> m (Vector (Int, Int, cap, cap))
changeEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> cap -> cap -> m ()

Max flow graph

data MfGraph s cap Source #

Max flow graph.

Since: 1.0.0.0

Constructor

new :: (PrimMonad m, Unbox cap) => Int -> m (MfGraph (PrimState m) cap) Source #

Creates a graph of $n$ vertices and $0$ edges. cap is the type of the capacity.

Constraints

$0 \leq n$

Complexity

$O(n)$

Since: 1.0.0.0

Graph building

addEdge Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	from
-> Int	to
-> cap	cap
-> m Int	Edge index

Adds an edge oriented from the vertex from to the vertex to with the capacity cap and the flow amount $0$. It returns an integer $k$ such that this is the $k$-th edge that is added.

Constraints

$0 \leq \mathrm{from}, \mathrm{to} \lt n$
$0 \leq \mathrm{cap}$

Complexity

$O(1)$ amortized

Since: 1.0.0.0

addEdge_ Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	from
-> Int	to
-> cap	cap
-> m ()

addEdge with the return value discarded.

Constraints

$0 \leq \mathrm{from}, \mathrm{to} \lt n$
$0 \leq \mathrm{cap}$

Complexity

$O(1)$ amortized

Since: 1.0.0.0

getEdge Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	Vertex
-> m (Int, Int, cap, cap)	Tuple of `(from, to, cap, flow)`

$O(1)$ Returns the current internal state of $i$-th edge: (from, to, cap, flow). The edges are ordered in the same order as added by addEdge.

Constraints

$0 \leq i \lt m$

Complexity

$O(1)$

Since: 1.0.0.0

Flow operations

flow Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	Source `s`
-> Int	Sink `t`
-> cap	Flow limit
-> m cap	Max flow

Augments the flow from $s$ to $t$ as much as possible, until reaching the amount of flowLimit. It returns the amount of the flow augmented. You may call it multiple times.

Constraints

$s \neq t$
$0 \leq s, t \lt n$

Complexity

$O((n + m) \sqrt{m})$ (if all the capacities are $1$),
$O(n^2 m)$ (general), or
$O(F(n + m))$, where $F$ is the returned value

Since: 1.0.0.0

maxFlow Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Bounded cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	Source `s`
-> Int	Sink `t`
-> m cap	Max flow

flow with no capacity limit.

Constraints

$s \neq t$
$0 \leq s, t \lt n$

Complexity

$O((n + m) \sqrt{m})$ (if all the capacities are $1$),
$O(n^2 m)$ (general), or
$O(F(n + m))$, where $F$ is the returned value

Since: 1.0.0.0

Minimum cut

minCut Source #

Arguments

:: (PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	Source `s`
-> m (Vector Bit)	Minimum cut

Returns a vector of length $n$, such that the $i$-th element is True if and only if there is a directed path from $s$ to $i$ in the residual network. The returned vector corresponds to a $s-t$ minimum cut after calling maxFlow s t.

Complexity

$O(n + m)$, where $m$ is the number of added edges.

Since: 1.0.0.0

Edge information

edges Source #

Arguments

:: (PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> m (Vector (Int, Int, cap, cap))	Vector of `(from, to, cap, flow)`

Returns the current internal state of the edges: (from, to, cap, flow). The edges are ordered in the same order as added by addEdge.

Complexity

$O(m)$, where $m$ is the number of added edges.

Since: 1.0.0.0

changeEdge Source #

Arguments

:: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap)
=> MfGraph (PrimState m) cap	Graph
-> Int	Edge index
-> cap	New capacity
-> cap	New flow
-> m ()

$O(1)$ Changes the capacity and the flow amount of the $i$-th edge to newCap and newFlow, respectively. It oes not change the capacity or the flow amount of other edges.

Constraints

$0 \leq \mathrm{newflow} \leq \mathrm{newcap}$

Complexity

$O(1)$

Since: 1.0.0.0