[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: |
Nicholas Dahm |
Subject: |
Re: [igraph] Complex node attributes for subgraph isomorphism via vf2 |
Date: |
Wed, 18 Jan 2012 12:34:00 +1000 |
> 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