| |||||||||||||||

| |||||||||||||||

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 | |||||||||||||||

| |||||||||||||||

Documentation | |||||||||||||||

getRevEdges :: (Num b, Ord b) => [(Node, Node)] -> [(Node, Node, b)] | |||||||||||||||

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, Ord b) => gr a b -> gr a (b, b, b) | |||||||||||||||

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, Ord b) => [((b, b, b), Node)] -> Node -> b -> Bool -> [((b, b, b), Node)] | |||||||||||||||

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, Ord b) => Path -> b -> gr a (b, b, b) -> gr a (b, b, b) | |||||||||||||||

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) | |||||||||||||||

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) | |||||||||||||||

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 grap 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) | |||||||||||||||

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 grap whose edges are labeled with (y,x) = (current flow, max capacity). | |||||||||||||||

maxFlow :: (DynGraph gr, Num b, Ord b) => gr a b -> Node -> Node -> b | |||||||||||||||

Compute the value of a maximumflow | |||||||||||||||

Produced by Haddock version 0.8 |