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

[Tamás Nepusz]

Hi Nick,

> // 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)
I assume that g1_vec and g2_vec are the "color" vectors. This seems good as 
long as you need only these two vectors to make decisions, but a more general 
solution would be to pass the graph pointer instead and let the user query 
anything he/she wants within the compatibility handler. Also, of course you 
will need igraph_bool_t instead of bool (plain C has no bool) and 
igraph_integer_t instead of int (for historical reasons, igraph_integer_t is 
actually a double, but this will probably change in 0.6 to a long int). It is 
also standard to add an extra "void* arg" parameter; this is a pointer that the 
user may pass in to igraph_subisomorphic_function_vf2 as the last argument and 
it just gets forwarded to the compatibility function and the isomorphism 
handler function. The purpose of this pointer to allow the user to pass in any 
extra variables that he/she may require to make decisions in the handler 
functions. So, the compatibility function signature would look like this:

typedef igraph_bool_t igraph_isocomp_t(const igraph_t*, igraph_integer_t, 
igraph_integer_t, void*);

> 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)
Again, here I'd keep the last void* argument that is currently there in the 
signature of igraph_subisomorphic_function_vf2 (because it is already passed to 
the isohandler_t function and it should also be passed to the compatibility 
handler). Also note that there are no default arguments in plain C, so you 
cannot write something like "compat_fn *node_compat_fn = default_compat_fn". 
More on avoiding the default argument down below.

>       if (g1_node_attribs && !node_compat_fn(g1_node_attribs,
>                       g2_node_attribs, cand1, cand2))
Here, I would write something like this:

igraph_bool_t nodes_compatible;
[...]
if (node_compat_fn == 0) {
    nodes_compatible = (vertex_color1 == 0 ? 1 : VECTOR(vertex_color1)[cand1] 
== VECTOR(vertex_color2)[cand2]);
} else {
    nodes_compatible = node_compat_fn(graph, cand1, cand2, arg);
}
if (!nodes_compatible) {
   /* whatever */
}

The advantage is that we can avoid a function call to the default node 
compatibility function at the expense of checking a pointer value, which is 
likely to be cheaper.

OR, we could simply assume that the compatibility function is an "add-on" to 
the color checks, i.e. if the color check fails then we can assume that the 
nodes are not compatible, otherwise we proceed with the compatibility function 
check.

> If what I have shown is mostly correct, and if igraph_vector_int_t is a 
> subclass of igraph_vector_t
Plain C does not know the concept of "subclasses". igraph_vector_t and 
igraph_vector_int_t are plain C structs with a similar structure and similar 
handler functions, but you cannot use an igraph_vector_int_t in place of an 
igraph_vector_t or vice versa.

Anyway, if you are happy to work on this, check out the latest code from our 
Bazaar repo and start hacking. I'll be happy to provide guidance should you get 
stuck. The "standard" way of doing this would be to

1) create an account on Launchpad (http://launchpad.net)

2) optionally create a blueprint where you describe roughly what you would like 
to implement and how (https://blueprints.launchpad.net/igraph/+addspec). I 
don't know whether you can add a blueprint to a project you are not a member of 
yet, but it's worth a try.

3) register a new branch of the codebase where you will work 
(https://code.launchpad.net/igraph/+addbranch) and link it to the blueprint if 
you have one.

4) check out your branch using Bazaar and start hacking.

5) once you are done, push the changes back to Launchpad and propose it for 
merging.

Cheers,
Tamas