Detecting a cycle in a graph

[Frank Millman]

"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