Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.MinCostFlow

Description

Minimum cost flow calculation (Ford-Fulkerson algorithm).

Typical problems

Considerations

Remove negative edges in order to avoid negative, infinite loop.
Create bipass when the best cost can come with smaller flow than the target flow.
Or I should implement min_cost_slop alternative.

Synopsis

type CapacityMCF c = c
type FlowMCF c = c
type CostMCF c = c
data MinCostFlow s c = MinCostFlow {
- nVertsMCF :: !Int
- nEdgesMCF :: !Int
- offsetsMCF :: !(Vector Int)
- edgeDstMCF :: !(Vector Int)
- edgeRevIndexMCF :: !(Vector Int)
- edgeCapMCF :: !(MVector s (CapacityMCF c))
- edgeCostMCF :: !(Vector (CostMCF c))
}
data MinCostFlowBuffer r s c = MinCostFlowBuffer {
- distsMCF :: !(MVector s r)
- prevVertMCF :: !(MVector s Vertex)
- prevEdgeMCF :: !(MVector s EdgeId)
}
bestFlow' :: (Num (f (CostMCF c)), Monoid (f (CostMCF c)), Unbox (f (CostMCF c)), Ord (f (CostMCF c)), PrimMonad m, Num c, Unbox c, Ord c) => (CostMCF c -> f (CostMCF c)) -> Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m ((f (CostMCF c), CapacityMCF c), MinCostFlow (PrimState m) c)
bestFlow :: (Monoid (f (CostMCF c)), Unbox (f (CostMCF c)), Ord (f (CostMCF c)), Num (f (CostMCF c)), Unbox c, Integral c) => (CostMCF c -> f (CostMCF c)) -> Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> (f (CostMCF c), CapacityMCF c)
minCostFlow :: (Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> (Min (CostMCF c), CapacityMCF c)
minCostFlow' :: (PrimMonad m, Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m ((Min (CostMCF c), CapacityMCF c), MinCostFlow (PrimState m) c)
maxCostFlow :: (Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> (Max (CostMCF c), CapacityMCF c)
maxCostFlow' :: (PrimMonad m, Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m ((Max (CostMCF c), CapacityMCF c), MinCostFlow (PrimState m) c)
edgesMCF :: (PrimMonad m, Num c, Unbox c) => MinCostFlow (PrimState m) c -> m (Vector (Int, Int, CapacityMCF c, FlowMCF c, CostMCF c))
undefMCF :: Int
buildMinCostFlow :: forall c m. (PrimMonad m, Num c, Unbox c, Ord c) => Int -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m (MinCostFlow (PrimState m) c)
runMinCostFlow :: forall f c m. (Monoid (f (CostMCF c)), Unbox (f (CostMCF c)), Ord (f (CostMCF c)), Num (f (CostMCF c)), PrimMonad m, Num c, Unbox c, Ord c) => (CostMCF c -> f (CostMCF c)) -> Vertex -> Vertex -> FlowMCF c -> MinCostFlow (PrimState m) c -> m (f (CostMCF c), CapacityMCF c)
runMinCostFlowShortests :: (Unbox (f (CostMCF c)), Monoid (f (CostMCF c)), Ord (f (CostMCF c)), Num (f (CostMCF c)), Unbox c, Num c, Ord c, PrimMonad m) => (CostMCF c -> f (CostMCF c)) -> Vertex -> MinCostFlow (PrimState m) c -> MinCostFlowBuffer (f (CostMCF c)) (PrimState m) c -> m ()

Documentation

type CapacityMCF c = c #

type FlowMCF c = c #

type CostMCF c = c #

data MinCostFlow s c #

The state for CostFlow

Internals

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

Constructors

MinCostFlow

Fields

nVertsMCF :: !Int
nEdgesMCF :: !Int
offsetsMCF :: !(Vector Int)
Source vertex -> initial edge index. Note that edges are sorted by the starting vertex.
edgeDstMCF :: !(Vector Int)
Edge index -> destination vertex.
edgeRevIndexMCF :: !(Vector Int)
Edge index -> reverse edge index.
edgeCapMCF :: !(MVector s (CapacityMCF c))
Edge index -> residual edge capacity.
edgeCostMCF :: !(Vector (CostMCF c))
Edge index -> cost

data MinCostFlowBuffer r s c #

Mutable states on running MinCostFlow algorithm.

Constructors

MinCostFlowBuffer
Fields distsMCF :: !(MVector s r) Vertex -> shortest wrapped cost (Bellman-Ford result) prevVertMCF :: !(MVector s Vertex) Vertex -> shortest distance + last vertex prevEdgeMCF :: !(MVector s EdgeId) Vertex -> shortest distance + last edge

bestFlow' :: (Num (f (CostMCF c)), Monoid (f (CostMCF c)), Unbox (f (CostMCF c)), Ord (f (CostMCF c)), PrimMonad m, Num c, Unbox c, Ord c) => (CostMCF c -> f (CostMCF c)) -> Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m ((f (CostMCF c), CapacityMCF c), MinCostFlow (PrimState m) c) #

Returns the wrapped cost for getting the target flow, or Nothing when impossible. Be warned that it attampts to maximize the flow (up to the target flow) even if the best result is with smaller flow. Make a bipassing edge!

bestFlow :: (Monoid (f (CostMCF c)), Unbox (f (CostMCF c)), Ord (f (CostMCF c)), Num (f (CostMCF c)), Unbox c, Integral c) => (CostMCF c -> f (CostMCF c)) -> Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> (f (CostMCF c), CapacityMCF c) #

minCostFlow :: (Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> (Min (CostMCF c), CapacityMCF c) #

Returns (minCost, flow). REMARK: Invalid (negative cost) edges should not be filtered. Instead, use them as zero-cost edges (or else we can't retrieve the best solution (at least in the current implementation)

minCostFlow' :: (PrimMonad m, Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m ((Min (CostMCF c), CapacityMCF c), MinCostFlow (PrimState m) c) #

maxCostFlow :: (Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> (Max (CostMCF c), CapacityMCF c) #

Returns (maxCost, flow). REMARK: Invalid (negative cost) edges should not be filtered. Instead, use them as zero-cost edges (or else we can't retrieve the best solution (at least in the current implementation)

maxCostFlow' :: (PrimMonad m, Unbox c, Integral c, Bounded c) => Int -> Int -> Int -> CapacityMCF c -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m ((Max (CostMCF c), CapacityMCF c), MinCostFlow (PrimState m) c) #

edgesMCF :: (PrimMonad m, Num c, Unbox c) => MinCostFlow (PrimState m) c -> m (Vector (Int, Int, CapacityMCF c, FlowMCF c, CostMCF c)) #

Retrieves edge information (v1, v2, cap, flow, cost) from the maxFlow results.

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

undefMCF :: Int #

For vertices and edge indices?

buildMinCostFlow :: forall c m. (PrimMonad m, Num c, Unbox c, Ord c) => Int -> Vector (Vertex, Vertex, CapacityMCF c, CostMCF c) -> m (MinCostFlow (PrimState m) c) #

Builds MinCostFlow from edges.

runMinCostFlow :: forall f c m. (Monoid (f (CostMCF c)), Unbox (f (CostMCF c)), Ord (f (CostMCF c)), Num (f (CostMCF c)), PrimMonad m, Num c, Unbox c, Ord c) => (CostMCF c -> f (CostMCF c)) -> Vertex -> Vertex -> FlowMCF c -> MinCostFlow (PrimState m) c -> m (f (CostMCF c), CapacityMCF c) #

Runs the MinCostFlow algorithm.

runMinCostFlowShortests :: (Unbox (f (CostMCF c)), Monoid (f (CostMCF c)), Ord (f (CostMCF c)), Num (f (CostMCF c)), Unbox c, Num c, Ord c, PrimMonad m) => (CostMCF c -> f (CostMCF c)) -> Vertex -> MinCostFlow (PrimState m) c -> MinCostFlowBuffer (f (CostMCF c)) (PrimState m) c -> m () #

Collect shortest distances from the source vertex using Bellman-Ford algorithm.

Panics on negative loop.

TODO: replace with dijkstra with potencials.