On the design of igraph_eulerian_path

Development
1

While working on integrating the Eulerian functions into the Mathematica interface, I came across a small issue. The same issue will apply to other similar functions too, so I wanted to discuss it.

Currently, igraph_eulerian_path and igraph_eulerian_cycle will issue an error if the input is not Eulerian. When exposing these functions in a high-level interface, the simplest choice is to keep the same behaviour. This is reasonable in languages that have exceptions (like Python), but less so in languages that might indicate the lack of an Eulerian path with a certain return value (Mathematica, and, I presume, R).

In a typical usage situation, it may not be known in advance if the graph is Eulerian. In a language with exceptions, one may do (pseudocode):

try:
    eulerian_path(g)
except:
    # do something if g was not Eulerian

In a language where errors are not catchable exceptions, this may need to look like

if is_eulerian(g):
    eulerian_path(g)
else:
    # do something if g was not Eulerian

This duplicates the is_eulerian check, which is also done by eulerian_path internally.

In such languages, an expected failure such as an Eulerian path not existing is often better indicated by returning a special value, and not displaying an error message. I can implement this with the current design of the igraph_eulerian_path C function, but in order to do so I need an extra igraph_is_eulerian check, which is a waste.

I cautiously propose changing igraph_eulerian_path (and _cycle) so that instead of erroring out, it indicates that the graph is not Eulerian, with this prototype:

int igraph_eulerian_path(
    const igraph_t *graph, 
    igraph_bool_t *eulerian, 
    igraph_vector_t *edge_res, igraph_vector_t *vertex_res);

If the graph was not Eulerian, then eulerian gets set to false and edge_res and vertex_res are not set.

Any thoughts? Alternative solutions?

@Gabor, how would you expose this function in R?

2

I don’t mind if you change it. The ideal for R would be to throw an “igraph_not_eulerian_error” error I guess.