tag:blogger.com,1999:blog-786333285568106173.post8782972098907906605..comments2023-06-06T10:41:49.490-04:00Comments on WebDiarios de Motocicleta: Puzzle: Cycle Containing Two NodesMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-786333285568106173.post-36887782062458397272009-04-08T21:54:00.000-04:002009-04-08T21:54:00.000-04:00PS: You should really implement this (I did it in ...PS: You should really implement this (I did it in 98 or so). You will understand these technical details much better when you need to think of them carefully.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-10519101220709450122009-04-08T21:53:00.000-04:002009-04-08T21:53:00.000-04:00Ok, I think I understand your problem: you may get...Ok, I think I understand your problem: you may get a flow plus a circulation, instead of just a flow.<BR/><BR/>0) Recap your lectures on flow :) These things have fairly standard fixes.<BR/><BR/>1) You can avoid the extra circulation by implementing your flow carefully. More precisely, the back edges in the residual graph should have priority in your 2nd run of DFS (this way, if there is a path going back on some edges, you will go back in a contiguous way, not hop on and off the back path).<BR/><BR/>2) Otherwise, you can easily get rid of the extra circulation. In the node-capacitated case, just keep the edges with nonzero flow that are in the same connected component with the source and sink. <BR/><BR/>Without node capacities, do two DFS from the source to the sink, staying only on edges with nonzero flow. The 2nd scan cannot get stuck, by flow conservation (what comes in must go out).Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-87444980769218031702009-04-08T19:17:00.000-04:002009-04-08T19:17:00.000-04:00Ok, so let's look at your directed network (assume...Ok, so let's look at your directed network (assume no node capacities for the moment).<BR/><BR/>Say you find a flow given by two paths v, v_1, v_2, ..., v_k, u <BR/><BR/>and v, w_1, w_2, ..., v_7, v_6, ..., v_3, v_2, ..., v_10, v_9, ..., w_l, u.<BR/><BR/>What next?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6771569896474634892009-04-07T17:31:00.000-04:002009-04-07T17:31:00.000-04:00Dude, you shouldn't run flow on the undirected gra...Dude, you shouldn't run flow on the undirected graph if you want to add node capacities. Every node v is split into v1 and v2; all edge have a version coming into v1 and one going out of v2. There is a single edge between v1 and v2 with the capacity of the node. The residual network is just what the residual network is.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-56199674615586781762009-04-07T17:09:00.000-04:002009-04-07T17:09:00.000-04:00Just define it. Let's say I have G=(V_G,E_G) undir...Just define it. Let's say I have G=(V_G,E_G) undirected, with capacities u_G, and a flow x on it. What exactly is R=(V_R, E_R), and what are the capacities u_R?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-18674286170771909342009-04-07T12:34:00.000-04:002009-04-07T12:34:00.000-04:00What's wrong with the residual network for an undi...What's wrong with the residual network for an undirected node-capacitated graph? It seems like a perfectly healthy creature to me. It's of course a directed graph.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-60365349701243877322009-04-07T04:46:00.000-04:002009-04-07T04:46:00.000-04:00This comment has been removed by the author.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-60996863298066480062009-04-07T01:53:00.000-04:002009-04-07T01:53:00.000-04:00Mihai, how do you define the residual graph for a ...Mihai, how do you define the residual graph for a flow problem with node capacities in an *undirected* graph? <BR/><BR/>Just trying to see if you are an mathematician, or a mere algorithmist. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-83291498793962769172009-04-07T01:23:00.000-04:002009-04-07T01:23:00.000-04:00An interesting variant would be find such a cycle ...<I>An interesting variant would be find such a cycle in a directed graph.</I><BR/><BR/>But that is simply DFS, no?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-71140442396221500442009-04-07T00:40:00.000-04:002009-04-07T00:40:00.000-04:00An interesting variant would be find such a cycle ...An interesting variant would be find such a cycle in a directed graph.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-35769965637434490902009-04-06T13:12:00.000-04:002009-04-06T13:12:00.000-04:00Do you want edge-disjoint/node-disjoint cycles?Doe...<I>Do you want edge-disjoint/node-disjoint cycles?</I><BR/><BR/>Doesn't matter, both have an O(m) solution.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-39658557883123863372009-04-06T10:14:00.000-04:002009-04-06T10:14:00.000-04:00Do you want edge-disjoint/node-disjoint cycles?Do you want edge-disjoint/node-disjoint cycles?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-86069516650519358052009-04-06T07:31:00.000-04:002009-04-06T07:31:00.000-04:00i was anon 2, who MISREAD.corrected solution--DFS ...i was anon 2, who MISREAD.<BR/><BR/>corrected solution--DFS from u, backtrack after hitting v (through parents in tree) to find a u--v path. cut this path's edges from the graph, and DFS to find another path. works since undirected graph has cycle iff has pair of paths.<BR/><BR/>the 2-flow idea works too, in fact it'll do what i wrote (find a path, mark it as used, find another).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-79885994440420332552009-04-06T06:10:00.000-04:002009-04-06T06:10:00.000-04:00It seems to be straightforward flow with value 2. ...It seems to be straightforward flow with value 2. Am I right?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-78423198029816127942009-04-06T05:58:00.000-04:002009-04-06T05:58:00.000-04:00yeah just backtrack through parents in DFS tree if...yeah just backtrack through parents in DFS tree if v hit; if v not hit, no cycle. DFS times O(m), backtrack time O(m).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90475969648152182432009-04-06T02:56:00.000-04:002009-04-06T02:56:00.000-04:00single DFS from u. there is a cycle iff there is a...single DFS from u. there is a cycle iff there is a whitepath to u from a node in the subtree of v.Anonymousnoreply@blogger.com