tag:blogger.com,1999:blog-4195135246107166251.post9207890879544479903..comments2017-06-28T13:26:58.724-07:00Comments on Neopythonic: Detecting Cycles in a Directed GraphGuido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-4195135246107166251.post-51736259506829525062013-05-26T03:40:18.966-07:002013-05-26T03:40:18.966-07:00Some literatur:
K.A.HawickandH.A.James,
Enumerat...Some literatur:<br /><br />K.A.HawickandH.A.James, <br />EnumeratingCircuitsandLoopsinGraphswithSelf-ArcsandMultiple-Arcsfeffe81https://www.blogger.com/profile/15222716677682195926noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-78919124289130039822013-03-01T09:30:01.452-08:002013-03-01T09:30:01.452-08:00Here's Peter's version: https://www.dropbo...Here's Peter's version: https://www.dropbox.com/s/s0hc6jr47hmoitf/find_cycle_norvig.py (He posted it here but the indentation was all messed up.)Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-34374575612862362922013-02-28T21:55:43.976-08:002013-02-28T21:55:43.976-08:00Here's my version using OrderedDict -- O(1) me...Here's my version using OrderedDict -- O(1) membership, and no ned to re-generate links.<br /><br />def find_cycle(nodes, links):<br /> """Given a set of nodes, and a function links(node) => [child, ...], return<br /> a path of nodes that forms a cycle, or None if there is no cycle. Example:<br /> >>> find_cycle(range(10), lambda x: [x+1, (x+2)%10])<br /> [9, 1, 3, 5, 7, 9]<br /> """<br /> # Adapted from a blog post by Guido:<br /> # http://neopythonic.blogspot.com/2009/01/detecting-cycles-in-directed-graph.html<br /> # Maintain path as a a depth-first path in the implicit tree; <br /> # path is represented as an OrderedDict of {node: [child,...]} pairs.<br /> while nodes:<br /> root = nodes.pop()<br /> path = OrderedDict({root: links(root)})<br /> while path:<br /> # Consider the children at the fringe of the tree<br /> children = path[next(reversed(path))]<br /> while children:<br /> child = children.pop()<br /> if child in path: ## Cycle found<br /> pathlist = list(path)<br /> return pathlist[pathlist.index(child):] + [child]<br /> if child in nodes: ## New child not seen before<br /> path[child] = links(child)<br /> nodes.remove(child)<br /> break<br /> else: ## no more children; pop back up a level<br /> path.popitem()<br /> return NonePeter Norvighttps://www.blogger.com/profile/04019538682957797752noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-5671578487725078552013-02-28T21:29:41.597-08:002013-02-28T21:29:41.597-08:00I just got an email fro Peter Norvig pointing out ...I just got an email fro Peter Norvig pointing out that the efficiency of the algorithm can be fixed by using an OrderedDict. Nice!Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-33590416256311656272012-04-12T11:55:31.028-07:002012-04-12T11:55:31.028-07:00I don't think Guido's definition is that i...I don't think Guido's definition is that it will call READY() on all nodes that aren't in a cycle before returning a cycle that exists, or None. From a quick look, whether some get passed to READY() before the first cycle is spotted depends. Break you cycle and then see if READY() is being called.Anonymoushttps://www.blogger.com/profile/13140975971019765573noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-29244094867953616102012-04-12T11:00:39.755-07:002012-04-12T11:00:39.755-07:00What is the definition of a node that is READY? P...What is the definition of a node that is READY? Playing with some cycles, it isn't quite obvious to me.<br /><br /># aren't d and e not part of a cycle?<br />graph = { 'a': ['b', 'c'], <br /> 'b': ['c'], <br /> 'c': ['a'], # cycle <br /> 'd': ['e',], <br /> 'e': [], <br /> } <br /> <br />def ready(node): <br /> print "node %s is not in a cycle" % node <br /> <br />def nodes(): <br /> """ Return all of the nodes """ <br /> return graph.keys() <br /> <br />def edges(node): <br /> """ Return the children of node """ <br /> return graph[node] <br /> <br />cycles = find_cycle(nodes, edges, ready) <br /> <br />print "cycles: %s" % cycles<br /><br />$ ./cycle.py <br />cycles: ['a', 'b', 'c']Anonymoushttps://www.blogger.com/profile/08943774697145664628noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-24786810313039861872010-08-27T21:55:55.013-07:002010-08-27T21:55:55.013-07:00sorry.what we want is not present here.we want the...sorry.what we want is not present here.we want the efficient algorithm to find out loop in a directed graph.Unknownhttps://www.blogger.com/profile/05498103849692665211noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-88954741524677972872009-03-17T09:50:00.000-07:002009-03-17T09:50:00.000-07:00It is interesting discussion. I am also looking fo...It is interesting discussion. I am also looking for an algorithm to find cycles + loop from directed graph possibly with linear complexity. This discussion gives me some idea. I will post which method I choose later<BR/>AbrehetAbrehethttps://www.blogger.com/profile/06808638223687683921noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-86593573287550410602009-03-06T11:48:00.000-08:002009-03-06T11:48:00.000-08:00> Why the uppercased NODES, EDGES, and READY?I ...> Why the uppercased NODES, EDGES, and READY?<BR/><BR/>I was trying to emphasize the algorithm. These three parametrize the algorithm, and I felt the need to call them out. Any realistic implementation would not use functions but expand these in-line according to the needs of the application. So you can think of them as template parameters or macros. :-)Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-15975383186827182912009-02-25T08:12:00.000-08:002009-02-25T08:12:00.000-08:00Why the uppercased NODES, EDGES, and READY? Don't...Why the uppercased NODES, EDGES, and READY? Don't want to be a hobgoblin, and I'm not, I prefer `my' to `self', but PEP 8 exists. :-)Anonymoushttps://www.blogger.com/profile/13140975971019765573noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-90127654123067971562009-02-12T14:28:00.000-08:002009-02-12T14:28:00.000-08:00I'm going to be off topic for which I apologize, b...I'm going to be off topic for which I apologize, but the bit of code here reminded me of something I was curious about earlier.<BR/><BR/>Is the 2 space indentation part of an internal Google coding guideline? I first noticed it in the app engine SDK. It seems all Python code coming out of Google shares this trait.<BR/><BR/>Just curious.. and sorry to get off topic. :D<BR/><BR/>Thank you for starting the history of Python blog. I find it fascinating and look forward to reading the next post.Samuelhttps://www.blogger.com/profile/17533713217663530422noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-38927113669280913902009-02-09T13:59:00.000-08:002009-02-09T13:59:00.000-08:00your code is similar to something i used just the ...your code is similar to something i used just the other day - it's basically your routine (i assume - i've not read it in detail, but assume it's dfs checking for duplicates) turned into a generator for edges: http://www.ics.uci.edu/~eppstein/PADS/DFS.py<BR/><BR/>in your case i think you'd just filter for the nontree nodes.Unknownhttps://www.blogger.com/profile/02499827660415185543noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-17255274589839152742009-01-30T21:15:00.000-08:002009-01-30T21:15:00.000-08:00@lorg: (a) It's not so much the limited scope of m...@lorg: (a) It's not so much the limited scope of my problem but the fact that the algorithm is really only a small part of much more complex code I am writing anyway. (It's less than 20 lines!)<BR/><BR/>(b) Loops are runtime cycles, not compile-time cycles. My edges are dependencies between variable and function definitions, not between values. Eventually I will have to deal with recursive function definitions, but then I'll somehow have to break those cycles since I don't want to deal with cyclical definitions.Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-34257693297181914712009-01-30T13:50:00.000-08:002009-01-30T13:50:00.000-08:00@Guido:1. Even when your problem is more limited i...@Guido:<BR/>1. Even when your problem is more limited in scope, I find using existing libraries is best. (Especially since finding strongly connected parts is O(V+E) (DFS twice), and any algorithm to prove that there aren't any cycles could not be better in this regard.)<BR/><BR/>2. Your programs don't have loops? Care to elaborate, or is this a future blog post? :)lorghttps://www.blogger.com/profile/10081475780192298906noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-26043280717551549852009-01-30T10:46:00.000-08:002009-01-30T10:46:00.000-08:00I had this problem way back in schooldays, I resol...I had this problem way back in schooldays, I resolved it (in Fortran...) like this :<BR/><BR/>Another way to see the problem is through node activation, which results in matrix/vector multiplication. <BR/><BR/>"Activate" each node. <BR/><BR/>Iterate :<BR/>On each iteration, each node will activate its descendents and desactivate itself, and keep being activated only if one of its predecessors do activate it (see it as a flow of information that nodes push into their children). <BR/><BR/>After n iterations, if any node is still activated, there must be a cycle (or else all of the initial activations on the nodes would have extinguished).<BR/><BR/>To achieve it, the mathematical operation is matrix multiplication.<BR/><BR/>See the graph as a matrix of 0's where i does not point to j, and 1 where it does.<BR/><BR/>Multiply your matrix by a vector of 1's, get the result and iterate : multiply n times (n is the number of nodes) your matrx by the last result. If the sum of your last vector is greater than 1, you have a graph.<BR/><BR/>I didn't count the brute version of this algorythm might not be linear at all, rather in the O(n*n). Optimizations can be done (iterate only while you still have 1's, etc.).subtenantehttps://www.blogger.com/profile/05077243411812540118noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-82720223399819379252009-01-30T10:35:00.000-08:002009-01-30T10:35:00.000-08:00@rjprins: True, "if node in stack" is a search loo...@rjprins: True, "if node in stack" is a search loop (but could easily be replaced by a hash table lookup as I said above). However "if node in todo" is a set membership test, which is a hash table lookup, not an implied loop.<BR/><BR/>To everyone recommending existing graphing libraries: I'm actually not interested in the cycles, I'm interesting in proving their absence, and then doing a bottom-up algorithm on the DAG. The graphs I am thinking of are not all that large; I'm expecting thousands of nodes but not millions (if you must know, it represents a program, not a social network :-).Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-6011328281120341382009-01-30T09:44:00.000-08:002009-01-30T09:44:00.000-08:00This is not a linear algorithm because statements ...This is not a linear algorithm because statements like "if node in stack" and "if node in all" are actually nested loops.<BR/><BR/>Here is another way to find cycles:<BR/><BR/>- count the number of incoming edges for each node. O(n+e)<BR/>- put each node with 0 incoming edges in a set S. O(n)<BR/>- while S has nodes:<BR/>- take a node n from S.<BR/>- delete n and update the number of incoming edges of the nodes connected to n. if any of those nodes now have 0 incoming edges, put them in S.<BR/>- endwhile O(n+e)<BR/>- if S is empty put there are still nodes left, you have cycle.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-67548353061887151722009-01-30T08:37:00.000-08:002009-01-30T08:37:00.000-08:00I would recommend checking out the networkx graph ...I would recommend checking out the <A HREF="http://networkx.lanl.gov/" REL="nofollow">networkx</A> graph library.<BR/><BR/>Apart from being quite mature, it can also find strongly connected parts, which seems to be what you're interested in.lorghttps://www.blogger.com/profile/10081475780192298906noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-6237401475402873872009-01-30T04:47:00.000-08:002009-01-30T04:47:00.000-08:00@Paul: I agree with you, the top variable is not u...@Paul: I agree with you, the top variable is not used, make only sense if it's:<BR/>"for node in EDGES(top):"Djabxhttps://www.blogger.com/profile/11580262714858657760noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-41206008431811182612009-01-30T00:06:00.000-08:002009-01-30T00:06:00.000-08:00http://grapy.googlecode.com has a strongly connect...http://grapy.googlecode.com has a strongly connected components function you can use for this as well.Cimarron Taylorhttps://www.blogger.com/profile/14309356161143663890noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-2956619092074694542009-01-29T17:08:00.000-08:002009-01-29T17:08:00.000-08:00Ah, true.Tarjan's algorithm can find *all* the cyc...Ah, true.<BR/><BR/>Tarjan's algorithm can find *all* the cycles in a directed graph (or rather, all the strongly connected components, which includes things more complicated than cycles), with the same worst case complexity as detecting a single cycle, (which, now that I read your post more carefully, is what you are doing here). It's interesting that it's possible to do this fast.<BR/><BR/>By the way, "for node in EDGES(node):" should probably read "for node in EDGES(top):".Paul Harrisonhttps://www.blogger.com/profile/16075937464283403018noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-45923924869408761292009-01-29T16:40:00.000-08:002009-01-29T16:40:00.000-08:00You could also make the function in to an iterable...You could also make the function in to an iterable so that it can find all cycles. Someone who wants just one could just call it and get the first element.slobberchopshttps://www.blogger.com/profile/06850195969044920625noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-85988869752610600312009-01-29T14:58:00.000-08:002009-01-29T14:58:00.000-08:00@Paul: I believe my algorithm can be linear time t...@Paul: I believe my algorithm can be linear time too (in something like the number of nodes+edges) with the iter-stack optimization and e.g. a set parallel to the stack to be able to test "node in stack" in constant time (what @Johannes pointed out). <BR/><BR/>That's assuming stack pushes and pops and hash table lookups are linear time, which IMO they are or can be made to be with enough trickery (e.g. pre-allocating a fixed stack).<BR/><BR/>@mlk: good point. Or 'todo' (I like short names :-).Guido van Rossumhttps://www.blogger.com/profile/12821714508588242516noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-48021726498212467392009-01-29T14:19:00.000-08:002009-01-29T14:19:00.000-08:00If you need to do this for large graphs, Tarjan's ...If you need to do this for large graphs, Tarjan's algorithm can do it in linear time.<BR/><BR/><A HREF="http://www.logarithmic.net/pfh/blog/01208083168" REL="nofollow">Here is a Python implementation.</A>Paul Harrisonhttps://www.blogger.com/profile/16075937464283403018noreply@blogger.comtag:blogger.com,1999:blog-4195135246107166251.post-1529103265206194922009-01-29T13:46:00.000-08:002009-01-29T13:46:00.000-08:00That's very nice. I think it would make it even mo...That's very nice. I think it would make it even more easy to read and understand if `all` was renamed to `unchecked`.Anonymousnoreply@blogger.com