Detecting a cycle in a graph
Frank Millman
frank at chagford.com
Sun Jan 14 03:30:31 EST 2018
Hi all
I am adding a bpm (Business Process Management) module to my accounting app.
A process is laid out as a flowchart, and is therefore a form of directed
graph, so I am getting into a bit of graph theory. I got some good ideas
from this essay - https://www.python.org/doc/essays/graphs/
I need to detect when a 'cycle' occurs - when a path loops back on itself
and revisits a node previously visited. I have figured out a way to do this,
but I have a problem.
A cycle occurs as a result of a node with more than one path leading out
from it. I am following the BPMN spec, and they call these nodes 'gateways',
so I will use that terminology. A gateway can optionally have a boolean
condition associated with it, which determines which path is followed. If a
given path loops back to an earlier node, a cycle is created.
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.
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.
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.
Thanks
Frank Millman
More information about the Python-list
mailing list