Detecting a cycle in a graph
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Detecting a cycle in a graph
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Generating SVG from turtle graphics
Steven D'Aprano wrote: > I'd like to draw something with turtle, then generate a SVG file from it. > > Is this possible? If this is a one-off job consider creating Postscript from the underlying Canvas: >>> import turtle >>> for i in range(12): ... turtle.forward(100) ... turtle.left(150) ... >>> turtle.getcanvas().postscript(file="tmp_turtle.ps") [...] Then convert to SVG with an external tool. It looks like ghostscript can do that: $ gs -dBATCH -dNOPAUSE -sDEVICE=svg -sOutputFile=tmp_turtle.svg tmp_turtle.ps -- https://mail.python.org/mailman/listinfo/python-list
Re: Detecting a cycle in a graph
"Steven D'Aprano" wrote in message news:[email protected]... 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Generating SVG from turtle graphics
maybe save to .png then use another tool to svg On 11 Jan 2018 15:06, "Steven D'Aprano" < [email protected]> wrote: > I'd like to draw something with turtle, then generate a SVG file from it. > > Is this possible? > > If not, is there something I can do which lets me plot lines, shapes and > curves and output to SVG? > > Ideally, I'd like to draw a figure pixel by pixel, and then have the SVG > library fit a bezier curve to it. > > > > > -- > Steve > > -- > https://mail.python.org/mailman/listinfo/python-list > -- https://mail.python.org/mailman/listinfo/python-list
Re: Generating SVG from turtle graphics
11.01.18 13:03, Steven D'Aprano пише: I'd like to draw something with turtle, then generate a SVG file from it. Is this possible? If not, is there something I can do which lets me plot lines, shapes and curves and output to SVG? You can translate the following Tcl/Tk recipe to Python/Tkinter: http://wiki.tcl.tk/4534. Or just run the code directly in the buildin Tcl interpreter. -- https://mail.python.org/mailman/listinfo/python-list
Re: Detecting a cycle in a graph
Am 14.01.18 um 09:30 schrieb Frank Millman: 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. I don't know if that helps, but there is a classic graph theory algorithm called "Floyd's cycle detector". The idea is to have a pointer move along the graph and a second one which runs at double the speed. If they meet, you found a cycle. It is not straight-forward to come up with this algorithm, which even runs in constant storage. ISTR that there are some variants which can give you the split point of the cycle, too. Christian -- https://mail.python.org/mailman/listinfo/python-list
Why does pylint give this warning?
The warning is 'C0103:Method name "__len__" doesn't conform to
'_?_?[a-z][A-Za-z0-9]{1,30}$' pattern' but it doesn't complain about __repr__
or __str__. If there is an explanation out in the wild my search fu has missed
it :-(
My setup on Ubuntu 17.10 is:-
$ pylint --version
Using config file /home/mark/.pylintrc
pylint 1.8.1,
astroid 1.6.0
Python 3.6.3 (default, Oct 3 2017, 21:45:48)
[GCC 7.2.0]
--
Kindest regards.
Mark Lawrence.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Detecting a cycle in a graph
Am 14.01.18 um 22:04 schrieb Christian Gollwitzer: Am 14.01.18 um 09:30 schrieb Frank Millman: 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. I don't know if that helps, but there is a classic graph theory algorithm called "Floyd's cycle detector". The idea is to have a pointer move along the graph and a second one which runs at double the speed. If they meet, you found a cycle. It is not straight-forward to come up with this algorithm, which even runs in constant storage. ISTR that there are some variants which can give you the split point of the cycle, too. And here is an algorithm to enumerate all cycles in a directed graph: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.335.5999&rep=rep1&type=pdf with an implementation in C++ here: https://github.com/hellogcc/circuit-finding-algorithm Christian -- https://mail.python.org/mailman/listinfo/python-list
Re: Why does pylint give this warning?
[email protected] wrote: > Why does pylint give this warning? No idea. > The warning is 'C0103:Method name "__len__" doesn't conform to > '_?_?[a-z][A-Za-z0-9]{1,30}$' pattern' but it doesn't complain about > __repr__ or __str__. If there is an explanation out in the wild my search > fu has missed it :-( > > My setup on Ubuntu 17.10 is:- > > $ pylint --version > Using config file /home/mark/.pylintrc > pylint 1.8.1, > astroid 1.6.0 > Python 3.6.3 (default, Oct 3 2017, 21:45:48) > [GCC 7.2.0] > > -- > Kindest regards. > > Mark Lawrence. I cannot replicate this with $ pylint --version Using config file /home/petto/.pylintrc pylint 1.8.1, astroid 1.6.0 Python 3.4.0 (default, Apr 11 2014, 13:05:11) [GCC 4.8.2] $ cat pylint_fodder.py class FooBar: def __len__(self): return 42 def __repr__(self): return "FooBar(length={})".format(len(self)) $ pylint pylint_fodder.py Using config file /home/petto/.pylintrc * Module pylint_fodder C: 1, 0: Missing module docstring (missing-docstring) C: 1, 0: Missing class docstring (missing-docstring) R: 1, 0: Too few public methods (0/2) (too-few-public-methods) --- Your code has been rated at 4.00/10 $ so the complaint is probably caused by your configuration file. Rename it, regenerate the default with $ pylint --generate-rcfile > ~/.pylintrc and reapply your changes -- I hope there aren't too many of them ;) -- until you see the warning message again. -- https://mail.python.org/mailman/listinfo/python-list
Re: Why does pylint give this warning?
> I cannot replicate this with
>
> $ pylint --version
> Using config file /home/petto/.pylintrc
> pylint 1.8.1,
> astroid 1.6.0
> Python 3.4.0 (default, Apr 11 2014, 13:05:11)
> [GCC 4.8.2]
>
> $ cat pylint_fodder.py
> class FooBar:
> def __len__(self):
> return 42
> def __repr__(self):
> return "FooBar(length={})".format(len(self))
>
> $ pylint pylint_fodder.py
> Using config file /home/petto/.pylintrc
> * Module pylint_fodder
> C: 1, 0: Missing module docstring (missing-docstring)
> C: 1, 0: Missing class docstring (missing-docstring)
> R: 1, 0: Too few public methods (0/2) (too-few-public-methods)
Ditto. Mark, do you have any tweaks in your .pylintrc file which might
affect it?
Skip
--
https://mail.python.org/mailman/listinfo/python-list
Re: Generating SVG from turtle graphics
On Sun, 14 Jan 2018 16:32:53 +0400, Abdur-Rahmaan Janhangeer wrote: > maybe save to .png then use another tool to svg PNG is a bitmap format[1], so you can't covert it to an SVG (a vector format) without guessing things like the start/end points of the lines, their slopes, etc... not to mention things like arcs. [1] RFC2083 -- https://mail.python.org/mailman/listinfo/python-list
Where is the usage of (list comprehension) documented?
Hi,
I see the following usage of list comprehension can generate a
generator. Does anybody know where this is documented? Thanks.
$ cat main.py
#!/usr/bin/env python
import sys
lines = (line.rstrip('\n') for line in sys.stdin)
print lines
lines = [line.rstrip('\n') for line in sys.stdin]
print lines
$ seq 10 | ./main.py
at 0x1101ecd70>
['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
--
Regards,
Peng
--
https://mail.python.org/mailman/listinfo/python-list
Re: Where is the usage of (list comprehension) documented?
On Mon, Jan 15, 2018 at 10:01 AM, Peng Yu wrote:
> Hi,
>
> I see the following usage of list comprehension can generate a
> generator. Does anybody know where this is documented? Thanks.
>
> $ cat main.py
> #!/usr/bin/env python
>
> import sys
> lines = (line.rstrip('\n') for line in sys.stdin)
> print lines
>
> lines = [line.rstrip('\n') for line in sys.stdin]
> print lines
> $ seq 10 | ./main.py
> at 0x1101ecd70>
> ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
>
When you use square brackets, you're creating a generator, as in your
second example. Your first example is a slightly different beast
called a "generator expression". If you search for that in the docs or
on the web, you'll find what you want.
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
Re: Where is the usage of (list comprehension) documented?
> When you use square brackets, you're creating a generator, as in your > second example. Your first example is a slightly different beast > called a "generator expression". If you search for that in the docs or > on the web, you'll find what you want. Thanks. Can the documentation be found by `help()` in python? -- Regards, Peng -- https://mail.python.org/mailman/listinfo/python-list
Re: Where is the usage of (list comprehension) documented?
Peng Yu writes: > > When you use square brackets, you're creating a generator, as in your > > second example. Your first example is a slightly different beast > > called a "generator expression". If you search for that in the docs or > > on the web, you'll find what you want. > > Thanks. Can the documentation be found by `help()` in python? The ‘help’ command is not intended to provide comprehensive user documentation. Rather, it is intended primarily to provide a reminder of syntax and purpose of specific API. It is not a replacement for having the Python documentation available. -- \ “The history of Western science confirms the aphorism that the | `\ great menace to progress is not ignorance but the illusion of | _o__)knowledge.” —Daniel J. Boorstin, historian, 1914–2004 | Ben Finney -- https://mail.python.org/mailman/listinfo/python-list
Re: Where is the usage of (list comprehension) documented?
On Sun, Jan 14, 2018 at 3:01 PM, Peng Yu wrote: > Hi, > > I see the following usage of list comprehension can generate a > generator. Does anybody know where this is documented? Thanks. Here's the (a?) generator expression PEP: https://www.python.org/dev/peps/pep-0289/ Here's a presentation I put together on this and related topics a while back: http://stromberg.dnsalias.org/~strombrg/Intro-to-Python/Python%20Generators,%20Iterators%20and%20Comprehensions%202014.pdf FWIW, [a for a in range(2)] is a list comprehension; it's eager. And (a for a in range(2)) is a generator expression; it's lazy. HTH -- https://mail.python.org/mailman/listinfo/python-list
Re: Why does pylint give this warning?
On Sunday, January 14, 2018 at 10:32:44 PM UTC, Skip Montanaro wrote:
> > I cannot replicate this with
> >
> > $ pylint --version
> > Using config file /home/petto/.pylintrc
> > pylint 1.8.1,
> > astroid 1.6.0
> > Python 3.4.0 (default, Apr 11 2014, 13:05:11)
> > [GCC 4.8.2]
> >
> > $ cat pylint_fodder.py
> > class FooBar:
> > def __len__(self):
> > return 42
> > def __repr__(self):
> > return "FooBar(length={})".format(len(self))
> >
> > $ pylint pylint_fodder.py
> > Using config file /home/petto/.pylintrc
> > * Module pylint_fodder
> > C: 1, 0: Missing module docstring (missing-docstring)
> > C: 1, 0: Missing class docstring (missing-docstring)
> > R: 1, 0: Too few public methods (0/2) (too-few-public-methods)
>
> Ditto. Mark, do you have any tweaks in your .pylintrc file which might
> affect it?
>
> Skip
Having followed Peter's advice everything worked a treat once I'd put my
changes into the new configuration file. Having compared it to the old one it
looks as if I'd upgraded pylint but didn't regenerate the config file, as there
were a number of obvious changes. Thanks for the help guys, and if nothing
else this is on the record for anyone with the same or similar problems.
--
Kindest regards.
Mark Lawrence.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Detecting a cycle in a graph
"Christian Gollwitzer" wrote in message news:[email protected]... Am 14.01.18 um 22:04 schrieb Christian Gollwitzer: > Am 14.01.18 um 09:30 schrieb Frank Millman: >> 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. > > I don't know if that helps, but there is a classic graph theory > algorithm called "Floyd's cycle detector". The idea is to have a pointer > move along the graph and a second one which runs at double the speed. If > they meet, you found a cycle. It is not straight-forward to come up with > this algorithm, which even runs in constant storage. ISTR that there are > some variants which can give you the split point of the cycle, too. And here is an algorithm to enumerate all cycles in a directed graph: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.335.5999&rep=rep1&type=pdf with an implementation in C++ here: https://github.com/hellogcc/circuit-finding-algorithm I appreciate the input, Christian, but I am afraid both of those were over my head :-( I think/hope that a business process graph does not require such a complex solution. Here is my cycle-detecting algorithm. In BPMN terms, each node can have 0->* incoming connections, and 0->* outgoing connections. Any node with 0 incoming is deemed to start the process. Normally there is only one such node. Any node with 0 outgoing represents the end of an 'active path'. If there is more than one such node, all 'active' ones must reach the end before the process is finished. There is no formal definition of an 'active path', and I can think of a few corner cases which could prove problematic, but normally the meaning is clear. 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. Frank -- https://mail.python.org/mailman/listinfo/python-list
