Safe Haskell	Safe-Inferred
Language	GHC2021

Data.Graph.MinCostFlow

Synopsis

nothingMCF :: Int
type Vertex = Int
type Cost = Int
type Capacity = Int
minCostFlow :: Int -> Vertex -> Vertex -> Capacity -> (forall s. MinCostFlowBuilder s -> ST s ()) -> (Cost, Capacity)
data MinCostFlow s = MinCostFlow {
- numVerticesMCF :: !Int
- numEdgesMCF :: !Int
- offsetMCF :: Vector Int
- dstMCF :: Vector Vertex
- costMCF :: Vector Cost
- residualMCF :: MVector s Capacity
- potentialMCF :: MVector s Cost
- distMCF :: MVector s Cost
- heapMCF :: MinBinaryHeap s Word64
- revEdgeMCF :: Vector Int
- prevVertexMCF :: MVector s Vertex
- prevEdgeMCF :: MVector s Int
}
runMinCostFlow :: PrimMonad m => Vertex -> Vertex -> Capacity -> MinCostFlow (PrimState m) -> m (Cost, Capacity)
encodeMCF :: Cost -> Vertex -> Word64
decodeMCF :: Word64 -> (Cost, Vertex)
dijkstraMCF :: PrimMonad m => Vertex -> Vertex -> MinCostFlow (PrimState m) -> m Bool
updateResidualMCF :: PrimMonad m => Vertex -> Capacity -> MinCostFlow (PrimState m) -> m Capacity
data MinCostFlowBuilder s = MinCostFlowBuilder {
- numVerticesMCFB :: !Int
- inDegreeMCFB :: MVector s Int
- edgesMCFB :: Buffer s (Vertex, Vertex, Cost, Capacity)
}
newMinCostFlowBuilder :: PrimMonad m => Int -> m (MinCostFlowBuilder (PrimState m))
addEdgeMCFB :: PrimMonad m => MinCostFlowBuilder (PrimState m) -> Vertex -> Vertex -> Cost -> Capacity -> m ()
buildMinCostFlow :: PrimMonad m => MinCostFlowBuilder (PrimState m) -> m (MinCostFlow (PrimState m))

Documentation

nothingMCF :: Int Source #

type Vertex = Int Source #

type Cost = Int Source #

type Capacity = Int Source #

minCostFlow Source #

Arguments

:: Int	number of vertices
-> Vertex	source
-> Vertex	sink
-> Capacity	flow
-> (forall s. MinCostFlowBuilder s -> ST s ())
-> (Cost, Capacity)

Primal Dual O(FElog V)

>>> :{
minCostFlow 2 0 1 2 (\builder -> do
    addEdgeMCFB builder 0 1 123 2
    )
:}
(246,2)
>>> :{
minCostFlow 2 0 1 123456789 (\builder -> do
    addEdgeMCFB builder 0 1 123 2
    )
:}
(246,2)

data MinCostFlow s Source #

Constructors

MinCostFlow
Fields numVerticesMCF :: !Int numEdgesMCF :: !Int offsetMCF :: Vector Int dstMCF :: Vector Vertex costMCF :: Vector Cost residualMCF :: MVector s Capacity potentialMCF :: MVector s Cost distMCF :: MVector s Cost heapMCF :: MinBinaryHeap s Word64 revEdgeMCF :: Vector Int prevVertexMCF :: MVector s Vertex prevEdgeMCF :: MVector s Int

runMinCostFlow :: PrimMonad m => Vertex -> Vertex -> Capacity -> MinCostFlow (PrimState m) -> m (Cost, Capacity) Source #

encodeMCF :: Cost -> Vertex -> Word64 Source #

cost 48bit / vertex 16bit

decodeMCF :: Word64 -> (Cost, Vertex) Source #

dijkstraMCF :: PrimMonad m => Vertex -> Vertex -> MinCostFlow (PrimState m) -> m Bool Source #

updateResidualMCF :: PrimMonad m => Vertex -> Capacity -> MinCostFlow (PrimState m) -> m Capacity Source #

data MinCostFlowBuilder s Source #

Constructors

MinCostFlowBuilder
Fields numVerticesMCFB :: !Int inDegreeMCFB :: MVector s Int edgesMCFB :: Buffer s (Vertex, Vertex, Cost, Capacity) default buffer size: 1024 1024*

newMinCostFlowBuilder :: PrimMonad m => Int -> m (MinCostFlowBuilder (PrimState m)) Source #

addEdgeMCFB :: PrimMonad m => MinCostFlowBuilder (PrimState m) -> Vertex -> Vertex -> Cost -> Capacity -> m () Source #

cost >= 0

buildMinCostFlow :: PrimMonad m => MinCostFlowBuilder (PrimState m) -> m (MinCostFlow (PrimState m)) Source #