[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Complex node attributes for subgraph isomorphism via vf2
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Complex node attributes for subgraph isomorphism via vf2 |
Date: |
Wed, 18 Jan 2012 11:59:47 +0100 |
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