<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!--Rendered using the Haskell Html Library v0.2-->
<HTML
><HEAD
><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"
><TITLE
>Data.Graph.Inductive.Query.MaxFlow</TITLE
><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"
><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"
></SCRIPT
><SCRIPT TYPE="text/javascript"
>window.onload = function () {setSynopsis("mini_Data-Graph-Inductive-Query-MaxFlow.html")};</SCRIPT
></HEAD
><BODY
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="topbar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
></TD
><TD CLASS="title"
>fgl-5.4.2.3: Martin Erwig's Functional Graph Library</TD
><TD CLASS="topbut"
><A HREF="index.html"
>Contents</A
></TD
><TD CLASS="topbut"
><A HREF="doc-index.html"
>Index</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="modulebar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><FONT SIZE="6"
>Data.Graph.Inductive.Query.MaxFlow</FONT
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Description</TD
></TR
><TR
><TD CLASS="doc"
><P
>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.
</P
><P
>A flow in G=(V,E) is a real-valued function f:VxV->R that satisfies:
</P
><PRE
>
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
</PRE
><P
>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.
</P
><P
>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.
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Synopsis</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A HREF="#v%3AgetRevEdges"
>getRevEdges</A
> :: (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => [(<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>, <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>)] -> [(<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>, <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>, b)]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AaugmentGraph"
>augmentGraph</A
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdAdjList"
>updAdjList</A
> :: (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => [((b, b, b), <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>)] -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool"
>Bool</A
> -> [((b, b, b), <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>)]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AupdateFlow"
>updateFlow</A
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => <A HREF="Data-Graph-Inductive-Graph.html#t%3APath"
>Path</A
> -> b -> gr a (b, b, b) -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Amfmg"
>mfmg</A
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a (b, b, b) -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Amf"
>mf</A
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmaxFlowgraph"
>maxFlowgraph</A
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> gr a (b, b)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmaxFlow"
>maxFlow</A
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> b</TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Documentation</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:getRevEdges"
><A NAME="v%3AgetRevEdges"
></A
></A
><B
>getRevEdges</B
> :: (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => [(<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>, <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>)] -> [(<A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>, <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>, b)]</TD
></TR
><TR
><TD CLASS="doc"
><PRE
>
i 0
For each edge a--->b this function returns edge b--->a .
i
Edges a<--->b are ignored
j
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:augmentGraph"
><A NAME="v%3AaugmentGraph"
></A
></A
><B
>augmentGraph</B
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="doc"
><PRE
>
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
</PRE
><P
>where label (x,y,z)=(Max Capacity, Current flow, Residual capacity)
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updAdjList"
><A NAME="v%3AupdAdjList"
></A
></A
><B
>updAdjList</B
> :: (<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => [((b, b, b), <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>)] -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> b -> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool"
>Bool</A
> -> [((b, b, b), <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
>)]</TD
></TR
><TR
><TD CLASS="doc"
>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.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:updateFlow"
><A NAME="v%3AupdateFlow"
></A
></A
><B
>updateFlow</B
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => <A HREF="Data-Graph-Inductive-Graph.html#t%3APath"
>Path</A
> -> b -> gr a (b, b, b) -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="doc"
>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.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mfmg"
><A NAME="v%3Amfmg"
></A
></A
><B
>mfmg</B
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a (b, b, b) -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="doc"
>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.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mf"
><A NAME="v%3Amf"
></A
></A
><B
>mf</B
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> gr a (b, b, b)</TD
></TR
><TR
><TD CLASS="doc"
>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
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:maxFlowgraph"
><A NAME="v%3AmaxFlowgraph"
></A
></A
><B
>maxFlowgraph</B
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> gr a (b, b)</TD
></TR
><TR
><TD CLASS="doc"
>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).
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:maxFlow"
><A NAME="v%3AmaxFlow"
></A
></A
><B
>maxFlow</B
> :: (<A HREF="Data-Graph-Inductive-Graph.html#t%3ADynGraph"
>DynGraph</A
> gr, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Prelude.html#t%3ANum"
>Num</A
> b, <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => gr a b -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> <A HREF="Data-Graph-Inductive-Graph.html#t%3ANode"
>Node</A
> -> b</TD
></TR
><TR
><TD CLASS="doc"
>Compute the value of a maximumflow
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="botbar"
>Produced by <A HREF="http://www.haskell.org/haddock/"
>Haddock</A
> version 2.6.1</TD
></TR
></TABLE
></BODY
></HTML
>
