| Safe Haskell | Safe |
|---|---|
| Language | Haskell98 |
Data.Graph.Inductive.Query.MaxFlow
Description
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).