Re: [igraph] Complex node attributes for subgraph isomorphism via vf2

[Nicholas Dahm]

> In this case, take a look at the upcoming igraph 0.6 (currently in
> development stage), where the signature of
> igraph_subisomorphism_function_vf2() is extended to accomodate for
> vertex and edge "colors":
> 
> http://bazaar.launchpad.net/~igraph/igraph/0.6-main/view/head:/src/topology.c#L1801
> 
> Would this be a suitable solution for you (i.e. can you group your
> vertices into "classes" such that vertices in the same class are
> compatible with each other)?
Unfortunately there is no way to encode/group them effectively into
classes.

> Theoretically, the only modification required would be to call an
> external function here instead of doing a simple comparison.
Yes this would be best. I realise I may be the only person at present
requesting this extra functionality so do feel free to tell me if this
is too much effort, but I would like to propose the following.

I primarily program in C++ and am not very advanced with using functions
as parameters so please correct any mistakes/misconceptions about what
can/can't be done. For readability, I will shorten types.



////////////////////// BEGIN CODE //////////////////////////

// This new function handles node colourings for those who do not
// need/want to write their own handler function, and are using
// nodes coloured as ints
bool default_compat_fn(vector_t *g1_vec,
                       vector_t *g2_vec,
                       int g1_num, // node or edge num
                       int g2_num)
{
        vec_int_t *g1_vec_int = (vec_int_t)g1_vec;
        vec_int_t *g2_vec_int = (vec_int_t)g2_vec;
        if(g1_vec_int[g1_node_num] == g2_vec_int[g2_node_num])
                return true;
        else return false;
}

typedef bool compat_fn(vector *g1_attribs,
                       vector *g2_attribs,
                       int g1_num, // node or edge num
                       int g2_num);

int subisomorhpic_function_vf2(igraph_t *g1
                               igraph_t *g2
                               vector_t *g1_node_attribs
                               vector_t *g2_node_attribs
                               vector_t *g1_edge_attribs
                               vector_t *g2_edge_attribs
                               vector_t *map12,
                               vector_t *map21,
                               isohandler_t *function,
                        compat_fn *node_compat_fn = default_compat_fn,
                        compat_fn *edge_compat_fn = default_compat_fn)
{
        // In the function, keep the checks of whether attribs have
        // been passed in, but change:

        if (vertex_color1 && VECTOR(*vertex_color1)[cand1] !=
                        VECTOR(*vertex_color2)[cand2])

        // TO

        if (g1_node_attribs && !node_compat_fn(g1_node_attribs,
                        g2_node_attribs, cand1, cand2))
}

//////////////////////// END CODE ///////////////////////////


If what I have shown is mostly correct, and if igraph_vector_int_t is a
subclass of igraph_vector_t, then anyone who has written their code for
the colouring version will not have to even change their code.

Please let me know your thoughts. I am more than happy to do the coding
for this, but will require a little guidance/supervision to ensure I
don't mess anyone else's code up (this is my first time proposing
serious changes to the workings of a widely-used codebase).

cheers

Nick