[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] MCS and result of "igraph_get_subisomorphisms_vf2"
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] MCS and result of "igraph_get_subisomorphisms_vf2" |
Date: |
Fri, 19 Jul 2013 23:39:07 +0200 |
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