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

[Szabolcs Horvát]

Hi Tamas,

All this sounds good, but I am a bit uncomfortable with one thing:
using IGRAPH_INTERRUPTED to signal the stop.  This error code is used
to signal a user-interrupt checked through
igraph_allow_interruption().  When such an interruption is detected,
there is no expectation for the function to return anything
meaningful, only to free resources (i.e. ensure no memory leak).  The
interruption is handled as a sort of error condition which is passed
up to the calling igraph function.

In this case there would be no error, only a signal to stop the
search.  The top-level clique search function should not indicate an
error to its caller, it should return with IGRAPH_SUCCESS.  The
behaviour should be the same as with igraph_isomorphic_function_vf2()

It must be possible to distinguish between an interactive user
interruption (which is an error condition) and the callback function
requesting a stop (which is not an error).

Of course what you expect would work regardless because the _bk
function does not check for interruptions internally (yet). But what
if in the future someone adds a check there?


On 22 April 2016 at 18:31, Tamas Nepusz <address@hidden> wrote:
> 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.
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help