Detecting a cycle in a graph
Frank Millman
frank at chagford.com
Tue Jan 16 00:00:49 EST 2018
"MRAB" wrote in message
news:1f67363c-4d2a-f5ac-7fa8-b6690ddbaf66 at 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
More information about the Python-list
mailing list