toy-lib-0.1.0.0

Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.MaxFlow

Description

\(O(V^2 E)\) Max flow algorithm (Dinic's algorithm). Heavily inspired by cojna/iota.

Just run maxFlow to get the result. maxFlow' returns result with context.

Typical problems

ABC 205 - F

Synopsis

data MaxFlow s c = MaxFlow {
- nVertsMF :: !Int
- nEdgesMF :: !Int
- offsetsMF :: !(Vector Int)
- edgeDstMF :: !(Vector Int)
- edgeRevIndexMF :: !(Vector Int)
- edgeCapMF :: !(MVector s c)
}
data MaxFlowBuffer s c = MaxFlowBuffer {
- distsMF :: !(MVector s Int)
- queueMF :: !(Buffer s Vertex)
- iterMF :: !(MVector s Int)
}
maxFlow :: (Unbox c, Num c, Ord c, Bounded c) => Int -> Int -> Int -> Vector (Vertex, Vertex, c) -> c
maxFlow' :: (PrimMonad m, Unbox c, Num c, Ord c, Bounded c) => Int -> Int -> Int -> Vector (Vertex, Vertex, c) -> m (c, MaxFlow (PrimState m) c)
edgesMF :: (PrimMonad m, Unbox c, Num c) => MaxFlow (PrimState m) c -> m (Vector (Int, Int, c, c))
undefMF :: Int
buildMaxFlow :: forall c m. (Unbox c, Num c, PrimMonad m) => Int -> Vector (Vertex, Vertex, c) -> m (MaxFlow (PrimState m) c)
runMaxFlow :: forall c m. (Unbox c, Num c, Ord c, Bounded c, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) c -> m c
runMaxFlowBfs :: forall c m. (Unbox c, Num c, Ord c, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) c -> MaxFlowBuffer (PrimState m) c -> m ()
runMaxFlowDfs :: forall c m. (Unbox c, Num c, Ord c, PrimMonad m) => Vertex -> Vertex -> c -> MaxFlow (PrimState m) c -> MaxFlowBuffer (PrimState m) c -> m c

Documentation

data MaxFlow s c #

Max flow calculation information and states.

Internals

Internally the graph is stored in a CSR (compressed sparse row).

Invariants

Sum of the capacities of one edge and the reverse edge is zero.

Constructors

MaxFlow
Fields nVertsMF :: !Int nEdgesMF :: !Int offsetsMF :: !(Vector Int) Source vertex -> initial edge index. Note that edges are sourted by the starting vertex. edgeDstMF :: !(Vector Int) Edge index -> destination vertex. edgeRevIndexMF :: !(Vector Int) Edge index -> reverse edge index. edgeCapMF :: !(MVector s c) Edge index -> residual edge capacity.

data MaxFlowBuffer s c #

Mutable states on running Dinic's algorithm.

Constructors

MaxFlowBuffer
Fields distsMF :: !(MVector s Int) BFS result. queueMF :: !(Buffer s Vertex) Queue for BFS iterMF :: !(MVector s Int) DFS state for iterating through all the neighbors.

maxFlow :: (Unbox c, Num c, Ord c, Bounded c) => Int -> Int -> Int -> Vector (Vertex, Vertex, c) -> c #

\(O(V^2E)\) max flow algorithm (Dinic's algorithm).

maxFlow' :: (PrimMonad m, Unbox c, Num c, Ord c, Bounded c) => Int -> Int -> Int -> Vector (Vertex, Vertex, c) -> m (c, MaxFlow (PrimState m) c) #

\(O(V^2E)\) Runs maxFlow and retrieves the last state.

TODO: Return a freezed version?

edgesMF :: (PrimMonad m, Unbox c, Num c) => MaxFlow (PrimState m) c -> m (Vector (Int, Int, c, c)) #

\(O(E)\) Handy API for retrieving edge information (v1, v2, cap, flow) from the maxFlow results.

Be warned that it contains reverse edges and edge fromto sourcesink.

undefMF :: Int #

buildMaxFlow :: forall c m. (Unbox c, Num c, PrimMonad m) => Int -> Vector (Vertex, Vertex, c) -> m (MaxFlow (PrimState m) c) #

\(O(V+E)\) Builds MaxFlow from edges.

runMaxFlow :: forall c m. (Unbox c, Num c, Ord c, Bounded c, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) c -> m c #

\(O(V^2E)\) Runs the Dinic's algorithm.

Overview

Dinic's algorithm loops the following steps: 1. runMaxFlowBfs: Creates a DAG with BFS. 2. runMaxFlowDfs: Adds flow from the source to the sink.

runMaxFlowBfs :: forall c m. (Unbox c, Num c, Ord c, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) c -> MaxFlowBuffer (PrimState m) c -> m () #

Collect shortest distances from the source vertex using BFS.

runMaxFlowDfs :: forall c m. (Unbox c, Num c, Ord c, PrimMonad m) => Vertex -> Vertex -> c -> MaxFlow (PrimState m) c -> MaxFlowBuffer (PrimState m) c -> m c #

Modify the flow