"MRAB" wrote in message
news:1f67363c-4d2a-f5ac-7fa8-b6690ddba...@mrabarnett.plus.com...
On 2018-01-15 06:15, Frank Millman wrote:
> I start my cycle-detection with a node with 0 incoming connections.
>
> def find_cycle(node, path):
> for output in node.outputs:
> if output in path:
> print('Cycle found in', path)
> else:
> new_path = path[:]
> new_path.append(output)
> find_cycle(output, new_path)
>
> find_cycle(node, [node])
>
> This traverses every possible path in the graph. I think/hope that a
> typical
> business process will not grow so large as to cause a problem.
>
> If anyone can see a flaw in this, please let me know.
>
A couple of suggestions:
1. Instead of copying the list and appending, I'd do:
find_cycle(output, path + [output])
2. Lists are ordered, but searching them is O(n), so I'd pass a set too to
speed it up a bit:
def find_cycle(node, path, visited):
for output in node.outputs:
if output in visited:
print('Cycle found in', path)
else:
find_cycle(output, path + [output], visited | {output})
That will help as the paths get longer, although on a small graph, it
won't matter.
Both suggestions are much appreciated - so simple, and yet they improve my
code enormously.
I have never seen the use of '|' to update a set before, though now I check
the docs, it is there. It is very neat.
Many thanks
Frank
--
https://mail.python.org/mailman/listinfo/python-list
