Detecting a cycle in a graph
Frank Millman
frank at chagford.com
Sun Jan 14 06:04:17 EST 2018
"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
More information about the Python-list
mailing list