Safe Haskell	Safe-Inferred
Language	GHC2021

Data.Graph.MaxFlow

Synopsis

nothingMF :: Int
type Vertex = Int
maxFlow :: (Unbox cap, Num cap, Ord cap, Bounded cap) => Int -> Vertex -> Vertex -> (forall s. MaxFlowBuilder s cap -> ST s ()) -> cap
data MaxFlow s cap = MaxFlow {
- numVerticesMF :: !Int
- numEdgesMF :: !Int
- offsetMF :: Vector Int
- dstMF :: Vector Vertex
- residualMF :: MVector s cap
- levelMF :: MVector s Int
- revEdgeMF :: Vector Int
- iterMF :: MVector s Int
- queueMF :: Queue s Vertex
}
runMaxFlow :: (Unbox cap, Num cap, Ord cap, Bounded cap, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) cap -> m cap
bfsMF :: (Num cap, Ord cap, Unbox cap, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) cap -> m ()
dfsMF :: (Unbox cap, Num cap, Ord cap, Bounded cap, PrimMonad m) => Vertex -> Vertex -> cap -> MaxFlow (PrimState m) cap -> m cap
data MaxFlowBuilder s cap = MaxFlowBuilder {
- numVerticesMFB :: !Int
- inDegreeMFB :: MVector s Int
- edgesMFB :: Buffer s (Vertex, Vertex, cap)
}
newMaxFlowBuilder :: (Unbox cap, PrimMonad m) => Int -> m (MaxFlowBuilder (PrimState m) cap)
buildMaxFlow :: (Num cap, Unbox cap, PrimMonad m) => MaxFlowBuilder (PrimState m) cap -> m (MaxFlow (PrimState m) cap)
addEdgeMFB :: (Unbox cap, PrimMonad m) => MaxFlowBuilder (PrimState m) cap -> (Vertex, Vertex, cap) -> m ()

Documentation

nothingMF :: Int Source #

type Vertex = Int Source #

maxFlow Source #

Arguments

:: (Unbox cap, Num cap, Ord cap, Bounded cap)
=> Int	number of vertices
-> Vertex	source
-> Vertex	sink
-> (forall s. MaxFlowBuilder s cap -> ST s ())
-> cap

Dinic O(V^2E)

>>> :{
maxFlow @Int 5 0 4 $ \builder -> do
    addEdgeMFB builder (0, 1, 10)
    addEdgeMFB builder (0, 2, 2)
    addEdgeMFB builder (1, 2, 6)
    addEdgeMFB builder (1, 3, 6)
    addEdgeMFB builder (3, 2, 2)
    addEdgeMFB builder (2, 4, 5)
    addEdgeMFB builder (3, 4, 8)
:}
11
>>> maxFlow @Int 2 0 1 $ const (return ())
0

data MaxFlow s cap Source #

Constructors

MaxFlow
Fields numVerticesMF :: !Int numEdgesMF :: !Int offsetMF :: Vector Int dstMF :: Vector Vertex residualMF :: MVector s cap levelMF :: MVector s Int revEdgeMF :: Vector Int iterMF :: MVector s Int queueMF :: Queue s Vertex

runMaxFlow :: (Unbox cap, Num cap, Ord cap, Bounded cap, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) cap -> m cap Source #

bfsMF :: (Num cap, Ord cap, Unbox cap, PrimMonad m) => Vertex -> Vertex -> MaxFlow (PrimState m) cap -> m () Source #

dfsMF :: (Unbox cap, Num cap, Ord cap, Bounded cap, PrimMonad m) => Vertex -> Vertex -> cap -> MaxFlow (PrimState m) cap -> m cap Source #

data MaxFlowBuilder s cap Source #

Constructors

MaxFlowBuilder
Fields numVerticesMFB :: !Int inDegreeMFB :: MVector s Int edgesMFB :: Buffer s (Vertex, Vertex, cap) default buffer size: 1024 1024*

newMaxFlowBuilder :: (Unbox cap, PrimMonad m) => Int -> m (MaxFlowBuilder (PrimState m) cap) Source #

buildMaxFlow :: (Num cap, Unbox cap, PrimMonad m) => MaxFlowBuilder (PrimState m) cap -> m (MaxFlow (PrimState m) cap) Source #

addEdgeMFB :: (Unbox cap, PrimMonad m) => MaxFlowBuilder (PrimState m) cap -> (Vertex, Vertex, cap) -> m () Source #