Safe Haskell | Safe |
---|---|

Language | Haskell98 |

Maximum Flow algorithm

We are given a flow network `G=(V,E)`

with source `s`

and sink `t`

where each edge `(u,v)`

in `E`

has a nonnegative capacity
`c(u,v)>=0`

, and we wish to find a flow of maximum value from `s`

to `t`

.

A flow in `G=(V,E)`

is a real-valued function `f:VxV->R`

that
satisfies:

For all u,v in V, f(u,v)<=c(u,v) For all u,v in V, f(u,v)=-f(v,u) For all u in V-{s,t}, Sum{f(u,v):v in V } = 0

The value of a flow f is defined as `|f|=Sum {f(s,v)|v in V}`

, i.e.,
the total net flow out of the source.

In this module we implement the Edmonds-Karp algorithm, which is
the Ford-Fulkerson method but using the shortest path from `s`

to
`t`

as the augmenting path along which the flow is incremented.

## Synopsis

- getRevEdges :: Num b => [Edge] -> [LEdge b]
- augmentGraph :: (DynGraph gr, Num b) => gr a b -> gr a (b, b, b)
- updAdjList :: Num b => Adj (b, b, b) -> Node -> b -> Bool -> Adj (b, b, b)
- updateFlow :: (DynGraph gr, Num b) => Path -> b -> gr a (b, b, b) -> gr a (b, b, b)
- mfmg :: (DynGraph gr, Num b, Ord b) => gr a (b, b, b) -> Node -> Node -> gr a (b, b, b)
- mf :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b, b)
- maxFlowgraph :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b)
- maxFlow :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> b

# Documentation

getRevEdges :: Num b => [Edge] -> [LEdge b] Source #

i 0 For each edge a--->b this function returns edge b--->a . i Edges a<--->b are ignored j

augmentGraph :: (DynGraph gr, Num b) => gr a b -> gr a (b, b, b) Source #

i 0 For each edge a--->b insert into graph the edge a<---b . Then change the i (i,0,i) label of every edge from a---->b to a------->b

where label (x,y,z)=(Max Capacity, Current flow, Residual capacity)

updAdjList :: Num b => Adj (b, b, b) -> Node -> b -> Bool -> Adj (b, b, b) Source #

Given a successor or predecessor list for node `u`

and given node `v`

, find
the label corresponding to edge `(u,v)`

and update the flow and
residual capacity of that edge's label. Then return the updated
list.

updateFlow :: (DynGraph gr, Num b) => Path -> b -> gr a (b, b, b) -> gr a (b, b, b) Source #

Update flow and residual capacity along augmenting path from `s`

to `t`

in
graph @`G. For a path `

[u,v,w,...]` find the node `

u` in `

G```
and
its successor and predecessor list, then update the corresponding
edges
```

(u,v)` and `

(v,u)@ on those lists by using the minimum
residual capacity of the path.

mfmg :: (DynGraph gr, Num b, Ord b) => gr a (b, b, b) -> Node -> Node -> gr a (b, b, b) Source #

Compute the flow from `s`

to `t`

on a graph whose edges are labeled with
`(x,y,z)=(max capacity,current flow,residual capacity)`

and all
edges are of the form `a<---->b`

. First compute the residual
graph, that is, delete those edges whose residual capacity is
zero. Then compute the shortest augmenting path from `s`

to `t`

,
and finally update the flow and residual capacity along that path
by using the minimum capacity of that path. Repeat this process
until no shortest path from `s`

to `t`

exist.

mf :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b, b) Source #

Compute the flow from s to t on a graph whose edges are labeled with
`x`

, which is the max capacity and where not all edges need to be
of the form a<---->b. Return the flow as a graph whose edges are
labeled with (x,y,z)=(max capacity,current flow,residual
capacity) and all edges are of the form a<---->b

maxFlowgraph :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> gr a (b, b) Source #

Compute the maximum flow from s to t on a graph whose edges are labeled with x, which is the max capacity and where not all edges need to be of the form a<---->b. Return the flow as a graph whose edges are labeled with (y,x) = (current flow, max capacity).