{"id":2935,"date":"2015-04-03T14:00:07","date_gmt":"2015-04-03T18:00:07","guid":{"rendered":"http:\/\/www.acarlstein.com\/?p=2935"},"modified":"2015-04-03T15:00:08","modified_gmt":"2015-04-03T19:00:08","slug":"ford-fulkerson-method","status":"publish","type":"post","link":"http:\/\/blog.acarlstein.com\/?p=2935","title":{"rendered":"Ford-Fulkerson Method"},"content":{"rendered":"<p><strong>Facts<\/strong><\/p>\n<ul>\n<li>The Ford-Fulkerson method\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?(G,S,t)\" alt=\"(G,S,t)\" align=\"absmiddle\" \/> is iterative<\/li>\n<li>This method depends on three ideas:\n<ul>\n<li>Augmenting paths<\/li>\n<li>Residual networks<\/li>\n<li>Cuts<\/li>\n<\/ul>\n<\/li>\n<li>Simplified Pseudo-code:\n<pre>initialize flow f to 0\r\nwhile there exist an augmenting path p\r\n    do augmented flow f along p\r\nreturn f<\/pre>\n<\/li>\n<\/ul>\n<p><span style=\"text-decoration: underline;\"><a id=\"AugmentingPaths\"><\/a>Augmenting Paths<\/span><\/p>\n<ul>\n<li>An augmenting path <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?p\" alt=\"p\" align=\"absmiddle\" \/> is a simple path from source <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?S\" alt=\"S\" align=\"absmiddle\" \/> to sing <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?t\" alt=\"t\" align=\"absmiddle\" \/> in the <a href=\"#ResidualNetworks\">residual network<\/a><\/li>\n<li>Each path have alternative free and matched edges in such way that begins and ends with free vertices.<\/li>\n<\/ul>\n<p><span style=\"text-decoration: underline;\"><a id=\"ResidualNetwork\"><\/a>Residual networks<\/span><\/p>\n<ul>\n<li>Definition: Each edge <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?(u,v)\" alt=\"(u,v)\" align=\"absmiddle\" \/> on an <a href=\"#AugmentingPaths\">augmenting path<\/a> admits some additional positive flow\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?u\" alt=\"u\" align=\"absmiddle\" \/> to\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?v\" alt=\"v\" align=\"absmiddle\" \/> without violating the capacity constrain on the edge.<br \/>\n<a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_fulkerson_Residual_Flow.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-2945\" src=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_fulkerson_Residual_Flow.jpg\" alt=\"Ford_fulkerson_Residual_Flow\" width=\"296\" height=\"380\" srcset=\"http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/Ford_fulkerson_Residual_Flow.jpg 296w, http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/Ford_fulkerson_Residual_Flow-234x300.jpg 234w\" sizes=\"auto, (max-width: 296px) 100vw, 296px\" \/><\/a><\/li>\n<li>Example:<br \/>\n<a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Transformation.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-2947\" src=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Transformation.jpg\" alt=\"Ford_Fulkerson_Transformation\" width=\"353\" height=\"478\" srcset=\"http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Transformation.jpg 353w, http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Transformation-222x300.jpg 222w\" sizes=\"auto, (max-width: 353px) 100vw, 353px\" \/><\/a><\/li>\n<\/ul>\n<p><span style=\"text-decoration: underline;\">Cuts<\/span><\/p>\n<ul>\n<li>Minimum cut of a network: A cut whose capacity is minimum over all cuts on the network.<\/li>\n<li>Max-flow min-cut theorem: A flow is maximum if and only if its residual network contains no augmenting path.<\/li>\n<li>Example: <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?cut(\\{S,&amp;space;v_{1},&amp;space;v_{2}\\}),&amp;space;\\{v_{3},&amp;space;v_{4},&amp;space;t\\})\" alt=\"cut(\\{S, v_{1}, v_{2}\\}), \\{v_{3}, v_{4}, t\\})\" align=\"absmiddle\" \/><a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Cut.jpg\"><br \/>\n<\/a><a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Cut1.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-2943 size-full\" src=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Cut1.jpg\" alt=\"\" width=\"348\" height=\"257\" srcset=\"http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Cut1.jpg 348w, http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Cut1-300x222.jpg 300w\" sizes=\"auto, (max-width: 348px) 100vw, 348px\" \/><\/a><a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/Ford_Fulkerson_Cut.jpg\"><span style=\"color: #000000;\">Net-flow Across Cut (including net-flow between vertices): <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f(v_{1},&amp;space;v_{3})&amp;space;+&amp;space;f(v_{2},v_{3})&amp;space;+&amp;space;f(v_{2},&amp;space;v_{4})&amp;space;=&amp;space;14&amp;space;+&amp;space;(-4)&amp;space;+&amp;space;11&amp;space;=&amp;space;19\" alt=\"f(v_{1}, v_{3}) + f(v_{2},v_{3}) + f(v_{2}, v_{4}) = 14 + (-4) + 11 = 19\" align=\"absmiddle\" \/><\/span><\/a><br \/>\nCapacity (only edges going from source <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?S\" alt=\"S\" align=\"absmiddle\" \/> to sink <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?t\" alt=\"t\" align=\"absmiddle\" \/>): <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c(v_{1},&amp;space;v_{3})&amp;space;+&amp;space;c(v_{2},&amp;space;v_{4})&amp;space;=&amp;space;12&amp;space;+&amp;space;14&amp;space;=&amp;space;26\" alt=\"c(v_{1}, v_{3}) + c(v_{2}, v_{4}) = 12 + 14 = 26\" align=\"absmiddle\" \/><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Pseudocode<\/strong><\/p>\n<p>\/\/ Comments<br \/>\nFord-Fulkerson <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?(G,S,t)\" alt=\"(G,S,t)\" align=\"absmiddle\" \/><br \/>\n<span style=\"padding-left: 2em;\">for each edge <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?(u,v)\\epsilon&amp;amp;space;E[G]\" alt=\"(u,v)\\epsilon E[G]\" align=\"absmiddle\" \/><\/span><br \/>\n<span style=\"padding-left: 4em;\">do <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f[u,v]\\leftarrow&amp;amp;space;0\" alt=\"f[u,v]\\leftarrow 0\" align=\"absmiddle\" \/> \/\/ <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f\" alt=\"f\" align=\"absmiddle\" \/>:flow<\/span><br \/>\n<span style=\"padding-left: 4em;\">do <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f[v,u]\\leftarrow&amp;amp;space;0\" alt=\"f[v,u]\\leftarrow 0\" align=\"absmiddle\" \/><\/span><br \/>\n<span style=\"padding-left: 4em;\">while there exist a path <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?p\" alt=\"p\" align=\"absmiddle\" \/> from <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?S\" alt=\"S\" align=\"absmiddle\" \/> to <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?t\" alt=\"t\" align=\"absmiddle\" \/> in the residual network <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?Gf\" alt=\"Gf\" align=\"absmiddle\" \/><\/span><br \/>\n<span style=\"padding-left: 6em;\">do <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?cf(p)\\leftarrow&amp;amp;space;min\\{cf(u,v):&amp;amp;space;(u,v)\" alt=\"cf(p)\\leftarrow min\\{cf(u,v): (u,v)\" align=\"absmiddle\" \/> is in <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?p&amp;amp;space;\\}\" alt=\"p \\}\" align=\"absmiddle\" \/> \/\/ <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?cf\" alt=\"cf\" align=\"absmiddle\" \/>: residual capacity<\/span><br \/>\n<span style=\"padding-left: 6em;\">for each edge <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?(u,v)\" alt=\"(u,v)\" align=\"absmiddle\" \/> in <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?p\" alt=\"p\" align=\"absmiddle\" \/><\/span><br \/>\n<span style=\"padding-left: 8em;\">do <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f[u,v]\\leftarrow&amp;amp;space;f[u,v]+cf(p)\" alt=\"f[u,v]\\leftarrow f[u,v]+cf(p)\" align=\"absmiddle\" \/> \/\/ <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?p\" alt=\"p\" align=\"absmiddle\" \/>: path<\/span><br \/>\n<span style=\"padding-left: 8em;\">do <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f[v,u]\\leftarrow&amp;space;-f[u,v]\" alt=\"f[v,u]\\leftarrow -f[u,v]\" align=\"absmiddle\" \/><\/span><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Big O<\/strong><\/p>\n<p>Using either dept-first search or breadth-first search, the time to find a path in a residual network is <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?O(V+E')&amp;space;=&amp;space;O(E)\" alt=\"O(V+E') = O(E)\" align=\"absmiddle\" \/><\/p>\n<p>Total running time is <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?O(E|F*|)\" alt=\"O(E|F*|)\" align=\"absmiddle\" \/> where <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?f*\" alt=\"f*\" align=\"absmiddle\" \/> is the maximum flow found<\/p>\n<p>&nbsp;<\/p>\n<p><em>Note: If you find any mistake please let me know<\/em><\/p>\n\n<script>\nvar zbPregResult = '0';\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Facts The Ford-Fulkerson method\u00a0 is iterative This method depends on three ideas: Augmenting paths Residual networks Cuts Simplified Pseudo-code: initialize flow f to 0 while there exist an augmenting path p do augmented flow f along p return f Augmenting Paths An augmenting path is a simple path from source to sing in the residual [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,218],"tags":[1277,1273,1275,1276,919,1269,1270,1271,934,1274,265,225,1272],"class_list":["post-2935","post","type-post","status-publish","format-standard","hentry","category-programming","category-algorithms-programming","tag-breadth-first","tag-capacity","tag-cut","tag-depth-first","tag-flow","tag-ford","tag-fulkerson","tag-maximum","tag-method","tag-netflow","tag-network","tag-path","tag-residual"],"_links":{"self":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2935","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2935"}],"version-history":[{"count":11,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2935\/revisions"}],"predecessor-version":[{"id":2952,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2935\/revisions\/2952"}],"wp:attachment":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2935"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2935"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2935"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}