Computations should be interruptible (e.g. support Ctrl-C)

[szhorvat]

This is continuing from https://github.com/Qiskit/retworkx/issues/505#issuecomment-985100707

As someone who uses network analysis software daily, I think that the ability to interrupt computations is critical. Many (including myself) like to do data analysis interactively in a notebook environment. There is nothing more annoying than when a function turns out to take much longer to finish than expected, forcing me to kill the notebook kernel and start from the beginning again.

Many problems relating to graphs do not have polynomial time solutions, which means that it is often impossible to predict how long a computation will take before starting it. It's very easy to jump from 2 seconds to 2 days by changing the input only slightly. Interruptibility is a critical in such cases. retworkx does not seem to have any algorithms of this type implemented yet, but I expect it will (an exact Steiner tree solver?)

It is a core principle of both igraph and Mathematica (two systems I use interactively regularly), that no computation should ever hang. Everything must be interruptible. This is a solvable problem.

@mtreinish If I understand you correctly, you mentioned in the comment I linked at the top that the difficulty is that retworkx has a pure-Rust component that does not know about Python. The same is the case with igraph: it has a core C library that does not know about any high-level language. Then there are interfaces to several high-level language. The C library has a feature where the user can set an "interruption handler" function. This function is called periodically during any computation, and the return value signals if the computation should be interrupted. Feel free to ask about the details.

[georgios-ts]

I've looked a bit of how you handled this in igraph, and the way I understand it, is that in the C level you've defined a thread local interruption handler https://github.com/igraph/igraph/blob/master/src/core/interruption.c#L27 that you typically call at the main while/for loop of the functions. Then, in python-igraph, when you initialize the module, you set the interruption handler to call PyErr_CheckSignals https://github.com/igraph/python-igraph/blob/master/src/_igraph/igraphmodule.c#L920. My questions are:

1. Do users of the C API worry to initialize the handler properly?
2. Are there any multithreaded functions in igraph? If so, how do you stop all threads if an interruption occurs? In retworkx, some functions run in parallel, and in order to safely call https://docs.rs/pyo3/0.15.1/pyo3/prelude/struct.Python.html#method.check_signals a thread must hold https://docs.rs/pyo3/0.15.1/pyo3/prelude/struct.Python.html# but it's !Send and !Sync (i.e can't be safely shared between threads).

Many problems relating to graphs do not have polynomial time solutions

Right now, the only function in retworkx that does not run in polynomial time is is_subgraph_isomorphic and we have a call_limit argument that controls the "resources" you want to spend in the computation.

[szhorvat]

1. Do users of the C API worry to initialize the handler properly?

No. If the handler is not set, it is not used.

2. Are there any multithreaded functions in igraph?

Not really, but in the future we might move in that direction. I am not feeling sufficiently qualified in parallel programming to give a satisfactory answer. Including @ntamas as well, who is the maintainer of igraph's Python interface. Is it not safe to call PyErr_CheckSignals from multiple threads?

(With Mathematica, which I am much more familiar with, the interruption handler can be safely called from multiple threads.)

---

Right now, the only function in retworkx that does not run in polynomial time is is_subgraph_isomorphic and we have a call_limit argument that controls the "resources" you want to spend in the computation.

It is of course your choice to decide whether interruptions would be supported. It was merely a suggestion.

When running a standalone script, it is not necessary to support interruptions. You can just kill the Python process. However, for interactive work (think Jupyter notebook or command line) I find it to be very useful, even critical. Just yesterday, my session got locked up by the Fruchterman-Reingold (FR) layout function because I accidentally created a large graph, and FR did not support interruptions (that's fixed now). This shows that it's not just non-polynomial problems that require interruptibility.

If the library would ever be used from a GUI program (a less likely use case), interruptions are also useful.

[ntamas]

PyErr_CheckSignals() does not do anything when called from a non-main thread, according to the docs:

If the function is called from a non-main thread, or under a non-main Python interpreter, it does nothing and returns 0.

As for multi-threading: igraph is not thread-safe at the moment and it's unlikely that it will become thread-safe in the near term. Cross-platform threading is a mess if you want to stick to plain C and don't want to bring in any heavyweight dependencies to handle the intricacies (you cannot simply use pthreads because that won't work on Windows). I'd rather move in the direction that we parallelize certain functions with OpenMP where parallelization makes sense. This would restrict threading to a limited scope (to OpenMP-enabled blocks) where they are easier to reason about.

[IvanIsCoding]

The argmin crate implements interruption of computations, we could try getting some inspiration from their work: https://argmin-rs.org/blog/version-v0-8-0/

[IvanIsCoding]

This crate could be interesting to handle this case: https://docs.rs/ctrlc/latest/ctrlc/