Detecting a cycle in a graph

[Steven D'Aprano]

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.

If you do have gateways, who is to say which one is to blame? Or even 
that *any* of them is to blame?

    A -> (B) -> C -> F -> E
           \
            D -> E -> F

Why say that the gateway (B) is to blame for the cycle E -> F -> E?

I'm sure that if you draw some diagrams, you can come up with a scenario 
where a cycle is formed by the action of two gateways, either one on its 
own being harmless. Why blame one rather than the other?

For that matter, why are cycles necessarily harmful? So long as you can 
escape a cycle eventually, that's just a loop with an exit:

    A -> B -> C -> (D) -> E -> B
                     \
                      X

Now the path will loop B -> ... -> E and back to B, until the gateway D 
takes the alternate path and escapes.

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.


> I scribbled down a pseudo process on the back of an envelope. It has a
> gateway that can cause a cycle.
> 
> Before that, there is a gateway that checks for a 'fast-track'
> indicator. If true, it bypasses the next part of the process and jumps
> to the next stage.
> 
> 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.


> I can 'visually' identify the gateway that triggers the cycle, but I
> cannot figure out how to determine it 'logically'. My intention is that
> users can create their own processes, and we know that they can
> sometimes create a dog's breakfast, so I cannot rely on it being
> 'obvious'. Maybe there is no logical way of identifying it.
> 
> I am sure you will need more details if you want to assist, but maybe
> there is some literature you can point me to that explains these things
> in more detail.

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.



-- 
Steve