Detecting a cycle in a graph

[Frank Millman]

"Steven D'Aprano"  wrote in message news:p3f9uh$ar4$1 at blaine.gmane.org...

> On Sun, 14 Jan 2018 10:30:31 +0200, Frank Millman wrote:
>
> > I can detect a cycle in a path. It is possible for there to be more than
> > one gateway in the path. I want to identify the gateway that actually
> > triggered the cycle, but I have not figured out a way to do this.
>
> You don't need a gateway to get a cycle. Suppose you have nodes
>
>     A -> B -> C -> D -> B
>
> that's a cycle with no gateways.
>

[skip more good examples]

>
> The usual way of fixing this sort of thing for systems intended for non-
> expert use is to have a (user-configurable?) limit on the number of
> steps, and have the process raise an error once it reaches the limit.
>
> > After that, in the path returning to the previous node, there is another
> > gateway that checks a counter. If the boolean check fails three times,
> > terminate the process.
>
> What boolean check? You mentioned a counter -- that's normally considered
> to be an integer.
>

Sorry, I left out a couple of steps. In my imaginary process, every time the 
boolean check in the first gateway fails, it increments a counter. The 
second gateway checks the counter, and terminates the process if it exceeds 
a limit.

> Try googling for "Halting problem" to learn why you cannot, in general,
> prove that all cycles will eventually terminate. You may be able to
> identify *some* non-terminating graphs, but you cannot determine all of
> them.

I will do so. Thanks for clearing up some confusion and giving me some 
pointers.

Frank