[igraph] MCS and result of "igraph_get_subisomorphisms_vf2"

[Wen Cheng]

Hello!

Firstly, I wonder whether igraph can help find maximum common subgraph (or just common subgraphs) of two or more graphs. If so, could you please let me know which function can do that?

My second question is about the result of "igraph_get_subisomorphisms_vf2". I created two simple un-directed graphs with same node color and same edge color. Each of the two graphs has 5 nodes. However, one resultant mapping given by "igraph_get_subisomorphisms_vf2" looks not correct. Here is my code:

  igraph_t g1, g2;

  igraph_vector_t v1, v2;

  igraph_vector_int_t vertex_colors1, vertex_colors2;

  igraph_vector_ptr_t maps;

  igraph_vector_init(&v1, 14);

  VECTOR(v1)[0] = 0; VECTOR(v1)[1] = 1;

  VECTOR(v1)[2] = 1; VECTOR(v1)[3] = 3;

  VECTOR(v1)[4] = 0; VECTOR(v1)[5] = 3;

  VECTOR(v1)[6] = 3; VECTOR(v1)[7] = 4;

  VECTOR(v1)[8] = 3; VECTOR(v1)[9] = 2;

  VECTOR(v1)[10] = 1; VECTOR(v1)[11] = 2;

  VECTOR(v1)[12] = 2; VECTOR(v1)[13] = 4;

  igraph_create(&g1, &v1, 0, IGRAPH_UNDIRECTED);

  igraph_vector_init(&v2, 12);

  VECTOR(v2)[0] = 0; VECTOR(v2)[1] = 1;

  VECTOR(v2)[2] = 1; VECTOR(v2)[3] = 2;

  VECTOR(v2)[4] = 1; VECTOR(v2)[5] = 3;

  VECTOR(v2)[6] = 2; VECTOR(v2)[7] = 3;

  VECTOR(v2)[8] = 2; VECTOR(v2)[9] = 4;

  VECTOR(v2)[10] = 3; VECTOR(v2)[11] = 4;

  igraph_create(&g2, &v2, 0, IGRAPH_UNDIRECTED);

  igraph_vector_int_init(&vertex_colors1, igraph_vcount(&g1));

  igraph_vector_int_init(&vertex_colors2, igraph_vcount(&g2));

  igraph_vector_ptr_init(&maps, 0);

  igraph_get_subisomorphisms_vf2(&g1, &g2, &vertex_colors1, &vertex_colors2, 0, 0, &maps, 0, 0, 0);

Here are 4 resultant mappings:

0, 1, 2, 3, 4

0, 1, 3, 2, 4

4, 2, 1, 3, 0

4, 2, 3, 1, 0

The first three mappings make sense but the last one seems weird. I wonder whether you have any comment on it.

Thank you very much for any help!!

Best regards,

Wen