Re: [igraph] maximal_cliques_template.h: a way to stop the search?

[Tamas Nepusz]

Hi,

> Maximal clique related functions are implemented (mostly) through
> maximal_cliques_template.h.  There is a RECORD macro where we can
> define how to record a clique that was found.  Is there a way to
> signal within this RECORD section that the clique search does not need
> to continue and the clique search function should now return (after
> doing all the necessary cleanup)?
Well, not with the current implementation, but I think it is not too
hard to modify the existing implementation.

Basically, what you need to do is:

- Formally state that a nonzero return value from
igraph*_maximal_cliques_bk (the backtracking step) is a request to
stop the search. (Right now the function always returns zero, but it
has an int return type, so you can safely return any igraph error code
there).

- Whenever igraph_*_maximal_cliques_bk is called, you have to check
whether there was a nonzero value returned and if so, stop the search
and propagate the error value back to the caller.

- At the topmost level where igraph_*_maximal_cliques_bk is called the
first time, you need to check the return value and interrupt the
search accordingly.

By the way, the RECORD macros currently don't do any error checking on
calls to igraph_vector_ptr_push_back() and alike, so errors from these
functions may go unnoticed, which is a Bad Thing (TM). I think the
best would be to:

1) update all RECORD macros with IGRAPH_CHECK() calls whenever we
perform an operation that may potentially return an error code
2) use the special (and currently undocumented) IGRAPH_INTERRUPTED
error code from the RECORD macros to signal that the user wants to
stop the search
3) make sure that nonzero return values from
igraph_*_maximal_cliques_bk are propagated upwards. (Surrounding every
such call except the topmost one with IGRAPH_CHECK() should suffice).
4) at the topmost call to igraph_*_maximal_cliques_bk, check whether
the error code is IGRAPH_INTERRUPTED; if not, return the error code to
the caller. Something like:

int ret = igraph_..._maximal_cliques_bk(...);
if (ret == IGRAPH_INTERRUPTED) {
    /* handle the interruption */
} else {
    /* let igraph handle the error */
    IGRAPH_CHECK(ret);
}

T.