Re: [igraph] MCS and result of "igraph_get_subisomorphisms_vf2"

[Tamás Nepusz]

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?
There is no implementation for the MCS problem in igraph yet. If your graphs 
are not too large, you can try building the modular product manually (see 
http://en.wikipedia.org/wiki/Modular_product_of_graphs) and then find the 
largest clique in the modular product graph -- this will correspond to a 
solution of the MCS problem. Finding largest cliques is implemented in 
igraph_largest_cliques.

> 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.
Let's see. The edges in your first graph are:

0-1, 0-3, 1-2, 1-3, 2-3, 2-4, 3-4

The edges in the second graph are:

0-1, 1-2, 1-3, 2-3, 2-4, 3-4

The mapping vector is [4, 2, 3, 1, 0]. This describes the mapping _from_ the 
vertices of the _second_ graph _to_ the vertices of the _first_ graph. In other 
words, vertex 0 in the second graph is mapped to vertex 4 of the first graph, 
vertex 1 of the second graph is mapped to vertex 2 of the first graph and so 
on. So, let's take the edge list of the second graph and do all these 
replacements at once:

Replace 0 with 4; 1 with 2; 2 with 3; 3 with 1 and 4 with 0.

The remapped edge list is:

4-2, 2-3, 2-1, 3-1, 3-0, 1-0

Let's swap the order of vertices where the smaller vertex index comes second 
because I used the convention of writing the smaller index first when I wrote 
down the edge list of the first graph. This gives us:

2-4, 2-3, 1-2, 1-3, 0-3, 0-1

As you can see, this is a subset of the edge list of the first graph; only edge 
3-4 is missing. Therefore, the mapping describes a proper sub-isomorphism.

Cheers,
Tamas