| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.MaxFlow
Description
It solves maximum flow problem.
Example
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 20>>>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
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
Constructor
new :: (PrimMonad m, Unbox cap) => Int -> m (MfGraph (PrimState m) cap) #
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
Graph building
addEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m Int #
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
addEdge_ :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m () #
addEdge with return value discarded.
Constraints
- \(0 \leq \mathrm{from}, \mathrm{to} \lt n\)
- \(0 \leq \mathrm{cap}\)
Complexity
- \(O(1)\) amortized
Since: 1.0.0
getEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> m (Int, Int, cap, cap) #
\(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
Flow operations
flow :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m cap #
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
maxFlow :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Bounded cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> m cap #
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
Minimum cut
minCut :: (PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> m (Vector Bit) #
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
Edge information
edges :: (PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> m (Vector (Int, Int, cap, cap)) #
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
changeEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Unbox cap) => MfGraph (PrimState m) cap -> Int -> cap -> cap -> m () #
\(O(1)\) Changes the capacity and the flow amount of the $i$-th edge to newCap and
newFlow, respectively. It doesn't 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